Lune

AAAI2025Top-tier venue

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

Zixi Chen, Yumin Xu, Ruixun Zhang

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A Single-timescale Analysis for Stochastic Approximation with Multiple Coupled Sequences cites A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. A Finite-Time Analysis of Two Time-Scale Actor-Critic MethodsYue Wu, Weitong Zhang, Pan Xu, Quanquan GuNeurIPS 2020 · 189 citations
  2. A Single-timescale Analysis for Stochastic Approximation with Multiple Coupled SequencesHan Shen, Tianyi ChenNeurIPS 2022 · 25 citations

Related papers

  1. Gaussian Approximation for Two-Timescale Linear Stochastic ApproximationBogdan Butyrin, Artemy Rubtsov, Alexey Naumov, Vladimir V. Ulyanov et al.AAAI 2026 · 2 citations
  2. Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement LearningVagul Mahadevan, Claire Chen, Shuze D Liu, Shangtong ZhangICML 2026
  3. Convergence Rates of Stochastic Gradient Descent under Infinite Noise VarianceHongjian Wang, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Simsekli et al.NeurIPS 2021 · 57 citations
  4. Derivatives of Stochastic Gradient Descent in parametric optimizationFranck Iutzeler, Edouard Pauwels, Samuel VaiterNeurIPS 2024
  5. SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine VarianceAmit Attia, Tomer KorenICML 2023 · 34 citations
Dusk over the sea between two cliffs drawn in fine vertical lines