Random Shuffling Beats SGD after Finite Epochs

Jeffery Z. HaoChen, Suvrit Sra

Abstract

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" number of epochs RandomShuffle indeed converges faster than SGD. Specifically, we prove that under strong convexity and second-order smoothness, the sequence generated by RandomShuffle converges to the optimal solution at the rate $O(1/T^2 + n^3/T^3)$, where $n$ is the number of components in the objective, and $T$ is the total number of iterations. This result shows that after a reasonable number of epochs RandomShuffle is strictly better than SGD (which converges as $O(1/T)$). The key step toward showing this better dependence on $T$ is the introduction of $n$ into the bound; and as our analysis will show, in general a dependence on $n$ is unavoidable without further changes to the algorithm. We show that for sparse data RandomShuffle has the rate $O(1/T^2)$, again strictly better than SGD. Furthermore, we discuss extensions to nonconvex gradient dominated functions, as well as non-strongly convex settings.

Introduction

In the world of machine learning, Stochastic Gradient Descent (SGD) is the workhorse. However, there is a curious disconnect between how SGD is studied and how it is actually used. Theoretically, SGD is usually analyzed by assuming we sample data points with replacement (independently and uniformly). In practice, almost every deep learning framework uses without-replacement sampling: we shuffle the dataset at the start of each epoch and iterate through it. This is called RandomShuffle.

Practitioners have long known that shuffling leads to faster convergence, but proving this mathematically has been a "long-standing problem." The difficulty lies in the fact that without-replacement sampling introduces statistical dependencies between iterations, making the standard tools of probability much harder to apply. Previous proofs were either purely asymptotic (only true as $T \to \infty$) or didn't show a clear advantage over SGD for a realistic number of iterations. This paper provides the first non-asymptotic proof that RandomShuffle converges faster than standard SGD after a reasonable number of epochs.

Methods

The authors tackle the finite-sum optimization problem where the objective is an average of $n$ smooth, convex functions. Their primary contribution is a new non-asymptotic convergence analysis for RandomShuffle. Key technical moves include:

  1. Sensitivity to $n$: Unlike standard SGD bounds that ignore the dataset size $n$, the authors explicitly include $n$ in their bounds. This is crucial because, intuitively, if you haven't even seen the whole dataset once, shuffling can't be much better than random sampling.
  2. Error Decomposition: They decompose the progress made in one epoch into two parts: a "full gradient descent" step and a "shuffling error" term.
  3. Second-Order Smoothness: The analysis assumes the functions have a Lipschitz continuous Hessian (second-order smoothness). This allows them to use Taylor expansions to more tightly bound the error introduced by the shuffling process.

The analysis is evaluated across several function classes, including quadratic functions for tight bounds, sparse functions representing common ML problems like logistic regression, and Polyak-Łojasiewicz (PL) functions for non-convex global convergence analysis.

Key Results

The core finding is that RandomShuffle achieves a rate of $O(1/T^2)$, outperforming the classic $O(1/T)$ rate of SGD after a finite number of epochs.

Comparison of convergence rates for SGD and RandomShuffle under various conditions.

As shown in the table above, the convergence rates for RandomShuffle include a dependence on $n$. For strongly convex functions, RandomShuffle converges at a rate of $O\left(\frac{1}{T^2} + \frac{n^3}{T^3}\right)$. Since SGD converges at $O(1/T)$, the $1/T^2$ term eventually dominates, making shuffling strictly faster.

Key Insights

  • The Birthday Paradox Intuition: If the number of iterations $T$ is much smaller than $\sqrt{n}$, RandomShuffle and SGD are essentially indistinguishable because the chance of picking the same index twice in SGD is very low. This justifies why $n$ must appear in the bound.
  • The $\sqrt{n}$ Threshold: The analysis shows that RandomShuffle becomes provably better than SGD after roughly $O(\sqrt{n})$ epochs. For many modern datasets, this is a very "reasonable" and practical number of passes.
  • Sparsity is a Superpower: For sparse data, RandomShuffle is even more effective. Because shuffling guarantees that every single data point (and thus every feature) is visited exactly once per epoch, it avoids the "missing dimension" problem that can plague i.i.d. sampling in SGD. In sparse settings, the rate improves to $O(1/T^2)$.
  • The Necessity of $n$: The authors prove a "negative" result showing that it is impossible to prove a rate better than $O(1/T)$ without including $n$ in the bound. This explains why previous theoretical attempts might have failed to show the advantage of shuffling.

Discussion and Limitations

While this work closes a significant gap, several challenges remain:

  • The "Finite Epoch" Requirement: The bound only holds after a certain number of epochs (dependent on the condition number $\kappa$). If the problem is extremely ill-conditioned, the "reasonable" number of epochs might become quite large.
  • Comparison to GD: While RandomShuffle beats SGD, it is still slower than full Gradient Descent (GD) in the very long run (GD converges exponentially, while RandomShuffle is polynomial).
  • General Convexity: For non-strongly convex problems, the results are less dramatic, showing RandomShuffle is comparable to SGD but not necessarily faster by an order of magnitude. Improving these bounds remains an open challenge.

Summary updated

Abstract

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" number of epochs RandomShuffle indeed converges faster than SGD. Specifically, we prove that under strong convexity and second-order smoothness, the sequence generated by RandomShuffle converges to the optimal solution at the rate O(1/T^2 + n^3/T^3), where n is the number of components in the objective, and T is the total number of iterations. This result shows that after a reasonable number of epochs RandomShuffle is strictly better than SGD (which converges as O(1/T)). The key step toward showing this better dependence on T is the introduction of n into the bound; and as our analysis will show, in general a dependence on n is unavoidable without further changes to the algorithm. We show that for sparse data RandomShuffle has the rate O(1/T^2), again strictly better than SGD. Furthermore, we discuss extensions to nonconvex gradient dominated functions, as well as non-strongly convex settings.
BibTeX
@inproceedings{haochen2019random,
  author = {Jeffery Z. HaoChen and Suvrit Sra},
  title = {{Random Shuffling Beats SGD after Finite Epochs}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=rkW_-nb_-S},
}
Figure