$H(p) \le H(q) + KL(p, q)$?

Question

Let $H(p) = \sum_i p_i\log\frac{1}{p_i}$ be the entropy of $p$ and $KL(p, q) = \sum_i p_i\log\frac{p_i}{q_i}$ be the KL divergence between $p$ and $q$. Does it hold that $H(p) \le H(q) + KL(p, q)$?

If this is not true, can we bound $H(p)$ using $H(q)$ and $KL(p, q)$ in certain form?

Edit 1: The motivation of this problem is this. Suppose that we are a bunch of data points as features (say $\{x_1, \dots, x_m\}$). And we have different distributions of labels over them. Say the first distribution is $q$. We use $q$ for training, and somehow we achieved Bayes optimal classifier. The loss of this classifier is $H(q)$.

Now say the second distribution is $p$. We know that the Bayesian optimal classifier over $p$ achieves loss $H(p)$.

Now I want to capture what is the difference between these two optimal classifiers over $p$ and $q$? There are two natural ways to capture this:

1. $H(p) - H(q)$. This simply measures the absolute performance difference (namely if Bayes optimal classifier over $q$ is doing well, would the Bayes optimal classifier over $p$, possibly different though, also doing well). This boils down to exactly measure the difference of entropy of $p$ and $q$.

2. $KL(p, q)$. This arises if we apply cross entropy to $p$ and $q$, $\ell(p, q) = H(p) + KL(p, q)$. Which is about what happens if we actually use $q$ to predict $p$. In this case $KL(p, q)$ captures the divergence.

I basically want to ask if these 2 are related.

Answer 1

There are already nice negative answers by Steve and Rémi Peyre. In the comments, user111 mentioned this post by David Reeb who gives a bound on the difference of entropies in terms of the KL-divergence when $p$ and $q$ are probability distributions on a finite set. I want to mention two other such bounds.

Suppose that $p$ and $q$ are distributions on a finite set $X$. Let \begin{align} \|p-q\| &:= \frac{1}{2}\sum_{i\in X}|p_i-q_i|=\sup_{A\subseteq X}\big|p(A)-q(A)\big| \end{align} be the total variation distance between $p$ and $q$.

Bound 1: \begin{align} \big|H(p)-H(q)\big| &\leq \sqrt{2 KL(p,q)}\,\log\left[\frac{|X|}{\sqrt{2 KL(p,q)}}\right] \;, \end{align} provided that $\|p-q\|\leq\frac{1}{4}$.

Bound 2: \begin{align} \big|H(p)-H(q)\big| &\leq H\left(\sqrt{\frac{1}{2}KL(p,q)}\right) + \sqrt{\frac{1}{2}KL(p,q)}\log(|X|-1) \;, \end{align} provided that $\|p-q\|\leq\frac{1}{2}$, where $H(\cdot)$ on the right-hand side is the binary entropy function.

Both are based on Pinsker's inequality (Lemma 11.6.1 of the book of Cover and Thomas, 2nd edition), \begin{align} \|p-q\| &\leq \sqrt{\frac{1}{2}KL(p,q)} \;. \end{align} For Bound 1, we use Theorem 17.3.3 of Cover and Thomas, which gives the bound \begin{align} \big|H(p)-H(q)\big| &\leq 2\|p-q\|\log\frac{|X|}{2\|p-q\|} \end{align} when $\|p-q\|\leq\frac{1}{4}$. For Bound 2, we instead use the bound \begin{align} \big|H(p)-H(q)\big| &\leq H(\|p-q\|) + \|p-q\|\log(|X|-1) \end{align} discussed in this post, which is valid when $\|p-q\|\leq\frac{1}{2}$.

I believe that Bound 2 is the sharpest of all three.

Answer 2

No, there is no hope of getting something of this kind. Consider the probability distribution $p$ on $\mathbf{N} \setminus \{0, 1\}$ defined by $p(n) := Z_p^{-1} n^{-1} \log^{-3/2} n$; and likewise $q(n) := Z_q^{-1} n^{-1} \log^{-3} n$. Then $H(p) = \infty$, but $H(q)$, $\mathit{KL}(p, q)$ and $\mathit{KL}(q, p)$ all are finite…

Answer 3

Just a partial answer, but the proposed inequality doesn't hold.

Take $p = [0.2, 0.8], q = [0.1, 0.9]$.

Then $H(p) = 0.2 \log(5) + 0.8 \log(1/0.8) \approx 0.5$,

$H(q) = 0.1 \log(10) + 0.9 \log(1/0.9) \approx 0.33$

and $KL(p, q) = 0.2 \log(2) + 0.8 \log(0.8/0.9) \approx 0.04$.