# On the Convergence of Local Descent Methods in Federated Learning

arXiv: https://arxiv.org/abs/1910.14425 · HTML: https://mlsanity.com/paper/1910.14425/

## Key facts

- Cited by 153 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2019.

## Built on by (most cited first, 30 of 153)

- [Federated Learning on Non-IID Data: A Survey](https://mlsanity.com/paper/2106.06843/) (2021)
- [Personalized Federated Learning using Hypernetworks](https://mlsanity.com/paper/2103.04628/) (2021)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Multi-Center Federated Learning: Clients Clustering for Better Personalization](https://mlsanity.com/paper/2108.08647/) (2021)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Personalized Federated Learning with Gaussian Processes](https://mlsanity.com/paper/2106.15482/) (2021)
- [On the Importance and Applicability of Pre-Training for Federated Learning](https://mlsanity.com/paper/2206.11488/) (2022)
- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregations](https://mlsanity.com/paper/2103.10481/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [No Free Lunch Theorem for Security and Utility in Federated Learning](https://mlsanity.com/paper/2203.05816/) (2022)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Efficient Distribution Similarity Identification in Clustered Federated Learning via Principal Angles Between Client Data Subspaces](https://mlsanity.com/paper/2209.10526/) (2022)
- [Game of Gradients: Mitigating Irrelevant Clients in Federated Learning](https://mlsanity.com/paper/2110.12257/) (2021)
- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [FedJAX: Federated learning simulation with JAX](https://mlsanity.com/paper/2108.02117/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Convergence Analysis and System Design for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2105.00872/) (2021)
- [FedADMM: A Robust Federated Deep Learning Framework with Adaptivity to System Heterogeneity](https://mlsanity.com/paper/2204.03529/) (2022)
- [Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer](https://mlsanity.com/paper/2109.08119/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)

## Abstract (arXiv)

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.