論文の概要: Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles

• arxiv url: http://arxiv.org/abs/2511.19656v2
• Date: Wed, 26 Nov 2025 03:12:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-27 14:46:34.423008
• Title: Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
• Title（参考訳）: 第一次オラクルを用いた非凸-ストロングリ-凸二レベル最適化のための低次複素境界
• Authors: Kaiyi Ji,
• Abstract要約: 少なくとも$()/2$呼び出しは、関連する設定で最もよく知られた境界を強化する必要があります。 我々の結果は、単純化された体制でさえ、そのような体制が低レベルに適用可能であることを示唆していることを示唆している。
• 参考スコア（独自算出の注目度）: 26.059192929942842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure. In this work, we focus on the smooth nonconvex-strongly-convex setting and develop new hard instances that yield nontrivial lower bounds under deterministic and stochastic first-order oracle models. In the deterministic case, we prove that any first-order zero-respecting algorithm requires at least $Ω(κ^{3/2}ε^{-2})$ oracle calls to find an $ε$-accurate stationary point, improving the optimal lower bounds known for single-level nonconvex optimization and for nonconvex-strongly-convex min-max problems. In the stochastic case, we show that at least $Ω(κ^{5/2}ε^{-4})$ stochastic oracle calls are necessary, again strengthening the best known bounds in related settings. Our results expose substantial gaps between current upper and lower bounds for bilevel optimization and suggest that even simplified regimes, such as those with quadratic lower-level objectives, warrant further investigation toward understanding the optimal complexity of bilevel optimization under standard first-order oracles.
• Abstract（参考訳）: 双レベル最適化の上限保証は広く研究されているが、双レベル構造の複雑さのため、下位境界の進行は制限されている。 本研究では,スムーズな非凸-強凸設定に着目し,決定論的および確率的一階オラクルモデルの下で非自明な下界を生み出す新しいハードインスタンスを開発する。 決定論的な場合、任意の一階ゼロ参照アルゴリズムが少なくとも$Ω(κ^{3/2}ε^{-2})$ oracle コールで$ε$-正確な定常点を見つけ、単階非凸最適化や非凸-強凸 min-max 問題で知られている最適下界を改善する必要があることを証明する。 確率的場合、少なくとも$Ω(κ^{5/2}ε^{-4})$stchastic oraclecallが必要であることが示され、関連する設定において最もよく知られた境界が強化される。 その結果,2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化では2次最適化が最適であることがわかった。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization [5.269633789700637]
  emphBilevel Optimization (BLO) における新しい一階法を提案する。 低レベル関数が典型的に強い凸性仮定を持つという仮定の下では、emphBilevel Approximation (textttPRAF$2$BA) が提案される。 また,低次関数が典型的に強い凸性仮定を欠いている場合,BLOにおける高次関数の定常点の探索についても検討する。
  論文  参考訳（メタデータ） (2024-05-01T23:59:36Z)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。 本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
  論文  参考訳（メタデータ） (2023-07-14T19:59:18Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization [1.6973426830397942]
  平滑な非有限和最適化における高階法の下限を証明する。 pth-order regularized method は有限和の目的から利益を得ることができないことを示す。 新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
  論文  参考訳（メタデータ） (2021-03-08T23:33:58Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)

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

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