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

Abstract

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(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+ρ (ρ[0,1]), the uncorrected recursion satisfies \[ E\|Y_k\|^2 C (k^-1+k^-a(1+ρ) ), \] 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+ρ) 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), β_k γ_k α_k, \] and subtracting M_k from the slow update. Under the same stability, moment, and remainder assumptions, the corrected recursion achieves E\| Y_k\|^2=O(k^-1) for every ρ[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.

Reproductions