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

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2019.

## Built on by (most cited first, 18 of 18)

- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [Large-Scale Deep Learning Optimizations: A Comprehensive Survey](https://mlsanity.com/paper/2111.00856/) (2021)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [Communication-Efficient Design for Quantized Decentralized Federated Learning](https://mlsanity.com/paper/2303.08423/) (2023)
- [Federated Learning under Covariate Shifts with Generalization Guarantees](https://mlsanity.com/paper/2306.05325/) (2023)
- [MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks](https://mlsanity.com/paper/2207.07941/) (2022)
- [CGX: Adaptive System Support for Communication-Efficient Deep Learning](https://mlsanity.com/paper/2111.08617/) (2021)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)
- [Optimal and Near-Optimal Adaptive Vector Quantization](https://mlsanity.com/paper/2402.03158/) (2024)
- [L-GreCo: Layerwise-Adaptive Gradient Compression for Efficient and Accurate Deep Learning](https://mlsanity.com/paper/2210.17357/) (2022)
- [Addressing Label Shift in Distributed Learning via Entropy Regularization](https://mlsanity.com/paper/2502.02544/) (2025)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [Entropy-Constrained Adaptive Stochastic Quantization](https://mlsanity.com/paper/2608.18147/) (2026)
- [Contractive error feedback for gradient compression](https://mlsanity.com/paper/2312.08538/) (2023)
- [Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms](https://mlsanity.com/paper/2606.00289/) (2026)

## 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.