PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax rates of entropy estimation on large alphabets via best polynomial approximation

Yihong Wu, Pengkun Yang

arXiv:1407.0381v3cs.ITmath.ST

TL;DR

The paper asks how accurately Shannon entropy can be estimated from samples over a large alphabet. It characterizes the minimax risk and develops polynomial-approximation-based estimation, showing that consistency fails below the k log k sample scale and that empirical entropy is optimal only in a data-rich regime.

  • Problem

    The problem is to estimate Shannon entropy from samples when the alphabet is large and undersampling makes plug-in estimation highly biased.

  • Method

    The paper uses best polynomial approximation to construct estimable approximations of entropy, balancing approximation bias against estimator variance, and applies the same apparatus to the minimax lower bound.

  • Results

    If n ≲ k log k, no consistent estimator exists; empirical entropy is rate-optimal only when n = Ω(k^2) and is strictly rate-suboptimal otherwise.

  • Takeaways & Limitations

    The results identify the sample-size boundary for consistent entropy estimation and provide a linear-time estimator achieving the minimax risk within universal constant factors.

  • Takeaways & Limitations

    The estimator's analysis uses sample splitting, which loses half the sample and inflates risk by a constant factor; whether the same-sample version remains optimal is unresolved.

Abstract

from arXiv · show

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 universal multiplicative constant factors of $$\Big(\frac{k }{n \log k}\Big)^2 + \frac{\log^2 k}{n}$$ if $n$ exceeds a constant factor of $\frac{k}{\log k}$; otherwise there exists no consistent estimator. This refines the recent result of Valiant-Valiant \cite{VV11} that the minimal sample size for consistent entropy estimation scales according to $Θ(\frac{k}{\log k})$. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound.

1 Introduction

The paper studies minimax entropy estimation on large alphabets, where undersampling makes plug-in estimation highly biased, and characterizes optimal risk using best polynomial approximation.

  • The goal is to characterize the minimax quadratic risk for Shannon entropy estimation and construct a linear-time estimator achieving it within universal constant factors.
  • Large-alphabet applications exhibit undersampling, including rare words, infrequently observed users, and high-dimensional neural responses.
  • The minimax risk is characterized within universal constant factors, with a squared-bias term driven by insufficient samples and a variance term governed by the central limit theorem.
  • If n ≲ k log k, no consistent entropy estimator exists, with minimax risk bounded below by a constant.
  • Empirical entropy is rate-optimal only in the data-rich regime n = Ω(k^2); outside that regime, it is strictly rate-suboptimal.
  • Best polynomial approximation supports both the optimal estimator and the minimax lower bound, replacing entropy by estimable polynomial functionals and balancing bias against variance.

2 Poisson sampling

Poisson sampling replaces the fixed sample size with a Poisson variable, making histogram counts independent while preserving the statistical problem up to concentration-controlled risk comparisons.

  • Poissonization: Poisson sampling draws n′ ∼ Poi(n) observations before sampling independently from P.The Poissonized sample size concentrates near its mean n.
  • Poissonization: Under Poisson sampling, the sufficient-statistic counts N_i are independent Poisson variables with means np_i.This independence substantially simplifies analysis relative to the multinomial histogram.
  • Risk comparison: The Poissonized minimax risk is defined as the counterpart of the fixed-sample minimax risk.The exponential tail of the Poisson distribution supports comparison between the two sampling models.
  • Risk comparison: The fixed-sample and Poissonized risks are provably close, allowing the upper-bound analysis to focus on the Poisson model.The paper invokes the risk inequality together with concentration of the Poisson sample size.

3 Minimax lower bound

