Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
This work addresses a theoretical gap for researchers in stochastic control, optimization, and machine learning, offering incremental improvements over existing linear-case results.
The paper tackles the lack of theoretical guarantees for nonlinear two-time-scale stochastic approximation, providing asymptotic convergence and finite-time analysis, and shows it achieves a convergence rate of O(1/k^{2/3}) in expectation.
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.