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 xt ∈ X subset ℝd, a convex loss function ft and a convex constraint function gt that drives the constraint gt(x)≤ 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 ft and gt for all t ahead of time, and chooses a static optimal action that is feasible with respect to all gt(x)≤ 0. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of O(√T) and CCV of O(T1/3) for d=2 [Balasundaram et al., 2026], and simultaneous regret of O(√T) and CCV of O(√T) for any d [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is Omega (T^fracd-12d). This is the first such lower bound result.