Efficient Unbiased Sparsification
<|reference_start|>Efficient Unbiased Sparsification: An unbiased $m$-sparsification of a vector $p\in \mathbb{R}^n$ is a random vector $Q\in \mathbb{R}^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 $\mathsf{Div}(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.<|reference_end|>
@article{barnes2024efficient,
    title={Efficient Unbiased Sparsification},
    author={Leighton Barnes, Stephen Cameron, Timothy Chow, Emma Cohen, Keith
  Frankston, Benjamin Howard, Fred Kochman, Daniel Scheinerman, Jeffrey
  VanderKam},
    journal={arXiv preprint arXiv:2402.14925},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.14925},
    primaryClass={cs.IT cs.LG math.IT math.ST stat.TH}
}