Minimax Rate-optimal Estimation of KL Divergence between Discrete Distributions

By Yanjun Han, Jiantao Jiao, Tsachy Weissman. 2016

44 citations recorded by the source corpus.

We refine the general methodology in [1] for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions with support size S comparable with the number of observations n. Specifically, we determine the "smooth" and "non-smooth" regimes based on the confidence set and the smoothness of the functional. In the "non-smooth" regime, we apply an unbiased estimator for a "suitable" polynomial approximation of the functional. In the "smooth" regime, we construct a bias corrected version of the Maximum Likelihood Estimator (MLE) based on Taylor expansion. We apply the general methodology to the problem of estimating the KL divergence between two discrete distributions from empirical data. We construct a minimax rate-optimal estimator which is adaptive in the sense that it does not require the knowledge of the support size nor the upper bound on the likelihood ratio. Moreover, the performance of the optimal estimator with n samples is essentially that of the MLE with n ln n samples, i.e., the effective sample size enlargement phenomenon holds.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal (2017, background): “The discrete case has been studied recently [28, 7].”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, background): “[20] J. Jiao, Y. Han, and T. Weissman, “Beyond maximum likelihood: Boosting the Chow-Liu algorithm for large alphabets,” in Signals, Systems and Computers, 2016 50th Asilomar Conference on.”