# Optimal Gradient Compression for Distributed and Federated Learning

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

## Key facts

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

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

- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [Layer-wise Adaptive Model Aggregation for Scalable Federated Learning](https://mlsanity.com/paper/2110.10302/) (2021)
- [FedHM: Efficient Federated Learning for Heterogeneous Models via Low-rank Factorization](https://mlsanity.com/paper/2111.14655/) (2021)
- [Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimization](https://mlsanity.com/paper/2201.07912/) (2022)
- [Federated Learning with Spiking Neural Networks](https://mlsanity.com/paper/2106.06579/) (2021)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Recycling Model Updates in Federated Learning: Are Gradient Subspaces Low-Rank?](https://mlsanity.com/paper/2202.00280/) (2022)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [Optimizing the Communication-Accuracy Trade-off in Federated Learning with Rate-Distortion Theory](https://mlsanity.com/paper/2201.02664/) (2022)
- [Communication-Efficient Federated Learning for Heterogeneous Edge Devices Based on Adaptive Gradient Quantization](https://mlsanity.com/paper/2212.08272/) (2022)
- [Federated Learning with Flexible Control](https://mlsanity.com/paper/2212.08496/) (2022)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregation](https://mlsanity.com/paper/2308.00263/) (2023)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [Sparsified Secure Aggregation for Privacy-Preserving Federated Learning](https://mlsanity.com/paper/2112.12872/) (2021)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [Shifted Compression Framework: Generalizations and Improvements](https://mlsanity.com/paper/2206.10452/) (2022)
- [Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design](https://mlsanity.com/paper/2211.03942/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Addressing Client Drift in Federated Continual Learning with Adaptive Optimization](https://mlsanity.com/paper/2203.13321/) (2022)
- [TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation](https://mlsanity.com/paper/2302.09832/) (2023)
- [Accelerated Distributed Optimization with Compression and Error Feedback](https://mlsanity.com/paper/2503.08427/) (2025)
- [Wyner-Ziv Gradient Compression for Federated Learning](https://mlsanity.com/paper/2111.08277/) (2021)
- [Towards cost-effective and resource-aware aggregation at Edge for Federated Learning](https://mlsanity.com/paper/2204.07767/) (2022)
- [Divide-and-Conquer the NAS puzzle in Resource Constrained Federated Learning Systems](https://mlsanity.com/paper/2305.07135/) (2023)
- [Quantized and Asynchronous Federated Learning](https://mlsanity.com/paper/2410.00242/) (2024)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)

## Abstract (arXiv)

Communicating information, like gradient vectors, between computing nodes in distributed and federated learning is typically an unavoidable burden, resulting in scalability issues. Indeed, communication might be slow and costly. Recent advances in communication-efficient training algorithms have reduced this bottleneck by using compression techniques, in the form of sparsification, quantization, or low-rank approximation. Since compression is a lossy, or inexact, process, the iteration complexity is typically worsened; but the total communication complexity can improve significantly, possibly leading to large computation time savings. In this paper, we investigate the fundamental trade-off between the number of bits needed to encode compressed vectors and the compression error. We perform both worst-case and average-case analysis, providing tight lower bounds. In the worst-case analysis, we introduce an efficient compression operator, Sparse Dithering, which is very close to the lower bound. In the average-case analysis, we design a simple compression operator, Spherical Compression, which naturally achieves the lower bound. Thus, our new compression schemes significantly outperform the state of the art. We conduct numerical experiments to illustrate this improvement.