# A Question on Convex Conjugate Duality for KL Divergence

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

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

• thanks a lot for your answer. Just another question, do you know what space $x$ lives in, I mean, what is the dual space of probability simplex. – SAmath Jan 22 '15 at 14:34
• I don't understand the question. The simplex lives in a vector space and $x$ lives in the (topological) dual of that vector space. In the final dimensional case, which is the only thing I have talked about here, this is isomorphic to $\mathbb{R}^n$. I do not understand what you mean by the dual space of something which is not a vector space. – Sasho Nikolov Jan 23 '15 at 23:53

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