論文の概要: 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次更新を交互に行うことによって,既存の解法を進化させる。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees [14.301500851291989]
  合成ミニマックス問題は、機械学習において存在するが、このクラスの問題の収束に関してのみ確立されている。 本稿では,ミニマックス損失を合成構造で最適化するミニマックス問題の形式的定義を提案する。
  論文  参考訳（メタデータ） (2024-08-22T16:00:31Z)
• 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)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis [23.80683445944524]
  PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。 PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
  論文  参考訳（メタデータ） (2022-09-22T07:12:48Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。 また,非コンケーブミニマックス問題に対処できることを示す。
  論文  参考訳（メタデータ） (2021-08-01T15:23:49Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• 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)

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

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