$$

In the formula for ratio divergences

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

since the function $f$ is convex, it can be lower bounded by the tangent at any point $t^{\ast }$:

$$f(t)\ge f(t^{\ast })-f^{\prime }(t)(t-t^{\ast })$$

or equivalently, using the convex dual of $f$, it can be lower bounded by a tangent of any slope $a$:

$$f(t)\ge at-f^{\ast }(a),$$

with equality whenever $a=f^{\prime }(t)$.

Plugging this into $D^f\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$, we can even pick different values of $a$ depending on $\mathit{x}$, which gives us a very general family of lower bounds on the ratio divergence:

$$\begin{array}{rl}{D}^f\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)& =\underset{\mathit{x}\sim P}{\mathrm{E}}\left[f\left(\frac{Q(\mathit{x})}{P(\mathit{x})}\right)\right]\\ & \ge \underset{\mathit{x}\sim P}{\mathrm{E}}[a(x)\frac{Q(\mathit{x})}{P(\mathit{x})}-f^{\ast }(a(\mathit{x}))]\\ & =\underset{\mathit{x}\sim Q}{\mathrm{E}}[a(\mathit{x})]-\underset{\mathit{x}\sim P}{\mathrm{E}}[f^{\ast }(a(\mathit{x}))]\end{array}$$

with equality when $a(x)=f^{\prime }\left(\frac{Q(x)}{P(x)}\right)$ for all $x$.

Rearranging, this becomes

$$\underset{\mathit{x}\sim Q}{\mathrm{E}}[a(\mathit{x})]\le \underset{\mathit{x}\sim P}{\mathrm{E}}[f^{\ast }(a(\mathit{x}))]+D^f\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right).$$

That is, when $D^f\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ is not too large, it gives us a generic upper bound on expectations over $Q$ in terms of some other expectation over $P$!

Total variation distance

Things are particularly nice in the case of total variation distance:

$$d_{\mathrm{TV}}(P,Q)=\underset{\mathit{x}\sim P}{\mathrm{E}}\left[{(\frac{Q(\mathit{x})}{P(\mathit{x})}-1)}^{+}\right].$$

Indeed, $f(t)=(t-1{)}^{+}$ has the tangents

$$f(t)\ge a(t-1)$$

for any $a\in [0,1]$, though in general only two of them are interesting:

• $f(t)\ge 0$ for slope $a=0$,
• $f(t)\ge t-1$ for slope $a=1$.

Therefore we can write it as

$$d_{\mathrm{TV}}(P,Q)=\underset{a(\cdot )\in \{0,1\}}{max}(\underset{\mathit{x}\sim Q}{\mathrm{E}}[a(\mathit{x})]-\underset{\mathit{x}\sim P}{\mathrm{E}}[a(\mathit{x})]),$$

or rephrasing $a(\cdot )$ as the indicator of a set $A$,

$$d_{\mathrm{TV}}(P,Q)=\underset{A}{max}(Q(A)-P(A)).$$

That is, the total variation distance is the maximum difference between the probabilities that $P$ and $Q$ give to some event.

Information divergence

For the information divergence $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$, we will in general be able to get a better bound if we consider all possible tilts of $f$ around $t=1$

$$f(t):=t\log t+(r-1)(t-1).$$

Indeed, we know that the inequality will be tight iff

$$a=f^{\prime }(t)=\log t+r⟺e^a\propto t,$$

so $a(x)$ can be interpreted of as the logarithm of an (unnormalized) density function, with optimality (for some $r$) when $e^{a(x)}\propto \frac{Q(x)}{P(x)}$ for all $x$.

The convex dual of $f$ at the slope $a=f^{\prime }(t)$ is:

$$\begin{array}{rl}{f}^{\ast }(a)& =at-t\log t-(r-1)(t-1)\\ & =at-t(a-r)-(r-1)(t-1)\\ & =t+r-1\\ & =e^{a-r}+r-1,\end{array}$$

so

$$\begin{array}{rl}\underset{\mathit{x}\sim Q}{\mathrm{E}}[a(\mathit{x})]& \le \underset{\mathit{x}\sim P}{\mathrm{E}}[e^{a(\mathit{x})-r}+r-1]+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\\ & =\frac{{\mathrm{E}}_{\mathit{x}\sim P}\left[e^{a(\mathit{x})}\right]}{e^r}+r-1+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right),\end{array}$$

