Two-Timescale Stochastic Approximation

Momentum

3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 14

Oct 7, 2026cs.LG

Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation

Constant-step stochastic approximation generally has a nonzero stationary mean error that persists under time averaging. This paper studies that error for nonlinear two-timescale recursions driven by an exogenous finite-state Markov chain. Under stated smoothness assumptions and conditions on the stationary distribution, we derive a first-order bias expansion whose error bound remains uniform as the slow step size becomes much smaller than the fast step size. Fast-manifold coordinates keep the associated covariance equation regular in this limit. For fast step

η

and slow step

\varepsilon

, the expansion reveals a mixed contribution

\varepsilon^2/η

alongside terms linear in each step size. This dependence matters for bias reduction: along power-law step-size paths, the bias exponents need not be integers, so Richardson--Romberg extrapolation requires weights matched to the path. An exactly solvable nonlinear Markov example verifies the coefficients. We verify localization for temporal-difference learning and compare finite-run extrapolation at equal update budgets. For finite runs, we bound the initialization error of tail averages on both timescales under an additional coupling assumption. In the special case of additive independent noise, signed third-moment cancellation yields a sharper remainder.

A. Ch. Madhusudanarao, Rahul Singh

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

Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Oct 6, 2026stat.ML

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For

\ell

-smooth games with an inner

μ

-PL inequality, we prove a complexity lower bound

Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})

, where

κ=\ell/μ

is the condition number,

σ^2

is the gradient variance, and

\varepsilon

measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as

o(κ^2)

. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Junsoo Ha

Optimization Convergence Analysis Min-Max Optimization Two-Timescale Stochastic Approximation Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Sep 28, 2026math.OC

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

We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contractive, while the slow iterate is projected onto a compact convex polyhedron. The associated projected ordinary differential equation may have a discontinuous vector field at the boundary, preventing a direct application of standard analyses based on Lipschitz vector fields. Using the Skorokhod map, we establish explicit high-probability bounds for tracking the moving fast equilibrium and the projected slow dynamics. These bounds separate martingale fluctuations, Markov-noise residuals, and the bias due to time-scale separation. A Lipschitz Lyapunov function satisfying a uniform decrease condition over fixed time intervals yields almost-sure convergence, with explicit last-iterate rates when the decrease admits a power lower bound. Under uniform Lyapunov contraction, polynomial step sizes yield joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to

1/3

. Under the additional assumption that the reduced slow update map is a Euclidean contraction, logarithmically separated step sizes improve the joint rate to

O(n^{-1/2}\log n)

almost surely, including for boundary equilibria. The same rate holds under a distinct geometric condition involving a strictly attracting face of a box and a fast equilibrium that is constant on that face. An actor-critic application achieves an almost-sure value-gap rate of

O(n^{-1}\log n)

relative to the optimum within the constrained policy class. Further applications include projected TD(0) and projected stochastic gradient descent. We also extend the analysis to projection of the fast recursion under Euclidean contractivity.

Rahul Singh, Vivek S. Borkar, Eric Moulines

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

Last-Iterate Convergence Stochastic Approximation Constrained RL Two-Timescale Stochastic Approximation

Ask PDF

Sep 24, 2026cs.LG

A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Significant research effort has been directed in recent years towards establishing both asymptotic and non-asymptotic convergence guarantees for two-timescale actor--critic algorithms, where the actor recursion is run on a slower timescale than the critic recursion. This work derives a uniform all-time concentration bound for the actor--critic algorithm with function approximation in the long-run average-reward setting. This bound helps us analyze the behavior of the actor parameter with high probability. We show that, after some finite time, the actor parameter enters a safe region and remains within it thereafter with high probability. Specifically, with probability at least

1-ε_1-ε_2

, the actor error

\Vert θ_k-θ^{*}\Vert

O\left(\frac{n_0^{3/4}}{k}\frac{1}{\sqrt{ε_2}}+\left(\frac{1}{n_0}\right)^{1/4}\log^{1/4}\left(\frac{1}{ε_1}\right)+\left(\frac{1}{n_0}\right)^{1/4}\right)

for all

k\geq n_0

and sufficiently large

n_0

. We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.

Prashansa Panda, Shalabh Bhatnagar

Department of Computer Science and Automation IISc Bangalore

