On the Convergence of Local Descent Methods in Federated Learning

Abstract

In federated distributed learning, the goal is to optimize a global training objective defined over distributed devices, where the data shard at each device is sampled from a possibly different distribution (a.k.a., heterogeneous or non i.i.d. data samples). In this paper, we generalize the local stochastic and full gradient descent with periodic averaging-- originally designed for homogeneous distributed optimization, to solve nonconvex optimization problems in federated learning. Although scant research is available on the effectiveness of local SGD in reducing the number of communication rounds in homogeneous setting, its convergence and communication complexity in heterogeneous setting is mostly demonstrated empirically and lacks through theoretical understating. To bridge this gap, we demonstrate that by properly analyzing the effect of unbiased gradients and sampling schema in federated setting, under mild assumptions, the implicit variance reduction feature of local distributed methods generalize to heterogeneous data shards and exhibits the best known convergence rates of homogeneous setting both in general nonconvex and under {\pl}~ condition (generalization of strong-convexity). Our theoretical results complement the recent empirical studies that demonstrate the applicability of local GD/SGD to federated learning. We also specialize the proposed local method for networked distributed optimization. To the best of our knowledge, the obtained convergence rates are the sharpest known to date on the convergence of local decant methods with periodic averaging for solving nonconvex federated optimization in both centralized and networked distributed optimization.

47 pages, "Updates from v1: A technical error in Lemma B3 is corrected"

References in corpus (4)

• Agnostic Federated Learning
• One-Shot Federated Learning
• Parallel training of DNNs with Natural Gradient and Parameter Averaging
• Parallel SGD: When does averaging help?

Cited by in corpus (39)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Multi-Armed Bandit Based Client Scheduling for Federated Learning
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning with Buffered Asynchronous Aggregation
• Confederated Learning: Federated Learning with Decentralized Edge Servers
• Personalized Federated Learning using Hypernetworks
• ISFL: Federated Learning for Non-i.i.d. Data with Local Importance Sampling
• FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning
• Federated learning-outcome prediction with multi-layer privacy protection
• Communication-Efficient Robust Federated Learning with Noisy Labels
• Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioning
• Multi-Edge Server-Assisted Dynamic Federated Learning with an Optimized Floating Aggregation Point
• FedJAX: Federated learning simulation with JAX
• Cross-domain Federated Object Detection
• Client Selection and Bandwidth Allocation in Wireless Federated Learning Networks: A Long-Term Perspective
• A Theoretical Perspective on Differentially Private Federated Multi-task Learning
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
• FedCos: A Scene-adaptive Federated Optimization Enhancement for Performance Improvement
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Personalized Federated Learning with Gaussian Processes
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• Federated Learning on Non-IID Data: A Survey
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Bandwidth Allocation for Multiple Federated Learning Services in Wireless Edge Networks
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Convergence Analysis and System Design for Federated Learning over Wireless Networks
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Gradient Masked Federated Optimization
• Towards Heterogeneous Clients with Elastic Federated Learning
• Federated Learning from Small Datasets