Chebyshev polynomials, moment matching, and optimal estimation of the unseen

By Yihong Wu, Pengkun Yang. 2015

119 citations recorded by the source corpus.

We consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of $\epsilon k$ with probability at least 0.1 is within universal constant factors of $ \frac{k}{\log k}\log^2\frac{1}{\epsilon} $, which improves the state-of-the-art result of $ \frac{k}{\epsilon^2 \log k} $ in \cite{VV13}. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\log^2 k)$ time and attains the sample complexity within a factor of six asymptotically. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, methodology): “To prove Theorem 2, we build on the moment matching method from the literature on (non-private) distribution estimation, namely [43, 45], and tailor it to CountDistinct in the DP local setting (see Section 3.1 for more details on this connection).”
Minimax Rates of Estimating Approximate Differential Privacy (2019, methodology): “ntify the regime where the property to be estimated is not smooth, and use functional approximation to estimate a smoothed version of the property. This has been widely successful in support recovery [WY19], density estimation with ‘ 1 loss [HJW15], and estimating Renyi entropy [AOST17]. more recent”
INSPECTRE: Privately Estimating the Unseen (2018, methodology): “The non-private statistics have recently been demonstrated to be practical [OSW16, WY18], and the additional cost of the Laplace mechanism is minimal.”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, background): “The approximation ideas proved to be very fruitful in Acharya et al. [22], Wu and Yang [23], Han, Jiao, and Weissman [24], Jiao, Han, and Weissman [25], Bu et al. [26], Orlitsky, Suresh, and Wu [27], Wu and Yang [28].”
Introduction to Property Testing (2017, background): “28 with respect to the dependence on ǫ is provided in [271, 1].”