Provably convergent quasistatic dynamics for mean-field two-player zero-sum games

• URL: http://arxiv.org/abs/2202.10947v1
• Date: Tue, 15 Feb 2022 20:19:42 GMT
• Title: Provably convergent quasistatic dynamics for mean-field two-player zero-sum games
• Authors: Chao Ma, Lexing Ying
• Abstract summary: We consider a quasistatic Wasserstein gradient flow dynamics in which one probability distribution follows the Wasserstein gradient flow, while the other one is always at the equilibrium. Inspired by the continuous dynamics of probability distributions, we derive a quasistatic Langevin gradient descent method with inner-outer iterations.
• Score: 10.39511271647025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of finding mixed Nash equilibrium for mean-field two-player zero-sum games. Solving this problem requires optimizing over two probability distributions. We consider a quasistatic Wasserstein gradient flow dynamics in which one probability distribution follows the Wasserstein gradient flow, while the other one is always at the equilibrium. Theoretical analysis are conducted on this dynamics, showing its convergence to the mixed Nash equilibrium under mild conditions. Inspired by the continuous dynamics of probability distributions, we derive a quasistatic Langevin gradient descent method with inner-outer iterations, and test the method on different problems, including training mixture of GANs.

Related papers

• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [62.51015395213579]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games [0.0]
  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-inspired machine learning applications, such as distributionally-robust learning. We introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem.
  arXiv  Detail & Related papers  (2022-11-02T17:03:40Z)
• Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games [8.780797886160402]
  We study Nash equilibria learning of a general-sum game with an unknown transition probability density function. For the case with exact pseudo gradients, we design a two-loop algorithm by the equivalence of Nash equilibrium and variational inequality problems.
  arXiv  Detail & Related papers  (2022-10-14T09:09:56Z)
• Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
  A deep equilibrium model (DEQ) is implicitly defined through an equilibrium point of an infinite-depth weight-tied model with an input-injection. Instead of infinite computations, it solves an equilibrium point directly with root-finding and computes gradients with implicit differentiation. We propose a novel probabilistic framework to overcome the technical difficulty in the non-asymptotic analysis of infinite-depth weight-tied models.
  arXiv  Detail & Related papers  (2022-05-27T08:00:13Z)
• Simultaneous Transport Evolution for Minimax Equilibria on Measures [48.82838283786807]
  Min-max optimization problems arise in several key machine learning setups, including adversarial learning and generative modeling. In this work we focus instead in finding mixed equilibria, and consider the associated lifted problem in the space of probability measures. By adding entropic regularization, our main result establishes global convergence towards the global equilibrium.
  arXiv  Detail & Related papers  (2022-02-14T02:23:16Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• A mean-field analysis of two-player zero-sum games [46.8148496944294]
  Mixed Nash equilibria exist in greater generality and may be found using mirror descent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
  arXiv  Detail & Related papers  (2020-02-14T22:46:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.