論文の概要: An Exponentially Converging Particle Method for the Mixed Nash
Equilibrium of Continuous Games
- arxiv url: http://arxiv.org/abs/2211.01280v3
- Date: Thu, 13 Apr 2023 11:56:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 20:22:44.594141
- Title: An Exponentially Converging Particle Method for the Mixed Nash
Equilibrium of Continuous Games
- Title（参考訳）: 連続競技の混合ナッシュ平衡に対する指数収束粒子法
- Authors: Guillaume Wang and L\'ena\"ic Chizat
- Abstract要約: 我々は,2プレイヤーゼロサムゲームの混合ナッシュ平衡と,純戦略の連続的なセットと,ペイオフ関数への一次アクセスとの問題を考察する。
この問題は例えば、分散ロバスト学習のようなゲームにインスパイアされた機械学習アプリケーションで発生する。
本稿では,この問題に対する局所収束性を保証する粒子法の導入と解析を行う。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of computing mixed Nash equilibria of two-player
zero-sum games with continuous sets of pure strategies and with first-order
access to the payoff function. This problem arises for example in
game-theory-inspired machine learning applications, such as
distributionally-robust learning. In those applications, the strategy sets are
high-dimensional and thus methods based on discretisation cannot tractably
return high-accuracy solutions.
In this paper, we introduce and analyze a particle-based method that enjoys
guaranteed local convergence for this problem. This method consists in
parametrizing the mixed strategies as atomic measures and applying proximal
point updates to both the atoms' weights and positions. It can be interpreted
as a time-implicit discretization of the "interacting" Wasserstein-Fisher-Rao
gradient flow.
We prove that, under non-degeneracy assumptions, this method converges at an
exponential rate to the exact mixed Nash equilibrium from any initialization
satisfying a natural notion of closeness to optimality. We illustrate our
results with numerical experiments and discuss applications to max-margin and
distributionally-robust classification using two-layer neural networks, where
our method has a natural interpretation as a simultaneous training of the
network's weights and of the adversarial distribution.
- Abstract（参考訳）: 純粋戦略の連続的な集合とペイオフ関数への一階アクセスを伴う2人のプレイヤーゼロサムゲームの混合ナッシュ均衡の計算の問題を考える。
この問題は例えば、分散ロバスト学習のようなゲーム理論にインスパイアされた機械学習アプリケーションで発生する。
これらの応用では、戦略集合は高次元であり、離散化に基づく手法は高い精度の解を抽出できない。
本稿では,この問題に対して局所収束を保証できる粒子ベースの手法を提案し,解析する。
この方法は、混合戦略を原子測度としてパラメータ化し、原子の重みと位置の両方に近点更新を適用する。
これは「相互作用する」ワッサーシュタイン-フィッシャー-ラオ勾配流の時間単純離散化と解釈できる。
非退化仮定の下では、この方法は指数速度で、任意の初期化から最適性への自然な近さの概念を満たす正確な混合ナッシュ平衡に収束する。
本手法は,ネットワークの重みと逆分布の同時学習として自然な解釈を持つ2層ニューラルネットワークを用いて,数値実験を行い,max-marginおよびdistributionally-robust分類への応用について考察する。
関連論文リスト
- A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳（メタデータ） (2024-05-24T21:09:19Z) - Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
異種データを用いた因果推論のための協調的逆確率スコア推定器を提案する。
異質性の増加に伴うメタアナリシスに基づく手法に対して,本手法は有意な改善を示した。
論文 参考訳（メタデータ） (2024-04-24T09:04:36Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Sampling with Mollified Interaction Energy Descent [57.00583139477843]
モーフィファイド相互作用エネルギー降下(MIED)と呼ばれる新しい最適化に基づくサンプリング手法を提案する。
MIEDは、モル化相互作用エネルギー(MIE)と呼ばれる確率測度に関する新しいクラスのエネルギーを最小化する
我々は,制約のないサンプリング問題に対して,我々のアルゴリズムがSVGDのような既存の粒子ベースアルゴリズムと同等に動作することを示す。
論文 参考訳（メタデータ） (2022-10-24T16:54:18Z) - A note on large deviations for interacting particle dynamics for finding
mixed equilibria in zero-sum games [0.0]
連続ミニマックスゲームにおける平衡点の発見は、機械学習において重要な問題となっている。
最近の発展は純平衡から混合平衡点に焦点を移している。
本研究では,粒子の数が無限に増加するにつれて,粒子系の経験的測定の順序が大きな偏差原理を満たすことを示す。
論文 参考訳（メタデータ） (2022-06-30T10:29:21Z) - Conjugate Gradient Method for Generative Adversarial Networks [0.0]
深層ニューラルネットワークモデルの密度関数と密度関数のJensen-Shannon分散を計算することは不可能である。
GAN(Generative Adversarial Network)は、この問題をジェネレータと識別器という2つのモデルで識別する問題として定式化することができる。
本稿では,GANの局所的なナッシュ平衡問題の解法として共役勾配法を提案する。
論文 参考訳（メタデータ） (2022-03-28T04:44:45Z) - A blob method method for inhomogeneous diffusion with applications to
multi-agent control and sampling [0.6562256987706128]
重み付き多孔質媒質方程式(WPME)に対する決定論的粒子法を開発し,その収束性を時間間隔で証明する。
提案手法は,マルチエージェントカバレッジアルゴリズムや確率測定のサンプリングに自然に応用できる。
論文 参考訳（メタデータ） (2022-02-25T19:49:05Z) - Provably convergent quasistatic dynamics for mean-field two-player
zero-sum games [10.39511271647025]
我々は、ある確率分布がワッセルシュタイン勾配の流れに従うような準静的ワッセルシュタイン勾配流れのダイナミクスを考察し、他方の確率分布は常に平衡状態にある。
確率分布の連続力学に着想を得て、内外反復を伴う擬静的なランゲヴィン勾配降下法を導出する。
論文 参考訳（メタデータ） (2022-02-15T20:19:42Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。