Global Stochastic Recursive Algorithms

In a series of papers Saul Gelfand and myself ([1], [2]) have developed a theory of discrete-time stochastic recursive algorithms for obtaining the global minima of functions. These algorithms are generalizations of stochastic approximation algorithms which usually exhibit only local convergence. The key idea in our work is the elucidation of the role of a stochastic differential equation in the analysis of the recursive algorithm. This stochastic differential equation plays the same role as the ordinary differential equation plays in the analysis of ordinary stochastic approximation algorithms. In this talk ([4], [5]) I present a wide ranging generalization of these ideas to recursive algorithms which arise in adaptive parameter estimation, various signal processing algorithms, maximum likelihood estimation and quantization. These algorithms are global versions of algorithms presented in Beneveniste, Metivier and Priouret [3]. This work sheds new light on the behavior of ordinary stochastic approximation algorithms.