8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.