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

会议: NeurIPS 2026
arXiv: 2605.08006
OpenReview: https://openreview.net/forum?id=K4vQ9YKOxc
代码: https://github.com/weiranwang19/minimax
领域: 优化/理论
关键词: 双层优化、极小极大优化、罚函数法、一阶算法、约束双层优化

一句话总结¶

针对上下层均含极小极大（Minimax）结构的新型双层优化难题，提出首个基于对偶对隙罚函数的一阶邻近点算法，确定性与随机场景分别达到 $\tilde{O}(\epsilon^{-4})$ 与 $\tilde{O}(\epsilon^{-9})$ 的 KKT 点复杂度，并将凸非线性约束下层双层优化的复杂度由现有的 $\tilde{O}(\epsilon^{-7})$ 大幅降至 $\tilde{O}(\epsilon^{-4})$。

研究背景与动机¶

双层优化（Bilevel Optimization）已广泛渗透于超参数调节、元学习、强化学习以及神经架构搜索等机器学习核心领域；与此同时，极小极大优化（Minimax Optimization）在对抗训练、生成对抗网络以及分布鲁棒优化（DRO）中同样扮演着不可替代的角色。然而，在现有双层优化的理论文献中，绝大多数研究均假设下层问题为单目标最小化问题，且高度依赖下层问题的强凸性假设。在此强凸性前提下，下层最优解是上层决策变量的单值可微映射，算法可通过隐函数定理或自动微分高效求解超梯度（Hypergradient）。一旦下层问题演变为更复杂的极小极大博弈架构或退化为仅具弱凸性的问题，解集合可能呈现多值或非光滑特征，传统基于隐函数求导的超梯度算法便彻底失效。

这一理论与现实的脱节带来了显著痛点：一方面，诸多新兴前沿应用（例如带有正则化超参数调节的分组分布鲁棒深度学习以及鲁棒元学习）本质上要求在下层求解一个极小极大鞍点问题，现存算法均无法提供具备理论收敛率保证的直接求解方案；另一方面，针对下层含有凸非线性不等式约束的传统双层优化，已有惩罚法（如 FOP 与 SMO）往往在内外层同时引入两重惩罚参数 $\rho=O(\epsilon^{-1})$ 与 $\mu=O(\epsilon^{-2})$，导致惩罚代理问题的光滑常数膨胀至 $O(\epsilon^{-3})$，进而使一阶预言机复杂度严重退化至 $\tilde{O}(\epsilon^{-7})$（一般凸下层）或 $\tilde{O}(\epsilon^{-6})$（强凸下层）。

面对下层鞍点结构与约束引起的双重瓶颈，本文切入的角度是：利用下层凸-凹极小极大问题的对偶对隙（Duality Gap）作为非负违约惩罚项，将双层极小极大问题等价重构为单层非凸-凹（NCC）极小极大罚问题，并借助拉格朗日对偶性将下层带约束凸优化直接归约至该框架。核心 idea：通过构建下层对偶对隙单参数罚函数，将双层极小极大及非线性约束双层问题统一转化为单层非凸-凹鞍点问题，进而结合非精确邻近点法与一阶鞍点求解器，在无需下层强凸性的前提下取得 $\tilde{O}(\epsilon^{-4})$（确定性）与 $\tilde{O}(\epsilon^{-9})$（随机）一阶复杂度。

方法详解¶

整体框架¶

