$$

The information divergence¹ measures the information gained when going from a prior distribution $P$ to a posterior distribution $Q$, i.e. how much you learned if you believed something was distributed according to $P$ and now believe it is distribution $Q$ based on evidence. Concretely, it measures (the logarithm of) how much more “confident” you now are about your current beliefs:

$$\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right):=\underset{x\sim Q}{\mathrm{E}}[\log \frac{Q(x)}{P(x)}].$$

We can extend the notion to random variables:

$$\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]:=\underset{\mathit{x}\sim \left[{\mathit{X}}^{\prime }\right]}{\mathrm{E}}[\log \frac{\mathrm{Pr}[{\mathit{X}}^{\prime }=\mathit{x}]}{\mathrm{Pr}[\mathit{X}=\mathit{x}]}]$$

(note that this is only a function of the distributions of $\mathit{X}$ and ${\mathit{X}}^{\prime }$ seen separately; we’re not thinking of them as jointly distributed).

Interpretations

The information divergence can be understood in three main ways, as a measure of

• the information gained when updating from $P$ to $Q$,
• the specificity of draws from $Q$ compared to $P$,
• and the unlikelihood of $P$ as a model given that your observations suggest $Q$.

And all of these links ultimately rely on the fact that the information divergence adds up nicely if we compare several independent samples from both $P$ and $Q$. A good intuition is that as $n$ grows, $Q^n$ looks more and more like we just conditioned $P^n$ on some event of probability $\exp (-n\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right))$.

See Six (and a half) intuitions for KL divergence for more intuitions, in particular ones related to betting.

Information gained

The information divergence is the core of information theory because it defines what it means to gain information based on observations. In particular,

• the mutual information $\mathrm{I}[\mathit{X};\mathit{Y}]$ is the average information we gain about $\mathit{Y}$ when observing $\mathit{X}$ (and vice versa): $\mathrm{I}[\mathit{X};\mathit{Y}]=\mathrm{E}\left[\mathrm{D}\left[\begin{array}{c}\phantom{\left(\mathit{Y}|\mathit{X}\right)}\mathit{Y}|\mathit{X}\\ \\ \phantom{\left(\mathit{Y}\right)}\mathit{Y}\end{array}\right]\right]=\mathrm{E}\left[\mathrm{D}\left[\begin{array}{c}\phantom{\left(\mathit{X}|\mathit{Y}\right)}\mathit{X}|\mathit{Y}\\ \\ \phantom{\left(\mathit{X}\right)}\mathit{X}\end{array}\right]\right]$;
• and the entropy $\mathrm{H}[\mathit{X}]$ is the average information we gain about $\mathit{X}$ when observing it: $\mathrm{H}[\mathit{X}]=\mathrm{I}[\mathit{X};\mathit{X}]=\mathrm{E}\left[\mathrm{D}\left[\begin{array}{c}\phantom{\left(\mathit{X}|\mathit{X}\right)}\mathit{X}|\mathit{X}\\ \\ \phantom{\left(\mathit{X}\right)}\mathit{X}\end{array}\right]\right]=\mathrm{E}[\log \frac{1}{[\mathit{X}](\mathit{X})}]$.

Specificity of draws from $Q$

The prior $P$ should be thought of as a more uniform baseline, and the posterior $Q$ as taking more specific or weird values, and being the interesting object of study. In particular, the definition only makes sense if the support of $Q$ is contained in the support of $P$.

Asymptotic likelihood ratio

The information divergence $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ quantifies the typical likelihood ratio between $Q$ and $P$ for large samples of independent draws from $Q$. More precisely, for any fixed tolerance $\delta >0$, if you draw a sample $\mathit{S}\sim Q^n$, then we have

$$\log \frac{Q^n(\mathit{S})}{P^n(\mathit{S})}\in n(\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\pm o(1))$$

except with probability $\delta$.

