Small Gradient Norm Regret for Online Convex Optimization
stat.ML, cs.LG, math.OC
Submitted: 2026-01-20
Updated: 2026-09-21
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses.
Terminology
Abstract
This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the G regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the G regret strictly refines the existing L (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the G regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
Sources
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
- A Smooth Approximation Framework for Weakly Convex Optimization
- On the Properties of Convex Functions over Open Sets
- Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
- Handbook of Convergence Theorems for (Stochastic) Gradient Methods
- Non-Stationary Bandit Convex Optimization: An Optimal Algorithm with Two-Point Feedback
- Online Learning: A Modern Introduction Using Convex Optimization
- Less Regret via Online Conditioning
- Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with H\"older Smoothness
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
- Online Conformal Prediction for Non-Exchangeable Panel Data
- Deep Time-Series Forecasting in 10 Years: A Survey