論文の概要: On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2507.23155v1
• Date: Wed, 30 Jul 2025 23:10:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-01 17:19:08.908047
• Title: On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
• Title（参考訳）: 非凸単純二値最適化における定常点探索の複雑さについて
• Authors: Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, Aryan Mokhtari,
• Abstract要約: 動的勾配の簡単な実装可能な変種は、単純な双レベル問題を効果的に解くことができることを示す。 これは、一般の非単純二段階問題において、両レベルの合同局を保証する最初の結果時間アルゴリズムである。
• 参考スコア（独自算出の注目度）: 16.709026203727007
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the problem of solving a simple bilevel optimization problem, where the upper-level objective is minimized over the solution set of the lower-level problem. We focus on the general setting in which both the upper- and lower-level objectives are smooth but potentially nonconvex. Due to the absence of additional structural assumptions for the lower-level objective-such as convexity or the Polyak-{\L}ojasiewicz (PL) condition-guaranteeing global optimality is generally intractable. Instead, we introduce a suitable notion of stationarity for this class of problems and aim to design a first-order algorithm that finds such stationary points in polynomial time. Intuitively, stationarity in this setting means the upper-level objective cannot be substantially improved locally without causing a larger deterioration in the lower-level objective. To this end, we show that a simple and implementable variant of the dynamic barrier gradient descent (DBGD) framework can effectively solve the considered nonconvex simple bilevel problems up to stationarity. Specifically, to reach an $(\epsilon_f, \epsilon_g)$-stationary point-where $\epsilon_f$ and $\epsilon_g$ denote the target stationarity accuracies for the upper- and lower-level objectives, respectively-the considered method achieves a complexity of $\mathcal{O}\left(\max\left(\epsilon_f^{-\frac{3+p}{1+p}}, \epsilon_g^{-\frac{3+p}{2}}\right)\right)$, where $p \geq 0$ is an arbitrary constant balancing the terms. To the best of our knowledge, this is the first complexity result for a discrete-time algorithm that guarantees joint stationarity for both levels in general nonconvex simple bilevel problems.
• Abstract（参考訳）: 本稿では,下層問題の解集合に対して上層目標を最小化する,単純な二層最適化問題の解法について検討する。 我々は、上層と下層の両方の目的が滑らかであるが、潜在的に非凸であるような一般的な設定に焦点を当てる。 凸性 (convexity) やpolyak-{\L}ojasiewicz (PL) のような低次の目的に対する構造的仮定が存在しないため、大域的最適性を求める条件は一般に難解である。 代わりに、この問題の分類に適切な定常性の概念を導入し、多項式時間内にそのような定常点を求める一階アルゴリズムを設計することを目指す。 直感的には、この設定の定常性は、上層目標が下層目標に大きな劣化を引き起こすことなく、局所的に実質的に改善できないことを意味する。 この目的のために、動的バリア勾配勾配勾配(DBGD)フレームワークの単純かつ実装可能な変種が、非凸な単純な双レベル問題を定常性まで効果的に解くことができることを示す。 具体的には、$(\epsilon_f, \epsilon_g)$-stationary point-where $\epsilon_f$ と $\epsilon_g$ は、それぞれ上層および下層目標に対する目標定常精度を表すため、検討されたメソッドは、$\mathcal{O}\left(\max\left(\epsilon_f^{-\frac{3+p}{1+p}}, \epsilon_g^{-\frac{3+p}{2}}\right)\right)$, $p \geq 0$ は、項のバランスをとる任意の定数である。 我々の知る限りでは、これは離散時間アルゴリズムにおける最初の複雑さの結果であり、一般の非凸な単純二値問題において、両レベルの連立定常性を保証する。

関連論文リスト

• 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)
• 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)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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