首次给出重尾与长程依赖噪声下SA的有限时间收敛分析
Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis
- 用噪声平均法控制非经典噪声影响，不修改迭代过程
- 导出显式收敛率，量化重尾与时间相关性的危害
- 适用于强化学习、优化中的SGD与梯度博弈场景
随机逼近（SA）是强化学习与优化中的基础迭代框架。经典分析通常假设噪声为鞅差或具有有界二阶矩的马尔可夫噪声，但金融、通信等实际场景中常出现重尾与长程依赖（LRD）噪声。本文研究在强单调算子根求解问题下，带有此类非经典噪声的SA。首次建立了两种情形下的有限时间矩界，给出了显式的收敛速率，量化了重尾与时间依赖的影响。分析采用噪声平均策略，在不修改迭代的前提下正则化噪声作用。最后将通用框架应用于随机梯度下降（SGD）与梯度博弈，并通过数值实验验证了有限时间分析的有效性。
原文摘要 · Abstract (English)
Stochastic approximation (SA) is a fundamental iterative framework with broad applications in reinforcement learning and optimization. Classical analyses typically rely on martingale difference or Markov noise with bounded second moments, but many practical settings, including finance and communications, frequently encounter heavy-tailed and long-range dependent (LRD) noise. In this work, we study SA for finding the root of a strongly monotone operator under these non-classical noise models. We establish the first finite-time moment bounds in both settings, providing explicit convergence rates that quantify the impact of heavy tails and temporal dependence. Our analysis employs a noise-averaging argument that regularizes the impact of noise without modifying the iteration. Finally, we apply our general framework to stochastic gradient descent (SGD) and gradient play, and corroborate our finite-time analysis through numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。