Retrospective approximation algorithms for the multidimensional stochastic root-finding problem

The stochastic root-finding problem (SRFP) is that of solving a system of q equations in q unknowns using only an oracle that provides estimates of the function values. This paper presents a family of algorithms to solve the multidimensional (q ≥ 1) SRFP, generalizing Chen and Schmeiser´s one-dimensional retrospective approximation (RA) family of algorithms. The fundamental idea used in the algorithms is to generate and solve, with increasing accuracy, a sequence of approximations to the SRFP. We focus on a specific member of the family, called the Bounding RA algorithm, which finds a sequence of polytopes that progressively decrease in size while approaching the solution. The algorithm converges almost surely and exhibits good practical performance with no user tuning of parameters, but no convergence proofs or numerical results are included here.