# Distributed Stochastic Optimization under a General Variance Condition

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 61 references that are in the map.
- First posted on arXiv 30 Jan 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions](https://mlsanity.com/paper/1902.00908/) (2019)
- [A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2110.09993/) (2021)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019)
- [Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization](https://mlsanity.com/paper/2201.11066/) (2022)

## Built on by (most cited first, 4 of 4)

- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Unity is Power: Semi-Asynchronous Collaborative Training of Large-Scale Models with Structured Pruning in Resource-Limited Clients](https://mlsanity.com/paper/2410.08457/) (2024)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Achieving Linear Speedup for Composite Federated Learning](https://mlsanity.com/paper/2602.03357/) (2026)

## Abstract (arXiv)

Distributed stochastic optimization has drawn great attention recently due to its effectiveness in solving large-scale machine learning problems. Though numerous algorithms have been proposed and successfully applied to general practical problems, their theoretical guarantees mainly rely on certain boundedness conditions on the stochastic gradients, varying from uniform boundedness to the relaxed growth condition. In addition, how to characterize the data heterogeneity among the agents and its impacts on the algorithmic performance remains challenging. In light of such motivations, we revisit the classical Federated Averaging (FedAvg) algorithm (McMahan et al., 2017) as well as the more recent SCAFFOLD method (Karimireddy et al., 2020) for solving the distributed stochastic optimization problem and establish the convergence results under only a mild variance condition on the stochastic gradients for smooth nonconvex objective functions. Almost sure convergence to a stationary point is also established under the condition. Moreover, we discuss a more informative measurement for data heterogeneity as well as its implications.