論文の概要: Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

• arxiv url: http://arxiv.org/abs/2610.24538v1
• Date: Sat, 17 Oct 2026 07:58:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-22 17:47:39.07252
• Title: Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
• Title（参考訳）: 完全な1次Oracleによる有限サムバイレベル最適化の高速化
• Abstract要約: 低次変数に対するペナルティ近似と分散還元補正を組み合わせた2レベル最適化のためのインプリシット補正(BO)を提案する。 シングルレベル還元は、$$と$vareps$への依存が固定$に対する対数因子に最適であることを示している。
• 参考スコア（独自算出の注目度）: 2.076917207095107
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.
• Abstract（参考訳）: 非凸-強凸二レベル最適化を有限サム目的と完全一階オラクルを用いて検討する。 低レベル変数に対するペナルティ近似と分散還元補正を組み合わせたSICBO(Sampred Implicit Corrections for Bilevel Optimization)を提案する。 成分的に低い凸性の下で、SICBO は $\mathbb{E}\|\nablash(x)\|^2\le\varepsilon^2$ in $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient call, ここで$N$ は成分の総数、$κ$ は正規化下層条件数である。 境界は勾配のみを用いて平方根有限サム依存を達成し、滑らかな問題に対して最もよく知られた決定論的完全一階条件数指数を保存する。 我々の改善は、非線型補正誤差に対する曲率依存境界(英語版)(curvature-dependent bound)から導かれるもので、これは長さ $\tilde'(\sqrt{N/κ})$ のエポックを許容し、サイズ $\tilde'(\sqrt{Nκ})$ のバッチを許容する。 シングルレベル還元は、$N$と$\varepsilon$への依存が、固定された$κ$に対する対数因子に最適であることを示している。

関連論文リスト

• Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  インクリメンタルな1次アルゴリズムをゼロ参照する場合、複雑性は$tildeO(n+sqrtn,Lvarepsilon-2)$で、クエリ予算は固定される。
  論文  参考訳（メタデータ） (2026-10-04T04:38:36Z)
• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• 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)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

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

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