SGD without Replacement: Sharper Rates for General Smooth Convex Functions
share
We study stochastic gradient descent without replacement () for smooth convex functions. is widely observed to converge faster than true where each sample is drawn independently with replacement 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 when applied to general smooth, strongly-convex functions. In particular, we show that converges at a rate of O(1/K^2) while is known to converge at O(1/K) rate, where K denotes the number of passes over data and is required to be large enough. Existing results for in this setting require additional Hessian Lipschitz assumption gurbuzbalaban2015random,haochen2018random. For small K, we show can achieve same convergence rate as for general smooth strongly-convex functions. Existing results in this setting require K=1 and hold only for generalized linear models 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.
READ FULL TEXT