提出零阶多时标优化算法的有限时间分析，实现收敛性保障。
Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms
- 设计双时标梯度与三时标牛顿算法，用零阶估计梯度和海森矩阵。
- 证明算法在有限步内收敛至一阶驻点，误差界可量化。
- 适用于仿真优化场景，尤其适合无梯度信息的复杂系统优化。
本文针对基于仿真的优化问题，提出两种平滑函数随机近似算法的有限时间分析。第一种为双时标基于梯度的方法，第二种为三时标基于牛顿的方法，后者同时估计目标函数 $J$ 的梯度与海森矩阵。两类算法均采用零阶估计。尽管以往工作已证明其渐近收敛性，但此前未给出零阶设置下多时标随机优化算法的有限时间保证。本文为牛顿算法建立了海森矩阵估计的均方误差界，并推导出 $\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2$ 的有限时间上界，证明其收敛至一阶驻点。分析明确刻画了多时标间的交互作用及估计误差传播机制。进一步识别出平衡主导误差项的步长选择，实现接近最优的收敛速率。在相同框架下，也提供了梯度算法的相应有限时间保证。理论结果通过连续山地小车环境中的实验得到验证。
原文摘要 · Abstract (English)
We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function $J$. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on $\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2$, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。