Average-Reward RL Two-Timescale Stochastic Approximation Actor-Critic Methods

Ask PDF

Sep 17, 2026cs.LG

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

Two-timescale stochastic approximation (TTSA) is a fundamental tool for analyzing coupled iterative algorithms in reinforcement learning, optimization, and stochastic control. However, finite-time guarantees for nonlinear two-timescale schemes remain difficult to obtain, especially under constant step-sizes. In this paper, we study nonlinear TTSA with step-sizes

α\ggβ

. Under standard stability, regularity, and Markovian noise assumptions, we upper bound the mean-squared error and the bias of both iterates around their limiting equilibria. Our bounds scale as

O(α+β^2/α^2)

, which we prove to be tight when

β\leα^{3/2}

. The analysis separates the contributions of initial conditions, fast-timescale tracking error, Markovian dependence, and timescale coupling, thereby clarifying the origin of the

β^2/α^2

term. Our results reveal qualitative differences from the linear TTSA setting previously studied, showing that nonlinear dynamics introduce additional finite-time effects that are absent in the linear case.

Djamel Rassem Lamouri, Dorian Baudry, Nicolas Gast

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

Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Jul 15, 2026stat.ML

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

Non-expansive two-time-scale stochastic approximation is governed by a slow stochastic Krasnoselskii--Mann fixed-point iteration rather than by contraction to a unique equilibrium. We study this regime under a contractive fast map and a non-expansive reduced slow map. We first prove a finite-horizon lower bound showing that, for any prescribed slow stepsize schedule

(β_k)

, the classical KM residual scale

(\sum_{i<N}β_i(1-β_i))^{-1}

is worst-case sharp for the corresponding unregularized KM update. Combined with the raw fast-tracking leakage scale, this explains the previously observed

k^{-1/4+o(1)}

last-iterate mean-square residual exponent. We then introduce a residual-preconditioned slow oracle that cancels the first-order dependence on the fast tracking error. In a nested Tikhonov-KM algorithm, the uncorrected oracle yields total-sample rate

T^{-1/4+o(1)}

, while the corrected oracle yields

T^{-1/3+o(1)}

. This improvement comes from changing the slow-oracle bias from first order to second order in the fast error after all inner-loop samples are counted. Finally, we show that the repeated inner-loop cost of the nested method can be avoided in a smooth derivative-oracle model. A single-loop algorithm that tracks both the fast equilibrium and the leakage preconditioner online achieves

T^{-1/2+o(1)}

with

O(1)

primitive samples per iteration.

Dhruv Sarkar, Vaneet Aggarwal

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

Last-Iterate Convergence Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Jun 21, 2026cs.LG

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

Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed stochastic noise. Existing variance-reduction techniques typically rely on myopic magnitude checks, which fail to distinguish informative geometric signals from impulsive outliers. To resolve this, we propose \textbf{RQ-TTSA} (Robust Quantile-guided TTSA), a distribution-aware framework that leverages historical gradient buffers to estimate rolling quantiles for adaptive Huber-style clipping, effectively preserving local optimization geometry while strictly bounding effective variance. Theoretically, we provide a convergence analysis for quantile-guided TTSA under nonconvex-strongly convex assumptions with infinite-variance noise (

p \in (1,2]

), deriving a rate of

\mathcal{O}(T^{-\frac{p-1}{3p-2}})

that recovers optimal dependence on the heavy-tailed parameter. Empirically, across six diverse tasks, spanning heterogeneous vision benchmarks, dynamic games under momentum poisoning, and offline reinforcement learning, RQ-TTSA consistently outperforms state-of-the-art baselines by eliminating divergence spikes and ensuring stable convergence. Our method demonstrates significant robustness to hyperparameter variations and incurs negligible computational overhead (

\approx 2.7\%

increase), validating distribution-aware gradient control as a practical and necessary component for reliable bilevel learning.

Zhiyu Li, Xi Xuan, Davide Carbone

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

Stochastic Optimization Stochastic Approximation Bilevel Optimization Two-Timescale Stochastic Approximation Heavy-Tailed Stochastic Optimization

Ask PDF

Jun 21, 2026cs.LG

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

