論文の概要: SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2608.23211v1
• Date: Mon, 24 Aug 2026 13:00:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-25 13:29:44.092982
• Title: SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization
• Title（参考訳）: SGHA:非凸-ストロングリ-凸二値最適化のための単一ループ完全一階アルゴリズム
• Abstract要約: 我々は、Stoc-SGHAが$Oleft(bar_y-4)$のオラクル複雑性を、任意の$in(1)$に対して少なくとも$$$と、追加の仮定の下で$Oleft(bar_y-4)$の複雑さを達成することを示す。 決定論的設定では、Stoc-SGHAは$Oleft(bar_y)$のオラクル複雑性を少なくとも$in(1)$に対して$$$$$で達成し、$Oleft(bar_y)$以下の複雑さを達成している。
• 参考スコア（独自算出の注目度）: 9.118433290504035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study the oracle complexity of finding an $ε$-stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization using only first-order oracles. Existing methods achieving the best-known complexity guarantees typically rely on double-loop, penalty-based procedures. We propose a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint. Specifically, we construct a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain, and then apply Smoothed Gradient Descent Ascent [Zhang et al., 2020], with Hessian-vector products approximated via finite differences of gradients. We refer to the resulting deterministic and stochastic algorithms as SGHA and Stoc-SGHA, respectively. In the deterministic setting, SGHA achieves an oracle complexity of $O(\barκ_y^{5}ε^{-2})$, where $\barκ_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$ with probability at least $1-ρ$ for any $ρ\in(0,1)$, and an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}\right)$ in expectation under an additional bounded-iterate assumption. Moreover, under an additional stochastic smoothness assumption imposed only on the lower-level objective, the stochastic oracle complexity of Stoc-SGHA improves to $O\left(\barκ_y^{11}ε^{-4}ρ^{-2}\right)$ with high probability and $O\left(\barκ_y^{11}ε^{-4}\right)$ in expectation, matching the $ε$-dependence of the lower bounds.
• Abstract（参考訳）: 本研究では,一階オラクルのみを用いて,非凸強凸(NC-SC)二値最適化のためのε$-定常点を求める場合のオラクルの複雑さについて検討する。 最もよく知られた複雑性を保証する既存の方法は、典型的には二重ループ、ペナルティベースの手順に依存している。 制約として低レベルの定常性を課す制約付き再構成に基づく新しい単一ループアルゴリズムを提案する。 具体的には、二次正則化を導入し、双対変数を有界領域に制限することで正規化ラグランジアンを構築し、その後、勾配の有限差分によりヘッセンベクトル積を近似したスムースなグラディエントDescent Ascent [Zhang et al , 2020] を適用する。 決定論的アルゴリズムと確率論的アルゴリズムをそれぞれ SGHA と Stoc-SGHA と呼ぶ。 決定論的設定では、SGHAは$O(\barκ_y^{5}ε^{-2})$のオラクル複雑性を達成し、$\barκ_y$は関連する条件数を表す。 確率的設定では、Stoc-SGHAは、任意の$ρ\in(0,1)$に対して少なくとも1-ρ$の確率で$O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$のオラクル複雑性を達成する。 さらに、Stoc-SGHAの確率的オラクル複雑性は、低次の目的にのみ課せられる確率的滑らか性仮定の下で、高い確率で$O\left(\barκ_y^{11}ε^{-4}ρ^{-2}\right)$と$O\left(\barκ_y^{11}ε^{-4}\right)$に改善される。

関連論文リスト

• Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
  コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。 弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-09-08T23:09:39Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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