1
$\begingroup$

Let $P$ be a distribution on an alphabet of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ via $n$ i.i.d samples $a_1,\ldots,a_n \sim P$, i.e $\hat{P}_n := (1/n)\sum_{i=1}^n\delta_{a_i}$.

Question

Does there exist a non-asymptotic bound of the form $\text{Proba}(KL(P \|\hat{P}_n) \ge \epsilon) \le (n + 1)^ke^{-\epsilon n}$ ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I'm a bit confused -- this is exactly Sanov's theorem, no? I find it as Theorem 11.4.1 of Cover and Thomas, and earlier in that chapter. (I guess some places only mention the asymptotic version?) $\endgroup$
    – usul
    Commented Apr 17, 2019 at 19:49
  • $\begingroup$ @usul Thanks for the input. (1) Part of my frustration is that I haven't seen any non-asymptotic version of the theorem anywhere. So I'd be more than appreciate any good reference on the subject. (2) I really mean $KL(P\|\hat{P}_n)$. Just to be clear, $KL(p\|q) := \int \log(\frac{dp}{dq})dp$ is $p \ll q$, and $KL(p\|q) := \infty$ otherwise. $\endgroup$
    – dohmatob
    Commented Apr 17, 2019 at 22:04
  • $\begingroup$ Indeed a non-asymptotic inequality for $Proba(KL(\hat{P}_n\|P) \ge \epsilon)$ is given and proven in Theorem 11.2.1 of Cover and Thomas staff.ustc.edu.cn/~cgong821/…. $\endgroup$
    – dohmatob
    Commented Apr 17, 2019 at 22:43
  • $\begingroup$ Still I'm interested in $KL(P\|\hat{P}_n)$. $\endgroup$
    – dohmatob
    Commented Apr 17, 2019 at 22:49
  • $\begingroup$ Ah great, thanks. OK, this is going to be really problematic because if you don't sample some $x$, then $\hat{P}(x) = 0$ and your KL-divergence is infinite, but $P$ can put arbitrarily small probability on some $x$ requiring arbitrarily many samples to avoid this...(right?) $\endgroup$
    – usul
    Commented Apr 17, 2019 at 23:46

0

Reset to default

You must log in to answer this question.