Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems

会议: NeurIPS 2026
arXiv: 2607.11056
领域: 优化/理论
关键词: 凸凹极小极大优化, 随机外梯度算法, 乐观梯度下降上升, 最后迭代收敛, 扰动正则化

一句话总结

针对随机光滑凸凹极小极大问题中 vanilla 外梯度与乐观梯度算法最后迭代发散的根本难题，本文提出一种基于二次扰动的单循环稳定框架（PS-EG 与 PS-OGDA），在标准有界方差随机预言机下首次证明了约束域上的非渐近最后迭代收敛保证（时间范围已知时受限原始-对偶间隙达 \(\mathcal{O}(T^{-1/4})\)，随时版本达 \(\mathcal{O}(T^{-1/5})\)，无约束梯度范数达 \(\mathcal{O}(T^{-1/4})\)）。

研究背景与动机

在现代机器学习与博弈论领域，光滑凸凹极小极大优化问题广泛存在于生成对抗网络（GANs）、对抗鲁棒性训练以及强化学习多智能体博弈中。对于确定性凸凹极小极大问题，外梯度算法（EG）与乐观梯度下降上升（OGDA）已展现出卓越的理论收敛性质，其最后迭代（last-iterate）在原始-对偶间隙上能够达到最优收敛界。而在随机优化场景中，尽管算法轨迹的遍历平均（ergodic / averaged iterates）在标准有界方差一阶随机预言机下能实现经典的 \(\mathcal{O}(T^{-1/2})\) 期望收敛速率，但遍历平均在实际应用中具有显著缺陷——实际部署通常直接输出优化器停止时的最后一步单点迭代（last iterate），且平均化操作可能彻底破坏稀疏性与流形结构。

然而，在随机噪声存在的情况下，分析并保证算法的最后迭代收敛面临着根本性的数学障碍。随机梯度的固有方差会在极小极大博弈动态中引入破坏性旋转与随机扰动，甚至在最简单的双线性问题（如 \(\min_x \max_y x^\top y\)）中，经典的随机外梯度算法（S-EG）与随机乐观梯度下降上升（S-OGDA）的最后迭代轨迹都会发生剧烈振荡甚至发散。以往尝试恢复最后迭代收敛的工作大多依赖于加强预言机假设（例如多点采样、小批量 mini-batch 或递归方差缩减 PAGE/STORM），或者在约束凸集上仅获得较慢的收敛率（如锚定镜像下降的 \(\widetilde{\mathcal{O}}(T^{-1/10})\) 或 \(\widetilde{\mathcal{O}}(T^{-1/7})\)），且要求强烈的紧集假设或 Lipschitz Hessian 条件。

本文的切入角度是回到优化动力学最本质的收缩性质：无需引入任何方差缩减技巧或增大批量，仅通过在目标函数中施加轻量且可控的二次强凸-强凹扰动，即可为原单调变分不等式系统注入急需的严格单调收缩力。核心 idea：引入二次扰动将凸凹问题转化为强凸强凹子问题，并构造单循环扰动外梯度（PS-EG）与乐观梯度（PS-OGDA）算法，通过“先证明到移动扰动鞍点的均方距离收缩、再基于均匀均方有界性转化至受限原始-对偶间隙及梯度范数”的统一两阶段分析体系，在标准有界方差预言机下直接建立约束与无约束域上的最优非渐近最后迭代收敛率。

方法详解

整体框架

