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

Question

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.

Answer 1

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.