Random Reshuffling Dominates Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) is a cornerstone of modern machine learning, yet its practical implementation—often involving shuffling data points within each epoch—differs from the theoretical version of SGD that samples data uniformly with replacement. While this practice, known as Random Reshuffling (RR), is empirically superior, theoretical support has historically been limited. Existing convergence theories for RR often required restrictive conditions on the stepsize (proportional to 1/n) or the number of epochs, creating a significant mismatch between theory and practice. This paper addresses the question: Does RR dominate standard SGD in smooth convex optimization without these restrictive conditions?

The author provides a unified convergence analysis for Shuffling SGD under RR. The approach introduces two novel technical lemmas to bound the difference between the iterates of RR and the true gradient descent trajectory. By establishing a new inequality that measures the difference between the expected function value and its stochastic counterpart, the author avoids the need for additional Lipschitz assumptions. The analysis is split into two parts: one demonstrating that RR never converges more slowly than SGD under any reasonable stepsize, and another showing that RR converges faster than SGD when the stepsize is sufficiently small.

The paper proves that Shuffling SGD under RR achieves a convergence rate that is never worse than standard SGD for any reasonable stepsize (η ≲ 1/L). Specifically, the author establishes that the optimally tuned rate for RR is strictly better than that of SGD for any finite number of epochs. In the special case where all individual functions share a common minimizer, the RR rate improves upon the best-known results by a factor of 1/n. These results resolve a long-standing open question by providing the first theoretical guarantee that RR dominates SGD under general, practical conditions.