2025-11-22T15:28:16.372787

An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization

Nie, Li, Wen
Recently, lower-level constrained bilevel optimization has attracted increasing attention. However, existing methods mostly focus on either deterministic cases or problems with linear constraints. The main challenge in stochastic cases with general constraints is the bias and variance of the hyper-gradient, arising from the inexact solution of the lower-level problem. In this paper, we propose a novel stochastic augmented Lagrangian value function method for solving stochastic bilevel optimization problems with nonlinear lower-level constraints. Our approach reformulates the original bilevel problem using an augmented Lagrangian-based value function and then applies a penalized stochastic gradient method that carefully manages the noise from stochastic oracles. We establish an equivalence between the stochastic single-level reformulation and the original constrained bilevel problem and provide a non-asymptotic rate of convergence for the proposed method. The rate is further enhanced by employing variance reduction techniques. Extensive experiments on synthetic problems and real-world applications demonstrate the effectiveness of our approach.
academic

An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization

基本信息

  • 论文ID: 2509.24249
  • 标题: An Augmented Lagrangian Value Function Method for Lower-level Constrained Stochastic Bilevel Optimization
  • 作者: Hantao Nie (北京大学), Jiaxiang Li (明尼苏达大学), Zaiwen Wen (北京大学)
  • 分类: math.OC (数学优化与控制)
  • 发表时间: 2025年1月 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2509.24249v2

摘要

本文针对带有非线性下层约束的随机双层优化问题，提出了一种新颖的随机增广拉格朗日值函数方法。该方法通过增广拉格朗日值函数重新表述原始双层问题，并应用惩罚随机梯度方法来精心管理来自随机预言机的噪声。作者建立了随机单层重构与原始约束双层问题之间的等价性，并提供了非渐近收敛率分析。通过方差减少技术进一步改进了收敛率。在合成问题和真实应用上的大量实验验证了该方法的有效性。

研究背景与动机

  1. 问题背景: 带下层约束的双层优化(LC-BLO)在机器学习领域应用广泛，包括超参数优化、元学习、强化学习等。这类问题具有层次结构，上层问题的解依赖于下层约束优化问题的最优解。
  2. 现有方法局限性:
    • 大多数现有方法仅关注确定性情况或线性约束问题
    • 随机情况下的非线性约束问题缺乏有效解决方案
    • 主要挑战在于下层问题不精确解导致的超梯度偏差和方差
  3. 技术挑战:
    • 超目标函数的非光滑性
    • 由于下层问题不精确解导致的超梯度偏差
    • 随机预言机带来的噪声管理
  4. 研究动机: 填补随机非线性约束双层优化理论和算法的空白，为实际机器学习应用提供理论保证的高效算法。

核心贡献

  1. 新颖重构方法: 提出基于随机增广拉格朗日函数及其Moreau包络的双层问题重构，有效处理下层问题不精确解带来的噪声
  2. 理论等价性: 建立了随机单层重构与原始双层问题的等价性，提供了实用且理论基础扎实的方法
  3. 首个收敛分析: 为非线性LC-BLO在随机设置下的值函数方法提供首个收敛性分析，证明了Õ(cε⁻²), Õ(cc₁²ε⁻²)的样本复杂度
  4. 方差减少改进: 通过方差减少技术将上层变量的样本复杂度改进至Õ(c^1.5ε⁻^1.5)

方法详解

任务定义

考虑随机下层约束双层优化问题：

下层问题:

min_{y∈Y} G(x,y) = E_{ξ~D_ξ}[g(x,y;ξ)]
s.t. H_i(x,y) ≤ 0, i = 1,...,p

上层问题:

min_{x∈X} F(x,y*(x)) = E_{ζ~D_ζ}[f(x,y*(x);ζ)]
s.t. y*(x) ∈ arg min_{y∈Y(x)} G(x,y)

其中Y(x) := {y ∈ Y | H(x,y) ≤ 0}是下层可行域。

模型架构

1. 增广拉格朗日重构

引入增广拉格朗日惩罚项：

A_{γ₁}(x,y,z) = (1/2γ₁)∑ᵢ[γ₁zᵢ + Hᵢ(x,y)]²₊

定义增广拉格朗日函数：

L_{γ₁}(x,y,z) = G(x,y) + A_{γ₁}(x,y,z)

2. Moreau包络值函数

构造对偶函数及其Moreau包络：

D_{γ₁}(x,z) = min_{y∈Y} L_{γ₁}(x,y,z)
E^{γ₂}_{γ₁}(x,z) = max_{λ∈ℝ^p₊} {D_{γ₁}(x,λ) - (γ₂/2)||λ-z||²}

3. 单层重构

将原双层问题重构为：

min_{(x,y,z)∈X×Y×ℝ^p₊} F(x,y)
s.t. Ĝ(x,y,z;ξ) ≤ ε₁, (1/2)∑ᵢ[Hᵢ(x,y)]²₊ ≤ ε₂²

其中Ĝ(x,y,z;ξ) = G(x,y) - ℓ_γ(x,z,ŵ(ξ),λ̂(ξ))。

4. 惩罚方法

采用增广拉格朗日惩罚重构：

min_{(x,y,z)∈X×Y×Z} E_ξ[Ψ(x,y,z;ξ)]

其中Ψ(x,y,z;ξ) := F(x,y) + c₁Ĝ(x,y,z;ξ) + (c₂/2)∑ᵢHᵢ(x,y)²₊

