2022/11/21 by Shyam Narayanan, Jakub Tětek, Narayanan, Shyam +1 · 1 citation
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2211.11344
openalex publication_date 2022/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Estimating the support size of a distribution is a well-studied problem in statistics. Motivated by the fact that this problem is highly non-robust (as small perturbations in the distributions can drastically affect the support size) and thus hard to estimate, Goldreich [ECCC 2019] studied the query complexity of estimating the ε-effective support size Essε of a distribution P, which is equal to the smallest support size of a distribution that is ε-far in total variation distance from P. In his paper, he shows an algorithm in the dual access setting (where we may both receive random samples and query the sampling probability p(x) for any x) for a bicriteria approximation, giving an answer in [Ess(1+β)ε,(1+γ) Essε] for some values β, γ> 0. However, his algorithm has either super-constant query complexity in the support size or super-constant approximation ratio 1+γ= ω(1). He then asked if this is necessary, or if it is possible to get a constant-factor approximation in a number of queries independent of the support size. We answer his question by showing that not only is complexity independent of n possible for γ>0, but also for γ=0, that is, that the bicriteria relaxation is not necessary. Specifically, we show an algorithm with query complexity O((1)/(β3 ε3)). That is, for any 0 < ε, β< 1, we output in this complexity a number n ∈ [Ess(1+β)ε,Essε]. We also show that it is possible to solve the approximate version with approximation ratio 1+γ in complexity O((1)/(β2 ε) + (1)/(βεγ2)). Our algorithm is very simple, and has 4 short lines of pseudocode.