Minimax Estimation of Functionals of Discrete Distributions

DOI10.1109/TIT.2015.2412945zbMATH Open1359.62104DBLPjournals/tit/JiaoVHW15arXiv1406.6956OpenAlexW1989151402WikidataQ47555295 ScholiaQ47555295MaRDI QIDQ2978652FDOQ2978652

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)

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.

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)

Cited In (24)

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

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)