Is log-sum-exp a contraction

Question

For $x \in \mathbb{R}^n$, the log-sum-exp (lse) function $\mathbb{R}^n \rightarrow \mathbb{R}$ is defined as $lse(x) = \tau \log \sum_{i=1}^n \exp(\frac{x_i}{\tau})$, where $\tau > 0$ is a temperature. Is lse an infinity norm contraction? In other words, is there an $L \in (0, 1)$ such that for all $x, y \in \mathbb{R}^n$, $$|lse(x) - lse(y)| \leq L ||x - y||_\infty$$ From some literature search I find it holds for $L=1$, but is it possible for $L < 1$? I guess $L$ may be a function of $\tau$. I did some simulation and found it seems true and $L$ is not monotonic w.r.t. $\tau$.

Answer 1

You cannot do better than $L=1$. To see this, let us first get rid of the $\tau$. Using the fact that $\tau\neq 0$ and scaling the coordinates by $\tau$, it clearly follows that proving the displayed inequality in the question is the same as showing that $$ \tag{1} |lse(\tau x ) - lse(\tau y)| \leq L || \tau x - \tau y ||_\infty, \text{ for all } x, y \in \mathbb{R}^n. $$ Writing $(1)$ explicitly, gives $$ \tag{2} \left|\log \sum\limits_{i=1}^n e^{x_i} - \log \sum\limits_{i=1}^n e^{y_i} \right| \leq L || x - y||. $$

In dimension $n=1$, $(2)$ is reduced to $$ |\log e^x - \log e^y | = |x - y|, $$ hence $L=1$ is the Lipschitz constant when $n=1$. In higher dimensions, for instance, $L=1$ is realized on points having all their $n$ coordinates $0$ except one.

To see that $L=1$ actually satisfies $(1)$, denote $f(x) = \log \sum\limits_{i=1}^n e^{x_i}$ and observe that for any $1\leq i \leq n$ we have $$ f_{x_i}(x) = \frac{e^{x_i}}{e^{x_1} + ... + e^{x_n}}, $$ where $f_{x_i}$ is the $i$-th partial derivative of $f$. Hence, from the intermediate value theorem for some $c\in \mathbb{R}^n$ lying on the segment $[x,y]$ we have $$ |f(x) - f(y)| = |\nabla f(c) \cdot (x-y)| \leq ||x-y||_\infty \sum\limits_{i=1}^n f_{x_i}(c) = ||x-y||_\infty, $$ which proves that $L=1$ is indeed the Lipschitz constant for $lse$.