PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax Estimation of Functionals of Discrete Distributions

Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman

arXiv:1406.6956v5cs.ITmath.ST

TL;DR

The paper studies how to estimate information-theoretic functionals when the underlying distribution is unknown and the sample size may be comparable to parameter dimension. It develops separate methods for nonsmooth and smooth regions, obtaining minimax results for entropy and related functionals.

  • Problem

    Unknown distributions make information-theoretic quantities difficult to compute, while plug-in MLE approaches can be highly sub-optimal when observations are comparable to parameter dimension.

  • Method

    The approach treats nonsmooth and smooth regions separately, using unbiased estimation of best polynomial approximations in nonsmooth regions and bias-corrected MLE in smooth regions.

  • Results

    The minimax rates include n ≳ S/ln S for entropy-related estimation and (n ln n)^-2(α-1) for F_α(P) when 1<α<3/2, compared with n^-2(α-1) for the MLE.

  • Takeaways & Limitations

    Entropy estimation can be easier than estimating the full distribution or compression, and the estimator can simultaneously achieve minimax rates over entropy-constrained subsets without knowing the constraint or alphabet size.

  • Takeaways & Limitations

    The entropy results considered here apply to all distributions supported on S elements; additional structural restrictions define different estimation problems and may yield different answers.

Abstract

from arXiv · show

We propose a general methodology for the construction and analysis of minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the alphabet size $S$ is unknown and may be comparable with the number of observations $n$. We treat the respective regions where the functional is "nonsmooth" and "smooth" separately. In the "nonsmooth" regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the "smooth" regime, we apply a bias-corrected Maximum Likelihood Estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing two important cases: the entropy $H(P) = \sum_{i = 1}^S -p_i \ln p_i$ and $F_α(P) = \sum_{i = 1}^S p_i^α,α>0$. We obtain the minimax $L_2$ rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity $n \asymp S/\ln S$ for entropy estimation. We also show that the sample complexity for estimating $F_α(P),0<α<1$ is $n\asymp S^{1/α}/ \ln S$, which can be achieved by our estimator but not the MLE. For $1<α<3/2$, we show the minimax $L_2$ rate for estimating $F_α(P)$ is $(n\ln n)^{-2(α-1)}$ regardless of the alphabet size, while the $L_2$ rate for the MLE is $n^{-2(α-1)}$. For all the above cases, the behavior of the minimax rate-optimal estimators with $n$ samples is essentially that of the MLE with $n\ln n$ samples. We highlight the practical advantages of our schemes for entropy and mutual information estimation. We demonstrate that our approach reduces running time and boosts the accuracy compared to existing various approaches. Moreover, we show that the mutual information estimator induced by our methodology leads to significant performance boosts over the Chow--Liu algorithm in learning graphical models.

I. INTRODUCTION AND MAIN RESULTS

The paper develops minimax rate-optimal estimators for functionals of high-dimensional discrete distributions with unknown support size. Its polynomial-approximation and bias-corrected MLE scheme achieves optimal rates for entropy and Fα(P), often matching the MLE with n ln n samples.

  • The paper studies estimating functionals of an unknown discrete distribution from n independent samples when the support size S is unknown and may be comparable to n.
  • The approach treats nonsmooth and smooth regions separately, using unbiased estimation of best polynomial approximations and a bias-corrected MLE, respectively.The procedure is applied coordinate-wise and the estimates are summed.
  • Entropy H(P): n ≫ S ln S is sufficient for consistent entropy estimation, while n ≲ S ln S leaves every estimator with maximum risk bounded away from zero.
  • Fα(P), 0 < α < 1: n ≫ S^(1/α) ln S is sufficient for consistent estimation of Fα(P) when 0 < α < 1, and n ≲ S^(1/α) ln S is insufficient for any estimator.
  • Fα(P), 1 < α < 3/2: (n ln n)^−2(α−1) is the minimax L2 convergence rate for Fα(P) when 1 < α < 3/2, regardless of support size.
  • For entropy and Fα(P) with 0 < α < 3/2, the proposed estimators essentially achieve with n samples the MLE performance obtained with n ln n samples, improving the dominating bias term.

C. Discussion of main results

