論文の概要: Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria
of Continuous Games: A Mean-Field Perspective
- arxiv url: http://arxiv.org/abs/2212.08791v1
- Date: Sat, 17 Dec 2022 03:44:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 16:04:21.578492
- Title: Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria
of Continuous Games: A Mean-Field Perspective
- Title(参考訳): 2スケールのグラディエントDescent Ascent Dynamicsが連続ゲームにおける混合ナッシュ平衡を発見:平均的な視点
- Authors: Yulong Lu
- Abstract要約: 2プレイヤーゼロ和連続ゲームにおける混合ナッシュ平衡(MNE)の発見は、機械学習において重要かつ困難な問題である。
まず, エントロピー正規化対象のMNEを求めるために, 2次元平均場GDAダイナミクスの収束について検討する。
- 参考スコア(独自算出の注目度): 5.025654873456756
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous
game is an important and challenging problem in machine learning. A canonical
algorithm to finding the MNE is the noisy gradient descent ascent method which
in the infinite particle limit gives rise to the {\em Mean-Field Gradient
Descent Ascent} (GDA) dynamics on the space of probability measures. In this
paper, we first study the convergence of a two-scale Mean-Field GDA dynamics
for finding the MNE of the entropy-regularized objective. More precisely we
show that for any fixed positive temperature (or regularization parameter), the
two-scale Mean-Field GDA with a {\em finite} scale ratio converges to
exponentially to the unique MNE without assuming the convexity or concavity of
the interaction potential. The key ingredient of our proof lies in the
construction of new Lyapunov functions that dissipate exponentially along the
Mean-Field GDA. We further study the simulated annealing of the Mean-Field GDA
dynamics. We show that with a temperature schedule that decays logarithmically
in time the annealed Mean-Field GDA converges to the MNE of the original
unregularized objective function.
- Abstract(参考訳): 2プレイヤーゼロ和連続ゲームの混合ナッシュ平衡(MNE)を見つけることは、機械学習において重要かつ困難な問題である。
mne を見つけるための標準的なアルゴリズムは、無限の粒子極限において確率測度の空間上の「em平均場勾配上昇」(gda)ダイナミクスをもたらすノイズ勾配降下上昇法である。
本稿では, エントロピー正規化対象のMNEを求めるために, 2次元平均場GDAダイナミクスの収束性について検討する。
より正確には、任意の正の温度(あるいは正則化パラメータ)に対して、相互作用ポテンシャルの凸性や凸性を仮定することなく、2スケールの平均場 GDA が MNE に指数関数的に収束することを示す。
我々の証明の重要な要素は、平均場GDAに沿って指数関数的に散逸する新しいリャプノフ函数の構築である。
さらに平均場gdaダイナミクスのシミュレーションアニーリングについても検討した。
熱処理された平均場GDAは、対数的に減衰する温度スケジュールで元の非正規化対象関数のMNEに収束することを示す。
関連論文リスト
- Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳(メタデータ) (2023-12-02T13:01:29Z) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。
近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。
有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
論文 参考訳(メタデータ) (2023-06-12T16:28:11Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - Learning Discretized Neural Networks under Ricci Flow [51.36292559262042]
低精度重みとアクティベーションからなる離散ニューラルネットワーク(DNN)について検討する。
DNNは、訓練中に微分不可能な離散関数のために無限あるいはゼロの勾配に悩まされる。
論文 参考訳(メタデータ) (2023-02-07T10:51:53Z) - Birth-death dynamics for sampling: Global convergence, approximations
and their asymptotics [9.011881058913184]
純粋死動力学に基づく実用的な数値システムを構築した。
核化されたダイナミクスは有限時間間隔で収束し、純粋な勾配死ダイナミクスは0に縮まる。
最後に、Gibs測度に対する核化されたダイナミクスの状態の収束に関する長時間の結果を証明する。
論文 参考訳(メタデータ) (2022-11-01T13:30:26Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳(メタデータ) (2022-10-13T03:55:04Z) - Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
平均場ランゲヴィン力学の収束速度解析について述べる。
ダイナミックスに付随する$p_q$により、凸最適化において古典的な結果と平行な収束理論を開発できる。
論文 参考訳(メタデータ) (2022-01-25T17:13:56Z) - An Optimal Multistage Stochastic Gradient Method for Minimax Problems [8.615625517708324]
滑らかかつ強凸な凹凸配置におけるミニマックス最適化問題について検討する。
まず, 定常ステップサイズでグラディエントDescent Ascent (GDA) 法を解析した。
本稿では,学習速度の減衰スケジュールを多段階に設定した多段階型GDAを提案する。
論文 参考訳(メタデータ) (2020-02-13T18:01:18Z) - Function approximation by neural nets in the mean-field regime: Entropic regularization and controlled McKean-Vlasov dynamics [7.1822457112352955]
我々は「ほぼガウス的」なランダム重みを持つ2層ニューラルネットワークによる関数近似の問題を考察する。
この問題は、ウェイト上の確率測度を超える経路空間で機能する自由エネルギーの大域的最小化として表現できることを示す。
論文 参考訳(メタデータ) (2020-02-05T20:50:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。