and optimizing over $r$ requires $e^r={\mathrm{E}}_{\mathit{x}\sim P}\left[e^{a(\mathit{x})}\right]$ (i.e. $e^r$ is the normalization constant of $e^a$ as a density), which gives

$$\begin{array}{rl}\underset{\mathit{x}\sim Q}{\mathrm{E}}[a(\mathit{x})]& \le r+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\\ & =\log \underset{\mathit{x}\sim P}{\mathrm{E}}[\exp a(\mathit{x})]+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right),\end{array}$$

or more simply, interpreting $a(\mathit{x})$ as a random variable $\mathit{a}$,¹

$$\underset{Q}{\mathrm{E}}[\mathit{a}]\le \log \underset{P}{\mathrm{E}}[\exp \mathit{a}]+\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right).$$

Choosing the base

The above is² actually true for any base of the logarithm and exponentiation, as long as $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ is also expressed over that same base:

$$\begin{array}{rl}\underset{Q}{\mathrm{E}}[\mathit{a}]& \le {\log }_b\underset{P}{\mathrm{E}}\left[b^{\mathit{a}}\right]+\underset{\text{``}\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)\text{ in base }b\text{''}}{\underbrace{\underset{Q}{\mathrm{E}}[{\log }_b\frac{Q(\mathit{x})}{P(\mathit{x})}]}}\\ & =\frac{\ln \stackrel{\text{moment-generating function}}{\overbrace{{\mathrm{E}}_P\left[e^{s\mathit{a}}\right]}}+\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)}{s},\end{array}$$

for $s:=\ln b$.

That is, when $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ is small, we can bound the expected value of $\mathit{a}$ over $Q$ by its moment-generating function over $P$. The smaller $s$ is, the more $\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ gets amplified, so it is generally best to choose one of the largest possible values of $s$ for which the moment-generating function doesn’t blow up.

#to-write

• special case where $P$ is uniform
• see it as generalization of union bound:
  • when you show that ${\mathrm{Pr}}_{\mathit{x}}[\mathrm{\exists }\theta :B_{\mathit{x}}(\theta )]\le \frac{1}{3}$ (say), usually it’s because you pick $\theta$ in a way that depends on $\mathit{x}$ and want to take a worst-case view, so what you really care about is $\mathrm{\forall }f:{\mathrm{Pr}}_{\mathit{x}}[B_{\mathit{x}}(f(\mathit{x}))]$, in which case the union bound becomes $\mathrm{\forall }f:{\mathrm{Pr}}_{\mathit{x}}[B_{\mathit{x}}(f(\mathit{x}))]\le \left|\mathrm{\Theta }\right|{\mathrm{Pr}}_{\begin{array}{c}\mathit{x}\\ \mathit{\theta }\sim \mathcal{U}\left(\mathrm{\Theta }\right)\end{array}}[B_{\mathit{x}}(\mathit{\theta })]$?
    • actually i’m not sure that this one is an axis on which DV generalizes the union bound
  • ok and i guess it’s mostly smoothing it in another axis, which is from $\{0,1\}$ values to arbitrary real values, i.e. instead of $\mathrm{Pr}[\mathrm{\exists }\theta :B(\theta )]$, you want to bound ${\mathrm{E}}_{\mathit{x}}[\underset{\theta }{max}{B}_{\mathit{x}}(\theta )]\le \left|\mathrm{\Theta }\right|{\mathrm{E}}_{\mathit{x},\mathit{\theta }}\left[B_{\mathit{x}}\left(\mathit{\theta }\right)\right]$
  • … in addition to generalizing by making the prior non-uniform
    • note: the most obvious result that generalizes in this way uses max-divergence instead
      • and as compensation for that sharp penalty, it doesn’t have to be about exponentials
      • i.e. just get $E_Q\left[\mathit{a}\right]\le D_{\mathrm{\infty }}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right){\mathrm{E}}_P\left[\mathit{a}\right]$
      • #to-think can you use this to make the variational representations of power divergences make sense in general?
        • actually maybe this is all cleaner if e.g. you look at the posterior form?
        • do they all take the form $g({\mathrm{E}}_Q[\mathit{a}])\le D_{\alpha }\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right){\mathrm{E}}_P[g(\mathit{a})]$ for some function $g$?