In particular, this means that the information divergence measures the amount of selection pressure you typically need to pick out a sample that roughly looks like it came from $Q$ from $n$-samples that actually came from $P$ (here, “roughly” means we might give up on reproducing a $\delta$ part of the distribution of $Q^n$). If you want to match the distribution exactly, this is measured by max-divergence instead, no matter what $n$ is.

Entropy deficit

If $P$ is uniform over some sample space $\mathcal{X}$, then $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ measures the difference between the entropies $\mathrm{H}(P)-\mathrm{H}(Q)$. Since uniform distributions maximize entropy, this represents how much entropy $Q$ is potentially “missing out” on, i.e. its entropy deficit.

Unlikelihood of $P$

$\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ is the “amount of evidence against $P$” that you get per sample: it’s the amortized log-unlikelihood that a large sample from $P$ ends up empirically distributed in a way that looks exactly like $Q$. Indeed, suppose $P,Q$ are distributions over $[m]$ (and denoting $p_i:=P(i)$ and $q_i:=Q(i)$), then the probability that we draw $n$ samples from $P$ and each $i\in [m]$ appears $\approx q_{i}n$ times is roughly

$$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n}{\approx q_{1}n,\dots ,\approx q_{m}n})\prod p_i^{q_{i}n}& =\underset{\text{probability that a sample from }Q\text{ ends up looking like }Q}{\underbrace{(\genfrac{}{}{0ex}{}{n}{\approx q_{1}n,\dots ,\approx q_{m}n})\prod q_i^{q_{i}n}}}\prod {\left(\frac{p_i}{q_i}\right)}^{q_{i}n}\\ & \approx \prod {\left(\frac{p_i}{q_i}\right)}^{q_{i}n}\\ & =\exp (-\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)n).\end{array}$$

Hypothesis testing

As a consequence, there exists a test for “detecting “ based on a large enough number of samples, such that

• if the samples are from $Q$, the test comes up positive with high probability in $n$ (the test is sensitive),
• and if the samples are from $P$, the test comes up positive with probability at most $2^{-n(\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)-o(1))}$ (the test is extremely specific).²

So if the test comes up positive, the belief that the samples came from $P$ as opposed to $Q$ becomes extremely untenable as $n$ grows.

Learning theory: minimizing divergence maximizes likelihood of $P$

In learning theory, we can let $Q$ be the target real-world distribution, and $P$ be the distribution represented by a simplified generative model from a restricted class. Then, minimizing $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ corresponds to picking the model $P$ that minimizes the information we still have to learn per sample. Since $Q$ is fixed, this is equivalent to minimizing the cross-entropy $\mathrm{H}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$. #to-write actually that’s an interpretation for the cross entropy not the information div

In terms of dynamics, the model knows less than nature, so it starts out more uncertain, and therefore $P$ is generally more uniform, and gives fairly low probabilities to everything. Minimizing the information divergence $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ will incentivize $P$ to give higher probabilities to values that are frequent in $Q$.

If instead we define $Q$ to be uniform over the training data, then the $P$ that minimizes $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ is the maximum likelihood model.

#to-write explicitly model Q as P conditioned on E?

Properties

Nonnegativity

As a ratio divergence, it is always nonnegative, and is $0$ iff $P$ and $Q$ are identical.

Asymptotics

Using its nonnegative form, we get

