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

• URL: http://arxiv.org/abs/2607.10808v1
• Date: Sun, 12 Jul 2026 15:36:04 GMT
• Title: Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
• Abstract summary: The objective is to simultaneously minimize the static regret and cumulative constraint violation.<n>This paper shows that the CCV of the OGD+Projection algorithm is $(Tfracd-12d)$.
• Score: 4.167459103689586
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions [5.533296779866529]
  We extend CONES to allow for loss functions $f_t'$s to also change over time.<n>We show that any online algorithm with sublinear it anytime regret has a movement cost of $left(log Tright)$.
  arXiv  Detail & Related papers  (2026-09-10T08:13:27Z)
• Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension [80.40589035328607]
  We study the problem of minimizing a convex function $f : [0,1] to [0,1]$ using a zero-order oracle with subGaussian noise.<n>We propose a computationally efficient algorithm that achieves the optimal $O(1/sqrtT)$ convergence rate, matching the lower bound.
  arXiv  Detail & Related papers  (2026-07-14T16:10:33Z)
• Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction [7.798233121583888]
  We consider Constrained Online Convtrained (COCO) with adversarially chosen constraints.<n>For strongly convex losses, our algorithm improves the $mathsfCCV$ to $O(sqrtT)$ while maintaining the $O(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2026-05-20T12:40:27Z)
• Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization [4.167459103689586]
  The objective is to simultaneously minimize the static regret and cumulative constraint violation.<n>It is widely believed that CCV is $(sqrtT)$ for all algorithms that ensure that regret is $O(sqrtT)$ with the worst case input for any $dge 2$.
  arXiv  Detail & Related papers  (2026-03-21T06:19:35Z)
• Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  We revisit the Online Convex Optimization problem with adversarial constraints.<n>We propose an online policy that achieves $tildeO(sqrtdT+ Tbeta)$ regret and $tildeO(dT1-beta)$ CCV.
  arXiv  Detail & Related papers  (2025-05-10T17:23:10Z)
• $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization [16.99491218081617]
  The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV)<n>An algorithm is proposed that guarantees a static regret of $O(sqrtT)$ and a CCV of $mincV, O(sqrtTlog T) $, where $cV$ depends on the distance between the consecutively revealed constraint sets.
  arXiv  Detail & Related papers  (2025-02-07T15:47:04Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints.<n>We focus on a setting where the algorithm has access to predictions of the loss and constraint functions.<n>Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems.<n>Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems. The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
  arXiv  Detail & Related papers  (2023-03-06T17:54:33Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.