# Root finding for stochastic function

Suppose we have a function $f(x)$ that we can only observe through some noise. We can not compute $f(x)$ directly, only $f(x) + \eta$ where $\eta$ is some random noise. (In practice: I compute $f(x)$ using some Monte Carlo method.)

What methods are available for finding roots of $f$, i.e. computing $x$ so that $f(x) = 0$?

I am looking for methods which minimize the number of evaluations needed for $f(x)+\eta$, as this is computationally expensive.

I am particularly interested in methods that generalize to multiple dimensions (i.e. solve $f(x,y) = 0, g(x,y) = 0$).

I'm also interested in methods that can make use of some information about the variance of $\eta$, as an estimate of this may be available when computing $f(x)$ using MCMC.

• I am not sure what are the right tags for this question, please help in re-tagging. – Szabolcs Apr 8 '14 at 23:22
• To be fair, I found Stochastic approximation, but very little practical information with examples or practical discussion of when it works well and when it doesn't. Most of the info is in academic papers which seem to require quite a bit of work to convert into a practical application. Another thing I found is the keyword Likelihood-free estimation which solves a very similar problem and there's more practical information available online. Is there anything else? References are welcome! – Szabolcs Apr 9 '14 at 0:38
• interesting problem. i suppose all the gradient methods go out the window – Aksakal Apr 9 '14 at 2:10
• also, in your case the problem is more difficult: you may control $var[\eta]$ through MC – Aksakal Apr 9 '14 at 2:19
• I'll add an extra 50 to Glen_b's bounty for a good answer. – Szabolcs Apr 13 '14 at 20:35