論文の概要: Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2609.17973v1
• Date: Wed, 16 Sep 2026 01:00:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.584622
• Title: Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
• Title（参考訳）: 単一ループでの多重ループ複雑性のマッチング:非凸における最適最適化定常度とベスト知識ゲーム定常度--コンケーブ最小値最適化
• Abstract要約: 我々は,スムーズな非コンケーブ最小値最適化のための新しいアルゴリズムフレームワークを提案する。 結果として生じる減衰外段法は、漸進的更新、二重運動量、移動中心を組み合わせたものである。 最適化とゲームステーションの両条件で,本手法は最もよく知られた複雑性を実現する。
• 参考スコア（独自算出の注目度）: 5.666898899412153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new single-loop algorithmic framework for smooth nonconvex--concave minimax optimization. The resulting projected damped extragradient method combines projected extragradient updates, dual momentum, and a moving proximal center. Under both the optimization-stationarity and game-stationarity criteria, our method achieves the best-known complexity among single-loop first-order methods. For optimization stationarity, our method achieves a gradient complexity of $O(L^2D_Y\barΔ_0\varepsilon^{-3})$, where $L$ is the gradient Lipschitz constant, $D_Y$ bounds the diameter of the dual feasible set, and $\barΔ_0$ is an initialization quantity involving the value-function gap and the initial gradients. Moreover, by incorporating a fixed-center warm-up phase, the complexity can be improved to $O(L^2D_YΔ_φ\varepsilon^{-3})$, up to an additive lower-order cost, where $Δ_φ:=φ(x_0)-\inf_xφ(x)$. We further establish a lower bound of $Ω(L^2D_YΔ_φ\varepsilon^{-3})$ for optimization stationarity over projected zero-respecting first-order methods. This lower bound proves that the warm-started version of our algorithm is optimal up to a constant factor for optimization stationarity within this oracle class. For game stationarity, our method achieves $\mathcal{O}\!(L^{3/2}D_Y^{1/2}Δ_φ\varepsilon^{-5/2})$ gradient complexity. This matches the best-known complexity of multi-loop first-order methods, thereby establishing the same complexity with a single-loop algorithmic structure. Under dual strong concavity, the proposed framework achieves $O\!(\sqrtκ\,LΔ_φ\varepsilon^{-2})$ leading complexity for both stationarity criteria, where $κ=L/μ$ is the dual condition number, up to an additive initialization cost. The $\varepsilon^{-2}$ accuracy dependence is optimal under fixed regularity and initialization bounds.
• Abstract（参考訳）: 我々は、スムーズな非凸-凹最小値最適化のための新しい単一ループアルゴリズムフレームワークを導入する。 結果として生じる減衰外段法は、予測外段法更新、双対運動量、移動近位中心を組み合わせたものである。 最適化定常度基準とゲーム定常度基準の両方の下で,本手法は単一ループ1次法において最もよく知られた複雑性を実現する。 ここでは、L$は勾配リプシッツ定数、$D_Y$は双対実現可能な集合の直径を束縛し、$\barΔ_0$は値関数ギャップと初期勾配を含む初期化量である。 さらに、固定中心ウォームアップフェーズを組み込むことで、複雑さを$O(L^2D_YΔ_φ\varepsilon^{-3})$、加法的な低次コストまで改善することができる。 さらに、投影されたゼロ反射一階法に対する最適化定常性に対して、$Ω(L^2D_YΔ_φ\varepsilon^{-3})の低い境界を確立する。 この下界は、我々のアルゴリズムのウォームスタートバージョンが、このオラクルクラス内の定常性を最適化するための定数係数まで最適であることを証明している。 ゲーム定常性では、このメソッドは$\mathcal{O}\! (L^{3/2}D_Y^{1/2}Δ_φ\varepsilon^{-5/2})=勾配複雑性。 これはマルチループ一階法でよく知られた複雑さと一致し、単一のループアルゴリズム構造と同じ複雑さを確立する。 二重強凸下では、提案されたフレームワークは$O\! (\sqrtκ\,LΔ_φ\varepsilon^{-2})$ $κ=L/μ$ は双対条件数であり、加法初期化コストに達する。 $\varepsilon^{-2}$精度依存は、固定正則性と初期化境界の下で最適である。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
  2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。 我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
  論文  参考訳（メタデータ） (2022-07-12T17:21:45Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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