Search papers, labs, and topics across Lattice.
This paper investigates non-expansive two-time-scale stochastic approximation using a slow Krasnoselskii鈥揗ann fixed-point iteration, revealing that the classical KM residual scale is sharp for unregularized updates. By introducing a residual-preconditioned slow oracle, the authors improve the total-sample rate from $T^{-1/4+o(1)}$ to $T^{-1/3+o(1)}$, effectively reducing the bias from first to second order in fast tracking errors. Additionally, they propose a single-loop algorithm that achieves a rate of $T^{-1/2+o(1)}$ with minimal sample cost, optimizing the efficiency of the approach.
Achieving a total-sample rate improvement from $T^{-1/4+o(1)}$ to $T^{-1/2+o(1)}$ could redefine efficiency benchmarks in stochastic approximation methods.
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/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/4+o(1)}$, while the corrected oracle yields $T^{-1/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/2+o(1)}$ with $O(1)$ primitive samples per iteration.