The paper shows that functional estimation can be easier or harder than distribution estimation in high-dimensional settings, depending on the functional and parameter regime. Its estimators combine local polynomial approximation with smooth-regime estimation to attain minimax rates without knowing S.

  • n ≫ S/ln S samples are necessary and sufficient for consistently estimating entropy over all distributions supported on S elements.
  • Estimating entropy can be easier than estimating the corresponding distribution or data compression in the large-alphabet setting.
  • A sharp phase transition occurs at α = 1: consistent estimation requires super-linear sample size for α < 1 but constant-in-S sample size for α > 1.
  • For α ∈ (1, 3/2), the paper establishes a minimax result for Fα(P), while the MLE Hα(Pn) requires n ≳ S samples for estimating Hα(P).
  • The proposed estimators are conjectured to yield minimax rate-optimal estimators for Hα(P) for all α > 0 when formed from the corresponding Fα(P) estimators.
  • The general scheme reduces bias through local rather than global polynomial approximation, while measure concentration supports local treatment of nonsmooth regions.

C. Related work

The paper situates functional estimation across statistics and information-related fields, emphasizing finite-sample, high-dimensional settings where standard MLE intuition can fail. It motivates a general theory for improving functional estimators through approximation-based methods.

  • Information-theoretic functional estimation spans statistics, machine learning, physics, neuroscience, psychology, ecology, and related disciplines.
  • Functional estimation asks for an optimal estimate of a function of a finite-dimensional parameter, a problem distinct from estimating the parameter itself.
  • Classical asymptotic theory provides systematic estimators for finite-dimensional parameters, but finite-sample functional estimation remains challenging.
  • High-dimensional, finite-sample applications motivate analysis beyond asymptotic regimes with large sample sizes.
  • The MLE can be non-optimal for specific estimation problems, while shrinkage improves parameter risk by trading added bias for reduced variance.
  • The paper develops a general methodology using unbiased estimation of polynomial approximations, exploiting approximation theory for functional estimation.

E. Remaining content

The paper constructs estimators by separating nonsmooth and smooth probability regimes, then analyzes their bias and variance under Poissonization. The resulting scheme combines polynomial approximation with bias-corrected likelihood estimation.

  • Estimator construction: The estimator uses independent sample splits to decide whether each coordinate belongs to the nonsmooth or smooth regime.
  • Estimator construction: For 0 < α < 1, interpolation makes the upper-region estimator smooth near zero, where the unmodified estimator would be unbounded.
  • Entropy estimator: For entropy, a 3-order polynomial approximation over [0, ln n/n] has an expectation close to −p ln p, whereas the MLE plug-in is far from it in the illustrated setting.
  • Estimator analysis: The analysis divides coordinates into probability regimes and bounds the bias and variance of the corresponding estimator components.
  • Estimator analysis: For 1 < α < 3/2, the stated bound includes a term of order (n ln n)^−2(α−1).

IV. MINIMAX LOWER BOUNDS FOR ESTIMATING Fα(P), 0 < α < 3/2

The paper establishes minimax lower bounds using two complementary hypothesis-testing tools. Le Cam’s two-point method handles fixed alternatives, while fuzzy hypotheses use prior distributions and marginal indistinguishability.

  • Le Cam’s two-point method gives a general minimax lower bound from two parameter values and their induced distributions.
  • The fuzzy-hypotheses method constructs two priors on the parameter space and compares the resulting marginal distributions of observations.
  • Total variation distance provides the concrete measure used to compare probability distributions in the lower-bound argument.

A. Minimax lower bound for Theorem 2 (Fα : 0 < α < 1)

For 0 < α < 1, the lower-bound proof constructs priors whose low-order moments agree while their functional values differ, making the hypotheses difficult to distinguish from samples.

  • The lower bound has two parts when 1/2 < α < 1, requiring separate treatment of the corresponding terms.
  • Two probability measures on [0,1] are chosen to share moments through order L while differing in expectations of x^α.
  • The prior measures are selected so their functional values are maximally separated subject to moment matching, making them difficult to distinguish from samples.
  • The construction scales the measures and forms product priors over coordinates of the probability vector.
  • The argument establishes the lower bound for F_α(P) by relating it to the corresponding transformed functional and applying the fuzzy-hypotheses lemma.
  • The proof applies Poissonized observations, controls the resulting marginal distributions, and transfers the lower bound to the Multinomial model.

