A Question on Convex Conjugate Duality for KL Divergence

Question

The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as $$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the topological dual of $X$ and $\langle\cdot, \cdot\rangle$ is dual pairing between $X$ and $X^*$.

The relative entropy (aka Kullback-Leibler divergence) $D(\cdot||Q):\mathcal{P}(X)\mapsto \mathbb{R}^+$, is defined for two probability measures $P$ and $Q$ (P<< Q) as $$D(P||Q)=\int_XdP \log\frac{dP}{dQ}.$$

I have been trying to calculate the convex conjugate of map $P\mapsto D(P||Q)$ but I have failed. I know that the answer is $\log \mathbb{E}_{Q}[e^{f}]$ where $\mathbb{E}_Q[\cdot]$ is the expectation operator with respect to probability measure $Q$.

Answer 1

To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$ with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with the support of $q$. Then the conjugate is $$ f^*_q(x) = \sup_p\ \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}. $$ where the supremum is over the probability simplex $\{p\geq 0: \sum_i p_i = 1\}$. Since the simplex is compact and the function inside the supremum is continuous, the supremum is achieved at some $p$. Using Lagrange multipliers you get that for some real value $\lambda$ an optimal $p$ must satisfy $x_i - 1 - \log(p_i/q_i) = - \lambda$ for all $i$, which gives $p_i = q_ie^{x_i + \lambda-1 }$. Since $1 = \sum_i p_i$, we have $\lambda - 1 = -\log\left(\sum_i{q_i e^{x_i}}\right)$. Substituting, we get $$ \begin{align} f^*_q(x) &= \sum_i{q_i e^{x_i + \lambda- 1 }x_i} - \sum_i{q_i e^{x_i+ \lambda-1 }(x_i+ \lambda-1)} \\ &= -(\lambda-1)\sum_i{q_ie^{x_i+ \lambda-1 }} \\ &= -(\lambda-1)\sum_i{p_i}\\ &= -(\lambda-1) = \log\left(\sum_i{q_i e^{x_i}}\right), \end{align} $$ which is exactly the logarithm of the expectation of $e^{x_i}$ under $q$.

Answer 2

An alternative proof:

Given that $\psi(p)=D_{KL}\left(p\,||q\,\right)$ is closed and convex we know that $\psi^{**}(p)=\psi(p)$.

One proposes $\psi^{*}(\lambda)=\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)$.

It is enough to show that $\psi^{**}(p)=\sup_{\lambda}\{\lambda^{T}p-\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)\}=D_{KL}\left(p\,||q\,\right)=\psi(p)$

First order conditions imply $p(x)=\frac{q(x)e^{\lambda_{x}}}{\sum_{x}q(x)e^{\lambda_{x}}}$, substituting in the conjugate objective:

$$ \begin{equation} \psi^{**}(p) = \lambda^{T}p-\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)=\sum_{x}\lambda_{x}p(x)-\sum_{x}p(x)\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)\\ =\sum_{x}p(x)\log\left(\frac{e^{\lambda_{x}}}{\sum_{x}q(x)e^{\lambda_{x}}}\right) =\sum_{x}p(x)\log\left(\frac{q(x)}{q(x)}\frac{e^{\lambda_{x}}}{\sum_{x}q(x)e^{\lambda_{x}}}\right)\\ =\sum_{x}p(x)\log\left(\frac{p(x)}{q(x)}\right)=D_{KL}\left(p\,||q\,\right)=\psi(p) \end{equation} $$

Reference https://math.stackexchange.com/questions/2468515/how-to-prove-the-conjugate-of-the-conjugate-function-is-itself)