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)+η where η 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)+η, 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 η, as an estimate of this may be available when computing f(x) using MCMC.

**Answer**

You might find the following references useful:

Pasupathy, R.and Kim, S. (2011) The stochastic root-finding problem: Overview, solutions, and open questions. ACM Transactions on Modeling and Computer Simulation, 21(3). [DOI] [preprint]

Waeber, R. (2013) Probabilistic Bisection Search for Stochastic Root-Finding.

Ph.D dissertation, Cornell University, Ithaca. [pdf]

**Attribution***Source : Link , Question Author : Szabolcs , Answer Author : QuantIbex*