Group Abstract Group Abstract

Message Boards Message Boards

Stochastic root finding with Mathematica

GROUPS:

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.

POSTED BY: Szabolcs Horvat
Answer
5 months ago

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.

POSTED BY: Daniel Lichtblau
Answer
5 months ago

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
POSTED BY: Szabolcs Horvat
Answer
5 months ago