# QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

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

## Key facts

- Cited by 147 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2016.

## Built on by (most cited first, 30 of 147)

- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [FedPara: Low-Rank Hadamard Product for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.06098/) (2021)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.04487/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)
- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Permutation Compressors for Provably Faster Distributed Nonconvex Optimization](https://mlsanity.com/paper/2110.03300/) (2021)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergence](https://mlsanity.com/paper/2204.08125/) (2022)
- [Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimization](https://mlsanity.com/paper/2201.07912/) (2022)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulations](https://mlsanity.com/paper/2203.13789/) (2022)
- [Time-Correlated Sparsification for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2101.08837/) (2021)
- [QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning](https://mlsanity.com/paper/2106.00797/) (2021)
- [Accurate Neural Training with 4-bit Matrix Multiplications at Standard Formats](https://mlsanity.com/paper/2112.10769/) (2021)
- [Scaling Language Model Size in Cross-Device Federated Learning](https://mlsanity.com/paper/2204.09715/) (2022)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Learned Gradient Compression for Distributed Deep Learning](https://mlsanity.com/paper/2103.08870/) (2021)
- [Scheduling and Aggregation Design for Asynchronous Federated Learning over Wireless Networks](https://mlsanity.com/paper/2212.07356/) (2022)

## Abstract (arXiv)

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.