$\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO
We study constrained online convex optimization with adversarial convex losses and constraints ($\mathsf{COCO}$). At each round \(t\in[T]\), a learner selects \(x_t\) from a \(d\)-dimensional convex decision set \(\mathcal X\), after which an adaptive adversary reveals a convex cost function \(f_t\) and constraint function \(g_t\). Consequently, the learner incurs cost \(f_t(x_t)\) and constraint violation \(\max\{0,g_t(x_t)\}\), and aims to simultaneously minimize regret and cumulative constraint violation ($\mathsf{CCV}$) over the entire horizon. Existing algorithms achieve \(O(\sqrt{T})\) regret and \(\widetilde O(\sqrt{T})\) $\mathsf{CCV}$. We show that an online policy can achieve \(...
| Authors | Dhruv Sarkar, Abhishek Sinha |
|---|---|
| Primary category | cs.LG |
| Published | 2 October 2026 |
| Last updated at source | 2 October 2026 |
Popularity, last 2 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
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.