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

arXiv:2607.13414v1 Announce Type: new
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 $(beta_k)$, the classical KM residual scale $(sum_{i