Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would iteratively have to solve the following equation at iteration $n$:

$C = \sum_{1 \leq i \leq n}{e^{\frac{x_i}{T}}x_i}$ for $T$.

Each iteration $i$ an unknown $x_i$ will be observed and $C$ is a constant.

For the first iteration obtaining $T$ is trivial, but I have no clue how to do so for later iterations as it would involve logarithms of sums.

I could settle for a (crude) approximation, but I would like to limit the computation in each iteration, thus I would like to reuse $T$ or some other partial result (recursive formula) to avoid summing over all observations (as $n$ can become very large).

Thank you in advance for your help.

share|improve this question

3 Answers 3

Here is an idea that may work.

Assume we are interested in minimizing the expected value

\begin{equation*} f(T) := E_z[F(T,z)], \end{equation*} where $F'(T,z) = x(z)e^{x(z)/T}-C$. If the $z$'s are sampled independently, then $E_z[F'(T,z)]=f'(T)$, and you can run the Robbins-Monro iteration (stochastic gradient) to update

\begin{equation*} T_{k+1} = T_k - \alpha_k F'(T_k,z_k), \end{equation*} where $\alpha_k \propto 1/k$.

Assuming the theory applies to your case, in principle it'll lead to the following iteration:

\begin{equation*} T_{k+1} = T_k - \alpha_k(x_ke^{x_k/T_k}-C),\quad k \ge 0, \end{equation*} which only depends on updating our guess $T_k$ as every new example comes along. It solves the equation only in expectation (under additional assumptions that stochastic approximation usually requires)---but hopefully, this approximation suits your purpose.

share|improve this answer

I would just expand the exponents into the Taylor series with 100 terms or so and update the sums of powers, which have trivial cumulative dynamics. The programming issue is that summing $x_i^{100}$ directly even in the float point arithmetic is not very nice, so I would just keep the polynomial in the form $\sum_{k=0}^{100} (a_k/T)^k$ and update $a_k$ as $$ a_k'=(a_k^k+x_n^{k+1}/k!)^{1/k}=M\cdot(1+q^k)^{1/k} $$ where $M=\max(a_k,y_n)$, $q=\min(a_k,y_n)/\max(a_k,y_n)$, $y_n=(x_n)^{1+1/k}/v_k$ and $v_k=(k!)^{1/k}=exp(-\frac 1k\sum_{j=2}^k\log j)$. This way you should be able to get away with double precision arithmetic in all but most extreme cases and still have reasonable accuracy in the final answer.

Solving a polynomial (in $1/T$) equation of this form should not be a problem.

share|improve this answer

After some simple algebra, this is equivalent to the calculation of "internal rate of return" in finance, on which there is a large literature and many implementations (e.g. in Microsoft Excel).

In general, this can only be solved numerically, by a nonlinear root-finding algorithm. The function you're searching for the root of is bounded and smooth, so there's no problem of convergence. I recently implemented this using Brent's method, but bisection or the secant method work almost as well and are easier to implement.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.