Understanding Gradient Bias in Random Reshuffling

16 concepts16 papers2 proposals

In optimization theory, there is a persistent gap between how algorithms are analyzed and how they are actually implemented. Standard proofs for Stochastic Gradient Descent (SGD) rely on the assumption of Independent and Identically Distributed (i.i.d.) sampling with replacement. Under this paradigm, every step selects a data point uniformly at random from the entire dataset, ensuring that the expected value of the stochastic gradient exactly equals the true gradient.

In practice, however, almost no one trains models this way. Instead, deep learning frameworks use Random Reshuffling (RR): at the start of each epoch, the dataset is permuted, and the algorithm iterates through the data points sequentially without replacement.

As noted by Mishchenko et al. and Safran et al., this empirical preference exists because shuffling is highly memory-efficient and consistently converges faster than standard SGD. Yet, from a theoretical perspective, sampling without replacement introduces a severe mathematical complication: shuffling-induced gradient bias.

Why Without-Replacement Sampling Introduces Bias

To understand why shuffling breaks standard optimization theory, consider a simple dataset containing only two points, $A$ and $B$.

If we sample with replacement, the probability of choosing point $B$ at the second step is always $1/2$, completely independent of whether we chose $A$ or $B$ first. Because the steps are decoupled, the gradient estimate remains unbiased at every single iteration.

If we sample without replacement, the moment we select point $A$ as our first step, the probability of choosing point $B$ as our second step immediately jumps to $100\%$. The choice of the second data point is strictly conditioned on the history of the current epoch.

As Pauwels and Medyakov et al. explain, this statistical coupling means that within a single training epoch, intermediate stochastic gradients are no longer independent. Because selecting one data point alters the remaining pool, the expected value of a single step no longer aligns with the true gradient of the full dataset. This lack of independence invalidates standard martingale-based convergence proofs, which rely on independent and identically distributed noise.

The Secret to Shuffling's Success: Intra-Epoch Error Cancellation

If shuffling introduces statistical bias, why does it outperform unbiased i.i.d. sampling? The answer lies in how errors accumulate and cancel out over the course of a full epoch.

In standard SGD, because you sample with replacement, you might accidentally sample point $A$ multiple times while missing point $B$ entirely. This sampling variance introduces a persistent background noise that forces the algorithm's convergence rate to slow down to $O(1/t)$, requiring rapidly decaying learning rates to stabilize.

In Random Reshuffling, even though individual steps within an epoch are biased, you are guaranteed to visit every single data point exactly once by the end of the epoch. If the model parameters do not move drastically during these intermediate steps, the sum of these gradients over the entire epoch will closely approximate the true full gradient of the dataset.

Ahn et al. demonstrated that this structural guarantee allows the optimization errors to cancel each other out as the epoch concludes. Instead of being limited by the average variance of individual samples, shuffling methods benefit from the collective properties of the entire dataset. Ma et al. formalized this phenomenon using the concept of model incoherence, proving that Random Reshuffling exploits the interplay of data characteristics to achieve faster and more accurate convergence, particularly in over-parameterized models.

Mathematical Frameworks for Biased Gradients

To bridge the gap between practical success and theoretical guarantees, researchers have developed new mathematical tools to analyze optimization trajectories through the lens of dependent variables.

Unified and Nonconvex Convergence

To prove that shuffling is more than a heuristic, Tran-Dinh et al. established a unified convergence analysis for shuffling-type gradient methods across both convex and nonconvex landscapes, notably removing restrictive and unrealistic assumptions like bounded gradients. For purely nonconvex optimization, Pauwels provided rigorous convergence guarantees, validating that practical shuffling strategies achieve superior asymptotic convergence rates compared to standard SGD.

Last-Iterate Convergence

Historically, theoretical proofs for shuffling methods could only guarantee the convergence of the average of all generated iterates. However, practitioners always deploy the final model iteration after training. Liu et al. resolved this discrepancy by providing the first theoretical proof for the last-iterate convergence of shuffling gradient methods on general convex problems.

Proving Fundamental Optimality

To determine the absolute theoretical limits of these approaches, Cha et al. constructed worst-case functions to establish perfectly tight convergence lower bounds. Their analysis closed the theoretical gap between upper and lower bounds for random permutations, proving that advanced shuffling-based frameworks can achieve fundamental optimality.

Shuffling in Complex Optimization Landscapes

The realization that shuffling-induced bias can be managed has allowed researchers to port without-replacement sampling into more sophisticated optimization paradigms.

  • Momentum and Acceleration: Traditional momentum methods assume unbiased gradient estimates. Tran et al. introduced the Nesterov Accelerated Shuffling Gradient (NASG) method, which applies momentum at the end of each epoch rather than at every individual iteration. This design neatly sidesteps intra-epoch gradient correlations, achieving a state-of-the-art $O(1/T)$ convergence rate for convex problems.
  • Variance Reduction: Malinovsky et al. combined Random Reshuffling with Variance Reduction (VR) techniques. By utilizing "controlled linear perturbations," the authors established faster linear convergence rates, proving that shuffling methods can be made both faster and more stable than standard SGD.
  • Minimax Optimization and Games: In adversarial training and minimax optimization, gradient bias is doubly challenging because updates for one variable block directly alter the optimization landscape of the opposing block. Tran-Dinh et al. successfully extended shuffling methods to nonconvex-concave minimax problems, while Emmanouilidis et al. provided theoretical guarantees for the Stochastic Extragradient method with Random Reshuffling (SEG-RR), showing it outperforms traditional with-replacement sampling in variational inequalities.

Parallel Dependency Challenges

The core challenge of shuffling—where an update creates a statistical dependency that biases subsequent steps—mirrors several other modern optimization bottlenecks:

Without-Replacement Sampling:
[Sample A Selected] ──> [Remaining Pool Changes] ──> [Next Gradient Step Biased]

Sequential Block Updates:
[Update Block 1] ──> [Model State Changes] ──> [Next Block Gradient Biased]

Pairwise Learning:
[Reuse Past Samples] ──> [Data-Model Coupling] ──> [Stochastic Gradient Biased]

As shown by Yin et al. in Block Stochastic Gradient (BSG) descent, updating multiple variable blocks sequentially using a single data sample causes later blocks to become statistically dependent on earlier updates. Similarly, Roberts et al. noted that reshaping sampling distributions to optimize policy gradients creates a bottleneck where updates are constrained by historical gradient dependencies. Finally, in pairwise learning environments (such as AUC maximization), Sun et al. demonstrated that reusing historical data samples to construct pairs couples the model state with the training data, introducing a structural gradient bias.

By understanding how intra-epoch error cancellation tames the statistical dependencies of Random Reshuffling, optimization theory continues to develop robust frameworks for handling biased gradients across machine learning.

Key Foundational Work

Block stochastic gradient iteration for convex and nonconvex optimization (2014) — contributed 1 concept elements to this direction.
Signal-to-Noise Ratio Analysis of Policy Gradient Algorithms (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_shuffling_induced_gradient_bias_55fe78e0,
  title = {shuffling-induced gradient bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shuffling-induced-gradient-bias/rdr_55fe78e039914524a17eb95401f92c40},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_shuffling_induced_gradient_bias_55fe78e0_v1,
  title = {shuffling-induced gradient bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shuffling-induced-gradient-bias/rdr_55fe78e039914524a17eb95401f92c40/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake