Maximum Likelihood Estimation of Functionals of Discrete Distributions

By Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman. 2014

112 citations recorded by the source corpus.

We consider the problem of estimating functionals of discrete distributions, and focus on a tight (up to universal multiplicative constants for each specific functional) 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 <italic>bias</italic>. We explicitly characterize the worst case squared error risk incurred by the maximum likelihood estimator (MLE) in estimating the Shannon entropy <inline-formula> <tex-math notation="LaTeX">$H(P) = \sum _{i = 1}^{S} -p_{i} \ln p_{i}$ </tex-math></inline-formula>, and the power sum <inline-formula> <tex-math notation="LaTeX">$F_\alpha (P) = \sum _{i = 1}^{S} p_{i}^\alpha ,\alpha >0$ </tex-math></inline-formula>, up to universal multiplicative constants for each fixed functional, for any alphabet size <inline-formula> <tex-math notation="LaTeX">$S\leq \infty $ </tex-math></inline-formula> and sample size <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> for which the risk may vanish. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have <inline-formula> <tex-math notation="LaTeX">$n \gg S$ </tex-math></inline-formula> observations for the MLE to be consistent. In addition, we establish that it is necessary and sufficient to consider <inline-formula> <tex-math notation="LaTeX">$n \gg S^{1/\alpha }$ </tex-math></inline-formula> samples for the MLE to consistently estimate <inline-formula> <tex-math notation="LaTeX">$F_\alpha (P), 0<\alpha <1$ </tex-math></inline-formula>. The minimax rate-optimal estimators for both problems require <inline-formula> <tex-math notation="LaTeX">$S/\ln S$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$S^{1/\alpha }/\ln S$ </tex-math></inline-formula> samples, which implies that the MLE has a strictly sub-optimal sample complexity. When <inline-formula> <tex-math notation="LaTeX">$1<\alpha <3/2$ </tex-math></inline-formula>, we show that the worst case squared error rate of convergence for the MLE is <inline-formula> <tex-math notation="LaTeX">$n^{-2(\alpha -1)}$ </tex-math></inline-formula> for infinite alphabet size, while the minimax squared error rate is <inline-formula> <tex-math notation="LaTeX">$(n\ln n)^{-2(\alpha -1)}$ </tex-math></inline-formula>. When <inline-formula> <tex-math notation="LaTeX">$\alpha \geq 3/2$ </tex-math></inline-formula>, the MLE achieves the minimax optimal rate <inline-formula> <tex-math notation="LaTeX">$n^{-1}$ </tex-math></inline-formula> regardless of the alphabet size. As an application of the general theory, we analyze the Dirichlet prior smoothing techniques for Shannon entropy estimation. In this context, one approach is to plug-in the Dirichlet prior smoothed distribution into the entropy functional, while the other one is to calculate the Bayes estimator for entropy under the Dirichlet prior for squared error, which is the conditional expectation. We show that in general such estimators do <italic>not</italic> improve over the maximum likelihood estimator. No matter how we tune the parameters in the Dirichlet prior, this approach cannot achieve the minimax rates in entropy estimation. The performance of the minimax rate-optimal estimator with <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> samples is essentially <italic>at least</italic> as good as that of Dirichlet smoothed entropy estimators with <inline-formula> <tex-math notation="LaTeX">$n\ln n$ </tex-math></inline-formula> samples.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Statistics and Probability

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 Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Estimating Mutual Information for Discrete-Continuous Mixtures (2017, background): “mutual information estimators, on both the theoretical as well as practical fronts [46, 31, 44, 45, 22, 19, 7, 15, 14, 17, 16].”
Estimating Renyi Entropy of Discrete Distributions (2014, result): “It follows that the power sum estimation results in [16] and [17] and the Rényi-entropy estimation results in this paper complement each other in several ways.”
Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation (2014, background): “Combining the above steps, our lower bound is proportional to the value of the following convex optimization problem (in fact, inﬁnite-dimensional linear programming): for some L ∈ N and λ > 1 depending on n and k .”
A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions (2017, background): “(Canonne, 2015) surveyed testing whether distributions have certain properties, and (Jiao et al., 2014) studied the performance of SML estimators for several properties.”