<p>An alternative proof:</p>

<p>Given that <span class="math-container">$\psi(p)=D_{KL}\left(p\,||q\,\right)$</span> is closed and convex we know that <span class="math-container">$\psi^{**}(p)=\psi(p)$</span>. </p>

<p>One proposes <span class="math-container">$\psi^{*}(\lambda)=\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)$</span>. </p>

<p>It is enough to show that <span class="math-container">$\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)$</span></p>

<p>First order conditions imply <span class="math-container">$p(x)=\frac{q(x)e^{\lambda_{x}}}{\sum_{x}q(x)e^{\lambda_{x}}}$</span>, substituting in the conjugate objective:</p>

<p><span class="math-container">$$
\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}
$$</span></p>

<p>Reference <a href="https://math.stackexchange.com/questions/2468515/how-to-prove-the-conjugate-of-the-conjugate-function-is-itself">https://math.stackexchange.com/questions/2468515/how-to-prove-the-conjugate-of-the-conjugate-function-is-itself</a>)</p>

CC BY-SA 4.0
2019-10-03T18:18:38.800Z
2019-10-03T18:18:38.800Z
nosferatttu
<p>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) &amp;= \sum_i{q_i e^{x_i + \lambda- 1 }x_i} - \sum_i{q_i e^{x_i+ \lambda-1 }(x_i+ \lambda-1)}  \\
&amp;= -(\lambda-1)\sum_i{q_ie^{x_i+ \lambda-1 }}  \\
&amp;= -(\lambda-1)\sum_i{p_i}\\
&amp;= -(\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$.</p>

CC BY-SA 3.0
2015-01-22T14:34:25.483Z
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
CC BY-SA 3.0
2015-01-23T23:53:55.517Z
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
CC BY-SA 3.0
2015-01-22T05:16:40.740Z
2015-01-22T09:25:38.970Z
2015-01-22T09:25:38.970Z
Sasho Nikolov
<p>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^*$.</p>

<p>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&lt;&lt; Q)  as 
$$D(P||Q)=\int_XdP \log\frac{dP}{dQ}.$$</p>

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

<it.information-theory><convex-optimization><convex-geometry>
A Question on Convex Conjugate Duality for KL Divergence
SAmath
# A Question on Convex Conjugate Duality for KL Divergence

(Asked by: username_0 on 2015-01-21)

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

**Tags:** it.information-theory, convex-optimization, convex-geometry


---

## 2 answers

### Answer by username_2 on 2015-01-22. Score: 11 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  

---

### Answer by username_1 on 2019-10-03. Score: 4

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>)


---

