Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

arXiv:2609.32729 · math.OC, cs.LG · Submitted 2026-09-26 · Read on arXiv

math.OC, cs.LG

Submitted: 2026-09-26

Updated: 2026-09-26

Terminology

• Regret — 12× in this paper · explained in 3 episodes
• Adam — 5× in this paper · explained in 2 episodes
• Adaptation — 4× in this paper · explained in 1 episode
• International Conference on Learning Representations — 3× in this paper
• Adaptivity — 2× in this paper · explained in 1 episode
• Adaptive Gradient Methods — 1× in this paper · explained in 1 episode

Sources

• A Simple Convergence Proof of Adam and Adagrad
• Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Asymptotic Convergence and Stability of Adaptive Gradient Methods in Smooth Non-convex Optimization
• On the Convergence of mSGD and AdaGrad for Stochastic Optimization
• Better Theory for SGD in the Nonconvex World
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods
• Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimization
• On the Convergence of Adam and Beyond
• New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
• Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability
• Petrov-Galerkin operator inference with application to stability-encouraging identification