PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum Likelihood Estimation of Functionals of Discrete Distributions

Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman

arXiv:1406.6959v7cs.ITmath.ITmath.STstat.TH

TL;DR

The paper addresses the limits of MLE estimation for discrete-distribution functionals in large-alphabet settings. It characterizes worst-case risk using nonasymptotic analysis and approximation theory. The results give consistency thresholds for entropy and Fα(P), and show that Dirichlet smoothing does not improve on the MLE’s large-alphabet consistency requirement.

  • Problem

    Classical asymptotic theory does not adequately address entropy estimation when the alphabet is comparable to or larger than the sample size, where the MLE is suboptimal.

    Source: §I · p. 2

  • Method

    The paper characterizes worst-case squared-error risk for plug-in MLEs and connects their bias analysis to approximation theory using positive linear operators.

    Source: §I · p. 2, B. Bias · p. 7

  • Results

    MLE consistency requires n ≫ S for entropy and n ≫ S^(1/α) for Fα(P) when 0 < α < 1; Dirichlet approaches also require n ≫ S in the large-alphabet regime.

    Source: §I · p. 2, B. Estimating H(P) · p. 5, A. Estimating Fα(P) · p. 5

  • Takeaways & Limitations

    The risk analysis provides a benchmark for other estimation procedures and identifies regimes where the problem is difficult.

    Source: §I · p. 2

Abstract

from arXiv · show

We consider the problem of estimating functionals of discrete distributions, and focus on tight nonasymptotic analysis of the worst case squared error risk of widely used estimators. We apply concentration inequalities to analyze the random fluctuation of these estimators around their expectations, and the theory of approximation using positive linear operators to analyze the deviation of their expectations from the true functional, namely their \emph{bias}. We characterize the worst case squared error risk incurred by the Maximum Likelihood Estimator (MLE) in estimating the Shannon entropy $H(P) = \sum_{i = 1}^S -p_i \ln p_i$, and $F_\alpha(P) = \sum_{i = 1}^S p_i^\alpha,\alpha>0$, up to multiplicative constants, for any alphabet size $S\leq \infty$ and sample size $n$ for which the risk may vanish. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have $n \gg S$ observations for the MLE to be consistent. In addition, we establish that it is necessary and sufficient to consider $n \gg S^{1/\alpha}$ samples for the MLE to consistently estimate $F_\alpha(P), 0<\alpha<1$. The minimax rate-optimal estimators for both problems require $S/\ln S$ and $S^{1/\alpha}/\ln S$ samples, which implies that the MLE has a strictly sub-optimal sample complexity. When $1<\alpha<3/2$, we show that the worst-case squared error rate of convergence for the MLE is $n^{-2(\alpha-1)}$ for infinite alphabet size, while the minimax squared error rate is $(n\ln n)^{-2(\alpha-1)}$. When $\alpha\geq 3/2$, the MLE achieves the minimax optimal rate $n^{-1}$ regardless of the alphabet size. As an application of the general theory, we analyze the Dirichlet prior smoothing techniques for Shannon entropy estimation. We show that no matter how we tune the parameters in the Dirichlet prior, this technique cannot achieve the minimax rates in entropy estimation.

I. INTRODUCTION

The paper studies when plug-in MLEs work for discrete-distribution functionals in large-alphabet settings, where classical fixed-dimension asymptotics do not settle the question. It characterizes worst-case squared-error risk and connects plug-in bias analysis to approximation theory, then gives consistency and rate results for Fα(P).

I. INTRODUCTION

  • The empirical entropy is the plug-in MLE for Shannon entropy, whose large-alphabet consistency threshold is n ≫ S.This threshold is necessary and sufficient for MLE consistency.Source: §I · p. 1
  • The MLE’s worst-case squared-error risk for H(P) and Fα(P) is characterized up to universal multiplicative constants over regimes where risk may vanish.The analysis also relates plug-in bias analysis to approximation theory using positive linear operators.Source: §I · p. 2
  • For entropy estimation, neither Dirichlet prior approach improves on the MLE in the large-alphabet regime; both require n ≫ S for consistency.The paper contrasts this with minimax rate-optimal estimators, which need n ≫ S/ln S.Source: §I · p. 2

II. PRELIMINARIES

  • The paper defines the MLEs of H(P) and Fα(P) as their plug-in estimates evaluated at the empirical distribution Pn.It models the observations as n i.i.d. draws from an unknown discrete distribution.Source: §II · p. 3

