# Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 3 Apr 2024.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings](https://mlsanity.com/paper/2002.12414/) (2020)
- [Gradient methods for convex minimization: better rates under weaker conditions](https://mlsanity.com/paper/1303.4645/) (2013)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)](https://mlsanity.com/paper/2006.06835/) (2020)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition](https://mlsanity.com/paper/2006.06782/) (2020)
- [Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions](https://mlsanity.com/paper/2006.08167/) (2020)
- [Accelerated Convex Optimization with Stochastic Gradients: Generalizing the Strong-Growth Condition](https://mlsanity.com/paper/2207.11833/) (2022)

## Abstract (arXiv)

We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated SGD under the strong growth condition. In this special case, our analysis reduces the dependence on the strong growth constant from ρ to √ρ as compared to prior work. This improvement is comparable to a square-root of the condition number in the worst case and address criticism that guarantees for stochastic acceleration could be worse than those for SGD.