# A Geometric Approach to Constrained Online Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 20 May 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [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)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [Breaking the O(√T) Cumulative Constraint Violation Barrier while Achieving O(√T) Static Regret in Constrained Online Convex Optimization](https://mlsanity.com/paper/2603.20671/) (2026)

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

- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets](https://mlsanity.com/paper/2608.29074/) (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)
- [tildeO(√T) Regret and Polylogarithmic Constraint Violation for COCO](https://mlsanity.com/paper/2610.03983/) (2026)

## Abstract (arXiv)

We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved O(log T) regret with O(√Tlog T) CCV for strongly convex losses, and O(√T) regret with O(√Tlog T) CCV for convex losses. We present NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves O(log T) regret and O(log T) CCV; for convex losses it achieves O(√T) regret and O(√T) CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least Omega((log T)(d-1)/(d+1)/loglog T). For convex losses, we prove CCV lower bounds Omega(T(d-1)/(2(d+3))) for weakly adaptive algorithms and Omega(T(d-1)/(2d)) for NP-OGD. Finally, for the constrained experts special case over N experts, an active Hedge algorithm attains O(√Tlog N) regret and O(N) CCV, with a matching minimax CCV lower bound for sufficiently large horizons.