# Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning

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

## Key facts

- Cited by 278 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2018.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [Federated Graph Classification over Non-IID Graphs](https://mlsanity.com/paper/2106.13423/) (2021)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning](https://mlsanity.com/paper/2105.05883/) (2021)
- [Selective Aggregation for Low-Rank Adaptation in Federated Learning](https://mlsanity.com/paper/2410.01463/) (2024)
- [Tackling Data Heterogeneity in Federated Learning with Class Prototypes](https://mlsanity.com/paper/2212.02758/) (2022)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [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)
- [Decentralized Federated Learning: Balancing Communication and Computing Costs](https://mlsanity.com/paper/2107.12048/) (2021)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Improving the Model Consistency of Decentralized Federated Learning](https://mlsanity.com/paper/2302.04083/) (2023)
- [Federated Learning via Inexact ADMM](https://mlsanity.com/paper/2204.10607/) (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)
- [Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning](https://mlsanity.com/paper/2106.03328/) (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)
- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Quantized Federated Learning under Transmission Delay and Outage Constraints](https://mlsanity.com/paper/2106.09397/) (2021)
- [Faster Adaptive Federated Learning](https://mlsanity.com/paper/2212.00974/) (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)
- [FedHM: Efficient Federated Learning for Heterogeneous Models via Low-rank Factorization](https://mlsanity.com/paper/2111.14655/) (2021)
- [SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks](https://mlsanity.com/paper/2106.02743/) (2021)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)

## Abstract (arXiv)

In distributed training of deep neural networks, parallel mini-batch SGD is widely used to speed up the training process by using multiple workers. It uses multiple workers to sample local stochastic gradient in parallel, aggregates all gradients in a single server to obtain the average, and update each worker's local model using a SGD update with the averaged gradient. Ideally, parallel mini-batch SGD can achieve a linear speed-up of the training time (with respect to the number of workers) compared with SGD over a single worker. However, such linear scalability in practice is significantly limited by the growing demand for gradient communication as more workers are involved. Model averaging, which periodically averages individual models trained over parallel workers, is another common practice used for distributed training of deep neural networks since (Zinkevich et al. 2010) (McDonald, Hall, and Mann 2010). Compared with parallel mini-batch SGD, the communication overhead of model averaging is significantly reduced. Impressively, tremendous experimental works have verified that model averaging can still achieve a good speed-up of the training time as long as the averaging interval is carefully controlled. However, it remains a mystery in theory why such a simple heuristic works so well. This paper provides a thorough and rigorous theoretical study on why model averaging can work as well as parallel mini-batch SGD with significantly less communication overhead.