mlsanityData to 7 Oct 2026

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

arXiv 2401.12764 ↗First posted 23 Jan 2024math.OC cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

This paper proposes to develop a new variant of the two-time-scale stochastic approximation to find the roots of two coupled nonlinear operators, assuming only noisy samples of these operators can be observed. Our key idea is to leverage the classic Ruppert-Polyak averaging technique to dynamically estimate the operators through their samples. The estimated values of these averaging steps will then be used in the two-time-scale stochastic approximation updates to find the desired solution. Our main theoretical result is to show that under the strongly monotone condition of the underlying nonlinear operators the mean-squared errors of the iterates generated by the proposed method converge to zero at an optimal rate O(1/k), where k is the number of iterations. Our result significantly improves the existing result of two-time-scale stochastic approximation, where the best known finite-time convergence rate is O(1/k2/3). We illustrate this result by applying the proposed method to develop new reinforcement learning algorithms with improved performance.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 38 of its 77 references that are in the map. First posted on arXiv 23 Jan 2024.

Builds on

38 of 77 references.

References · 38

  1. 2022Generative Adversarial Networkscited by 5,603
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2016Adversarial Machine Learning at Scalecited by 934
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  6. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  7. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  8. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  9. 2017The Numerics of GANscited by 104
  10. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  11. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  12. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
26 more
  1. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  2. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  3. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  4. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  5. 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 42
  6. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  7. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  8. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  9. 2018Robust Optimization over Multiple Domainscited by 34
  10. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  11. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  12. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  13. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  14. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  15. 2015Saddle-point dynamics: conditions for asymptotic stability of saddle pointscited by 17
  16. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  17. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14
  18. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  19. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  20. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  21. 2024Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximationcited by 10
  22. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  23. 2021Improved Convergence Rate for a Distributed Two-Time-Scale Gradient Method under Random Quantizationcited by 5
  24. 2020Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximationcited by 3
  25. 2020Distributed two-time-scale methods over clustered networkscited by 2
  26. 2021Convergence Rates of Distributed Consensus over Cluster Networks: A Two-Time-Scale Approachcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 1.

7 papers.

  1. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  2. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  3. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  4. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  5. 2025Gaussian Approximation for Two-Timescale Linear Stochastic Approximationcited by 5
  6. 2024Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applicationscited by 4
  7. 2026ABC-Align: Prediction-Powered Alignment with Adaptive Bias Controlcited by 0