本文针对约束随机光滑凸凹极小极大问题 \(\min_{\bm{x}\in\mathcal{X}}\max_{\bm{y}\in\mathcal{Y}} F(\bm{x},\bm{y}) \coloneqq \mathbb{E}_{\bm{\zeta}}[f(\bm{x},\bm{y};\bm{\zeta})]\) 展开研究，将其等价表述为单调变分不等式算子 \(V(\bm{u}) = [\nabla_{\bm{x}}F(\bm{x},\bm{y}); -\nabla_{\bm{y}}F(\bm{x},\bm{y})]\) 在约束集 \(\mathcal{U} = \mathcal{X}\times\mathcal{Y}\) 上的单调包含问题。整体算法机制首先在目标函数中引入二次正则化构造扰动算子 \(W(\bm{u}) = V(\bm{u}) + \tau \bm{u}\)，使算子具备 \(\tau\)-强单调性；随后在其上构建纯单循环的扰动外梯度（PS-EG）与扰动乐观梯度（PS-OGDA）更新法则；最后依据是否预先知晓总迭代步数 \(T\)，匹配固定扰动或递减扰动步长调度，分别驱动最后迭代点收敛。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["随机凸凹极小极大问题<br/>单调算子 V(u) + 有界方差预言机"] --> B["二次扰动强单调算子化<br/>构建 W(u) = V(u) + tau*u 诱导动力学收缩"]
    B --> C["单循环扰动迭代更新<br/>PS-EG 两次前向投影 / PS-OGDA 历史外推更新"]
    C --> D["两阶段收敛分析体系<br/>阶段一: 距离平方收缩 ||u_t - u*_tau||^2 递归界"]
    D --> E["受限原始-对偶间隙转化<br/>利用均方一致有界性将扰动误差转化为 G^R(u_t) 与梯度范数界"]
    E -->|已知总步数 T: 固定扰动| F["时域相关最优最后迭代保证<br/>G^R(u_T) 达 O(T^-1/4)"]
    E -->|未知总步数: 递减扰动调度| G["随时收敛最后迭代保证<br/>G^R(u_t) 达 O(t^-1/5) / PS-EG 无约束达 O(t^-1/4)"]

关键设计

1. 二次扰动强单调算子化：诱导动力学强收缩以克服随机发散

在常规随机极小极大博弈中，算子 \(V(\bm{u})\) 仅具有单调性（monotonicity），在存在梯度方差 \(\sigma^2\) 时无法提供阻止轨迹离心漂移的内向收缩力。为此，算法构造带参数 \(\tau > 0\) 的二次扰动目标函数： $\(F_\tau(\bm{x},\bm{y}) \coloneqq F(\bm{x},\bm{y}) + \frac{\tau}{2}\|\bm{x}\|^2 - \frac{\tau}{2}\|\bm{y}\|^2\)$ 对应的合成梯度算子为 \(W(\bm{u}) \coloneqq V(\bm{u}) + \tau \bm{u}\)。这一设计赋予了 \(W\) 严格的 \(\tau\)-强单调性（\(\langle W(\bm{u})-W(\bm{v}), \bm{u}-\bm{v}\rangle \geq \tau\|\bm{u}-\bm{v}\|^2\)）与 \((L+\tau)\)-Lipschitz 连续性。随机梯度估计直接沿用单次预言机返回的 \(\hat{W}_t = \hat{V}_t + \tau_t \bm{u}_t\)，不仅完全保留了原问题算子的单循环计算复杂度，而且在无需多重采样或历史方差跟踪的情况下，直接为迭代动力学注入了指数级收缩项 \((1-\eta_t \tau_t)\)。

2. 单循环扰动外梯度（PS-EG）与扰动乐观梯度（PS-OGDA）：保留经典结构的高效迭代

在获得扰动算子后，算法避免复杂的嵌套循环或近端点子问题，直接将经典的两大单极值加速技术移植到扰动流上： 对于 PS-EG，每步执行两次投影更新： $\(\bm{u}_{t+\frac{1}{2}} = \text{proj}_{\mathcal{U}}(\bm{u}_t - \eta_t \hat{W}_t), \qquad \bm{u}_{t+1} = \text{proj}_{\mathcal{U}}(\bm{u}_t - \eta_t \hat{W}_{t+\frac{1}{2}})\)$ 对于 PS-OGDA，利用前一步的梯度外推实现单次评估： $\(\bm{u}_{t+\frac{1}{2}} = \text{proj}_{\mathcal{U}}(\bm{u}_t - \eta_t \hat{W}_{t-\frac{1}{2}}), \qquad \bm{u}_{t+1} = \text{proj}_{\mathcal{U}}(\bm{u}_t - \eta_t \hat{W}_{t+\frac{1}{2}})\)$ 与已有的锚定梯度方法（如以固定基准点拉回的 \(\bm{u}_{\text{ref}}\) 机制）不同，PS-EG 在第二步中外推点 \(\bm{u}_{t+1/2}\) 上的收缩项天然来源于受扰动算子自身的自洽评估，从而彻底避免了额外的人工锚定漂移超参数调节，且严格支持任意闭凸约束集 \(\mathcal{U}\) 上的正交投影。

