Stochastic root finding with Mathematica

Questions
, ,
1

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.

2

I’d try NMinimize[f[x,…]^2, x,…] to see if that gives anything useful. Probably would go with Method->“DifferentialEvolution” as the first method to try.

3

It appears that NMinimize uses BlockRandom with a fixed seed, so any stochastic function passed to NMinimize will always produce exactly the same result. I can work around this, just observing how NMinimize works. Example:

In[20]:= f[x_?NumericQ] := (Sow@RandomReal[]; x^2)

In[21]:= Last@Reap@NMinimize[f[x], x] == Last@Reap@NMinimize[f[x], x]
Out[21]= True