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{equation} \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} \end{equation} 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$?

  • $\begingroup$ 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$. $\endgroup$ – Eric Towers May 20 '19 at 18:53
  • $\begingroup$ @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$ $\endgroup$ – dm_k May 20 '19 at 19:02
  • $\begingroup$ @EricTowers in that case I get: $$ -\frac{\log \frac{1}{N} \sum_{i=1}^{N} \exp ( -\rho x_i) }{\rho} $$ as $\rho \to +\infty$ $\endgroup$ – dm_k May 20 '19 at 19:03
  • $\begingroup$ @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}$. $\endgroup$ – 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.

  • $\begingroup$ Very nice. Thank you! This is exactly what I was looking for. $\endgroup$ – dm_k May 20 '19 at 22:06
  • $\begingroup$ 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$? $\endgroup$ – dm_k May 20 '19 at 22:10
  • $\begingroup$ @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. $\endgroup$ – Eric Towers May 20 '19 at 23:17
  • $\begingroup$ Everything is clear now. Thanks a lot for the help. $\endgroup$ – dm_k May 20 '19 at 23:25

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.