How does a stochastic optimization/approximation algorithm adapt to a randomly evolving optimum/root with jump Markov sample paths |
| |
Authors: | G Yin C Ion V Krishnamurthy |
| |
Institution: | (1) Department of Mathematics, Wayne State University, Detroit, MI 48202, USA;(2) Department of Electrical Engineering, University of British Columbia, Vancouver, Canada, V6T 1Z4 |
| |
Abstract: | Stochastic optimization/approximation algorithms are widely used to recursively estimate the optimum of a suitable function
or its root under noisy observations when this optimum or root is a constant or evolves randomly according to slowly time-varying
continuous sample paths. In comparison, this paper analyzes the asymptotic properties of stochastic optimization/approximation
algorithms for recursively estimating the optimum or root when it evolves rapidly with nonsmooth (jump-changing) sample paths.
The resulting problem falls into the category of regime-switching stochastic approximation algorithms with two-time scales.
Motivated by emerging applications in wireless communications, and system identification, we analyze asymptotic behavior of
such algorithms. Our analysis assumes that the noisy observations contain a (nonsmooth) jump process modeled by a discrete-time
Markov chain whose transition frequency varies much faster than the adaptation rate of the stochastic optimization algorithm.
Using stochastic averaging, we prove convergence of the algorithm. Rate of convergence of the algorithm is obtained via bounds
on the estimation errors and diffusion approximations. Remarks on improving the convergence rates through iterate averaging,
and limit mean dynamics represented by differential inclusions are also presented.
The research of G. Yin was supported in part by the National Science Foundation under DMS-0603287, in part by the National
Security Agency under MSPF-068-029, and in part by the National Natural Science Foundation of China under #60574069. The research
of C. Ion was supported in part by the Wayne State University Rumble Fellowship. The research of V. Krishnamurthy was supported
in part by NSERC (Canada). |
| |
Keywords: | Stochastic approximation Stochastic optimization Nonsmooth-jump component Two-time scale Convergence and rate of convergence |
本文献已被 SpringerLink 等数据库收录! |
|