3. 两阶段收敛分析体系：从扰动鞍点距离到受限原始-对偶间隙的转化

由于扰动问题的鞍点 \(\bm{u}_\tau^\star\) 与原始未扰动问题的真实解集 \(\mathcal{U}^\star\) 存在偏差，建立最后迭代收敛的关键在于将算法对 \(\bm{u}_\tau^\star\) 的逼近转化为对原问题优化质量的度量。分析框架将其拆解为两个阶段： 第一阶段推导精细的一步均方距离递推关系，将强单调性带来的负二次项完整保留，证明了迭代点到扰动鞍点的距离界 \(\mathbb{E}[\|\bm{u}_t - \bm{u}_{\tau}^\star\|^2] \leq \epsilon_t\)； 第二阶段针对可能无界的闭凸约束集，通过证明序列均方一致有界性 \(\sup_{t\geq 0} \mathbb{E}[\|\bm{u}_t - \bm{u}^\star\|^2] \leq C\)，定义紧支撑集 \(\mathcal{B}_{\bm{x}} \times \mathcal{B}_{\bm{y}}\) 上的受限原始-对偶间隙（Restricted Primal-Dual Gap）： $\(\mathcal{G}^R(\bm{x},\bm{y}) \coloneqq \max_{\bm{y}'\in\mathcal{B}_{\bm{y}}} F(\bm{x},\bm{y}') - \min_{\bm{x}'\in\mathcal{B}_{\bm{x}}} F(\bm{x}',\bm{y})\)$ 利用 \(L\)-光滑性将误差精确分解为优化误差（optimization error）与近似误差（approximation error），确立了根本性的转换引理： $\(\mathbb{E}[\mathcal{G}^R(\bm{u})] \leq M_R \sqrt{\epsilon_t} + \frac{L\epsilon_t}{2} + \tau \cdot \text{const} = \mathcal{O}(\sqrt{\epsilon_t} + \tau)\)$ 由此将逼近误差的控制完美转化为参数 \(\tau\) 与方差累积项之间的代数权衡。

4. 调度机制：时域相关（Horizon-Dependent）与随时收敛（Anytime）调度设计

针对不同的实际场景，框架提供了两种步长与扰动配置： - 时域已知情况：选取固定扰动 \(\tau = T^{-1/4}\)。若采用正则化感知调和步长（regularization-aware harmonic stepsize）\(\eta_t = \frac{2}{\tau(t+b)}\)（其中偏移量 \(b = \Theta(\tau^{-2})\)），不仅能使收缩因子实现精确的伸缩累乘消去，而且能保证 \(\sum_t \eta_t^2 < \infty\) 维持均方有界，最终得出 \(\epsilon_T = \mathcal{O}(T^{-1/2})\)，代入转换引理直接获得 \(\mathcal{O}(T^{-1/4})\) 的受限间隙界； - 时域未知（随时）情况：采用递减扰动 \(\tau_t = \tau_0 (t+b)^{-1/5}\) 与递减步长 \(\eta_t = \eta_0 (t+b)^{-3/5}\)。此时需额外控制随时间移动的中心点漂移 \(\|\bm{u}_{\tau_t}^\star - \bm{u}_{\tau_{t+1}}^\star\| \leq \frac{|\tau_t - \tau_{t+1}|}{\tau_t}\|\bm{u}^\star\|\)，最终获得 \(\mathbb{E}[\mathcal{G}^R(\bm{u}_t)] = \mathcal{O}(t^{-1/5})\)；而在无约束设置下，通过构造确定性参考轨迹并建立随机跟踪误差界（Stochastic Tracking），PS-EG 进一步提升至 \(\mathcal{O}(t^{-1/4})\) 的梯度范数界。

损失函数 / 训练策略

在算法实现过程中，为确保收缩项能够严格主导随机噪声并抑制交叉误差，步长需满足平稳界限约束： - 对于固定扰动下的 PS-EG 与 PS-OGDA，要求 \(\sup_{t\geq 0} \eta_t \leq \min\left\{\frac{1}{\sqrt{48}(L+\tau)}, \frac{1}{4\tau}\right\}\)； - 对于随时递减方案，要求 \(\eta_t \leq \min\left\{\frac{\tau_t}{192(\tau_t-\tau_{t-1})^2}, \frac{1}{96(L+\tau_{t-1})}, \frac{1}{5\tau_t}\right\}\)，保证 Lyapunov 函数 \(\Phi_t\) 能够稳定递推衰减。

