提出新方法降低马尔可夫噪声下线性随机逼近的偏差
High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
- 用线性化分解偏差，发现主导项与步长α线性相关
- 引入理查森-罗姆伯格外推，消除主要偏差项
- 理论证明误差收敛速度达最优，适合高精度优化场景
本文研究在马尔可夫噪声下，带Polyak-Ruppert平均的线性随机逼近（LSA）算法的偏差与高阶误差界。针对固定步长α的版本，提出一种基于线性化技术的偏差新分解方法。分析表明，主导偏差项与α呈线性关系，无法通过PR平均消除。为此，采用理查森-罗姆伯格（RR）外推方法，有效抵消主导偏差项。推导出RR迭代点的高阶矩界，证明其主导误差项与原始平均LSA的渐近最优协方差矩阵一致。
原文摘要 · Abstract (English)
In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size $α$ and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in $α$ and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。