🤖 machine learning

Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

This paper introduces a tighter, data-dependent regret analysis for constrained online convex optimization that incorporates observed gradient accumulation and a nonnegative Polyak correction term, leading to the proposal of the adaptive AdaOGD-PFS algorithm which achieves improved $O(\sqrt{G_T})$ regret while maintaining per-round feasibility.

Original authors: Wentao Zhang

Published 2026-07-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Wentao Zhang

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 where you have to make a move every second. The game world is constantly changing, throwing new challenges at you that you can't predict. Your goal is to score as many points as possible (minimize your "regret" or missed opportunities) compared to the best possible strategy you could have used if you knew the future. But there's a catch: every move you make must stay inside a specific, invisible safety zone. If you step outside, you crash the game. This is the world of Constrained Online Convex Optimization. It's the math behind self-driving cars avoiding pedestrians, power grids balancing loads without blackouts, and doctors adjusting medication doses in real-time. The core problem is simple: how do you learn and adapt quickly without ever breaking the rules?

For a long time, the best way to handle this was a method called "Online Gradient Descent" combined with a "Polyak feasibility step." Think of this like a robot walking through a foggy maze. It takes a step forward based on where it thinks the exit is (the gradient). If that step pushes it toward a wall, it immediately takes a tiny, calculated step back to stay safe (the Polyak step). This method is known to be very good at keeping the robot safe and learning efficiently, but the math used to prove how good it is was a bit like using a sledgehammer to crack a nut. The old math assumed the worst-case scenario for every single step the robot took, essentially saying, "The walls might be made of steel, and the robot might always trip." This made the safety guarantees look much weaker than they actually were in real life.

This paper, titled "Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization," takes a fresh look at that same robot and the same safety steps. The authors, led by Wentao Zhang, realized that the old math was being too pessimistic. They discovered that by paying closer attention to the actual steps the robot took (the "data-dependent" part) and the specific little corrections it made to stay safe (the "Polyak corrections"), they could prove the robot is actually much smarter and safer than previously thought. They didn't invent a new robot or a new way to walk; they just found a better way to measure how well the existing robot performs.

Here is what they found:

1. The "Real-World" Score is Better than the "Worst-Case" Score
The old math calculated the robot's performance by assuming every single step it took was as difficult as possible. It was like grading a student's test by assuming every question was the hardest one in the book, even if the student only got easy questions. The authors showed that if you look at the actual difficulty of the questions the robot faced (the sum of the actual gradients), the score improves dramatically. In their experiments, this simple switch from "worst-case" to "real-world" data tightened the performance guarantee by about 34–37%. It's like realizing your robot isn't walking through a minefield every day; it's mostly walking on a smooth path with just a few bumps.

2. The "Safety Step" is a Hidden Superpower
The second discovery is even more clever. When the robot takes a step and realizes it's about to hit a wall, it uses a "Polyak step" to bounce back. The old math treated this bounce as a neutral event—it just said, "Okay, it's back inside." But the authors realized that this bounce actually tightens the mathematical guarantee of the robot's performance. Every time the robot has to correct its path, it creates a "geometric slack" in the math that was previously ignored. They found a mathematical term, which they call the "Polyak correction," that acts like a bonus point for the robot. Because this correction is always positive (it's a bonus), it subtracts from the robot's total "regret" score. In their experiments, this bonus shaved off another 1–8% of the error, making the total improvement between 38% and 43% better than the old estimates.

3. A Smarter Robot for the Future
Based on these insights, the authors proposed a new version of the algorithm called AdaOGD-PFS. Imagine a robot that doesn't just walk at a fixed speed, but learns to speed up when the path is easy and slow down when it gets tricky. This new robot uses the "real-world" data to adjust its steps on the fly. The result is a robot that is just as safe as the old one but comes with a mathematical guarantee that is much tighter and doesn't require knowing the "worst-case" difficulty in advance. In their tests, this adaptive robot performed competitively against the fixed-speed one, achieving a regret bound that is potentially much smaller than the standard worst-case estimate.

What This Means for You
The authors are very clear about what they did and didn't do. They didn't create a new way to solve the problem from scratch; they took an existing, proven method and showed that the math describing it was too conservative. They proved mathematically that their new, tighter bounds are always better than or equal to the old ones. They tested this on computer simulations with thousands of rounds, showing that in real-world-like scenarios, the old math was overestimating the difficulty by a huge margin.

They also ruled out a few things. They didn't claim that their method works for every possible type of constraint without any assumptions (they still need the constraint to be "convex," which is a fancy way of saying the safety zone doesn't have weird, jagged holes). They also noted that while their new adaptive robot is great, it still needs a little bit of help to guarantee safety in the very first few steps if the starting point isn't perfect.

In short, this paper is a victory for precision. It shows that in the world of safety-critical AI, we don't always need to build a new engine; sometimes, we just need to look at the dashboard with sharper eyes and realize the car is actually running better than the manual said. By tracking the actual data and the specific corrections made to stay safe, we can trust our algorithms a little more and push them a little further.

Technical Summary: Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

