Regime switching stochastic approximation algorithms with switched ODE limit

TitleRegime switching stochastic approximation algorithms with switched ODE limit
Publication TypeConference Paper
Year of Publication2003
AuthorsYin, G., V. Krishnamurthy, and C. Ion
Conference NameDecision and Control, 2003. Proceedings. 42nd IEEE Conference on
Pagination900 - 905 Vol.1
Date Publisheddec.
Keywordsadaptive discrete stochastic approximation algorithm, approximation theory, asymptotic properties, CDMA wireless communication, code division multiple access, code division multiple access wireless communication, continuous time interpolation, continuous time systems, differential equations, finite state space, interpolation, Markov chain, Markov processes, Markovian jumps, Markovian parameters, motivation stems, ordinary differential equation, radiocommunication, recursive stochastic algorithms, regime switching stochastic approximation algorithms, spreading code optimization, state-space methods, step size algorithm, stochastic programming, switched ODE limit, switching diffusion, time varying signal, time-varying systems, tracking

Our objective is to treat tracking problems where the time-varying signal is a Markov chain with finite state space. The motivation stems from using recursive stochastic algorithms for tracking Markovian parameters such as those in spreading code optimization in CDMA wireless communication. We use constant step size algorithm to update the increments of a sequence of occupation measures. The usual stochastic approximation (SA) techniques cannot be carried over in the analysis due to the time-varying nature and Markovian jumps. Combining stochastic approximation method and two-time scale Markov chains, we develop asymptotic properties of the algorithm. The results are distinct from the usual SA results. We show that under suitable conditions, continuous-time interpolation of the iterates converges weakly to regime-switching ordinary differential equation. Then suitably scaled sequence of the tracking error is shown to converge to a switching diffusion. As an application of these results, the performance of an adaptive discrete stochastic approximation algorithm is analyzed.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia