mlsanityData to 7 Oct 2026

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

arXiv 2401.09339 ↗First posted 17 Jan 2024stat.ML cs.LG math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

Two-timescale stochastic approximation (TTSA) is among the most general frameworks for iterative stochastic algorithms. This includes well-known stochastic optimization methods such as SGD variants and those designed for bilevel or minimax problems, as well as reinforcement learning like the family of gradient-based temporal difference (GTD) algorithms. In this paper, we conduct an in-depth asymptotic analysis of TTSA under controlled Markovian noise via central limit theorem (CLT), uncovering the coupled dynamics of TTSA influenced by the underlying Markov chain, which has not been addressed by previous CLT results of TTSA only with Martingale difference noise. Building upon our CLT, we expand its application horizon of efficient sampling strategies from vanilla SGD to a wider TTSA context in distributed learning, thus broadening the scope of Hu et al. (2022). In addition, we leverage our CLT result to deduce the statistical properties of GTD algorithms with nonlinear function approximation using Markovian samples and show their identical asymptotic performance, a perspective not evident from current finite-time bounds.

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

Builds on

48 of 110 references.

References · 48

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  3. 2019SGD: General Analysis and Improved Ratescited by 206
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  5. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
  6. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  7. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  8. 2019How Good is SGD with Random Shuffling?cited by 63
  9. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  10. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  11. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  12. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
36 more
  1. 2016Stochastic Heavy Ballcited by 40
  2. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  3. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  4. 2020Gradient Temporal-Difference Learning with Regularized Correctionscited by 38
  5. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  6. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  7. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  8. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  9. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  10. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  11. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  12. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  13. 2019Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximationcited by 18
  14. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 18
  15. 2022A principled framework for the design and analysis of token algorithmscited by 17
  16. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  17. 2019Two-Timescale Voltage Control in Distribution Grids Using Deep Reinforcement Learningcited by 15
  18. 2022On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Networkcited by 14
  19. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
  20. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 13
  21. 2020Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysiscited by 12
  22. 2023Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity -- the Strongly Convex Casecited by 12
  23. 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11
  24. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  25. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  26. 2018Concentration bounds for two time scale stochastic approximationcited by 8
  27. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
  28. 2023Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chainscited by 8
  29. 2016Stochastic Recursive Inclusions in two timescales with non-additive iterate dependent Markov noisecited by 7
  30. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  31. 2020First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approachcited by 5
  32. 2022Revisiting the central limit theorems for the SGD-type methodscited by 5
  33. 2016Two-Timescale Stochastic Dispatch of Smart Distribution Gridscited by 3
  34. 2019Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problemscited by 3
  35. 2023Stochastic Subgradient Methods with Guaranteed Global Stability in Nonsmooth Nonconvex Optimizationcited by 3
  36. 2020Dynamic social learning under graph constraintscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 2.

7 papers.

  1. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  2. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  3. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  4. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  5. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  6. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  7. 2026Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimizationcited by 0