Problem Statement
The paper addresses the problem of Constrained Online Convex Optimization (OCO), where a learner must sequentially select decisions $x_t$ to minimize cumulative regret against adversarially chosen convex cost functions $f_t$ , while satisfying a convex constraint $g(x) \le 0$ at every round. This setting is critical for safety-sensitive domains (e.g., power systems, autonomous control) where transient constraint violations are unacceptable. The specific challenge lies in the computational intractability of projecting onto the feasible set $X = \{x : g(x) \le 0\}$ when $g$ is a general convex function. The standard approach, Online Gradient Descent (OGD) with a Polyak feasibility step (OGD-PFS), offers a computationally efficient alternative by projecting onto a linearized half-space approximation of the constraint using only the constraint value $g(x_t)$ and a single subgradient. While OGD-PFS is known to achieve $O(\sqrt{T})$ regret with per-round feasibility, the paper argues that the existing theoretical analysis of this algorithm is suboptimal and relies on coarse worst-case relaxations.

Methodology and Analysis
The authors provide a refined regret analysis of the existing OGD-PFS algorithm (Hutchinson & Alizadeh, 2025) without modifying the algorithmic procedure itself. The analysis identifies two specific quantities that standard worst-case proofs discard but which can be retained to tighten the bound:

Data-Dependent Gradient Accumulation ( $G_T$ ): Instead of bounding the sum of squared gradient norms by the worst-case envelope $G_f^2 T$ (where $G_f$ is the supremum of gradients over the domain), the analysis retains the observed accumulation $G_T = \sum_{t=1}^T \|\nabla f_t(x_t)\|^2$ .
Polyak Correction ( $P_T$ ): The analysis utilizes the strong Pythagorean inequality for projections rather than the standard non-expansiveness property. This retains the cumulative squared displacement $\delta_t = \|y_t - \Pi_{H_t}(y_t)\|^2$ incurred by the Polyak step when it corrects an iterate $y_t$ that has violated the linearized constraint. The cumulative correction is defined as $P_T = \sum_{t=1}^T \delta_t$ .

By retaining these terms, the authors derive a refined regret bound (Theorem 1) for the fixed-step-size algorithm:
$\text{Reg}_T \le \frac{2R^2}{\eta} + \frac{\eta}{2} G_T - \frac{1}{2\eta} P_T + \frac{G_f \rho}{\sigma} T$
This bound improves upon the prior state-of-the-art by replacing $G_f^2 T$ with $G_T$ and introducing a strictly negative term $-\frac{1}{2\eta} P_T$ . The total improvement $\Delta_T$ is proven to be non-negative, vanishing only in the degenerate case where gradients are uniformly maximal and the Polyak step is never active.

Building on this, the paper proposes AdaOGD-PFS, an adaptive-step-size variant that sets $\eta_t = c / \sqrt{\epsilon_0 + \sum_{i<t} \|\nabla f_i(x_i)\|^2}$ . This algorithm achieves an $O(\sqrt{G_T})$ regret bound, potentially significantly smaller than $O(G_f \sqrt{T})$ , while preserving per-round feasibility guarantees.

Key Results

Theoretical Tightening: The refined bound (Theorem 1) is uniformly no worse than the prior bound and strictly tighter in non-degenerate cases. The improvement decomposes into two independent sources: gradient refinement (replacing worst-case with observed gradients) and the Polyak correction (accounting for the slack in the projection inequality).
Adaptive Rate: Theorem 2 establishes that AdaOGD-PFS achieves $O(\sqrt{G_T})$ regret, adapting to the actual gradient magnitudes observed during execution without requiring prior knowledge of the worst-case gradient bound $G_f$ .
Empirical Validation: Experiments on ball-constrained and halfspace-constrained instances ( $T=10,000$ $T = 10, 000$ ) demonstrate that the refined bounds are valid upper bounds on actual regret.
- The refined bound (Theorem 1) reduces the gap to the actual regret by 38–43% compared to the prior bound.
- The gradient refinement component contributes 34–37% of this improvement, while the Polyak correction contributes 1–8%.
- In an adversarial worst-case experiment where gradients are constant at the maximum ( $G_T = G_f^2 T$ ), the gradient refinement vanishes, yet the Polyak correction still provides a 49.9% tightening, confirming its structural independence from gradient adaptation.

Significance and Claims
The paper claims that the existing analysis of OGD-PFS has been "loose" by discarding information naturally available in the algorithm's iterates. The significance of this work lies in:

Tighter Bounds without Algorithmic Change: Demonstrating that the standard OGD-PFS algorithm already possesses better theoretical properties than previously recognized, simply by refining the analysis to track $G_T$ and $P_T$ .
First Instantiation of Polyak Correction: Identifying $P_T$ as a measurable, data-dependent quantity in OCO regret bounds. While the slack in the strong projection inequality is implicit in convex analysis, this work explicitly instantiates it as a negative term in the regret bound, providing a new mechanism for tightening guarantees in constrained settings.
Adaptive Feasibility: Proposing AdaOGD-PFS as a practical method to achieve data-dependent rates ( $O(\sqrt{G_T})$ ) in constrained settings while maintaining the strict per-round feasibility required for safety-critical applications.

The authors note that while the regret bounds are tightened, the feasibility bounds remain identical to prior work. They also clarify that the "no knowledge of $G_f$ " claim for AdaOGD-PFS applies to the regret rate, but achieving per-round feasibility in their analysis still relies on parameters tuned using $G_f$ (or a known strictly feasible starting point). The work suggests that the techniques of retaining data-dependent gradients and projection slacks are generalizable to other constrained optimization frameworks, including mirror descent and Frank-Wolfe variants.

More like this