1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

I found answer here. Basically, the "good looking" version of Hoeffding bound uses the inequality $D(p||q) \le (p-q)^2$ to "trim" the upper bound. One should keep in mind that $D(p||q)$ is actually more tighten although "bad looking".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.