Elamur Research⌕
☰
home / papers / 2016 / QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Paper · 2016 · Dan Alistarh, Demjan Grubic, Jerry Li et al.

Summary

Data-parallel SGD over many GPUs is often slowed by the need to exchange full dense gradients at every step. Earlier lossy compression tricks, such as 1BitSGD, work in practice but lack convergence proofs. The authors propose QSGD, a family of gradient compressors with two parts. First, each gradient coordinate is randomly rounded to one of a few levels in a way that stays unbiased. Second, a lossless integer code (Elias-style) exploits the sparse, skewed values that rounding produces. The number of levels sets the trade-off between bits sent and extra variance. The authors prove tight bounds on this trade-off and argue, via lower bounds for distributed mean estimation, that it cannot be improved asymptotically. Convergence guarantees cover convex and non-convex objectives and asynchronous updates, and there is a variance-reduced variant called QSVRG. QSGD was implemented in Microsoft CNTK and tested on AlexNet, VGG, Inception, ResNet, an LSTM and an MLP. It cut wall-clock training time markedly, for example ResNet-152 on ImageNet with 16 GPUs about 1.8× faster, with no meaningful accuracy loss. This gives a principled, nearly tuning-free way to scale training when bandwidth is the bottleneck.

Key points

  • Theoretical bounds at two extremes:
    • In the sparsest setting, roughly √n(log n + O(1)) bits per iteration, at a variance increase of up to √n.
    • In the denser setting, about 2.8n + 32 bits, at only 2× variance.
    • Against 32n bits for full precision, the denser setting saves about 5.7× in bandwidth.
  • Communication share of training time: with full 32-bit gradients, communication took over 80% of training time for AlexNet (16 GPUs, batch 1024) and 71% for the LSTM on AN4 (2 GPUs, batch 256).
  • Speedups with 4-bit QSGD:
    • AlexNet on 16 GPUs: communication time cut 4×, epoch time 2.5×.
    • LSTM: communication time cut 6.8×, epoch time 2.7×.
  • Accuracy: 8-bit gradients with bucket size 512 matched or slightly beat full-precision accuracy in every reported run, covering ImageNet, CIFAR-10 (ResNet110), AN4 and MNIST.
  • Limits of aggressive settings:
    • 4-bit with bucket size 8192 lost 0.57% top-5 and 0.68% top-1 on AlexNet.
    • 2-bit with bucket size 64 lost up to 1.73% top-1.
    • Convolutional layers were the most sensitive to coarse quantization.

Interesting ideas

  • I1. Treat compression as zero-mean noise. Making the quantizer unbiased turns compression into extra noise, so standard SGD convergence results apply almost unchanged. The same idea could justify other lossy shortcuts in any stochastic optimizer.
  • I2. Quantize, then entropy-code. Coarse rounding makes values sparse and skewed, which a lossless code can then compress well. This two-stage design fits other settings where large numeric arrays must be shipped, such as embeddings or model deltas.
  • I3. Use buckets as a tuning knob. Normalizing and quantizing small chunks (buckets) instead of the whole vector controls the variance–size trade-off. Bucket size becomes a simple dial for accuracy versus bandwidth.
  • I4. Profile before optimizing. The authors first measured each network's split between communication and computation as GPU count grew. This kind of profiling shows where compression will pay off, for example communication-heavy AlexNet and LSTM versus compute-heavy ResNet and Inception.
  • I5. Skip tiny tensors. Small tensors were left in full precision because quantizing them costs more than it saves, yet over 99% of parameters were still compressed. This pragmatic exception rule is worth copying in any compression pipeline.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 worksHardware and Architecture · 167 works

Cite

Cite as Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka and Milan Vojnovic. 2016. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. arXiv:1610.02132.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1610.02132 · arXiv 1610.02132

@misc{alistarh2016qsgd,
  title = {{QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding}},
  author = {Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka and Milan Vojnovic},
  year = {2016},
  doi = {10.48550/arxiv.1610.02132},
  eprint = {1610.02132},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1610.02132}
}

