Gradient Sparsification for Communication-Efficient Distributed Optimization

By Jianqiao Wangni, Jialei Wang, Ji Liu, Tong Zhang. 2017

605 citations recorded by the source corpus.

Modern large scale machine learning applications require stochastic optimization algorithms to be implemented on distributed computational architectures. A key bottleneck is the communication overhead for exchanging information such as stochastic gradients among different workers. In this paper, to reduce the communication cost we propose a convex optimization formulation to minimize the coding length of stochastic gradients. To solve the optimal sparsification efficiently, several simple and fast algorithms are proposed for approximate solution, with theoretical guaranteed for sparseness. Experiments on $\ell_2$ regularized logistic regression, support vector machines, and convolutional neural networks validate our sparsification approaches.

Subfields: Artificial Intelligence, Computational Mechanics, ML Systems & Hardware, Mathematical Optimization

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 ML Systems & Hardware

In Mathematical Optimization

Citations in the corpus

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].”
Gradient Descent with Compressed Iterates (2019, methodology): “Further, while there is ample work on non-local methods which communicate compressed gradients [1, 3, 11, 34, 35], including methods which perform variance-reduction to remove the variance introduced by compression [10, 23, 24], to the best of our knowledge there is little work on methods performing”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “• random a (Wangni et al., 2018).”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “Previous works mostly focus on a centralized scenario where the compression is assumed to be unbiased [Jiang and Agrawal, 2018, Shen et al., 2018, Wangni et al., 2018, Wen et al., 2017, Zhang et al., 2017].”
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.”
Natural Compression for Distributed Deep Learning (2019, background): “, with the optimized sparsifiers [28, 47], or with [4, 44]), boosting the performance of the system even further.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “• (Advantage over non error-compensated SGD (Alistarh et al., 2017; Wangni et al., 2018)) For non error-compensated SGD, there is no guarantee for convergence in general unless the compression operator is unbiased.”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “…Bernstein et al. (2018, 2019) and Karimireddy et al. (2019) replace each coordinate of the gradient with its sign; Lin et al. (2018); Stich et al. (2018) and Wangni et al. (2018) use the largest few coordinates; and Koneˇcn ` y et al. (2016) and Wang et al. (2018) use a low-rank approximation.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Much sparser vectors can be obtained by random sparsiﬁcation techniques that randomly mask the input vectors and only preserve a constant number of coordinates (Wangni et al., 2018; Konecny & Richt´arik, 2018; Stich et al., 2018).”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “An alternative approach to communication-efficiency is gradient compression techniques (Wangni et al., 2017; Wen et al., 2017; Lin et al., 2017) that quantize the gradients computed by workers.”
Local SGD Converges Fast and Communicates Little (2018, methodology): “Sparsification methods reduce the number of non-zero entries in the stochastic gradient [4, 39].”
Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms (2019, methodology): “There is a recent line of work providing methods for communication reduction in distributed training, including stochastic quantization [1, 27, 26] and 1-bit gradient compression such as SIGNSGD [4, 5].”
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, methodology): “Sparsification methods reduce the number of non-zero entries in the stochastic gradient [3, 40].”
Communication Compression for Decentralized Training (2018, methodology): “The commonly used stochastic unbiased compression include random quantization 1 [Zhang et al., 2017a] and sparsiﬁcation 2 [Wangni et al., 2017, Konečn`y and Richtárik, 2016].”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, methodology): “The idea of viewing gradient sparsification through a meta-optimization lens was also used in [34].”
Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization (2018, methodology): “Other methods imposed sparsity onto gradients during communication, where only a small fraction of gradients get exchanged across nodes in each iteration (Wangni et al., 2017; Lin et al., 2018).”