The lower bound separates variance and bias contributions, using composite-hypothesis testing and randomized priors whose indistinguishability reduces to moment matching and polynomial approximation.

  • Lower-bound strategy: The minimax lower bound is obtained by separately lower-bounding the two terms in the risk characterization.These converse bounds are combined to prove the lower-bound part of the main theorem.
  • Lower-bound strategy: Le Cam’s two-point method lower-bounds risk when distributions with separated entropies induce nearly indistinguishable histograms.The resulting quadratic risk scales with the squared entropy separation.
  • Composite testing: Composite hypotheses H0: H(P) ≤ t versus H1: H(P) ≥ t + d enable a stronger fuzzy-testing lower bound than simple two-point testing.If the hypotheses cannot be reliably distinguished, the quadratic risk is at least on the order of d^2.
  • Randomized priors: Permutation-invariant i.i.d. priors on random masses U and U′ exploit Poissonized independence, reducing indistinguishability analysis to one dimension.The induced random vectors are approximately probability distributions when the masses have unit mean and controlled variance.
  • Polynomial duality: Moment matching controls total variation, while a convex optimization over priors maximizes the entropy separation under those constraints.The optimization is connected to best uniform polynomial approximation of the entropy-related function.
  • Threshold result: Choosing degree L ≍ log k and λ ≍ log^2 k yields impossibility of consistent estimation when n ≍ k log k.For n ≫ k log k, relaxing the unit-mean constraint and scaling gives the quadratic-risk lower bound.

4 Optimal estimator via best polynomial approximation

The estimator approximates the entropy contribution of small probabilities with an unbiased polynomial estimator and uses a bias-corrected plug-in estimator for larger counts, achieving the minimax rate up to constants.

  • Motivation: The main estimation difficulty is bias from insufficient samples, especially for individually small probabilities that collectively contribute substantially to entropy.The relevant probability interval is approximately [0, log k/n].
  • Estimator construction: The estimator uses Poisson sample splitting, selecting between polynomial and plug-in procedures with one half and estimating with the other.The resulting count vectors N and N′ are independent.
  • Polynomial approximation: A degree L = floor(c0 log k) polynomial uniformly approximates x log(1/x) on the small-mass interval.Factorial moments provide an unbiased estimator for the polynomial’s monomials under Poisson sampling.
  • Estimator construction: For counts above the threshold, the procedure uses a bias-corrected plug-in estimator and clips the final estimate to [0, log k].The clipping uses the universal entropy range for distributions on an alphabet of size k.
  • Guarantee and computation: The estimator is computable in linear time because its fingerprint coefficients can be pre-computed using fast best-polynomial-approximation algorithms.The upper bound under Poisson sampling implies the fixed-sample minimax upper bound.
  • Limitation: Sample splitting costs a constant-factor risk inflation, and optimality without splitting remains unresolved in the paper.The authors note that other functionals can sometimes avoid sample splitting.
  • Guarantee and computation: The minimax rate continues to hold for k log k ≲ n ≲ k^2/log^2 k, where the plug-in estimator is rate-suboptimal.Removing the polynomial’s constant term can create systematic underbias, motivating a constrained approximation with p_L(0)=0.

5 Numerical experiments

The experiments compare the proposed estimator with alternatives across sparse and abundant sampling regimes, using synthetic distributions and RMSE over repeated trials.

  • Implementation: The implementation precomputes polynomial coefficients, applies the estimator efficiently, and uses fixed experimental parameters c0 = c2 = 1.6 and c1 = 3.5.The coefficients can be obtained efficiently with the Remez algorithm.
  • Estimator: Degree 18 polynomial estimation is used for symbols observed at most 18 times, while bias-corrected plug-in estimation handles larger counts.The approximation interval parameter is c1 log k = 40.
  • Experimental setup: 50 trials measure each estimator’s root mean squared error on four distributions over k = 10^5 elements.The distributions are uniform, two Zipf variants, and an even mixture of geometric and Zipf distributions.
  • Results: In the one-to-five-percent-of-k regime, the proposed estimator and those from VV13, JVHW15, and Pan03 significantly outperform Miller–Madow.The proposed estimator beats JVHW15 and Pan03 in most tested cases and is comparable to VV13.
  • Results: When samples are abundant, all estimators achieve very small error, while linear programming can deteriorate at very large sample sizes.For large samples, the proposed estimator tends toward Miller–Madow when every symbol is observed many times.

