mlsanityData to 7 Oct 2026

Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning

arXiv 2101.11203 ↗First posted 27 Jan 2021cs.LG cs.DCcited by 192

Not on the map. Why?

Abstract (arXiv)

Federated learning (FL) is a distributed machine learning architecture that leverages a large number of workers to jointly learn a model with decentralized data. FL has received increasing attention in recent years thanks to its data privacy protection, communication efficiency and a linear speedup for convergence in training (i.e., convergence performance increases linearly with respect to the number of workers). However, existing studies on linear speedup for convergence are only limited to the assumptions of i.i.d. datasets across workers and/or full worker participation, both of which rarely hold in practice. So far, it remains an open question whether or not the linear speedup for convergence is achievable under non-i.i.d. datasets with partial worker participation in FL. In this paper, we show that the answer is affirmative. Specifically, we show that the federated averaging (FedAvg) algorithm (with two-sided learning rates) on non-i.i.d. datasets in non-convex settings achieves a convergence rate O(frac1√mKT + frac1T) for full worker participation and a convergence rate O(frac√K√nT + frac1T) for partial worker participation, where K is the number of local steps, T is the number of total communication rounds, m is the total worker number and n is the worker number in one communication round if for partial worker participation. Our results also reveal that the local steps in FL could help the convergence and show that the maximum number of local steps can be improved to T/m in full worker participation. We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.

Key facts. Cited by 192 papers in the map (data through 7 Oct 2026). Builds on 25 of its 30 references that are in the map. First posted on arXiv 27 Jan 2021.

Builds on

25 of 30 references.

References · 25

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  6. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  7. 2018Federated Learning with Non-IID Datacited by 1,099
  8. 2020Adaptive Federated Optimizationcited by 1,036
  9. 2019Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classificationcited by 836
  10. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  11. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  12. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
13 more
  1. 2018Adaptive Federated Learning in Resource Constrained Edge Computing Systemscited by 408
  2. 2018Sparsified SGD with Memorycited by 373
  3. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  4. 2018Communication-Efficient On-Device Machine Learning: Federated Distillation and Augmentation under Non-IID Private Datacited by 242
  5. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  6. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  7. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  8. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  9. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  10. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 91
  11. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  12. 2019Semi-Cyclic Stochastic Gradient Descentcited by 40
  13. 2018LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care datacited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 42; 2023: 52; 2024: 44; 2025: 23; 2026: 14.

192 papers.

Sort:

By area:

  1. 2021A Field Guide to Federated Optimizationcited by 312
  2. 2022FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correctioncited by 181
  3. 2022Generalized Federated Learning via Sharpness Aware Minimizationcited by 144
  4. 2022Federated Class-Incremental Learningcited by 126
  5. 2022FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settingscited by 121
  6. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 100
  7. 2023Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmarkcited by 97
  8. 2023Efficient Parallel Split Learning over Resource-constrained Wireless Edge Networkscited by 95
  9. 2021On Large-Cohort Training for Federated Learningcited by 73
  10. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  11. 2021Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacycited by 66
  12. 2021Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Samplingcited by 66
38 more
  1. 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
  2. 2022Communication-Efficient Adaptive Federated Learningcited by 55
  3. 2023No One Left Behind: Real-World Federated Class-Incremental Learningcited by 53
  4. 2023FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracycited by 49
  5. 2023Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscapecited by 46
  6. 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
  7. 2023Improving the Model Consistency of Decentralized Federated Learningcited by 45
  8. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  9. 2021Anarchic Federated Learningcited by 42
  10. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  11. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 37
  12. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  13. 2023Federated Incremental Semantic Segmentationcited by 36
  14. 2021Layer-wise Adaptive Model Aggregation for Scalable Federated Learningcited by 35
  15. 2022Faster Adaptive Federated Learningcited by 35
  16. 2023Make Landscape Flatter in Differentially Private Federated Learningcited by 33
  17. 2023Optimal Resource Allocation for U-Shaped Parallel Split Learningcited by 33
  18. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  19. 2022A Multi-agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learningcited by 28
  20. 2022Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimizationcited by 28
  21. 2023GradMA: A Gradient-Memory-based Accelerated Federated Learning with Alleviated Catastrophic Forgettingcited by 27
  22. 2022FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networkscited by 24
  23. 2022DELTA: Diverse Client Sampling for Fasting Federated Learningcited by 24
  24. 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedupcited by 23
  25. 2023Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initializationcited by 21
  26. 2024FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extractioncited by 21
  27. 2021Context-Aware Online Client Selection for Hierarchical Federated Learningcited by 20
  28. 2023Achieving Linear Speedup in Non-IID Federated Bilevel Learningcited by 18
  29. 2024Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Modelcited by 17
  30. 2022Semi-Decentralized Federated Learning with Collaborative Relayingcited by 16
  31. 2023A Survey for Federated Learning Evaluations: Goals and Measurescited by 16
  32. 2023On the Role of Server Momentum in Federated Learningcited by 16
  33. 2021Optimal Rate Adaption in Federated Learning with Compressed Communicationscited by 15
  34. 2023Accelerating Hybrid Federated Learning Convergence under Partial Participationcited by 15
  35. 2024FedImpro: Measuring and Improving Client Update in Federated Learningcited by 15
  36. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  37. 2021Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradientscited by 13
  38. 2023Federated Learning with Regularized Client Participationcited by 13

50 most cited of 192 All 192 (JSON)