$$\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)=\mathrm{\Theta }\left(\sum _x\{\begin{array}{ll}P(x){(\frac{Q(x)}{P(x)}-1)}^2& \text{if }\frac{Q(x)}{P(x)}\le O(1)\\ Q(x)\log \frac{Q(x)}{P(x)}& \text{otherwise}\end{array}\right)$$

(change $\sum _x$ to ${\int }_x$ if $P,Q$ are continuous probability distributions).

Additivity

Independent priors and posteriors

If the priors and posteriors are both product distributions, then the divergence can be decomposed:

$$\begin{array}{rl}\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{(Q_1\cdots Q_n)}{Q}_1\cdots Q_n}\\ \\ {\displaystyle \phantom{(P_1\cdots P_n)}{P}_1\cdots P_n}\end{array}\right)& =\underset{\mathit{x}\sim Q_1\cdots Q_n}{\mathrm{E}}[\log \frac{Q_1({\mathit{x}}_1)\cdots Q_n({\mathit{x}}_n)}{P_1({\mathit{x}}_1)\cdots P_n({\mathit{x}}_n)}]\\ & =\underset{\mathit{x}\sim Q_1\cdots Q_n}{\mathrm{E}}[\log \frac{Q_1({\mathit{x}}_1)}{P_1({\mathit{x}}_1)}+\cdots +\log \frac{Q_n({\mathit{x}}_n)}{P_n({\mathit{x}}_n)}]\\ & =\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q_1\right)}{Q}_1}\\ \\ {\displaystyle \phantom{\left(P_1\right)}{P}_1}\end{array}\right)+\cdots +\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q_n\right)}{Q}_n}\\ \\ {\displaystyle \phantom{\left(P_n\right)}{P}_n}\end{array}\right).\end{array}$$

This situation mostly occurs when we believe these $n$ values ${\mathit{x}}_1,\dots ,{\mathit{x}}_n$ are independent samples from an identical random process, and we want to update our belief about the random process but not about the values themselves. When that’s the case, the additivity simplifies to

$$\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q^n\right)}{Q}^n}\\ \\ {\displaystyle \phantom{\left(P^n\right)}{P}^n}\end{array}\right)=n\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right).$$

Independent priors

If the prior variables $\mathit{X}$ and $\mathit{Y}$ are independent, then we have superadditivity (this generalizes the superadditivity of entropy deficit):

$$\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right]\ge \mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]+\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right].$$

Intuitively, this is because you can notice more ways in which ${\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }$ differ from $\mathit{X},\mathit{Y}$ if you get to look at the together and cross-check. Formally, we have

$$\begin{array}{rl}& \mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right]-\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]-\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right]\\ & =\underset{(x,y)\sim ({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathrm{E}}\left[\frac{\mathrm{Pr}[{\mathit{X}}^{\prime }=x\wedge {\mathit{Y}}^{\prime }=y]\mathrm{Pr}[\mathit{X}=x]\mathrm{Pr}[\mathit{Y}=y]}{\mathrm{Pr}[\mathit{X}=x\wedge \mathit{Y}=y]\mathrm{Pr}[{\mathit{X}}^{\prime }=x]\mathrm{Pr}[{\mathit{Y}}^{\prime }=y]}\right]\\ & =\underset{(x,y)\sim ({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathrm{E}}\left[\frac{\mathrm{Pr}[{\mathit{X}}^{\prime }=x\wedge {\mathit{Y}}^{\prime }=y]}{\mathrm{Pr}[{\mathit{X}}^{\prime }=x]\mathrm{Pr}[{\mathit{Y}}^{\prime }=y]}\right]\\ & =\mathrm{I}[{\mathit{X}}^{\prime };{\mathit{Y}}^{\prime }]\\ & \ge 0.\end{array}$$

I’m not sure about the case when ${\mathit{X}}^{\prime }$ and ${\mathit{Y}}^{\prime }$ are independent, but it seems less natural anyway: why would the posterior be independent if the prior isn’t?

#to-write

• also rewrite in distribution form?
• no actually maybe it’s better to write it like $\mathrm{D}\left[\begin{array}{c}\phantom{\left({(\mathit{X},\mathit{Y})|}_{\mathit{E}}\right)}{(\mathit{X},\mathit{Y})|}_{\mathit{E}}\\ \\ \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}\end{array}\right]$?
• ohh hold on this is where “total correlation” comes in right?
  • can you also write that one as a sum of mutual information? or of interaction informations?
    • is it the sum of all the interaction informations

    • is I[X1,X2] + I[X3;X2

      X1] + I[X4;X3

      X1,X2] etc?

  • ==okay this is highly relevant to my plight with the small-read local lemma!==
• also explain typical situation: were from a common process but now have observed something about the values in aggregate
• link to the information theoretic proof of the Chernoff bound

General case

In general, though, the quantities $\mathrm{D}\left[\begin{array}{c}\phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }\\ \\ \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}\end{array}\right]$ and $\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }\\ \\ \phantom{\left(\mathit{X}\right)}\mathit{X}\end{array}\right]+\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }\\ \\ \phantom{\left(\mathit{Y}\right)}\mathit{Y}\end{array}\right]$ are not comparable: information divergence is neither subadditive nor superadditive. For example, even when $\mathit{X}$ and $\mathit{Y}$ are independent, we can have

