# Efficient Unbiased Sparsification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 22 Feb 2024.

## Builds on (most cited first, 11 of 11)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2006.11077/) (2020)
- [Randomized Distributed Mean Estimation: Accuracy vs Communication](https://mlsanity.com/paper/1611.07555/) (2016)
- [rTop-k: A Statistical Estimation Approach to Distributed SGD](https://mlsanity.com/paper/2005.10761/) (2020)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)

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

- [On Unbiased Low-Rank Approximation with Minimum Distortion](https://mlsanity.com/paper/2505.09647/) (2025)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)

## Abstract (arXiv)

An unbiased m-sparsification of a vector p∈ ℝn is a random vector Q∈ ℝn with mean p that has at most m<n nonzero coordinates. Unbiased sparsification compresses the original vector without introducing bias; it arises in various contexts, such as in federated learning and sampling sparse probability distributions. Ideally, unbiased sparsification should also minimize the expected value of a divergence function mathsfDiv(Q,p) that measures how far away Q is from the original p. If Q is optimal in this sense, then we call it efficient. Our main results describe efficient unbiased sparsifications for divergences that are either permutation-invariant or additively separable. Surprisingly, the characterization for permutation-invariant divergences is robust to the choice of divergence function, in the sense that our class of optimal Q for squared Euclidean distance coincides with our class of optimal Q for Kullback-Leibler divergence, or indeed any of a wide variety of divergences.