論文の概要: Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games

• arxiv url: http://arxiv.org/abs/2007.05477v1
• Date: Fri, 10 Jul 2020 16:56:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-11 21:43:06.717531
• Title: Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
• Title（参考訳）: コンケーブネットワークゼロサムゲームにおける勾配法の指数収束
• Authors: Amit Kadan and Hu Fu
• Abstract要約: コンケーブネットワークゼロサムゲーム(NZSG)におけるナッシュ平衡の計算について検討する。 この一般化において,凸凹型2プレーヤゼロサムゲームの様々なゲーム理論的性質が保存されていることを示す。
• 参考スコア（独自算出の注目度）: 6.129776019898013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by Generative Adversarial Networks, we study the computation of Nash equilibrium in concave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum games first proposed with linear payoffs. Extending previous results, we show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization. We then generalize last iterate convergence results obtained previously in two-player zero-sum games. We analyze convergence rates when players update their strategies using Gradient Ascent, and its variant, Optimistic Gradient Ascent, showing last iterate convergence in three settings -- when the payoffs of players are linear, strongly concave and Lipschitz, and strongly concave and smooth. We provide experimental results that support these theoretical findings.
• Abstract（参考訳）: 本研究では,2人プレイのゼロサムゲームのマルチプレイヤー一般化であるconcave network zero-sum games (nzsgs) におけるnash均衡の計算について検討した。 この一般化では,凸凹型2プレーヤゼロサムゲームの様々なゲーム理論特性が保存されている。 次に、2つのプレイヤーゼロサムゲームで得られた最後の反復収束結果を一般化する。 選手の報酬が線形で、強い凹凸とリプシッツであり、強い凹凸と滑らかである3つの設定で、プレイヤーが戦略を更新する際の収束率と、その変種である楽観的な勾配上昇を分析し、最後に反復的な収束を示す。 これらの理論的知見を裏付ける実験結果を提供する。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Improved Convergence Guarantees for Shallow Neural Networks [91.3755431537592]
  勾配降下法により訓練された深度2ニューラルネットの収束度を世界最小とする。 我々のモデルには、二次損失関数による回帰、完全連結フィードフォワードアーキテクチャ、RelUアクティベーション、ガウスデータインスタンス、逆ラベルといった特徴がある。 彼らは、少なくとも我々のモデルでは、収束現象がNTK体制をはるかに超越していることを強く示唆している」。
  論文  参考訳（メタデータ） (2022-12-05T14:47:52Z)
• A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games [104.3339905200105]
  この研究は、ミラー降下と非ユークリッド近位勾配アルゴリズムにインスパイアされた、磁気ミラー降下と呼ばれるアルゴリズムを研究する。 我々の貢献は、2人のプレイヤーゼロサムゲームにおける平衡解法および強化学習へのアプローチとしての磁気ミラー降下の利点を実証することである。
  論文  参考訳（メタデータ） (2022-06-12T19:49:14Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Complex Momentum for Learning in Games [42.081050296353574]
  我々は、微分可能なゲームにおいて学習する運動量を伴う勾配降下を複素数値運動量を持つように一般化する。 我々は、複雑な値の運動量によってゲーム内の収束性が改善できることを実証する。 我々はまた、CIFAR-10のより良いスコアにBigGANを訓練するために使用する複素値アダム変種への実用的な一般化を示す。
  論文  参考訳（メタデータ） (2021-02-16T19:55:27Z)
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent [40.99558326586079]
  非コンケーブゼロサムゲームクラスは、ゼロサムゲームを隠す機能を持つ。 我々は「隠れた」凸凹ゲームのフォン・ノイマン平衡への収束を証明する。 我々の保証は非ローカルであり、これは我々が知る限り、非コンケーブゲームにおける第一種の結果である。
  論文  参考訳（メタデータ） (2021-01-13T18:13:49Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

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

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