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 $({\beta }_k)$, the classical KM residual scale $({\sum }_{i<N}{\beta }_i(1-{\beta }_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\mathrm{/}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\mathrm{/}4+o(1)}$, while the corrected oracle yields $T^{-1\mathrm{/}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\mathrm{/}2+o(1)}$ with $O(1)$ primitive samples per iteration.