📊 statistics

Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

本文针对上下两层均具有极小极大结构的双层优化问题，提出了基于惩罚的一阶方法，在确定性设定下建立了 $\tilde{O}(\epsilon^{-4})$ 的改进 oracle 复杂度界，在随机设定下建立了 $\tilde{O}(\epsilon^{-9})$ 的改进 oracle 复杂度界，且无需对下层问题施加强凸性假设。

原作者： Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试解决一个极其复杂的拼图，但拼图的规则会根据你尝试解决它的方式而不断改变。这就是双层优化（Bilevel Optimization）的精髓，这是一种用于机器学习的数学问题，其中一个决策（“上层”）取决于另一个决策（“下层”）的结果。

通常，下层决策就像寻找山谷中的最低点（最小化）。但这篇论文解决了一个更为棘手的场景：如果下层决策是一场拔河比赛呢？

核心问题：拼图内部的“拔河”

在这篇论文中，作者关注一种特定类型的问题，其中：

老板（上层）： 希望做出决策以最小化自身的成本。
团队（下层）： 团队并非仅仅试图寻找最低点，而是分裂了。一半人希望最小化得分，而另一半人希望最大化它。他们彼此之间进行着“极小化极大”（minimax）博弈（类似于石头剪刀布或零和博弈）。

老板必须制定策略，同时预见到团队会立即开始互相争斗，以寻找一个“鞍点”（即一种平衡状态，任何一方都无法通过改变策略而获胜）。

挑战： 现有的用于解决此类拼图的数学工具通常假设团队只是在寻找单个最低点（就像球滚下山坡）。当团队互相争斗时，这些工具就会失效。此外，许多旧工具要求“山坡”必须是完美平滑且呈碗状的（强凸），但这并不符合许多现实世界的人工智能问题。

解决方案：“惩罚”策略

作者提出了一种使用基于惩罚的方法（Penalty-Based Method）来解决此问题的新途径。

类比：严格的裁判
想象老板和团队在一个房间里。团队本应在老板行动之前达到完美的平衡（鞍点）。

旧方法： 老板耐心地等待，每次检查团队是否达到了完美平衡。这既缓慢又计算成本高昂。
新方法（惩罚法）： 作者引入了一个严格裁判（惩罚参数）。
- 裁判说：“你不必等到团队达到完美平衡。你可以继续前进，但如果团队没有达到平衡，你将被处以巨额罚款（惩罚）。”
- 你越想快速解决问题（误差 $\epsilon$ 越小），罚款就越重。
- 该算法本质上将复杂的“等待完美平衡”规则转化为一个简单的数学问题：最小化你的成本 + 最小化罚款。

通过这样做，他们将一个两层、复杂的问题转化为单个巨大的“极小 - 极大”博弈，标准计算机可以更快地处理。

他们取得的成就（结果）

这篇论文声称，利用这种“严格裁判”方法取得了两大胜利：

加速确定性情况（无噪声）：
当数学完美且清晰（确定性）时，他们的方法以大约 $\tilde{O}(\epsilon^{-4})$ 的复杂度找到了一个良好的解。
- 解读： 如果你希望答案的准确度提高 10 倍，你不需要做 1,000 倍的工作；你只需要做大约 10,000 倍的工作。
- 比较： 以前针对类似约束问题的方法要慢得多（约为 $\epsilon^{-7}$ ）。作者显著改进了这一点。
处理混乱、有噪声的情况（随机）：
在现实世界中，数据是有噪声的（就像试图在拥挤的房间里听清对话）。作者扩展了他们的方法以处理这种“随机”设置。
- 他们证明了该方法仍然有效，以 $\tilde{O}(\epsilon^{-9})$ 的复杂度找到了一个“近乎完美”的解。
- 注意： 虽然 $\epsilon^{-9}$ 听起来很高，但作者承认这是针对此类特定问题的第一步，并建议未来的工作（使用方差缩减）可以使其更快。

现实世界测试

作者不仅做了数学推导，还在两件事上进行了测试：

合成线性问题： 他们创建了虚假的数学拼图，将其方法与现有方法（FOP 和 SMO）进行比较。他们的方法收敛更快，并找到了更好的解，特别是在他们调整了“裁判”的灵敏度时。
鲁棒人工智能的超参数调整： 他们将此应用于一个名为分布鲁棒优化（Distributionally Robust Optimization, DRO）的现实世界问题。
- 场景： 想象训练一个 AI 来识别鸟类。大多数照片是陆地上的鸟，但少数是在水上的。标准的 AI 可能会作弊，只看背景（陆地 vs. 水）而不是鸟。
- 修正： 作者使用他们的双层方法来调整 AI，使其即使在“最坏情况”组（例如，水上的鸟）中也能表现良好。
- 结果： 与现有方法相比，他们的方法显著提高了“最坏组”的准确率（例如，在某个数据集上从 41% 跃升至 75%），同时没有损害整体平均性能。

总结

这篇论文引入了一种新的“严格裁判”策略，用于解决复杂的、两层优化问题，其中内层是一场拔河（极小化极大）。通过将“完美平衡”的硬性约束转化为惩罚，他们创造了一种更快、更高效的算法，优于以前的方法，特别是在涉及约束和噪声数据的场景中。他们成功地在合成拼图和现实世界的人工智能鲁棒性挑战上证明了这一点。

技术摘要：基于惩罚的一阶方法求解具有极小极大结构与约束下层问题的双层优化

问题表述

