Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence

Zixi Chen, Yumin Xu, Ruixun Zhang
9/14/2025
math.OCcs.LG

No confident code implementation found for this paper.

Abstract

The nonlinear two-time-scale stochastic approximation is widely studied under conditions of bounded variances in noise. Motivated by recent advances that allow for variability linked to the current state or time, we consider state- and time-dependent noises. We show that the Lyapunov function exhibits polynomial convergence rates in both cases, with the rate of polynomial delay depending on the parameters of state- or time-dependent noises. Notably, if the state noise parameters fully approach their limiting value, the Lyapunov function achieves an exponential convergence rate. We provide two numerical examples to illustrate our theoretical findings in the context of stochastic gradient descent with Polyak-Ruppert averaging and stochastic bilevel optimization.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity

84% match2024

Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way

82% match2024

Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications

80% match2024

Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation

80% match2026

Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning

79% match2024

Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise

79% match2024

Cite this paper

@article{chen2025convergence,
  title  = {Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence},
  author = {Zixi Chen and Yumin Xu and Ruixun Zhang},
  year   = {2025},
  eprint = {2509.11039},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2509.11039v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2509.11039.svg)](https://codeofpaper.com/paper/2509.11039)

Discussion