# First Analysis of Local GD on Heterogeneous Data

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

## Key facts

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

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

- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy](https://mlsanity.com/paper/2302.10429/) (2023)
- [Anarchic Federated Learning](https://mlsanity.com/paper/2108.09875/) (2021)
- [FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation](https://mlsanity.com/paper/2203.15104/) (2022)
- [Multi-Level Branched Regularization for Federated Learning](https://mlsanity.com/paper/2207.06936/) (2022)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Cost-Effective Federated Learning in Mobile Edge Networks](https://mlsanity.com/paper/2109.05411/) (2021)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Communication-Efficient Federated Learning with Accelerated Client Gradient](https://mlsanity.com/paper/2201.03172/) (2022)
- [Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup](https://mlsanity.com/paper/2308.00522/) (2023)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [D2NO: Efficient Handling of Heterogeneous Input Function Spaces with Distributed Deep Neural Operators](https://mlsanity.com/paper/2310.18888/) (2023)
- [Differential Privacy Meets Federated Learning under Communication Constraints](https://mlsanity.com/paper/2101.12240/) (2021)

## Abstract (arXiv)

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.