# Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization

arXiv: https://arxiv.org/abs/2406.04592 · HTML: https://mlsanity.com/paper/2406.04592/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 38 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 27 of 27)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [A new regret analysis for Adam-type algorithms](https://mlsanity.com/paper/2003.09729/) (2020)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [Asymptotic study of stochastic adaptive algorithm in non-convex landscape](https://mlsanity.com/paper/2012.05640/) (2020)
- [A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Acceleration](https://mlsanity.com/paper/1808.03408/) (2018)
- [Revisiting Convergence of AdaGrad with Relaxed Assumptions](https://mlsanity.com/paper/2402.13794/) (2024)
- [On the complexity of finding stationary points of smooth functions in one dimension](https://mlsanity.com/paper/2209.07513/) (2022)
- [The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions](https://mlsanity.com/paper/2104.05468/) (2021)

## Built on by (most cited first, 16 of 16)

- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Norm](https://mlsanity.com/paper/2505.11840/) (2025)
- [Better Convergence Guarantees for Sign-Based Momentum Methods](https://mlsanity.com/paper/2507.12091/) (2025)
- [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [Optimizer-Model Consistency: Full Finetuning with the Same Optimizer as Pretraining Forgets Less](https://mlsanity.com/paper/2605.06654/) (2026)
- [Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad](https://mlsanity.com/paper/2605.18694/) (2026)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [Convergence Rate Analysis of the AdamW-style Shampoo: Unifying One-Sided and Two-Sided Preconditioning](https://mlsanity.com/paper/2601.07326/) (2026)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)
- [A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise](https://mlsanity.com/paper/2608.09004/) (2026)
- [A regret minimization approach to fixed-point iterations](https://mlsanity.com/paper/2509.21653/) (2025)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)
- [Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds](https://mlsanity.com/paper/2609.32729/) (2026)
- [Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients](https://mlsanity.com/paper/2609.37787/) (2026)

## Abstract (arXiv)

Adaptive gradient methods, such as AdaGrad, are among the most successful optimization algorithms for neural network training. While these methods are known to achieve better dimensional dependence than stochastic gradient descent (SGD) for stochastic convex optimization under favorable geometry, the theoretical justification for their success in stochastic non-convex optimization remains elusive. In fact, under standard assumptions of Lipschitz gradients and bounded noise variance, it is known that SGD is worst-case optimal in terms of finding a near-stationary point with respect to the l2-norm, making further improvements impossible. Motivated by this limitation, we introduce refined assumptions on the smoothness structure of the objective and the gradient noise variance, which better suit the coordinate-wise nature of adaptive gradient methods. Moreover, we adopt the l1-norm of the gradient as the stationarity measure, as opposed to the standard l2-norm, to align with the coordinate-wise analysis and obtain tighter convergence guarantees for AdaGrad. Under these new assumptions and the l1-norm stationarity measure, we establish an upper bound on the convergence rate of AdaGrad and a corresponding lower bound for SGD. In particular, we identify non-convex settings in which the iteration complexity of AdaGrad is favorable over SGD and show that, for certain configurations of problem parameters, it outperforms SGD by a factor of d, where d is the problem dimension. To the best of our knowledge, this is the first result to demonstrate a provable gain of adaptive gradient methods over SGD in a non-convex setting. We also present supporting lower bounds, including one specific to AdaGrad and one applicable to general deterministic first-order methods, showing that our upper bound for AdaGrad is tight and unimprovable up to a logarithmic factor under certain conditions.