# EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2022.

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

- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [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)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [LoCo: Low-Bit Communication Adaptor for Large-scale Model Training](https://mlsanity.com/paper/2407.04480/) (2024)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [The Panaceas for Improving Low-Rank Decomposition in Communication-Efficient Federated Learning](https://mlsanity.com/paper/2505.23176/) (2025)
- [ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compression](https://mlsanity.com/paper/2303.04622/) (2023)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [Communication-Efficient Distributed Learning with Local Immediate Error Compensation](https://mlsanity.com/paper/2402.11857/) (2024)
- [Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learning](https://mlsanity.com/paper/2408.13787/) (2024)
- [Improved Convergence in Parameter-Agnostic Error Feedback through Momentum](https://mlsanity.com/paper/2511.14501/) (2025)
- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [FedBiF: Communication-Efficient Federated Learning via Bits Freezing](https://mlsanity.com/paper/2509.10161/) (2025)
- [First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions](https://mlsanity.com/paper/2512.21521/) (2025)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [Analysis of Asynchronous Federated Learning: Unraveling the Interactions between Gradient Compression, Delay, and Data Heterogeneity](https://mlsanity.com/paper/2504.19903/) (2025)
- [Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction](https://mlsanity.com/paper/2506.23836/) (2025)
- [Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2511.05593/) (2025)
- [Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedback](https://mlsanity.com/paper/2512.22623/) (2025)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

## Abstract (arXiv)

In this work we focus our attention on distributed optimization problems in the context where the communication time between the server and the workers is non-negligible. We obtain novel methods supporting bidirectional compression (both from the server to the workers and vice versa) that enjoy new state-of-the-art theoretical communication complexity for convex and nonconvex problems. Our bounds are the first that manage to decouple the variance/error coming from the workers-to-server and server-to-workers compression, transforming a multiplicative dependence to an additive one. Moreover, in the convex regime, we obtain the first bounds that match the theoretical communication complexity of gradient descent. Even in this convex regime, our algorithms work with biased gradient estimators, which is non-standard and requires new proof techniques that may be of independent interest. Finally, our theoretical results are corroborated through suitable experiments.