$$\{\begin{array}{rl}& \mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]=\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]=0\\ & \mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right]>0.\end{array}$$

On the other hand, by the section on conditional divergence below, we know that $\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }\\ \\ \phantom{\left(\mathit{X}\right)}\mathit{X}\end{array}\right],\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }\\ \\ \phantom{\left(\mathit{Y}\right)}\mathit{Y}\end{array}\right]\le \mathrm{D}\left[\begin{array}{c}\phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }\\ \\ \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}\end{array}\right]$, so

$$\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]+\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right]\le 2\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right],$$

and the second example below approximately saturates this bound.³

#figure redo the figure with the new notation

Triangle inequality

Sadly, the information divergence doesn’t satisfy the triangle inequality. In general, $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)+\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)$ can be much smaller than $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(P\right)}P\end{array}\right)$. In fact, we can make $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ while keeping $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)+\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)$ arbitrarily small by arbitrarily large by zooming into a value from $P$ to $Q$ and again from $Q$ to $R$ while taking care to keep it just small enough that it doesn’t get noticed in $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ or $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)$.

Some representative examples:

• “zoom regime”:
  • example 1
    • if the distributions are
      • $P$ uniform over $[D]$
      • $Q$ gives $\frac{1}{\log D}$ probability to the value $1$ and is otherwise uniform
      • $R$ is $1$ deterministically
    • then
      • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)\le \frac{1}{\log D}\log \left(\frac{D}{\log D}\right)\le 1$
      • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)=\log \log D$
      • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(P\right)}P\end{array}\right)=\log D$
  • example 2 (even worse)
    • if the distributions are
      • $P:=\mathcal{B}\left(\frac{1}{\exp \exp \mathrm{D}}\right)$
      • $Q:=\mathcal{B}\left(\frac{1}{\exp D}\right)$
      • $R:=\mathcal{B}\left(\frac{1}{D}\right)$
    • then
      • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ and $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)$ are both $\le 1$
      • but $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)\ge \exp \mathrm{\Omega }\left(\mathrm{D}\right)$
• “tweak regime”:
  • if $P:=B\left(\frac{1}{2}\right)$, $Q:=B\left(\frac{1+ϵ}{2}\right)$, $R:=B\left(\frac{1+2ϵ}{2}\right)$
  • then
    • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)\sim \mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(Q\right)}Q\end{array}\right)\sim \frac{{ϵ}^2}{2}$
    • $\mathrm{D}\left(\begin{array}{c}\phantom{\left(R\right)}R\\ \\ \phantom{\left(P\right)}P\end{array}\right)\sim 2{ϵ}^2$

#to-think I think in general, for any distributions $P$ and $R$, there is a distribution $Q$ such that

$$\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(R\right)}R}\\ \\ {\displaystyle \phantom{\left(Q\right)}Q}\end{array}\right)\le (1-\mathrm{\Omega }(1))\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(R\right)}R}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right).$$

Minimization

Information projection: minimizing over $Q$

Minimizing $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ over $Q$ is called information projection or mode seeking. We can rewrite it as

$$\underset{Q}{min}\underset{\text{try to hit frequent values under }P}{\underbrace{\underset{\mathit{x}\sim Q}{\mathrm{E}}[\log \frac{1}{P(\mathit{x})}]}}-\underset{\text{try to be broad}}{\underbrace{\mathrm{H}(Q)}}.$$

