Estimating entropy on m bins given fewer than m samples

By Liam Paninski. 2004

147 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Mathematical Physics

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 Mathematical Physics

Citations in the corpus

Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “In a signiﬁcant body of work spanning more than a decade [8, 41, 7, 42, 2, 14, 37, 53, 23, 56, 36, 13, 25], a myriad of properties has been investigated under this lens.”
A CLT and tight lower bounds for estimating entropy (2010, background): “We explicitly exhibit such a family of pairs of distributions D,D′ via a Laguerre polynomial construction that may be of independent interest.”
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (2011, methodology): “In a different direction, Paninski gave a simple though non–constructive proof of the existence of a sublinear sample estimator for additively approximating the entropy to within a constant; the proof is via a direct application of the Stone-Weierstrass theorem to the set of Poisson functions [33, 3”
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.”
Minimax Estimation of Functionals of Discrete Distributions (2014, background): “[60] L. Paninski, “Variational minimax estimation of discrete distributions under KL loss,” in Advances in Neural Information Processing Systems, 2004, pp. 1033–1040.”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, unknown): “[6], [4], [10], [11], [12], [3], [8]), and on establishing lower bounds [14], [18].”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “It was recently shown that estimating the Shannon entropy of a discrete distribution p over k elements to a given additive accuracy requires (k/ log k) independent samples from p [33], [41]; see [16], [43] for subsequent extensions.”
Instance optimal learning of discrete distributions (2016, background): “…a long line of work considering distributional property testing, estimation, and learning questions from a worst case standpoint—typically parameterized via an upper bound on the support size of the distribution from which the samples are drawn (e.g. [8, 31, 5, 24, 10, 30, 36, 33, 32, 12, 34]).”
Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation (2014, methodology): “Paninski also investigated using approximation by Bernstein polynomials to reduce the bias of the plug-in estimators [Pan03], which forms the basis for proving the existence of consistent estimators with sublinear sample complexity in [Pan04].”
The Power of Linear Estimators (2011, methodology): “Turning, for a moment, to the side of constructing linear estimators, a natural and popular approach is to represent the “characteristic function” of the property in question as a linear combination of “Poisson functions” poi(x, i) ≜ e−xxi i! ; see [11], [20], [21], [22], [25], [30].”
Causality detection based on information-theoretic approaches in time series analysis (2007, background): “In a more recent work by the same author [168], the entropy estimation is investigated in the undersampled regime (i.e. on m bins given fewer than m samples).”
A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data (2008, methodology): “This is similar in spirit to the recent observation that estimating the entropy of discrete distributions is easy (Paninski, 2004) (in that case,N = cm for any c > 0 suffices, and hence by a subsequence argument in fact slightly fewer than∼ m samples are required to estimate the entropy onm bins).”
A Bernstein-Von Mises Theorem for discrete probability distributions (2008, background): “ven probability distribution (Csisza´r and Korner, 1981; Cover and Thomas, 1991; Gallager, 1968). The problem of estimating such functionals has been investigated by Antos and Kontoyiannis (2001) and Paninski (2004). It has been checked there that plug-in estimates of the Shannon and R´enyi entropie”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, background): “Paninski [14] showed that the MLE needs n S samples to consistently estimate the Shannon entropy, and Paninski [15] established the existence of a (non-explicit) estimator that only required n S samples.”