論文の概要: To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity

• arxiv url: http://arxiv.org/abs/2609.30501v1
• Date: Thu, 24 Sep 2026 19:40:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.123987
• Title: To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationarity
• Title（参考訳）: 非凸下層の二段階最適化を解くためには2次定常性が必要である
• Abstract要約: 機械学習の既存の問題のほとんどは、低レベル凸(LLSC)または低レベル凸(LLGC)設定に限られている。 本稿では,その初期段階にある一般低レベルノン(LLNC)設定におけるBLO問題の解決について検討する。
• 参考スコア（独自算出の注目度）: 16.121146457416053
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 近年、二段階最適化(BLO)は、多くの複雑でネストした機械学習問題に対処するための強力なフレームワークとして登場したが、既存の研究の多くは、低レベルの強凸(LLSC)または低レベルの一般凸(LLGC)設定に限定されている(つまり、低レベルの客観的関数は少なくとも凸(convex)と仮定される)。 LLSC/LLGCの仮定はより難解なアルゴリズム設計と理論的解析をもたらすが、実際には多くの機械学習問題を包含するには厳密すぎる。 BLOにおけるLLSC/LLGC仮定の限界は、BLOの問題をLLNC(下層非凸)設定で解くことの動機となっている。 LLNC-BLOに関する文献では、既存の研究の多くは、抽出可能な理論解析のための下層目標関数の付加構造を必要とするか、LLSC/LLGC設定から受け継がれるが、LLNC設定においてその効果を失う可能性のある下層サロゲート問題として、一階定常性再構成を採用するかのどちらかである。 このギャップを埋めるために,2次定常性に基づくサロゲートを用いて非凸な低レベル問題を再構成することを提案する。 本稿では,2レベル問題に対する摂動勾配アルゴリズム PROBE (Perturbed gradient algorithm for bilevel problem) を提案し,低レベルサドル点の探索とエスケープによって先行研究の限界を克服することを示す。 我々は PROBE が有限時間収束率 $O(T^{-2/5})$ を達成することを証明し、T は反復を表す。 我々の知る限り、この研究はLLNC-BLO一般において下位2階定常解を達成するための有限時間収束を確立する最初のものである。 大規模言語モデルに基づくデータキュレーションタスクとメタラーニングタスクの両方に関する実験により, PROBEがSOTA法より優れていることが示された。

関連論文リスト

• DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity [77.51981761667302]
  二次正規化二段階分散最適化 (DUET) と呼ばれる新しい単一ループDBOアルゴリズムを導入する。 DUETは、低レベル(LL)の目的に2次正規化を減少させることにより、LLSCの必要性を排除する。 我々の知る限りでは、データを不均一に分散した設定の下でLLSCなしでDBOに取り組むのは、これが初めてです。
  論文  参考訳（メタデータ） (2026-06-19T06:45:13Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm [8.479947546216131]
  We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA) LV-HBAは特に機械学習アプリケーションに適している。
  論文  参考訳（メタデータ） (2024-01-29T13:50:56Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。 最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
  論文  参考訳（メタデータ） (2023-06-04T17:54:11Z)
• Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity [43.092883358935545]
  単ループ二値乗算器 (sl-BAMM) を両レベル最適化 (BLO) のために提案する。 我々は, sl-BAMMのKKT定常点への非漸近収束解析を行い, 解析の利点は強い勾配有界性仮定の欠如にある。
  論文  参考訳（メタデータ） (2023-02-07T11:29:05Z)
• Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
  勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。 機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。 上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
  論文  参考訳（メタデータ） (2021-10-11T03:13:39Z)
• A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton [49.23948907229656]
  Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。 LLS条件なしでBDAの収束を証明する新しい手法を導出する。 我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
  論文  参考訳（メタデータ） (2020-06-07T05:18:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。