Finite-sample concentration of the empirical relative entropy around its mean
share
In this note, we show that the relative entropy of an empirical distribution of n samples drawn from a set of size k with respect to the true underlying distribution is exponentially concentrated around its expectation, with central moment generating function bounded by that of a gamma distribution with shape 2k and rate n/2. This improves on recent work of Bhatt and Pensia (arXiv 2021) on the same problem, who showed such a similar bound with an additional polylogarithmic factor of k in the shape, and also confirms a recent conjecture of Mardia et al. (Information and Inference 2020). The proof proceeds by reducing the case k>3 of the multinomial distribution to the simpler case k=2 of the binomial, for which the desired bound follows from standard results on the concentration of the binomial.
READ FULL TEXT