SGD without Replacement: Sharper Rates for General Smooth Convex Functions

By Prateek Jain, Dheeraj M. Nagaraj, Praneeth Netrapalli. 2019

101 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “Remarkably, Theorem 1 improves upon the epoch requirement K & κ(2) log(nK) of an existing bound [11] for RANDOMSHUFFLE on smooth strongly convex functions, without needing convexity of fi’s.”
Closing the convergence gap of SGD without replacement (2020, unknown): “For our convergence rate on quadratic functions, we heavily rely on and combine the approaches used by Nagaraj et al. (2019) and HaoChen & Sra (2018). The convergence rate analyses proposed by HaoChen & Sra (2018) can be tightened by a more careful analysis that employs iterate coupling similar to t”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “Here, we use diminishing learning rates in Theorem 2 instead of constant ones as in (HaoChen and Sra, 2019; Mishchenko et al., 2020; Nagaraj et al., 2019).”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, background): “Nagaraj et al. (2019) also study convergence of RR for smooth objectives, and Safran and Shamir (2020); Rajput et al. (2020) give lower bounds for RR and related methods.”