技术创新点

  1. 双重循环算法结构:
    • 内循环：使用随机增广拉格朗日方法(SALM)求解子问题
    • 外循环：对重构问题应用随机梯度下降
  2. 偏差控制机制: 通过控制下层解的精度来缓解偏差梯度问题
  3. 方差减少技术: 采用类似STORM的更新规则减少上层变量的样本复杂度

实验设置

数据集

  1. 合成问题: 来自Jiang et al. (2012)的测试例子，添加高斯噪声σ = 0.1
  2. SVM超参数优化: 在Diabetes和Fourclass数据集上进行
  3. 权重衰减调优: 在digit数据集上使用两层MLP进行神经网络权重衰减参数优化

评价指标

  • 测试精度
  • 收敛时间
  • 迭代次数
  • 目标函数值

对比方法

  • LV-HBA: 基于拉格朗日值函数的方法
  • GAM: 梯度增广方法
  • BLOCC: 双层优化约束控制方法
  • SALVF: 本文提出的基础方法
  • SALVF-VR: 本文提出的方差减少版本

实现细节

  • 内循环步长：ηⱼ = η/(j+1), ρⱼ = ρ/(j+1)
  • 外循环步长：αₖ = α < 1/(2L_Ψ)
  • 样本大小：rₖ = r, qₖ = q, sₖ = s (常数)
  • 惩罚参数：c₁, c₂根据理论分析选择

实验结果

主要结果

  1. 合成问题: SALVF和SALVF-VR都能收敛到全局最优解附近，SALVF-VR的分布更加集中，验证了方差减少的加速效果
  2. SVM超参数优化:
    • SALVF在测试精度上优于所有基线方法
    • 虽然BLOCC也能达到相近的峰值精度，但SALVF的迭代更加时间高效
    • 在Diabetes数据集上达到约80%测试精度，在Fourclass数据集上达到约75%测试精度
  3. 权重衰减调优:
    • 所有双层方法都比无权重衰减的基准表现更好，有效减少了过拟合
    • SALVF在时间效率上最优，得益于双循环迭代过程的简洁性

理论结果

  1. 样本复杂度:
    • SALVF: (Õ(cε⁻²), Õ(cc₁²ε⁻²))
    • SALVF-VR: (Õ(c^1.5ε⁻^1.5), Õ(c^1.5c₁²ε⁻^2.5))
  2. 收敛率:
    • SALVF: Õ(cε⁻¹)迭代复杂度
    • SALVF-VR: Õ(c^1.5ε⁻^1.5)迭代复杂度

实验发现

  1. 方差减少有效性: SALVF-VR相比SALVF在分布集中度和收敛速度上都有显著改进
  2. 时间效率优势: 双循环结构相比三循环方法(如BLOCC)具有明显的计算优势
  3. 实用性验证: 在真实机器学习任务中表现优异，验证了方法的实用价值

相关工作

主要研究方向

  1. 隐式梯度方法(IG): 主要关注计算超梯度，但需要二阶导数，计算成本高
  2. 下层值函数方法(LLVF): 引入下层问题值函数，作为无Hessian的替代方案
  3. 惩罚方法: 将约束问题转化为无约束问题求解

本文优势

  1. 首个随机非线性约束分析: 现有工作主要关注确定性或线性约束情况
  2. 理论保证: 提供非渐近收敛率分析
  3. 实用性: 无需Hessian计算，适合大规模问题

结论与讨论

主要结论

  1. 成功解决了随机非线性约束双层优化这一重要但未充分研究的问题
  2. 提出的增广拉格朗日值函数方法在理论和实践上都表现优异
  3. 方差减少技术有效改进了算法性能

局限性

  1. 样本复杂度依赖性: 下层变量的样本复杂度仍然较高(O(c₁²ε⁻¹))
  2. 参数选择: 惩罚参数c₁, c₂的选择依赖于问题参数，可能需要调优
  3. 强凸假设: 下层问题需要满足强凸性假设

未来方向

  1. 样本复杂度改进: 探索是否能同时减少上层和下层变量的样本复杂度
  2. 自适应参数选择: 开发自适应选择惩罚参数的策略
  3. 非凸扩展: 扩展到下层问题非凸的情况

深度评价

优点

  1. 理论贡献显著: 首次为随机非线性约束双层优化提供完整的理论分析
  2. 方法设计巧妙: 增广拉格朗日重构既保持了问题等价性又改善了算法性质
  3. 实验充分: 从合成问题到实际应用的全面验证
  4. 写作清晰: 数学推导严谨，表述清楚

不足

  1. 计算复杂度: 双循环结构仍然带来较高的计算成本
  2. 假设条件: 需要多个技术假设(强凸性、Slater条件等)
  3. 参数敏感性: 算法性能可能对惩罚参数选择敏感

影响力

  1. 学术价值: 填补了重要理论空白，为后续研究提供基础
  2. 实用价值: 在机器学习的多个重要应用中都有潜在用途
  3. 可复现性: 提供了详细的算法描述和理论分析

适用场景

  1. 超参数优化: 特别是带约束的超参数调优问题
  2. 元学习: 需要在约束条件下学习学习策略
  3. 强化学习: 带约束的策略优化问题
  4. 神经架构搜索: 在资源约束下的架构优化

参考文献

论文引用了49篇相关文献，主要包括：

  • 双层优化的经典工作和最新进展
  • 增广拉格朗日方法的理论基础
  • 随机优化和方差减少技术
  • 机器学习中的应用案例

总体评价: 这是一篇高质量的理论与应用并重的论文，在重要但困难的问题上取得了实质性进展，为随机约束双层优化领域做出了重要贡献。方法新颖，理论严谨，实验充分，具有很好的学术价值和实用前景。