# MSTGD:A Memory Stochastic sTratified Gradient Descent Method with an Exponential Convergence Rate

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 21 Feb 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [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)
- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Large-Scale Visual Speech Recognition](https://mlsanity.com/paper/1807.05162/) (2018)
- [A Study of Gradient Variance in Deep Learning](https://mlsanity.com/paper/2007.04532/) (2020)
- [Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization](https://mlsanity.com/paper/2103.17182/) (2021)
- [A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity](https://mlsanity.com/paper/1710.07783/) (2017)

## Abstract (arXiv)

The fluctuation effect of gradient expectation and variance caused by parameter update between consecutive iterations is neglected or confusing by current mainstream gradient optimization algorithms.Using this fluctuation effect, combined with the stratified sampling strategy, this paper designs a novel underlineMemory underlineStochastic sunderlineTratified Gradient Descend(underlineMSTGD) algorithm with an exponential convergence rate. Specifically, MSTGD uses two strategies for variance reduction: the first strategy is to perform variance reduction according to the proportion p of used historical gradient, which is estimated from the mean and variance of sample gradients before and after iteration, and the other strategy is stratified sampling by category. The statistic  barGmst designed under these two strategies can be adaptively unbiased, and its variance decays at a geometric rate. This enables MSTGD based on barGmst to obtain an exponential convergence rate of the form λ2(k-k0)(λ∈ (0,1),k is the number of iteration steps,λ is a variable related to proportion p).Unlike most other algorithms that claim to achieve an exponential convergence rate, the convergence rate is independent of parameters such as dataset size N, batch size n, etc., and can be achieved at a constant step size.Theoretical and experimental results show the effectiveness of MSTGD