A. Estimating Fα(P)

  • For α ≥ 3/2, the MLE achieves the minimax rate n^-1, while for 1 < α < 3/2 its rate is n^-2(α-1) and the minimax rate is (n ln n)^-2(α-1) when S ≳ n ln n.The latter comparison shows a slower MLE rate in that stated alphabet-size regime.Source: A. Estimating Fα(P) · p. 4
  • For 0 < α < 1, MLE consistency for Fα(P) requires and is guaranteed by n ≫ S^(1/α).The required sample scale grows as α decreases; the minimax rate-optimal estimator instead needs n ≫ S^(1/α)/ln S.Source: A. Estimating Fα(P) · p. 5
  • Figure 1 presents the consistency boundary: above its thick curve the MLE consistently estimates Fα(P), while below it nonvanishing risk is established for 0 < α < 1.The figure’s below-curve conclusion is limited to that α regime.Source: Figure 1 · p. 5

B. Estimating H(P)

For Shannon entropy, the MLE is consistent exactly when n >> S. Dirichlet prior smoothing also requires n >> S for consistency and does not attain the minimax sample complexity.

B. Estimating H(P)

  • n >> S observations are necessary and sufficient for MLE consistency in Shannon entropy estimation.The paper states this conclusion from its worst-case risk analysis.Source: B. Estimating H(P) · p. 5
  • The MLE does not attain the minimax squared-error rates for Shannon entropy or Fα(P) when 0 < α < 3/2.The paper reports that strictly better estimators exist in these cases.Source: B. Estimating H(P) · p. 5

C. Dirichlet prior techniques applying to entropy estimation

  • For the Dirichlet prior plug-in estimator, risk vanishes when n >> S and a is bounded above by a constant, while it stays bounded away from zero when n ≲ S.Unlike the MLE, this smoothing scheme generally requires knowledge of the alphabet size S.Source: C. Dirichlet prior techniques applying… · p. 6
  • Dirichlet prior plug-in and Bayes estimators still require n >> S for consistency when the prior parameter is not too large.The compared minimax estimators are consistent with n >> S/ln S samples.Source: C. Dirichlet prior techniques applying… · p. 7

IV. FUNDAMENTAL IDEAS OF OUR ANALYSIS

The analysis separates estimator fluctuation from bias: concentration inequalities bound variance, while positive-linear-operator approximation theory analyzes bias. General bias bounds can be loose, so the analysis also uses properties specific to the functionals.

A. Variance

  • Concentration inequalities, especially Efron–Stein and bounded differences, provide tight bounds on estimator fluctuation for the functionals considered.The section presents these as tools for bounding variance.Source: A. Variance · p. 7

B. Bias

  • Taylor expansions may fail to give uniform MLE entropy-bias bounds, motivating the use of Bernstein polynomial approximation error to analyze plug-in bias.The sum appearing in the Taylor-based bound can be arbitrarily large, even though entropy is bounded above by ln S.Source: B. Bias · pp. 7–8

1) Approximation theory using positive linear operators:

  • The expectation of a plug-in estimator is a positive linear operator, making its bias an approximation error that positive-operator theory can analyze.For the MLE, the relevant approximation is the Bernstein polynomial of the function being estimated.Source: 1) Approximation theory using positive… · p. 8, B. Bias · p. 8
  • General positive-operator tools are well developed for functions on one-dimensional compact sets, but remain incomplete for vector-valued multivariate functions on non-compact sets.The paper applies such tools to analyze MLE bias for Fα(P) and H(P).Source: 1) Approximation theory using positive… · p. 8

2) Some general results in bias analysis:

  • General bias bounds can be non-optimal; for entropy, a Ditzian–Totik modulus bound can be stronger than the earlier general estimate.The section notes that even the pointwise bound cited for entropy is strictly suboptimal when θ ≤ 1/n, motivating use of specific-function structure.Source: 2) Some general results in bias analysis · p. 9

C. Lower bounds

The proofs combine estimator-specific bias or variance analysis with lower bounds that apply to all estimators. For upper bounds, Bernstein-polynomial approximation controls bias, with separate bounds developed for power functionals and entropy.

C. Lower bounds

  • The lower-bound construction combines careful analysis of an estimator's bias or variance with bounds that hold for every estimator.The section also states the van Trees inequality for average squared-error risk under regularity conditions on the model and prior.Source: C. Lower bounds · pp. 9–10

