Small Gradient Norm Regret for Online Convex Optimization
This work provides a refined regret analysis for online convex optimization, which is incremental but offers potential improvements in scenarios with vanishing curvature, benefiting researchers in optimization and machine learning.
The paper tackles the problem of online convex optimization by introducing a new regret measure called $G^\star$ regret, which depends on cumulative squared gradient norms at the hindsight decision, and shows it can be arbitrarily sharper than existing measures, with theoretical bounds and extensions to dynamic regret and bandit settings.
This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the $G^\star$ regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight $\sum_{t=1}^T \|\nabla \ell(x^\star)\|^2$. We show that the $G^\star$ regret strictly refines the existing $L^\star$ (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^\star$ 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.