Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent

Random reshuffling is the sampling scheme used in practice, yet existing theory for smooth convex problems required stepsizes below a threshold proportional to \(1/n\), where \(n\) is the number of summands, and its optimally tuned rate was worse than that of stochastic gradient descent when the number of epochs was below a threshold proportional to \(n\).

Liu proves that reshuffling dominates stochastic gradient descent in smooth convex optimisation for any reasonable stepsize after any finite number of epochs, and adds algorithm-dependent lower bounds for both methods. The result closes a gap that had left practice ahead of the theory.