本文研究了一类双层优化问题，其中上层和下层问题均呈现极小极大结构。其一般形式定义为：
$\min_{x_1, y_1, y_2} \left\{ \max_{x_2} f(x_1, x_2, y_1, y_2) \mid (y_1, y_2) \in \arg\min_{z_1} \max_{z_2} \tilde{f}(x_1, z_1, z_2) \right\}$
其中 $(y_1, y_2)$ 表示下层函数 $\tilde{f}$ 的一个鞍点。作者假设了特定的结构性质： $f$ 和 $\tilde{f}$ 可分解为光滑分量与适当的闭凸函数，且关于各自变量具有特定的凸性/凹性（例如， $\tilde{f}$ 关于 $y_1$ 是凸的，关于 $y_2$ 是凹的）。

该工作的一个重要子集聚焦于下层为带有凸非线性不等式约束的凸最小化问题的双层问题：
$\min_{x_1, y_1} \left\{ f(x_1, y_1) \mid y_1 \in \arg\min_{z_1} \{ \bar{f}(x_1, z_1) \mid \bar{g}(x_1, z_1) \leq 0 \} \right\}$
在 Slater 条件下，该约束问题通过拉格朗日对偶性被重构为一般极小极大双层框架的特例。

现有文献主要关注下层为单目标最小化（通常具有强凸性）的双层优化。依赖超梯度或隐式微分的方法在下层仅为凸、非凸或具有极小极大结构时往往失效。本文旨在填补这一空白，开发适用于极小极大下层设定且无需强凸性假设的一阶方法。

方法论

所提出的方法利用值函数惩罚重构。通过引入惩罚参数 $\rho$ ，将约束双层问题转化为无约束（或更简单的约束）极小极大问题。

确定性设定

惩罚重构：将原问题重构为单层极小极大问题：
$\min_{x_1, y_1, y_2} \max_{x_2, z_1, z_2} P_\rho(x_1, x_2, y_1, y_2, z_1, z_2)$
其中 $P_\rho$ 包含目标函数和惩罚项 $\rho(p(x_1, y_1) - d(x_1, y_2))$ ，代表下层问题的对偶间隙。
算法：作者提出了一种非精确近端点法。外循环通过求解一系列强凸 - 强凹（SCSC）子问题来更新原始 - 对偶变量。
子问题求解器：每个子问题使用最优一阶方法求解（具体为 Lu 和 Mei [52] 或 Kovalev 和 Gasnikov [37] 方法的变体），记为 OptFOM。
复杂度：该方法以 $\tilde{O}(\epsilon^{-4})$ 的预言机复杂度找到一个 $\epsilon$ -KKT 点。

随机设定

当仅能获取光滑分量的随机梯度预言机时：

算法：将确定性近端点法适配为使用**随机加速原始 - 对偶（SAPD）**方法（具体为 Zhang 等人 [75] 提出的 SAPD+）来求解内层子问题。
收敛性：该方法找到一个“近乎” $\epsilon$ -KKT 点（即解与精确 $\epsilon$ -KKT 点的距离在 $\epsilon$ 范围内），其随机预言机复杂度为 $\tilde{O}(\epsilon^{-9})$ 。

应用于约束下层问题

对于具有约束凸下层的双层优化（问题 4）这一特定情况，作者表明在 Slater 条件下，拉格朗日乘子被限制在盒子 $[0, B]^l$ 内。这使得可以通过引入对偶变量作为带有盒子约束的显式优化变量，将约束问题重构为一般极小极大双层问题（问题 1）。这种重构避免了对内层约束使用第二个惩罚参数，从而与 prior work 相比获得了更优的复杂度界。

主要贡献

双层极小极大问题的首个复杂度结果：本文建立了针对下层为极小极大问题的双层优化的一阶确定性方法和随机方法的复杂度界。
- 确定性复杂度： $\tilde{O}(\epsilon^{-4})$ 。
- 随机复杂度： $\tilde{O}(\epsilon^{-9})$ 。
约束双层问题的改进界：通过将具有凸约束下层的双层问题重构为所提出的极小极大框架的实例，作者实现了 $\tilde{O}(\epsilon^{-4})$ 的复杂度。这优于现有针对仅凸下层（[53] 中的 $\tilde{O}(\epsilon^{-7})$ ）和强凸下层（[51] 中的 $\tilde{O}(\epsilon^{-6})$ ）的结果。这一改进源于避免了对内层约束使用第二个惩罚参数，而此前该方法会导致更高的光滑性参数。
实证验证：
- 合成数据：在约束线性双层问题上，所提方法在与现有基于惩罚的方法（FOP 和 SMO）的对比中表现出具有竞争力的收敛速度，特别是在调节 Lipschitz 常数时。
- 实际应用：该方法被应用于深度学习中**分布鲁棒优化（DRO）**的超参数调优。在 CelebA 和 Waterbirds 数据集上，所提出的随机双层方法在保持相当的平均准确率的同时，在最差组准确率方面优于标准 DRO 方法。

结果与意义

本文声称，所提出的基于惩罚的框架提供了一种统一的方法来处理具有极小极大结构的双层问题，而这一设定在关于一阶复杂度的文献中此前尚未被探索。

理论意义：该工作架起了双层优化与极小极大优化之间的桥梁，提供了严格的收敛保证，且无需依赖下层问题的强凸性假设。对于约束下层，复杂度从 $\tilde{O}(\epsilon^{-7})$ 降低到 $\tilde{O}(\epsilon^{-4})$ 被视为一项重大的理论进展。
实践意义：在 DRO 中的应用展示了该方法在处理涉及分布偏移和群体公平性的机器学习场景中的实用性。CelebA 和 Waterbirds 数据集上的结果表明，该方法能够有效应对“最差组”优化挑战，实现比基线 DRO 方法更高的最差组准确率。

作者承认了局限性，包括要求可行域紧致、使用提升空间来定义 KKT 条件，以及随机情况下的较高复杂度（ $\tilde{O}(\epsilon^{-9})$ ），并指出方差缩减技术可能是未来工作的方向。