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

arXiv: https://arxiv.org/abs/2401.12764 · HTML: https://mlsanity.com/paper/2401.12764/

## Key facts

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

## Builds on (most cited first, 30 of 38)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance](https://mlsanity.com/paper/2011.01868/) (2020)
- [Robust Optimization over Multiple Domains](https://mlsanity.com/paper/1805.07588/) (2018)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation](https://mlsanity.com/paper/2002.02584/) (2020)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)

## Built on by (most cited first, 7 of 7)

- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Gaussian Approximation for Two-Timescale Linear Stochastic Approximation](https://mlsanity.com/paper/2508.07928/) (2025)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [ABC-Align: Prediction-Powered Alignment with Adaptive Bias Control](https://mlsanity.com/paper/2609.34374/) (2026)

## 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.