level: research
two-time-scale stochastic approximation methods are used when a system has fast and slow dynamics. the fast part contracts quickly to an equilibrium, while the slow part follows a non-expansive fixed-point iteration. previous work showed that the slow part's error decays at a rate of k^{-1/4} in the number of steps k. this paper proves that this rate is the best possible for standard methods, by establishing a lower bound that matches the observed performance.
the authors then propose a new approach that uses a residual-preconditioned slow oracle. this correction cancels the first-order effect of fast tracking errors on the slow update. by combining this with a nested tikhonov regularization, the algorithm achieves a faster total-sample convergence rate of t^{-1/3} instead of t^{-1/4}. the improvement comes from better handling of the interaction between the two time scales.
the results apply to problems where the slow map is non-expansive, such as certain reinforcement learning and optimization settings. the lower bound confirms that simple step-size tuning cannot beat the k^{-1/4} rate. the corrected algorithm offers a practical way to speed up convergence without changing the problem structure. the analysis relies on finite-horizon bounds and careful tracking of error propagation.
why it matters: faster convergence in two-time-scale methods can reduce training time for reinforcement learning and stochastic optimization tasks.