Accelerated and Stable Convergence with Anchored Optimistic Method

技术摘要：基于锚定乐观方法的加速与稳定收敛

问题陈述
本文旨在解决单调变分不等式（VI）问题的求解挑战，这类问题广泛存在于极小极大优化（min-max optimization）、对抗训练以及多智能体强化学习中。具体目标是寻找一个解 $x^\star$，使得对于单调且 $L$-利普希茨（Lipschitz）的算子 $G$，满足 $G(x^\star) = 0$。

作者强调了现有一阶方法的三个关键局限性：

1. 计算成本： 经典的 Extragradient (EG) 方法在每次迭代中需要两次梯度评估，这使得它在仅能每步获取单个梯度的在线或随机设置中效率低下。
2. 随机环境下的稳定性： 虽然乐观方法（如 Popov 方法）将成本降低到单次梯度调用，但如果没有特定的改进，它们在随机环境中往往无法收敛，或者表现出振荡行为。
3. 次优的最后迭代率（Last-Iterate Rates）： 现有方法通常仅保证遍历（ergodic，即平均）意义下的收敛。对于最后迭代（即实际的最终迭代点），标准的 EG 方法在平方算子范数上达到 $O(1/k)$ 的速率，这并不符合已知为 $O(1/k^2)$ 的理论下界。此外，随机最后迭代保证通常依赖于方差缩减技术或增长的批量大小（batch sizes），这在常数批量（constant-batch）的在线学习中并不切实际。

方法论：广义锚定乐观方法 (GOMA)
作者提出了 GOMA，这是一个集成了两个关键机制的算法族：

1. 双时间尺度乐观更新： 基于广义乐观方法（Mokhtari 等人，2020），GOMA 采用了不同的步长来分别处理预测（探索）步骤和修正（更新）步骤。这种解耦增强了稳定性。
2. Halpern 型锚定： 受 Halpern 固定点迭代启发，GOMA 引入了一个将迭代点拉向初始点 $x_0$ 的锚定项。其更新规则定义为：
   $$\begin{aligned} y_k &= \beta_k x_0 + (1 - \beta_k)x_k - \gamma_k G(y_{k-1}) \\ x_{k+1} &= \beta_k x_0 + (1 - \beta_k)x_k - \eta_k G(y_k) \end{aligned}$$
   这里，$\beta_k$ 是一个趋于零的锚定系数（例如 $\beta_k = \frac{2}{k+6}$），而 $\gamma_k$ 和 $\eta_k$ 是步长。锚定项在瞬态阶段有效地为算子增加了人工的强单调性，从而加速收敛，同时在渐近意义上恢复原始问题。

论文分析了两种参数调度方案：

• 情况 I： 固定更新步长 $\eta^*$ 配合缩放后的探索步长。
• 情况 II： 固定探索步长 $\gamma^*$ 配合缩放后的更新步长。

核心贡献与结果

1. 确定性设置（单调利普希茨算子）：

   • GOMA 在平方算子范数 $\|G(x_k)\|^2$ 上实现了 $O(1/k^2)$ 的加速最后迭代收敛速率。
   • 该速率达到了此类算子的理论复杂度下界。
   • 分析提供了显式常数，并证明了 GOMA 通过伪固定步长方案实现这一最优速率，相比于之前的锚定方法（如 Anchored Popov），简化了超参数调优过程。

2. 随机设置（无界方差）：

   • 作者针对随机设置引入了一个简化的 单次调用变体（其中 $\gamma_k = 0$）。该变体在当前迭代点与初始点之间的锚定插值处评估算子。
   • 在状态相关噪声假设下（即噪声方差可以随 $\|G(x)\|^2$ 增长，即无界方差），该变体在平方算子范数上实现了 $O(1/\sqrt{k})$ 的最后迭代收敛速率。
   • 重要性： 据作者所知，这是在无约束设置下，针对随机单调利普希茨 VI 实现的首个最后迭代保证，且无需方差缩减技术或增长的批量大小。它在每次迭代中保持单样本的常数批量规模。

与现有工作的比较
论文将 GOMA 与几种最先进的方法进行了对比：

• 对比 Extragradient (EG) & FEG： 虽然 FEG 在确定性设置下达到 $O(1/k^2)$，但其随机保证通常需要增长的批量或有界方差。GOMA 通过单次调用和常数批量实现了鲁棒性。
• 对比方差缩减方法 (E-Halpern, RAIN++)： 这些方法实现了更快的速率（例如 $O(1/k)$ 或更好），但依赖于递归方差缩减或大规模批量快照。GOMA 通过牺牲部分最优速率，换取了在常数批量、无界噪声环境下运行的能力，且无需复杂的方差缩减机制。
• 对比 DSEG： 虽然 DSEG 处理了随机设置，但它在非仿射问题中往往失效，或者需要特定条件，而 GOMA 的锚定机制克服了这些问题。

意义与主张
论文声称 GOMA 在 VI 算法的设计空间中占据了一个独特的地位。它是唯一能同时保证以下特性的方法：

• 平方算子范数下的最后迭代收敛。
• 每次迭代仅需单次算子评估（单次调用）。
• 在无界、状态相关噪声下的收敛。
• 无需方差缩减或增长批量即可运行。

虽然 $O(1/\sqrt{k})$ 的随机速率（相当于 $O(1/\epsilon^4)$ 的样本复杂度）比方差缩减方法实现的 $O(1/\epsilon^2)$ 最优速率慢，但作者认为，GOMA 为那些方差缩减不可行或噪声结构为无界的场景提供了第一个可行的解决方案。实验证实，GOMA 在确定性负共单调（negative-comonotone）设置和具有乘性噪声的随机设置中均表现稳健，优于在类似条件下会发散或停滞的基准方法。

局限性与未来方向
作者承认，在不使用方差缩减的情况下，缩小 GOMA 的 $O(1/\epsilon^4)$ 复杂度与 $O(1/\epsilon^2)$ 下界之间差距仍是一个开放性问题。此外，目前的分析仅限于无约束问题；将这些保证扩展到约束设置（使用间隔函数/gap function）以及更广泛的算子类（如负共单调算子）被列为未来的研究方向。