Many central machine learning tasks, from entropy tuning in reinforcement learning to equilibrating generative adversarial networks, are fundamentally stochastic root-finding problems rather than loss minimization. Yet, they are frequently forced into a minimization framework via squared residuals, introducing a critical flaw we identify as the Variance Trap. Standard bilevel minimization algorithms require estimating hypergradients involving implicit Jacobians; in stochastic settings, these terms act as noise amplifiers, destabilizing convergence. We formalize Root-Finding Bilevel Optimization (RF-BO) as a distinct problem class that bypasses this pathology. We propose a Jacobian-free solution using Two-Time-Scale Stochastic Approximation (TTSA) that updates directly along the root error, structurally avoiding variance amplification. We provide the first non-asymptotic convergence guarantees for TTSA in this setting under Markovian noise. Extensive experiments demonstrate the decisive advantage of this paradigm: compared to squared-residual and implicit-gradient baselines, our framework achieves a 2.6% top-1 accuracy gain in SimCLR, 17

\times

faster convergence in non-linear ODE control where baselines fail, significantly improved entropy stability in reinforcement learning, and an 11.1% quality improvement in generative modeling.

Zhiyu Li, Xi Xuan, Davide Carbone

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

Stochastic Approximation Bilevel Optimization Two-Timescale Stochastic Approximation Stochastic Optimization Convergence

Ask PDF

Jun 12, 2026cs.IT

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

Recent finite-time analyses of nonlinear two-time-scale stochastic approximation show that under contractive assumptions the slow iterate

Y_k

with stepsizes

β_k=Θ(k^{-1})

and

α_k=Θ(k^{-a})

a\in(1/2,1)

, generally satisfies a mean-square rate of order

k^{-a}

; decoupled

k^{-1}

rates require strong local linearity. We identify a sharp regularity-dependent boundary. In a rate-determining normal form where the slow drift contains a locally linear leakage and a nonlinear remainder of order

1+ρ

(

ρ\in[0,1]

), the uncorrected recursion satisfies

\mathbb{E}\|Y_k\|^2 \le C\bigl(k^{-1}+k^{-a(1+ρ)}\bigr),

and a matching scalar Gaussian lower bound shows that the slower term is unavoidable without modifying the update. Thus the decoupled

k^{-1}

rate is guaranteed for the uncorrected recursion exactly when

a(1+ρ)\ge 1

. This lower bound concerns only the naive update; it is not an information-theoretic obstruction. We demonstrate this by equipping the normal-form recursion with an auxiliary online bias estimator

M_{k+1}=M_k+γ_k(R(X_k)-M_k),\qquad β_k\llγ_k\llα_k,

and subtracting

M_k

from the slow update. Under the same stability, moment, and remainder assumptions, the corrected recursion achieves

\mathbb{E}\|\widetilde Y_k\|^2=O(k^{-1})

for every

ρ\in[0,1]

, including regimes where the uncorrected update provably suffers the slower rate. Finally, we prove localized transfer theorems that extend the phase-transition mechanism to general nonlinear TTSA in fast-manifold coordinates. The proofs are non-asymptotic and rely on two Abel-transform cancellations: one for the locally linear fast-error leakage, and one for the tracked nonlinear bias.

Dhruv Sarkar, Vaneet Aggarwal

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

Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Jun 1, 2026cs.LG

Pseudospectral Bounds for Transient Amplification in Coupled Gradient Descent

Coupled gradient descent - where the update of one parameter depends on another - arises naturally in bilevel optimization, two-time-scale stochastic approximation, and generative adversarial networks. When the coupled Jacobian is block-triangular, asymptotic stability is determined by the spectral radii of the diagonal blocks, yet transient amplification before convergence can be arbitrarily large due to non-normality. We develop a sharp pseudospectral theory for block-triangular Jacobians J = [[A, 0], [C, D]], proving Kreiss-constant bounds of the form K(J) <= 2/(1-γ) + ||C||/(4(1-γ)) when ρ(A), ρ(D) <= γ< 1 and A, D are symmetric, and establishing matching minimax lower bounds. We characterize the critical coupling threshold for spectral instability and extend the theory to nearly self-referential systems via a Neumann-series perturbation framework. As a consequence, we obtain a finite-horizon O(K(J)^2 log(1/δ)) iteration complexity bound. Framed as scaling laws for stochastic two-time-scale optimization, our results expose a non-asymptotic, instance-dependent regime of high-dimensional learning dynamics that is invisible to spectral-radius analysis. Experiments on linear-quadratic problems, IQC-based comparisons, and neural-network training confirm the theory.