• ELBO is just taking ${\mathrm{E}}_Q[\mathit{a}]\le \log {\mathrm{E}}_P[\exp \mathit{a}]+\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ and plugging in log likelihood?
  • yuppp: $\log p(x)={\mathrm{E}}_{p(\mathit{z})}\left[p\left(x\right|\mathit{z})\right]\ge {\mathrm{E}}_{q(\mathit{z})}[\log p\left(x\right|\mathit{z})]-\mathrm{D}\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)$
  • or (for SUB) rearranging, $\log \frac{1}{{\mathrm{E}}_P[\exp \mathit{a}]}\le \mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)-{\mathrm{E}}_Q\left[\mathit{a}\right]$
    • so $\log \frac{1}{p(x)}=\log \frac{1}{{\mathrm{E}}_{p(\mathit{z})}\left[p\left(x\right|\mathit{z})\right]}\le \mathrm{D}\left(\begin{array}{c}\phantom{\left(q\right)}q\\ \\ \phantom{\left(p\right)}p\end{array}\right)+{\mathrm{E}}_{q(\mathit{z})}[\log \frac{1}{P\left(x\right|\mathit{z})}]$
• and could maybe present it alternatively as ${\mathrm{E}}_Q[\log \mathit{A}]\le \log {\mathrm{E}}_P\left[\mathit{A}\right]+\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$
  • and/or ${\mathrm{E}}_Q[\log \frac{1}{\mathit{L}}]\ge \log \frac{1}{{\mathrm{E}}_P\left[\mathit{L}\right]}+\mathrm{D}\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$
  • and/or ${\mathrm{E}}_P\left[\mathit{L}\right]\ge \frac{\exp {\mathrm{E}}_Q[\log \frac{1}{\mathit{L}}]}{D_1\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)}$
    • (which is worse than if we had $\ge \frac{{\mathrm{E}}_Q\left[\mathit{L}\right]}{D_1\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)}$)
  • (but the current formulation still seems good as the main one; e.g. for PAC-Bayes bounds $\mathit{a}$ is indeed the core thing)

#to-think

• make it make a little more sense to you that you’re adding KL (which is dimensionless) to a dimensional quantity?
  • maybe that one’s really just beacuse you should be using the non-logged version of KL, i.e. $\exp \left({\mathrm{E}}_Q\left[\mathit{a}\right]\right)\le D_1\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right){\mathrm{E}}_P[\exp \mathit{a}]$
    • (where $D_1$ is defined as in Power entropies and divergences)

${\chi }^2$-divergence

We get

$${(\underset{Q}{\mathrm{E}}[\mathit{a}]-\underset{P}{\mathrm{E}}[\mathit{a}])}^2\le {\chi }^2\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\underset{P}{\mathrm{Var}}[\mathit{a}],$$

but I haven’t yet found an intuitive proof for this.

#to-think is something like ${\mathrm{E}}_Q[\mathit{a}{]}^2\le {\chi }^2\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right){\mathrm{E}}_P[{\mathit{a}}^2]$ true?

• then let $a(\mathit{x}):=b(\mathit{x})-{\mathrm{E}}_P[b(\mathit{x})]$, giving
  • $\mathrm{LHS}={\mathrm{E}}_{\mathit{x}\sim Q}{[a(\mathit{x})]}^2={\mathrm{E}}_{\mathit{x}\sim Q}{[b(\mathit{x})-{\mathrm{E}}_{{\mathit{x}}^{\prime }\sim P}\left[{\mathit{x}}^{\prime }\right]]}^2={({\mathrm{E}}_Q[b(\mathit{x})]-{\mathrm{E}}_P[b(\mathit{x})])}^2$
  • $\mathrm{RHS}={\mathrm{E}}_{\mathit{x}\sim P}[b(\mathit{x})-{\mathrm{E}}_{{\mathit{x}}^{\prime }\sim P}[b({\mathit{x}}^{\prime })]]=\mathrm{Var}[b(\mathit{x})]$
  • ok nice that sounds very promising actually
  • and it suggests that a multiplicative version is cleaner in many cases?

As concentration bounds

These variational representations are in a sense a generalization of concentration bounds. Instead of only bounding the probability that $\mathit{a}$ exceeds a certain value, they bound ${\mathrm{E}}_Q[\mathit{a}]$ over any distribution $Q$ that is not too far from the prior $P$.

Formally, if we want to bound $p:={\mathrm{Pr}}_P[\mathit{a}\ge v]$ for some threshold $v$, we can let $Q$ be the conditional distribution ${P|}_{\cdot \ge v}$, which makes $D^f\left(\begin{array}{c}\phantom{\left(Q\right)}Q\\ \\ \phantom{\left(P\right)}P\end{array}\right)$ a (decreasing) function of $p$, and write

