# FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 42 references that are in the map.
- First posted on arXiv 10 Aug 2021.

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

- [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)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [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)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [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)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Variance Reduced Local SGD with Lower Communication Complexity](https://mlsanity.com/paper/1912.12844/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [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)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization](https://mlsanity.com/paper/2006.07013/) (2020)
- [FireCaffe: near-linear acceleration of deep neural network training on compute clusters](https://mlsanity.com/paper/1511.00175/) (2015)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)

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

- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [A Survey on Approximate Edge AI for Energy Efficient Autonomous Driving Services](https://mlsanity.com/paper/2304.14271/) (2023)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Deep Leakage from Model in Federated Learning](https://mlsanity.com/paper/2206.04887/) (2022)
- [On the effectiveness of partial variance reduction in federated learning with heterogeneous data](https://mlsanity.com/paper/2212.02191/) (2022)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [Federated Learning on Adaptively Weighted Nodes by Bilevel Optimization](https://mlsanity.com/paper/2207.10751/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Federated Learning Aggregation: New Robust Algorithms with Guarantees](https://mlsanity.com/paper/2205.10864/) (2022)
- [Personalized Federated Learning with Multiple Known Clusters](https://mlsanity.com/paper/2204.13619/) (2022)
- [FedSat: A Statistical Aggregation Approach for Class Imbalanced Clients in Federated Learning](https://mlsanity.com/paper/2407.03862/) (2024)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [FedControl: When Control Theory Meets Federated Learning](https://mlsanity.com/paper/2205.14236/) (2022)
- [Tackling Computational Heterogeneity in FL: A Few Theoretical Insights](https://mlsanity.com/paper/2307.06283/) (2023)
- [Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2511.05593/) (2025)
- [SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums](https://mlsanity.com/paper/2606.15832/) (2026)

## Abstract (arXiv)

Federated Averaging (FedAvg, also known as Local-SGD) (McMahan et al., 2017) is a classical federated learning algorithm in which clients run multiple local SGD steps before communicating their update to an orchestrating server. We propose a new federated learning algorithm, FedPAGE, able to further reduce the communication complexity by utilizing the recent optimal PAGE method (Li et al., 2021) instead of plain SGD in FedAvg. We show that FedPAGE uses much fewer communication rounds than previous local methods for both federated convex and nonconvex optimization. Concretely, 1) in the convex setting, the number of communication rounds of FedPAGE is O(fracN3/4Sε), improving the best-known result O(fracNSε) of SCAFFOLD (Karimireddy et al.,2020) by a factor of N1/4, where N is the total number of clients (usually is very large in federated learning), S is the sampled subset of clients in each communication round, and ε is the target error; 2) in the nonconvex setting, the number of communication rounds of FedPAGE is O(frac√N+SSε2), improving the best-known result O(fracN2/3S2/3ε2) of SCAFFOLD (Karimireddy et al.,2020) by a factor of N1/6S1/3, if the sampled clients S≤ √N. Note that in both settings, the communication cost for each round is the same for both FedPAGE and SCAFFOLD. As a result, FedPAGE achieves new state-of-the-art results in terms of communication complexity for both federated convex and nonconvex optimization.