# Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

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

## Key facts

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

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

- [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)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning](https://mlsanity.com/paper/2105.05883/) (2021)
- [Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.04487/) (2021)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Layer-wise Adaptive Model Aggregation for Scalable Federated Learning](https://mlsanity.com/paper/2110.10302/) (2021)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (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)
- [FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergence](https://mlsanity.com/paper/2204.08125/) (2022)
- [Towards Federated Foundation Models: Scalable Dataset Pipelines for Group-Structured Learning](https://mlsanity.com/paper/2307.09619/) (2023)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity](https://mlsanity.com/paper/2102.04635/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs](https://mlsanity.com/paper/2309.01172/) (2023)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Towards Communication-efficient Vertical Federated Learning Training via Cache-enabled Local Updates](https://mlsanity.com/paper/2207.14628/) (2022)
- [Citadel: Protecting Data Privacy and Model Confidentiality for Collaborative Learning with SGX](https://mlsanity.com/paper/2105.01281/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Communication-Efficient Federated Learning for Heterogeneous Edge Devices Based on Adaptive Gradient Quantization](https://mlsanity.com/paper/2212.08272/) (2022)

## Abstract (arXiv)

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. We strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Lojasiewicz condition, O((pT)1/3) rounds of communication suffice to achieve a linear speed up, that is, an error of O(1/pT), where T is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPU cluster.