論文の概要: Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2509.02937v1
• Date: Wed, 03 Sep 2025 02:02:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 21:40:46.385106
• Title: Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization
• Title（参考訳）: 高スムーズ確率二値最適化のための高速勾配法
• Authors: Lesi Chen, Junru Li, Jingzhao Zhang,
• Abstract要約: 上層問題と下層問題とが凸である場合、二レベル最適化のための$epsilon-gradient pointを求める複雑性を示す。 最近の研究は、一階スムーズな問題に対して$tildemathcalO(epsilon-4)$ lower boundを達成した、一階近似 F$2$SA を提案した。
• 参考スコア（独自算出の注目度）: 27.377966916440432
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the complexity of finding an $\epsilon$-stationary point for stochastic bilevel optimization when the upper-level problem is nonconvex and the lower-level problem is strongly convex. Recent work proposed the first-order method, F${}^2$SA, achieving the $\tilde{\mathcal{O}}(\epsilon^{-6})$ upper complexity bound for first-order smooth problems. This is slower than the optimal $\Omega(\epsilon^{-4})$ complexity lower bound in its single-level counterpart. In this work, we show that faster rates are achievable for higher-order smooth problems. We first reformulate F$^2$SA as approximating the hyper-gradient with a forward difference. Based on this observation, we propose a class of methods F${}^2$SA-$p$ that uses $p$th-order finite difference for hyper-gradient approximation and improves the upper bound to $\tilde{\mathcal{O}}(p \epsilon^{4-p/2})$ for $p$th-order smooth problems. Finally, we demonstrate that the $\Omega(\epsilon^{-4})$ lower bound also holds for stochastic bilevel problems when the high-order smoothness holds for the lower-level variable, indicating that the upper bound of F${}^2$SA-$p$ is nearly optimal in the highly smooth region $p = \Omega( \log \epsilon^{-1} / \log \log \epsilon^{-1})$.
• Abstract（参考訳）: 本稿では,上層問題が非凸であり,下層問題が強凸である場合に,確率的二段階最適化のための$\epsilon$-stationary点を求める複雑性について検討する。 最近の研究では、一階スムーズな問題に対して、$\tilde{\mathcal{O}}(\epsilon^{-6})$上の複雑性を達成できる一階法 F${}^2$SA が提案されている。 これは、最適な$\Omega(\epsilon^{-4})$複雑さよりも遅く、シングルレベルである。 本研究では,高次スムーズな問題に対して高速な速度が達成可能であることを示す。 まず、F$^2$SA を超勾配を前方差で近似するものとして再構成する。 この観測に基づいて、超次数近似に$p$th-次有限差分を使い、上界を$\tilde{\mathcal{O}}(p \epsilon^{4-p/2})$に改善するF${}^2$SA-$p$を提案する。 最後に、$\Omega(\epsilon^{-4})$ lowerbound もまた、F${}^2$SA-$p$ の上界が高滑らかな領域 $p = \Omega( \log \epsilon^{-1} / \log \log \epsilon^{-1})$ においてほぼ最適であることを示す高階滑らか度が下層変数に対して成り立つとき、確率的二値問題に対しても成り立つことを示した。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• On the Complexity of First-Order Methods in Stochastic Bilevel Optimization [9.649991673557167]
  両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。 既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。 我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
  論文  参考訳（メタデータ） (2024-02-11T04:26:35Z)
• Achieving ${O}(ε^{-1.5})$ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization [19.273672650548722]
  我々は,非精度な定常点勾配二値最適化のために,$O(epsilon1.5)$サンプル複雑性を実現する方法を示す。 私たちが知る限り、これは非精度な定常点勾配最適化のために$O(epsilon1.5)$サンプル複雑性を持つ最初のヘッセン/ヤコビアン自由法である。
  論文  参考訳（メタデータ） (2023-12-06T16:34:58Z)
• 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)
• 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)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
  論文  参考訳（メタデータ） (2022-01-19T05:56:19Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)

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

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