Convergence and error bounds for passive stochastic algorithms using vanishing step size (Q1917662)

The main goal of this work is to investigate the asymptotic properties of passive stochastic approximation algorithms with decreasing step size and window width. We obtain sufficient conditions for with probability one (w.p.1) convergence and we derive upper bounds of the estimation errors under rather general conditions. Various applications in control theory and optimization often require to find the solution of \(\overline f(x) = 0\) for some nonlinear function \(\overline f(\cdot)\). Very often either the form of the function is quite complex or it is not available at all; only noisy measurements are available. Thus one is forced to use methods such as stochastic approximation to resolve the problems. In many situations, however, both the input and output are subject to errors and the standard or traditional stochastic approximation methods are not applicable. Nevertheless, these problems fit into the framework of passive stochastic approximation, where unlike the traditional approach, passive strategies rather than active strategies are employed. The remainder of the paper is arranged as follows. The main assumptions and conditions, as well as statements of results, are gathered next. In Section 3 we present the proof of w.p.1 convergence. This is divided into two steps. In the first step, we obtain the w.p.1 boundedness of the iterates and in the second step, we establish the desired convergence property. In Section 4 we derive the upper bounds on the estimation errors. The main analytical techniques employed are perturbed Lyapunov function methods. Finally, some further remarks are made in Section 5.