First Analysis of Local GD on Heterogeneous Data

Abstract

We provide the first convergence analysis of local gradient descent for minimizing the average of smooth and convex but otherwise arbitrary functions. Problems of this form and local gradient descent as a solution method are of importance in federated learning, where each function is based on private data stored by a user on a mobile device, and the data of different users can be arbitrarily heterogeneous. We show that in a low accuracy regime, the method has the same communication complexity as gradient descent.

arXiv commentNeurIPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality. 11 pages, 4 lemmas, 1 theorem

References in corpus (12)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning for Mobile Keyboard Prediction
• On the Convergence of FedAvg on Non-IID Data
• Federated Optimization in Heterogeneous Networks
• Local SGD Converges Fast and Communicates Little
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Adaptive Federated Learning in Resource Constrained Edge Computing Systems
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Revisiting Stochastic Extragradient
• Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning

Cited by in corpus (41)

• On the Convergence of FedAvg on Non-IID Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Federated Learning of a Mixture of Global and Local Models
• Personalized Federated Learning with Moreau Envelopes
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• On the Convergence of Local Descent Methods in Federated Learning
• Adaptive Federated Optimization
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning With Quantized Global Model Updates
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• A Theoretical Perspective on Differentially Private Federated Multi-task Learning
• Communication-Efficient Robust Federated Learning Over Heterogeneous Datasets
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Gradient Descent with Compressed Iterates
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• From Local SGD to Local Fixed-Point Methods for Federated Learning
• RingFed: Reducing Communication Costs in Federated Learning on Non-IID Data
• Federated Semi-Supervised Learning with Class Distribution Mismatch
• Anarchic Federated Learning
• Communication-Efficient Distributed SVD via Local Power Iterations
• Cost-Effective Federated Learning in Mobile Edge Networks
• Vertical federated learning based on DFP and BFGS
• Energy-Efficient Resource Management for Federated Edge Learning with CPU-GPU Heterogeneous Computing
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Proximal and Federated Random Reshuffling
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• On Large-Cohort Training for Federated Learning
• Cost-Effective Federated Learning Design
• An Operator Splitting View of Federated Learning
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• Differential Privacy Meets Federated Learning under Communication Constraints
• DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Federated Submodel Optimization for Hot and Cold Data Features
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Iterated Vector Fields and Conservatism, with Applications to Federated Learning