# NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization

arXiv: https://arxiv.org/abs/2104.13818 · HTML: https://mlsanity.com/paper/2104.13818/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 28 Apr 2021.

## Builds on (most cited first, 25 of 25)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients](https://mlsanity.com/paper/1606.06160/) (2016)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Deep Speech: Scaling up end-to-end speech recognition](https://mlsanity.com/paper/1412.5567/) (2014)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Horovod: fast and easy distributed deep learning in TensorFlow](https://mlsanity.com/paper/1802.05799/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Convolutional Neural Networks using Logarithmic Data Representation](https://mlsanity.com/paper/1603.01025/) (2016)
- [Deep learning with Elastic Averaging SGD](https://mlsanity.com/paper/1412.6651/) (2014)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [A Unified Analysis of Stochastic Momentum Methods for Deep Learning](https://mlsanity.com/paper/1808.10396/) (2018)
- [Faster CNNs with Direct Sparse Convolutions and Guided Pruning](https://mlsanity.com/paper/1608.01409/) (2016)
- [Petuum: A New Platform for Distributed Machine Learning on Big Data](https://mlsanity.com/paper/1312.7651/) (2013)
- [Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms](https://mlsanity.com/paper/1506.06438/) (2015)
- [Loss-aware Weight Quantization of Deep Networks](https://mlsanity.com/paper/1802.08635/) (2018)

## Abstract (arXiv)

As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes gradients to reduce communication costs. The baseline variant of QSGD provides strong theoretical guarantees, however, for practical purposes, the authors proposed a heuristic variant which we call QSGDinf, which demonstrated impressive empirical gains for distributed training of large neural networks. In this paper, we build on this work to propose a new gradient quantization scheme, and show that it has both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical performance of the QSGDinf heuristic and of other compression methods.