NON-EXPANSIVE TWO-TIME-SCALE STOCHASTIC APPROXIMATION: A FIXED-SCHEDULE ONE-QUARTER BARRIER AND BIAS-CORRECTED ACCELERATION

Research Question and Approach

This paper investigates the finite-time convergence of two-time-scale stochastic approximation (TTSA) where the slow dynamics are non-expansive rather than contractive. In this regime, the slow variable follows a stochastic Krasnoselskii–Mann (KM) iteration. Previous literature established a last-iterate mean-square residual rate of $O(k^{-1/4+o(1)})$. The authors seek to explain why this specific exponent appears and to determine if algorithmic modifications can improve it.

To do this, the authors first prove a finite-horizon lower bound showing that the classical KM residual scale is sharp for any fixed-schedule unregularized update. They then analyze how the fast-tracking error (the lag between the current fast iterate and the moving fast equilibrium) propagates into the slow recursion. By identifying this as a first-order leakage problem, they propose a residual-preconditioned oracle that effectively cancels the first-order dependence on the fast tracking error.

The authors provide three primary contributions:

1. Diagnosis of the 1/4-barrier: They show that the $k^{-1/4}$ rate is a consequence of the underlying KM dynamics combined with the first-order leakage of fast-tracking error into the slow oracle. This confirms that the bottleneck is not merely a consequence of the two-time-scale separation condition, but a fundamental limitation of the raw oracle structure.
2. Nested Bias Correction: By introducing a residual-preconditioned slow oracle in a nested Tikhonov-KM algorithm, the authors improve the total-sample complexity from $T^{-1/4+o(1)}$ to $T^{-1/3+o(1)}$. This improvement occurs because the preconditioned residual reduces the slow-oracle bias from first-order to second-order in the fast tracking error.
3. Single-Loop Acceleration: The authors demonstrate that the repeated inner-loop cost of the nested method can be avoided. By maintaining an online estimate of the preconditioner, a single-loop algorithm achieves a $T^{-1/2+o(1)}$ residual rate with $O(1)$ primitive samples per iteration.