TY - GEN

T1 - Estimation of KL divergence between large-alphabet distributions

AU - Bu, Yuheng

AU - Zou, Shaofeng

AU - Liang, Yingbin

AU - Veeravalli, Venugopal V.

N1 - Funding Information:
The work of Y. Bu and V. V. Veeravalli was supported by the Air Force Office of Scientific Research (AFOSR) under the Grant FA9550-10-1-0458, and by the National Science Foundation under Grant NSF 11-11342, through the University of Illinois at Urbana-Champaign. The work of S. Zou and Y. Liang was supported by an NSF CAREER Award under Grant CCF-10-26565
Publisher Copyright:
© 2016 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2016/8/10

Y1 - 2016/8/10

N2 - The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio F(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k V log2(F(k)) and n = ω(kF(k)). Furthermore, if F(k) ≥ log2k and log2(F(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k V log2(F(k)) and n = ω( kF(k)/log k).

AB - The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio F(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k V log2(F(k)) and n = ω(kF(k)). Furthermore, if F(k) ≥ log2k and log2(F(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k V log2(F(k)) and n = ω( kF(k)/log k).

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

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

U2 - 10.1109/ISIT.2016.7541473

DO - 10.1109/ISIT.2016.7541473

M3 - Conference contribution

AN - SCOPUS:84985993750

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1118

EP - 1122

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -