Tight Rates for Random Reshuffling: Phase Transitions and Cost of Nonconvex Components

Random Reshuffling (RR) processes all $n$ components once per epoch in a fresh uniformly random order. We study the worst-case convergence of constant stepsize stochastic gradient descent under RR for a finite sum of smooth component functions whose average is strongly convex. Although recent works have established convergence guarantees for RR, most results require the number of epochs $K$ to be sufficiently large, and a tight characterization across the full range of epoch counts has remained under-explored, both with and without component convexity. For convex components, by characterizing tight rates up to polylogarithmic factors, we establish a phase transition at $K\asymp \kappa$, where $\kappa$ is the condition number: RR matches the convergence of with-replacement SGD below this threshold and achieves faster rates above it. Without component convexity, we prove that order $$\begin{gathered} \max \\ \kappa ,{\kappa }^2/n \end{gathered}$$ epochs are necessary in the worst case to reduce the last-iterate squared distance below a constant fraction of its initial value. Moreover, beyond this threshold, the convergence rate of RR worsens by a factor of $$\begin{gathered} \max \\ 1,\kappa /n \end{gathered}$$ relative to the convex-component rate. Together, these results characterize the cost of allowing nonconvex components, which takes different forms depending on the ratio $\kappa /n$.