# FetchSGD: Communication-Efficient Federated Learning with Sketching

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

## Key facts

- Cited by 179 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2020.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [FedKD: Communication Efficient Federated Learning via Knowledge Distillation](https://mlsanity.com/paper/2108.13323/) (2021)
- [FedScale: Benchmarking Model and System Performance of Federated Learning at Scale](https://mlsanity.com/paper/2105.11367/) (2021)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [Flora: Low-Rank Adapters Are Secretly Gradient Compressors](https://mlsanity.com/paper/2402.03293/) (2024)
- [Neurotoxin: Durable Backdoors in Federated Learning](https://mlsanity.com/paper/2206.10341/) (2022)
- [NVIDIA FLARE: Federated Learning from Simulation to Real-World](https://mlsanity.com/paper/2210.13291/) (2022)
- [Selective Aggregation for Low-Rank Adaptation in Federated Learning](https://mlsanity.com/paper/2410.01463/) (2024)
- [Personalized Federated Learning via Variational Bayesian Inference](https://mlsanity.com/paper/2206.07977/) (2022)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [Provably Secure Federated Learning against Malicious Clients](https://mlsanity.com/paper/2102.01854/) (2021)
- [Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytes](https://mlsanity.com/paper/2312.06353/) (2023)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Federated Learning via Decentralized Dataset Distillation in Resource-Constrained Edge Environments](https://mlsanity.com/paper/2208.11311/) (2022)
- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [Do Gradient Inversion Attacks Make Federated Learning Unsafe?](https://mlsanity.com/paper/2202.06924/) (2022)
- [DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learning](https://mlsanity.com/paper/2111.00465/) (2021)
- [Communication Efficiency in Federated Learning: Achievements and Challenges](https://mlsanity.com/paper/2107.10996/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Efficient Personalized Federated Learning via Sparse Model-Adaptation](https://mlsanity.com/paper/2305.02776/) (2023)
- [Cross-Gradient Aggregation for Decentralized Learning from Non-IID data](https://mlsanity.com/paper/2103.02051/) (2021)
- [FedCV: A Federated Learning Framework for Diverse Computer Vision Tasks](https://mlsanity.com/paper/2111.11066/) (2021)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation](https://mlsanity.com/paper/2103.11109/) (2021)
- [FedHM: Efficient Federated Learning for Heterogeneous Models via Low-rank Factorization](https://mlsanity.com/paper/2111.14655/) (2021)
- [A Multi-agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learning](https://mlsanity.com/paper/2201.02932/) (2022)
- [Fine-tuning Language Models over Slow Networks using Activation Compression with Guarantees](https://mlsanity.com/paper/2206.01299/) (2022)
- [Acceleration of Federated Learning with Alleviated Forgetting in Local Training](https://mlsanity.com/paper/2203.02645/) (2022)
- [FedSpace: An Efficient Federated Learning Framework at Satellites and Ground Stations](https://mlsanity.com/paper/2202.01267/) (2022)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)

## Abstract (arXiv)

Existing approaches to federated learning suffer from a communication bottleneck as well as convergence issues due to sparse client participation. In this paper we introduce a novel algorithm, called FetchSGD, to overcome these challenges. FetchSGD compresses model updates using a Count Sketch, and then takes advantage of the mergeability of sketches to combine model updates from many workers. A key insight in the design of FetchSGD is that, because the Count Sketch is linear, momentum and error accumulation can both be carried out within the sketch. This allows the algorithm to move momentum and error accumulation from clients to the central aggregator, overcoming the challenges of sparse client participation while still achieving high compression rates and good convergence. We prove that FetchSGD has favorable convergence guarantees, and we demonstrate its empirical effectiveness by training two residual networks and a transformer model.