# Proving convexity of the negative log complementary probability: $-\log\left(1 - \frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right)$

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.

• 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 Oct 5 '18 at 12:54
• Correct, in the binary outcome case, the complementary probability is just a sum over one term.
– ted
Oct 5 '18 at 16:01

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.

• This is nice. How did you choose the line of points (0,t,-t) to demonstrate the non-convexity?
– ted
Oct 6 '18 at 16:47
• 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. Oct 7 '18 at 2:39
• Thanks. Good thinking!
– ted
Oct 7 '18 at 18:18