B. Minimax lower bound for Theorem 4 (Fα : 1 < α < 3/2)

For 1 < α < 3/2, the lower-bound argument constructs carefully matched priors and transfers indistinguishability between Poissonized and Multinomial models to bound minimax risk.

  • Prior construction: Two probability measures on [η, 1] are constructed with controlled moment properties for the lower-bound argument.The construction uses an approximation-theoretic quantity measuring the uniform distance of x^β from degree-L polynomials.
  • Prior construction: The measures are extended to [0, 1] and transformed onto [0, M] while preserving the properties needed to construct product priors.The resulting product priors generate length-S parameter vectors that may be approximate rather than exact probability distributions before conditioning.
  • Poissonization: The proof reduces the Multinomial minimax risk to a Poissonized minimax risk through an equivalence lemma.The reduction is stated for any S, n, γ > 0 and 1 < α < 3/2.
  • Lower-bound scale: The argument specializes the construction to the scale S = m ln m and combines concentration bounds with the prior-equivalence lemma to complete the lower bound.The final parameter choices include logarithmic L and η determined by universal constants.
  • Indistinguishability: Total variation is bounded using the triangle inequality and data processing after converting approximate priors into valid priors by conditioning.The conditioning step follows the approach attributed to Wu and Yang.

V. EXPERIMENTS

The experiments compare the proposed estimator with established entropy estimators and evaluate theoretical convergence, practical accuracy, numerical stability, and efficiency. Along the scaling n = 10S/ln S, the proposed estimator is among the methods indicated to achieve the minimax rate.

  • Implementation: The implementation has linear complexity in sample size n and is independent of the support size.Best polynomial approximation is computed offline with the Remez algorithm before samples are observed.
  • Compared estimators: The study compares the proposed entropy estimator against MLE, Miller–Madow, jackknife, unseen, CAE, BUB, shrinkage, Dirichlet, Grassberger, and NSB estimators.Several comparison methods require the true support size S as input, while others have documented non-minimax behavior or numerical-stability issues.
  • Experimental design: The experiments assess estimator performance across distributions while also testing numerical stability, space efficiency, and time efficiency.The authors frame theory as necessary for distribution-robust guarantees, complementing simulation-based risk evaluation.
  • Convergence properties along n = c S: At n = 10S/ln S, the proposed estimator, Valiant and Valiant’s estimator, and BUB are identified as achieving the minimax rate among 12 estimators.The figure uses logarithmic scales for support size and empirical MSE; a small positive slope corresponds to exponential MSE growth.
  • Convergence properties along n = c S: The shrinkage estimator improves on MLE only near-uniform distributions and performs poorly under the experiment’s least-favorable-prior construction.The construction uses two priors, normalization into distributions, repeated sampling, and Monte Carlo averaging of empirical MSE.

C. Estimation of entropy

The section evaluates entropy estimators across data-rich and data-sparse regimes, emphasizing accuracy, runtime, mutual-information implications, and graphical-model performance.

  • 1) Data rich regime:: In the data-rich regime S ≪ n, our estimator and BUB perform well, whereas the MLE and estimator in exhibit large bias.For our estimator and BUB, variance dominates squared bias; for the MLE and, bias dominates MSE.
  • 1) Data rich regime:: 0.75s is our estimator’s runtime for 160 uniform-distribution simulations, versus 0.47s for the MLE, 186.72s for, and 32.97s for BUB.Similar runtime patterns hold for the Zipf distribution.
  • 2) Data sparse regime:: In sparse regimes S ≍ n or S ≫ n, the MLE remains far from the true entropy, while our estimator and perform well; BUB can have substantial bias.At n = 10000 for the uniform distribution, our estimator takes 0.71s, only 0.05s longer than the MLE, while remaining faster than the alternatives.
  • 2) Data sparse regime:: The MLE concentrates far from the true functional when support size is comparable to or exceeds observations, while alternative estimators have regime-specific weaknesses.BUB requires knowledge of S and lacks established worst-case guarantees in the cited discussion.
  • D. Estimation of mutual information: n ≍ S^2/ln S samples suffice for mutual-information estimation when both variables have alphabet size S, compared with n ≍ S^2 for the MLE.The paper applies its entropy estimator to construct an essentially minimax mutual-information estimator.
  • D. Estimation of mutual information: The mutual-information estimator is accurate for most support sizes and reduces simulation time to 1.98s, versus 128.13s for and 48.86s for BUB.The cited experiment reports a reduction in MSE from 0.01 to approximately half, with true mutual information about 0.4.
  • F. Application in learning graphical models: Replacing empirical mutual information in Chow–Liu with the paper’s estimator improves tree reconstruction in the reported experiments.The paper interprets Chow–Liu as plugging an estimated mutual information into the maximum-weight spanning-tree procedure.
  • F. Application in learning graphical models: After 6 × 10^3 samples, the modified Chow–Liu algorithm begins perfect reconstruction, while the original continues maximal failure until exceeding 47 × 10^3 samples.Both algorithms have wrong-edges-ratio 1 below 3 × 10^3 samples; the modified method therefore requires about eight times fewer samples in this experiment.

