🤖 machine learning

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

This paper establishes the first lower bound of $\Omega(T^{\frac{d-1}{2d}})$ on the cumulative constraint violation for the OGD+Projection algorithm in constrained online convex optimization, demonstrating that its performance is fundamentally limited by the problem's dimensionality.

Original authors: Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes video game called "Constrained Online Convex Optimization." In this game, you are a brave explorer (the "learner") trying to navigate a dark, shifting maze. Every turn, you have to pick a spot to stand (your "action"). Immediately after you pick your spot, the game reveals two things: a "loss" (how much score you lose for standing there) and a "constraint" (a new invisible wall that says, "You must not be on the wrong side of this line").

Your goal is twofold:

Minimize Regret: Don't lose too many points compared to a super-smart cheat-sheet player who knew all the walls and score traps before the game even started.
Minimize Constraint Violation (CCV): Don't spend too much time standing on the wrong side of the walls. If you do, you accumulate "violation points."

For a long time, the best strategy everyone knew was called OGD+Projection. It's like a robot that takes a step forward based on the last score, then immediately "projects" (bounces) itself back inside the safe zone if it accidentally stepped out.

The Big Question: How Bad Can the Robot Get?

Scientists have been trying to figure out the worst-case scenario for this robot. They already knew the robot could keep its score loss low (about $\sqrt{T}$ , where $T$ is the total number of turns). But what about the violation points?

Previous research showed that for a 2D maze, the robot's violation points grew slowly, like $T^{1/3}$ . For mazes of any size (any dimension $d$ ), the worst-case violation was thought to be around $\sqrt{T}$ .

Here is the paper's main discovery: The authors proved that the OGD+Projection robot is actually forced to rack up a specific amount of violation points, no matter how cleverly you design the maze. They showed that in a maze with $d$ dimensions, the violation points will grow at least as fast as $T^{\frac{d-1}{2d}}$ .

The "Impossible Maze" Construction

To prove this, the authors didn't just guess; they built a specific, nasty maze designed to trick the robot. Imagine the maze is made of concentric spheres (like layers of an onion) that get slightly smaller as you go deeper.

The Layers: The maze has $M$ layers. In each layer, there are many "safe spots" arranged in a circle (or a higher-dimensional sphere).
The Trap: The game reveals a new wall (constraint) that cuts off exactly one of those safe spots.
The Robot's Dilemma: The robot is standing on the safe spot. The wall appears. The robot must move to the next safe spot to stay safe. But because the walls keep appearing in a specific, rotating pattern, the robot is forced to take tiny, inefficient steps.
The Rotation: The authors used a clever mathematical trick (involving rotating vectors) to ensure that the robot's path winds around the sphere, hitting a new "cut" every single time.

The authors proved that in this specific setup, the robot cannot avoid stepping out of bounds. Every time a new wall appears, the robot is forced to violate the constraint by a tiny amount. When you add up all these tiny violations over the whole game, the total grows exactly at the rate of $T^{\frac{d-1}{2d}}$ .

What This Means for the "Best" Algorithm

This result is a "lower bound." Think of it like a speed limit sign that says, "You cannot go slower than 50 mph." The paper proves that the OGD+Projection algorithm cannot do better than this specific violation rate.

What it rules out: It rules out the hope that OGD+Projection is a "perfect" algorithm that could somehow achieve a much lower violation rate (like $O(1)$ or something tiny) for all types of mazes. The paper shows that for certain tricky mazes, the robot is fundamentally limited.
What it confirms: It confirms that the previous upper-bound estimates (the "best case" scenarios) were not just loose guesses; they were actually close to the truth. The algorithm is doing as well as it possibly can, given the geometry of the problem.

How Sure Are They?

The authors didn't just run a computer simulation or suggest this might be true. They provided a rigorous mathematical proof. They constructed the exact maze, defined the exact steps the robot takes, and calculated the exact number of violation points.

They showed that for any dimension $d \ge 2$ , there exists a scenario where the violation is $\Omega(T^{\frac{d-1}{2d}})$ . The symbol $\Omega$ means "at least this much."

So, if you are playing this game in a 2D world ( $d=2$ ), the violation is at least $T^{1/4}$ . If you are in a 3D world ( $d=3$ ), it's at least $T^{2/6}$ (which simplifies to $T^{1/3}$ ). As the dimensions get higher, the exponent gets closer to $1/2$ , meaning the robot has to work harder and harder to stay within the rules.

The Takeaway

This paper is like finding a hidden speed bump on the highway that everyone thought was smooth. It tells us that the "OGD+Projection" robot, while very good, has a hard limit on how well it can handle the worst-case constraints. It can't be perfect. The authors have mathematically proven that in a world with $d$ dimensions, the cumulative constraint violation will always grow at least as fast as $T^{\frac{d-1}{2d}}$ . This is the first time such a limit has been proven, closing the gap between what we hoped the algorithm could do and what it is mathematically forced to do.

Technical Summary: Lower Bound on the Cumulative Constraint Violation for the OGD+Projection Algorithm

Problem Statement
This paper addresses the problem of Constrained Online Convex Optimization (COCO). In this setting, an online learner operates over $T$ rounds. At each round $t$ , the learner selects an action $x_t$ from a convex feasible set $X \subset \mathbb{R}^d$ . Subsequently, an adversary reveals a convex loss function $f_t$ and a convex constraint function $g_t$ . The learner incurs a loss $f_t(x_t)$ and a constraint violation if $g_t(x_t) > 0$ . The objective is to minimize two metrics simultaneously compared to a static benchmark $x^\star$ that knows all future functions and chooses a feasible action ( $g_t(x^\star) \le 0$ for all $t$ ):

