A Geometric Approach to Constrained Online Learning
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(\sqrt{T\log T})$ CCV for strongly convex losses, and $O(\sqrt{T})$ regret with $O(\sqrt{T}\log 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(...
| Authors | Dhruv Sarkar, Abhishek Sinha |
|---|---|
| Primary category | cs.LG |
| Published | 20 May 2026 |
| Last updated at source | 22 July 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.