mlsanityData to 7 Oct 2026

Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance

arXiv 2011.01868 ↗First posted 3 Nov 2020math.OC cs.LG cs.SYcited by 35

Not on the map. Why?

Abstract (arXiv)

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 O(1/k2/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.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 5; 2024: 9; 2025: 6; 2026: 6.

35 papers.

Sort:

By area:

  1. 2023Efficient Dataset Distillation via Minimax Diffusioncited by 81
  2. 2021Amortized Implicit Differentiation for Stochastic Bilevel Optimizationcited by 62
  3. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  4. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  5. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  6. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  7. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  8. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  9. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  10. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  11. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  12. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
23 more
  1. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  2. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 7
  3. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  4. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  5. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  6. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  7. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  8. 2024Learning to Control Unknown Strongly Monotone Gamescited by 4
  9. 2024Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applicationscited by 4
  10. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  11. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  12. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysiscited by 3
  13. 2022Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Modelscited by 2
  14. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  15. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  16. 2025LSAM: Asynchronous Distributed Training with Landscape-Smoothed Sharpness-Aware Minimizationcited by 0
  17. 2025Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependencecited by 0
  18. 2025Convergence and stability of Q-learning in Hierarchical Reinforcement Learningcited by 0
  19. 2026Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approachcited by 0
  20. 2026Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat Itcited by 0
  21. 2026Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimizationcited by 0
  22. 2026Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Accelerationcited by 0
  23. 2026ABC-Align: Prediction-Powered Alignment with Adaptive Bias Controlcited by 0