Are there any existing tools or packages for stochastic root finding with Mathematica, preferably in more than one dimension?
The classical root finding problem seeks to approximate $x$ so that $f(x) = 0$, while minimizing the number of times $f$ needs to be evaluated. For example, Newton's method does this.
The stochastic root finding problem differs in that we cannot compute $f(x)$ directly. We can only compute $f(x) + \eta$ where $\eta$ is a noise term with mean zero. A real-world example would be when $f(x)$ is computed with some Monte Carlo method.
As a toy example, here's a small Monte Carlo integrator that computes $\int_0^x \sin^2 t \; dt$:
f[x_] := Sin[x]^2
n = 1000;
fun[x_?NumericQ] :=
With[{count = Round[n x]},
N@Total@UnitStep[f@RandomReal[x, count] - RandomReal[1, count]]/n
]
Two classes of methods I found are probabilistic bisection (only works in 1D) and the Robbins-Monro method. Robbins-Monro is related to Newton's method, but it's highly non-trivial as creating a usable iteration scheme involves making lots of choices, all of which can significantly impact the performance of the method. I am still researching the topic and would be interested in discussing with people who have had to solve similar problems in the past.
