Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs

By Gregory Valiant, Paul Valiant. 2011

317 citations recorded by the source corpus.

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear--sample estimators achieving arbitrarily small additive constant error for a class of properties that includes entropy and distribution support size. Additionally, we show new matching lower bounds. Together, this settles the longstanding question of the sample complexities of these estimation problems, up to constant factors. Our algorithm estimates these properties up to an arbitrarily small additive constant, using O(n/log n) samples, where n is a bound on the support size, or in the case of estimating the support size, 1/n is a lower bound on the probability of any element of the domain. Previously, no explicit sublinear--sample algorithms for either of these problems were known. Our algorithm is also computationally extremely efficient, running in time linear in the number of samples used. In the second half of the paper, we provide a matching lower bound of Ω(n/log n) samples for estimating entropy or distribution support size to within an additive constant. The previous lower-bounds on these sample complexities were n/2O(√log n). To show our lower bound, we prove two new and natural multivariate central limit theorems (CLTs); the first uses Stein's method to relate the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance metric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central limit theorem for "generalized multinomial" distributions---a large class of discrete distributions, parameterized by matrices, that represents sums of independent binomial or multinomial distributions, and describes many distributions encountered in computer science. Convergence here is in the strong sense of statistical distance, which immediately implies that any algorithm with input drawn from a generalized multinomial distribution behaves essentially as if the input were drawn from a discretized Gaussian with the same mean and covariance. Such tools in the multivariate setting are rare, and we hope this new tool will be of use to the community.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Formal Limitations on the Measurement of Mutual Information (2018, background): “hat estimator is used. There is a line of work that develops efﬁcient estimators for entropy by assuming distributions with very small support—distributions with support smaller than the sample size. Valiant and Valiant (2011) show that it is possible to achieve an optimal sample rate of O(n=lnn) wh”
Instance optimal learning of discrete distributions (2016, methodology): “The papers [32, 34] were concerned with developing estimators for entropy, support size, etc.— properties that depend only on the unlabeled vector of probabilities of a distribution.”
Learning Populations of Parameters (2017, background): “The benefit of pursuing this weaker goal of returning the unlabeled multiset is that it can be learned to significantly higher accuracy for a given sample size—essentially as accurate as the empirical distribution of a sample that is a logarithmic factor larger [15, 17].”
Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation (2014, background): “For (12) we need to choose a pair of priors, which, in this case, are distributions on the probability simplex M k , is to ensure the entropy values are separated.”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, background): “) For any constants 1 < 2, it requires Θ( n logn ) samples to distinguish ||p − q|||1≤ 1 from ||p − q|||1≥ 2 when p is the uniform distribution on n elements, many more than the √ n needed here [16], [17].”
Differentially private anonymized histograms (2019, methodology): “Anonymized histograms are also referred to as histogram of histograms [1], histogram order statistics [2], profiles [3], unattributed histograms [4], fingerprints [5], and frequency lists [6].”
Introduction to Property Testing (2017, methodology): “4 are based on the work of Valiant and Valiant [263].”
Obfuscation via Information Density Estimation (2019, background): “…inherently connected to mutual information estimation (since the expected value of information density is equal to the mutual information) which is known to be challenging (Valiant and Valiant, 2011; Wu and Yang, 2016; Gao et al., 2017) unless an adequate parametric model is assumed (Vapnik, 2013).”
A high-dimensional CLT in W2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {W}_2$$\end{document} distance wi (2017, background): “Then, This bound improves by a factor of √ d the result of Valiant and Valiant [24], who obtain under the same assumptions a O (cid:2) d β log n √ n (cid”
Demystifying fixed k-nearest neighbor information estimators (2016, methodology): “A canonical question in all these applications is to estimate the information theoretic quantities from samples, typically supposed to be drawn i.i.d. from an unknown distribution.”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, background): “It was Valiant and Valiant [16] who first explicitly constructed a linear programming based estimator (later modified in [17]) that achieves consistency in entropy estimation with n S/ ln S samples, which they also proved to be necessary.”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “The broader problem of estimating smooth functionals of distributions was considered in [41].”
Estimating Mutual Information for Discrete-Continuous Mixtures (2017, background): “Novel entropy estimators with sub-linear sample complexity have been proposed [48, 53, 19, 21, 20, 23].”