SGD with shuffling: optimal rates without component convexity and large epoch requirements
This work addresses optimization efficiency for machine learning practitioners by providing improved theoretical guarantees for common SGD variants, though it is incremental as it builds on prior convergence analyses.
The paper tackles the problem of analyzing without-replacement SGD for finite-sum optimization, establishing minimax optimal convergence rates for RandomShuffle and SingleShuffle algorithms without requiring component convexity, and sharpens results for RandomShuffle by eliminating large epoch requirements and poly-log factor gaps.
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. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.