# Sparsified SGD with Memory

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

## Key facts

- Cited by 376 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2018.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [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)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [Pufferfish: Communication-efficient Models At No Extra Cost](https://mlsanity.com/paper/2103.03936/) (2021)
- [FedLab: A Flexible Federated Learning Framework](https://mlsanity.com/paper/2107.11621/) (2021)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [Communication-Efficient Adaptive Federated Learning](https://mlsanity.com/paper/2205.02719/) (2022)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)
- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [Federated Learning via Inexact ADMM](https://mlsanity.com/paper/2204.10607/) (2022)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Gradient Obfuscation Gives a False Sense of Security in Federated Learning](https://mlsanity.com/paper/2206.04055/) (2022)
- [LDAdam: Adaptive Optimization from Low-Dimensional Gradient Statistics](https://mlsanity.com/paper/2410.16103/) (2024)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Layer-wise Adaptive Model Aggregation for Scalable Federated Learning](https://mlsanity.com/paper/2110.10302/) (2021)
- [Compressed-VFL: Communication-Efficient Learning with Vertically Partitioned Data](https://mlsanity.com/paper/2206.08330/) (2022)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)

## Abstract (arXiv)

Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsification techniques to reduce the amount of data that needs to be communicated, for instance by only sending the most significant entries of the stochastic gradient (top-k sparsification). Whilst such schemes showed very promising performance in practice, they have eluded theoretical analysis so far. In this work we analyze Stochastic Gradient Descent (SGD) with k-sparsification or compression (for instance top-k or random-k) and show that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory). That is, communication can be reduced by a factor of the dimension of the problem (sometimes even more) whilst still converging at the same rate. We present numerical experiments to illustrate the theoretical findings and the better scalability for distributed applications.