Estimation of KL Divergence: Optimal Minimax Rate
Estimation of KL Divergence: Optimal Minimax Rate
复制标题
DOI：
10.1109/tit.2018.2805844
复制
发表时间：
2018-04-01
影响因子：
2.5
通讯作者：
Veeravalli, Venugopal V.
中科院分区：
文献类型：
--
作者：
Bu, Yuheng;Zou, Shaofeng;Veeravalli, Venugopal V.
研究了两个未知分布P和Q之间的Kullback-Leibler散度D（P平行于Q）的估计问题，假设分布的字母表大小k可以无限大.该估计基于从P中抽取的m个独立样本和从Q中抽取的n个独立样本。它首先表明，不存在任何一致的估计，保证渐近小的最坏情况下的二次风险的所有对分布的集合。进一步考虑了一个包含分布对的约束集，其密度比由函数f（k）限定。提出了一种增广插入估计器，证明了当m和n分别超过常数因子k和kf（k）时，其最坏情况下的二次风险在常数因子（（k/m）+（kf（k）/n））（2）+（log（2）f（k）/m）+（f（k）/n）之内.当m和n分别超过常数因子k/log（k）和kf（k）/log k时，极小极大二次风险被刻画在常数因子（（k/（mlog k））+（kf（k）/（nlog k）（2）+（log（2）f（k）/m）+（f（k）/n）之内.最小最大二次风险的下界的特点是采用广义Le Cam的方法。一个极小极大最优估计，然后构造采用多项式逼近和插件的方法。
The problem of estimating the Kullback-Leibler divergence D(P parallel to 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) + (k f(k)/n))(2) + (log(2)f (k)/m) + (f (k)/n), if m and n exceed a constant factor of k and k f (k), respectively. Moreover, the minimax quadratic risk is characterized to be within a constant factor of ((k/(mlog k))+(k f (k)/(n log k)))(2) + (log(2)f (k)/m)+(f (k)/n), if m and n exceed a constant factor of k/log(k) and k f (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.