Stochastic Learning under Random Reshuffling

Bicheng Ying, Kun Yuan, Stefan Vlaski, Ali H. Sayed

Abstract

In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case and strongly convex loss function. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size $O(\mu^2)$ around the minimizer rather than $O(\mu)$. Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.

Introduction

Stochastic Gradient Descent (SGD) is a cornerstone of modern machine learning. While the standard theoretical formulation of SGD assumes sampling with replacement, most practical implementations utilize Random Reshuffling (RR). In RR, the dataset is shuffled at the start of each epoch, and samples are processed sequentially without replacement. Despite its widespread use, the theoretical understanding of RR, particularly in the constant step-size regime, has lagged behind empirical observations.

This paper addresses this gap by quantifying the performance gains of RR over standard SGD when using a constant step-size $\mu$. While standard SGD converges to a steady-state error neighborhood of size $O(\mu)$, this research demonstrates that RR achieves a significantly tighter neighborhood of size $O(\mu^2)$.

Methodology and Theoretical Insights

The authors employ a rigorous stochastic analysis to track error dynamics across multiple epochs. A central component of the analysis is the "Long-Term Model," an auxiliary framework that approximates the algorithm's trajectory over many epochs. The accuracy of this model is verified through a "Mismatch Bound."

The fundamental advantage of RR stems from the "zero-sum" property of gradient noise. Because RR visits every sample exactly once per epoch, the sum of the gradient noise over a full epoch is zero. In contrast, standard SGD noise accumulates like a random walk. This cancellation effect leads to the superior $O(\mu^2)$ scaling. Furthermore, the analysis explains the characteristic periodic oscillations seen in RR learning curves. The variance of the gradient estimate is not constant; it is lowest at the boundaries of an epoch and highest in the middle, creating a predictable bell-shaped error pattern within each epoch.

Experimental Results

The theoretical findings were validated using simulated logistic regression and quadratic (least-squares) problems.

Comparison of MSD for standard SGD and SGD with RR, highlighting the lower error floor and periodic behavior.

As shown in the convergence plots, RR reaches a significantly lower Mean-Square Deviation (MSD) floor than standard SGD. The results also clearly illustrate the periodic "jitter" predicted by the theory, where the error fluctuates within each epoch but maintains a lower average than uniform sampling.

Mean-square deviation versus step-size, demonstrating the O(μ²) scaling for random reshuffling.

Empirical simulations confirm the $O(\mu^2)$ scaling law. By plotting MSD against the step-size $\mu$ on a log-log scale, the regression line shows a slope of approximately 2. This indicates that reducing the step-size by one order of magnitude results in a two-order-of-magnitude (20dB) reduction in steady-state error for RR, compared to only 10dB for standard SGD.

Conclusion

This work provides a precise analytical foundation for the empirical success of Random Reshuffling. By proving the $O(\mu^2)$ steady-state error bound and deriving closed-form expressions for MSD, the authors clarify the benefits of sampling without replacement. While the current analysis focuses on strongly convex functions and constant step-sizes, it sets the stage for future exploration into non-convex landscapes and variance-reduced algorithms.

Summary updated

Abstract

In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case and strongly convex loss function. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size $O(\mu^2)$ around the minimizer rather than $O(\mu)$. Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.
BibTeX
@misc{ying2018stochastic,
  author = {Bicheng Ying and Kun Yuan and Stefan Vlaski and Ali H. Sayed},
  title = {{Stochastic Learning under Random Reshuffling}},
  year = {2018},
  eprint = {1803.07964},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.07964},
}
Figure