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

技术摘要：非扩张型双时间尺度随机近似

问题陈述
本文研究了在快映射为收缩映射、而简化后的慢映射仅为非扩张型的设定下，双时间尺度随机近似（TTSA）的收敛速率。这种设定常见于极小极大优化、变分不等式以及约束随机近似问题。与收缩型 TTSA（其中慢变量收敛至唯一的平衡点）不同，非扩张情形可能存在非单点的不动点集。因此，自然的性能指标是不动点残差 $p(y) = h(y) - y$，而非到特定点的距离。

先前的工作确立了在这种情形下，最后一次迭代（last-iterate）均方残差的速率为 $O(k^{-1/4+\epsilon})$。本文旨在解释该 $1/4$ 指数的理论起源，并确定算法改进是否能提升该速率。

方法论与理论框架
作者将误差动力学分解为两个截然不同的组成部分：非扩张慢递归的内在收敛性，以及快速追踪误差向慢算子的“泄漏”（leakage）。

1. 固定步长 KM 屏障的锐度（Sharpness of the Fixed-Schedule KM Barrier）：
   本文首先确立了经典的 Krasnoselskii–Mann (KM) 残差规模——即由 $\sum \beta_i(1-\beta_i)$ 的倒数定义的规模——对于任何固定的慢步长调度 $(\beta_k)$ 都是锐利的。通过一个平面旋转示例，作者证明了一个有限时界下界，表明对于给定的调度，任何未经正则化的 KM 更新都无法实现比该规模更快的最坏情况残差衰减。这意味着，若要提高速率，需要改变算法范式或算子结构，而不仅仅是精细化对标准 KM 更新的分析。

2. $1/4$ 指数的诊断：
   作者将“一阶快流形泄漏”（first-order fast-manifold leakage）识别为主要的障碍。在原始 TTSA 中，慢算子在当前的快迭代点 $X_k$ 处评估映射，而非在真实的平衡点 $x^*(Y_k)$ 处。由于慢映射在快坐标方向上的 Lipschitz 连续性，误差 $g(X_k, Y_k) - h(Y_k)$ 与追踪误差 $\|X_k - x^*(Y_k)\|$ 呈一阶关系。
   追踪误差本身受制于快随机方差 ($\alpha_k$) 与确定性滞后项 ($(\beta_k/\alpha_k)^2$) 之间的平衡。即使在满足标准分离条件 $\beta_k^2/\alpha_k^3 \lesssim 1$ 的情况下，由于尖锐的 KM 规模与这一一阶泄漏的共同作用，总样本复杂度仍为 $T^{-1/4+o(1)}$。违反分离条件并不能改善速率；它仅仅是将瓶颈从统计方差转移到了移动目标滞后，而后者仍然作为一阶扰动进入系统。

3. 通过残差预处理进行偏差修正（Bias Correction via Residual Preconditioning）：
   为了克服一阶泄漏，作者引入了一种残差预处理后的慢算子。通过利用快映射和慢映射的导数，他们构造了一个抵消对快追踪误差的一阶线性依赖关系的修正项。
   具体而言，若 $A(y) = I - \nabla_x f(x^*(y), y)$ 且 $C(y) = \nabla_x g(x^*(y), y)$，则预处理矩阵为 $P^*(y) = C(y)A(y)^{-1}$。修正后的算子定义为：
   $$H_{corr}(x, y) = g(x, y) + P^*(y)(f(x, y) - x)$$
   泰勒展开表明，该修正将慢算子的偏差从一阶（$O(\|e\|)$）降低到了二阶（$O(\|e\|^2)$），其中 $e$ 是快追踪误差。

主要贡献与结果

本文提出了三个主要理论结果，从对原始方法的诊断逐步过渡到在结构化算子假设下的优化算法。

1. 固定调度下界：
   作者证明，对于任何固定的慢步长调度，未经正则化的 KM 迭代的均方残差无法一致性地优于规模 $(\sum \beta_i(1-\beta_i))^{-1}$。这证实了前人工作中出现的 $1/4$ 指数并非分析松散导致的伪影，而是尖锐 KM 规模与一阶泄漏共同作用的结果。

2. 嵌套式偏差修正算法 ($T^{-1/3}$)：
   在嵌套 Tikhonov-KM 框架中，作者应用了残差预处理。

   • 未修正： 使用原始算子的嵌套方法其总样本速率为 $T^{-1//4+o(1)}$。
   • 已修正： 通过使用预处理后的算子，慢算子的平方偏差变为 $O(n^{-2})$（其中 $n$ 为内层采样数）而非 $O(n^{-1})$。这种结构性变化将总样本复杂度提升至 $T^{-1/3+o(1)}$。
   • 注： 此结果假设可以获取精确的预处理矩阵 $P^*(y)$ 或满足特定乘积精度条件的估计器。

3. 单循环学习型预处理算法 ($T^{-1/2}$)：
   为了避免嵌套法中重复调用内层求解的代价，作者提出了一种单循环算法，在线追踪快平衡点、慢变量以及预处理矩阵。

   • 该方法利用随机导数观测值，维护 $X_k$、$Y_k$ 和 $P_k$ 的运行估计。
   • 在平滑性假设下（映射的可微性以及可获得导数算子），该方法在每次迭代仅需 $O(1)$ 个原语样本的情况下，实现了 $T^{-1/2+o(1)}$ 的总样本速率。
   • 这一提升依赖于在线学习泄漏预处理矩阵的能力，从而有效地摊销了内层求解的成本。

意义与主张
本文声称为非扩张型 TTSA 中的 $1/4$ 指数提供了完整的理论解释，将其归因于尖锐 KM 残差规模与一阶快流形泄漏之间的相互作用。其主要贡献在于证明了这一屏障并非该问题类别的本质特征，而是特定于“原始”算子结构的。

通过引入残差预处理算子，作者展示了可以将泄漏降低至二阶，从而提升收敛速率。$T^{-1/3}$ 的结果证明了偏差修正的有效性，而 $T^{-1/2}$ 的结果则表明，如果具备导数信息，这些收益可以在单循环设定下实现。作者明确将这些结果界定为“结构化算子”的成就，指出它们依赖于可微性和对雅可比矩阵相关信息的获取，从而区别于黑盒非扩张不动点方法。本文并不声称解决了通用黑盒算子的问题，而是识别了在存在平滑性时加速收敛所需的特定结构化修改（即偏差抵消）。