# A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

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

- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning](https://mlsanity.com/paper/2111.11556/) (2021)
- [Communication-Efficient Agnostic Federated Averaging](https://mlsanity.com/paper/2104.02748/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [LoCo: Low-Bit Communication Adaptor for Large-scale Model Training](https://mlsanity.com/paper/2407.04480/) (2024)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [A simplified convergence theory for Byzantine resilient stochastic gradient descent](https://mlsanity.com/paper/2208.11879/) (2022)
- [From Risk to Resilience: Towards Assessing and Mitigating the Risk of Data Reconstruction Attacks in Federated Learning](https://mlsanity.com/paper/2512.15460/) (2025)
- [LoSAC: An Efficient Local Stochastic Average Control Method for Federated Optimization](https://mlsanity.com/paper/2112.07839/) (2021)
- [Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2605.25255/) (2026)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)
- [X-VFL: A New Vertical Federated Learning Framework with Cross Completion and Decision Subspace Alignment](https://mlsanity.com/paper/2508.05568/) (2025)
- [Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data](https://mlsanity.com/paper/2603.07654/) (2026)

## Abstract (arXiv)

In this paper, we study the performance of a large family of SGD variants in the smooth nonconvex regime. To this end, we propose a generic and flexible assumption capable of accurate modeling of the second moment of the stochastic gradient. Our assumption is satisfied by a large number of specific variants of SGD in the literature, including SGD with arbitrary sampling, SGD with compressed gradients, and a wide variety of variance-reduced SGD methods such as SVRG and SAGA. We provide a single convergence analysis for all methods that satisfy the proposed unified assumption, thereby offering a unified understanding of SGD variants in the nonconvex regime instead of relying on dedicated analyses of each variant. Moreover, our unified analysis is accurate enough to recover or improve upon the best-known convergence results of several classical methods, and also gives new convergence results for many new methods which arise as special cases. In the more general distributed/federated nonconvex optimization setup, we propose two new general algorithmic frameworks differing in whether direct gradient compression (DC) or compression of gradient differences (DIANA) is used. We show that all methods captured by these two frameworks also satisfy our unified assumption. Thus, our unified convergence analysis also captures a large variety of distributed methods utilizing compressed communication. Finally, we also provide a unified analysis for obtaining faster linear convergence rates in this nonconvex regime under the PL condition.