To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

📄 arXiv: 2609.30501v1 📥 PDF

作者: Zhiyao Zhang, Menglu Yu, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu

分类: cs.LG

发布日期: 2026-09-24

💡 一句话要点

提出PROBE算法以解决非凸下层双层优化问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 双层优化 非凸优化 二阶平稳性 机器学习 算法设计 收敛性分析 元学习 数据整理

📋 核心要点

  1. 现有的双层优化方法大多假设下层目标函数为凸，限制了其在实际复杂问题中的应用。
  2. 本文提出通过二阶平稳性重构非凸下层问题，设计了PROBE算法以有效逃离下层鞍点。
  3. 实验表明，PROBE算法在多个任务中表现优异，收敛速度达到O(T^{-2/5})，超越了现有方法。

📝 摘要（中文）

尽管双层优化（BLO）近年来成为解决复杂机器学习问题的强大框架，但大多数研究仍局限于下层强凸或一般凸的设定。本文探讨在一般下层非凸（LLNC）环境中解决BLO问题，提出基于二阶平稳性的替代方案，并设计了PROBE算法，证明其在有限时间内收敛至下层二阶平稳解。实验结果表明，PROBE在大语言模型数据整理任务和元学习任务中优于现有最先进方法。

🔬 方法详解

问题定义：本文旨在解决在下层非凸环境中进行双层优化的问题。现有方法多依赖于下层目标函数的凸性假设，导致在实际应用中面临局限性。

核心思路：论文提出通过二阶平稳性重构下层非凸问题，利用这一重构来设计PROBE算法，从而保证下层局部最优解的有效性。

技术框架：整体框架包括对下层非凸问题的二阶平稳性重构，接着通过扰动梯度算法进行优化，最终实现对下层鞍点的有效逃离。

关键创新：本研究首次在一般下层非凸双层优化中建立有限时间收敛性，提出的PROBE算法通过二阶平稳性替代了传统的一阶平稳性方法，显著提高了算法的有效性。

关键设计：在算法设计中，设置了适当的扰动参数以确保收敛性，并采用了特定的损失函数以适应非凸环境，确保了算法在复杂任务中的稳定性和有效性。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果显示，PROBE算法在大语言模型数据整理任务和元学习任务中均优于现有最先进方法，收敛速度达到O(T^{-2/5})，有效逃离下层鞍点，展现出显著的性能提升。

🎯 应用场景

该研究的潜在应用领域包括复杂的机器学习任务，如元学习、数据整理和深度学习模型的优化等。通过解决非凸下层问题，PROBE算法能够在更广泛的实际场景中提供有效的优化解决方案，推动相关领域的发展。

📄 摘要（原文）

Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.e., the lower-level objective function is assumed to be, at least, convex). While the LLSC/LLGC assumptions render more tractable algorithmic design and theoretical analysis, they are too rigid to encompass many machine learning problems in practice. The limitations of LLSC/LLGC assumptions in BLO motivate us to investigate solving the BLO problem in the general lower-level nonconvex (LLNC) settings, which remains in its infancy. In the literature on LLNC-BLO, most of the existing works either require additional structures in the lower-level objective function for tractable theoretical analysis, or adopt the first-order stationarity reformulation as a lower-level surrogate problem, which is inherited from the LLSC/LLGC settings but could lose their effectiveness in the LLNC setting. To bridge this gap, we propose to reformulate the nonconvex lower-level problem using a second-order stationarity-based surrogate, the solution of which guarantees a local optimal solution at the lower level. Based on this reformulation, we propose the PROBE (Perturbed gradient algorithm for bilevel problem) and show that it overcomes the limitations of prior works by probing and escaping lower-level saddle points. We prove that PROBE achieves a finite-time convergence rate of $O(T^{-2/5})$, where T denotes iterations. To our knowledge, this work is the first to establish the finite-time convergence for achieving lower-level second-order stationary solutions in general LLNC-BLO. Our experiments on both a large language model-based data curation task and a meta-learning task also show that PROBE outperforms SOTA methods.