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

Dhruv Sarkar; Vaneet Aggarwal

stat.MLJul 15, 2026

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

Authors: Dhruv Sarkar, Vaneet Aggarwal

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

Abstract

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.

Explore similar work

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

Stochastic Approximation Finite Time Analysis Phase Transitions Transitions

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

Stochastic Approximation Large Deviations Theory

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

Stochastic Approximation Temporal Difference Soft Actor-Critic Optimization Convergence Analysis Temporal Scales

Ask PDF