TY - GEN

T1 - Minimax rate-optimal estimation of KL divergence between discrete distributions

AU - Han, Yanjun

AU - Jiao, Jiantao

AU - Weissman, Tsachy

N1 - Publisher Copyright:
© 2016 IEICE.

PY - 2017/2/2

Y1 - 2017/2/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85015186940&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015186940&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85015186940

T3 - Proceedings of 2016 International Symposium on Information Theory and Its Applications, ISITA 2016

SP - 256

EP - 260

BT - Proceedings of 2016 International Symposium on Information Theory and Its Applications, ISITA 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 3rd International Symposium on Information Theory and Its Applications, ISITA 2016

Y2 - 30 October 2016 through 2 November 2016

ER -