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

By Haibo Yang, Minghong Fang, Jia Liu. 2021

319 citations recorded by the source corpus.

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 $\mathcal{O}(\frac{1}{\sqrt{mKT}} + \frac{1}{T})$ for full worker participation and a convergence rate $\mathcal{O}(\frac{1}{\sqrt{nKT}} + \frac{1}{T})$ 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$. We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

Federated Class-Incremental Learning (2022, background): “Federated Learning (FL) is a decentralized learning framework that can train a global model by aggregating local model parameters [24, 44, 51, 53].”
On Large-Cohort Training for Federated Learning (2021, background): “Many convergence analyses of federated optimization methods show that larger cohort sizes can lead to improved convergence rates, even without explicit variance reduction (Khaled et al., 2019, 2020; Yang et al., 2021).”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, methodology): “The classic FL approach, FedAvg (Koneˇcn`y et al., 2016; McMahan et al., 2017; Stich, 2019; Yu et al., 2019a; Lin et al., 2020; Wang and Joshi, 2021), performs multiple gradient-descent steps within each accessible client before communicating with the central server.”