Fetching the paper…

Reading the bibliography…

2020

On Tight Convergence Rates of Without-replacement SGD

Ahn, Kwangjun, Sra, Suvrit

Original
PDF
Post on X

Understand

For solving finite-sum optimization problems, SGD without replacement sampling is empirically shown to outperform SGD.

Denoting by $n$ the number of components in the cost and $K$ the number of epochs of the algorithm , several recent works have shown convergence rates of without-replacement SGD that have better dependency on $n$ and $K$ than the baseline rate of $O(1/(nK))$ for SGD.
However, there are two main limitations shared among those works: the rates have extra poly-logarithmic factors on $nK$, and denoting by $\kappa$ the condition number of the problem, the rates hold after $\kappa^c\log(nK)$ epochs for some $c>0$.
In this work, we overcome these limitations by analyzing step sizes that vary across epochs.

On Tight Convergence Rates of Without-replacement SGD · Around

Built on

On a stochastic approximation method
Kai Lai Chung · 1954
Earlier work this paper cites.
Stochastic approximation of minima with improved asymptotic speed
Vaclav Fabian · 1967
Earlier work this paper cites.
Convergence rate of incremental subgradient algorithms
Angelia Nedić and Dimitri Bertsekas · 2001
Earlier work this paper cites.
Curiously fast convergence of some stochastic gradient descent algorithms
Léon Bottou · 2009
Earlier work this paper cites.
Stochastic gradient descent tricks
Léon Bottou · 2012
Earlier work this paper cites.

Similar

Without-replacement sampling for stochastic gradient methods
Ohad Shamir · 2016
Cited alongside, same era.
Mathematics for computer science
Eric Lehman, Tom Leighton, and Albert Meyer · 2017
Cited alongside, same era.
Random shuffling beats SGD after finite epochs
Original
Jeffery Z HaoChen and Suvrit Sra · 2018
Cited alongside, same era.
Why random reshuffling beats stochastic gradient descent
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo Parrilo · 2019
Cited alongside, same era.

Then

SGD without replacement: Sharper rates for general smooth convex functions
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli · 2019
Later among the works it cites.
How good is SGD with random shuffling?
Original
Itay Safran and Ohad Shamir · 2019
Later among the works it cites.
A unified convergence analysis for shuffling-type gradient methods
Original
Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten van Dijk · 2020
Closest in time.
Closing the convergence gap of SGD without replacement
Original
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…