Why random reshuffling beats stochastic gradient descent

Mert Gürbüzbalaban; Asuman Ozdaglar; Pablo A. Parrilo

doi:10.1007/s10107-019-01440-w

Publications · Journal article · Math. Program. 2021

Why random reshuffling beats stochastic gradient descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

Mathematical Programming, 186, pp. 49–84, 2021.

Publisher (DOI)Code

In brief

Resolves a long-standing open question about without-replacement sampling: random reshuffling — the sampling scheme practitioners actually use — provably converges faster than i.i.d. sampling for SGD, with rate Θ(1/k^2s) over epochs against the Ω(1/k) barrier of with-replacement sampling.

Go further

Interactive

Why random reshuffling beats SGD → — a playground built around the ideas in this paper.

Topics

Incremental methods & data ordering

Cite

@article{gurbuzbalaban2021reshuffling,
  title   = {Why random reshuffling beats stochastic gradient descent},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2021},
  journal = {Mathematical Programming},
  volume  = {186},
  pages   = {49--84},
  doi     = {10.1007/s10107-019-01440-w},
}

Relatedsame topics

Randomness and permutations in coordinate descent methods (Math. Program., 2020)
Convergence rate of incremental gradient and incremental Newton methods (SIAM J. Optim., 2019)
Global convergence rate of proximal incremental aggregated gradient methods (SIAM J. Optim., 2018)
Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate (SIAM J. Optim., 2018)
A double incremental aggregated gradient method with linear convergence rate for large-scale optimization (ICASSP, 2017)

← All publications · Research program · Mert Gürbüzbalaban