On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants

By Sashank J. Reddi, Ahmed S. Hefny, Suvrit Sra, Barnab'as P'oczos, Alex Smola. 2015

200 citations recorded by the source corpus.

We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchronous versions of these algorithms---a crucial requirement for modern large-scale applications---have not been studied. We bridge this gap by presenting a unifying framework for many variance reduction techniques. Subsequently, we propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. An important consequence of our general approach is that it yields asynchronous versions of variance reduction algorithms such as SVRG and SAGA as a byproduct. Our method achieves near linear speedup in sparse settings common to machine learning. We demonstrate the empirical performance of our method through a concrete realization of asynchronous SVRG.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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 Optimization & Training

Citations in the corpus

Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of the works for instance are Reddi et al. (2015); Zhao and Li (2016); De and Goldstein (2015); Lee et al. (2015).”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, background): “While the latter problem can be addressed by using asynchronous and stochastic variants of gradient descent [15, 16], these algorithms still incur high communication costs at each iteration.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “…appeared in the SAGA paper [26], where the authors interpret SAGA as a midpoint between SAG and SVRG. Recent work [76] presents a general algorithm, which recovers SVRG, SAGA, SAG and GD as special cases, and obtains an asynchronous variant of these algorithms as a byproduct of the formulation.”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “ied problem that depends on the large mini-batches, SGD is able to converge at about the same speed as that of the small mini-batch counterpart [14,26,27]. Moreover, the asynchronous version of SVRG [18,34] can achieve near linear speed up under appropriate assumptions, and can be easily deployed on”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”
Stochastic Variance Reduction for Nonconvex Optimization (2016, neutral): “Asynchronous VR frameworks are developed in (Reddi et al., 2015; Mania et al., 2015).”
ASAGA: Asynchronous Parallel SAGA (2016, background): “• We give the first convergence analysis for an asynchronous parallel version of Saga (note that Reddi et al. (2015) only covers an epoch based version of Saga with random stopping times, a fairly different algorithm).”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Examples of such methods include distributed variants of stochastic gradient descent (SGD) [17, 27, 47], accelerated SGD [35], variance reduction SGD [10, 28], stochastic coordinate descent methods [5, 13, 20, 31] and dual coordinate ascent algorithms [30, 43, 46].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Recent work [145] presents a general algorithm, which recovers SVRG, SAGA, SAG and GD as special cases, and obtains an asynchronous variant of these algorithms as a byproduct of the formulation.”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, methodology): “[29] proved the convergence of asynchronous variance reduced stochastic gradient (SVRG) method and its speedup in sparse setting.”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, background): “Additional work in first order optimization and beyond [8, 21, 5], has further demonstrated that linear speedups are generically possible in the asynchronous shared-memory setting.”
Fast incremental method for smooth nonconvex optimization (2016, unknown): “, [6], [11], [19], [24], [25].”
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization (2016, background): “Instead, it maintains an average gradient vector g t , which changes at each iteration (refer to [21]).”
Efficient Distributed SGD with Variance Reduction (2015, background): “Recently, variance reduction methods have also gained popularity as an alternative to classical SGD. Variance reduction (VR) methods [17, 12, 29, 31, 13, 18, 19, 35, 34, 16] reduce the variance in the stochastic gradient estimates, and are able to maintain a large constant step size to achieve fast…”
Faster On-Device Training Using New Federated Momentum Algorithm (2020, background): “Synchronous and asynchronous gradient-based methods have already been proven to converge to critical points for non-convex problems [18, 20, 29].”
Automated Inference with Adaptive Batches (2017, background): “…enjoy a provably faster convergence rate than SGD and have been shown to outperform SGD on convex problems (Defazio et al., 2014a; Johnson and Zhang, 2013; Schmidt et al., 2013; Defazio et al., 2014b), as well as in parallel (Reddi et al., 2015) and distributed settings (De and Goldstein, 2016).”