Fast Asynchronous Parallel Stochastic Gradient Descent: A Lock-Free Approach with Convergence Guarantee

By Shen-Yi Zhao, Wu-Jun Li. 2016

81 citations recorded by the source corpus.

Stochastic gradient descent (SGD) and its variants have become more and more popular in machine learning due to their efficiency and effectiveness. To handle large-scale problems, researchers have recently proposed several parallel SGD methods for multicore systems. However, existing parallel SGD methods cannot achieve satisfactory performance in real applications. In this paper, we propose a fast asynchronous parallel SGD method, called AsySVRG, by designing an asynchronous strategy to parallelize the recently proposed SGD variant called stochastic variance reduced gradient (SVRG). AsySVRG adopts a lock-free strategy which is more efficient than other strategies with locks. Furthermore, we theoretically prove that AsySVRG is convergent with a linear convergence rate. Both theoretical and empirical results show that AsySVRG can outperform existing state-of-the-art parallel SGD methods like Hogwild! in terms of convergence rate and computation cost.

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

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “…with convergence rates, including asynchronous variants of coordinate descent (Liu et al., 2015), Sdca (Hsieh et al., 2015), Sgd for non-convex problems (De Sa et al., 2015; Lian et al., 2015), Sgd for stochastic optimization (Duchi et al., 2015) and Svrg (Reddi et al., 2015; Zhao and Li, 2016).”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “In contrast, asynchronous training [20, 40, 42] is faster when there are stragglers, but noisier due to asynchrony [7].”
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).”
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”
Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization (2018, background): “The convergence behaviour of asynchronous SGD have been extensively analysed in many works (Chaturapruek et al., 2015; Zhao & Li, 2016; Zheng et al., 2017; De Sa et al., 2017).”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us.”
HetPipe: Enabling Large DNN Training on (Whimpy) Heterogeneous GPU Clusters through Integration of Pipelined Model Parallelism and Data Parallelism (2020, background): “On the other hand, while ASP, which is possible for the parameter servers, has no synchronization overhead, it is known that ASP does not ensure convergence [43, 52].”
Heterogeneity-aware Distributed Parameter Servers (2017, background): “However, when some stragglers are significantly slower than other machines, ASP cannot guarantee correct convergence [37, 47].”