Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points¶

会议: NeurIPS 2026
arXiv: 2602.10565
OpenReview: https://openreview.net/forum?id=Z7Fzxtf74w
领域: 其他
关键词: 在线极小极大优化, 累积鞍点, 静态对偶间隙, 动态鞍点遗憾, 极小极大指数凹性

一句话总结¶

针对时序零和博弈中最小化个体遗憾无法保证收敛至累积鞍点的根本缺陷，本文提出以静态对偶间隙与动态鞍点遗憾为核心的在线极小极大优化框架，证明了 OGDA 与 OMMNS 算法的对数阶界与鞍点收敛性，并确立了非凸非凹两面 PL 条件下的动态遗憾界及静态纳什均衡遗憾的不可能性定理。

研究背景与动机¶

在线凸优化（OCO）作为序贯决策的基石理论，经过数十年发展已建立了完备的静态与动态遗憾分析体系，通常在一般凸与强凸条件下分别可达 $\Theta(\sqrt{T})$ 与 $\Theta(\log T)$ 的最优界。然而，在对抗机器学习、多智能体强化学习与鲁棒风险控制中广泛出现的极小极大博弈场景下，环境收益函数随时间动态演化。近年来针对时序变化零和博弈（Time-Varying Zero-Sum Games）的研究，绝大多数集中于博弈双方各自追求最小化自身的个体遗憾（Individual Regrets），或以动态纳什均衡遗憾（$\text{DNE-Reg}_T$）与累积对偶间隙（$\text{Dual-Gap}_T$）为性能度量。

这种基于个体遗憾或动态纳什均衡的传统研究范式存在致命盲区。一方面，既有文献已知在双线性博弈中静态纳什均衡遗憾（$\text{SNE-Reg}_T$）与个体遗憾互不兼容，算法无法同时使二者达到次线性界；另一方面更关键的是，即便博弈双方实现了极低的动态纳什均衡遗憾（甚至 $\text{DNE-Reg}_T \le O(1)$），双方策略的时间平均状态也可能与全局事后最优的“累积鞍点”（Cumulative Saddle Point）保持 $\Theta(1)$ 的恒定距离。这意味着个体无遗憾学习与寻找整个时间跨度的累积全局鞍点之间存在本质鸿沟，现有算法无法保证长期对抗策略收敛至整体最优决策。

面对这一理论断层，亟需一套直接锚定累积鞍点的新型在线极小极大优化（Online Min-Max Optimization, OMMO）准则，并厘清更弱正则性条件下算法的收敛极限。核心 idea：跳脱出单纯追求个体遗憾的传统博弈框架，以累积鞍点定义静态对偶间隙（$\text{SDual-Gap}_T$）与动态鞍点遗憾（$\text{DSP-Reg}_T$），通过将极小极大问题规约至 OCO 几何结构，证明 OGDA 与新型在线极小极大牛顿步（OMMNS）算法在无需预知累积鞍点的前提下实现 $O(\log T)$ 对偶间隙与向累积鞍点的收敛，并将不可能性定理推广至强凸强凹与极小极大指数凹函数类。

方法详解¶

整体框架¶

