Let $\mu$ and $\lambda$ be probability measures on a measurable space $(X, \Sigma)$.
In my experience, the usual definition of the Kullback-Liebler divergence of $\mu$ with respect to $\lambda$ is
$$
\tag{1}
\label{kl def}
\operatorname{KL}(\mu \| \lambda)
= \begin{cases}
\int_X \log\left(\frac{d\mu}{d\lambda}\right) \, d\mu, & \text{if $\mu \ll \lambda$ and $\log\left(\frac{d\mu}{d\lambda}\right) \in L^1(\mu)$,} \\
\infty, & \text{otherwise.}
\end{cases}
$$
While reading some machine learning theory literature, I encountered the following inequality, attributed to Donsker and Varadhan, which is valid at least for bounded, $\Sigma$-measurable functions $\Phi : X \to \mathbb{R}$:
$$
\tag{2}
\label{kl ineq}
\int_X \Phi \, d\mu \leq \operatorname{KL}(\mu \| \lambda) + \log\int_X \exp(\Phi) \, d\lambda.
$$
This led me to a 1983 paper by Donsker and Varadhan (see References below), in which they define the entropy of $\mu$ with respect to $\lambda$ by
$$
\tag{3}
\label{dv def}
h(\lambda : \mu)
= \inf\left\{c \in \mathbb{R} : \int_X \Phi \, d\mu \leq c + \log\int_X \exp(\Phi) \, d\lambda
\quad\text{for all $\Phi \in \mathscr{B}(\Sigma)$}
\right\},
$$
where $\mathscr{B}(\Sigma)$ is the space of all bounded, $\Sigma$-measurable functions from $X$ to $\mathbb{R}$.
The paper makes several assertions about this definition.
For instance,
- If $X$ is a separable, completely metrizable space and $\Sigma$ is its Borel $\sigma$-algebra, then $\mathscr{B}(\Sigma)$ can be replaced by $C(X)$ in \eqref{dv def}, yielding the same infimum.
(Presumably $C(X)$ here is the space of continuous functions on $X$, but not all such functions are necessarily $\mu$-integrable, so maybe the space of compactly supported continuous functions is intended?) - If $X$ is a separable, completely metrizable space and $\Sigma$ is its Borel $\sigma$-algebra, then $h(\lambda : \mu)$ is lower semicontinuous in $\mu$ in the weak topology.
- (Theorem 2.1) $h(\lambda : \mu) = \operatorname{KL}(\mu \| \lambda)$ (i.e., \eqref{kl def} and \eqref{dv def} define the same quantity).
I'm most interested in the first and last items above, whose proofs can be apparently found in an earlier 1976 paper by Donsker and Varadhan (see References below).
However, I was unable to find anything resembling these results in that paper.
Questions
-
How can I prove the assertions about $h(\lambda : \mu)$ made in the 1983 Donsker-Varadhan paper? In particular, why is $h(\lambda : \mu) = \operatorname{KL}(\mu \| \lambda)$?
-
For which functions $\Phi$ does \eqref{kl ineq} hold? It certainly holds for all bounded, $\Sigma$-measurable functions by the definition of $h(\lambda:\mu)$, and it holds for non-negative, $\Sigma$-measurable functions by the monotone convergence theorem. Does it hold for all $\mu$-integrable functions?
-
The machine learning literature also uses the following representation of Kullback-Liebler divergence, which is also attributed to Donsker and Varadhan:
$$
\operatorname{KL}(\mu \| \lambda)
= \sup_{\Phi \in \mathcal{C}} \left(\int_X \Phi \, d\mu – \log\int_X \exp(\Phi) \, d\lambda\right),
$$
where $\mathcal{C}$ is a usually unspecified class of functions (presumably $\mathcal{C} = \mathscr{B}(\Sigma)$ works). This looks like a dual formulation of \eqref{dv def}, but I would appreciate a proof of this as well (in particular, the $\infty – \infty$ case may need to be addressed).
References
-
Donsker, M.D. and Varadhan, S.R.S. (1976), Asymptotic evaluation of certain Markov process expectations for large time—III. Comm. Pure Appl. Math., 29: 389-461. DOI
-
Donsker, M.D. and Varadhan, S.R.S. (1983), Asymptotic evaluation of certain markov process expectations for large time. IV. Comm. Pure Appl. Math., 36: 183-212. DOI
Best Answer
Let us first start with the KL-divergence. As you pointed out, $KL$ divergence has a useful property (which is an immediate consequence of Jensen's inequality) that $$KL(\mu||\lambda)\ge \left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\},$$ for every $\Phi$ bounded and measurable. This tells us that $$KL(\mu||\lambda)\ge\sup\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}.$$
Now, assume that $\frac{d\mu}{d\lambda}$ is bounded. Then, the equality in the above expression holds for $\Phi^*:=\log\frac{d\mu}{d\lambda}.$ This should be enough to convince one that $$KL(\mu||\lambda)=\sup\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}.$$
In the general case when $\frac{d\mu}{d\lambda}$ is not bounded, one can approximate $\frac{d\mu}{d\lambda}$ by the function bounded, measurable functions $\Phi_M$ which increase to $\frac{d\mu}{d\lambda}.$ This is standard measure-theoretic detail and I will omit it.
This formulation clearly is a dual formulation for $KL$-divergence. Note that $\Lambda(\Phi)=\left(\log\int exp(\Phi)d\lambda\right)$ is (more or less) the cumulant generating function of $\lambda.$ And, the above formulation gives the relative entropy as the dual of the cumulant generating function. One can also write the cumulant generating function $$\Lambda(\Phi)=\sup\left\{\int \Phi d\mu - KL(\mu||\lambda): \mu\in M_1(\Sigma)\right\}.$$
Coming to your definition of $h(\lambda:\mu).$ It is just a matter of re-writing, and one can see that
$$h(\lambda:\mu)=\sup\sup\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\},$$ which we have already shown equals $KL(\mu||\lambda).$ To see that $h$ is indeed written as the above sup, note that $\alpha=\sup\sup\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}$ is a valid choice of $c.$ And, any $c$ that can occur in your definition of $h$ must be satisfy $c\ge\sup\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}$.
Now, this also answers your question of why we can replace $B(\Sigma)$ by $C(X).$ All we need to guarantee is that every bounded measurable function can be approximated by continuous functions. There is one little caveat though, as you mentioned a continuous function need not be bounded and therefore potentially the supremum can become bigger if we take the sup over $C(X).$ This does not happen because the first inequality, I wrote above can be proved for any function. Actually, what follows from Jensen's inequality is that $\left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}-KL(\mu||\lambda)\le 0$ for any function. (One can convince oneself of this at the heuristic level, the rigorous proof would require a lot of book-keeping but can be done). Therefore, when we take the sup over $C(X)$ or $C_b(X).$
Lastly about $h(\lambda:\mu)$ being lower-semicontinuous. This is where it is best to work with $C_b(X)$ in the $\sup$ defining $h.$ If we work with $C_b(X)$ we immediately note that for a fixed $\Phi\in C_b(X)$ the functional $$\mu\mapsto \left\{\int \Phi d\mu-\log\int exp(\Phi)d\lambda\right\}$$ is continuous with respect to weak-convergence of probability measures. It follows that $h(\lambda:\mu)$ is the the $\sup$ of continuous functionals and hence must be lower-semicontinuous.