Research map / Bandits and online learning / Online convex optimization and games
$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a projected-OGD algorithm for constrained online convex optimization that projects onto the nested feasible sets S_t, achieving O(√T) static regret and an instance-dependent CCV bound, combined with a switching scheme that caps CCV at O(√T log T).
Problem
Constrained online convex optimization with time-varying convex constraints, aiming to simultaneously minimize static regret and cumulative constraint violation (CCV) without Slater's condition.
Approach
Take an OGD step on the last loss and project onto the most recently revealed nested feasible set S_t, so CCV is controlled by the geometry (mean width, shape) of the nested sets rather than treated as a regret problem; a Switch algorithm falls back to a universal O(√T log T) CCV method once CCV exceeds √T log T.
Key results
- Projected OGD over nested sets achieves O(√T) static regret.
- CCV bounded by instance-dependent V = O(sqrt(d)(1/c*)^d D), which is O(1) for spheres and axis-parallel cuboids.
- Switch algorithm achieves CCV min{V, O(√T log T)} with O(√T) regret; for OCS (f_t=0) CCV is O(d^{d/2} D).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use nested-set projections after the online gradient step | COCO algorithm · COCO | CCV: O(\sqrt{T}\log T) -> O\left(\sqrt{d} \left(\frac{1}{c^\star}\right)^{d}D\right) | Helped |
| Switch to the prior COCO algorithm when accumulated CCV reaches the threshold | Online Algorithm for COCO · COCO | CCV: \min\left\{O\left(\sqrt{d} \left(\frac{1}{c^\star}\right)^{d}D\right), O(\sqrt{T}\log T)\right\} | Helped |
| Use spherical nested constraint sets | Online Algorithm for COCO · COCO with spherical nested constraint sets | CCV: O(\sqrt{T}\log T) -> O(1) | Helped |
| Use axis-parallel cuboid nested constraint sets | Online Algorithm for COCO · COCO with axis-parallel cuboid nested constraint sets | CCV: O(\sqrt{T}\log T) -> O(1) | Helped |
| Use a monotonic instance with progressively increasing projection angles | Online Algorithm for COCO · COCO, d=2 | CCV: O(GD) | Helped |
| Set all cost functions to zero | Online Algorithm for COCO · OCS | CCV: O(\sqrt{T}\log T) -> O\left(d^{d/2} D\right) | Helped |
| Use the prior state-of-the-art algorithm instead of geometry-based projections | COCO · COCO with fixed one-dimensional cost and constraint functions | CCV: \Omega(\sqrt{T}\log T) | Hurt |
Surprising findings
- The prior state-of-the-art algorithm has CCV Omega(√T log T) even in d=1 with fixed f and g, where O(1) CCV is achievable.
- For d=2 under a monotonic angle condition on projection hyperplanes, CCV is O(GD) independent of T.
Limitations
- CCV bound depends on the instance geometry constant c* and can be large or T-dependent for badly shaped sets, requiring the Switch fallback.
- Open question of O(1) or o(√T) CCV for general sets remains unresolved; the d=2 result needs a monotonicity assumption.
- No empirical experiments reported.
Experimental setup
Metrics: static regret cumulative constraint violation
Baselines: Algorithm from prior COCO work with O(√T log T) CCV primal-dual COCO methods drift-plus-penalty COCO methods
Builds on: online gradient descent drift-plus-penalty nested convex body chasing
Closest papers by meaning
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.93)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.92)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.89)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.88)
- Constrained Online Convex Optimization with Polyak Feasibility Steps (ICML 2025 · similarity 0.88)
- Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.