{"ID":6536245,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10808","arxiv_id":"2607.10808","title":"Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)","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.","short_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 simulta...","url_abs":"https://arxiv.org/abs/2607.10808","url_pdf":"https://arxiv.org/pdf/2607.10808v1","authors":"[\"Haricharan Balasundaram\",\"Karthick Krishna Mahendran\",\"Rahul Vaze\"]","published":"2026-07-12T15:36:04Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}