提出改进的双时间尺度随机逼近方法，显著提升收敛速度。
Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
- 引入残差预条件慢更新器，降低快速追踪误差影响
- 修正后达到采样总量 $T^{-1/3+o(1)}$ 收敛率，优于原 $T^{-1/4+o(1)}$
- 单循环算法实现 $T^{-1/2+o(1)}$ 速率，每轮仅需常数次采样
非扩张双时间尺度随机逼近由慢速随机Krasnoselskii-Mann固定点迭代主导，而非收敛到唯一平衡点。本文在快映射为压缩、慢映射为非扩张的前提下研究该情形。首先证明有限时域下存在下界：对任意指定慢步长序列 $(β_k)$，经典KM残差尺度 $(\sum_{i<N}β_i(1-β_i))^{-1}$ 在最坏情况下是紧的。结合原始快追踪泄漏尺度，解释了此前观察到的 $k^{-1/4+o(1)}$ 最后迭代均方残差指数。随后引入残差预条件慢查询器，消除对快速追踪误差的一阶依赖。在嵌套Tikhonov-KM算法中，未校正查询器总样本率为 $T^{-1/4+o(1)}$，校正后提升至 $T^{-1/3+o(1)}$。该改进源于将慢查询偏差从一阶转为二阶（在累计所有内层样本后）。最后表明，嵌套方法重复内层代价可避免；在平滑导数查询模型中，单循环算法在线跟踪快平衡与泄漏预条件器，实现 $T^{-1/2+o(1)}$ 速率，且每轮仅需 $O(1)$ 原始样本。
原文摘要 · Abstract (English)
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 $(β_k)$, the classical KM residual scale $(\sum_{i<N}β_i(1-β_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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。