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

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

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Big Transfer (BiT): General Visual Representation Learning](https://mlsanity.com/paper/1912.11370/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [On the linearity of large non-linear models: when and why the tangent kernel is constant](https://mlsanity.com/paper/2010.01092/) (2020)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent](https://mlsanity.com/paper/1904.06963/) (2019)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [On The Convergence of First Order Methods for Quasar-Convex Optimization](https://mlsanity.com/paper/2010.04937/) (2020)
- [Fast convergence to non-isolated minima: four equivalent conditions for C2 functions](https://mlsanity.com/paper/2303.00096/) (2023)
- [Accelerated Stochastic Optimization Methods under Quasar-convexity](https://mlsanity.com/paper/2305.04736/) (2023)

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

- [Challenges in Training PINNs: A Loss Landscape Perspective](https://mlsanity.com/paper/2402.01868/) (2024)
- [The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Training](https://mlsanity.com/paper/2501.18965/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (2023)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths](https://mlsanity.com/paper/2306.11922/) (2023)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [NeuCLIP: Efficient Large-Scale CLIP Training with Neural Normalizer Optimization](https://mlsanity.com/paper/2511.08417/) (2025)
- [Provable Optimization for Adversarial Fair Self-supervised Contrastive Learning](https://mlsanity.com/paper/2406.05686/) (2024)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Hybrid Coordinate Descent for Efficient Neural Network Learning Using Line Search and Gradient Descent](https://mlsanity.com/paper/2408.01374/) (2024)
- [Beyond Discretization: Learning the Optimal Solution Path](https://mlsanity.com/paper/2410.14885/) (2024)
- [Stochastic Gradient Descent Revisited](https://mlsanity.com/paper/2412.06070/) (2024)
- [A Novel Unified Parametric Assumption for Nonconvex Optimization](https://mlsanity.com/paper/2502.12329/) (2025)
- [Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach](https://mlsanity.com/paper/2605.14663/) (2026)
- [Label-NTK Alignments and A Tighter Convergence Bound in the NTK Regime](https://mlsanity.com/paper/2605.25275/) (2026)
- [A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm](https://mlsanity.com/paper/2605.29273/) (2026)
- [How AI settled the complexity of the oldest SGD algorithm](https://mlsanity.com/paper/2606.29593/) (2026)

## 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.