Maximum Likelihood Estimation of Functionals of Discrete Distributions

Abstract

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\le \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 \ge 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.

27 pages, 1 figure, published in IEEE Transactions on Information Theory

References in corpus (6)

• Entropy inference and the James-Stein estimator, with application to nonlinear gene association networks
• Minimax Estimation of the $L_1$ Distance
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Minimax Rate-Optimal Estimation of Divergences between Discrete Distributions
• Beyond Maximum Likelihood: from Theory to Practice
• Estimation of KL Divergence: Optimal Minimax Rate

Cited by in corpus (24)

• Inhomogeneous Hypergraph Clustering with Applications
• Multivariate trace estimation in constant quantum depth
• Ensemble Estimation of Information Divergence
• On Estimation of $L_r$-Norms in Gaussian White Noise Models
• Finite-Sample Concentration of the Multinomial in Relative Entropy
• Importance of Small Probability Events in Big Data: Information Measures, Applications, and Challenges
• Distributed Simulation and Distributed Inference
• Polynomial methods in statistical inference: theory and practice
• Adaptive Estimation of Shannon Entropy
• Ensemble Estimation of Generalized Mutual Information with Applications to Genomics
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Concentration Inequalities for the Empirical Distribution
• Estimation of KL Divergence: Optimal Minimax Rate
• Chernoff-type Concentration of Empirical Probabilities in Relative Entropy
• On estimating the entropy of shallow circuit outputs
• Bias Correction with Jackknife, Bootstrap, and Taylor Series
• Entropy Rate Estimation for Markov Chains with Large State Space
• Time-Efficient Quantum Entropy Estimator via Samplizer
• Statistical Inference in the Differential Privacy Model
• Locally differentially private estimation of nonlinear functionals of discrete distributions
• Modeling Psychotherapy Dialogues with Kernelized Hashcode Representations: A Nonparametric Information-Theoretic Approach
• Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
• Minimax Optimal Additive Functional Estimation with Discrete Distribution
• Sharp Concentration Inequalities for the Centered Relative Entropy