Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
This work addresses a theoretical gap in iterative methods for optimization, reinforcement learning, and control, but it is incremental as it broadens existing analyses rather than introducing a new paradigm.
The paper tackles the finite-time analysis of two-time-scale stochastic approximation algorithms by extending it to settings where the slower time-scale has a non-expansive mapping, showing that the last-iterate mean square residual error decays at a rate of O(1/k^{1/4-ε}) and establishing almost sure convergence to fixed points.
Two-time-scale stochastic approximation algorithms are iterative methods used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of these algorithms has primarily focused on fixed point iterations where both time-scales have contractive mappings. In this work, we broaden the scope of such analyses by considering settings where the slower time-scale has a non-expansive mapping. For such algorithms, the slower time-scale can be viewed as a stochastic inexact Krasnoselskii-Mann iteration. We also study a variant where the faster time-scale has a projection step which leads to non-expansiveness in the slower time-scale. We show that the last-iterate mean square residual error for such algorithms decays at a rate $O(1/k^{1/4-ε})$, where $ε>0$ is arbitrarily small. We further establish almost sure convergence of iterates to the set of fixed points. We demonstrate the applicability of our framework by applying our results to minimax optimization, linear stochastic approximation, and Lagrangian optimization.