论文标题
非线性两次尺度随机近似：收敛和有限的时间性能
Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
论文作者
论文摘要
两次尺度随机近似是流行的随机近似的广义版本，在许多领域都发现了广泛的应用，包括随机控制，优化和机器学习。尽管它很受欢迎，但这种方法的理论保证，尤其是其有限的时间性能，主要是在线性案例中实现的，而非线性对应物的结果非常稀少。由奇异扰动系统的经典控制理论的动机，我们在本文中研究了非线性两次尺度随机近似的渐近收敛和有限时间分析。在某些相当标准的假设下，我们提供了一种表征主要迭代趋于所需溶液的收敛速率的公式。特别是，我们表明该方法以$ \ MATHCAL {O}（1/k^{2/3}）$的速率达到了期望的融合，其中$ k $是迭代的数量。我们分析中的关键思想是正确选择两个步骤尺寸，以表征快速和缓慢尺度的迭代之间的耦合。
Two-time-scale stochastic approximation, a generalized version of the popular stochastic approximation, has found broad applications in many areas including stochastic control, optimization, and machine learning. Despite its popularity, theoretical guarantees of this method, especially its finite-time performance, are mostly achieved for the linear case while the results for the nonlinear counterpart are very sparse. Motivated by the classic control theory for singularly perturbed systems, we study in this paper the asymptotic convergence and finite-time analysis of the nonlinear two-time-scale stochastic approximation. Under some fairly standard assumptions, we provide a formula that characterizes the rate of convergence of the main iterates to the desired solutions. In particular, we show that the method achieves a convergence in expectation at a rate $\mathcal{O}(1/k^{2/3})$, where $k$ is the number of iterations. The key idea in our analysis is to properly choose the two step sizes to characterize the coupling between the fast and slow-time-scale iterates.
