A stopping rule for stochastic approximation

A stochastic approximation algorithm is a recursive procedure to find the solution to an unknown nonlinear equation via noisy measurements. In this paper, we present a stopping rule for a stochastic approximation. We show that there is a high probability that the distance between the exact solution and the candidate solution is less than a specified tolerance level when the stochastic approximation stops according to our stopping rule. Furthermore, the number of recursions required by the stopping rule is a polynomial function of the problem size.