mlsanityData to 14 Oct 2026

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

arXiv 1811.02564 ↗First posted 6 Nov 2018math.OC cs.LG stat.MLcited by 33

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 5; 2023: 9; 2024: 6; 2025: 3; 2026: 1.

33 papers.

Sort:

By area:

  1. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  2. 2021On Linear Stability of SGD and Input-Smoothness of Neural Networkscited by 63
  3. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  4. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  5. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 28
  6. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  7. 2021Global Convergence and Stability of Stochastic Gradient Descentcited by 17
  8. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 14
  9. 2024Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuningcited by 14
  10. 2025Uncertainty Quantification with the Empirical Neural Tangent Kernelcited by 11
  11. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  12. 2021Reversible Gromov-Monge Sampler for Simulation-Based Inferencecited by 10
21 more
  1. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  2. 2023A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descentcited by 9
  3. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  4. 2024Nesterov acceleration in benignly non-convex landscapescited by 7
  5. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  6. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  7. 2022Data-Efficient Augmentation for Training Neural Networkscited by 4
  8. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  9. 2023Fast Convergence in Learning Two-Layer Neural Networks with Separable Datacited by 3
  10. 2023A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spacescited by 3
  11. 2023Critical Influence of Overparameterization on Sharpness-aware Minimizationcited by 3
  12. 2024From Inverse Optimization to Feasibility to ERMcited by 3
  13. 2025Statistical Inference for Online Algorithmscited by 2
  14. 2022Benchmark Assessment for DeepSpeed Optimization Librarycited by 1
  15. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1
  16. 2023Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problemscited by 1
  17. 2026LARK: Learnability-Grounded Trajectory Selection for Efficient Reasoning Distillationcited by 1
  18. 2021Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Sizecited by 0
  19. 2022Adaptive Step-Size Methods for Compressed SGDcited by 0
  20. 2024Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolationcited by 0
  21. 2025Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappingscited by 0