Federated Optimization in Heterogeneous Networks (2018-12-14T00:00:00.000000Z)

TL;DR

This work introduces a framework, FedProx, to tackle heterogeneity in federated networks, and provides convergence guarantees for this framework when learning over data from non-identical distributions (statistical heterogeneity), and while adhering to device-level systems constraints by allowing each participating device to perform a variable amount of work.

Abstract

Federated Learning is a distributed learning paradigm with two key challenges that differentiate it from traditional distributed optimization: (1) significant variability in terms of the systems characteristics on each device in the network (systems heterogeneity), and (2) non-identically distributed data across the network (statistical heterogeneity). In this work, we introduce a framework, FedProx, to tackle heterogeneity in federated networks. FedProx can be viewed as a generalization and re-parametrization of FedAvg, the current state-of-the-art method for federated learning. While this re-parameterization makes only minor modifications to the method itself, these modifications have important ramifications both in theory and in practice. Theoretically, we provide convergence guarantees for our framework when learning over data from non-identical distributions (statistical heterogeneity), and while adhering to device-level systems constraints by allowing each participating device to perform a variable amount of work (systems heterogeneity). Practically, we demonstrate that FedProx allows for more robust convergence than FedAvg across a suite of realistic federated datasets. In particular, in highly heterogeneous settings, FedProx demonstrates significantly more stable and accurate convergence behavior relative to FedAvg---improving absolute test accuracy by 22% on average.

Authors

M. Zaheer

8 papers

Ameet Talwalkar

10 papers

Virginia Smith

6 papers

TL;DR

Abstract

Authors

References50 items

Unraveling Meta-Learning: Understanding Feature Representations for Few-Shot Tasks

FedDANE: A Federated Newton-Type Method

Federated Learning: Challenges, Methods, and Future Directions

Adaptive Gradient-Based Meta-Learning Methods

On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

Towards Federated Learning at Scale: System Design

LEAF: A Benchmark for Federated Settings

A Linear Speedup Analysis of Distributed Deep Learning with Sparse and Quantized Communication

LoAdaBoost: Loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data

LoAdaBoost: Loss-Based AdaBoost Federated Machine Learning on medical Data

Communication-Efficient On-Device Machine Learning: Federated Distillation and Augmentation under Non-IID Private Data

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

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 for Non-Convex Optimization with Faster Convergence and Less Communication

Federated Learning with Non-IID Data

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

Local SGD Converges Fast and Communicates Little

Adaptive Federated Learning in Resource Constrained Edge Computing Systems

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

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

Gradient Diversity: a Key Ingredient for Scalable Distributed Learning

Federated Multi-Task Learning

EMNIST: an extension of MNIST to handwritten letters

CoCoA: A General Framework for Communication-Efficient Distributed Optimization

AIDE: Fast and Communication Efficient Distributed Optimization

Communication-Efficient Learning of Deep Networks from Decentralized Data

Deep learning with Elastic Averaging SGD

Communication Efficient Distributed Machine Learning with the Parameter Server

GloVe: Global Vectors for Word Representation

Efficient mini-batch training for stochastic optimization

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

Distributed Coordinate Descent Method for Learning with Big Data

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition

Large Scale Distributed Deep Networks

Communication-efficient algorithms for statistical optimization

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

Optimal Distributed Online Prediction Using Mini-Batches

On Early Stopping in Gradient Descent Learning

A Randomized Kaczmarz Algorithm with Exponential Convergence

Approximate solution of systems of linear equations

Efficient Meta Learning via Minibatch Proximal Update

Federated Optimization in Heterogeneous Networks Bounded dissimilarity assumption. The bounded dissimilarity assumption we discuss in Assumption 1 has appeared in different forms, for example

character per training sample after 2 LSTM layers and a densely-connected layer

Twitter Sentiment Classiﬁcation using Distant Supervision

GradientBased Learning Applied to Document Recognition

Gradient-based learning applied to document recognition

This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Tensorflow: a System for Large-scale Machine Learning Tensorflow: a System for Large-scale Machine Learning

Tensorflow federated: Machine learning on decentralized data

Field of Study

Journal Information

Name

Venue Information

Name

Type

URL

Alternate Names