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 (19)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Multi-Armed Bandit Based Client Scheduling for Federated Learning
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Personalized Federated Learning using Hypernetworks
• FedJAX: Federated learning simulation with JAX
• Client Selection and Bandwidth Allocation in Wireless Federated Learning Networks: A Long-Term Perspective
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer
• A Theoretical Perspective on Differentially Private Federated Multi-task Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Personalized Federated Learning with Gaussian Processes
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Federated Learning on Non-IID Data: A Survey
• Bandwidth Allocation for Multiple Federated Learning Services in Wireless Edge Networks
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Towards Heterogeneous Clients with Elastic Federated Learning
• Gradient Masked Federated Optimization