首次给出两尺度随机逼近的非渐近中心极限定理，实现1/√n误差率
Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation
- 基于Polyak-Ruppert平均，建立非渐近中心极限定理
- 证明期望误差以1/√n速率衰减，优于以往结果
- 适用于需精确有限时间分析的机器学习场景
我们研究由鞅噪声驱动的线性两时间尺度随机逼近算法。近期机器学习应用推动了对有限时间误差率的理解需求，但传统随机逼近分析仅关注渐近分布收敛或远低于最优的有限时间界。已有研究表明，两时间尺度算法在期望下可能达到1/√n的误差，其常数由极限高斯向量的期望范数决定。然而，目前最佳已知的有限时间速率仍慢得多。本文首次针对带Polyak-Ruppert平均的两时间尺度随机逼近，建立了关于Wasserstein-1距离的非渐近中心极限定理。作为推论，我们证明了Polyak-Ruppert平均所实现的期望误差以1/√n速率衰减，显著优于先前工作。
原文摘要 · Abstract (English)
We consider linear two-time-scale stochastic approximation algorithms driven by martingale noise. Recent applications in machine learning motivate the need to understand finite-time error rates, but conventional stochastic approximation analysis focus on either asymptotic convergence in distribution or finite-time bounds that are far from optimal. Prior work on asymptotic central limit theorems (CLTs) suggest that two-time-scale algorithms may be able to achieve $1/\sqrt{n}$ error in expectation, with a constant given by the expected norm of the limiting Gaussian vector. However, the best known finite-time rates are much slower. We derive the first nonasymptotic central limit theorem with respect to the Wasserstein-1 distance for two-time-scale stochastic approximation with Polyak-Ruppert averaging. As a corollary, we show that expected error achieved by Polyak-Ruppert averaging decays at rate $1/\sqrt{n}$, which significantly improves on the rates of convergence in prior works.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。