# Variance Reduced Local SGD with Lower Communication Complexity

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

## Key facts

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

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

- [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)
- [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)
- [FedCM: Federated Learning with Client-level Momentum](https://mlsanity.com/paper/2106.10874/) (2021)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy](https://mlsanity.com/paper/2302.10429/) (2023)
- [Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape](https://mlsanity.com/paper/2305.11584/) (2023)
- [FedCor: Correlation-Based Active Client Selection Strategy for Heterogeneous Federated Learning](https://mlsanity.com/paper/2103.13822/) (2021)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Closing the Generalization Gap of Cross-silo Federated Medical Image Segmentation](https://mlsanity.com/paper/2203.10144/) (2022)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [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)
- [Local Adaptivity in Federated Learning: Convergence and Consistency](https://mlsanity.com/paper/2106.02305/) (2021)
- [FedFM: Anchor-based Feature Matching for Data Heterogeneity in Federated Learning](https://mlsanity.com/paper/2210.07615/) (2022)
- [Cost-Effective Federated Learning in Mobile Edge Networks](https://mlsanity.com/paper/2109.05411/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [Efficient Algorithms for Federated Saddle Point Optimization](https://mlsanity.com/paper/2102.06333/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [On Bridging Generic and Personalized Federated Learning for Image Classification](https://mlsanity.com/paper/2107.00778/) (2021)
- [Tighter Regret Analysis and Optimization of Online Federated Learning](https://mlsanity.com/paper/2205.06491/) (2022)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [FL Games: A Federated Learning Framework for Distribution Shifts](https://mlsanity.com/paper/2211.00184/) (2022)
- [Benchmarking Algorithms for Federated Domain Generalization](https://mlsanity.com/paper/2307.04942/) (2023)
- [Compositional federated learning: Applications in distributionally robust averaging and meta learning](https://mlsanity.com/paper/2106.11264/) (2021)
- [NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2208.08490/) (2022)

## Abstract (arXiv)

To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires O(T^frac34 N^frac34) communications to maintain its linear iteration speedup property, where T is the total number of iterations and N is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a linear iteration speedup with a lower communication complexity O(T^frac12 N^frac32) even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.