A A risk bound for the Poisson Sampling model

This appendix relates minimax entropy risk under fixed-size sampling to Poisson sampling. It uses Poisson concentration, minimax and Bayes-risk arguments, and monotone estimator sequences to establish the comparison.

  • Poissonization: Poisson sampling makes histogram counts independent Poisson variables, enabling the appendix’s risk comparison with fixed-size sampling.The appendix represents estimators as functions of the original samples and a Poisson sample count.
  • Risk comparison: The minimax theorem expresses the fixed-size minimax risk through a supremum of Bayes risks over priors on the simplex.This provides the basis for comparing fixed-size and Poissonized risks.
  • Risk comparison: A recursively defined estimator sequence has nonincreasing Bayes risk, allowing comparison across random Poisson sample sizes.At each sample size, the construction retains the better previous or current estimator.
  • Result: The appendix obtains the explicit comparison ˜R*(k, n/2) ≥ R*(k, n)/2.The argument uses Poisson concentration and the monotonicity of minimax risk.

B Proof of the lower bound

The lower-bound proof uses Le Cam’s two-point method and constructs distribution pairs whose entropy differs substantially while their induced observations remain difficult to distinguish.

  • Lower-bound strategy: Le Cam’s two-point method reduces the lower bound to finding distributions with separated entropy and nearly indistinguishable sufficient statistics.The proof applies this method to the histogram-based observation model.
  • Distribution construction: The construction uses two probability vectors differing through a parameter ϵ while maintaining a constant entropy separation.The parameter is later chosen as ϵ = 1 / √n.
  • Information-theoretic link: Pinsker’s inequality and entropy continuity connect total variation closeness to bounds on divergence and entropy differences.These inequalities provide an alternative perspective on the indistinguishability requirement.
  • Lower-bound strategy: The selected distribution pair is optimal for the two-point method, whose best lower bound is on the order of log k / √n.The proof identifies the supremum’s order and concludes that the pair achieves it.

B.2 Proof of Proposition 3

The proof constructs moment-matched random variables from the dual of a best polynomial approximation problem, then uses Poisson-mixture indistinguishability to obtain the minimax lower bound.

  • Poisson indistinguishability: Moment matching through order L makes Poisson mixtures indistinguishable when L exceeds a constant multiple of the support bound.The proof directly controls total variation between mixture probability mass functions.
  • Prior construction: The change-of-measure construction produces U and U′ with equal means, matched moments, and separated values of the entropy-related functional.Their common mean is α, and the functional separation is αE* before applying the approximation bound.
  • Polynomial duality: The dual of an infinite-dimensional linear program identifies the optimization value with twice the best uniform polynomial approximation error of log on [η, 1].The approximation uses polynomials of degree L.
  • Polynomial duality: For fixed degree L, the approximation error diverges as η approaches zero; keeping it bounded away from zero requires η to decay as L^-2.The error decreases with L when η is fixed.
  • Lower-bound rate: Choosing η = log^-2 k and L proportional to log k yields R*(k, n) ≳ (k / (n log k))^2 for n ≥ k log k, while smaller n gives a constant lower bound.The proof obtains this through Poisson-mixture total variation control and Le Cam’s method.
  • Least favorable priors: The least favorable priors use only log k distinct masses, randomly permuted across k symbols, with entropies separated by a constant multiple of k / (n log k).The entropy values concentrate near their respective means.

C Proof of the upper bound

The upper-bound proof controls the estimator’s bias and variance by separating small- and large-probability coordinates, using polynomial approximation and a bias-corrected plug-in estimator.

  • Thresholding and events: High-confidence thresholding distinguishes coordinates whose probabilities lie above or below constant factors of log k/n.The proof uses threshold events and Poisson concentration to classify coordinates.
  • Polynomial estimator: The polynomial estimator’s variance is controlled through bounded polynomial coefficients and Poisson factorial-moment variance bounds.Coefficient magnitudes are bounded by a constant factor of 2^3L, while Lemma 6 supplies monotonicity and variance bounds.
  • Bias-corrected plug-in estimator: The bias-corrected plug-in estimator uses a Taylor expansion of x log x around 1, with a fourth-order remainder bound.The expansion bounds the correction error by (x − 1)^4 and uses Poisson central moments.
  • Conclusion: Combining the bias, variance, and event-probability bounds completes the upper-bound proof after choosing constants c1 > c2 > c3.The estimator is clipped to [0, log k], which bounds its entropy error by log k on failure events.

