# rTop-k: A Statistical Estimation Approach to Distributed SGD

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2020.

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

- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [Time-Correlated Sparsification for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2101.08837/) (2021)
- [An Information-Theoretic Justification for Model Pruning](https://mlsanity.com/paper/2102.08329/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Neural Network Compression for Noisy Storage Devices](https://mlsanity.com/paper/2102.07725/) (2021)
- [Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning](https://mlsanity.com/paper/2202.02423/) (2022)
- [Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation](https://mlsanity.com/paper/2110.07751/) (2021)
- [Wireless Federated Learning with Limited Communication and Differential Privacy](https://mlsanity.com/paper/2106.00564/) (2021)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [Collaborative Learning over Wireless Networks: An Introductory Overview](https://mlsanity.com/paper/2112.05559/) (2021)
- [ResFed: Communication Efficient Federated Learning by Transmitting Deep Compressed Residuals](https://mlsanity.com/paper/2212.05602/) (2022)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [Over-the-Air Statistical Estimation](https://mlsanity.com/paper/2103.04014/) (2021)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning](https://mlsanity.com/paper/2102.03112/) (2021)
- [Efficient Unbiased Sparsification](https://mlsanity.com/paper/2402.14925/) (2024)
- [SSFL: Discovering Sparse Unified Subnetworks at Initialization for Efficient Federated Learning](https://mlsanity.com/paper/2405.09037/) (2024)
- [rAge-k: Communication-Efficient Federated Learning Using Age Factor](https://mlsanity.com/paper/2410.22192/) (2024)
- [Age-Aware Edge-Blind Federated Learning via Over-the-Air Aggregation](https://mlsanity.com/paper/2602.02469/) (2026)
- [Private Federated Submodel Learning with Sparsification](https://mlsanity.com/paper/2205.15992/) (2022)
- [Trading-off Accuracy and Communication Cost in Federated Learning](https://mlsanity.com/paper/2503.14246/) (2025)
- [Timely Parameter Updating in Over-the-Air Federated Learning](https://mlsanity.com/paper/2512.19103/) (2025)

## Abstract (arXiv)

The large communication cost for exchanging gradients between different nodes significantly limits the scalability of distributed training for large-scale learning models. Motivated by this observation, there has been significant recent interest in techniques that reduce the communication cost of distributed Stochastic Gradient Descent (SGD), with gradient sparsification techniques such as top-k and random-k shown to be particularly effective. The same observation has also motivated a separate line of work in distributed statistical estimation theory focusing on the impact of communication constraints on the estimation efficiency of different statistical models. The primary goal of this paper is to connect these two research lines and demonstrate how statistical estimation models and their analysis can lead to new insights in the design of communication-efficient training techniques. We propose a simple statistical estimation model for the stochastic gradients which captures the sparsity and skewness of their distribution. The statistically optimal communication scheme arising from the analysis of this model leads to a new sparsification technique for SGD, which concatenates random-k and top-k, considered separately in the prior literature. We show through extensive experiments on both image and language domains with CIFAR-10, ImageNet, and Penn Treebank datasets that the concatenated application of these two sparsification methods consistently and significantly outperforms either method applied alone.