In machine learning, there is a persistent disconnect between how optimization algorithms are theoretically analyzed and how they are actually deployed. Standard textbooks introduce Stochastic Gradient Descent (SGD) assuming an Independent and Identically Distributed (i.i.d.) data stream: at each step, a data point is sampled uniformly with replacement from the dataset.
In practice, almost nobody trains models this way. Instead, engineers use Random Reshuffling (RR). They partition the training process into epochs, shuffle the dataset at the start of each epoch, and iterate through the data sequentially—sampling without replacement until every data point has been visited exactly once.
While this heuristic has long been preferred for its superior empirical speed and stability, proving why it works has required rethinking the mathematical foundations of stochastic optimization.
The Core Mechanism: Gradient Noise Cancellation
To understand why sampling without replacement outperforms independent sampling, we must look at how gradient errors accumulate over time.
Consider a finite-sum optimization problem where we want to minimize the average loss over a dataset of $n$ samples. The true gradient at any state is the average of all individual sample gradients. When standard SGD samples with replacement, each step introduces an independent, zero-mean random error. Because these errors are decoupled, the optimization path behaves like a random walk. The variance of the gradient estimates remains bounded away from zero unless the learning rate vanishes, forcing the model to hover loosely around the optimum.
Random Reshuffling changes this dynamic through an implicit gradient noise cancellation mechanism. As explored by Yipeng Li et al. in A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond, processing data without replacement introduces tight dependencies between successive steps. Because every single data point is visited exactly once by the end of an epoch, the sum of the stochastic gradients encountered across the epoch perfectly reconstructs the true full gradient of the dataset (assuming the model parameters do not change drastically within those $n$ steps).
As a result, the local errors introduced by individual samples counteract one another. As Konstantin Mishchenko et al. demonstrate in Random Reshuffling: Simple Analysis with Vast Improvements, the variance introduced by sampling without replacement decreases much faster than standard SGD variance as the learning rate is reduced. By the end of each data cycle, the iterates effectively return to a highly accurate path, allowing the algorithm to exploit the local geometry of the data without getting derailed by persistent stochastic noise.
Quantifying the Shuffling Speedup
This noise cancellation translates directly into faster theoretical convergence rates. For smooth optimization problems, standard SGD with replacement converges at a rate of $\mathcal{O}(1/K)$ or $\mathcal{O}(1/\sqrt{K})$, where $K$ is the number of iterations.
In contrast, shuffling-based methods accelerate as the number of training epochs increases. Work by Kwangjun Ahn et al. in SGD with shuffling: optimal rates without component convexity and large epoch requirements and Shashank Rajput et al. in Closing the convergence gap of SGD without replacement establishes that without-replacement sampling can achieve a significantly faster convergence rate of $\mathcal{O}(1/nK^2)$ or $\mathcal{O}(1/T^2)$ (where $T$ represents total passes). This mathematical guarantee confirms that iterating through shuffled data in epochs is fundamentally more efficient than independent point sampling.
Theoretical analyses typically distinguish between two primary shuffling paradigms:
- Single Shuffling (SS): The dataset is permuted exactly once at the very beginning of training, and this fixed sequence is reused across all subsequent epochs.
- Random Reshuffling (RR): A fresh, random permutation is generated at the start of every epoch.
Intuitively, one might expect Single Shuffling to fail due to the lack of ongoing randomness. However, Itay Safran et al. show in How Good is SGD with Random Shuffling? that a single initial shuffle is often sufficient to break adversarial data patterns and unlock early convergence benefits.
Nevertheless, per-epoch reshuffling remains the gold standard for long-duration training. As proven by Zijian Liu et al. in Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization, continuously regenerating permutations maintains a tighter bound on gradient variance over time, preventing the algorithm from inheriting structural biases that can emerge from a single static sequence.
Bridging Theory and Practice: Last-Iterate Convergence
For years, a subtle gap remained in shuffling theory: many proofs could only guarantee convergence for the average of all iterates generated during training. Machine learning practitioners, however, almost always discard the history and deploy the last iterate (the final model state).
Recent theoretical breakthroughs have successfully closed this gap. In On the Last-Iterate Convergence of Shuffling Gradient Methods, Zijian Liu et al. provided the first mathematical proof that the final iterate of shuffling gradient methods converges robustly for general convex problems without requiring restrictive assumptions like strong convexity. This ensures that the model an engineer actually saves at the end of an epoch inherits the full theoretical advantages of the shuffling speedup.
Generalization to Complex Landscapes
The benefits of sampling without replacement extend far beyond standard supervised learning. Researchers have successfully adapted the random reshuffling framework to more complex optimization landscapes:
- Minimax Optimization: In adversarial settings like GAN training or distributionally robust learning, optimization behaves like a game-theoretic tug-of-war. Aniket Das et al. in Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization and Hanseul Cho et al. in SGDA with shuffling: faster convergence for nonconvex-PŁ minimax optimization demonstrate that shuffling data in epochs reduces gradient complexity from $\mathcal{O}(\epsilon^{-4})$ to $\mathcal{O}(\epsilon^{-3})$, stabilizing saddle-point trajectories.
- Federated and Distributed Learning: In decentralized environments, data cannot be easily pooled and shuffled globally. Algorithms like FedShuffle, analyzed by Samuel Horváth et al. in FedShuffle: Recipes for Better Use of Local Work in Federated Learning, mandate that individual clients process their local datasets using random reshuffling rather than uniform sampling. This acts as a powerful local variance reduction mechanism, mitigating the challenges of data heterogeneity across devices. Going a step further, hierarchical strategies like those proposed by Grigory Malinovsky et al. in Federated Learning with Regularized Client Participation utilize "double shuffling"—sampling both the participating clients and the local data points without replacement—to maximize global update stability.
Ultimately, the transition from independent sampling to structured data permutations represents a fundamental shift in how we conceptualize stochastic optimization. By forcing the algorithm to interact with every data point systematically, Random Reshuffling transforms chaotic gradient noise into a self-canceling, highly efficient path toward the optimum.