Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
CoRR(2024)
摘要
Two-timescale stochastic approximation (TTSA) is among the most general
frameworks for iterative stochastic algorithms. This includes well-known
stochastic optimization methods such as SGD variants and those designed for
bilevel or minimax problems, as well as reinforcement learning like the family
of gradient-based temporal difference (GTD) algorithms. In this paper, we
conduct an in-depth asymptotic analysis of TTSA under controlled Markovian
noise via central limit theorem (CLT), uncovering the coupled dynamics of TTSA
influenced by the underlying Markov chain, which has not been addressed by
previous CLT results of TTSA only with Martingale difference noise. Building
upon our CLT, we expand its application horizon of efficient sampling
strategies from vanilla SGD to a wider TTSA context in distributed learning,
thus broadening the scope of Hu et al. (2022). In addition, we leverage our CLT
result to deduce the statistical properties of GTD algorithms with nonlinear
function approximation using Markovian samples and show their identical
asymptotic performance, a perspective not evident from current finite-time
bounds.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要