Asymptotics of Adaptive Algorithms

Examination of long term behavior of adaptive algorithms. For large excursions, algorithms are asymptotically Poisson distributed. Gives estimates of expected time to failure of adaptive control systems. Conditions for stability of the sign-sign LMS algorithm had eluded researchers for years. This paper derives the stability conditions and presents a powerful methodology (stochastic ODE's) for analyzing arbitrary small stepsize algorithms.

W. A. Sethares and J. A. Bucklew, "Excursions of adaptive algorithms via the poisson clumping heuristic," IEEE Trans. on Signal Processing, Vol. 40, No. 6, pp. 1443-1451, June 1992.

J. A. Bucklew, T. Kurtz and W. A. Sethares, "Weak convergence and local stability properties of fixed stepsize recursive algorithms," IEEE Trans. on Information Theory, Vol. 39, No. 3, May 1993.

More recently, we have been generalizing the approach to deal with a variety of practical issues.

R. Sharma, W. A. Sethares, and J. A. Bucklew, "Analysis of stochastic gradient based adaptive filtering algorithms with general cost function," IEEE Transactions on Signal Processing, Vol. 44, No. 9, Sept. 1996. [Analyzes stochastic gradient algorithms with general cost functions and gives asymptotic distibutions for leaky LMS, momentum algorithms, quantized state algorithms, and LMF.]

R. Sharma, W. A. Sethares, and J. A. Bucklew, "Stochastic analysis of the Sigma Delta modulator and differential pulse code modulator," IEEE Transactions on Circuits and Systems, Vol. 44, No.10, Oct. 1997. [Generalizes and applies the weak connvergence framework to various kinds of modulators. The effects of various input densities are characterized concretely.]

R. Sharma, W. A. Sethares, and J. A. Bucklew, "Analysis of momentum adaptive filtering algorithms," IEEE Transactions on Signal Processing, Vol. 46, No.5, 1430-1434, May 1998. [Generalizes the weak convergence framework to deal with non-identity transition matrices, and applies this to "momentum" algorithms. The effects of momentum on both stability and asymptotic convergence are characterized concretely.]

To get to my homepage, click here.