Static Regret: The difference between the cumulative loss of the learner and the benchmark.
Cumulative Constraint Violation (CCV): The sum of positive parts of constraint violations, $\sum_{t=1}^T \max(g_t(x_t), 0)$ .

The paper focuses specifically on the OGD+Projection algorithm (proposed by Vaze and Sinha, 2025), which performs an Online Gradient Descent (OGD) step followed by a projection onto the intersection of all constraint sets revealed up to that point. While upper bounds for this algorithm are known, its lower bound performance regarding CCV had not been established.

Methodology and Construction
To derive the lower bound, the authors construct a specific "hard" instance of the COCO problem. The construction relies on a geometric arrangement of points and constraints in $d$ -dimensional space.

Vector Construction (Theorem 2): The core of the proof involves constructing an ordered collection of unit vectors $U_d(\rho)$ on the unit sphere $S^d$ . These vectors are designed to satisfy two properties:
- Separation: Any two distinct vectors are separated by an angular distance of at least $\rho$ .
- Local Connectivity: Consecutive vectors in the ordered sequence are separated by an angular distance of at most $A_d \rho$ .
- Cardinality: The number of such vectors scales as $\Omega(\rho^{-(d-1)})$ .
  This construction is achieved via an inductive process on the dimension $d$ , utilizing spherical caps and longitude/latitude traversals to ensure the ordering and separation properties hold.
Constraint and Action Trajectory:
- The action space $X$ is defined as a ball $B(0, D)$ .
- The time horizon $T$ is divided into $M = T^{1/d}$ "layers," each corresponding to a concentric sphere $C_m$ with shrinking radii.
- Within each layer $m$ , the algorithm is forced to traverse a sequence of $n$ points $z^{(m)}_i$ lying on sphere $C_m$ . These points are derived by scaling the unit vectors from the construction above.
- Constraint Design: For each point $z^{(m)}_i$ , a new constraint is introduced that is a half-space tangent to the next smaller sphere $C_{m+1}$ at the projection of $z^{(m)}_i$ . This constraint effectively "cuts off" a spherical cap centered at $z^{(m)}_i$ .
- Feasibility Logic: Due to the angular separation $\rho$ and the careful selection of the cut angle, the constraint associated with $z^{(m)}_i$ removes only that specific point from the current layer's set of candidates, leaving all other points in the sequence feasible. However, the point $z^{(m)}_i$ itself becomes infeasible immediately after the constraint is revealed.
Cost Function Design:
- The loss functions are designed to guide the OGD+Projection algorithm to follow the pre-defined trajectory $z_1, z_2, \dots, z_P$ (where $P$ is the total number of points).
- At the start of each phase (when a new constraint is revealed), the algorithm incurs a projection distance because the current action is infeasible with respect to the new constraint.
- During the subsequent time steps within a phase, the loss functions are linear and oriented to move the algorithm from the projected point back to the next target point in the sequence, ensuring the algorithm stays on the intended path.

Key Results
The paper establishes the first lower bound for the CCV of the OGD+Projection algorithm.

Theorem 1: There exists a COCO instance with diameter $2D$ and Lipschitz constant $G$ such that the CCV of the OGD+Projection algorithm is $\Omega(T^{\frac{d-1}{2d}})$ .
Derivation: The total CCV is the sum of violations incurred at the "phase heads" (when new constraints are introduced). There are $P \approx T^{\frac{d+1}{2d}}$ such phases. At each phase head, the algorithm incurs a violation of order $T^{-1/d}$ . Multiplying these yields:
$\text{CCV} \approx T^{\frac{d+1}{2d}} \times T^{-\frac{1}{d}} = T^{\frac{d-1}{2d}}$
Dimensional Dependence: The result highlights that the lower bound depends on the dimension $d$ . For $d=2$ , the bound is $\Omega(T^{1/3})$ , which matches the known upper bound for $d=2$ (Balasundaram et al., 2026). For general $d$ , the bound is $\Omega(T^{\frac{d-1}{2d}})$ .

Significance and Claims
The authors claim this work provides the first lower bound result for the CCV of the OGD+Projection algorithm. The primary significance of this result is that it demonstrates the existing upper bound analysis for this algorithm is not fundamentally loose.

Specifically, the paper notes that while the OGD+Projection algorithm achieves a CCV of $O(T^{1/3})$ for $d=2$ and $O(\sqrt{T})$ universally, the derived lower bound of $\Omega(T^{\frac{d-1}{2d}})$ shows that the algorithm's performance is tight with respect to the dimension $d$ in the worst case. For $d=2$ , the lower bound $\Omega(T^{1/3})$ matches the upper bound, confirming optimality for that dimension. For higher dimensions, the gap between the lower bound and the universal $O(\sqrt{T})$ upper bound suggests that while the algorithm is robust, the specific geometric structure of the constraints can force a violation rate that scales with dimension.

The paper does not propose new algorithms or applications but serves to characterize the theoretical limits of the current state-of-the-art OGD+Projection approach in constrained online optimization.

The Big Question: How Bad Can the Robot Get?

The "Impossible Maze" Construction

What This Means for the "Best" Algorithm

How Sure Are They?

The Takeaway

More like this