D Non-asymptotic risk bounds for the plug-in estimator

This section derives non-asymptotic risk bounds for the plug-in entropy estimator by separately controlling its bias and variance using concentration inequalities.

  • Bias: The squared bias is bounded by (k−1/n)^2 for the plug-in estimator.The bound follows from a cited proposition on plug-in bias.
  • Variance: The variance is controlled with Steele’s inequality and binomial or Poisson tail bounds applied to histogram counts.The proof introduces independent histogram counts and applies Chernoff bounds.
  • Variance: When n ≥ k, the plug-in estimator’s variance satisfies var Ĥplug-in ≲ log^2 k.The proof uses n log^2 k ≲ 1 under the stated condition.

E Moment matching and best polynomial approximation

The paper connects moment matching with best uniform polynomial approximation, using duality and alternating points to construct distributions that separate expectations of the target function.

  • Approximation formulation: Best uniform approximation error is defined as EL(g, [a, b]) = infp∈PL supx∈[a,b] |g(x) − p(x)|.This quantity measures the smallest degree-L polynomial approximation error on an interval.
  • Achievability: Chebyshev’s alternating theorem supplies a degree-L polynomial and at least L + 2 alternating extremal points.These points attain alternating deviations of magnitude equal to the best approximation error.
  • Moment matching: The alternating-point construction produces discrete random variables X and X′ with matching moments through degree L.The distributions assign alternating-point weights according to the signs of the interpolation coefficients.
  • Lower-bound connection: The resulting expectation gap is 2 ĤE∗, directly linking moment matching to the best polynomial approximation error.This supplies the duality-based separation used in the lower-bound argument.

F Best polynomial approximation of the logarithm function

The section establishes non-asymptotic approximation bounds for a logarithm-derived function on an interval approaching zero, showing that the relevant degree-scaled error remains constant-order.

  • Problem: The approximation problem is difficult because the approximand fL changes with the degree L.The cited asymptotic result concerns approximation of log(a − x) for fixed a > 1.
  • Approximation bounds: The modulus τ1(f, Δm) measures the largest function change over pairs constrained by the degree-dependent distance Δm(x).Here Δm(x) = (1 − x^2)^(1/2)/m + 1/m^2.
  • Approximation bounds: Direct and converse approximation bounds are combined to control Em(fL) non-asymptotically.The proof applies bounds relating approximation error to the modulus of continuity and uses monotonicity in polynomial degree.
  • Conclusion: EcL(log, [1/L^2, 1]) ≍ 1, so the degree-cL approximation error on this interval is tight up to constant factors.The direct bound gives the matching upper order, while the converse argument gives the lower order.

G Approximation error at the end points

The endpoint errors of the best polynomial approximation attain the maximum uniform approximation error, with the signs determined from the derivative behavior at zero.

  • Chebyshev alternation gives at least L+2 alternating extrema of the error function, located at stationary points or endpoints.This alternation structure is the starting point for counting possible stationary points.
  • The approximation error reaches its uniform maximum at both endpoints, so |g(0)| = |g(1)| = E_L(φ).The argument uses the limited number of stationary points of g to force endpoint alternation values.
  • Because g′ has at most L−1 stationary points, the interior stationary points cannot account for all alternating extrema, forcing maximal errors at the endpoints.The root-counting argument bounds the number of interior stationary points of g.
  • Since g′(0) = −∞, the endpoint sign must be positive at zero, yielding a_0 = g(0) = E_L(φ).A negative value at zero would make the first stationary value violate the uniform error bound.
Loading 1407.0381v3…