Asynchronous Decentralized Parallel Stochastic Gradient Descent

By Xiangru Lian, Ce Zhang, Ji Liu. 2017

561 citations recorded by the source corpus.

Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when workers are many, and 2) significantly worse convergence when the traffic to parameter server is congested. Can we design an algorithm that is robust in a heterogeneous environment, while being communication efficient and maintaining the best-possible convergence rate? In this paper, we propose an asynchronous decentralized stochastic gradient decent algorithm (AD-PSGD) satisfying all above expectations. Our theoretical analysis shows AD-PSGD converges at the optimal $O(1/\sqrt{K})$ rate as SGD and has linear speedup w.r.t. number of workers. Empirically, AD-PSGD outperforms the best of decentralized parallel SGD (D-PSGD), asynchronous parallel SGD (A-PSGD), and standard data parallel SGD (AllReduce-SGD), often by orders of magnitude in a heterogeneous environment. When training ResNet-50 on ImageNet with up to 128 GPUs, AD-PSGD converges (w.r.t epochs) similarly to the AllReduce-SGD, but each epoch can be up to 4-8X faster than its synchronous counterparts in a network-sharing HPC environment. To the best of our knowledge, AD-PSGD is the first asynchronous algorithm that achieves a similar epoch-wise convergence rate as AllReduce-SGD, at an over 100-GPU scale.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Federated & Distributed Learning

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

In Federated & Distributed Learning

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Although some previous works [432, 267, 143] have proposed similar methods, the error convergence analysis is an open and challenging problem.”
Privacy Amplification by Decentralization (2020, background): “[37, 18, 52, 38, 51, 11, 45, 35] for recent work and [32] (Section 2.”
Decentralized gradient methods: does topology matter? (2020, neutral): “Recently Lian et al. (2017, 2018) have promoted an alternative approach in the ML research community, where each worker 1) keeps updating a local version of the parameters and 2) broadcasts its updates only to a subset of nodes (its neighbors).”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “There are two main types of decentralized learning algorithms: ﬁxed network topology (He et al., 2018), and time-varying (Nedi´c and Olshevsky, 2015; Lian et al., 2018) during training.”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “lel SGD (D-PSGD), where each worker sends a copy of its model to its peers at every iteration, and show it can be faster than parameter-server and ALLREDUCE methods for training deep neural networks. Lian et al. (2018) study an asynchronous extension, AD-PSGD. Assran et al. (2019) study stochastic g”
Robust and Communication-Efficient Collaborative Learning (2019, background): “Recently, there have been some works which study non-convex decentralized consensus optimization and establish convergence to a stationary point (Zeng and Yin, 2018; Hong et al., 2017, 2018; Sun and Hong, 2018; Scutari et al., 2017; Scutari and Sun, 2018; Jiang et al., 2017; Lian et al., 2017a).”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “There are two main types of decentralized learning algorithms: ﬁxed network topology [He et al., 2018], or time-varying [Lian et al., 2018, Nedić and Olshevsky, 2015] during training.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “subsequently applied it to distributed deep learning in both synchronous [9], [10], [11] and asynchronous settings [12], [13].”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, neutral): “For the random topology decentralized algorithms, the communication network changes over time, for example, (Lian et al., 2018; Nedić & Olshevsky, 2015; Nedic et al., 2017).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a); Pedregosa et al. (2017); Lian et al. (2017b); Leblond et al. (2018); Alistarh et al. (2018).”
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).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest (Duchi et al., 2012; Wei and Ozdaglar, 2012; Colin et al., 2016; Lian et al., 2017; Jiang et al., 2017; Tang et al., 2018; Lian et al., 2018).”
Distributed Learning over Unreliable Networks (2018, background): “…of distributed stochastic gradient descent, such as the compression of communication, e.g Seide and Agarwal (2016), decentralized communication Lian et al. (2017a); Sirb and Ye (2016); Lan et al. (2017); Tang et al. (2018a); Stich et al. (2018), and asynchronous communication Lian et al.…”
COLA: Decentralized Linear Learning (2018, background): “[Lian et al., 2018] achieves O (1 / ✏ ) rate and has linear speedup with respect to number of workers.”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, methodology): “educe the communication overhead of parallel mini-batch SGD while preserving its linear speed-up w.r.t. the number of workers. One notable method called decentralized parallel SGD (D-PSGD) studied in [7, 4, 8] is shown to achieve O(1= p NT) convergence without requiring a single server to collect st”
D2: Decentralized Training over Decentralized Data (2018, background): “This is consistent with the original D-PSGD paper [Lian et al., 2017a].”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “gradient descent approach in [30] and [31], where after each local update step, parameter aggregation is performed over”
Communication Compression for Decentralized Training (2018, methodology): “Decentralized algorithms are mostly applied to solve the consensus problem [Zhang et al., 2017b, Lian et al., 2017a, Sirb and Ye, 2016], where the network topology is decentralized.”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “One approach to inconsistent decentralized parameter update is to use a fixed communication graph, via neighbor-based gradient/parameter exchange [161].”