論文の概要: Iterative Minimax Games with Coupled Linear Constraints
- arxiv url: http://arxiv.org/abs/2212.04672v5
- Date: Tue, 24 Jun 2025 00:47:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-25 19:48:23.173502
- Title: Iterative Minimax Games with Coupled Linear Constraints
- Title（参考訳）: 線形制約を結合した反復ミニマックスゲーム
- Authors: Huiling Zhang, Zi Xu, Yu-Hong Dai,
- Abstract要約: 非マックスミニゲームを扱う限界は、機械学習コミュニティで大きな勢いを増している。
批判的批判的敵戦略に対処するこの種のゲームの最初の分析を行う。
-2 であることを示す。
- 参考スコア（独自算出の注目度）: 3.4683309709605328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The study of nonconvex minimax games has gained significant momentum in machine learning and decision science communities due to their fundamental connections to adversarial training scenarios. This work develops a primal-dual alternating proximal gradient (PDAPG) algorithm framework for resolving iterative minimax games featuring nonsmooth nonconvex objectives subject to coupled linear constraints. We establish rigorous convergence guarantees for both nonconvex-strongly concave and nonconvex-concave game configurations, demonstrating that PDAPG achieves an $\varepsilon$-stationary solution within $\mathcal{O}\left( \varepsilon ^{-2} \right)$ iterations for strongly concave settings and $\mathcal{O}\left( \varepsilon ^{-4} \right)$ iterations for concave scenarios. Our analysis provides the first known iteration complexity bounds for this class of constrained minimax games, particularly addressing the critical challenge of coupled linear constraints that induce inherent interdependencies among strategy variables. The proposed game-theoretic framework advances existing solution methodologies by simultaneously handling nonsmooth components and coordinated constraint structures through alternating primal-dual updates.
- Abstract（参考訳）: 非凸ミニマックスゲームの研究は、敵の訓練シナリオに基本的な関係があるため、機械学習と意思決定科学のコミュニティで大きな勢いを増している。
本研究は,非滑らかな非凸目的を持つ反復ミニマックスゲームを線形制約に結合して解くための,原始二重交互近位勾配(PDAPG)アルゴリズムフレームワークを開発する。
PDAPGが$\mathcal{O}\left( \varepsilon ^{-2} \right)$ iterations for strong concave settings and $\mathcal{O}\left( \varepsilon ^{-4} \right)$ iterations for concave scenarios.
我々の分析は、この種の制約付きミニマックスゲームに対する最初の既知の反復複雑性境界を提供し、特に戦略変数間の固有の相互依存性を誘導する結合線形制約の臨界問題に対処する。
提案したゲーム理論フレームワークは,非滑らかなコンポーネントと調整された制約構造を同時に扱うことで,原始的2次更新を交互に行うことによって,既存の解法を進化させる。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文 参考訳（メタデータ） (2024-01-26T11:22:13Z) - An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems [0.4910937238451484]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(FORMDA)を高速化する。
有界アルゴリズムの最大の複雑さは、客観性関数の停止下での非可逆ミニマックス問題の解法である。
論文 参考訳（メタデータ） (2023-10-24T01:45:11Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - 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) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for
Nonconvex-Concave Min-Max Problems [33.83671897619922]
非con-max問題は、このロバストな問題を解決するために、ポイントワイズな非函数の集合を最小化するなど、多くのアプリケーションで発生する。
A.A.アルゴリズムは、有限個の非函数の集合に対して$(/A-O-)の$(/A-O-)を達成できる。
論文 参考訳（メタデータ） (2020-10-29T17:13:46Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳（メタデータ） (2020-06-03T04:00:52Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。