# Federated Accelerated Stochastic Gradient Descent

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

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

- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [FedPara: Low-Rank Hadamard Product for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.06098/) (2021)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [FedCM: Federated Learning with Client-level Momentum](https://mlsanity.com/paper/2106.10874/) (2021)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning](https://mlsanity.com/paper/2103.05032/) (2021)
- [Federated Learning via Decentralized Dataset Distillation in Resource-Constrained Edge Environments](https://mlsanity.com/paper/2208.11311/) (2022)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Acceleration of Federated Learning with Alleviated Forgetting in Local Training](https://mlsanity.com/paper/2203.02645/) (2022)
- [Understanding Generalization of Federated Learning via Stability: Heterogeneity Matters](https://mlsanity.com/paper/2306.03824/) (2023)
- [Differentially Private Label Protection in Split Learning](https://mlsanity.com/paper/2203.02073/) (2022)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Federated Learning for Face Recognition with Gradient Correction](https://mlsanity.com/paper/2112.07246/) (2021)
- [Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning](https://mlsanity.com/paper/2107.10663/) (2021)
- [The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning](https://mlsanity.com/paper/2111.05326/) (2021)
- [Gradient Masked Averaging for Federated Learning](https://mlsanity.com/paper/2201.11986/) (2022)
- [GIFAIR-FL: A Framework for Group and Individual Fairness in Federated Learning](https://mlsanity.com/paper/2108.02741/) (2021)
- [Efficient Algorithms for Federated Saddle Point Optimization](https://mlsanity.com/paper/2102.06333/) (2021)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Vertical Federated Learning without Revealing Intersection Membership](https://mlsanity.com/paper/2106.05508/) (2021)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning](https://mlsanity.com/paper/2308.09883/) (2023)
- [On Bridging Generic and Personalized Federated Learning for Image Classification](https://mlsanity.com/paper/2107.00778/) (2021)
- [RoBoSS: A Robust, Bounded, Sparse, and Smooth Loss Function for Supervised Learning](https://mlsanity.com/paper/2309.02250/) (2023)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)

## Abstract (arXiv)

We propose Federated Accelerated Stochastic Gradient Descent (FedAc), a principled acceleration of Federated Averaging (FedAvg, also known as Local SGD) for distributed optimization. FedAc is the first provable acceleration of FedAvg that improves convergence speed and communication efficiency on various types of convex functions. For example, for strongly convex and smooth functions, when using M workers, the previous state-of-the-art FedAvg analysis can achieve a linear speedup in M if given M rounds of synchronization, whereas FedAc only requires M^frac13 rounds. Moreover, we prove stronger guarantees for FedAc when the objectives are third-order smooth. Our technique is based on a potential-based perturbed iterate analysis, a novel stability analysis of generalized accelerated SGD, and a strategic tradeoff between acceleration and stability.