In some textbook the KL divergence shows up in the proof of Hoeffding's inequality (e.g., eq. (5) of this material). In contrary, most other textbooks seem not mention this fact. I know that KL divergence is essentially Bregman divergence, i.e., the difference between the true value of a convex function and tis locally linear approximation. But I have no idea why there is a place for KL divergence in Hoeffding's inequality? Any intuitively explanations?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I found answer here. Basically, the "good looking" version of Hoeffding bound uses the inequality $D(p\| q) \ge (p-q)^2$ to "trim" the upper bound. One should keep in mind that $D(p\| q)$ is actually tighter although "bad looking".
