mlsanityData to 14 Oct 2026

Improving Accelerated Federated Learning with Compression and Importance Sampling

arXiv 2306.03240 ↗First posted 5 Jun 2023cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Federated Learning is a collaborative training framework that leverages heterogeneous data distributed across a vast number of clients. Since it is practically infeasible to request and process all clients during the aggregation step, partial participation must be supported. In this setting, the communication between the server and clients poses a major bottleneck. To reduce communication loads, there are two main approaches: compression and local steps. Recent work by Mishchenko et al. [2022] introduced the new ProxSkip method, which achieves an accelerated rate using the local steps technique. Follow-up works successfully combined local steps acceleration with partial participation [Grudzie'n et al., 2023, Condat et al. 2023] and gradient compression [Condat et al. [2022]. In this paper, we finally present a complete method for Federated Learning that incorporates all necessary ingredients: Local Training, Compression, and Partial Participation. We obtain state-of-the-art convergence guarantees in the considered setting. Moreover, we analyze the general sampling framework for partial participation and derive an importance sampling scheme, which leads to even better performance. We experimentally demonstrate the advantages of the proposed method in practice.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 67 of its 86 references that are in the map. First posted on arXiv 5 Jun 2023.

Builds on

67 of 86 references.

References · 67

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  6. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  7. 2018Split learning for health: Distributed deep learning without sharing raw patient datacited by 395
  8. 2018Sparsified SGD with Memorycited by 376
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  10. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 356
  11. 2021A Field Guide to Federated Optimizationcited by 315
  12. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
38 more
  1. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  2. 2019SGD: General Analysis and Improved Ratescited by 207
  3. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 201
  4. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  5. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 180
  6. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 175
  7. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
  8. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  9. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  10. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  11. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  12. 2021Federated Learning for Open Bankingcited by 141
  13. 2020Federated Learning for Internet of Things: Recent Advances, Taxonomy, and Open Challengescited by 139
  14. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  15. 2020Optimal Client Sampling for Federated Learningcited by 124
  16. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  17. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  18. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  19. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 99
  20. 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
  21. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  22. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  23. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  24. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  25. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  26. 2021On Large-Cohort Training for Federated Learningcited by 74
  27. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  28. 2018Distributed learning with compressed gradientscited by 55
  29. 2020A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!cited by 42
  30. 2020Stochastic Client Selection for Federated Learning with Volatile Clientscited by 39
  31. 2021Node Selection Toward Faster Convergence for Federated Learning on Non-IID Datacited by 39
  32. 2021Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learningcited by 39
  33. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  34. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 36
  35. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  36. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  37. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  38. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 28

50 most cited of 67 All 67 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 0; 2026: 1.

8 papers.

  1. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  2. 2024Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysiscited by 8
  3. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  4. 2024Correlated Quantization for Faster Nonconvex Distributed Optimizationcited by 3
  5. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  6. 2024A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needscited by 2
  7. 2024Dual-Criterion Model Aggregation in Federated Learning: Balancing Data Quantity and Qualitycited by 0
  8. 2026Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimizationcited by 0