# Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2013.

## Built on by (most cited first, 30 of 54)

- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [Implicit Gradient Alignment in Distributed and Federated Learning](https://mlsanity.com/paper/2106.13897/) (2021)
- [Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models](https://mlsanity.com/paper/2308.08977/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Does Momentum Change the Implicit Regularization on Separable Data?](https://mlsanity.com/paper/2110.03891/) (2021)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [Nesterov Accelerated Shuffling Gradient Method for Convex Optimization](https://mlsanity.com/paper/2202.03525/) (2022)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [ODE approximation for the Adam algorithm: General and overparametrized setting](https://mlsanity.com/paper/2511.04622/) (2025)
- [Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2112.07369/) (2021)
- [Maestro: Uncovering Low-Rank Structures via Trainable Decomposition](https://mlsanity.com/paper/2308.14929/) (2023)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs](https://mlsanity.com/paper/2405.13136/) (2024)
- [Practical and Matching Gradient Variance Bounds for Black-Box Variational Bayesian Inference](https://mlsanity.com/paper/2303.10472/) (2023)
- [Off-Policy Actor-Critic with Emphatic Weightings](https://mlsanity.com/paper/2111.08172/) (2021)
- [Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations](https://mlsanity.com/paper/2405.15545/) (2024)
- [Target-based Surrogates for Stochastic Optimization](https://mlsanity.com/paper/2302.02607/) (2023)
- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [Fast Convergence in Learning Two-Layer Neural Networks with Separable Data](https://mlsanity.com/paper/2305.13471/) (2023)

## Abstract (arXiv)

We consider optimizing a function smooth convex function f that is the average of a set of differentiable functions fi, under the assumption considered by Solodov [1998] and Tseng [1998] that the norm of each gradient fi' is bounded by a linear function of the norm of the average gradient f'. We show that under these assumptions the basic stochastic gradient method with a sufficiently-small constant step-size has an O(1/k) convergence rate, and has a linear convergence rate if g is strongly-convex.