Sparse Communication for Distributed Gradient Descent

By Alham Fikri Aji, Kenneth Heafield. 2017

882 citations recorded by the source corpus.

We make distributed stochastic gradient descent faster by exchanging sparse updates instead of dense updates. Gradient updates are positively skewed as most updates are near zero, so we map the 99% smallest updates (by absolute value) to zero then exchange sparse matrices. This method can be combined with quantization to further improve the compression. We explore different configurations and apply them to neural machine translation and MNIST image classification tasks. Most configurations work on MNIST, whereas different configurations reduce convergence rate on the more complex translation task. Our experiments show that we can achieve up to 49% speed up on MNIST and 22% on NMT without damaging the final accuracy or BLEU.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Vision and Pattern Recognition

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Training Neural Networks with Fixed Sparse Masks (2021, background): “An orthogonal approach to reducing communication costs is to have workers only update a small subset of the model’s parameters [2, 13, 44, 45].”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, neutral): “Definition 1 (Top-r Sparsification [1], [10], [26], [27]): For a parameter 1 ≤ r ≤ d, the operator topr : Rd → Rd is defined for ω ∈ Rd as ( topr(ω) ) i := { (ω)i, if i ∈ {π(1), .”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “[2] Alham Fikri Aji and Kenneth Heafield.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “Gradient vector sparsification is another approach analyzed in [4, 40, 39, 5, 30, 34, 9, 3, 36, 21, 32].”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, background): “, k < 1%, has been proposed [2, 4, 20, 30, 32], combined with error compensation to ensure that all co-ordinates do get eventually updated as needed.”
Natural Compression for Distributed Deep Learning (2019, methodology): “References [1] Alham Fikri Aji and Kenneth Heafield.”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “To reduce the communication cost at each iteration, compression or sparsification based parallel SGD are considered in (Seide et al., 2014; Strom, 2015; Aji & Heafield, 2017; Wen et al., 2017; Alistarh et al., 2017).”
Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data (2019, methodology): “[25] present minor modifications to the work of Aji and Heafield [23] that even close this small”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “Another promising line of research addressing the communication bottleneck of large scale training is to use quantization [31, 32, 33] or more aggressive sparsification [34, 35, 36] of gradients.”
Local SGD Converges Fast and Communicates Little (2018, background): “A very aggressive—and promising—sparsification method is to keep only very few coordinates of the stochastic gradient by considering only the coordinates with the largest magnitudes [3, 9, 18, 32, 35, 36, 37].”
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training (2017, methodology): “Baseline Gradient Dropping [14] Gradient Sparsification with momentum correction and local gradient clipping Deep Gradient Compression”
Scheduling Policies for Federated Learning in Wireless Networks (2019, methodology): “…efﬁcient, where typical methods range from reducing the communication band-width by only updating the UEs with signiﬁcant training improvement [12], compressing the gradient vectors via quantization [13], or adopting momentum method in the sparse update to accelerate the training process [14].”
TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning (2017, methodology): “Aji and Heafield [24] proposed a heuristic gradient sparsification method that truncated the smallest gradients and transmitted only the remaining large ones.”
Sparsified SGD with Memory (2018, methodology): “Also gradient dropping [1] trivially satisfies (4), though with different parameter k in each iteration.”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, methodology): “Several papers considered the problem of reducing the precision of gradient by using fewer bits to represent floating pointing numbers [29, 44, 37, 2, 40, 8] or only transmitting coordinates [1, 24].”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “Other approaches for low-communication training focus on sparsification of gradients, either by thresholding small entries or by random sampling [6, 22, 23, 24, 25, 26, 27, 28].”
The Convergence of Sparsified Gradient Methods (2018, methodology): “Variants of this pattern are implemented in [2, 8, 15, 23, 24].”
Demystifying Parallel and Distributed Deep Learning (2018, background): “2,128,152] Sharded PS[39,56,120,137,142,244,254,255] Hierarchical PS[88,107,253] Decentralized[9,54,121,155] Compression Quantization[5,35,50,51,55,63,87,90,109,132,151,202,210,237,265] Sparsification[3,32,67,158,206,214,224] Other Methods[41,106,111,129,150,243,254] Training Distribution Model Cons”