論文の概要: Provable Particle-based Primal-Dual Algorithm for Mixed Nash Equilibrium

• arxiv url: http://arxiv.org/abs/2303.00970v1
• Date: Thu, 2 Mar 2023 05:08:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-03 16:00:48.260264
• Title: Provable Particle-based Primal-Dual Algorithm for Mixed Nash Equilibrium
• Title（参考訳）: 混合ナッシュ平衡の確率的粒子ベースプリマル双対アルゴリズム
• Authors: Shihong Ding, Hanze Dong, Cong Fang, Zhouchen Lin, Tong Zhang
• Abstract要約: 連続変数に対する一般の非凹極小問題を考察する。 これを解決するために、混合ナッシュ平衡を求める際の関連する問題を考察する。
• 参考スコア（独自算出の注目度）: 62.82264578555749
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the general nonconvex nonconcave minimax problem over continuous variables. A major challenge for this problem is that a saddle point may not exist. In order to resolve this difficulty, we consider the related problem of finding a Mixed Nash Equilibrium, which is a randomized strategy represented by probability distributions over the continuous variables. We propose a Particle-based Primal-Dual Algorithm (PPDA) for a weakly entropy-regularized min-max optimization procedure over the probability distributions, which employs the stochastic movements of particles to represent the updates of random strategies for the mixed Nash Equilibrium. A rigorous convergence analysis of the proposed algorithm is provided. Compared to previous works that try to update particle weights without movements, PPDA is the first implementable particle-based algorithm with non-asymptotic quantitative convergence results, running time, and sample complexity guarantees. Our framework gives new insights into the design of particle-based algorithms for continuous min-max optimization in the general nonconvex nonconcave setting.
• Abstract（参考訳）: 連続変数に対する一般の非凸非凸ミニマックス問題を考える。 この問題に対する大きな課題は、鞍点が存在しないかもしれないことである。 この問題を解決するために、連続変数上の確率分布で表されるランダム化戦略である混合ナッシュ平衡を求めるという関連する問題を考察する。 本稿では,混合ナッシュ平衡に対するランダム戦略の更新を表現するために,粒子の確率的移動を用いた確率分布上の弱エントロピー正規化min-max最適化手法のための粒子ベース原始双対アルゴリズム(ppda)を提案する。 提案アルゴリズムの厳密な収束解析を提供する。 運動のない粒子重みを更新しようとする以前の研究と比較すると、PPDAは非漸近的な定量的収束結果、実行時間、サンプルの複雑さを保証する最初の実装可能な粒子ベースアルゴリズムである。 我々のフレームワークは、一般の非凸非凹面設定における連続最小値最適化のための粒子ベースアルゴリズムの設計に関する新しい知見を提供する。

関連論文リスト

• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。 従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。 我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
  論文  参考訳（メタデータ） (2023-12-13T09:31:30Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games [0.0]
  我々は,2プレイヤーゼロサムゲームの混合ナッシュ平衡と,純戦略の連続的なセットと,ペイオフ関数への一次アクセスとの問題を考察する。 この問題は例えば、分散ロバスト学習のようなゲームにインスパイアされた機械学習アプリケーションで発生する。 本稿では,この問題に対する局所収束性を保証する粒子法の導入と解析を行う。
  論文  参考訳（メタデータ） (2022-11-02T17:03:40Z)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。 我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
  論文  参考訳（メタデータ） (2022-05-27T03:24:12Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。 この回避は、非自明な常微分方程式のノイズ離散化として研究される。
  論文  参考訳（メタデータ） (2020-12-07T19:14:49Z)

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

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