3
$\begingroup$

I want to calculate the Lipschitz constant of softmax with cross-entropy in the context of neural networks. If anyone can give me some pointers on how to go about it, I would be grateful.


Given a true label $Y=i$, the only non-zero element of the 1-hot ground truth vector is at the $i^{th}$ index. Therefore, the softmax-CE loss function can be written as:

$$ \mathrm{CE}(x) = - \log S_{i} (x) = -\log \left(\frac{e^{x_{i}}}{\sum_{j} e^{x_{j}}}\right) $$

$$ \left| \log S_{i} (x) - \log S_{i} (y) \right| \leq L | x - y | $$

I would like to estimate the value of $L$. I'd appreciate any pointers, thank you.

$\endgroup$

1 Answer 1

0
$\begingroup$

I'll try to solve this since I encountered the same problem.

First, note that since $\text{CE}: \mathbb{R}^n \to \mathbb{R}$ is differentiable, it is sufficient to find L such that $\lvert\lvert \nabla \text{CE}(x) \rvert\rvert \leq L$ where $\lvert\lvert \cdot \rvert\rvert$ is the euclidean norm. Now, let $s = \sum_{k}e^{x_k}$. Applying calculus rules we have that

$$ \nabla \text{CE}(x)_i = - \frac{\sum_{l \neq i} e^{x_l}}{s} \qquad \nabla \text{CE}(x)_j = \frac{e^{x_j}} {s} \qquad \forall j \neq i. $$ Therefore $$ \lvert\lvert \nabla \text{CE}(x) \rvert\rvert^2 = \frac{\big(\sum_{l \neq i} e^{x_l}\big)^2 + \sum_{l\neq i} e^{2x_l}}{s^2} \leq 2\frac{\big(\sum_{l \neq i} e^{x_l}\big)^2}{s^2} \leq 2\frac{\big(\sum_{l \neq i} e^{x_l}\big)^2}{\big(\sum_{l \neq i} e^{x_l}\big)^2} = 2, $$ where in the first inequality I used the fact that $\sum_i a_i^2 \leq (\sum_i a_i)^2$ when $a_i > 0$ for every $i$, while in the second inequality instead, I simply removed the (always positive) $i$-th term of the sum $s$ at the denominator, hence decreasing its value.

Hence we obtain that $\text{CE}$ is Lipschitz continuous with constant $L=\sqrt{2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .