# On the linear convergence of the stochastic gradient method with constant step-size

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2017.

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

- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)
- [Non-Uniform Noise-to-Signal Ratio in the REINFORCE Policy-Gradient Estimator](https://mlsanity.com/paper/2602.01460/) (2026)
- [Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition](https://mlsanity.com/paper/2304.00459/) (2023)

## Abstract (arXiv)

The strong growth condition (SGC) is known to be a sufficient condition for linear convergence of the stochastic gradient method using a constant step-size γ (SGM-CS). In this paper, we provide a necessary condition, for the linear convergence of SGM-CS, that is weaker than SGC. Moreover, when this necessary is violated up to a additive perturbation σ, we show that both the projected stochastic gradient method using a constant step-size (PSGM-CS) and the proximal stochastic gradient method exhibit linear convergence to a noise dominated region, whose distance to the optimal solution is proportional to γ σ.