  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.
