Random Shuffling Beats SGD after Finite Epochs

Jeff Z. HaoChen, Suvrit Sra

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-repla…