SGD with shuffling: optimal rates without component convexity and large epoch requirements

Understand

We study without-replacement SGD for solving finite-sum optimization problems.

• Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms.
• First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors.
• Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results.