論文の概要: PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium

• arxiv url: http://arxiv.org/abs/2303.00970v2
• Date: Mon, 20 Nov 2023 22:51:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-23 05:41:11.560031
• Title: PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium
• Title（参考訳）: papal:混合ナッシュ平衡のための証明可能な粒子ベース原始双対アルゴリズム
• Authors: Shihong Ding, Hanze Dong, Cong Fang, Zhouchen Lin, Tong Zhang
• Abstract要約: 2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
• 参考スコア（独自算出の注目度）: 62.51015395213579
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the non-convex non-concave objective function in two-player zero-sum continuous games. The existence of pure Nash equilibrium requires stringent conditions, posing a major challenge for this problem. To circumvent this difficulty, we examine the problem of identifying a mixed Nash equilibrium, where strategies are randomized and characterized by probability distributions over continuous domains.To this end, we propose PArticle-based Primal-dual ALgorithm (PAPAL) tailored for a weakly entropy-regularized min-max optimization over probability distributions. This algorithm employs the stochastic movements of particles to represent the updates of random strategies for the $\epsilon$-mixed Nash equilibrium. We offer a comprehensive convergence analysis of the proposed algorithm, demonstrating its effectiveness. In contrast to prior research that attempted to update particle importance without movements, PAPAL is the first implementable particle-based algorithm accompanied by non-asymptotic quantitative convergence results, running time, and sample complexity guarantees. Our framework contributes novel insights into the particle-based algorithms for continuous min-max optimization in the general non-convex non-concave setting.
• Abstract（参考訳）: 2人プレイのゼロサム連続ゲームにおける非凸非凸目的関数を考える。 純粋なナッシュ均衡の存在には厳密な条件が必要であり、この問題に対する大きな挑戦となる。 この問題を回避すべく,戦略がランダム化され,連続領域上の確率分布によって特徴づけられる混合ナッシュ均衡を同定する問題を考察し,この目的のために,確率分布上の弱エントロピー正規化min-max最適化のために調整された粒子型原始双対アルゴリズム(papal)を提案する。 このアルゴリズムは粒子の確率運動を用いて、$\epsilon$-mixed Nash平衡のランダム戦略の更新を表す。 提案アルゴリズムの包括的収束解析を行い,その有効性を示す。 運動なしで粒子の重要度を更新しようとする以前の研究とは対照的に、PAPALは非漸近的な定量的収束結果、実行時間、サンプルの複雑性保証を伴う最初の実装可能な粒子ベースのアルゴリズムである。 本フレームワークは,非凸非凸設定における連続min-max最適化のための粒子ベースのアルゴリズムに関する新たな知見を提供する。

関連論文リスト

• 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)

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

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