实验关键数据

主实验

论文对各具代表性的最后迭代随机算法在标准设置下的收敛速率与适用范围进行了理论与数值分析比较。在紧支撑闭凸约束域上，受限原始-对偶间隙与标准间隙重合：

方法	性能度量指标	理论收敛速率	需预知总步数 \(T\)	适用约束域	额外预言机/结构假设
Cai et al. (2022a)	梯度范数 \(\|V(\bm{u})\|\)	\(\mathcal{O}(T^{-1/3})\)	是	仅无约束	强随机预言机 (多点同样本采样 + 方差缩减)
Abe et al. (2025)	原始-对偶间隙 \(\mathcal{G}\)	\(\widetilde{\mathcal{O}}(T^{-1/7})\)	是	有约束	紧集约束 + 锚定项调优
Chen & Mazumdar (2024)	原始-对偶间隙 \(\mathcal{G}\)	\(\mathcal{O}(T^{-1/6})\)	是	有约束	紧集约束 + Hessian Lipschitz 连续性
PS-EG / PS-OGDA (本文, 固定步长)	受限原始-对偶间隙 \(\mathcal{G}^R\)	\(\mathbf{\mathcal{O}(T^{-1/4})}\)	是	任意闭凸集 (有界/无界)	无 (仅标准有界方差一阶预言机)
PS-EG / PS-OGDA (本文, 随时递减)	受限原始-对偶间隙 \(\mathcal{G}^R\)	\(\mathbf{\mathcal{O}(t^{-1/5})}\)	否	任意闭凸集 (有界/无界)	无 (仅标准有界方差一阶预言机)
PS-EG (本文, 随时无约束)	梯度范数 \(\|V(\bm{u})\|\)	\(\mathbf{\mathcal{O}(t^{-1/4})}\)	否	无约束	无 (仅标准有界方差一阶预言机)

消融实验

论文围绕扰动强度参数 \(\tau\) 在随机双线性问题（\(\min_x \max_y x^\top y + \text{noise}\)）中的动力学表现进行了系统的机制消融对比，揭示了强收缩与渐近偏差之间的基本权衡：

实验配置 (\(\tau\) 取值模式)	动力学行为与最后迭代状态	均方距离极限 / 渐近偏差	说明与收敛机理分析
\(\tau = 0\) (Vanilla S-EG / S-OGDA)	轨迹持续绕极限环旋转振荡并扩散	发散 / 无界	缺乏强单调阻尼，无法抵抗随机梯度噪声积累
\(\tau\) 过大 (\(\tau \gg T^{-1/4}\))	极快陷入稳定收缩区，方差极小	存在较大渐近偏差 (\(\mathcal{O}(\tau)\))	正则化过强导致扰动鞍点严重偏离原问题极值点
\(\tau\) 过小 (\(\tau \ll T^{-1/4}\))	收敛极度缓慢，方差累积占主导	随机扰动方差过大	动力学收缩阻尼不足，难以抵消方差带来的累积偏移
\(\tau = T^{-1/4}\) (最优平衡点)	快速收缩且逼近真实鞍点	平衡最优 (\(\mathcal{O}(T^{-1/4})\))	扰动近似偏差与优化方差累计达到理论最优平衡

关键发现

• 在无任何正则化的 vanilla 随机极小极大算法中，即使存在有界方差假设，最后迭代的发散具有普遍性，证明了扰动或锚定机制在随机环境中不可或缺。
• 引入二次扰动后，PS-EG 与 PS-OGDA 表现出几乎相同的收敛阶；但在随时无约束分析中，PS-EG 允许采用确定性参考轨迹跟踪分析直接规避均方有界性引理，从而解锁了更激进的递减步长并达成 \(\mathcal{O}(t^{-1/4})\)。
• 正则化感知调和步长通过引入 \(b = \Theta(\tau^{-2})\) 的大初始偏移，优雅地解决了长期存在的步长平方和有限性（保证全过程有界）与步长和充分大（保证收缩忘却初值）之间的矛盾。

亮点与洞察

