Efficient Unbiased Sparsification
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866907990276177920 |
|---|---|
| author | Barnes, Leighton Cameron, Stephen Chow, Timothy Cohen, Emma Frankston, Keith Howard, Benjamin Kochman, Fred Scheinerman, Daniel VanderKam, Jeffrey |
| author_facet | Barnes, Leighton Cameron, Stephen Chow, Timothy Cohen, Emma Frankston, Keith Howard, Benjamin Kochman, Fred Scheinerman, Daniel VanderKam, Jeffrey |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14925 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Unbiased Sparsification Barnes, Leighton Cameron, Stephen Chow, Timothy Cohen, Emma Frankston, Keith Howard, Benjamin Kochman, Fred Scheinerman, Daniel VanderKam, Jeffrey Information Theory Machine Learning Statistics Theory 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. |
| title | Efficient Unbiased Sparsification |
| topic | Information Theory Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2402.14925 |