# Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 37 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 30 of 30)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [The Future of Digital Health with Federated Learning](https://mlsanity.com/paper/2003.08119/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning](https://mlsanity.com/paper/2008.03606/) (2020)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Federated Learning for Keyword Spotting](https://mlsanity.com/paper/1810.05512/) (2018)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Faster Non-Convex Federated Learning via Global and Local Momentum](https://mlsanity.com/paper/2012.04061/) (2020)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity](https://mlsanity.com/paper/1912.06036/) (2019)

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

- [Personalized Federated Learning with Feature Alignment and Classifier Collaboration](https://mlsanity.com/paper/2306.11867/) (2023)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [FedCor: Correlation-Based Active Client Selection Strategy for Heterogeneous Federated Learning](https://mlsanity.com/paper/2103.13822/) (2021)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [SAFARI: Sparsity enabled Federated Learning with Limited and Unreliable Communications](https://mlsanity.com/paper/2204.02321/) (2022)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration](https://mlsanity.com/paper/2509.10439/) (2025)
- [From Deterioration to Acceleration: A Calibration Approach to Rehabilitating Step Asynchronism in Federated Optimization](https://mlsanity.com/paper/2112.09355/) (2021)
- [FedBCD:Communication-Efficient Accelerated Block Coordinate Gradient Descent for Federated Learning](https://mlsanity.com/paper/2603.05116/) (2026)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation](https://mlsanity.com/paper/2405.02745/) (2024)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning](https://mlsanity.com/paper/2202.06083/) (2022)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [On the Convergence of Momentum-Based Algorithms for Federated Bilevel Optimization Problems](https://mlsanity.com/paper/2204.13299/) (2022)
- [Federated Learning with Only Positive Labels by Exploring Label Correlations](https://mlsanity.com/paper/2404.15598/) (2024)
- [Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization](https://mlsanity.com/paper/2506.05791/) (2025)
- [Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning](https://mlsanity.com/paper/2209.00361/) (2022)
- [Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimation](https://mlsanity.com/paper/2306.01648/) (2023)
- [Joint Power Control and Data Size Selection for Over-the-Air Computation Aided Federated Learning](https://mlsanity.com/paper/2308.09072/) (2023)
- [Personalized Federated Learning with Contextual Modulation and Meta-Learning](https://mlsanity.com/paper/2312.15191/) (2023)
- [Sharpness-aware Federated Graph Learning](https://mlsanity.com/paper/2512.16247/) (2025)
- [Personalized Federated Learning via Gaussian Generative Modeling](https://mlsanity.com/paper/2603.11620/) (2026)
- [What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity](https://mlsanity.com/paper/2607.14731/) (2026)

## Abstract (arXiv)

Recently, local SGD has got much attention and been extensively studied in the distributed learning community to overcome the communication bottleneck problem. However, the superiority of local SGD to minibatch SGD only holds in quite limited situations. In this paper, we study a new local algorithm called Bias-Variance Reduced Local SGD (BVR-L-SGD) for nonconvex distributed optimization. Algorithmically, our proposed bias and variance reduced local gradient estimator fully utilizes small second-order heterogeneity of local objectives and suggests randomly picking up one of the local models instead of taking the average of them when workers are synchronized. Theoretically, under small heterogeneity of local objectives, we show that BVR-L-SGD achieves better communication complexity than both the previous non-local and local methods under mild conditions, and particularly BVR-L-SGD is the first method that breaks the barrier of communication complexity Theta(1/varepsilon) for general nonconvex smooth objectives when the heterogeneity is small and the local computation budget is large. Numerical results are given to verify the theoretical findings and give empirical evidence of the superiority of our method.