mlsanityData to 13 Oct 2026

A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences

arXiv 2206.10414 ↗First posted 21 Jun 2022cs.LG math.OC stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). In this paper, we study the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, we seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for multi-sequence single-timescale SA (STSA). At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications. When all sequences have strongly monotone increments, we establish the iteration complexity of O(ε-1) to achieve ε-accuracy, which improves the existing O(ε-1.5) complexity for two coupled sequences. When all but the main sequence have strongly monotone increments, we establish the iteration complexity of O(ε-2). The merit of our results lies in that applying them to stochastic bilevel and compositional optimization problems, as well as RL problems leads to either relaxed assumptions or improvements over their existing performance guarantees.

Key facts. Cited by 17 papers in the map (data through 13 Oct 2026). Builds on 48 of its 81 references that are in the map. First posted on arXiv 21 Jun 2022.

Builds on

48 of 81 references.

References · 48

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,870
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,142
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 718
  4. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 404
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  6. 2018Approximation Methods for Bilevel Programmingcited by 234
  7. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 226
  8. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  9. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  10. 2020On the Iteration Complexity of Hypergradient Computationcited by 154
  11. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  12. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
36 more
  1. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  2. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  3. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  4. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  5. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 79
  6. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  7. 2017A First Order Method for Solving Convex Bi-Level Optimization Problemscited by 67
  8. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 66
  9. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  10. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  11. 2021A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inversecited by 53
  12. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  13. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  14. 2016Accelerating Stochastic Composition Optimizationcited by 46
  15. 2021Lower Bounds and Accelerated Algorithms for Bilevel Optimizationcited by 46
  16. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  17. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  18. 2020Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performancecited by 35
  19. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  20. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  21. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
  22. 2020Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Ratescited by 25
  23. 2018Multi-Level Stochastic Gradient Methods for Nested Composition Optimizationcited by 24
  24. 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
  25. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  26. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  27. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 22
  28. 2020Optimal Algorithms for Convex Nested Stochastic Composite Optimizationcited by 20
  29. 2020On the Convergence Theory of Debiased Model-Agnostic Meta-Reinforcement Learningcited by 19
  30. 2022Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-startcited by 17
  31. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  32. 2020A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimizationcited by 16
  33. 2021A Gradient Method for Multilevel Optimizationcited by 12
  34. 2022Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximizationcited by 11
  35. 2019A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximationcited by 10
  36. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 7; 2025: 5; 2026: 2.

17 papers.

Sort:

By area:

  1. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  2. 2024SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selectioncited by 64
  3. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  4. 2025Beyond Two-Stage Training: Cooperative SFT and RL for LLM Reasoningcited by 29
  5. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  6. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  7. 2024Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximationcited by 7
  8. 2024A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraintscited by 7
  9. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  10. 2024Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applicationscited by 4
  11. 2025In-memory Training on Analog Devices with Limited Conductance States via Multi-tile Residual Learningcited by 3
  12. 2026Dynamic Symmetric Point Tracking: Tackling Non-ideal Reference in Analog In-memory Trainingcited by 2
5 more
  1. 2026Rethinking Neural Network Learning Rates: A Stackelberg Perspectivecited by 1
  2. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  3. 2024Heavy-Ball Momentum Accelerated Actor-Critic With Function Approximationcited by 0
  4. 2025Mission-Aligned Learning-Informed Control of Autonomous Systems: Formulation and Foundationscited by 0
  5. 2025Convergence Rate in Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependencecited by 0