Two-Timescale Stochastic Approximation

Ask about this topic

Overview

Two-timescale stochastic approximation analyzes algorithms in which a fast variable tracks a changing target while a slower variable learns or optimizes using that tracking. It appears in settings such as actor-critic reinforcement learning, bilevel optimization, and stochastic root-finding, where separating update speeds can make complex problems tractable. Researchers use ODE and fast-manifold analyses, martingale and Markov-noise bounds, Lyapunov methods, and Polyak–Ruppert averaging to establish convergence, finite-time error rates, and central limit theorems. A central challenge is that nonlinear tracking bias, heavy-tailed or dependent noise, and projections can slow convergence, so current work studies sharper rate limits and corrections that reduce bias without costly inner loops.

Latest papers

CardsList

20 papers4 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

  1. Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs

    Oct 16, 2026Maxime BaeldeMarkov Decision ProcessesPrimal-Dual Optimization

    Antvoice, Paris, France

  2. Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation

    Oct 7, 2026A. Ch. Madhusudanarao, Rahul SinghRichardson ExtrapolationStochastic Approximation

    Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France

  3. Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games

    Oct 6, 2026Junsoo HaOptimization Convergence AnalysisMin-Max Optimization

  4. Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

    Sep 28, 2026Rahul Singh, Vivek S. Borkar, Eric MoulinesLast-Iterate ConvergenceStochastic Approximation

    Laboratoire de Recherche de l’EPITA, Paris, France · Indian Institute of Technology Bombay · Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, United Arab Emirates

  5. A Concentration Bound for Two-Timescale Actor-Critic Algorithm

    Sep 24, 2026Prashansa Panda, Shalabh BhatnagarAverage-Reward RLTwo-Timescale Stochastic Approximation

    Department of Computer Science and Automation IISc Bangalore

  6. The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes

    Sep 17, 2026Djamel Rassem Lamouri, Dorian Baudry, Nicolas GastStochastic ApproximationTwo-Timescale Stochastic Approximation

    Univ. Grenoble Alpes, CNRS, Inria Grenoble INP, LIG, 38000 Grenoble France

  7. Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

    Jul 15, 2026Dhruv Sarkar, Vaneet AggarwalLast-Iterate ConvergenceStochastic Approximation

    Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

  8. Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

    Jun 21, 2026Zhiyu Li, Xi Xuan, Davide CarboneStochastic OptimizationStochastic Approximation

    University of Science and Technology of China Hefei, China · City University of Hong Kong Hong Kong SAR, China · Laboratoire de Physique de l’École Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université de Paris Paris, France

  9. Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization

    Jun 21, 2026Zhiyu Li, Xi Xuan, Davide CarboneStochastic ApproximationBilevel Optimization

    University of Science and Technology of China · City University of Hong Kong · Laboratoire de Physique de l’École Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université de Paris

  10. Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It

    Jun 12, 2026Dhruv Sarkar, Vaneet AggarwalStochastic ApproximationTwo-Timescale Stochastic Approximation

    1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Purdue University

  11. Transient Amplification in Cascaded Gradient Methods: Exact Minimax Laws and Tracking without Resonance

    Jun 1, 2026Ahanaf Hasan Ariq, Davide WiestStochastic ApproximationTwo-Timescale Stochastic Approximation

    Ideal School and College

  12. Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

    May 29, 2026Vagul Mahadevan, Claire Chen, Shuze Daniel Liu +1Stochastic ApproximationTemporal-Difference Learning

    Metron, Reston, VA, USA · Division Office Physics, Math and Astronomy, California Institute of Technology, Pasadena, CA, USA · Data Science Lab, MIT, Cambridge, MA, USA +2

  13. Adynamical systems view of training generativemodels and the memorization phenomenon

    May 19, 2026Siva Athreya, Chiranjib Bhattacharya, Vivek S. BorkarNeural Network MemorizationMemorization in Generative Models

    International Institute for Theoretical Sciences, Survey No. 151, Hesarghatta Road, Shivakote Hobli, Bengaluru 560089, India · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru 560012, India · Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India

  14. Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL

    May 8, 2026Shengbo Wang, Zexi ZhangStochastic ApproximationDistributionally Robust RL

    Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

  15. Multirate Stein Variational Gradient Descent for Efficient Bayesian Sampling

    Apr 5, 2026Arash SarsharStein Variational Gradient DescentBayesian Inference

    Department of Computer Engineering and Computer Science, California State University, Long Beach, 90840, CA, USA

  16. Finite-Time Analysis of Projected Two-Time-Scale Stochastic Approximation

    Mar 31, 2026Yitao Bai, Thinh T. Doan, Justin RombergPolyak-Ruppert AveragingStochastic Approximation

    Department of Aerospace Engineering, University of Texas at Austin · Department of Electrical and Computer Engineering, Georgia Tech

  17. Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

    Mar 31, 2026Kaustubh Kartikey, Shalabh BhatnagarStochastic OptimizationStochastic Optimization Convergence

  18. Two-Time-Scale Learning Dynamics: A Population View of Neural Network Training

    Mar 20, 2026Giacomo Borghi, Hyesung Im, Lorenzo PareschiNeural Network Training DynamicsHyperparameter Optimization

    Maxwell Institute for Mathematical Sciences and School of Mathematical and Computer Sciences Heriot–Watt University, Edinburgh, UK · Department of Mathematics and Computer Science University of Ferrara, Italy

  19. Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approach

    Mar 15, 2026Mathukumalli VidyasagarStochastic ApproximationTwo-Timescale Stochastic Approximation

    Indian Institute of Technology Hyderabad, Kandi, Telangana 502285

  20. Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation

    Feb 14, 2025Seo Taek Kong, Sihan Zeng, Thinh T. Doan +1Stochastic ApproximationTwo-Timescale Stochastic Approximation

    Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801 USA · JP Morgan AI Research, Palo Alto, CA 94304 USA · Aerospace Engineering and Engineering Mechanics Department at University of Texas, Austin, Austin, TX 78712 USA