An Invariant Measure Approach to the Convergence of Stochastic Approximations with State Dependent Noise.
Abstract
A new method is presented for quickly getting the ordinary differential equation associated with the asymptotic properties of a stochastic approximation (or the projected algorithm for the constrained problem). Either a(n) yields 0, or a(n) can be constant, in which case the analysis is on the sequence obtained when a yields 0.) The method basically requires that the stochastic approximation be Markov with a Feller transition function, but little else. The simplest result requires that if X sub n is equivalent to x, the corresponding noise process have a unique invariant measure; but the 'non-unique' case can also be treated. No mixing condition is required, nor the construction of averaged test functions, and f(.,.) need not be continuous. For the class of sequences treated, the conditions seem easier to verify than for other methods. There are extensions to the non-Markov case. Two examples illustrate the power and ease of use of the approach. Aside from the advantages of the method in treating standard problems, it seems to be particularly useful for handling the type of iterative algorithms which arise in adaptive communication theory, where the dynamics are often discontinuous and the 'noise' is often state dependent due to the effects of feedback.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1982
- Accession Number
- ADA119195
Entities
People
- Adam Shwartz
- Harold J. Kushner
Organizations
- Brown University