Analysis of adaptive step-size SA algorithms for parameter tracking

We present proofs and data for adaptive step-size algorithms for tracking time-varying parameters when recursive stochastic approximation type algorithms are used. A classical problem in adaptive control and communication theory concerns the tracking of the best fit of a given form when the statistics or the parameters change slowly. A major, and yet unresolved, problem has been the choice of the step sizes in the tracking algorithm. An algorithm for adapting the step size using the same system measurements which are used for the tracking was suggested by Benveniste and various examples worked out by Brossier. The numerical results were very encouraging. But proofs were lacking. These proofs are supplied here together with supporting numerical data. The proofs are based on recent results in stochastic approximation. The adaptive step-size technique works very well indeed. Much supporting analysis is presented, particularly concerning the interpretation of certain stationary processes as “stationary” pathwise derivatives. Finite difference forms are also treated. These are mathematically simpler and can be applied to a wide variety of systems, even when the system is not well modeled. The data shows that they work well