mlsanityData to 7 Oct 2026

Aiming towards the minimizers: fast convergence of SGD for overparametrized problems

arXiv 2306.02601 ↗First posted 5 Jun 2023cs.LG math.OC stat.MLcited by 22

Not on the map. Why?

Abstract (arXiv)

Modern machine learning paradigms, such as deep learning, occur in or close to the interpolation regime, wherein the number of model parameters is much larger than the number of data samples. In this work, we propose a regularity condition within the interpolation regime which endows the stochastic gradient method with the same worst-case iteration complexity as the deterministic gradient method, while using only a single sampled gradient (or a minibatch) in each iteration. In contrast, all existing guarantees require the stochastic gradient method to take small steps, thereby resulting in a much slower linear rate of convergence. Finally, we demonstrate that our condition holds when training sufficiently wide feedforward neural networks with a linear output layer.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 5 Jun 2023.

Builds on

26 of 39 references.

References · 26

  1. 2019EfficientNet: Rethinking Model Scaling for Convolutional Neural Networkscited by 6,415
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  4. 2019Big Transfer (BiT): General Visual Representation Learningcited by 766
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  8. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  9. 2017Three Factors Influencing Minima in SGDcited by 270
  10. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  11. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  12. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
14 more
  1. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  2. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  3. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  4. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
  5. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  6. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  7. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 59
  8. 2014Learning without Concentrationcited by 50
  9. 2019The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descentcited by 46
  10. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  11. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  12. 2020On The Convergence of First Order Methods for Quasar-Convex Optimizationcited by 8
  13. 2023Fast convergence to non-isolated minima: four equivalent conditions for C2 functionscited by 6
  14. 2023Accelerated Stochastic Optimization Methods under Quasar-convexitycited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 8; 2025: 6; 2026: 6.

22 papers.

Sort:

  1. 2024Challenges in Training PINNs: A Loss Landscape Perspectivecited by 109
  2. 2025The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Trainingcited by 31
  3. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  4. 2023A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descentcited by 8
  5. 2023No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Pathscited by 7
  6. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 7
  7. 2024Nesterov acceleration in benignly non-convex landscapescited by 6
  8. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 4
  9. 2024From Inverse Optimization to Feasibility to ERMcited by 3
  10. 2025NeuCLIP: Efficient Large-Scale CLIP Training with Neural Normalizer Optimizationcited by 3
  11. 2024Provable Optimization for Adversarial Fair Self-supervised Contrastive Learningcited by 2
  12. 2025Statistical Inference for Online Algorithmscited by 2
10 more
  1. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  2. 2024Hybrid Coordinate Descent for Efficient Neural Network Learning Using Line Search and Gradient Descentcited by 0
  3. 2024Beyond Discretization: Learning the Optimal Solution Pathcited by 0
  4. 2024Stochastic Gradient Descent Revisitedcited by 0
  5. 2025A Novel Unified Parametric Assumption for Nonconvex Optimizationcited by 0
  6. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  7. 2026Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approachcited by 0
  8. 2026Label-NTK Alignments and A Tighter Convergence Bound in the NTK Regimecited by 0
  9. 2026A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithmcited by 0
  10. 2026How AI settled the complexity of the oldest SGD algorithmcited by 0