STOCHASTIC-APPROXIMATION WITH AVERAGING AND FEEDBACK - RAPIDLY CONVERGENT ONLINE ALGORITHMS

Consider the stochastic approximation X(u+1) = X(u)+a(n)g(X(n).xi(n)), where 0 < a(n) -->0, Sigma(n) a(n) = infinity and {xi(n)} is the ''noise'' sequence, Suppose that a(n) -->0 slowly enough such that a(n)/a(n+1) = 1 + o(a(n)). Then various authors have shown that the rate of convergence of the average ($) over bar X(n) = 1/n Sigma(i=1)(n) X(i) is optimal in the sense that root n(X(n) - theta) converged in distribution to a normal random variable with mean zero and covariance V, where V was the smallest possible in an appropriate sense. V did not depend on {a(n)}. The analogs of the advantages of averaging extend to the constant parameter systems X(n+1) = X(n) + epsilon g(X(n),xi(n)) for small epsilon >0. The averaging method is essentially ''off line'' in the sense that the actual SA iterate X(n) is not influenced by the averaging. In many applications, X(n) itself is of greatest interest, since that is the ''operating parameter.'' This paper deals with the problem of stochastic approximation with averaging and with appropriate feedback of the averages into the original algorithm. It is shown both mathematically and via simulation that it works, very well and has numerous advantages. It is a clear improvement over the system X(n) by itself. It is fairly robust, and quite often it is much preferable to the use of the above averages without feedback. We will deal, in particular, with ''linear'' algorithms of the type appearing in parameter estimators, adaptive noise cancellers, channel equalizers, adaptive control, and similar applications. The main development mill be for the constant parameter case because of its importance in applications. But analogous results hold for the case where a(n) -->0.