# 1-Smoothness of the Symmetric Softmax Function

Define the symmetric softmax of a vector $x\in \mathbb{R}^n$ to be $$L(x)=\log\sum_i(e^{x_i}+e^{-x_i}).$$

Equation (6) in this paper states that for all $x$ and $y$ $$|\nabla L(x)-\nabla L(y)|_1 \leqslant ||x-y||_{\infty}.$$

(Apparently, this property is called 1-smoothness in optimisation)

I'm having a hard time proving this. I also tried to look for a proof but couldn't find one. I'd appreciate someone pointing me to a reference containing a proof. Thanks.

Edit: This question has been bugging my mind these days, to the extent that it forced me to start a bounty! Now if someone has any insights about this, please give it a try. I think I might have been on the right track, but now I'm lost. $$L(x)=\log\sum_{i=1}^n(e^{x_i}+e^{-x_i})=\log 2+\log\sum_{i=1}^n\cosh x_i$$ Hence $$\frac{\partial L}{\partial x_k}=\frac{\sinh x_k}{\sum_{i=1}^n\cosh x_i}$$ First we prove: $$\Vert \nabla L(x)\Vert_1\le\Vert x\Vert_\infty$$ Knowing that $\Vert v\Vert_1=\sum|v_i|$ and $\Vert v\Vert_\infty=\sup|v_i|$, and also $$\frac{\sinh z}{z}\le\cosh z,\; \forall z\in\mathbb R$$ we can write: \begin{align} \Vert \nabla L(x)\Vert_1=\sum_{k=1}^n\left|\frac{\partial L}{\partial x_k}\right|&= \frac{\sum_{i=1}^n|\sinh x_i|}{\sum_{i=1}^n\cosh x_i}\\ &\le\frac{\sum_{i=1}^n|x_i|\cosh x_i}{\sum_{i=1}^n\cosh x_i} \le\frac{\Vert x\Vert_\infty\sum_{i=1}^n\cosh x_i}{\sum_{i=1}^n\cosh x_i}\\&=\Vert x\Vert_\infty\end{align} Now write $y=x+\delta$, you need to show that $\Vert\nabla L(x+\delta)-\nabla L(x)\Vert_1\le\Vert\delta\Vert_\infty$.

But... the statement seems a bit hard to prove, and I doubt that changing $y$ to $x+\delta$ will get us anywhere. By the way, regarding this question, I came up with something like this:

Let $p=\nabla L(x)$ and $q=\nabla L(y)$, and define: $$M=\sum_{j=1}^n q_j\log p_j$$ then we have: $$q_i-p_i=\frac{\partial M}{\partial x_i}$$ and we will need to show that $\Vert \nabla M\Vert_1\le\Vert y-x\Vert_\infty$. Although it seems $\Vert p\Vert_1\le\Vert x\Vert_\infty$ and $\Vert q\Vert_1\le\Vert y\Vert_\infty$ are some valuable information, but I wasn't able to go any further.

So I've been messing around with this problem and I've made some progress, although I'm not at a full proof just yet. Maybe someone can pick up from here.

First, we notice that working with $L(x)=\log\sum_i e^{x_i}$ is without loss of generality since we can just plug in $[x^T, -x^T]^T$ and obtain the original softmax function.

For any $x,d \in \mathbb{R}^n$, \begin{align*} |\nabla L(x+d)-\nabla L(x)|_1 &= \sum_i \left| \frac{e^{x_i+d_i}}{\sum_j e^{x_j+d_j}}-\frac{e^{x_i}}{\sum_j e^{x_j}}\right|\\ &= \sum_i \left| \frac{\sum_je^{x_i+x_j+d_i}-\sum_je^{x_i+x_j+d_j}}{\sum_j \sum_k e^{x_j+x_k+d_j}}\right|\\ &= \frac{\sum_i \sum_j e^{x_i+x_j}|e^{d_i}-e^{d_j}|}{\sum_i \sum_je^{x_i+x_j}e^{d_i}}\stackrel{?}{\leqslant}||d||_{\infty}=:D. \end{align*}

By the positivity of $e^{x_i+x_j}$, it suffices to show that $\sum_i \sum_j |e^{d_i}-e^{d_j}|-De^{d_i}\leqslant 0$ (i.e., $\sum_i \sum_j |e^{d_i}-e^{d_j}|-nD\sum_i e^{d_i}\leqslant 0$). At this point, we can assume without loss of generality that $d_1 \geqslant d_2 \geqslant \cdots \geqslant d_n$, then collect terms and simplify the left-hand side of the required inequality (specifically the double-sum) to: \begin{align*} \sum_i \sum_j |e^{d_i}-e^{d_j}|-nD\sum_i e^{d_i} &= \sum_k 2(n-2k+1)e^{d_k}-nD\sum_k e^{d_k}\\ &=\sum_k ((2-D)n-4k+2)e^{d_k}. \end{align*} If all coefficients of $e^{d_k}$ are non-positive, we are done. Otherwise, we define $k_0$ to be the largest index for which the corresponding coefficient is positive; i.e., $$k_0 = \left\lfloor \frac{(2-D)n+2}{4}\right\rfloor.$$ Then we can split the terms into ones with positive and nonpositive coefficients and say: \begin{align*} \sum_{k=1}^n ((2-D)n-4k+2)e^{d_k} \leqslant \left(\sum_{k=1}^{k_0} ((2-D)n-4k+2)\right)e^{d_1}+\left(\sum_{k=k_0+1}^{n} ((2-D)n-4k+2)\right)e^{d_n}. \end{align*}

So the problem boils down to a condition on just two variables. After some massaging of the right-hand side, the condition to be shown is: $$2k_0(n-k_0-0.5Dn)(e^{d_1}-e^{d_n})-Dn^2e^{d_n}\stackrel{?}{\leqslant}0.$$

This seems to check out empirically. We can also note that whenever $D\geqslant 2$, all coefficients are nonpositive, so we can restrict our search to $-2\leqslant d_n \leqslant d_1 \leqslant 2$.

That's as far as I've gotten. If someone has any ideas on how to prove this, it would be much appreciated.

EDIT: So here's what this looks like. It's maximised at $(d_1,d_n)=(0,0)$ with value $0$, and as you head towards $(-2,-2)$, it drops and then starts tending to zero again. This is for $n=2$ but it's pretty much the same for any $n$. 