Why random reshuffling beats stochastic gradient descent

Mert Gürbüzbalaban, Asuman E. Ozdaglar, Pablo A. ParriloMath. Program 2021 · DOI

Abstract

While Random Reshuffling (RR) is the standard for training machine learning models, its theoretical superiority over Stochastic Gradient Descent (SGD) remained poorly understood due to the complex dependencies introduced by sampling without replacement. This paper provides a rigorous convergence analysis, showing that RR achieves faster rates than the $\Omega(1/k)$ limit of SGD. We introduce De-biased Random Reshuffling (DRR), which further accelerates convergence to $O(1/k^2)$ by removing predictable iterate bias.

Introduction

The "finite-sum" optimization problem is central to modern machine learning: minimizing a function $f(x)$ composed of $m$ individual data points. While practitioners almost exclusively use Random Reshuffling (RR) due to its empirical speed, theoretical analysis has historically favored Stochastic Gradient Descent (SGD). The difficulty in analyzing RR stems from the dependencies created by sampling without replacement; once a data point is used in an epoch, it cannot be reused, breaking the independent and identically distributed (i.i.d.) assumptions that simplify SGD's martingale-based proofs.

Methodology

The authors analyze RR under strong convexity assumptions, employing three key technical innovations:

  1. Cycle Error Decoupling: RR is modeled as gradient descent with "cycle gradient errors." The authors decouple these dependent errors into an independent component across cycles and a smaller term scaling with the square of the stepsize ($\alpha_k^2$).
  2. Iterate Averaging: By applying $q$-suffix averaging (averaging only the most recent fraction of iterates), the method filters noise from the larger stepsizes required for RR's optimal performance.
  3. De-biased Random Reshuffling (DRR): Analysis reveals that RR iterates possess a deterministic bias. DRR estimates this bias during the final training cycle and subtracts it from the averaged iterate, further accelerating convergence.

Key Insights: Bias vs. Variance

A fundamental finding of this work is the trade-off between bias and variance in sampling strategies. In SGD, the gradient error variance is $O(1)$, leading to a wide, zero-mean error distribution. In contrast, RR ensures every data point is visited exactly once per cycle, allowing errors to cancel out more effectively and reducing the cycle gradient error to $O(\alpha_k)$.

Individual error distributions showing RR's predictable bias (top) versus SGD's zero-mean variance (bottom).

As shown in the figure above, while RR iterates are biased (the distribution is not centered at zero), this bias is structured and predictable, depending on the Hessian and gradients at the optimal point. This structure is what allows for the "de-biasing" step in DRR.

Convergence Results and Empirical Validation

The theoretical analysis yields a convergence rate of $\Theta(1/k^{2s})$ for RR with averaging, where $s \in (1/2, 1)$. This rate is substantially faster than the $\Omega(1/k)$ lower bound established for SGD. The proposed DRR method further improves this to $O(1/k^2)$ with high probability.

Comparison of error distributions for RR (red) and SGD (blue), highlighting the significant variance reduction in RR.

Empirical tests on synthetic quadratic problems validate these findings. The figure above illustrates that the error distribution for RR is significantly more concentrated around the optimal solution than that of SGD, which exhibits a much wider Gaussian-like spread.

Limitations and Conclusion

While DRR offers superior convergence, it introduces computational overhead due to the required matrix inversion for bias estimation, which may be prohibitive for high-dimensional models. Future research aims to develop more efficient bias-removal techniques, such as low-rank Hessian approximations. Nonetheless, this work provides the long-awaited theoretical justification for the empirical success of Random Reshuffling in machine learning.

Summary updated

BibTeX
@article{gurbuzbalaban2021why,
  author = {Mert Gürbüzbalaban and Asuman E. Ozdaglar and Pablo A. Parrilo},
  title = {{Why random reshuffling beats stochastic gradient descent}},
  journal = {Math. Program.},
  year = {2021},
  doi = {10.1007/s10107-019-01440-w},
}
Figure