The Phase Transition in Random Reshuffling: Tight Rates under Strong Convexity

Abstract

Random Reshuffling (RR) processes every component function once per epoch in a fresh uniformly random order; we study constant-stepsize RR for convex, smooth component functions with a strongly convex average, writing $K$ for the number of epochs and $\kappa$ for the condition number. Although its theoretical advantage over with-replacement SGD after sufficiently many passes is well established, a sharp comparison in the small-epoch regime $K \lesssim \kappa$ has remained incomplete. We prove a new small-epoch upper bound for the expected squared distance of the last iterate and matching lower bounds across both epoch regimes. Together with existing large-epoch upper bounds, these results characterize tight worst-case rates up to polylogarithmic factors. For the last-iterate squared distance, this characterization establishes a phase transition at $K \asymp \kappa$: RR matches the worst-case scaling of with-replacement SGD below this scale and improves on it above the scale.

Chulhee Yun

Associate Professor

I am an Associate Professor at KAIST AI. I am interested in optimization and machine learning theory.