A. Bounding the bias

  • Bernstein-polynomial approximation bounds are used to analyze plug-in bias, with pointwise and norm estimates available for the approximation error.The bounds are not expected to be tight for every continuous function.Source: A. Bounding the bias · p. 10
  • For 1 < α < 2, the bias bound for Fα(Pn) can be made independent of alphabet size by combining bounds specific to x^α with general approximation estimates.The passage notes that the specific properties of x^α are used in the alphabet-size-independent bound.Source: 1) Bias of Fα(Pn) · p. 11
  • The entropy bias analysis also uses approximation bounds, while its sharper bound relies on a proof that applies only to the entropy function.A more general lemma gives a bound that is only sub-optimal up to a multiplicative constant.Source: 2) Bias of H(Pn) · p. 11, 3) Bias of H( ˆPB) · p. 12

B. Bounding the variance

This section upper-bounds the variances of the plug-in estimators for power functionals and entropy, as well as the Dirichlet-smoothed entropy estimator.

B. Bounding the variance

  • Variance upper bounds are provided for Fα(Pn) in both the α > 1 and 0 < α < 1 regimes.The proof for α > 1 invokes Bernoulli's inequality and a bounded-difference lemma.Source: B. Bounding the variance · p. 12
  • The section also gives variance upper bounds for the empirical entropy H(Pn) and the Dirichlet-smoothed entropy estimator.The supplied passages identify these bounds but do not state their full expressions.Source: B. Bounding the variance · p. 12

VI. PROOFS OF THE LOWER BOUNDS

The lower-bound proofs use different strategies across power-functional regimes, including van Trees for α ≥ 3/2 and approximation-based arguments for 1 < α < 3/2. They also construct lower bounds for entropy estimation.

A. Lower bounds for estimation of Fα(P) when α ≥3/2

  • For α ≥ 3/2, the proof reduces to the S = 2 binomial model and applies the van Trees inequality to obtain an n^-1 lower bound.A Dirichlet prior on the binomial parameter is used to evaluate the relevant integrals.Source: A. Lower bounds for estimation of… · pp. 12–13

B. Lower bounds for estimation of Fα(P) when 1 < α < 3/2

  • For 1 < α < 3/2, the proof applies a Taylor-remainder lemma to fα(x) = -x^α and considers distributions with S = cn.The construction treats c ≤ 1 and c > 1 separately, with a continuity argument for the latter case.Source: B. Lower bounds for estimation of… · pp. 13–14

C. Lower bounds for estimation of Fα(P) when 0 < α < 1

The lower-bound arguments cover power functionals for 0 < α < 1, Shannon entropy, and two Dirichlet-based entropy estimators.

C. Lower bounds for estimation of Fα(P) when 0 < α < 1

  • For 0 < α < 1, the proof uses a Taylor-remainder bound for x^α and a constructed distribution to lower-bound the MLE risk.It also invokes a minimax lower bound for 1/2 ≤ α < 1, which applies to the MLE because it is one of the estimators covered.Source: C. Lower bounds for estimation of… · p. 14

D. Lower bounds for estimation of H(P)

  • The entropy lower-bound arguments use approximation error for -x ln x and a uniform distribution, alongside a minimax lower bound applying to all estimators.The cited passages do not expose the full bound expressions.Source: D. Lower bounds for estimation of H(P) · p. 14

E. Lower bounds for entropy estimation using H( ˆPB)

  • For the Dirichlet plug-in entropy estimator, the paper gives lower-bound cases when n < Sa and when n < 2ea.The following theorem combines these cases with an entropy minimax lower bound.Source: E. Lower bounds for entropy estimation… · p. 15
  • For the Bayes entropy estimator, the proof uses its upper bound and evaluates squared error under the uniform distribution when S ≥ 2(n + 1).The supplied passages state this setting but do not include the full resulting error expression.Source: F. Lower bounds for entropy estimation… · p. 15

APPENDIX A AUXILIARY LEMMAS

The auxiliary lemmas establish negative association for multinomial counts and provide bounds used in the estimator analyses. The proofs also derive second-order moduli for entropy and power functions.

APPENDIX A AUXILIARY LEMMAS

  • Conditioning independent Poisson variables on their sum yields multinomial counts that are negatively associated.This property is used to upper-bound variance by treating empirical-distribution components as independent.Source: Appendix A · p. 15
  • The auxiliary lemmas also give digamma-function bounds and tail bounds for Poisson or Binomial variables.The digamma bound is ln(x + 1/2) < ψ(x + 1) ≤ ln(x + e^(1−γ) − 1).Source: Appendix A · p. 16
  • For the plug-in estimator Fα(Pn), the variance analysis separates probabilities into p ≤ 1/n and p > 1/n regimes.The corresponding lemmas give variance bounds for each regime.Source: Appendix A · p. 16

