The Theory-Practice Gap in Stochastic Optimization
If you look at a classic machine learning textbook, the theoretical analysis of Stochastic Gradient Descent (SGD) relies on a clean mathematical assumption: data points are sampled with replacement. At every single step, the algorithm selects an instance uniformly at random from the entire dataset, updates the model parameters, and throws the instance back into the pool. This ensures that each gradient estimate is independent and identically distributed (IID), making the stochastic gradient an unbiased estimator of the true full gradient.
In practice, almost nobody trains models this way.
Instead, deep learning frameworks like PyTorch and TensorFlow implement Random Reshuffling (RR) or sampling without replacement. The dataset is randomly permuted at the start of an epoch, and the algorithm iterates through the sequence sequentially until every data point has been seen exactly once. As noted by Shashank Rajput et al. and Itay Safran et al., this creates a significant theory-practice gap: the very assumption that makes SGD easy to analyze mathematically is routinely violated to achieve better performance in the real world.
Why Shuffling Outperforms Replacement
To understand why sampling without replacement works better, imagine a dataset containing 100 distinct examples. If you sample with replacement 100 times, basic probability tells us that you will completely miss about 36.8% ($1/e$) of the dataset, while aggressively oversampling other points. This introduces redundant noise and wastes computational cycles on duplicate information within a single pass.
By contrast, sampling without replacement guarantees that the algorithm visits every single data point exactly once per epoch. This constraint introduces an implicit variance reduction mechanism over the course of the epoch.
At the beginning of a shuffled pass, the gradient steps are highly stochastic and noisy. However, because every data point must be selected exactly once, the choices are coupled. If the first few steps happen to pull gradients that push the parameters too far in one direction, the remaining pool of unsampled data points is statistically tilted to pull the parameters back. By the time the algorithm reaches the final step of the epoch, the sum of all stochastic gradients must exactly equal the full batch gradient (minus the drift caused by changing weights).
This epoch-level error cancellation allows shuffling methods to achieve faster asymptotic convergence rates than standard SGD. As proven by Quoc Tran-Dinh et al. and Konstantin Mishchenko et al., this variance-reduction effect causes the optimization error to decay faster relative to the number of epochs compared to the loose bounds of with-replacement sampling.
The Mathematical Hurdle: Statistical Dependency
If random reshuffling is empirically and asymptotically superior, why did it take decades to formalize its convergence guarantees? The challenge lies entirely in the loss of independence.
Once a data point is sampled without replacement, the probability distribution of the remaining pool changes. The conditional expectation of a stochastic gradient step depends heavily on every choice made earlier in that epoch. This statistical dependency breaks standard martingale convergence proofs used for classical SGD.
Historically, researchers attempted to resolve this using matrix theory. A prominent line of inquiry centered on the Recht-Ré conjecture, which posited that a noncommutative version of the Arithmetic Mean-Geometric Mean (AM-GM) inequality could bound the product of these dependent gradient operators, as explored in a commentary by John Duchi et al.. However, Zehua Lai et al. proved that the Recht-Ré conjecture is false in the general case, forcing optimization theorists to develop entirely new mathematical frameworks to handle the dependencies of without-replacement sampling.
Modern Frameworks for Analyzing Shuffling Methods
To bypass the limitations of classical independence assumptions, recent literature has introduced several innovative perspectives to model the behavior of random reshuffling:
- Martingale Difference Sequences: Rather than assuming independent steps, the authors of New Insight into Hybrid Stochastic Gradient Descent: Beyond With-Replacement Sampling and Convexity utilized specialized martingale-based techniques. By analyzing the macro-history of an entire epoch rather than individual micro-steps, they successfully bounded the variance introduced by dependent sampling.
- Model Incoherence: Shaocong Ma et al. introduced the concept of model incoherence to explain why shuffling excels in modern over-parameterized regimes. They demonstrated that while standard random sampling is constrained by the average difficulty of individual data points, random reshuffling benefits from the product of data characteristics across the permutation, leading to tighter trajectories around the global minimum.
- Removing Bounded Gradient Constraints: Early attempts to prove shuffling convergence relied on the unrealistic assumption that gradients are globally bounded. Quoc Tran-Dinh et al. unified the analysis by relaxing these conditions, proving that shuffling-type methods converge robustly across both convex and nonconvex landscapes without requiring artificial gradient clipping.
Beyond Standard Optimization
The theoretical validation of without-replacement sampling has quickly spread from standard empirical risk minimization to more complex optimization paradigms:
- Nonconvex and Minimax Optimization: Edouard Pauwels extended these guarantees to general nonconvex optimization, showing that practical shuffling strategies are mathematically sound even when the loss landscape is highly complex. For adversarial settings like GANs, Aniket Das et al. demonstrated that sampling without replacement yields faster convergence rates for finite-sum minimax optimization.
- Federated Learning: In distributed environments, data shuffling occurs locally on client devices. Peter Richtárik proved that combining server-side stepsizes with local without-replacement sampling significantly accelerates federated optimization. Concurrently, the authors of FedShuffle: Recipes for Better Use of Local Work in Federated Learning provided frameworks to manage the variance-reduction effects of local shuffling, preventing the "client drift" that often degrades distributed training.