Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition
Not on the map. Why?
Abstract (arXiv)
Modern machine learning models are often over-parameterized and as a result they can interpolate the training data. Under such a scenario, we study the convergence properties of a sampling-without-replacement variant of stochastic gradient descent (SGD) known as random reshuffling (RR). Unlike SGD that samples data with replacement at every iteration, RR chooses a random permutation of data at the beginning of each epoch and each iteration chooses the next sample from the permutation. For under-parameterized models, it has been shown RR can converge faster than SGD under certain assumptions. However, previous works do not show that RR outperforms SGD in over-parameterized settings except in some highly-restrictive scenarios. For the class of Polyak-L ojasiewicz (PL) functions, we show that RR can outperform SGD in over-parameterized settings when either one of the following holds: (i) the number of samples (n) is less than the product of the condition number (kappa) and the parameter (α) of a weak growth condition (WGC), or (ii) n is less than the parameter (ρ) of a strong growth condition (SGC).
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 28 of its 38 references that are in the map. First posted on arXiv 2 Apr 2023.
Builds on
28 of 38 references.
References · 28
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
- 2019SGD: General Analysis and Improved Ratescited by 206
- 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
- 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
- 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
- 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
16 more
- 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
- 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
- 2018Random Shuffling Beats SGD after Finite Epochscited by 66
- 2019How Good is SGD with Random Shuffling?cited by 63
- 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
- 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
- 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
- 2020Closing the convergence gap of SGD without replacementcited by 56
- 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
- 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
- 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
- 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
- 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 16
- 2020Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is Falsecited by 15
- 2017On the linear convergence of the stochastic gradient method with constant step-sizecited by 6
- 2020Understanding the Impact of Model Incoherence on Convergence of Incremental SGD with Random Reshufflecited by 4
Built on by
Citing papers per year: 2023: 1.
1 paper.