Retrospective approximation algorithms for stochastic root finding

The stochastic root-finding problem is to find the root of the equation g(x)=γ, where g(x) can be estimated. There are many applications, including continuous and convex stochastic optimization, which is the problem of finding the zero of the gradient function. We propose a family of retrospective approximation algorithms that numerically solve a sequence of sample-path equations with increasing sample sizes. Algorithms in the family differ by the choice of several parameters including the deterministic root-finding method, sample sizes, the stopping rule of the numerical search, the point estimator, and the stopping rule of the entire algorithm. Under weak conditions, retrospective approximation converges. We also propose a simple version of the family: bounding retrospective approximation. General use algorithm parameter values are suggested. In our empirical comparison with the classical approach of stochastic approximation, bounding retrospective approximation is more efficient and less sensitive to parameter values.