技术摘要：非线性双时间尺度随机逼近

1. 问题陈述

双时间尺度随机逼近 (TTSA) 涉及耦合递归，其中“快”迭代变量 $x_k$（步长 $\alpha_k$）追踪由“慢”迭代变量 $y_k$（步长 $\beta_k$）决定的移动目标，且满足 $\beta_k \ll \alpha_k$。虽然线性 TTSA 已知即使在快步长为 $\alpha_k = \Theta(k^{-a})$ 且 $a < 1$ 的情况下，也能使慢迭代变量实现解耦的均方收敛速率 $O(k^{-1})$，但非线性 TTSA 的行为则较难理解。

近期文献表明，对于非线性收缩型 TTSA，慢迭代变量可能会受限于更慢的速率 $O(k^{-a})$，除非满足强局部线性假设。本文解决的核心问题是：

1. 结构性问题： 什么样的特定特征决定了慢漂移（slow drift）是使慢迭代变量实现最优解耦速率 $O(k^{-1})$，还是实现较慢的快追踪速率 $O(k^{-a})$？
2. 算法性问题： 如果慢速率受限于非线性偏差，是否可以在不需要模拟器访问或预言机去偏（oracle debiasing）的情况下，通过修改更新规则来消除这种偏差并恢复 $O(k^{-1})$ 的速率？

2. 方法论与模型

作者使用一个局部标准型模型 (local normal-form model) 来隔离决定速率的项，从而从一般的 TTSA 机制中分离出来。令 $X_k$ 表示快追踪误差，$Y_k$ 表示慢误差。该模型定义为：
$$\begin{aligned} X_{k+1} &= (I - \alpha_k A)X_k + \alpha_k \xi_{k+1}, \\ Y_{k+1} &= (I - \beta_k B)Y_k + \beta_k \left( H X_k + R(X_k) + \zeta_{k+1} \right). \end{aligned}$$
其中：

• $H X_k$ 代表快误差向慢递归中的局部线性泄漏 (locally linear leakage)。
• $R(X_k)$ 是真正的非线性余项 (genuinely nonlinear remainder)，假设满足 $\|R(x)\| \leq L_R \|x\|^{1+\rho}$，其中 $\rho \in [0, 1]$。
• $\rho$ 衡量局部正则性：$\rho=0$ 对应 Lipschitz 余项，而 $\rho=1$ 对应二阶（泰勒）余项。
• 步长满足 $\alpha_k = \Theta(k^{-a})$ 且 $\beta_k = \Theta(k^{-1})$，其中 $a \in (1/2, 1)$。

分析依赖于非渐近有限时间界限 (non-asymptotic finite-time bounds)，并利用阿贝尔变换抵消 (Abel-transform cancellations)（分部求和）来处理误差的卷积。

3. 主要贡献与结果

A. 未经修正递归的锐利相变

本文建立了一个取决于正则性的、针对未修正慢迭代变量均方误差的锐利上界：
$$\mathbb{E}\|Y_k\|^2 \leq C \left( k^{-1} + k^{-a(1+\rho)} \right).$$
这导致了一个由量值 $a(1+\rho)$ 决定的相变 (phase transition)：

• 情况 1 ($a(1+\rho) \geq 1$)： 非线性偏差衰减足够快，使得慢迭代变量达到解耦速率 $O(k^{-1})$。这包括对于任何 $a > 1/2$，当 $\rho=1$（二阶余项）时的情况。
• 情况 2 ($a(1+\rho) < 1$)： 非线性偏差占主导地位，速率被限制在 $O(k^{-a(1+\rho)})$。

下界： 作者在 $H=0$（无线性泄漏）的标量高斯子类中证明了一个匹配的下界。他们表明 $\mathbb{E}[Y_k^2] \geq c_1 k^{-a(1+\rho)} + c_2 k^{-1}$。这证实了当 $a(1+\rho) < 1$ 时，对于未经修正的递归，较慢的速率是不可避免的，且该速率仅由非线性余项的非零均值引起，而非由线性项的不完美平均引起。

B. 收敛机制

• 线性泄漏 ($HX_k$)： 尽管 $X_k$ 的量级为 $\Theta(k^{-a/2})$，但线性项 $HX_k$ 并不会降低速率。因为 $X_k$ 满足一个稳定的递归，所以 $HX_k$ 可以使用涉及鞅差 $\xi_{k+1}$ 和一个递推项的恒等式进行重写。这两部分都可以通过阿贝尔变换抵消，平均降至 $O(k^{-1})$ 的噪声水平。
• 非线性余项 ($R(X_k)$)： 相比之下，$R(X_k)$ 起到了可预测偏差 (predictable bias) 的作用（并非鞅差）。其量级按 $\mathbb{E}\|R(X_k)\| \approx k^{-a(1+\rho)/2}$ 缩放。由于它不是中心化的，它不会平均降至 $O(k^{-1})$；相反，它会累积为一个缓慢变化的漂移，从而限制了收敛速率。

C. 在线偏差追踪 (超越下界)

论文证明了该下界是更新规则的障碍，而非信息论极限。作者提出了一种在线偏差追踪算法 (online bias-tracking algorithm)，引入了一个在中间时间尺度 $\gamma_k$（满足 $\beta_k \ll \gamma_k \ll \alpha_k$）上的辅助变量 $M_k$：
$$\begin{aligned} M_{k+1} &= M_k + \gamma_k (R(X_k) - M_k), \\ \tilde{Y}_{k+1} &= (I - \beta_k B)\tilde{Y}_k + \beta_k (H X_k + R(X_k) - M_k + \zeta_{k+1}). \end{aligned}$$
通过从慢更新中减去运行估计值 $M_k$，可以消除可预测的偏差。残差 $R(X_k) - M_k$ 变成了一个类鞅差，可以通过第二次阿贝尔变换进行处理。
结果： 修正后的递归实现了对于所有 $\rho \in [0, 1]$（包括未经修正递归失效的区域）的 $\mathbb{E}\|\tilde{Y}_k\|^2 = O(k^{-1})$。

D. 向一般非线性 TTSA 的局部转移

作者将这些结果从标准型扩展到一般非线性 TTSA 的快流形坐标 (fast-manifold coordinates) ($X_k = x_k - \lambda(y_k)$)。他们证明，只要满足以下条件，相同的相变机制仍然成立：

1. 快平衡流形 $\lambda(y)$ 足够光滑。
2. 漂移函数满足局部泰勒展开。
3. 满足局部矩估计。
   转移定理考虑了由移动流形引起的扰动，并表明相变在这些条件下依然存在。

4. 意义与主张

本文声称解决了文献中关于非线性 TTSA 收敛性的结构性歧义：

1. 对前人工作的完善： 它纠正了“局部线性是 $O(k^{-1})$ 的必要条件”这一二元观点。相反，它表明充分的正则性（$a(1+\rho) \geq 1$）即足以实现 $O(k^{-1})$，即使在没有严格线性性的情况下也是如此。
2. 算法解决方案： 它证明了对于一般的非线性余项，无需预言机访问，只需通过在中间时间尺度上追踪可预测偏差，即可恢复 $O(k^{-1})$ 的速率。
3. 锐利性： 下界确立了在给定假设下，所推导出的速率对于一类未经修正的递归是极小极大最优（minimax optimal）的。

这项工作依赖于非渐近证明和特定的技术工具（阿贝尔变换抵消），以分离线性泄漏（会平均掉）与非线性偏差（会累积）的影响。论文并不声称解决了全局稳定性问题，而是专注于局部误差动力学的有限时间收敛速率。