APPENDIX A AUXILIARY LEMMAS

The appendix collects auxiliary results supporting the minimax analysis, including polynomial-approximation properties, Poissonization relations, probability bounds, and distributional constructions.

  • Poissonization: The minimax risks under Poissonized and Multinomial models satisfy |F(P)|^2 ≤ R(S,n) ≤ 2R_P(S,n/2).This relation transfers bounds between the two sampling models.
  • Polynomial approximation: Best polynomial approximation errors for x^α are characterized through limits and norm bounds, including coefficients bounded by 2^3n.The appendix treats 0 < α < 1 and α > 0 approximation behavior using Bernstein-function quantities.
  • Approximation constants: The appendix introduces Bernstein-function and related asymptotic quantities that can be evaluated numerically using polynomial-approximation machinery.Chebfun is cited as a practical way to compute the relevant quantities.
  • Probability bounds: Auxiliary lemmas provide tail and moment bounds for Poisson and Binomial variables and variance identities used in estimator analysis.The listed results include Poisson moments and decompositions involving independent indicator variables.
  • Lower-bound arguments: The appendix develops lower-bound constructions using uniform distributions and binomial counts, with central-limit arguments controlling their behavior.These constructions support minimax-risk analysis for discrete-distribution functionals.

C. Proof of Lemma 2

The proof analyzes the estimator for x^α by separating small and moderate-to-large observations, using Taylor expansions, remainder bounds, and Poisson concentration.

  • Taylor expansion: For 1 < α < 3/2, the proof applies a Taylor expansion around p when p ≥ Δ and bounds the resulting remainder terms.The analysis separately controls cases based on the observed value x relative to p.
  • Derivative bounds: The estimator’s remainder representation uses fourth derivatives, requiring bounds on U_α^(4) and related derivatives over the relevant regimes.The proof partitions x into [0,t], (t,2t), and [2t,1].
  • Case analysis: The proof distinguishes 0 < α ≤ 1/2 from 1/2 < α < 1 when bounding approximation-related terms.This case split reflects different remainder behavior for the two ranges of α.
  • Final bound: For 1 < α < 3/2, the combined remainder estimates yield the displayed upper bound after substituting bounds for R_1 and R_2.The final step plugs the separately obtained estimates into the overall error decomposition.

D. Proof of Lemma 3

The proof for entropy uses a bias-corrected function, Taylor expansion, and regime-specific derivative and remainder bounds under Poisson sampling.

  • Taylor expansion: For p ≥ Δ, the proof expands U_H(x) around p and represents the error through Taylor remainder terms.The analysis then bounds the remainder separately over different ranges of x.
  • Regime decomposition: The function U_H is zero on [0,t] and equals the target function on [2t,1], simplifying derivative analysis outside the transition region.The interval (t,2t) receives separate derivative bounds.
  • Remainder control: The proof bounds expected remainder terms using Poisson moments, tail inequalities, and separate cases for observations below p/2.The resulting bounds combine contributions from R_1 and R_2.
  • Bias bound: The entropy estimator’s bias bound includes terms proportional to p/n^2, p^2/n^3, and (p ln(1/p)+2p)n^-c1/8.The displayed inequalities progressively simplify the expectation bound.
  • Variance and remainder bounds: The proof obtains analogous bounds for the two remainder components before combining them into the entropy error analysis.The argument also uses fourth-order Taylor terms and derivative estimates for the corrected function.

