論文の概要: Optimal Stochastic Bilevel Optimization with First-Order Oracles

• arxiv url: http://arxiv.org/abs/2610.01843v1
• Date: Thu, 01 Oct 2026 15:11:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.217434
• Title: Optimal Stochastic Bilevel Optimization with First-Order Oracles
• Title（参考訳）: 1次オラクルを用いた確率的二値最適化
• Abstract要約: MRT-FDは、上位変数と下位変数を同時に追跡する1次解である。 MRT-FDはイテレーション毎に更新を行う。 任意の固定有限$p$に対して一致する$varepsilon$を証明し、この一階オラクル設定における複雑性ギャップを閉じる。
• 参考スコア（独自算出の注目度）: 4.741100658955038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-$p$ finite differences. For any fixed finite smoothness order $p\ge1$ in the lower-level variable, MRT-FD finds an $\varepsilon$-stationary point using $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient queries. We also prove a matching $Ω(\varepsilon^{-4-2/p})$ oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on $\varepsilon$ is optimal for every fixed finite $p$, closing the upper--lower complexity gap in this stochastic first-order oracle setting.
• Abstract（参考訳）: 確率的一階オラクルの下で非凸-強凸二値最適化について検討する。 MRT-FDは,高次変数,低次解,および高次対象の暗黙的微分から生じる補助応答を同時に追跡する単一ループ1次法である。 MRT-FDは反復ごとに各変数を1回更新し、次数-$p$有限差分を用いて2階微分作用を近似する。 低レベル変数の任意の固定有限滑らか性次数$p\ge1$に対して、MRT-FD は $\mathcal{O}(\varepsilon^{-4/p})$確率勾配クエリを用いて $\varepsilon$-定常点を求める。 また、一致する$Ω(\varepsilon^{-4/p})$ oracle lower bound も証明する。 下界の構成は、より強い確率的なオラクルを持つ硬い非凸最小化鎖から始まり、スカラーの低レベル変数との正弦波結合を通して双レベル問題に持ち上げる。 したがって、$\varepsilon$ への依存は任意の固定有限$p$ に対して最適であり、この確率的な一階オラクル設定におけるより低い複雑性のギャップを閉じる。

関連論文リスト

• SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization [9.118433290504035]
  我々は、Stoc-SGHAが$Oleft(bar_y-4)$のオラクル複雑性を、任意の$in(1)$に対して少なくとも$$$と、追加の仮定の下で$Oleft(bar_y-4)$の複雑さを達成することを示す。 決定論的設定では、Stoc-SGHAは$Oleft(bar_y)$のオラクル複雑性を少なくとも$in(1)$に対して$$$$$で達成し、$Oleft(bar_y)$以下の複雑さを達成している。
  論文  参考訳（メタデータ） (2026-08-24T13:00:40Z)
• First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
  本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。 線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
  論文  参考訳（メタデータ） (2024-06-18T16:41:21Z)
• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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