Why random reshuffling beats stochastic gradient descent

By Mert Gurbuzbalaban, Asuman E. Ozdaglar, Pablo A. Parrilo. 2015

181 citations recorded by the source corpus.

We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-replacement counterpart stochastic gradient descent (SGD), characterization of its convergence rate has been a long standing open question. In this paper, we answer this question by providing various convergence rate results for RR and variants when the sum function is strongly convex. We first focus on quadratic component functions and show that the expected distance of the iterates generated by RR with stepsize αk=Θ(1/ks)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k=\varTheta (1/k^s)$$\end{document} for s∈(0,1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s\in (0,1]$$\end{document} converges to zero at rate O(1/ks)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{O}(1/k^s)$$\end{document} (with s=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s=1$$\end{document} requiring adjusting the stepsize to the strong convexity constant). Our main result shows that when the component functions are quadratics or smooth (with a Lipschitz assumption on the Hessian matrices), RR with iterate averaging and a diminishing stepsize αk=Θ(1/ks)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k=\varTheta (1/k^s)$$\end{document} for s∈(1/2,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s\in (1/2,1)$$\end{document} converges at rate Θ(1/k2s)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta (1/k^{2s})$$\end{document} with probability one in the suboptimality of the objective value, thus improving upon the Ω(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (1/k)$$\end{document} rate of SGD. Our analysis draws on the theory of Polyak–Ruppert averaging and relies on decoupling the dependent cycle gradient error into an independent term over cycles and another term dominated by αk2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k^2$$\end{document}. This allows us to apply law of large numbers to an appropriately weighted version of the cycle gradient errors, where the weights depend on the stepsize. We also provide high probability convergence rate estimates that shows decay rate of different terms and allows us to propose a modification of RR with convergence rate O(1k2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{O}(\frac{1}{k^2})$$\end{document}.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

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 shuffling of the training set during each SGD epoch, which can give better results [3, 13].”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “Moreover, bad orderings of the data—known to lead to slow convergence in the worst case [61], [64], [65]—are “averaged out”.”
Differentially Private Model Publishing for Deep Learning (2019, unknown): “its random sampling with replacement [23].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Theoretical understanding of this phenomenon had been a long standing open problem, understood recently in [71].”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “[8] show a O( 1 T 2 ) bound, where T is the number of epochs, but”
Communication-Efficient Edge AI: Algorithms and Systems (2020, unknown): “• Data reshuffling via index coding and pliable index coding: Data reshuffling [202], [203] is a recognized approach to improve the statistical performance of machine learning algorithms.”
On the Convergence Rate of Incremental Aggregated Gradient Algorithms (2015, background): “Let us also note that in addition to being a natural order in some applications, deterministic orders are important to consider since their analysis for incremental methods could be a key step in understanding the convergence behavior of general component function sampling schemes (see the analysis ”
Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling (2017, background): “[13] Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo Parrilo.”
Coresets for Data-efficient Training of Machine Learning Models (2019, background): “If in addition to the strong convexity of the sum function, every component function f i is smooth, IG with diminishing stepsizes α k = Θ(1 /k s ) , s ∈ (0 , 1] converges at rate O (1 /k s ) (Gürbüzbalaban et al., 2015).”
FairBatch: Batch Selection for Model Fairness (2020, background): “, 2017; Masters & Luschi, 2018) and various sampling techniques (Shamir, 2016; Gürbüzbalaban et al., 2019).”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “Its cyclic variant, known as an incremental gradient method was proposed even much earlier, see (Nedic and Bertsekas, 2001), where the convergence analysis was given in (Nedi´c and Bertsekas, 2001) for a sub-gradient variant, and in (G¨urb¨uzbalaban et al., 2015) for gradient variants.”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “One of the first works to report progress is due to by Gürbüzbalaban, Ozdaglar, and Parrilo [5, 6] for strongly convex F and smooth quadratic fi’s.”
GraB: Finding Provably Better Data Permutations than Random Reshuffling (2022, background): “[19] Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo A Parrilo.”
Permutation-Based SGD: Is Random Optimal? (2021, background): “Incremental Gradient Descent on strongly convex functions has also been studied well in literature (Nedić & Bertsekas, 2001; Bertsekas, 2011; Gürbüzbalaban et al., 2019a).”
Closing the convergence gap of SGD without replacement (2020, unknown): “[8] Mert Gürbüzbalaban, Asu Ozdaglar, and PA Parrilo.”
SGD without Replacement: Sharper Rates for General Smooth Convex Functions (2019, background): “The first three rows of the table compare our result for large K against those of (Gürbüzbalaban et al., 2015) and (HaoChen & Sra, 2018).”