A note on large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games

• URL: http://arxiv.org/abs/2206.15177v1
• Date: Thu, 30 Jun 2022 10:29:21 GMT
• Title: A note on large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games
• Authors: Viktor Nilsson, Pierre Nyquist
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding equilibria points in continuous minimax games has become a key problem within machine learning, in part due to its connection to the training of generative adversarial networks. Because of existence and robustness issues, recent developments have shifted from pure equilibria to focusing on mixed equilibria points. In this note we consider a method proposed by Domingo-Enrich et al. for finding mixed equilibria in two-layer zero-sum games. The method is based on entropic regularisation and the two competing strategies are represented by two sets of interacting particles. 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, and how this implies convergence of the empirical measure and the associated Nikaid\^o-Isoda error, complementing existing law of large numbers results.

Related papers

• 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)
• On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce it [0.0]
  We propose iterative algorithms to solve adversarial problems in a variety of supervised learning settings interest. Our algorithms can be interpreted as suitable ascent-descent dynamics in Wasserstein spaces.
  arXiv  Detail & Related papers  (2023-01-09T20:14:30Z)
• Dilute neutron star matter from neural-network quantum states [58.720142291102135]
  Low-density neutron matter is characterized by the formation of Cooper pairs and the onset of superfluidity. We model this density regime by capitalizing on the expressivity of the hidden-nucleon neural-network quantum states combined with variational Monte Carlo and reconfiguration techniques.
  arXiv  Detail & Related papers  (2022-12-08T17:55:25Z)
• 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)
• Sudden quench of harmonically trapped mass-imbalanced fermions [0.0]
  Two-component mass-imbalanced few-fermion systems confined in a harmonic trap are studied. The role of mass imbalance and particle number imbalance on the system's evolution stability is investigated. The results may have implications for upcoming experiments on fermionic mixtures with a well-defined and small number of particles.
  arXiv  Detail & Related papers  (2022-09-13T10:33:10Z)
• Formation of robust bound states of interacting microwave photons [148.37607455646454]
  One of the hallmarks of interacting systems is the formation of multi-particle bound states. We develop a high fidelity parameterizable fSim gate that implements the periodic quantum circuit of the spin-1/2 XXZ model. By placing microwave photons in adjacent qubit sites, we study the propagation of these excitations and observe their bound nature for up to 5 photons.
  arXiv  Detail & Related papers  (2022-06-10T17:52:29Z)
• 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)
• Quantum Coherent States of Interacting Bose-Fermi Mixtures in One Dimension [68.8204255655161]
  We study two-component atomic gas mixtures in one dimension involving both bosons and fermions. We report a rich variety of coherent ground-state phases that vary with the intrinsic and relative strength of the interactions.
  arXiv  Detail & Related papers  (2021-10-26T17:52:37Z)
• 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.