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.

本文研究了无替换 SGD 算法在有限和优化问题上的应用及其两种不同的指标洗牌方式（RandomShuffle 和 SingleShuffle）。作者们建立了这些算法的最小二次理论下的优化收敛率。此外，作者们进一步应用了各自分量的凸性来缩小 RandomShuffle 的宽松收敛结果，并减少了所有先前艺术品中共有的缺点。

带洗牌的 SGD: 无需分量凸性和大的 epoch 要求的最优速率

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

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-replacement version. We present the first (to our
knowledge) non-asymptotic solution to this problem, which shows that after a
"reasonable" number of epochs RandomShuffle indeed converges faster than SGD.
Specifically, we prove that under strong convexity and second-order smoothness,
the sequence generated by RandomShuffle converges to the optimal solution at
the rate O(1/T^2 + n^3/T^3), where n is the number of components in the
objective, and T is the total number of iterations. This result shows that
after a reasonable number of epochs RandomShuffle is strictly better than SGD
(which converges as O(1/T)). The key step toward showing this better dependence
on T is the introduction of n into the bound; and as our analysis will show, in
general a dependence on n is unavoidable without further changes to the
algorithm. We show that for sparse data RandomShuffle has the rate O(1/T^2),
again strictly better than SGD. Furthermore, we discuss extensions to nonconvex
gradient dominated functions, as well as non-strongly convex settings.

本论文首次提出了证明随机梯度下降算法的 RandomShuffle 版本在 “合理” 迭代次数后，比常规的有替换版本更快收敛的非相态解决方法。同时，论文还探讨了该问题在强凸性、稀疏数据和非强凸梯度主导函数等方面的推广。