本文构建的在线极小极大优化（OMMO）体系围绕累积鞍点展开。在时序演化的博弈中，环境在每轮 $t \in [T]$ 揭晓目标函数 $f_t(x, y)$，局中人分别做出决策 $x_t \in \mathcal{X}$ 与 $y_t \in \mathcal{Y}$，并接收一阶算子反馈 $F_t(z_t) = (\nabla_x f_t(x_t, y_t), -\nabla_y f_t(x_t, y_t))$。整体方法分为三个递进层次：首先通过构造静态间隙函数 $g'_t(x, y) = f_t(x, y') - f_t(x', y)$，将寻找累积鞍点 $z' = (x', y')$ 的博弈问题严格规约到以 $g'_t$ 为目标的凸优化静态与动态遗憾分析；随后针对强凸强凹（SC-SC）与极小极大指数凹（min-max EC）两类低正则性几何结构，分别设计曲率匹配的更新算子（OGDA 与 OMMNS）；最后将单步学习器嵌套进多尺度休眠专家（Sleeping Experts）元学习调度框架 MMFLH，以对齐环境的非平稳变分动态。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["时序零和博弈序列<br/>{f_t(x, y)}_{t=1}^T 与梯度反馈 F_t(z_t)"] --> D1["目标重构：静态对偶间隙与累积鞍点指标<br/>以对偶间隙 g'_t(x, y) 刻画鞍点逼近误差"]
    D1 --> D2["二阶几何正则化与在线学习器更新<br/>OGDA 线性累积 / OMMNS 外积梯度 Hessian 矩阵"]
    D2 --> D3["多时间尺度休眠专家元框架<br/>MMFLH 动态区间划分与概率自适应集成"]
    D3 --> Out["理论输出与收敛保障<br/>对偶间隙 O(log T) 与动态鞍点遗憾 O(√(T V_T log T))"]

关键设计¶

1. 目标重构：以静态与动态对偶间隙锚定累积鞍点
传统时序博弈侧重评估玩家在对手既定动作下的事后最优偏离，导致即使个体遗憾极小，双人策略均值仍可能完全偏离全局累积鞍点 $z' = (x', y') = (\arg\min_x \max_y \sum_{t=1}^T f_t(x, y), \arg\max_y \min_x \sum_{t=1}^T f_t(x, y))$。针对这一脱节，本文引入静态间隙函数 $g'_t(x, y) = f_t(x, y') - f_t(x', y)$，并提出静态对偶间隙 $\text{SDual-Gap}_T \triangleq \sum_{t=1}^T g'_t(x_t, y_t)$ 与动态鞍点遗憾 $\text{DSP-Reg}_T \triangleq \sum_{t=1}^T g'_t(x_t, y_t) - \sum_{t=1}^T \min_{x,y} g'_t(x, y)$。由于 $\min_{x, y} \sum_{t=1}^T g'_t(x, y) = 0$ 且极值点恰在 $z'$ 取得，$\text{SDual-Gap}_T$ 在形式上等价于针对凸目标 $g'_t$ 的标准 OCO 静态遗憾。这一重构彻底打通了从在线博弈到 OCO 转化通道，不仅涵盖了两玩家对抗性资产组合再平衡模型（Two-Player Portfolio Selection），还直接保证了只要 $\text{SDual-Gap}_T$ 达到次线性，策略的时间平均值 $\frac{1}{T}\sum_{t=1}^T z_t$ 就能在 $\ell_2$ 范数下强收敛至累积鞍点 $z'$。

2. 二阶几何正则化：OGDA 与 OMMNS 的曲率自适应更新
为在不显式获知未来函数总和及真实累积鞍点 $z'$ 的严苛约束下最小化 $\text{SDual-Gap}_T$，本文揭示了下正则条件（Lower Regularity）在算子空间的作用机制。对于 $\lambda$-强凸强凹函数，静态间隙函数 $g'_t(z)$ 继承了 $\lambda$-强凸性，在线梯度下降上升（OGDA）只需采用线性增长的尺度矩阵 $A_t = t I$，即可以 $A_t^{-1} F_t(z_t)$ 实施正则化投影更新。而针对更广泛的 $\alpha$-极小极大指数凹（min-max EC）函数类（如 $f(x, y) = -\ln(x^\top A (1/y))$，其中对角矩阵 $A$ 遭受对抗性操纵），曲率具有极强的各向异性与非均匀特征。本文提出在线极小极大牛顿步（OMMNS），在每步累加梯度外积矩阵构造近似二阶曲率度量： $$A_t = A_{t-1} + F_t(x_t, y_t) F_t(x_t, y_t)^\top$$ 借助矩阵对数行列式的伸缩性质，OMMNS 使得局部梯度内积累加项 $\sum_{t=1}^T F_t(z_t)^\top A_t^{-1} F_t(z_t)$ 被严格上界控制在 $d \log T$ 之内，从而在全盲累积鞍点的前提下，优雅斩获 $O(d \log T)$ 的静态对偶间隙界。

3. 多时间尺度休眠专家元框架：以 MMFLH 攻克动态鞍点遗憾
当面对非平稳剧烈波动的环境时，静态对偶间隙不足以衡量跟踪时变极值点的能力。为此，本文设计了适配极小极大博弈的跟踪历史元学习器（Min-Max Follow the Leading History, MMFLH）。该框架将时间轴依指数级网格划分为重叠的时间区间段，并在各区间上动态激活、休眠与淘汰以 OGDA 或 OMMNS 为基学习器的局部专家。元算法将各个专家输出的决策点 $(x_t^j, y_t^j)$ 依其累积静态间隙损失进行指数加权融合。通过建立强自适应鞍点遗憾（$\text{SASP-Regret}_T$）与全局动态鞍点遗憾（$\text{DSP-Reg}_T$）的对偶转化上界，MMFLH 成功利用局部函数变差 $V_T = \sum_{t=1}^T \max_{x,y} |g'_t(x, y) - g'_{t-1}(x, y)|$，自适应取得最优的 $O(\sqrt{T V_T \log T})$ 动态平滑衰减率；并在可分离凸凹结构下，直接确立了 $\text{Dual-Gap}_T \le \text{DSP-Reg}_T$ 的支配关系。

损失函数 / 训练策略¶

算法执行严格遵循在线协议，局中人每轮输出 $(x_t, y_t)$ 后仅获取当期函数 $f_t$ 的算子梯度向量 $F_t(x_t, y_t) = (\nabla_x f_t(x_t, y_t), -\nabla_y f_t(x_t, y_t))$，无任何未来函数信息。

统一低正则算法更新（LRA，统一 OGDA 与 OMMNS）：
在第 $t$ 步，给定度量矩阵 $A_t$ 与学习率参数 $\gamma = \frac{1}{2}\min\{\frac{1}{L_0 D}, \alpha\}$，中间未投影动作通过拟牛顿方向推进： $$u_{t+1} = (u_{t+1}^x, u_{t+1}^y) = (x_t, y_t) - \frac{1}{\gamma} A_t^{-1} F_t(x_t, y_t)$$ 随后在 $A_t$ 诱导的局部加权马氏范数下进行凸集约束投影： $$(x_{t+1}, y_{t+1}) = \arg\min_{(x,y) \in \mathcal{X} \times \mathcal{Y}} \|u_{t+1} - (x, y)\|_{A_t}^2$$ 其中 OGDA 取 $A_t = t I$；OMMNS 取 $A_t = A_{t-1} + F_t(z_t) F_t(z_t)^\top$（初始化 $A_0 = I$）。
两面 PL 条件下的交替在线梯度下降上升（Online AGDA）：
针对超出凸凹体系的光滑非凸非凹问题，在 $L_1$-光滑与两面 PL 模量 $\mu_1, \mu_2$ 保证下，算法设定内循环步数： $$K_t = \max\left\{1, \left\lceil \log_\rho \frac{\max_y f_t(x_t, y) - \min_x f(x, y_t)}{4\beta (a_t + \frac{b_t}{10})} \right\rceil\right\}$$ 其中 $\rho = 1 - \frac{\mu_1 \mu_2^2}{36 L^3}$。在第 $t$ 轮内执行 $K_t$ 次严格交替迭代：$x$ 执行步长 $\tau_1 = \frac{\mu_2}{18 L_1^3}$ 的梯度下降，$y$ 在更新后的 $x$ 上执行步长 $\tau_2 = \frac{1}{L_1}$ 的梯度上升，确保各期动态间隙以 $\frac{1}{4}$ 的收缩率指数级收敛，从而以路径变差界控制全局累积对偶间隙。

实验关键数据¶

主实验¶

论文通过严格的理论推导建立了各类函数假设下算法在不同遗憾度量指标上的上界体系，并给出向累积鞍点的收敛速率对比。

问题设定 / 函数正则性	算法	静态度量指标与理论界	动态度量指标（MMFLH 元框架）	累积鞍点均值收敛率 $\\|\frac{1}{T}\sum z_t - z'\\|_2^2$
$\lambda$-强凸强凹 (SC-SC)	OGDA (Alg 1)	$\text{SDual-Gap}_T \le \frac{L_0^2}{\lambda} \log T$	$\text{DSP-Reg}_T \le O(\max\{\log T, \sqrt{T V_T \log T}\})$	$O\left(\frac{\log T}{\lambda T}\right)$
$\alpha$-极小极大指数凹 (min-max EC)	OMMNS (Alg 2)	$\text{SDual-Gap}_T \le 2d(\frac{1}{\alpha} + L_0 D) \log T$	$\text{DSP-Reg}_T \le O(d \max\{\log T, \sqrt{T V_T \log T}\})$	$O\left(\frac{d \log T}{\gamma T}\right)$
低秩单调变分不等式 (Low-Rank VI)	LR-Newton (Alg 6)	$\sum_{t=1}^T \langle F_t(z), z_t - z \rangle \le O(d \log T)$	对应离线收敛率 $O(\frac{d \log T}{T})$	优于标准有界算子的 $O(\frac{1}{\sqrt{T}})$
两面 PL 条件 (Two-Sided PL)	Online AGDA (Alg 3)	$\text{Dual-Gap}_T \le 2 U_T + 2(g_1^(z_1) - g_T^(z_{T+1}))$	$\text{Dual-Gap}_T \le O(\min\{U_T, V'_T + \Delta_T + C_T, V'_T + C'_T\})$	局部向当期鞍点线性收敛

消融实验¶

为系统阐明为何必须摒弃旧有的博弈遗憾准则、全面转向本文提出的鞍点对偶间隙，下表对比了各遗憾指标在性质兼容性、鞍点逼近能力及信息依赖度上的本质差异。

性能度量准则	与个体遗憾兼容性	策略均值是否收敛至累积鞍点 $z'$	依赖鞍点先验信息	核心机制与局限性分析
静态纳什均衡遗憾 ($\text{SNE-Reg}_T$)	❌ 不兼容（定理 4.5 证明即使在强凸强凹/simplex 域上亦无次线性共存界）	❌ 无法保证	需事后比对	既有文献仅证明双线性不兼容，本文拓展至 SC-SC 与 min-max EC，彻底否定其适用性
动态纳什均衡遗憾 ($\text{DNE-Reg}_T$)	✅ 兼容（由 $\text{Dual-Gap}_T$ 上界控制）	❌ 无法保证（反例 3.9 证实即使 $\text{DNE-Reg}_T \le 1$，距 $z'$ 仍保持 $\Theta(1)$）	需各步独立比对	仅约束当期博弈瞬态平衡，对跨时间尺度的长期全局最优鞍点漂移缺乏感知能力
静态对偶间隙 ($\text{SDual-Gap}_T$，本文)	✅ 建立 OCO 规约通道	✅ 强保证（OGDA 与 OMMNS 均达 $O(\frac{\log T}{T})$ 逼近界）	✅ 完全盲算（执行过程无需知道 $z'$）	真正将优化焦点从瞬态博弈转向累积全局鞍点，规约后目标具备凸性与确切极值
动态鞍点遗憾 ($\text{DSP-Reg}_T$，本文)	✅ 在可分离凸凹下严格支配 $\text{Dual-Gap}_T$	✅ 跟踪时变累积极值	元框架调度需理论锚定	捕获函数动态波动 $V_T$，无缝适配非平稳环境下的休眠专家多尺度聚合

关键发现¶

个体遗憾与累积鞍点的正交性：反例 3.9 构筑的交替强凸强凹二次函数序列深刻揭示了博弈论指标与优化指标的脱节。在该构造中，玩家仅需在奇偶时间步分别匹配极性翻转项，即可将 $\text{DNE-Reg}_T$ 严格压缩在 1 之内，然而其均值动作与累积全局鞍点却具有恒定下界 $\Theta(1)$。
不可能性定理的全面泛化：定理 4.5 将 Cardoso 等人在双线性场景下的不可能性界（No simultaneous sublinear regret）严格推广至 2 维单纯形上的强凸强凹与指数凹函数类，证明了试图在静态纳什均衡遗憾与个体遗憾之间谋求兼顾在理论上彻底不可行。
降阶单调性带来的二阶加速：变分不等式算子的低秩单调性结构使得二阶牛顿更新能够充分榨取子空间曲率，将离线收敛率由一阶经典的 $O(1/\sqrt{T})$ 大幅提速至 $O(d \log T / T)$。

亮点与洞察¶

从博弈对抗到凸优化规约的范式转移：论文最精妙的设计在于将双人零和博弈中形式复杂的“累积鞍点逼近”问题，构造性地转化成了静态间隙函数 $g'_t(z)$ 的凸优化静态遗憾（$\text{SDual-Gap}_T$）。更巧妙的是，虽然 $g'_t$ 显式依赖未知的全局鞍点 $z'$，但通过一阶泰勒展开与梯度算子对齐（引理 B.1），算法在运行阶段仅需单步梯度反馈 $F_t(z_t)$，即可自然取得次线性界，实现了“目标依赖鞍点，但执行完全盲算”的优雅闭环。
双人对抗资产组合的 min-max EC 建模：突破了传统 OCO 中通用投资组合选择（Universal Portfolios）的单智能体假设，开创性地刻画了资产价格遭受恶意对手乘性操纵的二元博弈模型 $f(x, y) = -\ln(x^\top A (1/y))$，并严格证明其满足参数 $\alpha=1$ 的极小极大指数凹性，使 OMMNS 算法能够无缝求解具有市场操纵抗性的长期稳健投资策略。
可迁移的元算法设计思想：MMFLH 中将两玩家极小极大算子封装为单体学习器、并在外层按区间方差调度休眠专家的架构，可直接迁移至分布式多智能体强化学习与对抗鲁棒流式计算等非平稳在线决策系统中。

局限与展望¶

动态鞍点遗憾对鞍点先验的理论依赖：作者在正文与结论中坦承，虽然静态对偶间隙在执行时无需先验，但在 MMFLH 元框架中对 $\text{DSP-Reg}_T$ 建立上界时，元学习器调度目前在理论层面仍依赖于将全局累积鞍点 $z'$ 输入给休眠机制。如何在完全不提供 $z'$ 信息的盲态设定下实现次线性 $\text{DSP-Reg}_T$，仍是一个未解决的开放性理论难题。
高维牛顿步更新的计算复杂度：OMMNS 算法与低秩 VI 优化每轮均需维持并求逆 $d \times d$ 维正定矩阵 $A_t$。尽管可以利用 Sherman-Morrison 公式以 $O(d^2)$ 代价进行增量更新，但在超大规模参数（如大规模神经网络对抗训练）场景下其计算与显存开销依然显著，未来需探索基于低秩 Sketching 或拟牛顿拟合的轻量化逼近算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次揭示个体遗憾与累积鞍点的鸿沟，定义了静态与动态对偶间隙全新指标，理论体系完备新颖]
实验充分度: ⭐⭐⭐⭐☆ [作为纯理论工作，包含了反例构造、完备的数学引理与多类函数条件下的收敛界，缺实质数值实验]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严密精炼，从动机、反例、算法构造到不可能性定理层层推进，逻辑链极其清晰]
价值: ⭐⭐⭐⭐⭐ [为对抗机器学习、非平稳博弈决策与鲁棒资产优化奠定了坚实的在线优化理论基石]

问题设定 / 函数正则性	算法	静态度量指标与理论界	动态度量指标（MMFLH 元框架）	累积鞍点均值收敛率 \(\\|\frac{1}{T}\sum z_t - z'\\|_2^2\)
\(\lambda\)-强凸强凹 (SC-SC)	OGDA (Alg 1)	\(\text{SDual-Gap}_T \le \frac{L_0^2}{\lambda} \log T\)	\(\text{DSP-Reg}_T \le O(\max\{\log T, \sqrt{T V_T \log T}\})\)	\(O\left(\frac{\log T}{\lambda T}\right)\)
\(\alpha\)-极小极大指数凹 (min-max EC)	OMMNS (Alg 2)	\(\text{SDual-Gap}_T \le 2d(\frac{1}{\alpha} + L_0 D) \log T\)	\(\text{DSP-Reg}_T \le O(d \max\{\log T, \sqrt{T V_T \log T}\})\)	\(O\left(\frac{d \log T}{\gamma T}\right)\)
低秩单调变分不等式 (Low-Rank VI)	LR-Newton (Alg 6)	\(\sum_{t=1}^T \langle F_t(z), z_t - z \rangle \le O(d \log T)\)	对应离线收敛率 \(O(\frac{d \log T}{T})\)	优于标准有界算子的 \(O(\frac{1}{\sqrt{T}})\)
两面 PL 条件 (Two-Sided PL)	Online AGDA (Alg 3)	\(\text{Dual-Gap}_T \le 2 U_T + 2(g_1^(z_1) - g_T^(z_{T+1}))\)	\(\text{Dual-Gap}_T \le O(\min\{U_T, V'_T + \Delta_T + C_T, V'_T + C'_T\})\)	局部向当期鞍点线性收敛

性能度量准则	与个体遗憾兼容性	策略均值是否收敛至累积鞍点 \(z'\)	依赖鞍点先验信息	核心机制与局限性分析
静态纳什均衡遗憾 (\(\text{SNE-Reg}_T\))	❌ 不兼容（定理 4.5 证明即使在强凸强凹/simplex 域上亦无次线性共存界）	❌ 无法保证	需事后比对	既有文献仅证明双线性不兼容，本文拓展至 SC-SC 与 min-max EC，彻底否定其适用性
动态纳什均衡遗憾 (\(\text{DNE-Reg}_T\))	✅ 兼容（由 \(\text{Dual-Gap}_T\) 上界控制）	❌ 无法保证（反例 3.9 证实即使 \(\text{DNE-Reg}_T \le 1\)，距 \(z'\) 仍保持 \(\Theta(1)\)）	需各步独立比对	仅约束当期博弈瞬态平衡，对跨时间尺度的长期全局最优鞍点漂移缺乏感知能力
静态对偶间隙 (\(\text{SDual-Gap}_T\)，本文)	✅ 建立 OCO 规约通道	✅ 强保证（OGDA 与 OMMNS 均达 \(O(\frac{\log T}{T})\) 逼近界）	✅ 完全盲算（执行过程无需知道 \(z'\)）	真正将优化焦点从瞬态博弈转向累积全局鞍点，规约后目标具备凸性与确切极值
动态鞍点遗憾 (\(\text{DSP-Reg}_T\)，本文)	✅ 在可分离凸凹下严格支配 \(\text{Dual-Gap}_T\)	✅ 跟踪时变累积极值	元框架调度需理论锚定	捕获函数动态波动 \(V_T\)，无缝适配非平稳环境下的休眠专家多尺度聚合