Curiously Fast Convergence of some Stochastic Gradient Descent Algorithms

By L. Eon Bottou. 2009

120 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour (2017, background): “In practice, common SGD implementations apply random shufﬂing of the training set during each SGD epoch, which can give better results [3, 13].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “This ordering is replaced by another random order after each such cycle [10].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “This ordering is replaced by another random order after each such cycle [18].”
Permutation-Based SGD: Is Random Optimal? (2021, methodology): “Although permutation-based SGD has been widely observed to perform better in practice (Bottou, 2009; Recht & Ré, 2012; 2013), the vanilla version has attracted the vast majority of theoretical analysis.”
Distributed stochastic optimization for deep learning (thesis) (2016, unknown): “Notice that each data loader cycles5 through the (5)Its advantage is observed in [10].”
Efficient Distributed SGD with Variance Reduction (2015, background): “Algorithm 3 CentralVR-Async Algorithm 1: parameters learning rate η 2: initialize x, {∇fj(x̃j)}j , g, α = 1/p, xold = gold = 0 3: while not converged do 4: for each local node do 5: g̃ ← 0 6: set π: random permutation of indices 1, 2, · · · , |Ωs| 7: for k in {1, . . . , |Ωs”
Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling (2017, methodology): “The most commonly used sampling methods are i.i.d. sampling [19][9] and without-replacement sampling [23][4].”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “Shuﬄing-type gradient methods are widely used in practice due to their eﬃciency (Bottou, 2009).”
Closing the convergence gap of SGD without replacement (2020, unknown): “In practice, SGD without replacement is much more widely used compared to its with replacement counterpart, as it can empirically converge significantly faster (Bottou, 2009; Recht & Ré, 2013; 2012).”
Twin Networks: Matching the Future for Sequence Generation (2017, unknown): “4The saw tooth pattern of both training curves corresponds to shuffling within each epoch as was previously noted by Bottou (2009).”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, background): “Besides this, we do not expect any direct or short term societal consequences.”
Why random reshuffling beats stochastic gradient descent (2015, unknown): “For instance, Bottou [7] empirically compares SGD and RR methods and finds that RR converges with a rate close to ∼ 1/k(2) whereas SGD is much slower achieving its min-max lower bound of Ω(1/k) for strongly convex objective functions [1, 26].”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, background): “In modern machine learning applications, RANDOMSHUFFLE and SINGLESHUFFLE are much more widely used than SGD, due to their simple implementations and better empirical performance [2, 3].”