References

45 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Martın Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016.
  2. Alex Acero. Acoustical and environmental robustness in automatic speech recognition, volume 201. Springer Science & Business Media, 2012. find
  3. Amit Agarwal, Eldar Akchurin, Chris Basoglu, Guoguo Chen, Scott Cyphers, Jasha Droppo, Adam Eversole, Brian Guenter, Mark Hillebrand, Ryan Hoens, et al. An introduction to computational networks and the computational network toolkit. Technical report, Tech. Rep. MSR-TR-2014-112, August 2014., 2014. find
  4. Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient SGD via gradient quantization and encoding. arXiv preprint arXiv:1610.02132, 2016. — [arXiv:1610.02132](https://arxiv.org/abs/1610.02132)
  5. Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In NIPS, 2015. find
  6. Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011. find
  7. Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends R in Machine Learning, 8(3-4):231–357, 2015. find
  8. Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In OSDI, October 2014. find
  9. Cntk brainscript file for alexnet. https://github.com/Microsoft/CNTK/tree/master/Examples/Image/Classification/AlexNet/BrainScript. Accessed: 2017-02-24. ↗
  10. Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré. Taming the wild: A unified analysis of hogwild-style algorithms. In NIPS, 2015. find
  11. Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In NIPS, 2012. find
  12. Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pages 248–255. IEEE, 2009. find
  13. John C Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex optimization. NIPS, 2015. find
  14. Peter Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 21(2):194–203, 1975. find
  15. Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013. find
  16. Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In ICML, pages 1737–1746, 2015. find
  17. Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015. find
  18. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
  19. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997. find
  20. Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems, pages 4107–4115, 2016. find
  21. Forrest N Iandola, Matthew W Moskewicz, Khalid Ashraf, and Kurt Keutzer. Firecaffe: near-linear acceleration of deep neural network training on compute clusters. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2592–2600, 2016. find
  22. Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015. find
  23. Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013. find
  24. Jakub Konečnỳ. Stochastic, distributed and federated optimization for machine learning. arXiv preprint arXiv:1707.01155, 2017. — [arXiv:1707.01155](https://arxiv.org/abs/1707.01155) find
  25. Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images, 2009. find
  26. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012.
  27. Yann LeCun, Corinna Cortes, and Christopher JC Burges. The mnist database of handwritten digits, 1998. find
  28. Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In OSDI, 2014. find
  29. Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In NIPS. 2015. find
  30. Arvind Neelakantan, Luke Vilnis, Quoc V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.06807, 2015. find
  31. Cntk implementation of qsgd. https://gitlab.com/demjangrubic/QSGD. Accessed: 2017-11-4. ↗
  32. Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In NIPS, 2011. find
  33. Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407, 1951. find
  34. Richard Schreier and Gabor C Temes. Understanding delta-sigma data converters, volume 74. IEEE Press, Piscataway, NJ, 2005. find
  35. Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In INTERSPEECH, 2014. find
  36. Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
  37. Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In INTERSPEECH, 2015. find
  38. Ananda Theertha Suresh, Felix X Yu, H Brendan McMahan, and Sanjiv Kumar. Distributed mean estimation with limited communication. arXiv preprint arXiv:1611.00429, 2016. — [arXiv:1611.00429](https://arxiv.org/abs/1611.00429) find
  39. Seiya Tokui, Kenta Oono, Shohei Hido, CA San Mateo, and Justin Clayton. Chainer: a next-generation open source framework for deep learning. In Proceedings of workshop on machine learning systems (LearningSys), 2015. find
  40. John N Tsitsiklis and Zhi-Quan Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3), 1987. find
  41. Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. arXiv preprint arXiv:1705.07878, 2017. — [arXiv:1705.07878](https://arxiv.org/abs/1705.07878) find
  42. Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning, pages 4035–4043, 2017. find
  43. Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. In Advances in Neural Information Processing Systems, pages 685–693, 2015. find
  44. Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS, 2013. find
  45. Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint arXiv:1606.06160, 2016. Roadmap of the Appendix

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/alistarh-2016-qsgd-communication-efficient-sgd-gradient/