Proof of convexity with logs

I'm trying to prove the following result. Let $$p$$ be an input probability distribution and $$Q$$ be a transition matrix. $$q = Qp$$ is a valid output probability distribution. The components of $$p$$ and $$q$$ are given as $$p_i$$ and $$q_i$$ respectively.

For any $$p, p'$$, define

$$J(p, p') = -D(p||p') + \sum_ip_i\left(\sum_{j}Q_{ij}\log(Q_{ij})\right) - \sum_{j}q_j\log q'_j,$$

where $$q'_j = \sum_k Q_{jk}p'_k$$ and $$D(p||p') = \sum_i p_i\log \frac{p_i}{p'_i}$$, the divergence.

The claims are the following

1) $$J$$ is concave in both $$p$$ and $$p'$$. I can see this for $$p$$ quite easily and numerically, it seems to be true for $$p'$$ but how can I prove it? Somehow, I need to combine the concave term $$-D(p||p')$$ and the convex $$-\log$$ term together to make a concave function but I don't know how.

2) $$J(p, p') \leq I$$, where $$I$$ is the mutual information between probability distributions $$p$$ and $$q$$, maximized over all possible input distributions $$p$$. It is given by

$$I = \max_{p}\left[\sum_ip_i\left(\sum_{j}Q_{ij}\log(Q_{ij})\right) - \sum_{j}q_j\log q_j\right]$$

Again, I have verified this numerically over random choices of $$Q$$ but have no proof.

EDIT: For the concavity problem, it follows from what I posted before but is easier to analyze. We require the function

$$\sum_i p(i)\log p'(i) - \sum_j q_j\log q'(j)$$

is concave in $$p'$$ for any choice of stochastic matrix $$Q$$ that gives us $$q_k = \sum_j Q_{kl}p_l$$ and $$q'_k = \sum_j Q_{kl}p'_l$$.

• What are $\lambda$ and $\lambda’$? – David M. Mar 8 at 13:29
• @DavidM. sorry, my mistake with the notation. It was p and p' – user1936752 Mar 8 at 13:32

First, for convenience rewrite $$J(p,p')$$ as \begin{align} J(p,p') &= -D(p\Vert p')+\sum_{i}p_{i}\sum_{j}Q_{ij}\log\frac{Q_{ij}}{q_{j}}+\sum_{j}q_{j}\log\frac{q_{j}}{q'_{j}} \\ &= I({p})-\left[D(p\Vert p')-D(q\Vert q')\right]\\ & = I(p) - \Delta D(p\Vert p') \end{align} where I have used your definition of $$I(p)$$, and defined \begin{align} \Delta D(p\Vert p')= D(p\Vert p')-D(q\Vert q') \end{align}

$$\Delta D(p\Vert p')$$ reflects the "contraction" of Kullback-Leibler divergence between $$p$$ and $$p'$$ under the stochastic matrix $$Q$$. $$\Delta D$$ is convex in the first argument. To see why, consider any two distributions $$p$$ and $$\bar{p}$$, and define the convex mixture $$p^\alpha = (1-\alpha) p + \alpha \bar{p}$$. We will show convexity by demonstrating that the second derivative with respect to $$\alpha$$ is non-negative.

First, compute the first derivative w.r.t. $$\alpha$$ as \begin{align*} & {\textstyle \frac{d}{d\alpha}}\Delta D(p^{\alpha}\Vert q) ={\textstyle \frac{d}{d\alpha}}\left[\sum_{i}p_{i}^{\alpha}\log p_{i}^{\alpha}-\sum_{i}p_{i}^{\alpha}\sum_{j}Q_{ij}\log q_{j}^{\alpha}+\sum_{i}p_{i}^{\alpha}\sum_{j}Q_{ij}\log\frac{q_{j}'}{p'_{i}}\right]\\ & =\sum_{i}(\bar{p}_{i}-p_{i})\log p_{i}^{\alpha}-\sum_{i}(\bar{p}_{i}-p_{i})\sum_{j}Q_{ij}\log q_{j}^{\alpha}+\sum_{i}(\bar{p}_{i}-p_{i})\sum_{j}Q_{ij}\log\frac{q_{j}'}{p'_{i}} \end{align*} Then, we compute the second derivative at $$\alpha=0$$ as \begin{align} {\textstyle \frac{d^{2}}{d\alpha^{2}}}\Delta D(p^{\alpha}\Vert q)\vert_{\alpha=0}=\sum_{i}\frac{\left(\bar{p}_{i}-p_{i}\right)^{2}}{p_{i}}-\sum_{j}\frac{\left(\bar{q}_{j}-q_{j}\right)^{2}}{q_{j}} \end{align} $$\sum_{i}\frac{\left(\bar{p}_{i}-p_{i}\right)^{2}}{p_{i}}$$ is the so-called $$\chi^2$$ divergence from $$p$$ to $$\bar{p}$$, and $$\sum_{j}\frac{\left(\bar{q}_{j}-q_{j}\right)^{2}}{q_{j}}$$ is the same once $$Q$$ is applied to $$p$$ and $$\bar{p}$$. Note that $$\chi^2$$ divergence is a special case of a $$f$$-divergence, and therefore obeys a data-processing inequality (see e.g. Liese and Vajda, IEEE Trans on Info Theory, 2006, Thm. 14). In particular, that means that $${\textstyle \frac{d^{2}}{d\alpha^{2}}}\Delta D(p^{\alpha}\Vert q)\vert_{\alpha=0} \ge 0$$.

At the same time, $$\Delta D(p\Vert p')$$ is not convex in the second argument. Consider $$p = (0.5,0.5,0)$$, $$q=(0.5,0.25,0.25)$$, and $$Q = \left( \begin{smallmatrix} 0.95 & 0.05 \\ 1 & 0 \\ 0 & 1\end{smallmatrix} \right)$$. Here is a plot of $$\Delta D$$ where the first argument is $$p$$ and the second argument is a convex mixture of between $$p$$ and $$q$$, $$\alpha p + (1-\alpha) q$$, for different $$\alpha$$:

(see code at https://pastebin.com/q8XLnGK8)

By visual inspection, it can be verified $$\Delta D(p\Vert p')$$ is neither convex nor concave in the second argument.

(1) $$I({p})$$ is known to be concave in $$p$$ (Theorem 2.7.4 in Cover and Thomas, 2006). As we've shown $$\Delta D(p\Vert p')$$ is convex in $$p$$, so $$-\Delta D(p\Vert p')$$ is concave in $$p$$. Since the sum of concave functions is concave, $$J(p,p') = I(p) - \Delta D(p\Vert p')$$ is concave in $$p$$.
At the same time, as a function of the second argument $$p'$$, $$J(p,p') = \mathrm{const} - \Delta D(p\Vert p')$$, and we've shown above that $$\Delta D(p\Vert p')$$ is neither convex nor concave in the second argument. Thus, $$J(p,p')$$ is not concave in the second argument.
(2) $$\Delta D(p\Vert p') \ge 0$$ by the data processing inequality for KL divergence (Csiszar and Körner, 2011, Lemma 3.11). That means that \begin{align} J(p,p') = I(p) - \Delta D(p\Vert p') \le I(p) , \end{align} from which $$J(p,p') \le \max_s I(s)$$ follows immediately.
• Great answer but regarding the convexity proof, I still have a question. You've used $\alpha > 1$ in your plot but the second argument of $\Delta D(p, p')$ is still a probability distribution so you'd have to restrict $\alpha$ between 0 and 1, no? – user1936752 Mar 10 at 19:35
• Sorry for the confusion -- the plot was not labelled correctly, but the x-axis did actually span $\alpha \in [0,1]$. I also fixed a typo in the specification of $Q$ and added a link to pastebin. – Artemy Mar 11 at 0:50
• Regarding the counterexample: I first tried to show convexity in the second argument, and computed some of the second derivatives of $\Delta D(p\Vert p')$ with respect to $p_i'$. I got something like $p_i/({p_i'}^2)-\sum_{j}q_{j}Q_{ij}Q_{ij}/({q_j'}^{2})$. – Artemy Mar 11 at 18:42
• I then tried to "make these negative" by coming up with a matrix $Q$, $p$, and $p'$ such that there is some $i,j$ such that $Q_{ij}$ is large, $p_i$ is smaller than $p_i'$ and $q_j$ is larger than $q_j'$. This is pretty hand-wavy and not at all rigorous, but it led me to values that are close to the ones shown in the plot. – Artemy Mar 11 at 18:42