On the Convergence of FedAvg on Non-IID Data (2019-07-04T00:00:00.000000Z)

TL;DR

This paper analyzes the convergence of Federated Averaging on non-iid data and establishes a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the number of SGDs.

Abstract

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.

Authors

Xiang Li

1 papers

Kaixuan Huang

1 papers

Wenhao Yang

1 papers

TL;DR

Abstract

Authors

References50 items

First Analysis of Local GD on Heterogeneous Data

Federated Learning: Challenges, Methods, and Future Directions

A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression

Asynchronous Federated Optimization

Robust and Communication-Efficient Federated Learning From Non-i.i.d. Data

Federated Reinforcement Learning

Federated Deep Reinforcement Learning

Federated Optimization in Heterogeneous Networks

Sparsified SGD with Memory

Don't Use Large Mini-Batches, Use Local SGD

Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms

Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning

Parallel Restarted SGD for Non-Convex Optimization with Faster Convergence and Less Communication

How To Backdoor Federated Learning

Federated Learning with Non-IID Data

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

Local SGD Converges Fast and Communicates Little

Exploiting Unintended Feature Leakage in Collaborative Learning

Adaptive Federated Learning in Resource Constrained Edge Computing Systems

Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization

Differentially Private Federated Learning: A Client Level Perspective

Practical Secure Aggregation for Privacy-Preserving Machine Learning

GIANT: Globally Improved Approximate Newton Method for Distributed Optimization

On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization

Stochastic, Distributed and Federated Optimization for Machine Learning

Federated Multi-Task Learning

Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning

CoCoA: A General Framework for Communication-Efficient Distributed Optimization

Federated Learning: Strategies for Improving Communication Efficiency

AIDE: Fast and Communication Efficient Distributed Optimization

Distributed Learning with Regularized Least Squares

A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization

Communication-Efficient Learning of Deep Networks from Decentralized Data

Federated Optimization: Distributed Optimization Beyond the Datacenter

Privacy-preserving deep learning

DiSCO: Distributed Optimization for Self-Concordant Empirical Loss

Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing

MLlib: Machine Learning in Apache Spark

Deep learning with Elastic Averaging SGD

Communication Efficient Distributed Machine Learning with the Parameter Server

Scaling Distributed Machine Learning with the Parameter Server

Introductory Lectures on Convex Optimization - A Basic Course

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method

A Functional Approximation Based Distributed Learning Algorithm

Distributed Coordinate Descent Method for Learning with Big Data

Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates

Communication-efficient algorithms for statistical optimization

Communication-efficient Sparse Regression

Distributed optimization: algorithms and convergence rates

Gradient-based learning applied to document recognition

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names