# Understanding Top-k Sparsification in Distributed Deep Learning

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2019.

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

- [What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions](https://mlsanity.com/paper/2405.13954/) (2024)
- [FedLab: A Flexible Federated Learning Framework](https://mlsanity.com/paper/2107.11621/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems](https://mlsanity.com/paper/2101.10761/) (2021)
- [Time-Correlated Sparsification for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2101.08837/) (2021)
- [On the Utility of Gradient Compression in Distributed Training Systems](https://mlsanity.com/paper/2103.00543/) (2021)
- [Near-Optimal Sparse Allreduce for Distributed Deep Learning](https://mlsanity.com/paper/2201.07598/) (2022)
- [ScaleCom: Scalable Sparsified Gradient Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2104.11125/) (2021)
- [Backdoored Retrievers for Prompt Injection Attacks on Retrieval Augmented Generation of Large Language Models](https://mlsanity.com/paper/2410.14479/) (2024)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projections](https://mlsanity.com/paper/2405.17991/) (2024)
- [MuLoCo: Muon is a practical inner optimizer for DiLoCo](https://mlsanity.com/paper/2505.23725/) (2025)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [Smart-Infinity: Fast Large Language Model Training using Near-Storage Processing on a Real System](https://mlsanity.com/paper/2403.06664/) (2024)
- [Neural Distributed Source Coding](https://mlsanity.com/paper/2106.02797/) (2021)
- [Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization](https://mlsanity.com/paper/2405.15861/) (2024)
- [Overcoming the Communication-Performance Tradeoff in LLM Pretraining](https://mlsanity.com/paper/2508.15706/) (2025)
- [GraVAC: Adaptive Compression for Communication-Efficient Distributed DL Training](https://mlsanity.com/paper/2305.12201/) (2023)
- [Distributed LLMs and Multimodal Large Language Models: A Survey on Advances, Challenges, and Future Directions](https://mlsanity.com/paper/2503.16585/) (2025)
- [Evaluation and Optimization of Gradient Compression for Distributed Deep Learning](https://mlsanity.com/paper/2306.08881/) (2023)
- [Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression](https://mlsanity.com/paper/2407.01378/) (2024)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Spark Transformer: Reactivating Sparsity in FFN and Attention](https://mlsanity.com/paper/2506.06644/) (2025)
- [DNN gradient lossless compression: Can GenNorm be the answer?](https://mlsanity.com/paper/2111.07599/) (2021)
- [Sparse-SignSGD with Majority Vote for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2302.07475/) (2023)
- [A Carbon Tracking Model for Federated Learning: Impact of Quantization and Sparsification](https://mlsanity.com/paper/2310.08087/) (2023)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Incentivizing Permissionless Distributed Learning of LLMs](https://mlsanity.com/paper/2505.21684/) (2025)
- [Model Parallelism With Subnetwork Data Parallelism](https://mlsanity.com/paper/2507.09029/) (2025)

## Abstract (arXiv)

Distributed stochastic gradient descent (SGD) algorithms are widely deployed in training large-scale deep learning models, while the communication overhead among workers becomes the new system bottleneck. Recently proposed gradient sparsification techniques, especially Top-k sparsification with error compensation (TopK-SGD), can significantly reduce the communication traffic without an obvious impact on the model accuracy. Some theoretical studies have been carried out to analyze the convergence property of TopK-SGD. However, existing studies do not dive into the details of Top-k operator in gradient sparsification and use relaxed bounds (e.g., exact bound of Random-k) for analysis; hence the derived results cannot well describe the real convergence performance of TopK-SGD. To this end, we first study the gradient distributions of TopK-SGD during the training process through extensive experiments. We then theoretically derive a tighter bound for the Top-k operator. Finally, we exploit the property of gradient distribution to propose an approximate top-k selection algorithm, which is computing-efficient for GPUs, to improve the scaling efficiency of TopK-SGD by significantly reducing the computing overhead. Codes are available at: urlhttps://github.com/hclhkbu/GaussianK-SGD.