Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation

By Yihong Wu, Pengkun Yang. 2014

241 citations recorded by the source corpus.

Consider the problem of estimating the Shannon entropy of a distribution over k elements from n independent samples. We show that the minimax mean-square error is within the universal multiplicative constant factors of (k/n log k)2 t log2 k/n if n exceeds a constant factor of (k/log k); otherwise, there exists no consistent estimator. This refines the recent result of Valiant and Valiant that the minimal sample size for consistent entropy estimation scales according to Θ(k/log k). The apparatus of the best polynomial approximation plays a key role in both the construction of optimal estimators and, by a duality argument, the minimax lower bound.

Subfields: Artificial Intelligence, Cellular and Molecular Neuroscience, Cognitive Neuroscience

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 Cellular and Molecular Neuroscience

In Cognitive Neuroscience

Citations in the corpus

Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “DP Le Cam’s method Le Cam’s method (Lemma 1 of Yu (1997)) is widely used to prove lower bounds for composite hypothesis testings such as uniformity testing (Paninski, 2008), density estimation (Yu, 1997; Ray and Schmidt-Hieber, 2018), and estimating functionals of distributions (Jiao et al., 2015; W”
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, background): “[44], Wu and Yang [45] and Issa et al.”
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].”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “In a significant body of work spanning more than a decade [2, 7, 8, 13, 14, 23, 26, 37, 39, 43, 44, 55, 57], a myriad of properties has been investigated under this lens.”
Efficient quantum tomography (2015, unknown): “true von Neumann entropy with high probability when n = O(d2/ǫ+ log(d)2/ǫ2). This gives an expression similar to both the bias and the mean absolute error of the classical empirical entropy estimator [WY16]. 1.7 Organization Section 2 contains the preliminaries, Section 3 contains the proof of Theor”
Chebyshev polynomials, moment matching, and optimal estimation of the unseen (2015, methodology): “The technique of polynomial approximation has been previously used for estimating non-smooth functions (Lq-norms) in Gaussian models [19, 22, 4] and more recently for estimating information quantities (entropy and power sums) on large discrete alphabets [43, 20].”
Estimating Information Flow in Neural Networks (2018, background): “We also note that, for any d, the critical β0(d) value from the 2nd part can be extracted by following the constants through the proof (which relies on Proposition 3 from [14]).”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, background): “Valiant(2011)). Yet another area of interest has been estimating quantities related to a discrete distribution, such as support size or entropy (see e.g.Valiant and Valiant(2011);Acharya et al.(2014);Wu and Yang (2016a,b);Orlitsky et al.(2016)). In much of this literature, it is often assumed that o”
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.”
Estimating Renyi Entropy of Discrete Distributions (2014, methodology): “The Polynomial Approximation Estimator Concurrently with a conference version of this paper [1], a polynomial approximation based approach was proposed in [16] and [43] for estimating additive functions of the form ∑ x f (px).”
Differentially private anonymized histograms (2019, background): “, [5, 18, 20, 21, 22, 19, 23, 24] and has applications in various fields from neuro-science [2] to genetics [25].”
Minimax optimal conditional independence testing (2020, background): “k>n P(N = k)Rk(H0,H0,H1, ε) ≤ P(Poi(2n) ≤ n) +Rn(H0,H0,H1, ε) ≤ exp(−(1− log 2)n) +Rn(H0,H0,H1, ε), where in the last inequality we used a Chernoff bound [40].”