mlsanityData to 14 Oct 2026

Can 5th Generation Local Training Methods Support Client Sampling? Yes!

arXiv 2212.14370 ↗First posted 29 Dec 2022cs.LG cs.DC math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

The celebrated FedAvg algorithm of McMahan et al. (2017) is based on three components: client sampling (CS), data sampling (DS) and local training (LT). While the first two are reasonably well understood, the third component, whose role is to reduce the number of communication rounds needed to train the model, resisted all attempts at a satisfactory theoretical explanation. Malinovsky et al. (2022) identified four distinct generations of LT methods based on the quality of the provided theoretical communication complexity guarantees. Despite a lot of progress in this area, none of the existing works were able to show that it is theoretically better to employ multiple local gradient-type steps (i.e., to engage in LT) than to rely on a single local gradient-type step only in the important heterogeneous data regime. In a recent breakthrough embodied in their ProxSkip method and its theoretical analysis, Mishchenko et al. (2022) showed that LT indeed leads to provable communication acceleration for arbitrarily heterogeneous data, thus jump-starting the 5rm th generation of LT methods. However, while these latest generation LT methods are compatible with DS, none of them support CS. We resolve this open problem in the affirmative. In order to do so, we had to base our algorithmic development on new algorithmic and theoretical foundations.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 44 of its 60 references that are in the map. First posted on arXiv 29 Dec 2022.

Builds on

44 of 60 references.

References · 44

  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. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 564
  7. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  8. 2021A Field Guide to Federated Optimizationcited by 315
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  12. 2019SGD: General Analysis and Improved Ratescited by 207
32 more
  1. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 175
  2. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  3. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  4. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  5. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  6. 2020Optimal Client Sampling for Federated Learningcited by 124
  7. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  8. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  9. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  10. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  11. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  12. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  13. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  14. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  15. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  16. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  17. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  18. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  19. 2015A Three-Operator Splitting Scheme and its Optimization Applicationscited by 34
  20. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  21. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  22. 2014Communication-Efficient Distributed Dual Coordinate Ascentcited by 31
  23. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 28
  24. 2015Distributed Optimization with Arbitrary Local Solverscited by 23
  25. 2015Adding vs. Averaging in Distributed Primal-Dual Optimizationcited by 19
  26. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  27. 2016A Simple Practical Accelerated Method for Finite Sumscited by 18
  28. 2018Nonconvex Variance Reduced Optimization with Arbitrary Samplingcited by 14
  29. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 14
  30. 2013Semi-Stochastic Gradient Descent Methodscited by 13
  31. 2015SparkNet: Training Deep Networks in Sparkcited by 13
  32. 2022Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Samplingcited by 10

Built on by

Cited by year

Citing papers per year: 2023: 8; 2024: 12; 2025: 2.

22 papers.

Sort:

  1. 2024PrE-Text: Training Language Models on Private Federated Data in the Age of LLMscited by 29
  2. 2023Federated Learning with Regularized Client Participationcited by 14
  3. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  4. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  5. 2024Federated Optimization with Doubly Regularized Drift Correctioncited by 10
  6. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 9
  7. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 8
  8. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  9. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 7
  10. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  11. 2023Explicit Personalization and Local Training: Double Communication Acceleration in Federated Learningcited by 5
  12. 2024FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Modelscited by 5
10 more
  1. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  2. 2023Distributed Stochastic Optimization under a General Variance Conditioncited by 4
  3. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 4
  4. 2024A survey on secure decentralized optimization and learningcited by 4
  5. 2024Enhancing Privacy in Federated Learning through Local Trainingcited by 3
  6. 2024Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participationcited by 3
  7. 2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
  8. 2024A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needscited by 2
  9. 2024Convergent Differential Privacy Analysis for General Federated Learningcited by 0
  10. 2025Communication-Efficient Learning for Satellite Constellationscited by 0