0
$\begingroup$

I am familiar with the convexity proof for \begin{align} f_i(x) &= -\log\left(p_i(x)\right) = -\log\left(\frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right) = \log\left(\sum_j \exp(x_j)\right) -x_i. \end{align}

Convexity here is due to the fact that "$-x_i$" is convex and so is "$\log\left(\sum_j \exp(x_j)\right)$".

But what about the convexity status of the negative log complementary probability \begin{align} g_i(x) &= -\log\left(1 - p_i(x)\right) = \log\left(\sum_j \exp(x_j)\right) - \log\left(\sum_{k\not=i} \exp(x_k)\right)? \end{align} Is $g_i(x)$ convex?

Here things are not so nice because we have a difference of convex functions (the log-sum-exps) which is not guaranteed to be convex. I've started writing out the Hessian which is messy and difficult to analyze. Any thoughts or suggestions are welcomed.

$\endgroup$
  • $\begingroup$ if $j$ only sums over two terms, $f_i$ and $g_i$ are the same; I suggest you create a plot of the function for three terms to see if it may be convex $\endgroup$ – LinAlg Oct 5 '18 at 12:54
  • $\begingroup$ Correct, in the binary outcome case, the complementary probability is just a sum over one term. $\endgroup$ – ted Oct 5 '18 at 16:01
1
$\begingroup$

In general, $g_i(x)$ is not convex. We can construct a counterexample as follows.

Consider the case of three categories, where $\boldsymbol{x} = (x_1, x_2, x_3)$. If $g_1(\boldsymbol{x})$ is convex, then $h(t) \triangleq g_1((0, t, -t))$ should also be convex.

Since $$ \begin{aligned} g_1(\boldsymbol{x}) &= \log \frac{\exp(x_1) + \exp(x_2) + \exp(x_3)}{\exp(x_2) + \exp(x_3)}\\ &= \log \left(1 + \frac{1}{\exp(x_2 - x_1) + \exp(x_3 - x_1)}\right) \end{aligned} $$ we know that $$ h(t) = \log\left(1 + \frac{1}{e^{t} + e^{-t}}\right), $$ and it is not convex.

Indeed, if $h(t)$ is convex, note that $$ \lim_{t \to \infty} h(t) = 0, $$ then the convexity will imply $h(t) \equiv 0$, which is impossible.

$\endgroup$
  • $\begingroup$ This is nice. How did you choose the line of points (0,t,-t) to demonstrate the non-convexity? $\endgroup$ – ted Oct 6 '18 at 16:47
  • $\begingroup$ When I was going to reduce the expression of $g_1$, I find this could be a good choice that is different from the trivial case of two categories. Instead, if you set $x_2 = x_3$ with $x_1 = 0$, you will eventually get a expression similar to $f_i$, which is convex. So the key point is to let $x_2$ and $x_3$ have different behaviors. Hence I try the setting $x_2 = -x_3$, and it works:) Hope this would be helpful. $\endgroup$ – Xiangxiang Xu Oct 7 '18 at 2:39
  • $\begingroup$ Thanks. Good thinking! $\endgroup$ – ted Oct 7 '18 at 18:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.