Small Gradient Norm Regret for Online Convex Optimization
TL;DR
A new problem-dependent regret measure for online convex optimization with smooth losses that strictly refines the existing small loss regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision.
Abstract
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. 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.
