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

Constrained online convex optimization (OCO) requires a learner to minimize regret against adversarial costs while ensuring that every decision satisfies a convex constraint. While the combination of Online Gradient Descent (OGD) and the Polyak feasibility step is computationally efficient—requiring only one constraint evaluation and one subgradient per round—existing analyses rely on coarse, worst-case bounds. This paper re-examines the regret of this algorithm by retaining two specific quantities typically discarded in standard proofs: the actual sum of squared gradient norms (G_T) and the cumulative squared displacement caused by feasibility projections (the Polyak correction, P_T).

The author proves a refined regret bound that replaces the worst-case gradient envelope with the observed accumulation of gradients and incorporates the Polyak correction as a negative term, which effectively tightens the bound. This improvement is achieved without any modification to the underlying algorithm. Furthermore, the paper introduces AdaOGD-PFS, an adaptive-step-size algorithm that automatically scales to the observed gradient magnitudes. This variant achieves an O(sqrt(G_T)) regret bound, which is often significantly smaller than the standard O(G_f * sqrt(T)) rate. Empirical evaluations on ball- and halfspace-constrained problems show that these analytical refinements yield a 38–43% improvement in the regret bound.

In safety-critical applications like power systems or autonomous control, violating constraints is often unacceptable. This work provides a more precise theoretical understanding of existing, computationally efficient algorithms, allowing researchers to obtain tighter performance guarantees without increasing computational overhead or requiring stronger assumptions. By bridging the gap between worst-case analysis and data-dependent performance, the paper offers a more realistic assessment of how these algorithms behave in practice.