{"id":"arxiv/2601.13519","url":"https://arxiv.org/abs/2601.13519","tags":["stat.ML","cs.LG","math.OC"],"score":0,"title":"Small Gradient Norm Regret for Online Convex Optimization","domain":"stat.ML","source":"arxiv","authors":["Wenzhi Gao","Chang He","Madeleine Udell"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-01-20","reactions":{}}