We study constrained online convex optimization with adversarial convex costs and constraints (COCO). At each round t\in[T], a learner selects x_t from a d-dimensional convex decision set X, after which an adaptive adversary reveals a convex cost function f_t and constraint function g_t. Consequently, the learner incurs a cost of f_t(x_t) and a constraint violation of \max{0,g_t(x_t)}, and aims to simultaneously minimize regret and cumulative constraint violation (CCV) over the entire horizon. Existing algorithms achieve O(\sqrt{T}) regret and \widetilde O(\sqrt{T}) CCV. We show that an online policy can achieve O(\sqrt{T\log T}) regret and O(\log^2 T) CCV, reducing the CCV from polynomial to polylogarithmic while retaining near-optimal regret. When all cost functions are either α-exp-concave or β-strongly convex, the algorithm achieves O(\log T) regret with the same CCV bound as above. Our approach combines continuous Hedge with elimination on shrinking feasible sets. The key observation is that whenever the mean of the Hedge distribution violates a constraint, Grünbaum's inequality guarantees that a constant fraction of the Hedge probability mass is eliminated. We use an adaptive learning-rate schedule and a potential function coupling the surviving volume with the learning rate to convert this probability-mass reduction into a bound of O(\log^2 T) on the CCV.
$\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO
We study constrained online convex optimization with adversarial convex costs and constraints ($\mathsf{COCO}$). At each round $t\in[T]$, a learner selects $x_t$ from a $d$-dimensional convex decision set $X$, after which an adaptive adversary reveals a convex cost function…
- Preview

- Year
- 2026
- Hosting
- Excerpt onlyCC-BY-NC-4.0
Cite
Notes
Only stored in your browser.
Attribution
- Abstract & full text
- arxiv.org/abs/2610.03983CC-BY-NC-4.0
- TL;DR
- Semantic Scholar