21
$\begingroup$

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.

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

1 Answer 1

Reset to default
15
+150
$\begingroup$

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]

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ (+1) Having a question answered with a dissertation citation from 2013 is pretty awesome. $\endgroup$
    – Sycorax ♦
    Commented Apr 13, 2014 at 21:30
  • 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
    Commented May 13, 2014 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$
    – Heberto Mayorquin
    Commented Aug 17, 2018 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
    Commented Nov 15, 2018 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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