Stochastic Optimization via Sampling Without Replacement

370 concepts145 papers3 proposals

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:

  1. 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.
  2. 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:

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.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 169 papers
  2. Version 1 · 2026-10-04 · 191 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_random_reshuffling_ebf59964,
  title = {random reshuffling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-reshuffling/rdr_ebf5996417a441deb3f6194119dcb914},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_random_reshuffling_ebf59964_v2,
  title = {random reshuffling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-reshuffling/rdr_ebf5996417a441deb3f6194119dcb914/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake