# Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 16 Jun 2021.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints](https://mlsanity.com/paper/2011.00083/) (2020)

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

- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints](https://mlsanity.com/paper/2206.00707/) (2022)
- [Training generative models from privatized data](https://mlsanity.com/paper/2306.09547/) (2023)
- [SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant](https://mlsanity.com/paper/2608.05127/) (2026)

## Abstract (arXiv)

We consider the problem of estimating a d-dimensional s-sparse discrete distribution from its samples observed under a b-bit communication constraint. The best-known previous result on ℓ2 estimation error for this problem is Oleft( fracslogleft( d/sright)n2bright). Surprisingly, we show that when sample size n exceeds a minimum threshold n^*(s, d, b), we can achieve an ℓ2 estimation error of Oleft( fracsn2bright). This implies that when n>n^*(s, d, b) the convergence rate does not depend on the ambient dimension d and is the same as knowing the support of the distribution beforehand. We next ask the question: ``what is the minimum n^*(s, d, b) that allows dimension-free convergence?''. To upper bound n^*(s, d, b), we develop novel localization schemes to accurately and efficiently localize the unknown support. For the non-interactive setting, we show that n^*(s, d, b) = Oleft( min left( d2log2 d/2b, s4log2 d/2bright) right). Moreover, we connect the problem with non-adaptive group testing and obtain a polynomial-time estimation scheme when n = tildeOmegaleft(s4log4 d/2bright). This group testing based scheme is adaptive to the sparsity parameter s, and hence can be applied without knowing it. For the interactive setting, we propose a novel tree-based estimation scheme and show that the minimum sample-size needed to achieve dimension-free convergence can be further reduced to n^*(s, d, b) = tildeOleft( s2log2 d/2b right).