mlsanityData to 14 Oct 2026

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

arXiv 2209.15218 ↗First posted 30 Sep 2022math.OC cs.DCcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 9; 2024: 7; 2025: 10; 2026: 2.

28 papers.

Sort:

By area:

  1. 2023Momentum Provably Improves Error Feedback!cited by 31
  2. 2023DoCoFL: Downlink Compression for Cross-Device Federated Learningcited by 28
  3. 2023THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compressioncited by 15
  4. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  5. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  6. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  7. 2023Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregationcited by 10
  8. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  9. 2024LoCo: Low-Bit Communication Adaptor for Large-scale Model Trainingcited by 6
  10. 2025The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applicationscited by 5
  11. 2025The Panaceas for Improving Low-Rank Decomposition in Communication-Efficient Federated Learningcited by 5
  12. 2023ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compressioncited by 4
16 more
  1. 2024Error Feedback under (L0,L1)-Smoothness: Normalization and Momentumcited by 4
  2. 2024Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channelscited by 2
  3. 2024Communication-Efficient Distributed Learning with Local Immediate Error Compensationcited by 2
  4. 2024Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learningcited by 2
  5. 2025Improved Convergence in Parameter-Agnostic Error Feedback through Momentumcited by 2
  6. 2023CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexitycited by 1
  7. 2024MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizescited by 1
  8. 2025Tight analyses of first-order methods with error feedbackcited by 1
  9. 2025FedBiF: Communication-Efficient Federated Learning via Bits Freezingcited by 1
  10. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 1
  11. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  12. 2025Analysis of Asynchronous Federated Learning: Unraveling the Interactions between Gradient Compression, Delay, and Data Heterogeneitycited by 0
  13. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0
  14. 2025Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learningcited by 0
  15. 2025Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedbackcited by 0
  16. 2026Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compressioncited by 0