研究带状态和时间依赖噪声的非线性双时标随机逼近收敛速度。
Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence
- 引入状态与时间相关噪声，分析其对收敛速率的影响。
- 证明了在特定条件下收敛速率达指数级，其他情况为多项式。
- 适用于优化算法分析，如SGD与双层优化中的理论推导。
非线性双时标随机逼近在噪声方差有界条件下被广泛研究。受近期允许噪声与当前状态或时间相关进展的启发，本文考虑状态与时间依赖型噪声。我们证明，在两种情况下，李雅普诺夫函数均呈现多项式收敛速率，其收敛阶数取决于状态或时间相关噪声的参数。值得注意的是，当状态噪声参数充分趋近于极限值时，李雅普诺夫函数可实现指数收敛。通过两个数值实例验证理论结果，分别应用于带Polyak-Ruppert平均的随机梯度下降和随机双层优化。
原文摘要 · Abstract (English)
The nonlinear two-time-scale stochastic approximation is widely studied under conditions of bounded variances in noise. Motivated by recent advances that allow for variability linked to the current state or time, we consider state- and time-dependent noises. We show that the Lyapunov function exhibits polynomial convergence rates in both cases, with the rate of polynomial delay depending on the parameters of state- or time-dependent noises. Notably, if the state noise parameters fully approach their limiting value, the Lyapunov function achieves an exponential convergence rate. We provide two numerical examples to illustrate our theoretical findings in the context of stochastic gradient descent with Polyak-Ruppert averaging and stochastic bilevel optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。