analiza aiqbench
This paper advances the theoretical foundations of online convex optimization by introducing $G^\star$ regret, a metric that offers sharper bounds than existing measures when loss functions exhibit vanishing curvature. By establishing rigorous upper and lower bounds across dynamic and bandit settings, the work provides refined convergence analyses for stochastic algorithms in the interpolation regime. These contributions are significant for researchers developing next-generation machine learning optimizers where gradient behavior critically impacts performance guarantees.
Small Gradient Norm Regret for Online Convex Optimization
arXiv:2601.13519v4 Announce Type: replace-cross 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.
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.
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2601.13519 [stat.ML]
(or arXiv:2601.13519v4 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2601.13519 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 209 cuvinte
Subiecte conexe
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
arXiv · 15 iun. 2026
Block-Norm Geometries for Online Mirror Descent with Sparse Losses
arXiv · 14 sept. 2026
Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
arXiv · 10 sept. 2026
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
arXiv · 9 sept. 2026