Stochastic Gradient Descent (\(\textsf{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 (\(\textsf{Shuffling SGD}\)). A particularly popular strategy in \(\textsf{Shuffling SGD}\) is Random Reshuffling (\(\textsf{RR}\)), which has achieved great empirical success. Despite its strong performance, \(\textsf{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 \(\textsf{RR}\), thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of \(\textsf{RR}\) remain. According to current theory, \(\textsf{Shuffling SGD}\) under \(\textsf{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 \(\textsf{Shuffling SGD}\) under \(\textsf{RR}\) is strictly worse than that of \(\textsf{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 \(\textsf{RR}\) dominates \(\textsf{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 \(\textsf{RR}\) and \(\textsf{SGD}\), respectively. Altogether, these results yield (nearly) sharp worst-case characterizations of \(\textsf{RR}\) and \(\textsf{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.