E. Proof of Lemma 4

The proof bounds bias and variance using Poisson properties and auxiliary lemmas, with the SK,H(x) case obtained analogously to SK,α(x).

  • Poisson moment-generating-function identities are used to bound the bias term.
  • The SK,H(x) proof follows the SK,α(x) argument after replacing α by 1 and using Lemma 20 instead of Lemma 19.
  • The variance analysis introduces auxiliary quantities and applies Lemma 17 and a stated inequality.

G. Proof of Lemma 6

The proof of Lemma 6 analyzes bias and variance across four ranges of p, separately bounding component terms before combining them into total bounds.

  • B1 is bounded by c3/(n ln n)^α in the analyzed cases.
  • Combining the component bounds yields an overall bound on |B(ξ)|.
  • The resulting rate expression includes the term (n ln n)^−α alongside additional n-dependent terms.
  • Four regimes partition the analysis according to p relative to 1/(n ln n) and Δ.

I. Proof of Lemma 10

The proof constructs two priors with matching moments, compares their induced marginal distributions, and combines expectation and variance bounds for the lower-bound argument.

  • Two prior distributions ν0 and ν1 are constructed using best polynomial approximation arguments for x^α on [0,1].
  • The expectation difference is decomposed into D1 and D2, whose bounds are combined.
  • Variance bounds use Lemma 17 and the Taylor expansion of e^−x.
  • The proof bounds total variation distance between the marginal distributions induced by the two priors.
  • Matching moments up to order d2 ln n enables the comparison of the two prior-induced expectations.

K. Proof of Lemma 13

The proof combines polynomial approximation, estimator risk reduction under Poissonization, and optimization of entropy-related expressions to establish the lemma’s bounds.

  • The approximation analysis uses the Ditzian-Totik modulus of smoothness and sets the approximation order proportional to L.
  • For sufficiently large universal D, the approximation bound follows from the condition 0 < 2β < 1.
  • Poissonization transfers a near-minimax Multinomial estimator to a Poisson model by conditioning on the observed sample count.
  • The transferred risk is bounded by a rescaled minimax risk, an exponential tail term, δ, and a residual term.
  • The expression Σ_i p_i(ln p_i − 1)^2 attains its maximum at the uniform distribution.
  • A Lagrangian calculation shows that an optimizing distribution’s components can take only two values.

C. Proof of Lemma 16

The proof develops bounds for minimax risks by relating Poissonized and multinomial models, then controls approximation errors through polynomial and smoothness arguments.

  • Model comparison: The minimax-risk analysis compares Poissonized and multinomial models using independent Poisson counts and conditioning on their total.For independent Z_i distributed as Poi(np_i), conditioning on the total count yields a multinomial sample.
  • Risk bounds: The Bayes risk is non-increasing with the sample size because an estimator using fewer observations can ignore later samples.The argument also bounds risk using the zero estimator and probability inequalities for Poisson variables.
  • Smoothness bounds: The approximation analysis applies modulus-of-smoothness inequalities to functions including y^(2α), with separate treatment for different α ranges.For 0 < α ≤ 1/2, the modulus satisfies ω(y^(2α), δ) ≤ δ^(2α), while the range 1 < α < 3/2 is handled separately.
  • Polynomial approximation: Best polynomial approximation errors are bounded through coefficient estimates involving Chebyshev polynomials on finite intervals.The coefficient bounds apply after transforming x^α or −x ln x into even polynomials on [−1,1].
  • Approximation degree: For 0 < α < 1, the polynomial degree is selected on the order of (n ln n)^α.The supplied bound states K_2α = c_3 (n ln n)^α.
  • Entropy approximation: The entropy approximation uses a rescaled interval and a best-polynomial approximation result for −x ln x to obtain a uniform bound.The construction defines x′ = x/(4Δ) and introduces a positive constant d controlling the approximation error.
Loading 1406.6956v5…