論文の概要: On the Condition Number Dependency in Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2511.22331v1
• Date: Thu, 27 Nov 2025 11:03:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:55.528263
• Title: On the Condition Number Dependency in Bilevel Optimization
• Title（参考訳）: 2レベル最適化における条件数依存性について
• Authors: Lesi Chen, Jingzhao Zhang,
• Abstract要約: 実現可能な領域が下層問題の解である上層問題によって定義される目的関数間の双レベル最適化。 2次および超滑らかな問題に対して、それぞれ$(_y13/4 )$と$(4-4)$を示す。
• 参考スコア（独自算出の注目度）: 23.985835962136793
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an $ε$-stationary point with first-order methods when the upper-level problem is nonconvex and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen el al., JMLR 2025) achieve a $\tilde{\mathcal{O}}(κ^4 ε^{-2})$ upper bound that is near-optimal in $ε$. However, the optimal dependency on the condition number $κ$ is unknown. In this work, we establish a new $Ω(κ^2 ε^{-2})$ lower bound and $\tilde{\mathcal{O}}(κ^{7/2} ε^{-2})$ upper bound for this problem, establishing the first provable gap between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show $Ω(κ_y^{13/4} ε^{-12/7})$ and $Ω(κ^{17/10} ε^{-8/5})$ lower bounds, respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from $Ω(κ/\sqrtε)$ to $Ω(κ^{5/4} / \sqrtε)$. (3) For smooth stochastic problems, we show an $Ω(κ^4 ε^{-4})$ lower bound.
• Abstract（参考訳）: 双レベル最適化は、実現可能な領域が下位レベルの問題の解である上層問題によって定義される目的関数を最小化する。 上層問題は非凸であり、下層問題は強凸である場合、一階法でε$定常点を求めるというオラクルの複雑さについて検討する。 最近の研究 (Ji et al , ICML 2021; Arbel and Mairal, ICLR 2022; Chen el al., JMLR 2025) は$\tilde{\mathcal{O}}(κ^4 ε^{-2})$ ε$ で最適に近い上限を達成している。 しかし、条件番号$κ$の最適依存は未知である。 本研究では、新しい$Ω(κ^2 ε^{-2})$ lower bound と $\tilde{\mathcal{O}}(κ^{7/2} ε^{-2})$ upper bound を確立し、この設定においてバイレベル問題とミニマックス問題の間の最初の証明可能なギャップを確立する。 下界は、高次滑らかな関数、確率的オラクル、凸超対象を含む様々な設定に拡張できる: 1) 2次および任意に滑らかな問題に対して、$Ω(κ_y^{13/4} ε^{-12/7})$と$Ω(κ^{17/10} ε^{-8/5})$下界を示す。 2)凸-強凸問題に対しては、それまでの最良の下界(Ji, Liang, JMLR 2022)を$Ω(κ/\sqrtε)$から$Ω(κ^{5/4} / \sqrtε)$に改善する。 (3) 滑らかな確率問題に対して、$Ω(κ^4 ε^{-4})$lowboundを示す。

関連論文リスト

• Stochastic Bilevel Optimization with Heavy-Tailed Noise [27.792016944321627]
  本稿では,低次問題を強く凸し,高次問題を非定常雑音レベルとするスムーズな二段階最適化について考察する。
  論文  参考訳（メタデータ） (2025-09-18T13:37:40Z)
• Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization [27.377966916440432]
  上層問題と下層問題とが凸である場合、二レベル最適化のための$epsilon-gradient pointを求める複雑性を示す。 最近の研究は、一階スムーズな問題に対して$tildemathcalO(epsilon-4)$ lower boundを達成した、一階近似 F$2$SA を提案した。
  論文  参考訳（メタデータ） (2025-09-03T02:02:52Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:29:14Z)
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain [11.562923882714093]
  Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。 我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
  論文  参考訳（メタデータ） (2021-10-08T07:46:18Z)
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization [31.0295459253155]
  min-max最適化問題の定常点を求めるための1次オラクル下界を提供する。 私たちの分析は、上限が$epsilon$依存性最大$kappa$で最適であることを示しています。 この結果から, 上の$mathcalOkappa3 epsilon-4)$ in (Lin et al., 2020a) と, 近似数依存性の下位境界との間には, 有意な差があることが示唆された。
  論文  参考訳（メタデータ） (2021-04-18T04:30:01Z)

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

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