# Gradient-Variation Bound for Online Convex Optimization with Constraints

arXiv: https://arxiv.org/abs/2006.12455 · HTML: https://mlsanity.com/paper/2006.12455/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

## Built on by (most cited first, 6 of 6)

- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Constrained Online Convex Optimization with Memory and Predictions](https://mlsanity.com/paper/2603.21375/) (2026)

## Abstract (arXiv)

We study online convex optimization with constraints consisting of multiple functional constraints and a relatively simple constraint set, such as a Euclidean ball. As enforcing the constraints at each time step through projections is computationally challenging in general, we allow decisions to violate the functional constraints but aim to achieve a low regret and cumulative violation of the constraints over a horizon of T time steps. First-order methods achieve an O(√T) regret and an O(1) constraint violation, which is the best-known bound under the Slater's condition, but do not take into account the structural information of the problem. Furthermore, the existing algorithms and analysis are limited to Euclidean space. In this paper, we provide an instance-dependent bound for online convex optimization with complex constraints obtained by a novel online primal-dual mirror-prox algorithm. Our instance-dependent regret is quantified by the total gradient variation V_*(T) in the sequence of loss functions. The proposed algorithm works in general normed spaces and simultaneously achieves an O(√V_*(T)) regret and an O(1) constraint violation, which is never worse than the best-known ( O(√T), O(1) ) result and improves over previous works that applied mirror-prox-type algorithms for this problem achieving O(T2/3) regret and constraint violation. Finally, our algorithm is computationally efficient, as it only performs mirror descent steps in each iteration instead of solving a general Lagrangian minimization problem.