# On exponential convergence of SGD in non-convex over-parametrized learning

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2018.

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

- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [On Linear Stability of SGD and Input-Smoothness of Neural Networks](https://mlsanity.com/paper/2105.13462/) (2021)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuning](https://mlsanity.com/paper/2402.07818/) (2024)
- [Uncertainty Quantification with the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2502.02870/) (2025)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [Reversible Gromov-Monge Sampler for Simulation-Based Inference](https://mlsanity.com/paper/2109.14090/) (2021)
- [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (2023)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Data-Efficient Augmentation for Training Neural Networks](https://mlsanity.com/paper/2210.08363/) (2022)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Fast Convergence in Learning Two-Layer Neural Networks with Separable Data](https://mlsanity.com/paper/2305.13471/) (2023)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [Critical Influence of Overparameterization on Sharpness-aware Minimization](https://mlsanity.com/paper/2311.17539/) (2023)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [Benchmark Assessment for DeepSpeed Optimization Library](https://mlsanity.com/paper/2202.12831/) (2022)
- [Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition](https://mlsanity.com/paper/2304.00459/) (2023)
- [Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems](https://mlsanity.com/paper/2305.09978/) (2023)
- [LARK: Learnability-Grounded Trajectory Selection for Efficient Reasoning Distillation](https://mlsanity.com/paper/2605.30651/) (2026)
- [Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size](https://mlsanity.com/paper/2112.14872/) (2021)

## Abstract (arXiv)

Large over-parametrized models learned via stochastic gradient descent (SGD) methods have become a key element in modern machine learning. Although SGD methods are very effective in practice, most theoretical analyses of SGD suggest slower convergence than what is empirically observed. In our recent work [8] we analyzed how interpolation, common in modern over-parametrized learning, results in exponential convergence of SGD with constant step size for convex loss functions. In this note, we extend those results to a much broader non-convex function class satisfying the Polyak-Lojasiewicz (PL) condition. A number of important non-convex problems in machine learning, including some classes of neural networks, have been recently shown to satisfy the PL condition. We argue that the PL condition provides a relevant and attractive setting for many machine learning problems, particularly in the over-parametrized regime.