Premium
Stochastic approximation: a survey
Author(s) -
Kushner Harold
Publication year - 2009
Publication title -
wiley interdisciplinary reviews: computational statistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.693
H-Index - 38
eISSN - 1939-0068
pISSN - 1939-5108
DOI - 10.1002/wics.57
Subject(s) - ode , mathematical proof , ordinary differential equation , convergence (economics) , rate of convergence , mathematics , stochastic approximation , stochastic process , stochastic differential equation , mathematical optimization , computer science , algorithm , differential equation , mathematical analysis , asynchronous communication , statistics , channel (broadcasting) , geometry , economic growth , economics , computer network
Stochastic recursive algorithms, also known as stochastic approximation, take many forms and have numerous applications. It is the asymptotic properties that are of interest. The early history, starting with the work of Robbins and Monro, is discussed. An approach to proofs of convergence with probability one is illustrated by a stability‐type argument. For general noise processes and algorithms, the most powerful current approach is what is called the ordinary differential equations (ODE) method. The algorithm is interpolated into a continuous‐time process, which is shown to converge to the solution of an ODE, whose asymptotic properties are those of the algorithm. There are probability one and weak convergence methods, the latter being the easiest to use and the most powerful. After discussing the basic ideas and giving some standard proofs, extensions are outlined. These include multiple time scales, tracking of time changing systems, state‐dependent noise, rate of convergence, and random direction methods for high‐dimensional problems. Copyright © 2009 John Wiley & Sons, Inc. This article is categorized under: Algorithms and Computational Methods > Stochastic Optimization