論文の概要: Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

• arxiv url: http://arxiv.org/abs/2610.07814v1
• Date: Tue, 06 Oct 2026 06:08:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.837534
• Title: Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games
• Title（参考訳）: 非凸PLMin-Maxゲームにおける確率的グラディエントDescent Ascentの最適値
• Abstract要約: 勾配降下(SGDA)は、非var min-maxゲームにおけるタイムスケール比とステップサイズによって変化する。 NC-PLゲームにおいて,SGDAは静止点の発見に失敗する可能性があることを示す。
• 参考スコア（独自算出の注目度）: 0.7106986689736826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For $\ell$-smooth games with an inner $μ$-PL inequality, we prove a complexity lower bound $Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})$, where $κ=\ell/μ$ is the condition number, $σ^2$ is the gradient variance, and $\varepsilon$ measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as $o(κ^2)$. Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.
• Abstract（参考訳）: 非凸min-maxゲームにおいて、その時間スケール比とステップサイズを調整することによって、確率勾配勾配上昇(SGDA)はどこまで進むことができるのか? 非凸PL(NC-PL)ゲームにおいて、固定時間スケール比と非増加ステップサイズの2時間スケールSGDAの最初の厳密な複雑性を確立することで、この問題に答える。 内部の$μ$-PL不等式を持つ$\ell$-smoothゲームの場合、複雑性の低い境界である$Ω(κ^2\ell\varepsilon^{-2}+κ^4\ellσ^2\varepsilon^{-4})$, ここで、$κ=\ell/μ$は条件数、$σ^2$は勾配分散、$\varepsilon$は外側勾配ノルムを測定する。 これは既存の SGDA 上界と一致し、Smoothed-AGDA (Yang et al , 22') との複雑性分離を確立する。 さらに、SGDAは、その時間スケール比が$o(κ^2)$ほど小さい場合、静止点を見つけることができないことを示す。 我々の否定的な結果はNC-PLゲームにおけるSGDAの基本的な制限を強調し、代替手法の開発を正当化するものである。

関連論文リスト

• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  我々は,SAPD+の決定論的複雑性における線形条件数依存性が,非連続性最適化に必要であることを証明した。
  論文  参考訳（メタデータ） (2026-09-25T06:34:04Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。 我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。 ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
  論文  参考訳（メタデータ） (2025-10-06T00:33:20Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• 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)
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation [11.091975655053547]
  有限時間スケールの分離パラメータ $tau$ は、非プレイヤ、非コンケーブゼロサムゲームにおいて勾配降下度に比例することを示す。 タイムスケールコンピューティングがパフォーマンスに与える影響を実証的に示す。
  論文  参考訳（メタデータ） (2020-09-30T17:51:28Z)

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

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