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.