[edit]
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1028-1059, 2021.
Abstract
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 O(slog(d/s)n2b). Surprisingly, we show that when sample size n exceeds a minimum threshold n∗(s,d,b), we can achieve an ℓ2 estimation error of O(sn2b). 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)=O(min. Moreover, we connect the problem with non-adaptive group testing and obtain a polynomial-time estimation scheme when n = \tilde{\Omega}\left({s^4\log^4 d}/{2^b}\right). 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) = \tilde{O}\left( {s^2\log^2 d}/{2^b} \right).