SGD without Replacement: Sharper Rates for General Smooth Convex Functions

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 citebottou2009curiously 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/K2) 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 citegurbuzbalaban2015random,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 citeshamir2016without. 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.