Variational Representation for Kullback-Leibler Divergence

Question

In the book I'm currently studying, the KL Divergence is defined as follows:$$D(q||p) = qlog\frac{q}{p}+(1-q)log\frac{1-q}{1-p}$$ for $p,q\in(0,1).$

I want to convert this definition into a so-called variational representation:$$D(q||p) = \sup_{a,b\in \mathbf{R}}[aq+b(1-q)-log(e^ap+e^b(1-p))]$$

I think probably I should prove the two directions $\leq$ and $\geq$. I have proven the $\leq$ part. For the $\geq$ part, I guess I may need to use the concavity of $log(x)$ or convexity of $e^x$.

Thanks a lot for any thoughts. Much appreciated.

Answer 1

Note that $$ aq+b(1-q)-\log(e^ap+e^b(1-p)) = \log \left( \frac{e^{aq + b(1-q)}}{e^ap+e^b(1-p)}\right) = \log\left(\frac{e^{q(a-b)}}{(e^{(a-b)}-1)p + 1}\right) $$

So (as the other answer points out) the function value depends on $a,b$ only through the combination $a-b$. Note that this implies that the hessian will be degenerate; the maximum is attained anywhere on some line $a-b=c$. But we can use this fact and 1-variable calculus to continue. Set $$f(t)= \frac{e^{qt}}{(e^t-1)p+1}$$ Then $$f'(t) = \frac{e^{q t}\left(p(q-1) e^{t}-p q+q\right)}{\left(p\left(e^{t}-1\right)+1\right)^{2}} $$ and $$f'(t)=0 \iff e^t = \frac{q(1-p)}{p(q-1)} $$

$f''$ is a mess but you don't need it since for any $p,q\in(0,1)$, $f(t) \to 0$ as $t\to\infty$ since $e^{qt}$ loses to the $pe^t$, and also as $t\to-\infty$ since then the function is like $e^{qt}$. As $f\ge 0$, the unique critical point must be a maximum. A plot of $f$:

Answer 2

The partial derivatives of the right-hand side's expression with respect to $a$ and $b$ are $$q - \frac{pe^a}{pe^a + (1-p) e^b}$$ and $$1-q - \frac{(1-p) e^b}{pe^a + (1-p)e^b}.$$ These derivatives are zero when $$p(1-q) e^a = (1-p) q e^b$$ i.e. $$b-a = \log \frac{p(1-q)}{q(1-p)}.$$ You can actually show that the value of $aq+b(1-q) - \log(e^a p + e^b (1-p))$ depends only on the value of $b-a$, so any choice (such as $a = \log \frac{p}{q}$ and $b = \log \frac{1-q}{1-p}$) will work.