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

(29)

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

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)