Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability

We consider the problem of estimating a discrete distribution p with support of size K and provide both upper and lower bounds with high probability in KL divergence. We prove that in the worst case, for any estimator p, with probability at least $δ$, KL(p \| p) ≥ Cmax,ln(K)ln(1/δ) \/n, where n is the sample size and $C > 0$ is a constant. We introduce a computationally efficient estimator pOTB, based on Online to Batch conversion and suffix averaging, and show that with probability at least $1 - δ$ KL(p \| p) ≤ C(Klog(log(K)) + ln(K)ln(1/δ)) /n. Furthermore, we also show that with sufficiently many observations relative to log(1/δ), the maximum likelihood estimator p̄ guarantees that with probability at least $1-δ$ 1/6 χ²(p̄\|p) ≤ 1/4 χ²(p\|p̄) ≤ KL(p|p̄) ≤ C(K + log(1/δ))/n\,, where χ² denotes the χ²-divergence.