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)+η 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

Leave a Comment