引言: 极小极大优化的高风险博弈

想象一个有两名玩家的游戏。一名玩家——最小化方 (Minimizer) ——希望某个值越小越好。另一名玩家——最大化方 (Maximizer) ——则希望同一个值越大越好。他们轮流行动,每一方都试图智取对方。这就是极小极大 (minimax) 问题的本质,一个位于许多现代机器学习核心的概念。

从训练能够生成逼真图像的生成对抗网络 (GANs) ,到构建能抵御对抗攻击的鲁棒 AI 模型,极小极大优化无处不在。其核心任务是解决如下形式的问题:

极小极大优化问题的一般形式。

极小极大优化问题的标准数学形式。

在这里,我们希望在第二名玩家在 \( y \) 上最大化函数 \( f(x, y) \) 之后,找到一个点 \( x \) 来最小化它。

当 \( f \) 在 \( x \) 上是凸的,在 \( y \) 上是凹的 (即凸–凹设定) 时,存在大量高效的算法。但在许多前沿应用中,\( f(x, y) \) 对最小化方是非凸的,对最大化方是非凹的。这个优化的“狂野西部”——非凸–非凹 (NC-NC) ——是出了名的困难且计算成本高昂。现有的算法要么过于复杂 (多循环结构) ,要么速度太慢,其收敛速度在大规模问题中不切实际。

正是在这里,一篇近期的 NeurIPS 2023 论文《A Single-Loop Accelerated Extra-Gradient Difference Algorithm with Improved Complexity Bounds for Constrained Minimax Optimization》登场了。作者提出了额外梯度差分加速 (Extra-Gradient Difference Acceleration, EGDA) 算法: 一种单循环方法——实现简单却速度惊人——它在理论上达到了 \( O(\epsilon^{-2}) \) 的复杂度,打破了此前 \( \widetilde{\mathcal{O}}(\epsilon^{-4}) \) 和 \( \widetilde{\mathcal{O}}(\epsilon^{-2.5}) \) 的界限。

在这篇文章中,我们将探讨为何极小极大优化如此具有挑战性,EGDA 是如何工作的,以及它在实践中的表现。


背景: 极小极大算法的全景

极小极大问题的类型

极小极大问题根据 \( f(x, y) \) 的“形状”而有所不同:

  • 凸–凹 (Convex–Concave, C-C) : 在 \( x \) 上是凸的 (像一个碗) ,在 \( y \) 上是凹的 (像一个倒置的碗) 。这是性质最好、最容易处理的设定。
  • 非凸–凹 (Nonconvex–Concave, NC-C) : 在 \( x \) 上是非凸的,但在 \( y \) 上是凹的。这在深度神经网络的对抗性训练中很常见。
  • 非凸–非凹 (Nonconvex–Nonconcave, NC-NC) : 在 \( x \) 上是非凸的,在 \( y \) 上也是非凹的。这是最一般且最困难的情况——寻找全局解是 NP-难的。

本文聚焦于具有挑战性的 NC-C 和 NC-NC 设定。

现有方法

最简单的方法是梯度下降–上升 (Gradient Descent–Ascent, GDA) : 将 \( x \) 沿 \(-\nabla_x f\) 方向移动,将 \( y \) 沿 \(+\nabla_y f\) 方向移动。不幸的是,对于许多问题,GDA 可能会陷入循环而无法收敛。

为了提高稳定性:

  • 多循环算法: 外循环更新一个变量,内循环为另一个变量解决优化子问题。理论上稳健,但实践中速度缓慢。
  • 单循环算法: 更实用,因为两个变量在同一个循环中更新。平滑 GDA (Smoothed-GDA) 向 \( f \) 添加平滑项以改善性质,但往往无法获得最优复杂度。

另一类是额外梯度 (Extra-Gradient, EG) 方法,它使用“预测–校正”序列: 先进行一个预测步,在新点处评估梯度,再用该梯度从原位置进行校正

额外梯度方法的通用预测–校正更新规则。

额外梯度框架在主更新前增加了一个稳定的预测步骤。


复杂度概览

下表比较了不同算法的复杂度。\( \epsilon \) 的指数越小,意味着算法向 \(\epsilon\)-驻点的收敛速度越快。

论文中的表1,比较了不同算法寻找函数 f 驻点的复杂度。所提出的工作在所有列出的类别中均达到最佳复杂度。

表1: EGDA 在 NC-C、C-NC 和 NC-NC 设置下均以 \( O(\epsilon^{-2}) \) 的复杂度领先。

论文中的表2,比较了在 NC-C 设置下寻找原始函数 φ 驻点的复杂度。所提出的工作将已知最佳结果从 O(ε⁻³) 改进到 O(ε⁻²)。

表2: EGDA 将原始函数 \( \phi \) 的已知最佳结果从 \( O(\epsilon^{-3}) \) 改进到 \( O(\epsilon^{-2}) \)。

挑战在于: 设计一个单循环直接加速的算法,在困难的极小极大问题上超越现有的最先进复杂度。


