論文の概要: Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2609.21747v1
• Date: Fri, 18 Sep 2026 13:24:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 18:40:17.110704
• Title: Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization
• Title（参考訳）: 確率的非凸---(Strongly) Concave Minimax Optimizationのための単一ループ確率射影減衰法
• Abstract要約: 我々は,最小値最適化のための単一ループ投影型減衰外勾配法を開発した。 その結果,各定常基準と問題クラスについて,最もよく知られたSFO 1次法が得られた。
• 参考スコア（独自算出の注目度）: 3.5121945389033904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop single-loop stochastic projected damped extragradient methods for stochastic nonconvex--(strongly) concave minimax optimization, with complexity guarantees for both game stationarity (GS) and optimization stationarity (OS). Our approach combines a stochastic projected damped extragradient (SPDE) method with a recursive variance-reduced variant, VR-SPDE, both of which retain a single-loop structure. Under an unbiased stochastic gradient oracle with uniformly bounded variance, SPDE finds an $\varepsilon$-game-stationary point with stochastic first-order oracle (SFO) complexities of $O(κ\varepsilon^{-4})$ and $O(\varepsilon^{-5})$ in the nonconvex--strongly concave and nonconvex--concave settings, respectively, where $κ=L/μ$. Under an additional mean-square Lipschitz condition on the stochastic gradients, VR-SPDE improves these GS complexities to $O(κ^{3/2}\varepsilon^{-3})$ and $O(\varepsilon^{-9/2})$, respectively. For an $\varepsilon$-optimization-stationary point, SPDE achieves SFO complexities of $O(κ\varepsilon^{-4})$ and $O(\varepsilon^{-6})$, while VR-SPDE achieves $O(κ^{3/2}\varepsilon^{-3})$ and $O(\varepsilon^{-6})$, in the two settings, respectively. These OS guarantees match the best-known bounds achieved by multi-loop methods while preserving a single-loop implementation. To the best of our knowledge, our results provide the best-known SFO complexity guarantees among single-loop stochastic first-order methods for the respective stationarity criteria and problem classes.
• Abstract（参考訳）: 我々は,ゲーム定常性 (GS) と最適化定常性 (OS) の両面に複雑性を保証した,確率的非凸-(強) 凹極小最適化のための単一ループ確率的減衰減衰法を開発した。 提案手法は,PSDE法と再帰的分散還元型VR-SPDE法を組み合わせたもので,いずれも単一ループ構造を保っている。 一様有界な確率勾配オラクルの下で、SPDE は、$O(κ\varepsilon^{-4})$ と $O(\varepsilon^{-5})$ の確率的一階オラクル(SFO)複素数を持つ$\varepsilon$-game-stationary point を見つける。 確率勾配上の平均二乗リプシッツ条件により、VR-SPDE はこれらの GS の複雑さを $O(κ^{3/2}\varepsilon^{-3})$ と $O(\varepsilon^{-9/2})$ に改善する。 SPDEは、$O(κ\varepsilon^{-4})$と$O(\varepsilon^{-6})$、VR-SPDEは$O(κ^{3/2}\varepsilon^{-3})$と$O(\varepsilon^{-6})$である。 これらのOSは、シングルループの実装を保ちながら、マルチループメソッドによって達成される最もよく知られた境界と一致することを保証している。 我々の知る限りでは、各定常基準と問題クラスに対する単一ループ確率的一階法のうち、最もよく知られたSFO複雑性保証を提供する。

関連論文リスト

• Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization [5.666898899412153]
  我々は,スムーズな非コンケーブ最小値最適化のための新しいアルゴリズムフレームワークを提案する。 結果として生じる減衰外段法は、漸進的更新、二重運動量、移動中心を組み合わせたものである。 最適化とゲームステーションの両条件で,本手法は最もよく知られた複雑性を実現する。
  論文  参考訳（メタデータ） (2026-09-16T01:00:23Z)
• 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)
• Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
  我々は,Blum-Gladyshev(mathsfBG$-0)ノイズモデルの下での非線形最適化について検討した。 モーメント付き正規化勾配降下は、勾配毎のパラメータを1つだけ使い、複雑さが$O(varepsilon-6)$で$mathsfBG$-0ノイズの下に収束することを示す。
  論文  参考訳（メタデータ） (2026-05-14T18:27:49Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [46.46038357597395]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• 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)

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

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