Optimal convergence rate of without-replacement SGD

Abstract

We study convergence lower bounds of without-replacement stochastic gradient descent (SGD) for solving smooth (strongly-)convex finite-sum minimization problems. Unlike most existing results focusing on lower bounds for SGD with Random Reshuffling where the random permutation is chosen independently on each epoch to sample the component function in each iterate, we seek bounds applicable to arbitrary permutation-based SGD. This method includes all variants that carefully select the best permutation beyond Random Reshuffling. Notably, our bounds significantly improve upon existing lower bounds and tightly match the upper bounds shown for a recently proposed algorithm called GraB, across all factors including the number of component functions $n$, the number of epochs $K$, and the condition number $\kappa$. We also extend our bounds to arbitrary weighted average iterates, providing a generalized result that covers the final iterate.