# Breaking the O(√T) Cumulative Constraint Violation Barrier while Achieving O(√T) Static Regret in Constrained Online Convex Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 16 references that are in the map.
- First posted on arXiv 21 Mar 2026.

## Builds on (most cited first, 7 of 7)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)

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

- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)](https://mlsanity.com/paper/2607.10808/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action xt ∈ X subset ℝd, a convex loss function ft and a convex constraint function gt that drives the constraint gt(x)≤ 0 are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions ft and gt for all t ahead of time, and chooses a static optimal action that is feasible with respect to all gt(x)≤ 0. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of O(√T) and CCV of O(√T) or (CCV of O(1) in specific cases Vaze and Sinha [2025], e.g. when d=1) have been proposed. It is widely believed that CCV is Omega(√T) for all algorithms that ensure that regret is O(√T) with the worst case input for any d≥ 2. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of O(√T) regret and CCV of O(T1/3) when d=2.