ilde{O}(sqrt{T}) Regret and Polylogarithmic Constraint Violation for COCO

arXiv:2610.03983v1 Announce Type: new Abstract: We study constrained online convex optimization with adversarial convex losses and constraints (mathsf{COCO}). At each round (tin[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 (O(sqrt{Tlog T})) regret and (O(log^2 T)) mathsf{CCV}, reducing the mathsf{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, Grunbaum'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{CCV}.

Source: arXiv cs.LG | 2026-10-06

Related