$\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO

We study constrained online convex optimization with adversarial convex losses and constraints ($\mathsf{C}\mathsf{O}\mathsf{C}\mathsf{O}$). 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{C}\mathsf{C}\mathsf{V}$) over the entire horizon. Existing algorithms achieve $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ $\mathsf{C}\mathsf{C}\mathsf{V}$. We show that an online policy can achieve $O(\sqrt{T\log T})$ regret and $O({\log }^{2}T)$ $\mathsf{C}\mathsf{C}\mathsf{V}$, reducing the $\mathsf{C}\mathsf{C}\mathsf{V}$ from polynomial to polylogarithmic while retaining near-optimal regret. 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 $\mathsf{C}\mathsf{C}\mathsf{V}$.