Communication Compression for Decentralized Training

By Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, Ji Liu. 2018

314 citations recorded by the source corpus.

Optimizing distributed learning systems is an art of balancing between computation and communication. There have been two lines of research that try to deal with slower networks: {\em communication compression} for low bandwidth networks, and {\em decentralization} for high latency networks. In this paper, We explore a natural question: {\em can the combination of both techniques lead to a system that is robust to both bandwidth and latency?} Although the system implication of such combination is trivial, the underlying theoretical principle and algorithm design is challenging: unlike centralized algorithms, simply compressing {\rc exchanged information, even in an unbiased stochastic way, within the decentralized network would accumulate the error and cause divergence.} In this paper, we develop a framework of quantized, decentralized training and propose two different strategies, which we call {\em extrapolation compression} and {\em difference compression}. We analyze both algorithms and prove both converge at the rate of $O(1/\sqrt{nT})$ where $n$ is the number of workers and $T$ is the number of iterations, matching the convergence rate for full precision, centralized training. We validate our algorithms and find that our proposed algorithm outperforms the best of merely decentralized and merely quantized algorithm significantly for networks with {\em both} high latency and low bandwidth.

Subfields: Artificial Intelligence, Computer Networks and Communications, Efficiency & Compression, 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 Computer Networks and Communications

In Efficiency & Compression

In Federated & Distributed Learning

Citations in the corpus

FedML: A Research Library and Benchmark for Federated Machine Learning (2020, methodology): “To tackle the system constraints challenge, researchers apply compression, sparsiﬁcation, or quantization techniques to reduce the communication overheads and computation costs during the training process [6, 7, 8, 9, 10, 11, 12].”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “The assumption has been made by the prior work [20, 44, 41, 40].”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “1 Whilst absolute bounds on the quantization error are sometimes considered in the literature (Reisizadeh et al., 2018b; Tang et al., 2018) these bounds might be restrictive (i.e. allowing only for low compression) when the input vectors are unbounded.”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, methodology): “• Our algorithm is compatible with almost all compression strategies, and admits a much higher tolerance on aggressive compression ratio than existing work (for example, [Tang et al., 2018]) in both theory and empirical study.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “An orthogonal way of reducing inter-node communication is to compress or quantize inter-node model updates (Tang et al., 2018; Koloskova et al., 2019).”
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; ?”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “These ideas have recently been introduced also to the decentralized setting by Tang et al. (2018a).”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “Lemma 4 (Lemma 6 in [Tang et al., 2018]) .”
Distributed Learning over Unreliable Networks (2018, background): “In Tang et al. (2018b), a new approach that admits a better performance than decentralized SGD when the data among workers is very different is studied.”
COLA: Decentralized Linear Learning (2018, background): “They further extend it to the asynchronous setting [17] and to deal with large data variance among nodes [36] or with unreliable network links [35].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “, [45]), the assumptions made do not take into consideration common characteristics of the federated setting, such as low device participation or locally updating optimization methods.”
Group Knowledge Transfer: Collaborative Training of Large CNNs on the Edge (2020, background): “Others [28, 29, 30, 31, 32, 33] optimize the communication cost without considering edge computational limitations.”
Sparsified SGD with Memory (2018, background): “Simultaneous to our work, [4, 39] at NeurIPS 2018 propose related schemes.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “Tang et al. (2018) consider unbiased quantization and show convergence to the neighborhood of a stationary point on non-convex functions under very rigid assumptions on the quantization, i.e. allowing only O (1) compression, Koloskova et al. (2019) relax those constraints but only consider strongly…”
Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection (2020, methodology): “Therefore, we generate it following the new assumption of the second eigenvalue similar to [29], [30], [32] but different from that in [26].”
On the Convergence of Quantized Parallel Restarted SGD for Serverless Learning (2020, methodology): “Inspired by DCD-PSGD [21], we design Quantized-PR-SGD for Gossip paradigm (D-Quantized-PR-SGD), whose procedure in Worker m is demonstrated as follows: • (Pull): pull the parameter x̃ from the last update as initial state x0 • (Compute): compute the gradient using PR-SGD • (Store): store the interme”