Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Not on the map. Why?
Abstract (arXiv)
AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Omega(log T/√ T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/√T).
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 32 of its 47 references that are in the map. First posted on arXiv 26 Sep 2026.
Builds on
32 of 47 references.
References · 32
- 2019On the Convergence of Adam and Beyondcited by 841
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
- 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
- 2020A Simple Convergence Proof of Adam and Adagradcited by 171
- 2020Better Theory for SGD in the Nonconvex Worldcited by 158
- 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
- 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
- 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
- 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
- 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
- 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
- 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
20 more
- 2018Online Adaptive Methods, Universality and Accelerationcited by 51
- 2017Variants of RMSProp and Adagrad with Logarithmic Regret Boundscited by 50
- 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
- 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
- 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
- 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
- 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 35
- 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
- 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
- 2024AdaGrad under Anisotropic Smoothnesscited by 22
- 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
- 2024Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailedcited by 18
- 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
- 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 15
- 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
- 2021On the Last Iterate Convergence of Momentum Methodscited by 10
- 2022On the Convergence of mSGD and AdaGrad for Stochastic Optimizationcited by 7
- 2025Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problemscited by 5
- 2026Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimizationcited by 3
- 2026Long-Run Dynamics of AdaGrad-Norm: Trajectory Stability and Asymptotic Stationaritycited by 1
Built on by
Not cited yet.