Stochastic Approximation With Iterate-Dependent Markov Noise Under Verifiable Conditions in Compact State Space With the Stability of Iterates Not Ensured

• 成果类型: Article
• 署名作者: Karmakar, Prasenjit; Bhatnagar, Shalabh
• 署名单位: Indian Institute of Science (IISC) - Bangalore; Technion Israel Institute of Technology; Indian Institute of Science (IISC) - Bangalore; Bosch; Indian Institute of Science (IISC) - Bangalore
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3057299
• 发表日期: 2021
• 页码: 5941-5954
• 关键词: Adaptive algorithms; lock-in probability; Markov noise; Sample Complexity

摘要

This article compiles several aspects of the dynamics of stochastic approximation algorithms with Markov iterate-dependent noise when the iterates are not known to be stable beforehand. We achieve the same by extending the lock-in probability (i.e., the probability of convergence of the iterates to a specific attractor of the limiting ordinary differential equation (o.d.e.) given that the iterates are in its domain of attraction after a sufficiently large number of iterations (say) n(0)) framework to such recursions. Specifically, with the more restrictive assumption of Markov iterate-dependent noise supported on a bounded subset of the Euclidean space, we give a lower bound for the lock-in probability. We use these results to prove almost sure convergence of the iterates to the specified attractor when the iterates satisfy an asymptotic tightness condition. The novelty of our approach is that if the state space of the Markov process is compact, we prove almost sure convergence under much weaker assumptions compared to the work by Andrieu et al., which solves the general state-space case under much restrictive assumptions by providing sufficient conditions for stability of the iterates. We also extend our single-timescale results to the case where there are two separate recursions over two different timescales. This, in turn, is shown to be useful in analyzing the tracking ability of general adaptive algorithms. Additionally, we show that our results can be used to derive a sample complexity estimate of such recursions, which then can be used for step-size selection.