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

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action x_t \in X \subset \mathbb{R}^d, a convex loss function f_t and a convex constraint function g_t that drives the constraint g_t(x)\le 0 are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions f_t and g_t for all t ahead of time, and chooses a static optimal action that is feasible with respect to all g_t(x)\le 0. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of O(\sqrt{T}) and CCV of O(T^{1/3}) for d=2 [Balasundaram et al., 2026], and simultaneous regret of O(\sqrt{T}) and CCV of O(\sqrt{T}) for any d [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is Ω(T^{\frac{d-1}{2d}}). This is the first such lower bound result.