$H(p) \le H(q) + KL(p, q)$? 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:


*

*$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$.

*$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.
 A: 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…
A: 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.
A: 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$.
