On the Convergence of FedAvg on Non-IID Data
By Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, Zhihua Zhang. 2019
3,042 citations recorded by the source corpus.
Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of \texttt{FedAvg} on non-iid data and establish a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for \texttt{FedAvg} on non-iid data: the learning rate $\eta$ must decay, even if full-gradient is used; otherwise, the solution will be $\Omega (\eta)$ away from the optimal.
Subfields: Artificial Intelligence, Computer Networks and Communications, Federated & Distributed Learning
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
- Peter Richtárik
- Martin Jaggi
- Qiang Yang
- Dacheng Tao
- Jakub Konecný
- Percy Liang
- Mohit Bansal
- Yoshua Bengio
In Computer Networks and Communications
- Aryan Mokhtari
- Peter Richtárik
- Nicolas Loizou
- Martin Jaggi
- Jianyu Wang
- Gauri Joshi
- Sebastian U. Stich
- Ramtin Pedarsani
In Federated & Distributed Learning
- Jianyu Wang
- Gauri Joshi
- Aryan Mokhtari
- Peter Richtárik
- Virginia Smith
- Jakub Konecný
- Mehrdad Mahdavi
- Zachary B. Charles
Citations in the corpus
- Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “Following previous works [38, 12, 20, 15], we assume the sampling scheme guarantees that the update rule (12) hold in expectation.”
- Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, background): “It is still widely used and has been studied extensively both from an applied and theoretical standpoint [44, 45].”
- On the Outsized Importance of Learning Rates in Local Update Methods (2020, methodology): “…of federated learning with topics including differential privacy (McMahan et al., 2018; Augenstein et al., 2020), fairness (Mohri et al., 2019; Li et al., 2020b), robustness (Ghosh et al., 2019; Bagdasaryan et al., 2018; Sun et al., 2019), and communication-efficiency (Konečný et al., 2016;…”
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “A second common assumption is to assume that the (stochastic) gradients are uniformly bounded (e.g. Koloskova et al., 2019; Li et al., 2020b), that is for a constant G .”
- Adaptive Federated Optimization (2020, background): “For a more in-depth discussion of federated learning and the challenges therein, we defer to Kairouz et al. (2019) and Li et al. (2019a).”
- Personalized Federated Learning: A Meta-Learning Approach (2020, background): “…paper, there are several works that study statistical heterogeneity of users’ data points in FL (Zhao et al., 2018; Sahu et al., 2018; Karimireddy et al., 2019; Haddadpour and Mahdavi, 2019; Khaled et al., 2019; Li et al., 2019), but they do not attempt to find a personalized solution for each user.”
- Secure Federated Submodel Learning (2019, background): “Recently, Yu et al. [32] and Li et al. [33] advanced the convergency analysis of federated averaging by imposing smooth and bounded assumptions on the loss function.”
- Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “In the study of centralized parallel SGD, the application of local updates inevitably results the residual error [15, 39, 44, 4, 19, 48].”
- SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “Several analyses bound this drift by using a very small step-size and assuming that the local updates admit bounded magnitude (Wang et al., 2019; Yu et al., 2019; Li et al., 2019b).”
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “To address this heterogeneity, other methods such as multitask learning and meta learning have been proposed to train multiple local models [Li et al., 2019b, Nichol et al., 2018, Smith et al., 2017].”
- Improving Federated Learning Personalization via Model Agnostic Meta Learning (2019, background): “Theoretical guarantees are only available under restrictive assumptions and for convex objectives, cf. Li et al. (2019b).”