3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Are you sure you want to write you inequality with $\mathit{KL}(p, q)$, not $\mathit{KL}(q, p)$? In information theory, $H(q) + \mathit{KL}(q, p)$ has a nice meaning (it is the cost to describe $q$ when using a description method optimized for $p$); while, as far as I know, $H(q) + \mathit{KL}(p, q)$ does not mean anything interesting… $\endgroup$ Dec 30 '19 at 15:11
  • 2
    $\begingroup$ A similar question (with answer in continuous and discrete cases) appears here. $\endgroup$
    – user111
    Dec 30 '19 at 15:14
  • 1
    $\begingroup$ @RémiPeyre: Replied with motivations on my side. $\endgroup$
    – Xi Wu
    Dec 31 '19 at 17:00
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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…

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