Interactive

Why random reshuffling beats SGD

Everyone who trains a model shuffles the data once per epoch rather than sampling it with replacement. This page shows what that buys: on a least-squares problem, the convergence rate goes from 1/k to 1/k² in the number of epochs — and shows where the extra factor comes from.

What to try

The top chart has logarithmic axes, so a rate k^−p is a straight line of slope −p. With the stepsize 1/k, the SGD curve settles onto the dashed slope −1: sampling with replacement cannot beat 1/k — that is a lower bound for stochastic approximation, not an artifact of this example. The reshuffling curve is steeper than the dashed −2 line the theorem guarantees, and keeps pulling away. The readout says when reshuffling has already reached the accuracy that SGD only reaches after a thousand epochs.

Move the stepsize exponent s and both slopes move with it, −s against −2s: the improvement is a squaring of the rate, not a constant. Then look at the second chart, which measures the error of one epoch’s total step against a full-gradient step of the same length. With replacement the error decays like α_k; under reshuffling every component is visited exactly once per epoch, the first-order sampling errors cancel, and only an α_k² term is left. Switch on the fixed cyclic order to see that the cancellation is about visiting each component once — the randomness is what averages out the remaining error from epoch to epoch.

Interactive · sampling with and without replacement

Try

Components n 50

Stepsize exponent s α_k = 1.9/k^1.00

Residual noise 1.00

Also show

Measured slope, SGD: …; over epochs 100–1000 · lower bound −1.00: the 1/k wall of sampling with replacement
Measured slope, reshuffling: …; same epochs · the theorem guarantees −2.00
Reshuffling catches SGD: …; when reshuffling first reaches the accuracy SGD has after 1000 epochs
Problem: κ = 1.05; condition number · gradient variance at the optimum σ² = 0.617

Least squares in two variables with n components, each gradient 1-smooth; the residuals at the optimum are what make the component gradients disagree there (the “residual noise” slider sets their size). One epoch is n component steps with the stepsize α_k = 1.9/k^s held fixed within the epoch. Curves average 12 runs. The second chart measures, for each epoch, how far the epoch’s total displacement is from one full-gradient step of the same length: with replacement that error is of order α_k, because the sampled gradients do not add up to the full gradient; under reshuffling every component appears exactly once, the first-order terms cancel, and only an α_k² error remains — which is the mechanism behind the squared rate.

Sampling with replacement pays for its noise at every step; reshuffling pays once per epoch, at second order — and that squares the rate.

The theorem behind this page is in Math. Program. 2021, SIAM J. Optim. 2019, and Math. Program. 2020: the first proves that random reshuffling with a diminishing stepsize Θ(1/k^s) converges at rate Θ(1/k^2s) for strongly convex problems, against the Ω(1/k) that sampling with replacement cannot beat, by decoupling the dependent within-epoch errors into an independent term across epochs; the second analyzes the fixed cyclic order; the third asks the same question of coordinate descent. The wider thread is on the research page.

To reference this page:

@misc{gurbuzbalaban2026reshuffling,
  title  = {Why random reshuffling beats SGD, interactively},
  author = {G{\"u}rb{\"u}zbalaban, Mert},
  year   = {2026},
  howpublished = {\url{https://mert-g.org/playground/reshuffling/}}
}