Random Shuffling Beats SGD after Finite Epochs

A long-standing problem in optimization is proving that RANDOMSHUFFLE, the withoutreplacement version of SGD, converges faster than (the usual) with-replacement SGD. Building upon (Gürbüzbalaban et al., 2015b), we present the first non-asymptotic results for this problem, proving that after a reasonable number of epochs RANDOMSHUFFLE converges faster than SGD. Specifically, we prove that for strongly convex, second-order smooth functions, the iterates of RANDOMSHUFFLE converge to the optimal solution as O(¹/T² +ⁿ³/T³), where n is the number of components in the objective, and T is number of iterations. This result implies that after O(^√n) epochs, RANDOMSHUFFLE is strictly better than SGD (which converges as O(¹/T)). The key step toward showing this better dependence on T is the introduction of n into the bound; and as our analysis shows, in general a dependence on n is unavoidable without further changes. To understand how RANDOMSHUFFLE works in practice, we further explore two valuable settings: data sparsity and over-parameterization. For sparse data, RAN DOMSHUFFLE has the rate O (¹/T²), again strictly better than SGD. Under a setting closely related to over-parameterization, RANDOMSHUFFLE is shown to converge faster than SGD after any arbitrary number of iterations. Finally, we extend the analysis of RANDOMSHUFFLE to smooth convex and some non-convex functions.