Finite-Sample Concentration of the Multinomial in Relative Entropy
Finite-Sample Concentration of the Multinomial in Relative Entropy
复制标题
DOI：
10.1109/tit.2020.2996134
复制
发表时间：
2019-04
影响因子：
2.5
通讯作者：
R. Agrawal
中科院分区：
文献类型：
--
作者：
R. Agrawal
我们证明了在一个k的有限字母表上的分布P（即多项式分布）的n个独立样本的经验分布与P本身之间的Kullback-Leibler散度（相对熵）的矩母函数不大于形状为k - 1且速率为n的伽玛分布的矩母函数。由此产生的指数浓度不等式变得有意义（小于1）当散度$\vareps $大于$（k-1）/n$时，而标准的类型绑定方法需要$\vareps> \frac {1}{n} \cdot \log {\binom {n+k-1}{k-1}} \geq（k-1）/n \cdot \log（1 + n/（k-1））$，从而在标准参数范围内节省了一个阶数$\log（n/k）$的因子，其中$n\gg k$。因此，我们还获得了经验散度（相当于离散似然比统计量）的所有矩的有限样本界，这些矩在其渐近值的常数因子（取决于矩）范围内。我们的证明通过简单简化到二进制字母表（即二项分布）的$k = 2$情况来进行，并且具有$k = 2$情况下的改进直接转化为一般$k$的改进的性质。特别是，我们猜想的二项式矩生成函数，将几乎关闭我们的有限样本界和渐近矩生成函数的Wilks定理（不适用于有限样本）之间的二次差距的约束。
We show that the moment generating function of the Kullback–Leibler divergence (relative entropy) between the empirical distribution of $n$ independent samples from a distribution $P$ over a finite alphabet of size $k$ (i.e. a multinomial distribution) and $P$ itself is no more than that of a gamma distribution with shape $k - 1$ and rate $n$ . The resulting exponential concentration inequality becomes meaningful (less than 1) when the divergence $\varepsilon $ is larger than $(k-1)/n$ , whereas the standard method of types bound requires $\varepsilon > \frac {1}{n} \cdot \log {\binom {n+k-1}{k-1}} \geq (k-1)/n \cdot \log (1 + n/(k-1))$ , thus saving a factor of order $\log (n/k)$ in the standard regime of parameters where $n\gg k$ . As a consequence, we also obtain finite-sample bounds on all the moments of the empirical divergence (equivalently, the discrete likelihood-ratio statistic), which are within constant factors (depending on the moment) of their asymptotic values. Our proof proceeds via a simple reduction to the case $k = 2$ of a binary alphabet (i.e. a binomial distribution), and has the property that improvements in the case of $k = 2$ directly translate to improvements for general $k$ . In particular, we conjecture a bound on the binomial moment generating function that would almost close the quadratic gap between our finite-sample bound and the asymptotic moment generating function bound from Wilks’ theorem (which does not hold for finite samples).