A. Proof of Lemma 3

B. Proof of Lemma 8

  • The entropy function −x ln x has second-order modulus t^2 ln 4/(1+t^2), attained at u = 0 and v = 2t^2/(1+t^2).For x^α with 0 < α < 1, the modulus is |2 − 2^α|t^α; for 1 < α < 2, it is of order t^2.Source: B. Proof of Lemma 8 · pp. 16–17

C. Proof of Lemma 9

These proofs bound bias terms for power-functional and entropy estimators. The entropy analysis separates the deterministic change from smoothing from an expected KL-divergence term.

C. Proof of Lemma 9

  • For the power-functional bias with 1 < α < 2, the proof bounds two terms separately, using Jensen’s inequality for one and a pointwise estimate for the other.Source: C. Proof of Lemma 9 · p. 17

D. Proof of Lemma 11

  • The proof of Lemma 11 bounds an entropy-related term using convexity over the probability simplex and requires n ≥ 4 for its stated intermediate condition.Source: D. Proof of Lemma 11 · p. 18

E. Proof of Lemma 12

F. Proof of Lemma 13

The proofs use changes to individual samples and count dependence properties to bound estimator fluctuations. For entropy, they condition on the observed counts to characterize the removed sample.

F. Proof of Lemma 13

  • For a monotone functional, changing one sample changes the estimate by at most the largest adjacent-grid increment; for a non-monotone functional, the bound is twice that increment.Source: F. Proof of Lemma 13 · p. 19

G. Proof of Lemma 14

  • The proof of Lemma 14 uses negative association of empirical counts together with monotonicity of x^α to obtain its bounds.Source: G. Proof of Lemma 14 · p. 19

H. Proof of Lemma 15

  • The entropy variance proof applies Efron–Stein after decomposing the estimator change into removal and replacement contributions.Source: H. Proof of Lemma 15 · pp. 19–20
  • Given the counts, the removed sample Z1 has conditional distribution (X1/n, X2/n, …, XS/n), enabling the entropy variance proof to split its change into removal and replacement terms.Source: H. Proof of Lemma 15 · p. 20

I. Proof of Lemma 16

The proof bounds fluctuations of the smoothed entropy estimator by analyzing how changing one sample alters it. It then applies bounded-differences and Efron–Stein inequalities.

I. Proof of Lemma 16

  • Changing one sample changes two symbol counts by one, and the proof uses the resulting estimator change to apply the bounded-differences inequality to the smoothed entropy estimate.Source: §I · p. 21
  • The proof also applies Efron–Stein to the smoothed entropy estimator, which is invariant to permutations of the sample.Source: §I · p. 21

J. Proof of Lemma 18

These proofs derive bounds for power functions using Taylor expansions around x0 and properties of Bernstein polynomials. The expansions and polynomial degrees differ between the two lemmas.

J. Proof of Lemma 18

K. Proof of Lemma 19

L. Proof of Lemma 23

These proofs establish bounds using case-specific inequalities for entropy and power sums, alongside Taylor-remainder estimates for binomial counts.

L. Proof of Lemma 23

  • The proof obtains a first lower bound from the point mass P = (1, 0, 0, · · ·, 0), for which H(P) = 0, and combines two inequalities to obtain a second bound when n < 15S.It also uses that f(x) = −x ln x is monotonically increasing on [0, e^-1].Source: L. Proof of Lemma 23 · pp. 23–24
  • The proof invokes a refinement result when all coordinate errors are at most 1/2, a condition ensured by n ≥ Sa.Source: L. Proof of Lemma 23 · p. 23

A. Proof of Lemma 27

  • For 0 < α < 1 and p ≤ 1/n, integrality of nX gives (nX)^2 ≥ (nX)^(2α), completing the proof of Lemma 27.Source: A. Proof of Lemma 27 · p. 24

B. Proof of Lemma 28

  • The Lemma 28 proof bounds expectations of f(X) and f²(X) for nX ∼ B(n, p), using Taylor expansions and remainder estimates.Source: B. Proof of Lemma 28 · p. 24

Related papers

Loading 1406.6959v7…