Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

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 propose 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(\sqrt{T})$ regret and $O(\sqrt{T})$ CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least $Ω((\log T)^{(d-1)/(d+1)}/\log\log T)$. For convex losses, we prove CCV lower bounds $Ω(T^{(d-1)/(2(d+3))})$ for weakly adaptive algorithms and $Ω(T^{(d-1)/(2d)})$ for NP-OGD. Finally, for the constrained experts special case over $N$ experts, an active Hedge algorithm attains $O(\sqrt{T\log N})$ regret and $O(N)$ CCV, with a matching minimax CCV lower bound for sufficiently large horizons.

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to $O(\log T)$ with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.

We study constrained online convex optimization with adversarial constraints and conditionally unbiased, finite-variance observations of constraint values and gradients. Under common feasibility, our \LEDGER\ algorithm attains $O(\sqrt T)$ expected regret and $O(\sqrt{T\log(eT)})$ expected budget violation, the largest cumulative overspend over any window. It uses a reflected exponential potential, clipped signed observations, and predictable adaptive regularization, with one feedback triple and one projection per round. Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed. A Gaussian testing lower bound proves that the budget rate has optimal horizon dependence under square-root regret at fixed positive noise, including the logarithm. The same obstruction holds for terminal violation, so the logarithm is not a cost of maximizing over windows; an $O(\sqrt T)$ budget bound instead forces linear regret. In contrast, fixed positive Gaussian value noise yields a joint regret--hard-violation lower bound of $Ω(\min\{σ,1\}T/\log^2 T)$, even with exact gradients in one dimension. The hard-violation construction matches arbitrarily many moments while preserving a feasible-endpoint gap and constant endpoint probabilities. Together, the bounds separate uncertainty about hard feasibility from learnable signed budgets. Deterministic restarts remove the horizon input without changing either upper rate.