5
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SAmath Jan 22 '15 at 14:34
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jan 23 '15 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.