Minimax Estimation of Functionals of Discrete Distributions

DOI10.1109/TIT.2015.2412945MaRDI QIDQ2978652zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jiantao Jiao, Kartik Venkat, Yanjun Han, Tsachy Weissman

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.6956

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Nonparametric estimation (62G05) Information theory (general) (94A15)

Abstract: 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)=su{m}_{i=1}^S-p_{i}ln{p}_i$ and $F_{a}lpha(P)=su{m}_{i=1}^S{p}_i^{a}lpha,alpha>0$. We obtain the minimax $L_2$ rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity $nasympS/lnS$ for entropy estimation. We also show that the sample complexity for estimating $F_{a}lpha(P),0<alpha<1$ is $nasymp{S}^{1/alpha}/lnS$, which can be achieved by our estimator but not the MLE. For $1<alpha<3/2$, we show the minimax $L_2$ rate for estimating $F_{a}lpha(P)$ is $(nlnn{)}^{-2(alpha-1)}$ regardless of the alphabet size, while the $L_2$ rate for the MLE is $n^{-2(alpha-1)}$. For all the above cases, the behavior of the minimax rate-optimal estimators with $n$ samples is essentially that of the MLE with $nlnn$ 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.

Cited in

(24)

• Optimal estimation of Schatten norms of a rectangular matrix
• Near-optimal estimation of the unseen under regularly varying tail populations
• Fisher-Pitman Permutation Tests Based on Nonparametric Poisson Mixtures with Application to Single Cell Genomics
• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• A method to find the minimax of functionals dependent on probability measures
• Minimum disparity estimators for discrete and continuous models.
• Estimation of Simultaneous Signals Using Absolute Inner Product with Applications to Integrative Genomics
• Optimal Estimation of Wasserstein Distance on a Tree With an Application to Microbiome Studies
• Optimal disclosure risk assessment
• Properties of Shannon and Rényi entropies of the Poisson distribution as the functions of intensity parameter
• On estimation of \(L_r\)-norms in Gaussian white noise models
• Two-stage algorithm for estimation of nonlinear functions of state vector in linear Gaussian continuous dynamical systems
• Minimax properties of Fréchet means of discretely sampled curves
• Sample complexity of the distinct elements problem
• Adversarial meta-learning of Gamma-minimax estimators that leverage prior knowledge
• Asymptotic properties of minimum \(S\)-divergence estimator for discrete models
• On estimation of nonsmooth functionals of sparse normal means
• Minimax Estimation of Discrete Distributions Under <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> Loss
• scientific article; zbMATH DE number 218926 (Why is no real title available?)
• Sparse signal detection in heteroscedastic Gaussian sequence models: sharp minimax rates
• Maximum Likelihood Estimation of Functionals of Discrete Distributions
• Mean-square estimation of nonlinear functionals via Kalman filtering
• Optimal rates of entropy estimation over Lipschitz balls
• Approximate profile maximum likelihood

This page was built for publication: Minimax Estimation of Functionals of Discrete Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978652)