Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximation

Aug 25, 2026

Finite-time decoupled convergence is studied for nonlinear two-time-scale stochastic approximation, where two coupled iterates evolve at different speeds via distinct step sizes. Prior linear results show that mean-square error convergence rates depend only on each step size, a property known as decoupled convergence; the nonlinear case is less understood. Under a nested local linearity assumption, finite-time decoupled convergence rates are established through cross-term analysis and fourth-order moment bounds. An illustrative counterexample shows that nonlinearity in the slow update alone can break decoupled convergence.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages69

Reading Time2 h 54 min

AccessFree to download

Introduction

Two-time-scale stochastic approximation and motivation

Problem setup and two-loop interpretation

Fast and slow time scales

Example: SGD with Polyak-Ruppert averaging

Main focus: finite-time decoupled convergence in nonlinear SA

Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximation Yuze Han [hanyuze97@ruc.edu.cn](hanyuze97@ruc.edu.cn) Center for Applied Statistics and School of Statistics Renmin University of China Beijing, China Xiang Li [lx10077@pku.edu.cn](lx10077@pku.edu.cn) School of Mathematical Sciences Peking University Beijing, China Zhihua Zhang∗ [zhzhang@math.pku.edu.cn](zhzhang@math.pku.edu.cn) School of Mathematical Sciences Peking University Beijing, China Editor: Peter Richtarik Abstract In two-time-scale stochastic approximation (SA), two iterates are updated at varying speeds using different step sizes, with each update influencing the other. Previous studies on linear two-time-scale SA have shown that the convergence rates of the mean-square errors for these updates depend solely on their respective step sizes, a phenomenon termed decoupled convergence. However, achieving decoupled convergence in nonlinear SA remains less understood. Our research investigates the potential for finite-time decoupled convergence in nonlinear two-time-scale SA. We demonstrate that, under a nested local linearity assumption, finite-time decoupled convergence rates can be achieved with suitable step size selection. To derive this result, we conduct a convergence analysis of the matrix cross term between the iterates and leverage fourth-order moment convergence rates to control the higher-order error terms induced by local linearity. To further investigate the necessity of local linearity for decoupled convergence, we also construct an example showing that, even when the fast-time-scale update is linear, the nonlinearity of the slow-time-scale update alone can destroy decoupled convergence. Keywords: two-time-scale stochastic approximation, finite-time convergence, decoupled convergence 1. Introduction Stochastic approximation (SA), initially introduced by Robbins and Monro (1951), is an iterative method for finding the root of an unknown operator based on noisy observations. This method has gained substantial attention over the past few decades, finding applications in stochastic optimization and reinforcement learning (Kushner and Yin, 2003; Borkar, 2009; Mou et al., 2020, 2022, 2023; Li et al., 2023b,a) . However, certain scenarios require ∗ . Corresponding Author ©2026 Yuze Han, Xiang Li, and Zhihua Zhang. License: CC-BY 4.0, see [https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/. Attribution)[. Attribution](https://creativecommons.org/licenses/by/4.0/. Attribution) requirements are provided at [http://jmlr.org/papers/v27/25-1449.html](http://jmlr.org/papers/v27/25-1449.html). Han, Li, and Zhang managing two iterates updated at different time scales using varying step sizes. Examples include stochastic bilevel optimization (Ghadimi and Wang, 2018; Chen et al., 2021; Hong et al., 2023), temporal difference learning (Sutton et al., 2009; Xu et al. , 2019; Xu and Liang, 2021; Wang et al., 2021) and actor-critic methods (Borkar and Konda, 1997; Konda and Tsitsiklis, 2003; Wu et al., 2020; Xu et al., 2020) . These cases highlight the limitations of traditional SA and underscore the need for a two-time-scale SA approach to better capture the complexities involved. In this paper, we study the two-time-scale SA (Borkar, 1997), a variant of the classical SA algorithm, designed to identify the roots of systems comprising two coupled, potentially nonlinear equations. We focus on two unknown Lipschitz operators, F : Rd x × Rdy → Rd x and G : Rd x × Rdy → Rd y, with the aim of finding the root pair (x⋆ , y⋆ ) satisfying (FG((xx ,, yy)) 00, (1) Given that F and G are unknown, we assume access to a stochastic oracle that provides noisy evaluations of F (x, y) and G (x, y) at any input pair (x, y) . Specifically, for any x and y, the oracle returns F (x, y) + ξ and G (x, y) + ψ where ξ and ψ represent noise components. Utilizing this stochastic

FAQs

What is decoupled convergence in two-time-scale stochastic approximation?

It refers to convergence rates of the mean-square errors that depend only on the respective step sizes, even though the two iterates influence each other through coupling.

What assumptions are used to obtain finite-time decoupled convergence for the nonlinear case?

The analysis relies on a nested local linearity assumption, enabling control of higher-order error terms via cross-term and fourth-order moment bounds.

Can decoupled convergence fail for nonlinear two-time-scale SA? Why?

Yes. Even if the fast-time-scale update is linear, nonlinearity in the slow-time-scale update alone can destroy decoupled convergence, as shown by a constructed example.

Aug 25, 2026

Uploaded by Valentina