Random Reshuffling Dominates SGD: Bridging the Theory-Practice Gap

TL;DR

For decades, the machine learning community has relied on Random Reshuffling (RR)—shuffling data at every epoch—despite theoretical textbooks focusing mostly on standard Stochastic Gradient Descent (SGD) with uniform sampling. This paper finally provides the definitive proof: RR provably dominates SGD in smooth convex optimization. It removes the unrealistic "small stepsize" and "large epoch" restrictions of previous theories, showing RR is better under any reasonable setting.

Problem: The Small Stepsize Paradox

In theory, standard SGD is well-understood. However, practitioners almost always use RR because it works better. Previous theoretical attempts to justify RR had a major flaw: they suggested RR only works better if the stepsize $\eta$ is smaller than $1/(nL)$, where $n$ is the number of data points.

In modern deep learning where $n$ can be millions, this $1/n$ threshold would require a stepsize so small that the model would never learn. This created a Small Stepsize Paradox: theory said RR was restricted, but practice showed it was robust.

Methodology: The Virtual Trajectory and Dual Bounds

The author, Zijian Liu, breaks the proof into two distinct "Clouds" and then combines them into one unified Theorem.

1. Bound I: "Never Worse than SGD"

The core challenge in RR is unbiasedness. Unlike SGD, the gradient at a specific step in RR depends on what came before it in the shuffle. The author handles this using a Virtual Sequence $x_k(i,j)$, which represents a trajectory where two data points $(i,j)$ in the shuffle are swapped.

By measuring how much the real trajectory deviates from this virtual "swapped" trajectory, the paper proves that RR behaves at least as well as SGD even with large, constant stepsizing.

2. Bound II: "Always Better than SGD"

To show superiority, the author treats an entire epoch as a single large step. By comparing RR to a Gradient Descent (GD) step with an error term, the analysis proves that as the stepsize decreases, RR’s error vanishes much faster than SGD’s error.

Algorithm 1: The standard implementation of Shuffling SGD analyzed in the paper.

Key Results: Dominance Confirmed

The new convergence rate is defined as: $\mathbb{E}[f({\bar{x}}_K)-f_{\star }]\le \frac{6D^2}{n\sum {\eta }_k}+51\min \{\eta ,{\eta }^{2}n\bar{L}\}{\sigma }_{\star }^2$

Why is this a big deal?

• The "Min" term: This is the secret sauce. If the stepsize is "large" $(\eta \gtrsim 1/n\bar{L})$, the rate matches the best SGD bounds. If the stepsize is "small," it transitions to the fast RR rate.
• No $n$ threshold: Unlike previous work, RR is now proven to be better than SGD even if you only run it for a few epochs.
• Common Minimizers: If all data points share a solution (${\sigma }_{\star }=0$), the speedup is a massive $1/n$ improvement over prior RR theory.

Critical Analysis & Conclusion

This paper effectively wipes out the "heuristic" label from Random Reshuffling. It confirms that the Inductive Bias introduced by shuffling—ensuring every data point is seen exactly once per epoch—is mathematically superior to the high-variance "sampling with replacement" of standard SGD.

Limitations & Future Work

While the smooth convex case is now "solved" in terms of dominance, the tech still needs to be expanded to:

1. Non-convex surfaces: Does the dominance hold for the complex loss landscapes of Transformers?
2. Adaptive optimizers: How does this theory interact with Adam or RMSProp?

Overall, this is a foundational step in optimization theory that validates years of empirical intuition.