Ahanaf Hasan Ariq

Ideal School and College

Stochastic Approximation Two-Timescale Stochastic Approximation Spectral Methods Gradient Descent Dynamics

Ask PDF

May 29, 2026cs.LG

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

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Vagul Mahadevan, Claire Chen, Shuze Daniel Liu +1

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

Stochastic Approximation Temporal-Difference Learning Two-Timescale Stochastic Approximation Stochastic Optimization Convergence

Ask PDF

May 19, 2026cs.LG

Adynamical systems view of training generativemodels and the memorization phenomenon

Using recent works of one of the authors (VSB) on collapse in generative models and two time scale dynamics in stochastic gradient descent in high dimensions, we give a system theoretic explanation of the memorization phenomenon in generative models. This relies purely on the dynamic aspects of the training phase. Specifically, we use a result of Austin [2016] to motivate a stylized model for the loss function for stochastic gradient descent (SGD) wherein the loss function has a strong dependence on some variables and weak dependence on the rest in a precise sense. This naturally leads to two distinct time scales in the constant step size SGD that is commonly used in machine learning. This fact has been used to explain the double descent phenomenon in SGD in Borkar [2026]. In conjunction with a mathematical model for collapse phenomenon in SGD developed in Borkar [2025a], we analyze the constant step size SGD using the recent results of Azizian et al. [2024] in order to explain the phenomenon of memorization wherein a generative model that is concurrently being tuned yields the same or similar outputs for significant stretches of time. This gives a novel perspective on the aforementioned phenomena reported in machine learning literature and their interrelationships, using a dynamical systems viewpoint.

Siva Athreya, Chiranjib Bhattacharya, Vivek S. Borkar

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

Neural Network Memorization Memorization in Generative Models Generative Modeling Two-Timescale Stochastic Approximation Neural Network Training Dynamics Stochastic Gradient Descent

Ask PDF

May 8, 2026cs.LG

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

Designing model-free algorithms for distributionally robust reinforcement learning (DRRL) poses fundamental challenges. The robust Bellman operator is nonlinear in the transition kernel, which makes one-sample Bellman updates biased, while the adversarial optimization underlying robustness makes robust evaluation computationally demanding. To address these difficulties, we consider the natural small-ambiguity regime under Kullback--Leibler ambiguity sets and propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional. This yields an approximate robust Bellman equation that removes the adversarial optimization while remaining first-order accurate in the ambiguity radius. To learn the fixed point of this approximate equation, we propose Mean-Variance Stochastic Approximation (MVSA), a model-free algorithm that uses only one-sample updates. This is achieved via a lifted stochastic approximation dynamics and a two-time-scale design. We then prove convergence and a central limit theorem for MVSA: its main iterate satisfies a central limit theorem at the canonical

n^{-1/2}

scale, with explicitly characterized asymptotic covariances. Finally, we validate our theoretical findings with a numerical experiment.

Shengbo Wang, Zexi Zhang

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

Stochastic Approximation Distributionally Robust RL Two-Timescale Stochastic Approximation Model-Free RL Robust RL

Ask PDF

Feb 14, 2025cs.LG

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

We consider linear two-time-scale stochastic approximation algorithms driven by martingale noise. Recent applications in machine learning motivate the need to understand finite-time error rates, but conventional stochastic approximation analyses focus on either asymptotic convergence in distribution or finite-time bounds that are far from optimal. Prior work on asymptotic central limit theorems (CLTs) suggests that two-time-scale algorithms may be able to achieve

1/\sqrt{K}

error in expectation, with a constant given by the expected norm of the limiting Gaussian vector. However, the best known finite-time rates are much slower. We derive the first nonasymptotic Wasserstein-1 CLT for linear two-time-scale stochastic approximation with Polyak-Ruppert averaging driven by martingale difference noise. As a corollary, we show that the expected error achieved by Polyak-Ruppert averaging decays at rate

1/\sqrt{K}

, which significantly improves on the rates of convergence in prior works.

Seo Taek Kong, Sihan Zeng, Thinh T. Doan +1

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

Stochastic Approximation Two-Timescale Stochastic Approximation

Ask PDF

Momentum

Related topics

Latest papers 14