# Communication-efficient distributed SGD with Sketching

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2019.

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

- [Neurotoxin: Durable Backdoors in Federated Learning](https://mlsanity.com/paper/2206.10341/) (2022)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Fine-tuning Language Models over Slow Networks using Activation Compression with Guarantees](https://mlsanity.com/paper/2206.01299/) (2022)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [On the Utility of Gradient Compression in Distributed Training Systems](https://mlsanity.com/paper/2103.00543/) (2021)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction](https://mlsanity.com/paper/2310.08670/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [ScaleCom: Scalable Sparsified Gradient Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2104.11125/) (2021)
- [Egeria: Efficient DNN Training with Knowledge-Guided Layer Freezing](https://mlsanity.com/paper/2201.06227/) (2022)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [On Distributed Adaptive Optimization with Gradient Compression](https://mlsanity.com/paper/2205.05632/) (2022)
- [PFA: Privacy-preserving Federated Adaptation for Effective Model Personalization](https://mlsanity.com/paper/2103.01548/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [Self-Aware Personalized Federated Learning](https://mlsanity.com/paper/2204.08069/) (2022)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [BAGUA: Scaling up Distributed Learning with System Relaxations](https://mlsanity.com/paper/2107.01499/) (2021)
- [Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization](https://mlsanity.com/paper/2111.00705/) (2021)
- [Federated Learning over Wireless Networks: A Band-limited Coordinated Descent Approach](https://mlsanity.com/paper/2102.07972/) (2021)
- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)
- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [Towards Efficient Synchronous Federated Training: A Survey on System Optimization Strategies](https://mlsanity.com/paper/2109.03999/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [FRL: Federated Rank Learning](https://mlsanity.com/paper/2110.04350/) (2021)

## Abstract (arXiv)

Large-scale distributed training of neural networks is often limited by network bandwidth, wherein the communication time overwhelms the local computation time. Motivated by the success of sketching methods in sub-linear/streaming algorithms, we introduce Sketched SGD, an algorithm for carrying out distributed SGD by communicating sketches instead of full gradients. We show that Sketched SGD has favorable convergence rates on several classes of functions. When considering all communication -- both of gradients and of updated model weights -- Sketched SGD reduces the amount of communication required compared to other gradient compression methods from O(d) or O(W) to O(log d), where d is the number of model parameters and W is the number of workers participating in training. We run experiments on a transformer model, an LSTM, and a residual network, demonstrating up to a 40x reduction in total communication cost with no loss in final model performance. We also show experimentally that Sketched SGD scales to at least 256 workers without increasing communication cost or degrading model performance.