# On the Convergence of mSGD and AdaGrad for Stochastic Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 26 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [Don't Decay the Learning Rate, Increase the Batch Size](https://mlsanity.com/paper/1711.00489/) (2017)
- [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)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [Asymptotic study of stochastic adaptive algorithm in non-convex landscape](https://mlsanity.com/paper/2012.05640/) (2020)
- [A Robust Accelerated Optimization Algorithm for Strongly Convex Functions](https://mlsanity.com/paper/1710.04753/) (2017)

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

- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality](https://mlsanity.com/paper/2305.17665/) (2023)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [Shuffling Momentum Gradient Algorithm for Convex Optimization](https://mlsanity.com/paper/2403.03180/) (2024)
- [Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds](https://mlsanity.com/paper/2609.32729/) (2026)

## Abstract (arXiv)

As one of the most fundamental stochastic optimization algorithms, stochastic gradient descent (SGD) has been intensively developed and extensively applied in machine learning in the past decade. There have been some modified SGD-type algorithms, which outperform the SGD in many competitions and applications in terms of convergence rate and accuracy, such as momentum-based SGD (mSGD) and adaptive gradient algorithm (AdaGrad). Despite these empirical successes, the theoretical properties of these algorithms have not been well established due to technical difficulties. With this motivation, we focus on convergence analysis of mSGD and AdaGrad for any smooth (possibly non-convex) loss functions in stochastic optimization. First, we prove that the iterates of mSGD are asymptotically convergent to a connected set of stationary points with probability one, which is more general than existing works on subsequence convergence or convergence of time averages. Moreover, we prove that the loss function of mSGD decays at a certain rate faster than that of SGD. In addition, we prove the iterates of AdaGrad are asymptotically convergent to a connected set of stationary points with probability one. Also, this result extends the results from the literature on subsequence convergence and the convergence of time averages. Despite the generality of the above convergence results, we have relaxed some assumptions of gradient noises, convexity of loss functions, as well as boundedness of iterates.