TY - JOUR

T1 - Estimation of KL Divergence

T2 - Optimal Minimax Rate

AU - Bu, Yuheng

AU - Zou, Shaofeng

AU - Liang, Yingbin

AU - Veeravalli, Venugopal V.

N1 - Funding Information:
Manuscript received September 14, 2016; revised April 19, 2017 and February 4, 2018; accepted February 5, 2018. Date of publication February 13, 2018; date of current version March 15, 2018. Y. Bu and V. V. Veeravalli were supported by National Science Foundation under Grant NSF 11-11342 and Grant 1617789. S. Zou was supported by the Air Force Office of Scientific Research under Grant FA 9550-16-1-0077. Y. Liang was supported in part by the Air Force Office of Scientific Research under Grant FA 9550-16-1-0077, in part by National Science Foundation under Grant CCF-1801855, and in part by DARPA FunLoL Program. This paper was presented at the 2016 International Symposium on Information Theory [1]. (Yuheng Bu and Shaofeng Zou contributed equally to this work.) Y. Bu, S. Zou, and V. V. Veeravalli are with the Coordinated Science Laboratory, ECE Department, University of Illinois at Urbana–Champaign, Urbana, IL 61801 USA (e-mail: bu3@illinois.edu; szou3@illinois.edu; vvv@illinois.edu).
Publisher Copyright:
© 2018 IEEE.

PY - 2018/4

Y1 - 2018/4

N2 - The problem of estimating the Kullback-Leibler divergence D(P||Q) between two unknown distributions P and Q is studied, under the assumption that the alphabet size k of the distributions can scale to infinity. The estimation is based on m independent samples drawn from P and n independent samples drawn from Q. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function f(k) is further considered. An augmented plug-in estimator is proposed, and its worst case quadratic risk is shown to be within a constant factor of ((k/m)+(kf(k)/n))2+(log2f(k)/m)+(f(k)/n), if m and n exceed a constant factor of k and kf(k), respectively. Moreover, the minimax quadratic risk is characterized to be within a constant factor of ((k/(m log k))+(kf(k)/(n log k)))2+(log2f(k)/m)+(f(k)/n), if m and n exceed a constant factor of k/log(k) and kf(k)/log k, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.

AB - The problem of estimating the Kullback-Leibler divergence D(P||Q) between two unknown distributions P and Q is studied, under the assumption that the alphabet size k of the distributions can scale to infinity. The estimation is based on m independent samples drawn from P and n independent samples drawn from Q. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function f(k) is further considered. An augmented plug-in estimator is proposed, and its worst case quadratic risk is shown to be within a constant factor of ((k/m)+(kf(k)/n))2+(log2f(k)/m)+(f(k)/n), if m and n exceed a constant factor of k and kf(k), respectively. Moreover, the minimax quadratic risk is characterized to be within a constant factor of ((k/(m log k))+(kf(k)/(n log k)))2+(log2f(k)/m)+(f(k)/n), if m and n exceed a constant factor of k/log(k) and kf(k)/log k, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.

KW - Functional approximation

KW - mean squared error

KW - minimax lower bound

KW - plug-in estimator

KW - polynomial approximation

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

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

U2 - 10.1109/TIT.2018.2805844

DO - 10.1109/TIT.2018.2805844

M3 - Article

AN - SCOPUS:85042062309

SN - 0018-9448

VL - 64

SP - 2648

EP - 2674

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 4

ER -