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 -