$$\begin{array}{rl}{D}^f\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)& \ge \underset{Q}{\mathrm{E}}\left[\mathit{a}\right]-\underset{P}{\mathrm{E}}[f^{\ast }(\mathit{a})]\\ & =\underset{P}{\mathrm{E}}\left[\mathit{a}\right|\mathit{a}\ge v]-\underset{P}{\mathrm{E}}[f^{\ast }(\mathit{a})]\\ & \ge v-\underset{P}{\mathrm{E}}[f^{\ast }(\mathit{a})],\end{array}$$

which then gives an upper bound on $p$.

Information divergence

We have

$$\begin{array}{rl}\log \frac{1}{p}& =\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\\ & \ge sv-\ln \underset{P}{\mathrm{E}}\left[e^{s\mathit{a}}\right],\end{array}$$

that is, for $\mathit{a}\sim P$,

$$\mathrm{Pr}[\mathit{a}\ge v]\le \frac{\mathrm{E}\left[e^{s\mathit{a}}\right]}{e^{sv}},$$

which is the moment-generating function method (also known as Chernoff bound).

${\chi }^2$-divergence

Let

$$\begin{array}{rl}\mu & :=\underset{P}{\mathrm{E}}[\mathit{a}]\\ {\sigma }^2& :=\underset{P}{\mathrm{Var}}[\mathit{a}]\end{array}$$

and let’s rewrite $v$ as $\mu +t\sigma$ for $t\ge 0$. Then we have

$$\begin{array}{rl}\frac{1}{p}-1& ={\chi }^2\left(\begin{array}{c}{\displaystyle \phantom{\left(Q\right)}Q}\\ \\ {\displaystyle \phantom{\left(P\right)}P}\end{array}\right)\\ & \ge \frac{{({\mathrm{E}}_Q[\mathit{a}]-{\mathrm{E}}_P[\mathit{a}])}^2}{{\mathrm{Var}}_P[\mathit{a}]}\\ & \ge \frac{{(v-\mu )}^2}{{\sigma }^2}\\ & =t^2,\end{array}$$

that is, for $\mathit{a}\sim P$,

$$\mathrm{Pr}[\mathit{a}\ge \mu +t\sigma ]\le \frac{1}{1+t^2},$$

which is Chebyshev’s inequality.

Total variation distance

This one requires a bit more adaptation (and because of this is perhaps more of a hairpull). We have

$$\begin{array}{rl}1-p& =d_{\mathrm{TV}}(P,Q)\\ & \ge \underset{x\sim Q}{\mathrm{E}}[a(x)]-\underset{x\sim P}{\mathrm{E}}[a(x)],\end{array}$$

but this only holds if $a(x)\in [0,1]$. So we perform the change of variables

$$a(x)\leftarrow \frac{min(a(x),v)}{v},$$

which means that for any $\mathit{a}\ge 0$ we have

$$\begin{array}{rl}1-p& \ge \underset{Q}{\mathrm{E}}\left[\frac{min(\mathit{a},v)}{v}\right]-\underset{P}{\mathrm{E}}\left[\frac{min(\mathit{a},v)}{v}\right]\\ & =1-\frac{{\mathrm{E}}_P[min(\mathit{a},v)]}{v}\\ & \ge 1-\frac{{\mathrm{E}}_P\left[\mathit{a}\right]}{v},\end{array}$$

so for $\mathit{a}\sim P$,

$$\mathrm{Pr}[\mathit{a}\ge v]\le \frac{\mathrm{E}[\mathit{a}]}{v},$$

which is Markov’s inequality.

See also

• Variational inference

#to-think are most/all of these basically versions of Hölder’s inequality, the same way that Cauchy–Schwarz inequality can be understood in terms of weighting one sequence by the other? see SRLL p.128

1. We can do slightly better in general by letting $a(\cdot )$ be the identity, so that the information divergence is that of $\mathit{a}$ itself and not done underlying variable $\mathit{x}$ (which is better by the data processing inequality for divergences. This is also why we can afford to be a bit sloppy about what exactly the subscripts mean in ${\mathrm{E}}_Q[\mathit{a}]$ and ${\mathrm{E}}_P[e^{\mathit{a}}]$. ↩

2. by the change of variables $a\leftarrow a\ln b$ ↩