• 极简即极致的扰动框架：没有引入复杂的方差缩减（VR）或递增批量（batch-size scheduling），算法更新形式与经典 EG/OGDA 几乎完全一致，计算开销与单步调用次数零增长。
• 突破紧集假设的受限原始-对偶间隙体系：以往关于最后迭代收敛的工作几乎全部受困于紧集假设以保证间隙有界；本文通过建立迭代点在均方意义下的全局一致有界性（Uniform Mean-Square Boundedness），成功将分析推广至全闭凸集乃至全空间。
• 优雅的随机参考轨迹跟踪技术（Stochastic Tracking）：在无约束 PS-EG 的分析中，绕开跟踪移动鞍点 \(\bm{u}_{\tau_t}^\star\) 的传统套路，转而对比同扰动场下的确定性参考序列 \(\bar{\bm{u}}_t\)，不仅证明了确定性序列梯度范数收敛至 \(\mathcal{O}(t^{-1/4})\)，而且证明了随机跟踪误差同样衰减至 \(\mathcal{O}(t^{-1/2})\)，为未来无约束随机博弈动力学分析开辟了新范式。

局限与展望

• 收敛速率与更强预言机方法的差距：在已知步长且无约束的情况下，本文的 \(\mathcal{O}(T^{-1/4})\) 略低于依赖多点同随机样本预言机的方差缩减方法所达到的 \(\mathcal{O}(T^{-1/3})\)，在标准预言机下能否达到 \(\mathcal{O}(T^{-1/3})\) 仍是开放问题。
• PS-OGDA 在随时设置下的收敛率次优：PS-OGDA 由于相邻步扰动算子变化引入的额外差分项，在随时无约束设置下未能套用参考轨迹跟踪，仍停留在 \(\mathcal{O}(t^{-1/5})\)，尚待统一。
• 向非凸-凹或结构性非单调问题的拓展：当前结论严格依赖凸凹性与算子单调性，将此类二次正则化扰动机制推广至满足 MBI 或弱单调条件的非凸极小极大优化是极具价值的后续方向。

相关工作与启发

• vs Abe et al. (2025) (锚定与自适应扰动梯度法)：Abe 等人基于锚定项在紧凸集上仅获得 \(\widetilde{\mathcal{O}}(T^{-1/7})\) 的最后迭代间隙；本文通过算子内部二次扰动与精细的一步收缩分析，在无紧集限制的一般闭凸集上显著提升到了 \(\mathcal{O}(T^{-1/4})\)。
• vs Cai et al. (2022a) (E-Halpern 方差缩减法)：Cai 等人取得了 \(\mathcal{O}(T^{-1/3})\) 的梯度范数收敛，但必须依赖于多点共享随机数采样及 PAGE 递归方差缩减机制，且无法处理约束集；本文完全立足于最纯粹的标准单点有界方差预言机，并通用支持约束投影。
• vs Sohrabi et al. (2026) (GOMA 乐观锚定法)：同期的 GOMA 算法仅针对无约束凸凹问题建立了梯度范数的 \(\mathcal{O}(T^{-1/4})\) 随时收敛；本文框架不仅在无约束梯度范数上取得相同保证，而且完备覆盖了约束凸凹极小极大问题的受限原始-对偶间隙。

评分

• 新颖性: ⭐⭐⭐⭐⭐ 巧妙利用二次微小扰动突破随机极小极大问题最后迭代收敛障碍，设计极其简洁有力。
• 实验充分度: ⭐⭐⭐⭐ 理论推导完备扎实，定理证明细致严谨，并辅以核心机制消融与动力学数值验证。
• 写作质量: ⭐⭐⭐⭐⭐ 结构清晰，问题背景阐述透彻，两阶段收敛分析体系层层递进，数学逻辑严丝合缝。
• 价值: ⭐⭐⭐⭐⭐ 解决了约束随机凸凹极小极大最后迭代收敛长期存在的收敛率瓶颈，为一阶博弈优化提供了标杆理论工具。

相关论文

• [NeurIPS 2026] On the Last-Iterate Convergence of Clipped Gradient Methods
• [NeurIPS 2026] Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
• [NeurIPS 2026] Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems
• [ICML 2025] Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
• [NeurIPS 2026] Capacity-Constrained Online Convex Optimization with Delayed Feedback