Asynchronous Stochastic Gradient Descent with Delay Compensation

By Shuxin Zheng, Qi Meng, Nenghai Yu, Zhiming Ma, Tie-Yan Liu. 2016

360 citations recorded by the source corpus.

With the fast development of deep learning, it has become common to learn big neural networks using massive training data. Asynchronous Stochastic Gradient Descent (ASGD) is widely adopted to fulfill this task for its efficiency, which is, however, known to suffer from the problem of delayed gradients. That is, when a local worker adds its gradient to the global model, the global model may have been updated by other workers and this gradient becomes "delayed". We propose a novel technology to compensate this delay, so as to make the optimization behavior of ASGD closer to that of sequential SGD. This is achieved by leveraging Taylor expansion of the gradient function and efficient approximation to the Hessian matrix of the loss function. We call the new algorithm Delay Compensated ASGD (DC-ASGD). We evaluated the proposed algorithm on CIFAR-10 and ImageNet datasets, and the experimental results demonstrate that DC-ASGD outperforms both synchronous SGD and asynchronous SGD, and nearly approaches the performance of sequential SGD.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Zeno++: Robust Fully Asynchronous SGD (2019, background): “Recent years have witnessed an increasing number of largescale machine learning algorithms, including asynchronous SGD (Zinkevich et al., 2009; Lian et al., 2018; Zheng et al., 2017; Zhou et al., 2018).”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “of distributed gradient descent are obtained in [27]–[29], which only allow one step of local update before global aggregation.”
Communication Compression for Decentralized Training (2018, methodology): “Zheng et al. [2016] proposed an algorithm to improve the performance of the asynchronous C-PSGD.”
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).”
Asynchronous Federated Optimization (2019, background): “Asynchronous training [17, 22, 23] is widely used in traditional distributed SGD.”
Continuous control for robot based on deep reinforcement learning (2019, background): “For A3C, the parameters of the global networks are updated by the different workers asynchronously, so it has the problem of gradient delay [65].”
CosmoFlow: Using Deep Learning to Learn the Universe at Scale (2018, neutral): “to scale synchronous methods have found that the scalability slows after a few hundred nodes [19]–[22].”
1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed (2021, neutral): “Example techniques include quantization (Zhang et al., 2017; Wangni et al., 2018), decentralization (Lian et al., 2017; Koloskova* et al., 2020; Li et al., 2018), and asynchronous communication (Zheng et al., 2016; Chaturapruek et al., 2015).”
Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization (2018, methodology): “Inspired by asynchronous parallel stochastic optimization techniques (Agarwal & Duchi, 2011; Lian et al., 2015; Zhang et al., 2015; Zhao & Li, 2015; Zheng et al., 2017), in this study, we propose an asynchronous parallel stochastic L-BFGS algorithm for large-scale non-convex optimization problems.”
GossipGraD: Scalable Deep Learning using Gossip Communication based Asynchronous Gradient Descent (2018, methodology): “Several PS optimizations specific to GPU have been proposed in approaches such as GeePS [21] and MXNET [23], and techniques to address delay compensation [63].”
Convergence of Edge Computing and Deep Learning: A Comprehensive Survey (2019, background): “These bottlenecks in FL can potentially be addressed by asynchronous training mechanisms [280]–[282].”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “Asynchronous stochastic optimization in shared-memory and distributed-memory systems has also been widelystudied (Bertsekas & Tsitsiklis, 1989; Chaturapruek et al., 2015; Niu et al., 2011; Lian et al., 2015; 2018; Chen et al., 2016; Zheng et al., 2017; Mania et al., 2017; Leblond et al., 2017; Reddi”
A Hitchhiker's Guide On Distributed Training of Deep Neural Networks (2018, methodology): “Another promising work by S. Zheng et al. [28] proposed Delay Compensated ASGD (DC-ASGD) using Taylor expansion of the gradient function and approximation of Hessian matrix to theoretically prove convergence for convex and non-convex optimization problems.”
OD-SGD (2020, methodology): “Delay Compensated ASGD (DC-ASGD) proposed by Shuxin Zheng et al. [18] is based on ASGD and the compensation operations are conducted in the master node to improve the convergence point.”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, background): “Much of this work cannot address constrained settings, and many formulations conﬂate the distributed setting with parallel computing [29], [30].”
A Survey on Federated Learning for Resource-Constrained IoT Devices (2021, neutral): “Xie et al. [96], Zheng et al. [97], and Lian et al. [98] analyzed asynchronous FL training with provable convergence by combining it with federated optimization.”