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.



$H(p) \le H(q) + KL(p, q)$?
There are already nice negative answers by [Steve](https://mathoverflow.net/a/349379/23297) and [Rémi Peyre](https://mathoverflow.net/a/349383/23297). In the comments, user111 mentioned [this post](https://mathoverflow.net/a/133774/23297) 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](https://en.wikipedia.org/wiki/Pinsker%27s_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](https://mathoverflow.net/q/310689/23297), which is valid when $\|p-q\|\leq\frac{1}{2}$.


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


