Necessary and sufficient conditions for a stochastic approximation method (Q920524)

The simplest interpretation of the stochastic approximation (SA) problem is to estimate a zero \(\theta\) of an unknown function \(f:\;{\mathbb{R}}\to {\mathbb{R}}\) via a sequence of iterates \(X_ n\) which, rather than providing exact values \(f(X_ n)\), give only ``noise corrupted'' observations \(f(X_ n)+\xi_ n\), where \(\xi_ n\) denotes the random observation error. If f is thought to have enough monotonicity, say, were the graph of f to lie above that of \(y=-\rho (x-\theta)\) for \(x<\theta\) and below it for \(x>\theta\), for some positive constant \(\rho\), then \[ (1)\quad X_{n+1}=X_ n+a_ n(f(X_ n)+\xi_ n),\quad a_ n>0, \] supplies such a sequence \((X_ n)\). Equation (1) is the original recursive SA method: the Robbins-Monro method. In Stochastic Processes Appl. 17, 359- 367 (1984; Zbl 0537.62068), we gave necessary and sufficient conditions for convergence of \(X_ n\) to \(\theta\) with probability 1 (wp 1) that were in the form of laws of large numbers \[ (2)\quad a_ n\cdot \sum^{n-1}_{j=0}\xi_ j\to 0\quad as\quad n\to \infty,\quad wp\quad 1. \] It turned out that the rate of decrease of the step-sizes \(a_ n\) was critical in determining whether (2) was a necessary or a sufficient condition for \(X_ n\to \theta\). If \(a_ n\) decreased at least as rapidly (slowly) as c/n, \(c>0\), then (2) was necessary (sufficient) for convergence. In the paper cited above, as in almost all the SA literature, it was assumed that \(a_ n\to 0\) as \(n\to \infty\), thus enabling the convergence \(X_ n\to \theta\). In this note we ask if this condition \(a_ n\to 0\) is strictly necessary for the approximation of \(\theta\) in some useful probabilistic sense as \(n\to \infty\) and answer that it is not.