Convexity of $f(\boldsymbol{p}) = \sum_i p_i \log \sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}$

Question

Question

Given that $\boldsymbol{a} > 0$, how to prove

$$f(\boldsymbol{p}) = \sum_i p_i \log \sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}$$

is a convex function of probability distribution $\boldsymbol{p}$? Is it possible to generalize from the convexity of the negative entropy $p \log p$?

---

Attempts

• Midpoint convex + continuous => convex: to prove $$f\left(\frac{\boldsymbol{p} + \boldsymbol{q}}{2}\right) \le \frac{f(\boldsymbol{p}) + f(\boldsymbol{q})}{2}$$ It reduces to $$\prod_i \left(\sum_j \frac{p_j+q_j}{2} \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{p_i+q_i} \le \prod_i \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{p_i} \left(\sum_j q_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{q_i}$$ and the original GM-HM trick for $p \log p$ does not work. It looks very similar to Holder's inequality but I failed to gain more insights...

• Hessian: the $(m,n)$ entry of Hessian is $$\frac{b_{m,n}}{\sum_j p_j b_{m,j}} + \frac{b_{n,m}}{\sum_j p_j b_{n,j}} - \sum_i p_i \frac{b_{i,m} b_{i,n}}{(\sum_j p_j b_{i,j})^2}$$ where $b_{i,j} = \frac{4 a_i a_j}{(a_i + a_j)^2}$. Simulation suggests the Hessian is generally positive semidefinite, but finding a proof seems nontrivial.

---

Thank you very much for the attention.

Answer 1

I also want to add some context for Hessian.

The Gram matrix $\boldsymbol{G}$ contains all possible inner products of a set of vectors $\{\boldsymbol{v}\}$, and its $(m,n)$ entry is $g_{m,n} = \boldsymbol{v}_m^\mathsf{T} \boldsymbol{v}_n = \sum_i [\boldsymbol{v}_m]_i [\boldsymbol{v}_n]_i$.

According to Wikipedia,

The Gram matrix is positive semidefinite, and every positive semidefinite matrix is the Gramian matrix for some set of vectors.

If we can write the Hessian as a Gram matrix, then it is positive semidefinite.

The $(m,n)$ entry of the Hessian is \begin{align} [D^2 f]_{m,n} & = \frac{b_{m,n}}{\sum_j p_j b_{m,j}} + \frac{b_{n,m}}{\sum_j p_j b_{n,j}} - \sum_i p_i \frac{b_{i,m} b_{i,n}}{(\sum_j p_j b_{i,j})^2}\\ & = \sum_i p_i \frac{[\boldsymbol{c}_{m,n}]_i}{\left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^2}\\ & \stackrel{?}{=} \sum_i [\boldsymbol{v}_m]_i [\boldsymbol{v}_n]_i, \end{align} where $$[\boldsymbol{c}_{m,n}]_i={\frac{4 a_m a_n}{(a_m + a_n)^2} \left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2} + \sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^2 - \left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \frac{4 a_i a_m}{(a_i + a_m)^2} \frac{4 a_i a_n}{(a_i + a_n)^2}}$$

If we can write $[\boldsymbol{c}_{m,n}]_i = [\boldsymbol{c}_{m}]_i [\boldsymbol{c}_{n}]_i$ then the Hessian is Grammian and the proof can be completed.

Answer 2

Please correct me If I am wrong. For midpoint convex:

Starting from the binary input $L=2$ case, where the inequality reduces to

$$\left(\frac{p_1+q_1}{2}+\frac{p_2+q_2}{2}b\right)^{p_1+q_1} \cdot \left(\frac{p_1+q_1}{2}b+\frac{p_2+q_2}{2}\right)^{p_2+q_2} \le (p_1+p_2b)^{p_1} \cdot (q_1+q_2b)^{q_1} \cdot (p_1b+p_2)^{p_2} \cdot (q_1b+q_2)^{q_2},$$

where $b=\frac{4a_1a_2}{(a_1+a_2)^2}$. Note both sides are symmetrical and it is sufficient to prove the inequality for the first half.

Let $p_1 = p$, $q_1 = q$ and the first half becomes $$\left(\frac{p+q+(1-p)b+(1-q)b}{2}\right)^{p+q} \le \Bigl(p+(1-p)b\Bigr)^{p} \Bigl(q+(1-q)b\Bigr)^{q},$$ that is, $$\left(\frac{(1-b)(p+q)}{2}-b\right)^{p+q} \le \Bigl((1-b)p+b\Bigr)^p \Bigl((1-b)q+b\Bigr)^q.$$ Since $0 < b \le 1$, we have $$\text{LHS} \le \left(\frac{(1-b)(p+q)}{2}\right)^{p+q},\quad \Bigl((1-b)p\Bigr)^p \Bigl((1-b)q\Bigr)^q \le \text{RHS}.$$ On the other hand, using $\left(\frac{p+q}{2}\right)^{p+q} \le p^p q^q$ [proof] gives $$(1-b)^{p+q} \left(\frac{p+q}{2}\right)^{p+q} \le (1-b)^{p+q} p^p q^q,$$ that is, $$\left(\frac{(1-b)(p+q)}{2}\right)^{p+q} \le \Bigl((1-b)p\Bigr)^p \Bigl((1-b)q\Bigr)^q,$$ which proves $\text{LHS} \le \text{RHS}$ and completes the proof for $L=2$.

For $L>2$, the proof extends by starting from $L=2$ and iteratively splitting one input probability to two.