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

arXiv: https://arxiv.org/abs/2101.11203 · HTML: https://mlsanity.com/paper/2101.11203/

## Key facts

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

## Builds on (most cited first, 25 of 25)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Communication-Efficient On-Device Machine Learning: Federated Distillation and Augmentation under Non-IID Private Data](https://mlsanity.com/paper/1811.11479/) (2018)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Semi-Cyclic Stochastic Gradient Descent](https://mlsanity.com/paper/1904.10120/) (2019)
- [LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data](https://mlsanity.com/paper/1811.12629/) (2018)

## Built on by (most cited first, 30 of 193)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correction](https://mlsanity.com/paper/2203.11751/) (2022)
- [Generalized Federated Learning via Sharpness Aware Minimization](https://mlsanity.com/paper/2206.02618/) (2022)
- [Federated Class-Incremental Learning](https://mlsanity.com/paper/2203.11473/) (2022)
- [FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings](https://mlsanity.com/paper/2210.04620/) (2022)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmark](https://mlsanity.com/paper/2311.06750/) (2023)
- [Efficient Parallel Split Learning over Resource-constrained Wireless Edge Networks](https://mlsanity.com/paper/2303.15991/) (2023)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Communication-Efficient Adaptive Federated Learning](https://mlsanity.com/paper/2205.02719/) (2022)
- [No One Left Behind: Real-World Federated Class-Incremental Learning](https://mlsanity.com/paper/2302.00903/) (2023)
- [FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy](https://mlsanity.com/paper/2302.10429/) (2023)
- [Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape](https://mlsanity.com/paper/2305.11584/) (2023)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Improving the Model Consistency of Decentralized Federated Learning](https://mlsanity.com/paper/2302.04083/) (2023)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Anarchic Federated Learning](https://mlsanity.com/paper/2108.09875/) (2021)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Layer-wise Adaptive Model Aggregation for Scalable Federated Learning](https://mlsanity.com/paper/2110.10302/) (2021)
- [Federated Incremental Semantic Segmentation](https://mlsanity.com/paper/2304.04620/) (2023)
- [Faster Adaptive Federated Learning](https://mlsanity.com/paper/2212.00974/) (2022)
- [Make Landscape Flatter in Differentially Private Federated Learning](https://mlsanity.com/paper/2303.11242/) (2023)
- [Optimal Resource Allocation for U-Shaped Parallel Split Learning](https://mlsanity.com/paper/2308.08896/) (2023)
- [A Multi-agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learning](https://mlsanity.com/paper/2201.02932/) (2022)

## 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.