分析双时间尺度随机优化的正态近似精度，揭示快慢尺度间的相互作用。
Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
- 基于凸距离度量，给出双时间尺度算法的非渐近正态近似界。
- 快慢尺度分离越大，最终迭代值的近似精度越高，但平均值反而下降。
- 首次提供线性双时间尺度算法的高阶矩界，对理论研究有独立价值。
本文建立了由鞅差或马尔可夫噪声驱动的线性双时间尺度随机逼近（TTSA）算法的正态近似精度的非渐近界。针对最终迭代值和Polyak-Ruppert平均两种情形，我们以概率分布间的凸距离为度量，推导了正态近似的误差界。分析揭示了快慢时间尺度间存在非平凡的交互作用：在最终迭代值情形下，随着时间尺度分离增大，正态近似速率提升；而在Polyak-Ruppert平均设置中，该速率反而降低。此外，我们还给出了线性TTSA算法误差的高阶矩界，可能具有独立研究意义。
原文摘要 · Abstract (English)
In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise. Focusing on both the last iterate and Polyak-Ruppert averaging regimes, we derive bounds for normal approximation in terms of the convex distance between probability distributions. Our analysis reveals a non-trivial interaction between the fast and slow timescales: the normal approximation rate for the last iterate improves as the timescale separation increases, while it decreases in the Polyak-Ruppert averaged setting. We also provide the high-order moment bounds for the error of linear TTSA algorithm, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。