In the standard textbook treatment of Stochastic Gradient Descent (SGD), we assume that at each step, a data point is sampled with replacement from the training set. This ensures that each gradient estimate is independent and identically distributed (i.i.d.), providing a clean mathematical path to prove convergence.
However, almost no one actually trains models this way. Instead, practitioners use without-replacement sampling, typically in the form of Random Reshuffling (RR)—where the dataset is permuted at the start of each epoch—or Single Shuffle (SS)—where the data is permuted only once. While Ohad Shamir noted in Without-Replacement Sampling for Stochastic Gradient Methods that this is preferred for its cache locality and empirical speed, it introduces a significant "theory-practice gap." Because points are not replaced, the choice of the next sample depends on all previous samples in the epoch, violating the i.i.d. assumption and introducing statistical bias.
The Intuition of Faster Convergence
The central mystery of shuffling methods is why they often converge faster than their i.i.d. counterparts. Jeffery Z. HaoChen provided a landmark non-asymptotic proof in Random Shuffling Beats SGD after Finite Epochs, showing that RR can achieve a convergence rate of $O(1/T^2)$ compared to the $O(1/T)$ rate of standard SGD.
To understand why, consider the "variance" of the gradient. In standard SGD, the noise from sampling never disappears. In shuffling methods, however, every data point is visited exactly once per epoch. This means that by the end of an epoch, the sum of the stochastic gradients is exactly equal to the full gradient of the dataset (at the various points visited). This "completeness" acts as an implicit form of variance reduction. As Kun Yuan and colleagues demonstrated in Stochastic Learning Under Random Reshuffling With Constant Step-Sizes, this allows RR to converge to a much smaller neighborhood of the optimizer than standard SGD when using constant step sizes.
Bridging the Theory-Practice Gap
For years, theoretical guarantees for shuffling were hampered by restrictive assumptions, such as requiring gradients to be globally bounded—a condition rarely met by neural networks. Quoc Tran-Dinh, Lam M. Nguyen, and their co-authors addressed this in A Unified Convergence Analysis for Shuffling-Type Gradient Methods, providing a framework that covers both convex and non-convex problems without these unrealistic constraints.
A major hurdle in these proofs is the "dependency" problem: how do you bound the error when the $k$-th step depends on the $k-1$ steps before it? Anastasia Koloskova and others introduced the concept of "effective correlation time" in On Convergence of Incremental Gradient for Non-convex Smooth Functions. By analyzing how long these dependencies persist, they were able to improve theoretical convergence rates by a factor of $n$ (the dataset size), finally aligning mathematical bounds with the strong empirical performance seen in deep learning.
Beyond Simple Shuffling
The success of basic shuffling has led to its integration into more complex optimization architectures:
- Momentum: Trang H. Tran and Quoc Tran-Dinh developed SMG: A Shuffling Gradient-Based Method with Momentum, proving that the benefits of momentum and shuffling are additive, matching state-of-the-art rates for non-convex optimization.
- Minimax Problems: For GANs and adversarial training, Hanseul Cho and Chulhee Yun provided the first rigorous analysis of SGDA with shuffling, showing that shuffling helps stabilize the often-turbulent dynamics of minimax optimization.
- Variance Reduction: New methods like "No Full Grad" (NFG), proposed by Daniil Medyakov and Aleksandr Beznosikov in Variance Reduction Methods Do Not Need to Compute Full Gradients, use shuffling to eliminate the need for expensive periodic full-gradient passes required by algorithms like SVRG.
Limits and Vulnerabilities
Despite its general superiority, shuffling is not a silver bullet. Christopher De Sa proved in Random Reshuffling is Not Always Better that there exist specific "noiseless" problems where sampling with replacement actually converges faster. Furthermore, the reliance on data ordering creates a security risk. Ilia Shumailov and Murat A Erdogdu demonstrated in Manipulating SGD with Data Ordering Attacks that if an attacker can control the shuffle order, they can stall learning or inject backdoors without ever changing the training data itself.
In summary, the shift from i.i.d. sampling to shuffling represents a transition from viewing SGD as a sequence of independent random trials to viewing it as a structured, epoch-based traversal of the data. This structure is not just a computational convenience; it is a mathematical engine for faster convergence.