Minimax estimation of functionals of discrete distributions

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Jiantao Jiao, K. Venkat, Yanjun Han, T. Weissman
Journal/Conference Name I
Paper Category
Paper 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)= ∑ S i=1 − p i ln p i and F α (P)= ∑ S i=1 p α i ,α>0 . We obtain the minimax L 2 rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n≍S/lnS for entropy estimation. We also show that the sample complexity for estimating F α (P),0<α<1 is n≍ S 1/α /lnS , which can be achieved by our estimator but not the MLE. For 1<α<3/2 , we show the minimax L 2 rate for estimating F α (P) is (nlnn ) −2(α−1) regardless of the alphabet size, while the L 2 rate for the MLE is n −2(α−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.
Date of publication 2015
Code Programming Language Jupyter Notebook

Copyright Researcher 2022