# On Communication Compression for Distributed Optimization on Heterogeneous Data

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

## Key facts

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

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

- [ProgFed: Effective, Communication, and Computation Efficient Federated Learning by Progressive Training](https://mlsanity.com/paper/2110.05323/) (2021)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Data-Aware Gradient Compression for FL in Communication-Constrained Mobile Computing](https://mlsanity.com/paper/2311.07324/) (2023)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [Accelerated Distributed Optimization with Compression and Error Feedback](https://mlsanity.com/paper/2503.08427/) (2025)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Accelerating Parallel Diffusion Model Serving with Residual Compression](https://mlsanity.com/paper/2507.17511/) (2025)
- [Composite Optimization with Error Feedback: the Dual Averaging Approach](https://mlsanity.com/paper/2510.03507/) (2025)
- [γ-FedHT: Stepsize-Aware Hard-Threshold Gradient Compression in Federated Learning](https://mlsanity.com/paper/2505.12479/) (2025)
- [Taming Latency and Bandwidth: A Theoretical Framework and Adaptive Algorithm for Communication-Constrained Training](https://mlsanity.com/paper/2507.17346/) (2025)
- [Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications](https://mlsanity.com/paper/2604.09276/) (2026)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

Lossy gradient compression, with either unbiased or biased compressors, has become a key tool to avoid the communication bottleneck in centrally coordinated distributed training of machine learning models. We analyze the performance of two standard and general types of methods: (i) distributed quantized SGD (D-QSGD) with arbitrary unbiased quantizers and (ii) distributed SGD with error-feedback and biased compressors (D-EF-SGD) in the heterogeneous (non-iid) data setting. Our results indicate that D-EF-SGD is much less affected than D-QSGD by non-iid data, but both methods can suffer a slowdown if data-skewness is high. We further study two alternatives that are not (or much less) affected by heterogenous data distributions: first, a recently proposed method that is effective on strongly convex problems, and secondly, we point out a more general approach that is applicable to linear compressors only but effective in all considered scenarios.