That is, $Q$ has to trade-off between hitting the most frequent values of $\mathit{x}$ under $P$ and still being as broad as possible. If $Q$ is unconstrained, then the optimum is $Q=P$.

More generally,

• the expression $\log \frac{1}{P(x)}$ doesn’t have to correspond to an actual distribution: we can let it be any energy function $E(x)$
• and we can weight the entropy maximization term by an “temperature” $T$,

in which case the problem becomes

$$\underset{Q}{min}\underset{\text{try to hit low energy values}}{\underbrace{\underset{\mathit{x}\sim Q}{\mathrm{E}}[E(\mathit{x})]}}-\underset{\text{try to be broad}}{\underbrace{T\mathrm{H}(Q)}}.$$

That is, $Q$ tries to hit the values with the lowest energy, but the higher the temperature $T$ is, the more important the entropy will be, and thus the more uncertain $Q$ will remain. This expression is sometimes called the Helmholtz free energy, and the optimum is given by the Boltzmann distribution $Q(x)\propto \exp (-\frac{E(x)}{T})$, since that’s precisely the distribution $P$ that would have given this minimization problem (up to constants).

#to-write

• link to Variational representations#Information divergence
• generalize this optimization pattern (keeps popping up and almost magical, see lee--entropy-opt-1.pdf how magical it is that the density takes a simple form, completely unaffected by actual values)

Moment projection: minimizing over $P$

Minimizing $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ over $P$ is called moment projection or mode covering. Since $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)=\mathrm{H}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)-\mathrm{H}(Q)$ and $Q$ is fixed, this is equivalent to minimizing the cross-entropy $\mathrm{H}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$. See Cross-entropy#Minimization.

Special cases

Binary divergence

Let

$$D\left(\begin{array}{c}{\displaystyle \phantom{\left(q\right)}q}\\ \\ {\displaystyle \phantom{\left(p\right)}p}\end{array}\right):=q\log \frac{q}{p}+(1-q)\log \frac{1-q}{1-p}$$

be the divergence between two Bernoullis $B(q)$ and $B(p)$.

Just like the general case, $D\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)$ is nonnegative with $D\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)=0$ iff $q=p$, and strictly convex over $[0,1{]}^2$. More precisely,

$$\frac{d^2}{d{q}^2}D\left(\begin{array}{c}{\displaystyle \phantom{\left(q\right)}q}\\ \\ {\displaystyle \phantom{\left(p\right)}p}\end{array}\right)=\frac{1}{q(1-q)}.$$

Assuming wlog that $p\le 1/2$, the asymptotics are

$$D\left(\begin{array}{c}{\displaystyle \phantom{\left(q\right)}q}\\ \\ {\displaystyle \phantom{\left(p\right)}p}\end{array}\right)=\{\begin{array}{ll}\mathrm{\Theta }\left(p{(\frac{q}{p}-1)}^2\right)& \text{if }0\le q\le 2p\\ \mathrm{\Theta }(q\log \frac{q}{p})& \text{if }q\ge 2p\text{,}\end{array}$$

(where the asymptotic constant is $\frac{1}{2}$ when $q\to p$). In particular, if $p=\frac{1}{2}$ (unbiased) and $q=\frac{1+\rho }{2}$ (bias $\rho$), we have $D\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)=\mathrm{\Theta }\left({\rho }^2\right)$.

#figure

#to-write

• expected score for logarithmic scoring rule
• full second derivative matrix
• $\mathrm{D}\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)\ge 2(q-p{)}^2$ (I believe? yup seems right since the second derivative is $\ge 4$)

Normals

#to-write

Conditional divergence

Similar to entropy (but unlike most ratio divergences), we can define the conditional information divergence by taking an average of the divergences of the conditional distributions:

