Stochastic root finding via retrospective approximation

Given a user-provided Monte Carlo simulation procedure to estimate a function at any specified point, the stochastic root-finding problem is to find the unique argument value to provide a specified function value. To solve such problems, we introduce the family of Retrospective Approximation (RA) algorithms. RA solves, with decreasing error, a sequence of sample-path equations that are based on increasing Monte Carlo sample sizes. Two variations are developed: IRA, in which each sample-path equation is generated independently of the others, and DRA, in which each equation is obtained by appending new random variates to the previous equation. We prove that such algorithms converge with probability one to the desired solution as the number of iterations grows, discuss implementation issues to obtain good performance in practice without tuning algorithm parameters, provide experimental results for an illustrative application, and argue that IRA dominates DRA in terms of the generalized mean squared error.