# DEED: A General Quantization Scheme for Communication Efficiency in Bits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

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

- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)

## Abstract (arXiv)

In distributed optimization, a popular technique to reduce communication is quantization. In this paper, we provide a general analysis framework for inexact gradient descent that is applicable to quantization schemes. We also propose a quantization scheme Double Encoding and Error Diminishing (DEED). DEED can achieve small communication complexity in three settings: frequent-communication large-memory, frequent-communication small-memory, and infrequent-communication (e.g. federated learning). More specifically, in the frequent-communication large-memory setting, DEED can be easily combined with Nesterov's method, so that the total number of bits required is tildeO( √kappa log 1/ε ), where tildeO hides numerical constant and log kappa factors. In the frequent-communication small-memory setting, DEED combined with SGD only requires tildeO( kappa log 1/ε) number of bits in the interpolation regime. In the infrequent communication setting, DEED combined with Federated averaging requires a smaller total number of bits than Federated Averaging. All these algorithms converge at the same rate as their non-quantized versions, while using a smaller number of bits.