# Log-Sum-Exp as an approximation of min function

I can prove that the function: $$f(\tau, x_1, x_2, ..., x_N) = -\tau \log \frac{1}{N} \sum_{i=1}^{N} \exp{\left(-\frac{x_i}{\tau}\right)}$$ converges to $$\min(x_1, x_2, ..., x_N)$$ for $$x_i \geq 0$$ as $$\tau \to +0$$ using the L'Hospital's rule (by substitution $$\tau=\frac{1}{\rho}$$ and finding the limit $$\rho \to +\infty$$)

However, I need also to find the upper bound of the approximation error: $$\left| f(\tau, x_1, x_2, ..., x_N) - z \right| \leq h(\tau, x_1, x_2, ..., x_N)$$ where $$z=\min(x_1, x_2, ..., x_N)$$.

Using Jensen's inequality and fact that $$-\log(y)$$ is convex I can show that $$$$\begin{split} \left| f(\tau, x_1, x_2, ..., x_N) - z \right| &= -\tau \log \frac{1}{N} \sum_{i=1}^{N} \exp \left( -\frac{x_i - z}{\tau} \right) \leq \\ &\leq -\frac{\tau}{N} \sum_{i=1}^{N} \log \exp \left( -\frac{x_i - z}{\tau} \right) = \bar{x} - z, \end{split}$$$$ where $$\bar{x}=\frac{1}{N}\sum x_i$$. However, this bound doesn't depend on parameter $$\tau$$.

I wonder if there any sharper upper bound, which depends on $$\tau$$?

• I suppose you mean "$\tau \rightarrow 0^+$", since the two-sided limit doesn't exist. Also, I have trouble with your limit claim. For $N = 1$, $x_1 = 1$, as $\tau \rightarrow 0^-$, $f \rightarrow \infty$ and as $\tau \rightarrow 0^+$, $f \rightarrow 0$. – Eric Towers May 20 '19 at 18:53
• @EricTowers thanks for the comment, yes, I looking for a limit $\tau \to +0$. I apply L'Hospital's rule by substituting $\tau = \frac{1}{\rho}$. Then $\rho \to +\infty$ – dm_k May 20 '19 at 19:02
• @EricTowers in that case I get: $$-\frac{\log \frac{1}{N} \sum_{i=1}^{N} \exp ( -\rho x_i) }{\rho}$$ as $\rho \to +\infty$ – dm_k May 20 '19 at 19:03
• @EricTowers it is $\lim_{\rho \to +\infty} -\frac{\log \frac{1}{N} \sum_{i=1}^{N} e ^ {( -\rho x_i)} }{\rho}$, which is $\frac{\infty}{\infty}$. – dm_k May 20 '19 at 19:11

We may rearrange the $$x_i$$ so that they are sorted $$x_1 \leq x_2 \leq \cdots \leq x_N$$. Then \begin{align*} f(\tau, x_1, \dots, x_N) &= -\tau \ln \left( \frac{1}{N}\sum_{i=1}^N \mathrm{e}^{-x_i/\tau} \right) \\ &= -\tau \left( \ln\left( \frac{1}{N}\mathrm{e}^{-x_1/\tau} \right) + \ln \left( 1 + \sum_{i=2}^N \mathrm{e}^{(x_1-x_i)/\tau} \right) \right) \\ &= -\tau \left( -\ln(N) - \frac{x_1}{\tau} + \ln \left( 1 + \sum_{i=2}^N \mathrm{e}^{(x_1-x_i)/\tau} \right) \right) \\ &= \tau \ln(N) + x_1 - \tau \ln \left( 1 + \sum_{i=2}^N \mathrm{e}^{(x_1-x_i)/\tau} \right) \text{.} \end{align*} Therefore, $$|f(\tau, x_1, \dots, x_N) - x_1| = \left| \tau \ln(N) - \tau \ln \left( 1 + \sum_{i=2}^N \mathrm{e}^{(x_1-x_i)/\tau} \right) \right| \text{.}$$ For $$\tau$$ sufficiently small, the sum expression in the the parentheses is $$\varepsilon \ll 1$$, so \begin{align*} |f(\tau, x_1, \dots, x_N) - x_1| &= \left| \tau \ln(N) - \tau \ln \left( 1 + \varepsilon \right) \right| \\ &= \tau \left| \ln(N) - \left(\varepsilon + O(\varepsilon^2) \right) \right| \\ &\approx \tau \ln N \text{.} \end{align*}
Visually inspecting graphs of $$f$$ versus $$\tau$$ for several choices of $$N$$ and $$x_i$$, this does capture the near zero behaviour.
• In fact, is it correct to write that $$| f(\tau, x_1, x_2, ..., x_n) - x_1 | = \tau | \log (N) - \log(1 + \varepsilon) | \leq \tau | \log N |,$$ since $\varepsilon \geq 0$? – dm_k May 20 '19 at 22:10
• @dm_k : I believe so. Not making that shift is a holdover from the "Therefore, [display equation].", when I wasn't sure whether the positive term or negative term would dominate (for what ranges of $\tau$). For $N>1$, since we can take $\varepsilon \ll \min\{ 1 , \ln N \}$, that works. For $N = 1$, $\varepsilon = 0$ and the equality in your inequality holds. – Eric Towers May 20 '19 at 23:17