mlsanityData to 14 Oct 2026

Analysis of Asynchronous Federated Learning: Unraveling the Interactions between Gradient Compression, Delay, and Data Heterogeneity

arXiv 2504.19903 ↗First posted 28 Apr 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

In practical federated learning (FL), the large communication overhead between clients and the server is often a significant bottleneck. Gradient compression methods can effectively reduce this overhead, while error feedback (EF) restores model accuracy. Moreover, due to device heterogeneity, synchronous FL often suffers from stragglers and inefficiency-issues that asynchronous FL effectively alleviates. However, in asynchronous FL settings-which inherently face three major challenges: asynchronous delay, data heterogeneity, and flexible client participation-the complex interactions among these system/statistical constraints and compression/EF mechanisms remain poorly understood theoretically. In this paper, we fill this gap through a comprehensive convergence study that adequately decouples and unravels these complex interactions across various FL frameworks. We first consider a basic asynchronous FL framework AsynFL, and establish an improved convergence analysis that relies on fewer assumptions and yields a superior convergence rate than prior studies. We then extend our study to a compressed version, AsynFLC, and derive sufficient conditions for its convergence, indicating the nonlinear interaction between asynchronous delay and compression rate. Our analysis further demonstrates how asynchronous delay and data heterogeneity jointly exacerbate compression-induced errors, thereby hindering convergence. Furthermore, we study the convergence of AsynFLC-EF, the framework that further integrates EF. We prove that EF can effectively reduce the variance of gradient estimation under the aforementioned challenges, enabling AsynFLC-EF to match the convergence rate of AsynFL. We also show that the impact of asynchronous delay and flexible participation on EF is limited to slowing down the higher-order convergence term. Experimental results substantiate our analytical findings very well.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 31 of its 46 references that are in the map. First posted on arXiv 28 Apr 2025.

Builds on

31 of 46 references.

References · 31

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2020Adaptive Federated Optimizationcited by 1,046
  3. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  4. 2018Sparsified SGD with Memorycited by 376
  5. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 310
  6. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  7. 2018The Convergence of Sparsified Gradient Methodscited by 229
  8. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 193
  9. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 190
  10. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  11. 2020On Biased Compression for Distributed Learningcited by 140
  12. 2016Distributed Mean Estimation with Limited Communicationcited by 136
19 more
  1. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  2. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  3. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  4. 2020Ternary Compression for Communication-Efficient Federated Learningcited by 57
  5. 2022Communication-Efficient Adaptive Federated Learningcited by 55
  6. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  7. 2022EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compressioncited by 28
  8. 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedupcited by 23
  9. 2022SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communicationcited by 21
  10. 2022On Distributed Adaptive Optimization with Gradient Compressioncited by 19
  11. 2022A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updatescited by 17
  12. 2024Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updatescited by 14
  13. 2022Unbounded Gradients in Federated Learning with Buffered Asynchronous Aggregationcited by 12
  14. 2023Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimizationcited by 11
  15. 2024FADAS: Towards Federated Adaptive Asynchronous Optimizationcited by 10
  16. 2024Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clientscited by 7
  17. 2022Accelerating Asynchronous Federated Learning Convergence via Opportunistic Mobile Relayingcited by 6
  18. 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
  19. 2024Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delayscited by 2

Built on by

Not cited yet.