A mean-field analysis of two-player zero-sum games

• URL: http://arxiv.org/abs/2002.06277v4
• Date: Thu, 6 May 2021 14:02:00 GMT
• Title: A mean-field analysis of two-player zero-sum games
• Authors: Carles Domingo-Enrich, Samy Jelassi, Arthur Mensch, Grant Rotskoff, Joan Bruna
• Abstract summary: 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.
• Score: 46.8148496944294
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures 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)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• 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)
• A note on large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games [0.0]
  Finding equilibria points in continuous minimax games has become a key problem within machine learning. Recent developments have shifted from pure equilibria to focusing on mixed equilibria points. We show that the sequence of empirical measures of the particle system satisfies a large deviation principle as the number of particles grows to infinity.
  arXiv  Detail & Related papers  (2022-06-30T10:29:21Z)
• 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)
• Provably convergent quasistatic dynamics for mean-field two-player zero-sum games [10.39511271647025]
  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.
  arXiv  Detail & Related papers  (2022-02-15T20:19:42Z)
• 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)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)
• Density dynamics in the mass-imbalanced Hubbard chain [0.0]
  We consider two mutually interacting fermionic particle species on a one-dimensional lattice. We study how the mass ratio $eta$ between the two species affects the dynamics of the particles.
  arXiv  Detail & Related papers  (2020-04-28T15:38:02Z)

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.