Estimation of KL divergence between large-alphabet distributions

Yuheng Bu; Shaofeng Zou; Yingbin Liang; Venugopal V. Veeravalli

doi:10.1109/ISIT.2016.7541473

Estimation of KL divergence between large-alphabet distributions

Yuheng Bu, Shaofeng Zou, Yingbin Liang, Venugopal V. Veeravalli

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Scopus citations

Abstract

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 log²(F(k)) and n = ω(kF(k)). Furthermore, if F(k) ≥ log²k and log²(F(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k V log²(F(k)) and n = ω( kF(k)/log k).

Original language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1118-1122
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541473
State	Published - Aug 10 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2016.7541473

Fingerprint Dive into the research topics of 'Estimation of KL divergence between large-alphabet distributions'. Together they form a unique fingerprint.

Cite this

Bu, Y., Zou, S., Liang, Y., & Veeravalli, V. V. (2016). Estimation of KL divergence between large-alphabet distributions. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 1118-1122). [7541473] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541473

Estimation of KL divergence between large-alphabet distributions. / Bu, Yuheng; Zou, Shaofeng; Liang, Yingbin; Veeravalli, Venugopal V.

Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 1118-1122 7541473 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bu, Y, Zou, S, Liang, Y & Veeravalli, VV 2016, Estimation of KL divergence between large-alphabet distributions. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541473, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 1118-1122, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541473

Bu Y, Zou S, Liang Y, Veeravalli VV. Estimation of KL divergence between large-alphabet distributions. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc. 2016. p. 1118-1122. 7541473. (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2016.7541473

@inproceedings{625a42cc5a274dda93a6eef9bbab5e71,

title = "Estimation of KL divergence between large-alphabet distributions",

abstract = "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).",

author = "Yuheng Bu and Shaofeng Zou and Yingbin Liang and Veeravalli, {Venugopal V.}",

note = "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: {\textcopyright} 2016 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541473",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1118--1122",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

}

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 -