ATOMO: Communication-efficient Learning via Atomic Sparsification

By Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary B. Charles, Dimitris Papailiopoulos, Stephen J. Wright. 2018

392 citations recorded by the source corpus.

Distributed model training suffers from communication overheads due to frequent gradient updates transmitted between compute nodes. To mitigate these overheads, several studies propose the use of sparsified stochastic gradients. We argue that these are facets of a general sparsification method that can operate on any possible atomic decomposition. Notable examples include element-wise, singular value, and Fourier decompositions. We present ATOMO, a general framework for atomic sparsification of stochastic gradients. Given a gradient, an atomic decomposition, and a sparsity budget, ATOMO gives a random unbiased sparsification of the atoms minimizing variance. We show that methods such as QSGD and TernGrad are special cases of ATOMO and show that sparsifiying gradients in their singular value decomposition (SVD), rather than the coordinate-wise one, can lead to significantly faster distributed training.

Subfields: Artificial Intelligence, Efficiency & Compression

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 Efficiency & Compression

Citations in the corpus

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[45] Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “The more direct approach is to reduce the size of the messages through gradient compression or sparsification [30, 22, 47, 38, 40, 8].”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “To further reduce the communication overhead, one promising direction is to compress the variables that are sent between diﬀerent workers [Chen et al., 2018, Wang et al., 2018].”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Though methods in [28], [29] use induced sparsity in the quantized gradients, explicitly sparsifying the gradients more aggressively by retaining Topk components, e.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “There have been massive amount of work in the context of algorithms [37, 33, 36, 5, 26] and systems [16, 43, 9] that improve the communication efficiency of synchronous distributed SGD in a fully-connected network.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “Wang et al. (2018) proposed an atomic sparsification strategy for gradient sparsification.”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “…the coordinates of the gradient with only their sign (Seide et al., 2014; Carlson et al., 2015; Bernstein et al., 2018, 2019; Karimireddy et al., 2019), quantizing the individual coordinates (Alistarh et al., 2017; Wen et al., 2017), and low-rank approximation of the gradient (Wang et al., 2018).”
Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data (2019, background): “Other authors propose to stochastically quantize the gradients during upload in an unbiased way (TernGrad [19], QSGD [20], ATOMO [21]).”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, methodology): “While the analyses of such methods have largely been restricted to unbiased compression schemes (Alistarh et al., 2017; Wen et al., 2017; Wang et al., 2018), biased schemes which perform extreme compression practically perform much better (Seide et al.”
Expanding the Reach of Federated Learning by Reducing Client Resource Requirements (2018, background): “Communication-efﬁcient distributed learning Distributed learning is known to suffer from communication over-heads associated with the frequent gradient updates exchanged among nodes [Wang et al., 2018, Dean et al., 2012, Smith et al., 2018, Reddi et al., 2016].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “(We refer readers to [47] for a more complete review.”
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.”
Communication-Efficient Local Decentralized SGD Methods (2019, background): “The more direct approach is to reduce the size of the messages through gradient compression or sparsification [28, 20, 49, 35, 39, 7].”
Federated Learning in Mobile Edge Networks: A Comprehensive Survey (2019, methodology): “• Model Compression: This is a technique commonly used in distributed learning [92].”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, methodology): “[38] Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright.”
Election Coding for Distributed Learning: Protecting SignSGD against Byzantine Attacks (2019, background): “Regarding this issue, the authors of [18]–[24] considered quantization of real-valued gradient vectors.”
Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air (2019, methodology): “Quantization methods implement lossy compression of the gradient vectors by quantizing each of their entries to a finite-bit low precision value [2], [4], [18]–[24].”