2
$\begingroup$

I am trying to prove that the Log-Sum-Exp function converges to the maximum function, i.e. $$ lim_{\tau\rightarrow0}\tau\log\left(\frac{1}{N}\sum_{i=1}^N\exp\left(\frac{x_{i}}{\tau}\right)\right) = \max_{i}(x_1, \dots, x_N).$$ I saw that a possible direction is to solve the limit as $\rho=1/\tau\rightarrow \infty$ and apply De l'Hôpital rule. What I get is the following: $$lim_{\rho\rightarrow\infty} \frac{\frac{1}{N}\sum_{i=1}^Nx_{i}\exp\left(\rho x_{i}\right)}{\frac{1}{N}\sum_{i=1}^N\exp\left(\rho x_{i}\right)}.$$ But at this point I got stuck and didn't know how to proceed. The final result should be the maximum among $\{x_{i}\}$. Does anyone have some suggestions?

$\endgroup$
1
  • $\begingroup$ Simply factor out the maximum. Then see what happens $\endgroup$
    – lcv
    Feb 26 at 11:46

2 Answers 2

3
$\begingroup$

Here's a hint if you want to try it yourself first: what happens if you divide by $\exp(\rho x_j)$ where $x_j$ is a maximal element?

Choose $x_j$ so that $x_j = \max_i (x_1, \ldots, x_N)$. We then have $$ \frac{\sum_i x_i \exp(\rho x_i)}{\sum_i \exp(\rho x_i)} = \frac{\sum_i x_i \exp(\rho (x_i - x_j))}{\sum_i \exp(\rho (x_i - x_j))} $$ Suppose $I$ is the set of indices $i$ such that $x_i = x_j$ for all $i \in I$, i.e. $I$ is the set of indices of elements with maximal value. We can then write $$ \sum_{i} x_i \exp(\rho (x_i - x_j)) = \sum_{i \in I} x_i \exp(\rho (x_i - x_j)) + \sum_{i \not\in I} x_i \exp(\rho (x_i - x_j)) = |I| x_j + \sum_{i \not\in I} x_i \exp(\rho (x_i - x_j)) $$ Then $$ \sum_{i} x_i \exp(\rho (x_i - x_j)) \rightarrow |I| x_j $$ as $\rho \rightarrow \infty$, since $x_i < x_j$ for all $i \not\in I$. Similarly, $$ \sum_i \exp(\rho (x_i - x_j)) = \sum_{k=1}^{|I|} 1 + \sum_{i \not\in I} x_i \exp(\rho (x_i - x_j)) = |I| + \sum_{i \not\in I} \exp(\rho (x_i - x_j)) \rightarrow |I| $$ as $\rho \rightarrow \infty$. Thus, $$ \lim\limits_{\rho \rightarrow \infty} \frac{\sum_i x_i \exp(\rho x_i)}{\sum_i \exp(\rho x_i)} = \frac{|I|x_j}{|I|} = x_j = \max_i (x_1, \ldots, x_N) $$ exists.

$\endgroup$
2
$\begingroup$

You don't need L'Hospital in the present case. Let's set $x_1 = \max(x_1,\ldots,x_N)$ without loss of generality $-$ because you can always re-index the list of $x_i$. The factor $e^{x_1/\tau}$ is thus the "heaviest weight" in the sum, which can be factorized as follows : $$ \sum_{i=1}^N e^{x_i/\tau} = e^{x_1/\tau} \left(1 + \sum_{i=2}^N e^{(x_i-x_1)/\tau}\right), $$ with $x_i - x_1 < 0$, hence $$ \tau\ln\left(\frac{1}{N}\sum_{i=1}^N e^{x_i/\tau}\right) = x_1 + \tau\ln\left(1 + \sum_{i=1}^N e^{-|x_1-x_i|/\tau}\right) - \tau\ln N, $$ which converges to $x_1$ when $\tau \to 0$, since $e^{-|x_1-x_i|/\tau} \to 0$. QED

$\endgroup$
2
  • $\begingroup$ Thank you, the reasoning for n=1 is clear. However, if I have multiple $x_{i}$ attaining the maximum I still retrieve the previous formula. Specifically, supposing I have $n > 1$ maximum instances what I'm left with is: $$ x_{1} - \tau\ln N + \tau\ln\left(n + \sum_{i=n+1}^N e^{(x_{i}-x_{1})/\tau}\right), $$ which should converge as well to $x_{1}$. $\endgroup$
    – rcescon
    Feb 26 at 17:29
  • $\begingroup$ @rcescon You're right, that's an error of mine. I'll remove this second part. $\endgroup$
    – Abezhiko
    Feb 27 at 16:32

You must log in to answer this question.

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