提出新方法分析双时间尺度随机逼近,证明几乎必然收敛并给出更优误差速率。
Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach
- 用鞅方法分析算法,避免传统线性假设
- 误差平方均值以 o(t⁻⁹) 速率收敛,优于此前 O(t⁻²ᐟ³)
- 适用于带非零均值或无界方差的噪声,适用范围更广
本文采用鞅方法分析Borkar(1997)提出的双时间尺度随机逼近(TTSSA)算法。该方法给出了迭代有界性的简单充分条件,并估计了均方误差趋于零的收敛速率。理论适用于非线性方程,突破了多数文献对线性方程的限制。算法收敛性在“几乎必然”意义下被证明,优于以往的分布收敛、均值收敛等结果。首次建立了快慢子系统不同的收敛速率。当测量误差条件均值为零且条件方差有界时,均方误差以 o(t⁻⁹) 速率收敛,对所有 η∈(0,1) 成立,优于现有最佳结果 O(t⁻²ᐟ³)(Doan, 2023)。该速率接近于 Doan(2024)中针对 Polyak-Ruppert 平均版本得到的 O(t⁻¹),但并非直接对应。同时,也给出了误差具有非零条件均值和/或无界条件方差情形下的收敛速率。
原文摘要 · Abstract (English)
In this paper, we analyze the two time-scale stochastic approximation (TTSSA) algorithm introduced in Borkar (1997) using a martingale approach. This approach leads to simple sufficient conditions for the iterations to be bounded almost surely, as well as estimates on the rate of convergence of the mean-squared error of the TTSSA algorithm to zero. Our theory is applicable to nonlinear equations, in contrast to many papers in the TTSSA literature which assume that the equations are linear. The convergence of TTSSA is proved in the "almost sure" sense, in contrast to earlier papers on TTSSA that establish convergence in distribution, convergence in the mean, and the like. Moreover, in this paper we establish different rates of convergence for the fast and the slow subsystems, perhaps for the first time. Finally, all of the above results to continue to hold in the case where the two measurement errors have nonzero conditional mean, and/or have conditional variances that grow without bound as the iterations proceed. This is in contrast to previous papers which assumed that the errors form a martingale difference sequence with uniformly bounded conditional variance. It is shown that when the measurement errors have zero conditional mean and the conditional variance remains bounded, the mean-squared error of the iterations converges to zero at a rate of $o(t^{-η})$ for all $η\in (0,1)$. This improves upon the rate of $O(t^{-2/3})$ proved in Doan (2023) (which is the best bound available to date). Our bound is virtually the same as the rate of $O(t^{-1})$ proved in Doan (2024), but for a Polyak-Ruppert averaged version of TTSSA, and not directly. Rates of convergence are also established for the case where the errors have nonzero conditional mean and/or unbounded conditional variance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。