本文考虑上下层均具极小极大结构的一般双层优化问题： $$ \min_{\mathbf{x}_1, \mathbf{y}_1, \mathbf{y}2} \left{ \max}_2} f(\mathbf{x}_1, \mathbf{x}_2, \mathbf{y}_1, \mathbf{y}_2) \;\Big|\; (\mathbf{y}_1, \mathbf{y2) \in \arg\min1} \max_2) \right} $$ 其中 }_2} \tilde{f}(\mathbf{x}_1, \mathbf{z}_1, \mathbf{z$f = f_1 + f_2(\mathbf{x}_1) - f_3(\mathbf{x}_2)$，$f_1$ 关于 $\mathbf{x}_2$ 凹且平滑；$\tilde{f} = \tilde{f}_1 + \tilde{f}_2(\mathbf{y}_1) - \tilde{f}_3(\mathbf{y}_2)$，$\tilde{f}_1$ 关于 $\mathbf{y}_1$ 凸且关于 $\mathbf{y}_2$ 凹。整体流水线分为三个层级：首先利用弱对偶性将下层鞍点等价约束重构为标量不等式 $p(\mathbf{x}_1,\mathbf{y}_1) - d(\mathbf{x}_1,\mathbf{y}_2) \le 0$；接着引入罚因子 $\rho = 1/\epsilon$ 构造单层非凸-凹极小极大罚问题；最后在外层执行非精确邻近点迭代，将每步子问题正则化为强凸-强凹（SCSC）极小极大问题并调用最优一阶算法（OptFOM / SAPD）求解。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["双层极小极大目标输入<br/>上层目标 f + 下层凸-凹目标 f~"] --> B["对偶对隙罚函数单层重构<br/>引入对隙 p(x1,y1)-d(x1,y2) 与单罚参数 ρ"]
    B --> C["非凸-凹邻近点外层迭代<br/>添加二次近端项与光滑扰动构造 SCSC 结构"]
    C --> D["强凸-强凹极小极大内层求解<br/>确定性调用 OptFOM / 随机调用 SAPD"]
    D -->|终止准则判别| E["输出 ϵ-KKT 点<br/>确定性复杂度 O~(ϵ^-4) / 随机 O~(ϵ^-9)"]

关键设计¶

1. 基于对偶对隙的单参数极小极大罚重构：消除双重惩罚与平滑度爆炸

传统惩罚法在处理下层约束时，常在内层引入软约束或下层最优值惩罚，形成两重惩罚参数 $\rho=O(\epsilon^{-1})$ 与 $\mu=O(\epsilon^{-2})$，导致联合平滑常数达到 $O(\rho\mu)=O(\epsilon^{-3})$。本文的关键洞察在于直接利用下层凸-凹博弈的原始与对偶目标： $$ p(\mathbf{x}_1, \mathbf{y}1) := \max}_2} \tilde{f}(\mathbf{x}_1, \mathbf{y}_1, \mathbf{z}_2), \qquad d(\mathbf{x}_1, \mathbf{y2) := \min}_1} \tilde{f}(\mathbf{x}_1, \mathbf{z}_1, \mathbf{y2) $$ 由于弱对偶性保证了 $p(\mathbf{x}_1, \mathbf{y}_1) \ge d(\mathbf{x}_1, \mathbf{y}_2)$ 恒成立，且等号成立当且仅当 $(\mathbf{y}_1, \mathbf{y}_2)$ 是鞍点，因此下层最优性完全等价于标量约束 $p(\mathbf{x}_1, \mathbf{y}_1) - d(\mathbf{x}_1, \mathbf{y}_2) \le 0$。通过将该差值乘以单一惩罚参数 $\rho = 1/\epsilon$ 移入上层目标，原问题转化为无约束极小极大罚问题： $$ \min}_1, \mathbf{y}_1, \mathbf{y2} \max_2) \big) \Big} $$ 该设计无需下层强凸性，亦无需内层第二惩罚参数，使整个罚问题的平滑常数严格控制在 }_2, \mathbf{z}_1, \mathbf{z}_2} \Big{ f(\mathbf{x}_1, \mathbf{x}_2, \mathbf{y}_1, \mathbf{y}_2) + \rho \big( \tilde{f}(\mathbf{x}_1, \mathbf{y}_1, \mathbf{z}_2) - \tilde{f}(\mathbf{x}_1, \mathbf{z}_1, \mathbf{y$O(\rho) = O(\epsilon^{-1})$，为降低复杂度奠定了理论基石。

2. 双端邻近点正则化机制：化非凸-凹为强凸-强凹子问题

经过重构后的单层罚问题关于最小化变量 $(\mathbf{x}_1, \mathbf{y}_1, \mathbf{y}_2)$ 是非凸的，关于最大化变量 $(\mathbf{x}_2, \mathbf{z}_1, \mathbf{z}_2)$ 是凹的。为了能够调用高效的一阶鞍点加速算法，算法设计了双端正则化非精确邻近点框架：在第 $k$ 次外层迭代中，针对最小化变量注入系数为 $\rho_1 = 2L_{\nabla f} + 4\rho L_{\nabla \tilde{f}}$ 的近端二次项，针对最大化变量注入系数为 $\rho_2 = \epsilon / (2D_2)$ 的强凹微扰项： $$ \min_{\mathbf{x}_1, \mathbf{y}_1, \mathbf{y}2} \max}_2, \mathbf{z}_1, \mathbf{z2} \left{ P\rho(\mathbf{x}_1, \mathbf{x}_2, \mathbf{y}_1, \mathbf{y}_2, \mathbf{z}_1, \mathbf{z}_2) + \frac{\rho_1}{2} |(\mathbf{x}_1,\mathbf{y}_1,\mathbf{y}_2) - (\mathbf{x}_1^{(k)},\mathbf{y}_1^{(k)},\mathbf{y}_2^{(k)})|^2 - \frac{\rho_2}{2} |(\mathbf{x}_2,\mathbf{z}_1,\mathbf{z}_2) - (\mathbf{x}_2^{(k)},\mathbf{z}_1^{(k)},\mathbf{z}_2^{(k)})|^2 \right} $$ 该设计精准地将非凸-凹鞍点问题转化为条件数可控的强凸-强凹（SCSC）极小极大子问题，允许确定性设置下直接嵌套 Kovalev & Gasnikov 的加速一阶算法（OptFOM），只需 $\tilde{O}(\sqrt{\kappa_x \kappa_y})$ 次迭代即可求得高精度解。

3. 拉格朗日对偶统一约简：下层非线性不等式约束的高效求解

对于下层含有凸非线性不等式约束 $\bar{\mathbf{g}}(\mathbf{x}_1, \mathbf{z}_1) \le 0$ 的经典双层优化，既有方法在面对非强凸下层时复杂度高达 $\tilde{O}(\epsilon^{-7})$。本文证明，在标准 Slater 条件下，对偶乘子必定被一致限制在紧盒 $[0, B]^l$ 内（其中 $B = 2L_{\bar{f}}D_{\mathcal{Y}_1}/G$）。借此构造拉格朗日函数 $\tilde{f}(\mathbf{x}_1, \mathbf{y}_1, \mathbf{y}_2) = \bar{f}(\mathbf{x}_1, \mathbf{y}_1) + \mathbf{y}_2^\top \bar{\mathbf{g}}(\mathbf{x}_1, \mathbf{y}_1) - \mathbf{1}_{[0, B]^l}(\mathbf{y}_2)$，直接将其严格转化为上下层极小极大双层优化的特例。这一重构使得下层约束问题完全复用单参数罚框架，避开了约束集合投影的沉重开销，直接将预言机复杂度压缩至 $\tilde{O}(\epsilon^{-4})$。

损失函数 / 训练策略¶

在外层主循环中，算法以当前迭代点为中心更新强凸-强凹目标，确定性分支采用动态精度 $\epsilon_k = \epsilon^{1.5} / (k + 1)$ 调用 OptFOM，外层检查位移收敛准则： $$ |(\mathbf{x}_1^{(k+1)}, \mathbf{y}_1^{(k+1)}, \mathbf{y}_2^{(k+1)}) - (\mathbf{x}_1^{(k)}, \mathbf{y}_1^{(k)}, \mathbf{y}2^{(k)})| \le \frac{\epsilon}{4L $$ 一旦满足即终止并输出 }$\epsilon$-KKT 解；在随机梯度预言机设置下，将内层求解器替换为随机加速原始对偶算法（SAPD），在总外层轮数 $K = \lceil (\mathbb{E}[\max_{\mathbf{x}_2} f] + 1 - f_{\text{low}} + \epsilon D_2 / 4)\epsilon^{-2} \rceil$ 到达后，均匀随机抽取历史迭代点输出，实现近乎 $\epsilon$-KKT 点的理论保证。

实验关键数据¶

主实验¶

在约束双层线性规划基准测试中，对比了一阶惩罚基线 FOP（Lu & Mei, 2024）与序贯极小极大方法 SMO（Lu & Mei, 2026）。所有方法以统一容差 $\epsilon_k \le 0.01$、下层可行性 $\|\bar{\mathbf{g}}\| \le 0.01$ 以及下层最优间隙 $\bar{f} - \bar{f}^* \le 0.01$ 为终止判定。下表展示了终止时的最终上层目标函数值 $f(\mathbf{x}_1, \mathbf{y}_1)$（越小越优）：

变量维度 $(n, m, l)$	评估指标	FOP	SMO	本文方法 (默认理论界)	本文方法 (步长调优 $L_{\nabla h}=6$)	较基线提升 (调优后)
$(100, 100, 5)$	上层目标值 $f \downarrow$	-135.97	-146.58	-145.09	-147.77	显著更低
$(200, 200, 10)$	上层目标值 $f \downarrow$	-285.73	-308.98	-302.58	-312.76	显著更低
$(300, 300, 15)$	上层目标值 $f \downarrow$	-430.08	-437.35	-430.61	-455.54	领先 18.19
$(400, 400, 20)$	上层目标值 $f \downarrow$	-573.76	-620.38	-588.08	-627.70	领先 7.32
$(500, 500, 25)$	上层目标值 $f \downarrow$	-712.83	-765.39	-708.40	-773.55	领先 8.16

消融实验¶

在真实场景的分组分布鲁棒深度学习（Deep Group DRO）超参数调优任务中，采用 ResNet 特征提取器（$\mathbf{x}_1$）与线性分类头（$\mathbf{y}_1$）解耦架构，通过随机版本算法协同优化对抗权重扰动参数 $\eta$。在 CelebA 与 Waterbirds 两个存在严重虚假关联（少数组仅占训练集 3%）的数据集上，考察有无 $\ell_2$ 正则化惩罚系数 $\lambda$ 时的表现：

数据集	正则化惩罚 $\lambda$	平均准确率 (DRO)	平均准确率 (本文)	最差组准确率 (DRO)	最差组准确率 (本文)	最差组增益 (绝对百分比)
CelebA	$\lambda = 0.0$	94.7%	93.9%	41.1%	75.0%	+33.9%
CelebA	$\lambda = 0.1$	93.5%	95.6%	86.7%	90.0%	+3.3%
Waterbirds	$\lambda = 0.0$	97.4%	93.3%	76.9%	86.9%	+10.0%
Waterbirds	$\lambda = 1.0$	96.6%	94.0%	84.6%	88.8%	+4.2%

关键发现¶

在约束双层优化中，本文基于拉格朗日紧盒对偶重构规避了常规方法内外双重惩罚导致的曲率恶化，梯度迭代收敛速度显著快于 FOP，调优平滑参数后全面超越 SMO 获得更优可行解。
在深度分布鲁棒学习中，无显式 $\ell_2$ 正则时标准 DRO 出现严重的虚假特征捷径学习（CelebA 最差组准确率仅 41.1%），而双层超参数协同优化驱动特征提取器学习到本质表征，将最差组准确率大幅挽救至 75.0%，验证了双层极小极大建模的有效性。

亮点与洞察¶

理论突破性：首次为双层上下层均带 Minimax 结构的问题建立了非渐近的一阶收敛率，填补了无强凸性假设下双层博弈优化的理论空白。
巧妙的归约技巧：通过 Slater 条件确立对偶乘子的上界 $B = 2L_{\bar{f}}D_{\mathcal{Y}_1}/G$，将下层非线性不等式约束转化为含紧约束集指示函数的极小极大子项，免去了投影操作并消除了内层惩罚因子。
算法模块化：将单层 NCC 惩罚问题解耦为外层邻近点更新与内层成熟的 SCSC 极小极大一阶加速求解器，既适配确定性场景的高效加速，又能直接扩展至随机预言机。

局限与展望¶

紧致可行域约束：理论分析严格要求变量定义域为紧集（有界直径），对于完全无界非凸优化场景仍需进一步松弛假设。
随机复杂度偏高：随机场景下的预言机复杂度为 $\tilde{O}(\epsilon^{-9})$，主要源于邻近点嵌套与非精确随机梯度的误差累积，未来可探索方差缩减（Variance Reduction）技术以压缩至更低阶数。
提升空间度量：当前的 $\epsilon$-KKT 点定义基于引入辅助变量 $(\mathbf{z}_1, \mathbf{z}_2)$ 的提升空间（Lifted Space），若能纯粹基于原决策变量建立驻定性度量将更具理论美感。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 提出首个双层极小极大优化的非渐近一阶算法框架，并给出精妙的对偶对隙单惩罚重构。
实验充分度: ⭐⭐⭐⭐ 涵盖合成约束优化与实际深度 DRO 超参数调优，涵盖收敛曲线、主对比表与消融分析。
写作质量: ⭐⭐⭐⭐⭐ 理论证明完整严谨，从定义、引理到定理推导逻辑清晰，与已有 SOTA 算法复杂度对比鲜明。
价值: ⭐⭐⭐⭐⭐ 推动了鲁棒学习、博弈机器学习与约束优化的算法统一，对双层优化理论社区有重要贡献。

变量维度 \((n, m, l)\)	评估指标	FOP	SMO	本文方法 (默认理论界)	本文方法 (步长调优 \(L_{\nabla h}=6\))	较基线提升 (调优后)
\((100, 100, 5)\)	上层目标值 \(f \downarrow\)	-135.97	-146.58	-145.09	-147.77	显著更低
\((200, 200, 10)\)	上层目标值 \(f \downarrow\)	-285.73	-308.98	-302.58	-312.76	显著更低
\((300, 300, 15)\)	上层目标值 \(f \downarrow\)	-430.08	-437.35	-430.61	-455.54	领先 18.19
\((400, 400, 20)\)	上层目标值 \(f \downarrow\)	-573.76	-620.38	-588.08	-627.70	领先 7.32
\((500, 500, 25)\)	上层目标值 \(f \downarrow\)	-712.83	-765.39	-708.40	-773.55	领先 8.16

数据集	正则化惩罚 \(\lambda\)	平均准确率 (DRO)	平均准确率 (本文)	最差组准确率 (DRO)	最差组准确率 (本文)	最差组增益 (绝对百分比)
CelebA	\(\lambda = 0.0\)	94.7%	93.9%	41.1%	75.0%	+33.9%
CelebA	\(\lambda = 0.1\)	93.5%	95.6%	86.7%	90.0%	+3.3%
Waterbirds	\(\lambda = 0.0\)	97.4%	93.3%	76.9%	86.9%	+10.0%
Waterbirds	\(\lambda = 1.0\)	96.6%	94.0%	84.6%	88.8%	+4.2%