Two-Timescale Stochastic Approximation

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

21 papers0 papers in the last four weeks, down 100% on the four weeks before. 0.0% of all new papers.

  1. Federated TD Learning in Heterogeneous Environments with Average Rewards: A Two-timescale Approach with Polyak-Ruppert Averaging

    Nov 16, 2026Ankur Naskar, Gugan Thoppe, Abbasali Koochakzadeh +1Federated RLHeterogeneous Federated Learning

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  13. Multirate Stein Variational Gradient Descent for Efficient Bayesian Sampling

    Apr 5, 2026Arash SarsharStein Variational Gradient DescentBayesian Inference

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

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

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

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

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

    Mar 15, 2026Mathukumalli VidyasagarStochastic ApproximationTwo-Timescale Stochastic Approximation

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