We study stochastic gradient descent {\em without replacement} (\sgdwor) for smooth convex functions. \sgdwor is widely observed to converge faster than true \sgd where each sample is drawn independently {\em with replacement}~\cite{bottou2009curiously} and hence, is more popular in practice. But it's convergence properties are not well understood as sampling without replacement leads to coupling between iterates and gradients. By using method of exchangeable pairs to bound Wasserstein distance, we provide the first non-asymptotic results for \sgdwor when applied to {\em general smooth, strongly-convex} functions. In particular, we show that \sgdwor converges at a rate of $O(1/K^2)$ while \sgd~is known to converge at $O(1/K)$ rate, where $K$ denotes the number of passes over data and is required to be {\em large enough}. Existing results for \sgdwor in this setting require additional {\em Hessian Lipschitz assumption}~\cite{gurbuzbalaban2015random,haochen2018random}. For {\em small} $K$, we show \sgdwor can achieve same convergence rate as \sgd for {\em general smooth strongly-convex} functions. Existing results in this setting require $K=1$ and hold only for generalized linear models \cite{shamir2016without}. In addition, by careful analysis of the coupling, for both large and small $K$, we obtain better dependence on problem dependent parameters like condition number.

本文提出了一种新的随机梯度下降算法sgdwor来优化平滑凸函数，相较于使用独立且重复地采样的传统算法sgd，sgdwor算法采样不重复且能获得更快的收敛速度，本文给出了sgdwor算法在一般的平滑且强凸函数下的首个非渐进结果：k次通信传输后，sgdwor算法的收敛速度为O(1/k^2)，并与sgd算法在小k下具有相同收敛率，同时对问题相关参数（如条件数）的依赖性更弱。

不带替换的SGD：一般平滑凸函数更锐利的速率