DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression

By Hanlin Tang, Xiangru Lian, Tong Zhang, Ji Liu. 2019

241 citations recorded by the source corpus.

A standard approach in large scale machine learning is distributed stochastic gradient training, which requires the computation of aggregated stochastic gradients over multiple nodes on a network. Communication is a major bottleneck in such applications, and in recent years, compressed stochastic gradient methods such as QSGD (quantized SGD) and sparse SGD have been proposed to reduce communication. It was also shown that error compensation can be combined with compression to achieve better convergence in a scheme that each node compresses its local stochastic gradient and broadcast the result to all other nodes over the network in a single pass. However, such a single pass broadcast approach is not realistic in many practical implementations. For example, under the popular parameter server model for distributed learning, the worker nodes need to send the compressed local gradients to the parameter server, which performs the aggregation. The parameter server has to compress the aggregated stochastic gradient again before sending it back to the worker nodes. In this work, we provide a detailed analysis on this two-pass communication model and its asynchronous parallel variant, with error-compensated compression both on the worker nodes and on the parameter server. We show that the error-compensated stochastic gradient algorithm admits three very nice properties: 1) it is compatible with an \emph{arbitrary} compression technique; 2) it admits an improved convergence rate than the non error-compensated stochastic gradient methods such as QSGD and sparse SGD; 3) it admits linear speedup with respect to the number of workers. The empirical study is also conducted to validate our theoretical results.

Subfields: Artificial Intelligence, Computational Mechanics, Efficiency & Compression, 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 Efficiency & Compression

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Characterizing such fundamental trade-offs between accuracy and communication has been of recent interest in theoretical statistics [434, 81, 195, 11, 47, 380].”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “…focus on the generalization performance (on the test-set) on standard machine learning benchmarks, hereby departing from previous work such as e.g. (Tang et al., 2018; Wang et al., 2019; Tang et al., 2019; Reisizadeh et al., 2019) that mostly considered training performance (on the train-set).”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “The key idea is to store the compression error in the previous step and send the compressed sum of the gradient and the remaining compression error in the previous step [Tang et al., 2019]: g′ ←Cω [g + δ] (compressed gradient on local worker(s)) δ ←(g + δ)− Cω [g + δ] (remaining error on the local w”
Natural Compression for Distributed Deep Learning (2019, background): “We note that there are two concurrent papers to ours (all appeared online in the same month and year) proposing the use of bidirectional compression, albeit in conjunction with different underlying algorithms, such as SGD with error feedback or local updates (Tang et al., 2019; Zheng et al., 2019).”
Variance Reduced Local SGD with Lower Communication Complexity (2019, methodology): “…such as lossy compression methods [Alistarh et al., 2017, Aji and Heaﬁeld, 2017, Bernstein et al., 2019, Lin et al., 2018b, Karimireddy et al., 2019, Tang et al., 2019], which use inexact approximations or partial data to represent the gradients, and methods [Stich, 2019, Yu et al., 2019b] based…”
Federated Learning With Quantized Global Model Updates (2020, methodology): “Furthermore, FL with compressed global model transmission has been studied recently in [41, 42] aiming to alleviate the communication footprint from the PS to the devices.”
Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning (2019, background): “…to reduce the cost of gradient communication (Al-istarh et al., 2017; Bernstein et al., 2018; Wen et al., 2017; Yu et al., 2018; Chen et al., 2018; Wang et al., 2019; Stich et al., 2018; Suresh et al., 2017; Sattler et al., 2019; Tang et al., 2018; 2019; Assran et al., 2019; Acharya et al., 2019).”
Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback (2019, unknown): “After our paper has appeared, we note a similar idea was independently proposed in [21].”
Artemis: tight convergence guarantees for bidirectional compression in Federated Learning (2020, methodology): “Unlike us, Tang et al. [31] assume uniformly bounded compression error, which is a much more restrictive assumption.”