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 $\widehat{p}$, with probability at least $δ$, $\text{KL}(p \| \widehat{p}) \geq C\max\{K,\ln(K)\ln(1/δ) \}/n $, where $n$ is the sample size and $C > 0$ is a constant. We introduce a computationally efficient estimator $p^{\text{OTB}}$, based on Online to Batch conversion and suffix averaging, and show that with probability at least $1 - δ$ $\text{KL}(p \| \widehat{p}) \leq C(K\log(\log(K)) + \ln(K)\ln(1/δ)) /n$. Furthermore, we also show that with sufficiently many observations relative to $\log(1/δ)$, the maximum likelihood estimator $\bar{p}$ guarantees that with probability at least $1-δ$ $$ 1/6 χ^2(\bar{p}\|p) \leq 1/4 χ^2(p\|\bar{p}) \leq \text{KL}(p|\bar{p}) \leq C(K + \log(1/δ))/n\,, $$ where $χ^2$ denotes the $χ^2$-divergence.