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

  1. Peter Richtárik
  2. Martin Jaggi
  3. Qiang Yang
  4. Dacheng Tao
  5. Jakub Konecný
  6. Percy Liang
  7. Mohit Bansal
  8. Yoshua Bengio

In Computer Networks and Communications

  1. Aryan Mokhtari
  2. Peter Richtárik
  3. Nicolas Loizou
  4. Martin Jaggi
  5. Jianyu Wang
  6. Gauri Joshi
  7. Sebastian U. Stich
  8. Ramtin Pedarsani

In Federated & Distributed Learning

  1. Jianyu Wang
  2. Gauri Joshi
  3. Aryan Mokhtari
  4. Peter Richtárik
  5. Virginia Smith
  6. Jakub Konecný
  7. Mehrdad Mahdavi
  8. Zachary B. Charles

Citations in the corpus