Adaptive stepsize selection for tracking in a non-stationary environment: a new pre-emptive approach

We consider the problem of using a stochastic approximation algorithm to perform online tracking in a non-stationary environment characterized by infrequent and sudden "regime changes". The primary contribution of this paper is a new approach for adaptive stepsize selection that is suitable for this type of non-stationarity. Our approach is pre-emptive rather than reactive, and is based on a strategy of maximising the rate of adaptation, subject to a constraint on the probability that the iterates fall outside a pre-determined range of "acceptable error". The theoretical basis for our approach is provided by the theory of weak convergence for stochastic approximation algorithms