0
$\begingroup$

I would like to maximize the following functional $F(q)$ w.r.t. the probability mass function $q:\mathcal{Z}\rightarrow [0,1]$ with $\sum_{z \in \mathcal{Z}} q(z)=1$, where $\mathcal{Z}$ is a finite set:

\begin{equation} \label{eq:one} \max_q F(q) = \max_{q} \sum_{x,y} p(x) \left(\sum_{z} p(y|x,z) q(z)\right) \log \frac{\sum_{\bar{z}} p(y|x,\bar{z}) q(\bar{z})}{\sum_{\bar{x}} p(\bar{x}) \sum_{\tilde{z}} p(y|\bar{x},\tilde{z}) q(\tilde{z})} \end{equation}

Just like $Z$ the random variables $X,Y$ are finite. In case of convexity this would be much easier so I am trying to establish whether this functional is convex in $q$ or not. If you see that it is or is not then you may stop reading here and just tell me why (If you know how to optimize this function reliably w.r.t. q let me know and I'll write an additional question). Below is just my failed attempt up to now.

One way to show convexity is to identify convexity preserving operations. If we substitute

$$r(y|x):=\sum_{z} p(y|x,z) q(z)$$

we can see that $F(r(q))$ is a mutual information:

$$F(r) = \sum_{x,y} p(x) r(y|x) \log \frac{r(y|x)}{\sum_{\bar{x}} p(\bar{x}) r(y|\bar{x})}=I(X:Y)$$

This is known to be convex in $r(y|x)$ (see e.g. [1]). We can also easily see that $r(q)$ is convex in $q$ because it is actually linear in $q$. Now we know that if $F(r)$ is convex in $r$ and nondecreasing in every component $r_{yx}:=r(y|x)$, and each of those components $r_{yx}(q)$ is convex in $q$ then $F(r(q))$ is convex in $q$ (see [2], p.86).

The problem is, that $F(r)$ is not nondecreasing in every component $r_yx:=r(y|x)$. This can be seen by taking the derivative of $F$ w.r.t. some $r(y'|x')$ which gives:

$$\frac{\partial}{\partial r(y'|x')} F(r)= p(x') \log \frac{r(y'|x')}{\sum_{\bar{x}} p(\bar{x}) r(y'|\bar{x})}.$$

Since examples with $r(y'|x')<\sum_{\bar{x}} p(\bar{x}) r(y'|\bar{x})$ are easy to construct this derivative can be negative so that $F(r)$ is not nondecreasing in general.

As far as I can see this does not imply that $F(q)$ is not convex, only that this way of showing it fails.

[1] Cover, Thomas M.; Thomas, Joy A., Elements of information theory, Wiley Series in Telecommunications. New York: John Wiley & Sons, Inc. xxii, 542 p. (1991). ZBL0762.94001.)

[2] Boyd, Stephen; Vandenberghe, Lieven, Convex optimization., Cambridge University Press (ISBN 0-521-83378-7/hbk). xiii, 716 p. (2004). ZBL1058.90049.

$\endgroup$
4
  • $\begingroup$ Even if you show that $F$ is convex, you have a problem, because convex optimization requires that you minimize a convex functional, and you are trying to maximize it. $\endgroup$ Jan 19, 2018 at 2:30
  • $\begingroup$ Nevertheless: consider the function $G(v,w) = v\log (v/w) = v\log v - v\log w$. Is it convex? If so can you take advantage of that fact? $\endgroup$ Jan 19, 2018 at 2:31
  • $\begingroup$ @MichaelGrant Ha, thanks for pointing that out. A bit embarrassing. I guess I'll leave the question here as it is well defined. I have to maximize this function however and convexity won't really help. 2nd comment: mutual information is a convex combination of sums $\sum_{y} G(v_{y},w_{y})$ so $F$ is convex if $G$ is convex (without the nondecreasing condition) and in my case $v_y=v_y(q)$ and $w_y=w_y(q)$. So showing $G(v_y(q),w_y(q))$ is convex in $q$ would be enough for convexity of $F(q)$. But 2nd derivative of $G(v_y(q),w_y(q))$ can be negative if I am not wrong and so this fails as well. $\endgroup$
    – mab
    Jan 19, 2018 at 8:37
  • $\begingroup$ I actually think $G$ is convex. $\endgroup$ Jan 19, 2018 at 12:38

0

Your Answer

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

Browse other questions tagged or ask your own question.