論文の概要: Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

• arxiv url: http://arxiv.org/abs/2605.08006v1
• Date: Fri, 08 May 2026 16:59:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.220796
• Title: Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
• Title（参考訳）: ミニマックスと制約付き下層問題を用いた二値最適化のための罰則に基づく一階法
• Authors: Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin,
• Abstract要約: ペナルティに基づく二レベル最小値最適化法を,低レベルの問題に対して強い凸性を必要とすることなく開発する。 決定論的設定では、提案法は、$tildeO(-4)$ complexityの$-KKT点を求める。 我々は、勾配オラクルしか利用できない設定へのアプローチを拡張し、提案手法が$tildeO(-9)$の複雑さを持つ約$-KKTの点を証明した。
• 参考スコア（独自算出の注目度）: 15.568350058772744
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a class of bilevel optimization problems in which both the upper- and lower-level problems have minimax structures. This setting captures a broad range of emerging applications. Despite the extensive literature on bilevel optimization and minimax optimization separately, existing methods mainly focus on bilevel optimization with lower-level minimization problems, often under strong convexity assumptions, and are not directly applicable to the minimax lower-level setting considered here. To address this gap, we develop penalty-based first-order methods for bilevel minimax optimization without requiring strong convexity of the lower-level problem. In the deterministic setting, we establish that the proposed method finds an $ε$-KKT point with $\tilde{O}(ε^{-4})$ oracle complexity. We further show that bilevel problems with convex constrained lower-level minimization can be reformulated as special cases of our framework via Lagrangian duality, leading to an $\tilde{O}(ε^{-4})$ complexity bound that improves upon the existing $\tilde{O}(ε^{-7})$ result. Finally, we extend our approach to the stochastic setting, where only stochastic gradient oracles are available, and prove that the proposed stochastic method finds a nearly $ε$-KKT point with $\tilde{O}(ε^{-9})$ oracle complexity.
• Abstract（参考訳）: 上層と下層の両方に極小構造を持つ二段階最適化問題のクラスについて検討する。 この設定は、幅広い新興アプリケーションを取り込む。 バイレベル最適化とミニマックス最適化を別々に研究しているにもかかわらず、既存の手法は主に低レベルの最小化問題による双レベル最適化に焦点を当てており、しばしば強い凸性仮定の下で、ここで考慮されたミニマックスの低レベル設定には直接適用できない。 このギャップに対処するために, 2レベル最小値最適化のためのペナルティに基づく一階法を開発した。 決定論的設定では、提案法は、$\tilde{O}(ε^{-4})$ Oracle complexity の$ε$-KKT点を求める。 さらに、凸制約付き低レベル最小化の両レベル問題は、ラグランジアン双対性(Lagrangian duality)を介して、我々のフレームワークの特別なケースとして再定義可能であることを示し、既存の$\tilde{O}(ε^{-4})$の複雑性境界が、既存の$\tilde{O}(ε^{-7})$の結果によって改善されることを示した。 最後に、確率的勾配オラクルのみが利用できる確率的設定にアプローチを拡張し、提案された確率的手法が、$\tilde{O}(ε^{-9})$ Oracle complexity の約$ε$-KKT点を求めることを証明した。

関連論文リスト

• Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles [26.059192929942842]
  少なくとも$()/2$呼び出しは、関連する設定で最もよく知られた境界を強化する必要があります。 我々の結果は、単純化された体制でさえ、そのような体制が低レベルに適用可能であることを示唆していることを示唆している。
  論文  参考訳（メタデータ） (2025-11-24T19:43:40Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。 最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
  論文  参考訳（メタデータ） (2023-06-04T17:54:11Z)
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem [18.15207779559351]
  そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。 本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
  論文  参考訳（メタデータ） (2022-06-17T16:12:47Z)
• FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
  多くの現代のML問題は、ミニマックスと合成最適化を仮定したネストされた双レベルプログラミングに該当する。 我々は、一般的なネスト問題に対処するフェデレーション付き交互勾配法を提案する。
  論文  参考訳（メタデータ） (2022-05-04T17:48:55Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)

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

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