QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks

By Dan Alistarh, Demjan Grubic, Jerry Zheng Li, Ryota Tomioka, Milan Vojnovic. 2016

391 citations recorded by the source corpus.

Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to excellent scalability properties of this algorithm, and to its efficiency in the context of training deep neural networks. A fundamental barrier for parallelizing large-scale SGD is the fact that the cost of communicating the gradient updates between nodes can be very large. Consequently, lossy compression heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always provably converge, and it is not clear whether they are optimal. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes which allow the compression of gradient updates at each node, while guaranteeing convergence under standard assumptions. QSGD allows the user to trade off compression and convergence time: it can communicate a sublinear number of bits per iteration in the model dimension, and can achieve asymptotically optimal communication cost. We complement our theoretical results with empirical data, showing that QSGD can significantly reduce communication cost, while being competitive with standard uncompressed techniques on a variety of real tasks. In particular, experiments show that gradient quantization applied to training of deep neural networks for image classification and automated speech recognition can lead to significant reductions in communication cost, and end-to-end training time. For instance, on 16 GPUs, we are able to train a ResNet-152 network on ImageNet 1.8x faster to full accuracy. Of note, we show that there exist generic parameter settings under which all known network architectures preserve or slightly improve their full accuracy when using quantization.

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

In Optimization & Training

Citations in the corpus

Beyond human-level accuracy: computational challenges in deep learning (2019, background): “Prior work also explores other forms of data parallelism [20, 23, 28], and there are opportunities to reduce data communication overheads of parallelism [5, 21, 37].”
Advances and Open Problems in Federated Learning (2019, background): “Much of the existing literature applies to the objective (a) [245, 376, 244, 20, 204].”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “Previous works in the mean estimation problem [8], [12], [20], [21], [22], [23] mainly focus on reducing communication cost, for instance, by random rotation [12] and sparsification [20], [21], [24], [25].”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “In [4, 40, 44], random quantization schemes are studied.”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Note that various approaches to gradient compression have been proposed to reduce the communication overhead for ALLREDUCE and decentralized learning methods (Alistarh et al., 2007; Wen et al., 2007; Bernstein et al., 2019; Karimireddy et al., 2019; Koloskova et al., 2019b; Vogels et al., 2019).”
Gradient Descent with Compressed Iterates (2019, methodology): “As a result, there are many algorithms designed with the goal of reducing communication in stochastic gradient methods: including SignSGD (1-bit quantization) [4], TernGrad (ternary quantization) [35], QSGD [1], DIANA (with arbitrary quantization) [11], ChocoSGD [15], and others, see e.”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, methodology): “[Alistarh et al., 2017]) the algorithm converges k times slower:”
Wireless Network Intelligence at the Edge (2018, background): “On top of these methods, one can further enhance communication efficiency, by additionally quantizing gradients [191], removing insignificant gradients, i.”
Local SGD Converges Fast and Communicates Little (2018, methodology): “For instance, by limiting the number of bits in the floating point representation [12, 24, 30], or random quantization [4, 40].”
Randomized Distributed Mean Estimation: Accuracy vs. Communication (2016, methodology): “Other works that were published since, such as [14, 15], propose algorithms that can also be represented as a particular choice of protocols α,β , γ , demonstrating the versatility of our proposal.”
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 [Alistarh et al., 2017, Wen et al., 2017] and 1-bit gradient compression such as signSGD [Bernstein et al., 2018a,b] Byzantine robust optimization. Byzantine robust”
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.”
TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning (2017, background): “For the same purpose, quantizing gradients to low-precision values with smaller bit width has also been extensively studied [22][25][26][27].”
Sparsified SGD with Memory (2018, methodology): “3 Comparison with QSGD Now we compare Mem-SGD with the QSGD compression scheme [3] which reduces communication cost by random quantization.”
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].”