# On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization

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

## Key facts

- Cited by 92 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2017.

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

- [Personalized Federated Learning using Hypernetworks](https://mlsanity.com/paper/2103.04628/) (2021)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Improving LoRA in Privacy-preserving Federated Learning](https://mlsanity.com/paper/2403.12313/) (2024)
- [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)
- [AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networks](https://mlsanity.com/paper/2403.13101/) (2024)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [A Bayesian Federated Learning Framework with Online Laplace Approximation](https://mlsanity.com/paper/2102.01936/) (2021)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Hierarchical Split Federated Learning: Convergence Analysis and System Optimization](https://mlsanity.com/paper/2412.07197/) (2024)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Efficient Device Scheduling with Multi-Job Federated Learning](https://mlsanity.com/paper/2112.05928/) (2021)
- [Toward Communication Efficient Adaptive Gradient Method](https://mlsanity.com/paper/2109.05109/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Trade-offs of Local SGD at Scale: An Empirical Study](https://mlsanity.com/paper/2110.08133/) (2021)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [Multi-Job Intelligent Scheduling with Cross-Device Federated Learning](https://mlsanity.com/paper/2211.13430/) (2022)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Fast Federated Learning by Balancing Communication Trade-Offs](https://mlsanity.com/paper/2105.11028/) (2021)
- [On Bridging Generic and Personalized Federated Learning for Image Classification](https://mlsanity.com/paper/2107.00778/) (2021)
- [HASFL: Heterogeneity-aware Split Federated Learning over Edge Computing Systems](https://mlsanity.com/paper/2506.08426/) (2025)
- [Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients](https://mlsanity.com/paper/2102.06329/) (2021)
- [Recent Methodological Advances in Federated Learning for Healthcare](https://mlsanity.com/paper/2310.02874/) (2023)
- [Wirelessly Powered Federated Edge Learning: Optimal Tradeoffs Between Convergence and Power Transfer](https://mlsanity.com/paper/2102.12357/) (2021)
- [Large-Scale Deep Learning Optimizations: A Comprehensive Survey](https://mlsanity.com/paper/2111.00856/) (2021)

## Abstract (arXiv)

Despite their popularity, the practical performance of asynchronous stochastic gradient descent methods (ASGD) for solving large scale machine learning problems are not as good as theoretical results indicate. We adopt and analyze a synchronous K-step averaging stochastic gradient descent algorithm which we call K-AVG. We establish the convergence results of K-AVG for nonconvex objectives and explain why the K-step delay is necessary and leads to better performance than traditional parallel stochastic gradient descent which is a special case of K-AVG with K=1. We also show that K-AVG scales better than ASGD. Another advantage of K-AVG over ASGD is that it allows larger stepsizes. On a cluster of 128 GPUs, K-AVG is faster than ASGD implementations and achieves better accuracies and faster convergence for cifar dataset.