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:
- 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.
- Error Decomposition: They decompose the progress made in one epoch into two parts: a "full gradient descent" step and a "shuffling error" term.
- 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.
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}$,
RandomShuffleand 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
RandomShufflebecomes 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,
RandomShuffleis 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
RandomShufflebeats SGD, it is still slower than full Gradient Descent (GD) in the very long run (GD converges exponentially, whileRandomShuffleis polynomial). - General Convexity: For non-strongly convex problems, the results are less dramatic, showing
RandomShuffleis comparable to SGD but not necessarily faster by an order of magnitude. Improving these bounds remains an open challenge.
Summary updated