Loosely speaking, the effective support size of a distribution  \(\mathcal D\) is the smallest size of the support of some distribution that is close to \(\mathcal D\) (in totally variation distance). We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distribution as well as an evaluation oracle (which returns the probability that the queried element appears in the distribution). In this context, we present several algorithms that exhibit a trade-off between the quality of the approximation and the complexity of obtaining it, and leave open the question of their optimality. In particular, for any constant \(\beta >1\) we present an algorithm that, on input \(\epsilon >0\) and oracle access to a distribution \(\mathcal D\) , uses \(O(1/\epsilon ^{1.001})\) samples and queries, and outputs a number \(\widetilde{n}\) such that \(\mathcal D\)  is \(\epsilon \) -far from any distribution that has support of size \(\widetilde{n}\) but is \(\beta \cdot \epsilon \) -close to a distribution that has support size \(f\cdot \widetilde{n}\) , where \(f=O(\log \log \log \log \log ({\widetilde{n}}/\epsilon ))\) . (Indeed, 1.001 stands for any constant larger than 1, and \(\log \log \log \log \log \) stands for any constant iterations of the logarithmic function.)

On the Complexity of Estimating the Effective Support Size

章节
发表日期：

2025年

查看全文

Oded Goldreich

摘要

Loosely speaking, the effective support size of a distribution \(\mathcal D\) is the smallest size of the support of some distribution that is close to \(\mathcal D\) (in totally variation distance). We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distribution as well as an evaluation oracle (which returns the probability that the queried element appears in the distribution). In this context, we present several algorithms that exhibit a trade-off between the quality of the approximation and the complexity of obtaining it, and leave open the question of their optimality. In particular, for any constant \(\beta >1\) we present an algorithm that, on input \(\epsilon >0\) and oracle access to a distribution \(\mathcal D\) , uses \(O(1/\epsilon ^{1.001})\) samples and queries, and outputs a number \(\widetilde{n}\) such that \(\mathcal D\) is \(\epsilon \) -far from any distribution that has support of size \(\widetilde{n}\) but is \(\beta \cdot \epsilon \) -close to a distribution that has support size \(f\cdot \widetilde{n}\) , where \(f=O(\log \log \log \log \log ({\widetilde{n}}/\epsilon ))\) . (Indeed, 1.001 stands for any constant larger than 1, and \(\log \log \log \log \log \) stands for any constant iterations of the logarithmic function.)