論文の概要: Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

• arxiv url: http://arxiv.org/abs/2101.05248v1
• Date: Wed, 13 Jan 2021 18:13:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-30 10:36:54.137380
• Title: Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
• Title（参考訳）: グラディエントDescent Ascentによる隠れ構造による最小最適化の解法
• Authors: Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras
• Abstract要約: 非コンケーブゼロサムゲームクラスは、ゼロサムゲームを隠す機能を持つ。 我々は「隠れた」凸凹ゲームのフォン・ノイマン平衡への収束を証明する。 我々の保証は非ローカルであり、これは我々が知る限り、非コンケーブゲームにおける第一種の結果である。
• 参考スコア（独自算出の注目度）: 40.99558326586079
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many recent AI architectures are inspired by zero-sum games, however, the behavior of their dynamics is still not well understood. Inspired by this, we study standard gradient descent ascent (GDA) dynamics in a specific class of non-convex non-concave zero-sum games, that we call hidden zero-sum games. In this class, players control the inputs of smooth but possibly non-linear functions whose outputs are being applied as inputs to a convex-concave game. Unlike general zero-sum games, these games have a well-defined notion of solution; outcomes that implement the von-Neumann equilibrium of the "hidden" convex-concave game. We prove that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to the von-Neumann solution. If the game lacks strict convexity properties, GDA may fail to converge to any equilibrium, however, by applying standard regularization techniques we can prove convergence to a von-Neumann solution of a slightly perturbed zero-sum game. Our convergence guarantees are non-local, which as far as we know is a first-of-its-kind type of result in non-convex non-concave games. Finally, we discuss connections of our framework with generative adversarial networks.
• Abstract（参考訳）: 最近のaiアーキテクチャの多くはゼロサムゲームにインスパイアされているが、ダイナミクスの振る舞いはまだよく分かっていない。 これに触発されて、非凸なゼロサムゲームの特定のクラスにおいて、隠れゼロサムゲームと呼ばれる標準勾配降下(GDA)ダイナミクスを研究する。 このクラスでは、プレイヤーは凸凹ゲームへの入力として出力が適用される滑らかだが、おそらく非線形関数の入力を制御する。 一般的なゼロサムゲームとは異なり、これらのゲームは解の概念をよく定義しており、"隠れた"凸凸凸ゲームにおけるフォン・ノイマン均衡を実装する結果である。 隠れたゲームが厳密な凸凸であれば、バニラ GDA は局所ナッシュに限らず、通常フォン・ノイマン解に収束する。 ゲームに厳密な凸性がなければ、GDAは任意の平衡に収束しないかもしれないが、標準的な正規化手法を適用することで、わずかに摂動したゼロサムゲームのフォン・ノイマン解への収束を証明できる。 我々の収束保証は非局所的であり、これは我々が知る限り、非凸な非凸ゲームにおける第一種の結果である。 最後に,当社のフレームワークとジェネレイティブ・アドバーサリー・ネットワークとの関連について論じる。

関連論文リスト

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games [6.129776019898013]
  コンケーブネットワークゼロサムゲーム(NZSG)におけるナッシュ平衡の計算について検討する。 この一般化において,凸凹型2プレーヤゼロサムゲームの様々なゲーム理論的性質が保存されていることを示す。
  論文  参考訳（メタデータ） (2020-07-10T16:56:56Z)
• On the Impossibility of Global Convergence in Multi-Loss Optimization [10.081768261298098]
  所望の収束特性が任意のアルゴリズムに対して同時に保持できないことを証明する。 我々の結果は、それぞれのアルゴリズムよりも、満足のいく結果のないゲームの存在と関係がある。 ML実践者にとって、高次元ゲームにそのような振る舞いが生じるかどうかは、未解決の問題である。
  論文  参考訳（メタデータ） (2020-05-26T12:11:18Z)
• Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method [10.819408603463426]
  ミニマックスサドル点降下器は、機械の傾きと信号処理において幅広い用途に現れる。 単純な多段階LA-Ascentアルゴリズムは文献上の既存アルゴリズムよりも強いことを示す。
  論文  参考訳（メタデータ） (2020-03-18T08:38:34Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)
• A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets [29.606063890097275]
  多目的最適化の特殊な例であるAdrial Trainingは、ますます普及している機械学習技術である。 GANベースの生成再生技術は、Goのようなポーカーゲームに応用されている。
  論文  参考訳（メタデータ） (2020-02-14T00:17:24Z)

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

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