$$\begin{array}{rl}\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }\right)}{\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}|\mathit{X}\right)}\mathit{Y}|\mathit{X}}\end{array}\right]:=& \underset{x\sim {\mathit{X}}^{\prime }}{\mathrm{E}}\left[\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({{\mathit{Y}}^{\prime }|}_{{\mathit{X}}^{\prime }=x}\right)}{{\mathit{Y}}^{\prime }|}_{{\mathit{X}}^{\prime }=x}}\\ \\ {\displaystyle \phantom{\left({\mathit{Y}|}_{\mathit{X}=x}\right)}{\mathit{Y}|}_{\mathit{X}=x}}\end{array}\right]\right]\\ =& \underset{(x,y)\sim ({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathrm{E}}[\log \frac{\mathrm{Pr}[{\mathit{Y}}^{\prime }=y\mid {\mathit{X}}^{\prime }=x]}{\mathrm{Pr}[\mathit{Y}=y\mid \mathit{X}=x]}],\end{array}$$

where ${\mathit{Y}|}_{\mathit{X}=x}$ denotes the random variable obtained by conditioning $\mathit{Y}$ on $\mathit{X}=x$.

Chain rule

Similar to conditional entropy, this gives a chain rule:

$$\begin{array}{rl}\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right]& =\underset{(x,y)\sim ({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathrm{E}}[\log \frac{\mathrm{Pr}[{\mathit{X}}^{\prime }=x\wedge {\mathit{Y}}^{\prime }=y]}{\mathrm{Pr}[\mathit{X}=x\wedge \mathit{Y}=y]}]\\ & =\underset{(x,y)\sim ({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathrm{E}}[\log \frac{\mathrm{Pr}[{\mathit{X}}^{\prime }=x]\mathrm{Pr}[{\mathit{Y}}^{\prime }=y\mid {\mathit{X}}^{\prime }=x]}{\mathrm{Pr}[\mathit{X}=x]\mathrm{Pr}[\mathit{Y}=y\mid \mathit{X}=x]}]\\ & =\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{X}}^{\prime }\right)}{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{X}\right)}\mathit{X}}\end{array}\right]+\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }\right)}{\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}|\mathit{X}\right)}\mathit{Y}|\mathit{X}}\end{array}\right],\end{array}$$

which immediately shows that adding data can only increase the divergence.

Mixtures and convexity

Since information divergence is neither subadditive nor superadditive, $\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }\right)}{\mathit{Y}}^{\prime }|{\mathit{X}}^{\prime }\\ \\ \phantom{\left(\mathit{Y}|\mathit{X}\right)}\mathit{Y}|\mathit{X}\end{array}\right]$ is sometimes bigger and sometimes smaller than $\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }\\ \\ \phantom{\left(\mathit{Y}\right)}\mathit{Y}\end{array}\right]$. However, like any ratio divergence when $\mathit{X}$ and ${\mathit{X}}^{\prime }$ are the same variable, we have

$$\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }\right)}{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right]\le \mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{(\mathit{X},{\mathit{Y}}^{\prime })}\mathit{X},{\mathit{Y}}^{\prime }}\\ \\ {\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\end{array}\right]=\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}}^{\prime }|\mathit{X}\right)}{\mathit{Y}}^{\prime }|\mathit{X}}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}|\mathit{X}\right)}\mathit{Y}|\mathit{X}}\end{array}\right].$$

That is, conditioning by the same variable can only increase the divergence, which is equivalent to saying that the information divergence is convex.

See also

• Data processing inequalities
• Variational representations#Information divergence

1. also known as Kullback–Leibler divergence and relative entropy ↩

2. Intuitively, this is because a typical sample $x_1,\dots ,x_n$ from $Q$ is about $2^{\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)n}$ times more likely according to $Q$ than $P$, so the set of values on which the test has to come up positive in order to have decent sensitivity will have very small weight $\approx 2^{-\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)n}$ when measured according to $P$. ↩

3. And maybe it even saturates it optimally as a function of $\mathrm{D}\left[\begin{array}{c}\phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }\\ \\ \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}\end{array}\right]$? #to-think ↩