Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

By Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Ji Liu. 2017

1,504 citations recorded by the source corpus.

Most distributed machine learning systems nowadays, including TensorFlow and CNTK, are built in a centralized fashion. One bottleneck of centralized algorithms lies on high communication cost on the central node. Motivated by this, we ask, can decentralized algorithms be faster than its centralized counterpart? Although decentralized PSGD (D-PSGD) algorithms have been studied by the control community, existing analysis and theory do not show any advantage over centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario where only the decentralized network is available. In this paper, we study a D-PSGD algorithm and provide the first theoretical analysis that indicates a regime in which decentralized algorithms might outperform centralized algorithms for distributed stochastic gradient descent. This is because D-PSGD has comparable total computational complexities to C-PSGD but requires much less communication cost on the busiest node. We further conduct an empirical study to validate our theoretical analysis across multiple frameworks (CNTK and Torch), different network configurations, and computation platforms up to 112 GPUs. On network configurations with low bandwidth or high latency, D-PSGD can be up to one order of magnitude faster than its well-optimized centralized counterparts.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, ML Systems & Hardware

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 Networks and Communications

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “While [370, 428, 399, 371] mainly focused on the IID case, the analysis technique can be extended to the non-IID case by adding an assumption on data dissimilarities, for example by constraining the difference between client gradients and the global gradient [266, 261, 265, 401] or the difference be”
Federated Learning With Differential Privacy: Algorithms and Performance Analysis (2019, background): “The work in [18] considered partially global aggregation, where after each local update step, parameter”
Privacy Amplification by Decentralization (2020, background): “…FL algorithms that do not require a central coordinator and instead rely on peer-to-peer exchanges along edges of a network graph, see e.g. (Lian et al., 2017; Colin et al., 2016; Vanhaesebrouck et al., 2017; Lian et al., 2018; Tang et al., 2018; Bellet et al., 2018; Neglia et al., 2020;…”
FedML: A Research Library and Benchmark for Federated Machine Learning (2020, background): “As demonstrated in Figure 3, FL has various topology deﬁnitions, such as vertical FL [34, 35, 36, 37, 38, 39, 40], split learning [41, 42], decentralized FL [43, 44, 45, 46], and Hierarchical FL [47, 48, 49, 50, 51, 52].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “In the machine learning context, decentralized implementations of stochastic gradient descent have gained a lot of attention recently (Lian et al., 2017; Tang et al., 2018b; Assran et al., 2019; Koloskova et al., 2020), especially for the particular (but not fully de-centralized) case of a…”
Decentralized gradient methods: does topology matter? (2020, methodology): “We observe that both the PS and the ring all-reduce paradigms 1) maintain a unique candidate parameter vector at any given time and 2) rely logically on an allto-all communication scheme.1 Recently Lian et al. (2017, 2018) have promoted an alternative approach in the ML research community, where eac”
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “Another line of work has focused on approaches based on decentralized learning [33], [34] or edge-assisted hierarchical physical layer topologies [35].”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “For example, decentralized SGD (Shi et al., 2014; Yuan et al., 2013; Lian et al., 2017) avoids congesting the central server node and improves the scalability by removing the server, and letting the workers communicate with their neighbours only.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “However, communication-efﬁciency for decentralized optimization has not been intensively studied, except for a few papers [20, 15, 41, 44, 45].”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “It has already been proved that decentralized learning can outperform the traditional centralized learning when the worker number is comparably large under a poor network condition (Lian et al., 2017).”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “Decentralized training (Jiang et al., 2017; Lian et al., 2017; 2018; Assran et al., 2019) reduces idling due to blocking and stragglers by employing approximate gradient aggregation (e.g., via gossip or distributed averaging).”
Gradient Descent with Compressed Iterates (2019, background): “[3, 19] and combinations of decentralization and gradient quantization have been studied in recent work, see e.”
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).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “In contrast, decentralized training algorithms such as e.g. (Lian et al., 2017; Assran et al., 2019) are free of any central coordinator, and alleviate some of these main concerns.”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, methodology): “Skipping the detailed derivation, we can obtain the closed forms: • D-PSGD [Lian et al., 2017] (without compression): • DCD-PSGD [Tang et al., 2018] (with compression): • CHCHO-SGD [Koloskova et al., 2019] (with compression): • Updating rule of DeepSqueeze (with error-compensated compression): We ca”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “Several other architectures, including having no hierarchy among the nodes have been explored [6].”
Decentralized Bayesian Learning over Graphs (2019, neutral): “This is unlike decentralized optimization and SGD based methods [15–21] where local (stochastic) gradients are computed for each instance of data and communication happens at a rate comparable to number of local updates.”
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, methodology): “There are two kinds of designs for parallelism: centralized de-sign (Agarwal & Duchi, 2011; Recht et al., 2011), where the network is designed to ensure that all workers can get information from all others, and decentralized design (He et al., 2018a; Lian et al., 2017b; Tang et al., 2018b; ?”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “…first time that a distributed momentum SGD method for non-convex stochastic optimization is proven to possess the same linear speedup property (with communication reduction) as distributed SGD (without momentum) in (Lian et al., 2017; Yu et al., 2018; Wang & Joshi, 2018a; Jiang & Agrawal, 2018).”