Several Inequalities for the logsumexp Operation

logsumexp运算的几个不等式 苏剑林 · 2022-05-10 · Mathematics inequality function

$\text{logsumexp}$ is an operation frequently encountered in machine learning, especially in the implementation and derivation of cross-entropy, and it is also a smooth approximation of $\max$ (see In Search of a Smooth Maximum Function]). Let $x=(x_1,x_2,\cdots,x_n)$, and define $\text{logsumexp}$ as

\begin{equation}\text{logsumexp}(x)=\log\sum_{i=1}^n e^{x_i}\end{equation}

This post introduces several inequalities involving $\text{logsumexp}$ that may prove useful in theoretical derivations.

Basic Bounds

Write $x_{\max} = \max(x_1,x_2,\cdots,x_n)$; then clearly we have

\begin{equation}e^{x_{\max}} < \sum_{i=1}^n e^{x_i} \leq \sum_{i=1}^n e^{x_{\max}} = ne^{x_{\max}}\end{equation}

Taking the logarithm of each term gives

\begin{equation}x_{\max} < \text{logsumexp}(x) \leq x_{\max} + \log n\end{equation}more

This is the most basic result concerning the upper and lower bounds of $\text{logsumexp}$, showing that the approximation error of $\text{logsumexp}$ to $\max$ does not exceed $\log n$. Note that this error is independent of $x$ itself, so we have

\begin{equation}x_{\max}/\tau < \text{logsumexp}(x/\tau) \leq x_{\max}/\tau + \log n\end{equation}

Multiplying each side by $\tau$ gives

\begin{equation}x_{\max} < \tau\text{logsumexp}(x/\tau) \leq x_{\max} + \tau\log n\end{equation}

When $\tau\to 0$, the error tends to 0, which tells us that we can improve the approximation to $\max$ by lowering the temperature parameter.

Averaging Bound

We know that $e^x$ is a convex function, satisfying Jensen's inequality] $\mathbb{E}[e^{x}]\geq e^{\mathbb{E}[x]}$, so

\begin{equation}\frac{1}{n}\sum_{i=1}^n e^{x_i}\geq e^{\bar{x}}\end{equation}

Here $\bar{x}=\frac{1}{n}\sum\limits_{i=1}^n x_i$; multiplying both sides by $n$ and taking the logarithm gives

\begin{equation}\text{logsumexp}(x)\geq \bar{x} + \log n\end{equation}

This is another result concerning the lower bound of $\text{logsumexp}$. This result can be further generalized to the weighted-average case: suppose we have $p_1,p_2,\cdots,p_n\geq 0$ with $\sum\limits_{i=1}^n p_i = 1$; by the Cauchy inequality we get

\begin{equation}\left[\sum_{i=1}^n (e^{x_i/2})^2\right]\left[\sum_{i=1}^n p_i^2\right]\geq \left[\sum_{i=1}^n p_i e^{x_i/2}\right]^2\end{equation}

Applying Jensen's inequality to the expression inside the brackets on the right-hand side gives

\begin{equation}\left[\sum_{i=1}^n p_i e^{x_i/2}\right]^2\geq \left[e^{\left(\sum\limits_{i=1}^n p_i x_i/2\right)}\right]^2 = e^{\left(\sum\limits_{i=1}^n p_i x_i\right)}\end{equation}

Taking the logarithm of both sides of each expression and rearranging gives

\begin{equation}\text{logsumexp}(x)\geq \sum_{i=1}^n p_i x_i - \log\sum_{i=1}^n p_i^2\end{equation}

If instead of the Cauchy inequality we start with the more general Hölder inequality], we can further obtain

\begin{equation}\text{logsumexp}(x)\geq \sum_{i=1}^n p_i x_i - \frac{1}{t-1}\log\sum_{i=1}^n p_i^t,\quad \forall t > 1\end{equation}

In particular, taking the limit of $t\to 1$, we can obtain

\begin{equation}\text{logsumexp}(x)\geq \sum_{i=1}^n p_i x_i - \sum_{i=1}^n p_i \log p_i\end{equation}

which can equivalently be rewritten as $\sum\limits_{i=1}^n p_i \log \frac{p_i}{e^{x_i}/Z} \geq 0$, where $Z=e^{\text{logsumexp}(x)}$ is a normalizing factor, so this is in fact just the $KL$ divergence between two distributions.

L-constraint

Under the infinity norm, $\text{logsumexp}$ also satisfies a Lipschitz constraint, i.e.,

\begin{equation}|\text{logsumexp}(x) - \text{logsumexp}(y)| \leq |x - y|_{\infty}\end{equation}

Here $|x-y|_{\infty} = \max\limits_i |x_i - y_i|$ (it would actually be more intuitive to denote it as $|x - y|_{\max}$). The proof is not too difficult either; define

\begin{equation}f(t) = \text{logsumexp}(tx + (1-t)y),\quad t\in[0, 1]\end{equation}

Regarding this as a univariate function of $t$, by the Mean Value Theorem] there exists $\varepsilon\in(0, 1)$ such that

\begin{equation}f'(\varepsilon) = \frac{f(1) - f(0)}{1 - 0} = \text{logsumexp}(x) - \text{logsumexp}(y) \end{equation}

It is not hard to work out that

\begin{equation}f'(\varepsilon) = \frac{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}(x_i - y_i)}{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}} \end{equation}

hence

\begin{equation}\begin{aligned}&\,|\text{logsumexp}(x) - \text{logsumexp}(y)| = \left|\frac{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}(x_i - y_i)}{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}}\right| \\ \leq &\, \frac{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i} |x_i - y_i|}{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}} \leq \frac{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i} |x - y|_{\infty}}{\sum\limits_{i=1}^n e^{\varepsilon x_i + (1-\varepsilon)y_i}} = |x - y|_{\infty} \end{aligned}\end{equation}

Convex Function

Finally, here is a very strong result: $\text{logsumexp}$ is in fact a convex function! This means that all inequalities related to convex functions apply to $\text{logsumexp}$, such as the most basic Jensen's inequality:

\begin{equation} \mathbb{E}[\text{logsumexp}(x)] \geq \text{logsumexp}(\mathbb{E}[x])\end{equation}

To prove that $\text{logsumexp}$ is convex, we need to show that for $\forall t\in[0, 1]$, the following always holds:

\begin{equation} t\text{logsumexp}(x) + (1-t)\text{logsumexp}(y)\geq \text{logsumexp}(tx + (1-t)y)\end{equation}

The proof is essentially a basic application of Hölder's inequality]. Specifically, we have

\begin{equation}t\text{logsumexp}(x) + (1-t)\text{logsumexp}(y) = \log\left(\sum_{i=1}^n e^{x_i}\right)^t \left(\sum_{i=1}^n e^{y_i}\right)^{(1-t)}\end{equation}

Now applying Hölder's inequality directly gives

\begin{equation}\log\left(\sum_{i=1}^n e^{x_i}\right)^t \left(\sum_{i=1}^n e^{y_i}\right)^{(1-t)}\geq \log\sum_{i=1}^n e^{tx_i + (1-t)y_i} = \text{logsumexp}(tx + (1-t)y)\end{equation}

This proves that $\text{logsumexp}$ is a convex function.

Closing Remarks

This post has mainly summarized various inequalities related to the $\text{logsumexp}$ operation, to have on hand for whenever they might be needed.