核心方法: 深入 EGDA 算法

EGDA 算法将标准的原始变量 \( x \) 更新与一个新颖的三部分加速对偶变量 \( y \) 更新相结合:

  1. 原始梯度下降 (x) :

原始变量 x 的更新规则。

近端梯度下降步骤使 \( x \) 朝减小 \( f \) 的方向移动,并将其投影回 \( \mathcal{X} \) 中。

  1. 额外梯度差分预测 (y) :

对偶变量 y 的新颖额外梯度差分预测步骤。

使用早期迭代点的梯度差构造预测点 \( u_{t+1/2} \)。

该梯度差分项作用类似二阶校正。在无需计算 Hessian 的情况下捕捉曲率信息,从而做出更聪明的更新。

  1. 梯度上升校正 (y) :

使用新预测点的梯度上升校正步骤。

从 \( y_t \) 出发,使用在 \( u_{t+1/2} \) 处的梯度进行标准的额外梯度校正。

  1. 动量加速 (y) :

最终确定 y 更新的动量加速步骤。

通过动量结合 \( y_t \) 和 \( u_{t+1} \) 以加快收敛速度。

这种对偶加速方案——梯度差分预测、校正与动量结合——是 EGDA 的核心创新。


理论关键: 准 Cocoercivity

在优化中,cocoercivity 有助于保证收敛,但在 NC-NC 问题中鲜有成立。EGDA 构造了一个称为准 cocoercivity 的性质:

Cocoercivity 的定义。它将梯度差的内积与梯度差的平方范数联系起来。

Cocoercivity 将梯度的内积与其范数联系起来——在非凸–非凹问题中极为罕见。

通过精心选择 \( u_{t+1/2} \),EGDA 保证了在证明所需的关键点上成立的类 cocoercivity 性质:

论文中的性质1,定义了准 cocoercivity 性质。

准 cocoercivity: 在构造点上具备类 cocoercivity 的性质。


收敛性保证与实验

最优性度量

一个 \(\epsilon\)-驻点是指梯度映射 \( \pi(\bar{x}, \bar{y}) \) 较小的点:

论文中的定义1,定义了用于衡量某点是否为 \\( f \\) 的 ε-驻点的梯度映射。

分析中引入了势函数 (potential function) \( G_t \):

收敛性分析中使用的势函数 G_t。

\( G_t \) 追踪目标函数值与进度指示器,并保证每次迭代递减。


主要结果

定理 1 (NC-NC) :

EGDA 在约束 NC-NC 设置下的复杂度界限。

EGDA 在 NC-NC 问题中实现了 \( O(\epsilon^{-2}) \) 复杂度——这是单循环算法前所未有的。

定理 2 (NC-C,原始函数 \( \phi \)) :

EGDA 在约束 NC-C 设置下对原始函数 φ 的复杂度界限。

EGDA 将已知的最佳 NC-C \( \phi \) 复杂度从 \( \widetilde{\mathcal{O}}(\epsilon^{-3}) \) 改进到 \( O(\epsilon^{-2}) \)。


实验结果

1. 玩具 NC-NC 问题:

论文中的图1,展示 EGDA (黑色菱形) 在示例 NC-NC 问题上收敛明显快于其他方法。

无论是在解的距离还是梯度范数上,EGDA (黑色菱形) 的收敛速度均明显快于 GDA、EG 和 FEG。

2. 凸–凹问题:

论文中的图2,展示了 EGDA 在凸–凹问题上的快速收敛。

即使在凸–凹设定下,EGDA 的收敛速度也超过了 GDA 和 EAG。

3. 对抗鲁棒神经网络训练 (NC-C) :

论文中的图3,比较了不同算法在鲁棒神经网络训练中的损失变化。EGDA (红色实线) 在两个数据集上均最快地降低了损失。

在 MNIST 和 Fashion-MNIST 数据集上,EGDA 更快的理论收敛率转化为比 Smoothed-GDA、MGDA 和 GDA 更快的损失下降。


结论与启示

通过引入额外梯度差分加速 (EGDA) 算法,这项工作在极小极大优化的速度与简洁性方面实现了飞跃:

  • 新颖加速方案: 一种对偶变量加速机制,其梯度差分步骤可从一阶信息中捕捉二阶效应。
  • 最先进复杂度: 在约束 NC-NC、NC-C 和 C-NC 问题中实现 \( O(\epsilon^{-2}) \) 复杂度,在更弱假设下改进或匹配已知的最佳结果。
  • 实践意义: 单循环的简洁性、验证过的更快收敛速度,以及在对抗训练等领域的真实性能提升。

这种新方法不仅带来了更优的算法,还提供了一种新颖的分析技巧——精心构造的准 cocoercivity——用于解决非凸–非凹优化。EGDA 框架表明,通过合理设计,我们可以在优化中打破速度极限,为在 GANs、强化学习与对抗防御等领域实现更快、更鲁棒的 AI 打开大门。