mlsanityData to 7 Oct 2026

Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression

arXiv 2609.36610 ↗First posted 29 Sep 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Agnostic federated learning (AFL) seeks a model that performs reliably across m heterogeneous workers, but communication remains a bottleneck. We improve communication efficiency by reducing the number of synchronization rounds via faster convergence and the communication cost per round via compression. We first propose AFL-BR, which updates the dual weights over workers using online mirror ascent with KL divergence and blockwise restarts. It achieves an O((log m)1/4T-1/8) stationarity rate after T update rounds, reducing the m-dependence of the synchronization rounds required for convergence from polynomial to logarithmic order. Building on AFL-BR, we develop AFL-Com by applying bidirectional compression with error feedback (EF). Instead of compressing local gradients, workers apply EF to their dual-weighted gradients, enabling direct control of the aggregated compression error under time-varying weights. We then establish an O((δ-1+(log m)1/4)T-1/8) stationarity rate for AFL-Com under general δ-approximate compressors and improve the δ-dependence from δ-1 to δ-1/2 for additive-and-idempotent compressors with shared randomness (SR). With suitable compression levels, AFL-Com retains the same convergence rate as AFL-BR at a lower per-round communication cost, yielding reductions in total communication complexity by factors of (log m)1/4 with Top-k and (log m)1/2 with Rand-k and SR. Experiments validate the improved synchronization and communication efficiency of our methods.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 48 of its 59 references that are in the map. First posted on arXiv 29 Sep 2026.

Builds on

48 of 59 references.

References · 48

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
  5. 2019Introduction to Online Convex Optimizationcited by 793
  6. 2018LEAF: A Benchmark for Federated Settingscited by 780
  7. 2019Agnostic Federated Learningcited by 451
  8. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
  9. 2018Sparsified SGD with Memorycited by 373
  10. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  11. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  12. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
36 more
  1. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  2. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  3. 2023Heterogeneous Federated Learning: State-of-the-art and Research Challengescited by 160
  4. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  5. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  6. 2020On Biased Compression for Distributed Learningcited by 140
  7. 2021Federated Learning for Open Bankingcited by 138
  8. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  9. 2021Distributionally Robust Federated Averagingcited by 104
  10. 2019Natural Compression for Distributed Deep Learningcited by 88
  11. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  12. 2022Communication-Efficient Adaptive Federated Learningcited by 55
  13. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  14. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  15. 2020Design and Analysis of Uplink and Downlink Communications for Federated Learningcited by 48
  16. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  17. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  18. 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
  19. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  20. 2022EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compressioncited by 28
  21. 2019Inference under Information Constraints II: Communication Constraints and Shared Randomnesscited by 22
  22. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  23. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  24. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  25. 2021Communication-Efficient Agnostic Federated Averagingcited by 10
  26. 2022Communication-Efficient Distributionally Robust Decentralized Learningcited by 10
  27. 2025Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guaranteescited by 9
  28. 2023Scaff-PD: Communication Efficient Fair and Robust Federated Learningcited by 6
  29. 2022DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphscited by 5
  30. 2024Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similaritycited by 5
  31. 2023Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyondcited by 4
  32. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  33. 2019Adaptive and Efficient Algorithms for Tracking the Best Expertcited by 3
  34. 2024Communication-Efficient Federated Group Distributionally Robust Optimizationcited by 3
  35. 2025Group Distributionally Robust Optimization with Flexible Sample Queriescited by 2
  36. 2025Distributionally Robust Federated Learning with Client Drift Minimizationcited by 1

Built on by

Not cited yet.