Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
Abstract
Stochastic Gradient Descent (SGD) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (Shuffling SGD). A particularly popular strategy in Shuffling SGD is Random Reshuffling (RR), which has achieved great empirical success. Despite its strong performance, RR has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for RR, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of RR remain. According to current theory, Shuffling SGD under RR converges only when the stepsize is smaller than a threshold proportional to 1/n, where n is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of Shuffling SGD under RR is strictly worse than that of SGD when the number of epochs is smaller than another threshold proportional to n. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that RR dominates SGD in smooth convex optimization for any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question. Moreover, we establish new algorithm-dependent lower bounds for RR and SGD, respectively. Altogether, these results yield (nearly) sharp worst-case characterizations of RR and SGD. Furthermore, we develop a shuffling-based method to optimize functions satisfying the quadratic growth condition, a strict relaxation of strong convexity, and derive a new complexity bound improving existing results proved under stronger assumptions.
Related
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Continuous Delayed-Memory Stochastic Gradient Descent and Continuous-Time Reinforcement Learning from History of Astrophysical Time Series Studies
BibTeX
@misc{liu2026random,
title = {{Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent}},
author = {Zijian Liu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07406},
eprint = {2611.07406},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07406},
}
RIS
TY - UNPB
TI - Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
AU - Zijian Liu
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07406
UR - https://arxiv.org/abs/2611.07406
AB - Stochastic Gradient Descent (SGD) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (Shuffling SGD). A particularly popular strategy in Shuffling SGD is Random Reshuffling (RR), which has achieved great empirical success. Despite its strong performance, RR has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for RR, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of RR remain. According to current theory, Shuffling SGD under RR converges only when the stepsize is smaller than a threshold proportional to 1/n, where n is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of Shuffling SGD under RR is strictly worse than that of SGD when the number of epochs is smaller than another threshold proportional to n. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that RR dominates SGD in smooth convex optimization for any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question. Moreover, we establish new algorithm-dependent lower bounds for RR and SGD, respectively. Altogether, these results yield (nearly) sharp worst-case characterizations of RR and SGD. Furthermore, we develop a shuffling-based method to optimize functions satisfying the quadratic growth condition, a strict relaxation of strong convexity, and derive a new complexity bound improving existing results proved under stronger assumptions.
ER -