提出单循环一阶算法，高效求解带线性约束的双层优化问题
A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
- 用惩罚与增广拉格朗日法将双层问题转为单层，避免二阶导计算
- 理论证明收敛速度从O(ε⁻³log(ε⁻¹))提升至O(ε⁻³)
- 适合需高效求解带约束双层优化的研究者与工程应用
我们研究下层问题为强凸且具有耦合线性约束的双层优化问题。为克服超目标函数可能存在的非光滑性以及海森矩阵带来的计算挑战，采用惩罚法与增广拉格朗日法将原问题重构为单层问题。特别地，通过刻画重构函数与原始超目标函数在值和导数上的接近性，建立了二者之间的强理论联系。基于该重构，提出一种用于线性约束双层优化的单循环一阶算法（SFLCB）。我们提供了严格的非渐近收敛率分析，表明其收敛速度相比以往双循环算法从O(ε⁻³log(ε⁻¹))提升至O(ε⁻³)。实验结果验证了理论结论，并展示了所提SFLCB算法的实际效率。仿真代码已公开于https://github.com/ShenGroup/SFLCB。
原文摘要 · Abstract (English)
We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non-smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian methods to reformulate the original problem as a single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose a single-loop, first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improvement over prior double-loop algorithms -- form $O(ε^{-3}\log(ε^{-1}))$ to $O(ε^{-3})$. The experiments corroborate our theoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https://github.com/ShenGroup/SFLCB.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。