# Finite-Bit Quantization For Distributed Algorithms With Linear Convergence

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 63 references that are in the map.
- First posted on arXiv 23 Jul 2021.

## Builds on (most cited first, 30 of 32)

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback](https://mlsanity.com/paper/1905.10936/) (2019)
- [A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!](https://mlsanity.com/paper/2011.01697/) (2020)
- [A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks](https://mlsanity.com/paper/1809.00710/) (2018)
- [Quantized Decentralized Stochastic Learning over Directed Graphs](https://mlsanity.com/paper/2002.09964/) (2020)
- [Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs](https://mlsanity.com/paper/1809.01106/) (2018)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [On Communication Compression for Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2009.02388/) (2020)
- [On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication](https://mlsanity.com/paper/1902.11163/) (2019)
- [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [Towards Tight Communication Lower Bounds for Distributed Optimisation](https://mlsanity.com/paper/2010.08222/) (2020)
- [Design and Analysis of Distributed Averaging with Quantized Communication](https://mlsanity.com/paper/1403.4696/) (2014)
- [Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks](https://mlsanity.com/paper/1812.04048/) (2018)
- [Compressed Gradient Tracking Methods for Decentralized Optimization with Linear Convergence](https://mlsanity.com/paper/2103.13748/) (2021)

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

- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Non-Coherent Over-the-Air Decentralized Gradient Descent](https://mlsanity.com/paper/2211.10777/) (2022)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Quantization for decentralized learning under subspace constraints](https://mlsanity.com/paper/2209.07821/) (2022)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Distributed Adaptive Learning Under Communication Constraints](https://mlsanity.com/paper/2112.02129/) (2021)
- [Differential error feedback for communication-efficient decentralized learning](https://mlsanity.com/paper/2406.18418/) (2024)
- [Compressed Regression over Adaptive Networks](https://mlsanity.com/paper/2304.03638/) (2023)
- [ERIS: Enhancing the Privacy-Utility-Scalability Trade-Off in Federated Learning via Federated Shard Aggregation](https://mlsanity.com/paper/2602.08617/) (2026)
- [Decentralized Federated Learning by Partial Message Exchange](https://mlsanity.com/paper/2603.01730/) (2026)
- [Distributed Training of Large Graph Neural Networks with Variable Communication Rates](https://mlsanity.com/paper/2406.17611/) (2024)
- [Quantitative Error Feedback for Quantization Noise Reduction of Filtering over Graphs](https://mlsanity.com/paper/2506.01404/) (2025)
- [Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity](https://mlsanity.com/paper/2607.12172/) (2026)

## Abstract (arXiv)

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Nonuniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules.