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.

  • $\begingroup$ I am not sure what are the right tags for this question, please help in re-tagging. $\endgroup$ – Szabolcs Apr 8 '14 at 23:22
  • 3
    $\begingroup$ 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! $\endgroup$ – Szabolcs Apr 9 '14 at 0:38
  • $\begingroup$ interesting problem. i suppose all the gradient methods go out the window $\endgroup$ – Aksakal Apr 9 '14 at 2:10
  • $\begingroup$ also, in your case the problem is more difficult: you may control $var[\eta]$ through MC $\endgroup$ – Aksakal Apr 9 '14 at 2:19
  • $\begingroup$ I'll add an extra 50 to Glen_b's bounty for a good answer. $\endgroup$ – Szabolcs Apr 13 '14 at 20:35

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]

  • $\begingroup$ (+1) Having a question answered with a dissertation citation from 2013 is pretty awesome. $\endgroup$ – Sycorax Apr 13 '14 at 21:30
  • 1
    $\begingroup$ This one's google-fu is strong $\endgroup$ – bdeonovic Apr 14 '14 at 1:17
  • 1
    $\begingroup$ The first paper you cite is useful, but it should be noted that there's still quite a bit of work needed to put the methods in practice. $\endgroup$ – Szabolcs May 13 '14 at 14:16
  • $\begingroup$ It would be really nice if someone that went through the methods could give an estimation of how much of work does it take to go from the paper to the most simple implementation. Took a glance at the first paper and it seems quite dense. $\endgroup$ – Ramon Martinez Aug 17 '18 at 9:55
  • $\begingroup$ I think for these kinds of problems you can use stochastic gradient descent, see e.g. finzi.psych.upenn.edu/R/library/sgd/html/sgd.html $\endgroup$ – Tom Wenseleers Nov 15 '18 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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