# On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication

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

## Key facts

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

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

- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Joint Optimization of Communications and Federated Learning Over the Air](https://mlsanity.com/paper/2104.03490/) (2021)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [Non-Coherent Over-the-Air Decentralized Gradient Descent](https://mlsanity.com/paper/2211.10777/) (2022)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Distributed Learning based on 1-Bit Gradient Coding in the Presence of Stragglers](https://mlsanity.com/paper/2403.14716/) (2024)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [Federated Reinforcement Learning at the Edge](https://mlsanity.com/paper/2112.05908/) (2021)
- [Communication-Efficient Distributed SGD with Compressed Sensing](https://mlsanity.com/paper/2112.07836/) (2021)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [BSAC-CoEx: Coexistence of URLLC and Distributed Learning Services via Device Selection](https://mlsanity.com/paper/2212.11805/) (2022)
- [Quantized Adaptive Subgradient Algorithms and Their Applications](https://mlsanity.com/paper/2208.05631/) (2022)
- [Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity](https://mlsanity.com/paper/2607.12172/) (2026)

## Abstract (arXiv)

In distributed optimization and machine learning, multiple nodes coordinate to solve large problems. To do this, the nodes need to compress important algorithm information to bits so that it can be communicated over a digital channel. The communication time of these algorithms follows a complex interplay between a) the algorithm's convergence properties, b) the compression scheme, and c) the transmission rate offered by the digital channel. We explore these relationships for a general class of linearly convergent distributed algorithms. In particular, we illustrate how to design quantizers for these algorithms that compress the communicated information to a few bits while still preserving the linear convergence. Moreover, we characterize the communication time of these algorithms as a function of the available transmission rate. We illustrate our results on learning algorithms using different communication structures, such as decentralized algorithms where a single master coordinates information from many workers and fully distributed algorithms where only neighbours in a communication graph can communicate. We conclude that a co-design of machine learning and communication protocols are mandatory to flourish machine learning over networks.