Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
2026-07-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a problem where a learner picks actions over time while facing certain rules (constraints) and losses. After choosing an action, the current loss and constraint are revealed, and the learner wants to do well compared to a best fixed action chosen with full knowledge of all losses and constraints. Previous work showed methods balancing the regret (how much worse the learner does compared to the best fixed action) and how much the learner violates constraints. The authors provide a new result proving a fundamental limit: the cumulative constraint violation cannot be smaller than a certain rate depending on the dimension, which sets a lower bound on performance for existing methods.
online convex optimizationregretconstraint violationconvex constraintsOGD (Online Gradient Descent)projection algorithmstatic regretlower boundsdimension dependence
Authors
Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze
Abstract
The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{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.