Stochastic Dynamic Barrier Perturbed Gradient Methods for Nonconvex Simple Bilevel Optimization¶
会议: NeurIPS 2026
arXiv: 2607.10957
OpenReview: https://openreview.net/forum?id=kVtxwFFyWj
论文: https://arxiv.org/abs/2607.10957
领域: 优化/理论
关键词: 双层优化、非凸优化、动态障碍物法、对偶扰动、样本复杂度
一句话总结¶
针对上层和下层目标均为光滑非凸函数的随机简单双层优化问题，提出扰动对偶动态障碍物法（SDBPG）与无需稀有访问假设的罚正则化方法（PR-SDBPG / VR-PR-SDBPG），首次建立了显式的 \((\epsilon_f, \epsilon_g)\)-稳态点样本复杂度理论保证。
研究背景与动机¶
简单双层优化（Simple Bilevel Optimization）旨在下层优化问题的最优解集约束下最小化上层目标函数，在持续学习、超参数优化、元学习、强化学习以及大语言模型（LLM）机器遗忘（Machine Unlearning）等前沿领域扮演着核心数学建模工具的角色。在现代大规模机器学习任务中，上下层目标函数往往由于深度神经网络参数化而呈现高度非凸性，且只能通过随机批次采样获取随机梯度估计。然而，下层问题的可行解集通常是隐式的，无法直接进行正交投影；若采用下层最优值函数重构（Value Function Reformulation），则不仅需要全局最优值，还会诱发对偶变量无界的奇异病态。
在现有一阶方法中，确定性动态障碍物梯度下降（Dynamic Barrier Gradient Descent, DBGD）通过显式平衡上下层下降方向避免了双层投影，但其对偶乘子具有 \(\lambda_k \propto \|\nabla g(\mathbf{x}_k)\|^{-1}\) 的尺度特性，当下层梯度接近驻点时会发生奇异发散。在确定性场景下精确梯度的连续性尚可控制这种发散，但在随机环境下，上下层小批量梯度噪声会剧烈放大这种不稳定性，使得基于批次梯度内积与范数比值构建的随机对偶乘子不仅存在显著偏差（bias），而且其方差在下层驻点附近无界。现有随机非凸双层优化方法（如 BLOOP）通过正交投影规避乘子发散，但仅能保证下层驻点收敛，彻底丧失了上层驻点收敛保证。
这种理论与算法维度的根本脱节，使得随机非凸-非凸简单双层优化领域一直缺乏同时对上下层目标给出显式 \((\epsilon_f, \epsilon_g)\)-稳态收敛性与样本复杂度界的方法。核心 idea：在对偶子问题分母中显式引入自适应扰动项或通过罚正则化重构子问题，从根本上压制下层梯度退化导致的对偶奇异性，并利用梯度算子的联合 Lipschitz 连续性严格控制随机方向的偏差与方差。
方法详解¶
整体框架¶
本文针对上层目标 \(f(\mathbf{x})=\mathbb{E}[\tilde{f}(\mathbf{x},\xi_f)]\) 与下层目标 \(g(\mathbf{x})=\mathbb{E}[\tilde{g}(\mathbf{x},\xi_g)]\) 均为光滑非凸的随机优化问题，提出了一整套单循环（Single-loop）随机下降算法。算法的整体流程分为样本采样、对偶乘子稳健估计、更新方向合成以及参数迭代推进。为了应对下层梯度模长趋于零时的乘子无界问题，本文设计了两种互补的正则化路径：SDBPG 通过分母扰动结合坏区域观测检测器规避失稳；PR-SDBPG 与 VR-PR-SDBPG 则通过将约束 QP 重构为罚正则化无约束子问题，将对偶分母一致下界化，从而彻底摆脱对样本轨迹的额外假设。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入：随机采样批次<br/>∇f~(x_k, ξ_f) 与 ∇g~(x_k, ξ_g)"] --> B["对偶扰动与稳定估计<br/>分母加正则项 γ 截断奇异值"]
B --> C["坏区域检测与乘子修正<br/>负对齐小梯度区置零 / 罚正则化"]
C --> D["单循环下降方向合成<br/>d~_k = ∇f~_k + λ~_k ∇g~_k"]
D -->|更新参数 x_{k+1} = x_k - η d~_k| E["输出：(ϵ_f, ϵ_g)-稳态解"]关键设计¶
1. 对偶分母正则化扰动机制：抑制下层近驻点处的乘子发散
确定性 DBGD 的对偶乘子形式为 \(\lambda_k = \max\left\{\frac{\beta_k \|\nabla g(\mathbf{x}_k)\|^2 - \nabla g(\mathbf{x}_k)^\top \nabla f(\mathbf{x}_k)}{\|\nabla g(\mathbf{x}_k)\|^2}, 0\right\}\)。当迭代点接近下层驻点时，分母趋于零，随机梯度替代下的样本相关比值估计量会发生方差爆炸与严重偏差。SDBPG 在对偶目标中对模长二次项引入非负扰动 \(\gamma_k > 0\)，将对偶乘子调整为： $$ \tilde{\lambda}_{\gamma,k} = \max\left{\beta_k - \frac{\nabla \tilde{g}_k^\top \nabla \tilde{f}_k}{|\nabla \tilde{g}_k|^2 + \gamma_k}, 0\right} $$ 该设计将可能无限发散的分母加上保护缓冲 \(\gamma_k\)。作者创新性地不直接分析标量乘子误差 \(|\tilde{\lambda}_{\gamma,k} - \lambda_k|\)，而是聚焦于合成更新项 \(\tilde{\lambda}_{\gamma,k} \nabla \tilde{g}_k\) 的算子映射 \(T_\gamma(u,v) = \frac{\langle u, v \rangle}{\|v\|^2 + \gamma} v\)，证明了其在有界梯度假设下关于输入 \((u, v)\) 具有联合 Lipschitz 连续性，从而为随机扰动方向建立了明确可控的条件偏差与二阶矩上界。
2. 坏区域观测检测器：切断负对齐恶劣区域的失稳路径
尽管引入了扰动 \(\gamma_k\)，当下层梯度极小且两层梯度严重负对齐（即 \(\nabla g(\mathbf{x}_k)^\top \nabla f(\mathbf{x}_k) < -\theta \|\nabla g(\mathbf{x}_k)\|^2\)）时，真实的对偶变量仍会快速膨胀。SDBPG 显式定义坏区域 \(\mathcal{R}_k(\tau, \theta)\) 及其独立采样的可观测估计域 \(\widehat{\mathcal{R}}_k(\tau/2, \theta)\)。当检测器触发时，算法强制设定 \(\tilde{\lambda}_{\gamma,k} = 0\)，将更新方向退化为纯上层随机梯度 \(\tilde{\mathbf{d}}_k = \nabla \tilde{f}_k\)。因为两层梯度的负对齐特性，单纯的上层梯度步能够推高下层函数值，驱使迭代点迅速脱离坏区域。结合稀有访问假设（Bad-region visit rate \(\mathcal{O}(K^{1-\varsigma})\)），检测器的非对称阈值设计保证了即便出现误报与漏报，由于切比雪夫不等式与样本量的匹配，误报率仍可被控制在可忽略的高阶小量内。
3. 罚正则化子问题重构与方差缩减扩展：彻底消除稀有访问假设
为了摆脱对迭代轨迹进入坏区域频次的不可验证假设，PR-SDBPG 放弃了对偶变量的事后截断，转而将对偶约束 QP 转化为尺度不变的罚正则化无约束优化： $$ \mathbf{d}k = \arg\min}\in\mathbb{R}^n} \frac{1}{2}|\mathbf{d} - \nabla f(\mathbf{x}_k)|^2 + \frac{\mu}{2} \frac{\left[\beta(|\nabla g(\mathbf{x}_k)|^2 + \gamma) - \nabla g(\mathbf{xk)^\top \mathbf{d}\right]+^2}{|\nabla g(\mathbf{x}_k)|^2 + \gamma} $$ 其显式解对应的乘子分母天然满足 \((1+\mu)\|\nabla \tilde{g}_k\|^2 + \gamma \geq \gamma > 0\)。通过严格的 AM-GM 不等式证明，该乘子在全空间一致有界（\(\hat{\lambda}_k \leq \mu \beta + \frac{\mu G_f}{2\sqrt{(1+\mu)\gamma}}\)）。进一步引入 STORM 递归动量方差缩减跟踪器（VR-PR-SDBPG），利用单循环历史动量梯度消除大批量样本依赖，将上层与下层样本复杂度分别从 \(\mathcal{O}(\epsilon^{-8}), \mathcal{O}(\epsilon^{-10})\) 显著优化至 \(\mathcal{O}(\epsilon^{-6}), \mathcal{O}(\epsilon^{-8})\)。
损失函数 / 训练策略¶
在双层优化中，整体策略是通过构建单循环复合更新方向 \(\tilde{\mathbf{d}}_k = \nabla \tilde{f}_k + \tilde{\lambda}_k \nabla \tilde{g}_k\) 推进参数 \(\mathbf{x}_{k+1} = \mathbf{x}_k - \eta_k \tilde{\mathbf{d}}_k\)。 - SDBPG 调度：步长设为 \(\eta_k = K^{-1/4}\)，障碍参数 \(\beta_k = K^{-1/4}\)，扰动量 \(\gamma_k = K^{-1}\)，阈值参数 \(\tau = K^{-1/2}, \theta = K^{-1/4}\)，批次大小设为 \(N_f = K, N_g = K^2\)。 - PR-SDBPG 调度：罚权重 \(\mu = 1\)，正则化参数 \(\gamma = 1\)，李雅普诺夫平衡权重 \(c = \mathcal{O}(G_f^3/\epsilon)\)，步长 \(\eta = \mathcal{O}(\epsilon / (G_f^3 (L_f + c L_g)))\)，批次大小设定为 \(N_f = \mathcal{O}(\epsilon^{-4}), N_g = \mathcal{O}(\epsilon^{-6})\)。 - VR-PR-SDBPG 调度：在 PR-SDBPG 参数基础上引入 STORM 跟踪，递归更新梯度估计 \(u_k = \nabla \tilde{f}(x_k, \xi_f^k) + (1-\alpha_k)(u_{k-1} - \nabla \tilde{f}(x_{k-1}, \xi_f^k))\)，仅需单样本或固定小批量更新。
实验关键数据¶
主实验¶
论文在大语言模型（LLM）机器遗忘基准任务上进行了系统验证，分别在 TOFU 数据集（基于 Llama-3.2-1B-Instruct 架构，forget05 配置）与 MUSE-News 数据集（基于 Llama-2-7B 架构，knowmem 配置）上评估了所提方法与确定性基线 DDBPG 的收敛效率。优化目标为在最小化保留集交叉熵损失（\(f\)）的同时，使遗忘集负偏好优化损失（\(g\)）达到极小驻点。实验以归一化稳态残差指标 \(\frac{1}{K}\sum_{k=0}^{K-1}\|\nabla \tilde{g}(\mathbf{x}_k)\|^2\)（下层稳态）与 \(\frac{1}{K}\sum_{k=0}^{K-1}\|\tilde{\mathbf{d}}_k\|^2\)（联合稳态）随样本数及计算时间（秒）的下降轨迹进行衡量。
| 数据集 / 模型 | 优化算法 | 样本复杂度 (达到 10⁻² 残差) | 耗时 (秒) | 联合稳态残差收敛速率 |
|---|---|---|---|---|
| TOFU / Llama-3.2-1B | DDBPG (确定性大批次) | \(\sim 3.6 \times 10^4\) 样本 | \(\sim 280\)s | 缓慢下降，每步大批次开销大 |
| TOFU / Llama-3.2-1B | PR-SDBPG (本文罚正则) | \(\sim 1.0 \times 10^4\) 样本 | \(\sim 85\)s | 稳步收敛，方差有轻微震荡 |
| TOFU / Llama-3.2-1B | VR-PR-SDBPG (本文方差缩减) | \(\sim 6.0 \times 10^3\) 样本 | \(\sim 50\)s | 快速平滑收敛，样本利用率高 |
| TOFU / Llama-3.2-1B | SDBPG (本文扰动对偶) | \(\sim 3.5 \times 10^3\) 样本 | \(\sim 32\)s | 最优，初期迅速下降并收敛 |
| MUSE-News / Llama-2-7B | DDBPG (确定性全批次) | \(\sim 1.6 \times 10^4\) 样本 | \(\sim 420\)s | 全批次梯度计算代价高昂 |
| MUSE-News / Llama-2-7B | PR-SDBPG (本文罚正则) | \(\sim 4.5 \times 10^3\) 样本 | \(\sim 120\)s | 优于确定性基线，鲁棒无发散 |
| MUSE-News / Llama-2-7B | VR-PR-SDBPG (本文方差缩减) | \(\sim 2.8 \times 10^3\) 样本 | \(\sim 78\)s | 显著优于小批量 PR-SDBPG |
| MUSE-News / Llama-2-7B | SDBPG (本文扰动对偶) | \(\sim 1.8 \times 10^3\) 样本 | \(\sim 48\)s | 最优，耗时减少超 88% |
消融实验¶
消融实验对比了不同算法构件与理论设置下的样本复杂度阶数与实际假设依赖条件：
| 算法变体 / 构件配置 | 上层复杂度 \(\mathcal{O}(\cdot)\) | 下层复杂度 \(\mathcal{O}(\cdot)\) | 额外假设需求 | 乘子有界性机制 |
|---|---|---|---|---|
| 标准 DBGD (无扰动 \(\gamma=0\)) | 发散 / 无界 | 发散 / 无界 | 需严格非退化假设 | 无界（除零风险） |
| SDBPG (理想空坏区域 \(\delta=1/2\)) | \(\epsilon^{-4}\) | \(\epsilon^{-6}\) | 坏区域均匀有限访问 | 分母扰动项 \(\gamma_k\) 缓冲 |
| SDBPG (一般稀有访问 \(\delta \in (0,1/2]\)) | \(\epsilon^{-2/\delta}\) | \(\epsilon^{-3/\delta}\) | 坏区域次线性访问频次 | 扰动项 + 观测检测器置零 |
| PR-SDBPG (无方差缩减) | \(\epsilon^{-8}\) | \(\epsilon^{-10}\) | 无任何额外假设 | 罚正则化分母一致下界 \(\gamma\) |
| VR-PR-SDBPG (STORM 动量跟踪) | \(\epsilon^{-6}\) | \(\epsilon^{-8}\) | 无额外假设 (仅均方光滑) | 罚正则化 + 递推方差缩减 |
关键发现¶
- 样本效率相比确定性方法提升显著：在相同样本预算下，随机方法（SDBPG 系列）的稳态残差比 DDBPG 降低了 1 至 2 个数量级；DDBPG 虽然单步迭代下降较多，但单步需消耗多达数百甚至上千个样本，整体效率远落后于随机单循环策略。
- 坏区域访问的实际自愈性：实验中观察到，在实际 LLM 遗忘训练中，迭代点进入坏区域的频次极低，且触发检测器置零后模型能迅速回到良态区域，验证了稀有访问假设在实际非凸学习中的合理性，解释了 SDBPG 实验表现优于理论悲观界的原因。
- 方差缩减的工程价值：VR-PR-SDBPG 在 PR-SDBPG 的基础上省去了大批次采样需求，使用递归动量跟踪使得小批量运行时的轨迹极为平滑，在保证无额外假设的同时显著缩小了与 SDBPG 的性能差距。
亮点与洞察¶
- 精巧的联合 Lipschitz 误差分析：避开对单独标量乘子 \(\lambda_k\) 的病态估计，转而分析复合向量映射 \(T_\gamma(u,v) = \frac{\langle u, v \rangle}{\|v\|^2 + \gamma} v\)，以数学优雅的方式直接控制了随机更新方向的偏差与二阶矩。
- 互补的双路线算法设计：SDBPG 在稀有访问假设下追求更优的复杂度（\(\epsilon^{-4}, \epsilon^{-6}\)），而 PR-SDBPG 则通过罚正则化构筑了无任何非退化假设的理论安全网，构成了严密的方法学闭环。
- 向复杂多任务/带约束学习的高可迁移性：其动态障碍物正则化思想可无缝推广至多目标权衡、模型编辑（Model Editing）、安全强化学习等各类存在隐式非凸流形约束的机器学习优化场景中。
局限与展望¶
- 理论复杂度阶数仍相对悲观：PR-SDBPG 为了消去额外假设，李雅普诺夫分析迫使其上层/下层样本复杂度达到 \(\mathcal{O}(\epsilon^{-8})\) 和 \(\mathcal{O}(\epsilon^{-10})\)，虽然 VR-PR-SDBPG 将其压制至 \(\mathcal{O}(\epsilon^{-6}), \mathcal{O}(\epsilon^{-8})\)，但与下界可能仍有差距。
- 超参数调度较为敏感：SDBPG 的阈值 \(\tau, \theta\) 以及扰动 \(\gamma_k\) 理论上依赖于优化时域 \(K\) 的幂次衰减，在未知步数或需要自适应学习率的深度学习训练中调参存在挑战。
- 未来方向：探索高阶动量加速或自适应步长机制，将样本复杂度进一步逼近经典非凸优化的极限率；并将理论分析拓展到一般非凸-非凸完全双层优化（带有上下层耦合变量 \(y\)）中。
相关工作与启发¶
- vs DBGD (Gong & Liu, 2021 / Cao et al., 2025)：确定性 DBGD 依赖精确梯度，下层梯度接近零时乘子无界；本文首次通过对偶分母扰动与罚正则化成功推广至完全随机非凸设置，并给出了首个联合收敛性理论。
- vs BLOOP (Hsieh et al., 2024)：BLOOP 仅在正交投影方向上避免了发散，但无法保证上层目标函数的驻点收敛；本文算法则是完整的联合稳态方法，严格保证 \((\epsilon_f, \epsilon_g)\)-稳态。
- vs 凸下层双层优化 (Cao et al., 2023 / Giang-Tran et al., 2025)：以往随机简单双层优化均严格依赖下层凸性或 Polyak-Łojasiewicz 条件；本文突破了这一理论禁区，适用于上下层双非凸的通用神经网络优化。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次为随机非凸-非凸简单双层优化建立显式的 \((\epsilon_f, \epsilon_g)\)-稳态点样本复杂度保证。
- 实验充分度: ⭐⭐⭐⭐ 在 TOFU 与 MUSE-News 两大主流 LLM 遗忘评测基准上进行了系统测试，兼顾样本与运行时间对比。
- 写作质量: ⭐⭐⭐⭐⭐ 结构清晰严谨，从动机、挑战、分步设计到渐进松弛假设的逻辑推导一气呵成。
- 价值: ⭐⭐⭐⭐⭐ 为双层优化、安全对齐与 LLM 遗忘提供了兼具理论深度与算法实用性的奠基性贡献。