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

We study constrained online convex optimization with adversarial convex losses and constraints (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 (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. 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.