Simultaneous Transport Evolution for Minimax Equilibria on Measures
- URL: http://arxiv.org/abs/2202.06460v1
- Date: Mon, 14 Feb 2022 02:23:16 GMT
- Title: Simultaneous Transport Evolution for Minimax Equilibria on Measures
- Authors: Carles Domingo-Enrich, Joan Bruna
- Abstract summary: 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.
- Score: 48.82838283786807
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Min-max optimization problems arise in several key machine learning setups,
including adversarial learning and generative modeling. In their general form,
in absence of convexity/concavity assumptions, finding pure equilibria of the
underlying two-player zero-sum game is computationally hard [Daskalakis et al.,
2021]. 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 by using simultaneous gradient ascent-descent with
respect to the Wasserstein metric -- a dynamics that admits efficient particle
discretization in high-dimensions, as opposed to entropic mirror descent. We
complement this positive result with a related entropy-regularized loss which
is not bilinear but still convex-concave in the Wasserstein geometry, and for
which simultaneous dynamics do not converge yet timescale separation does.
Taken together, these results showcase the benign geometry of bilinear games in
the space of measures, enabling particle dynamics with global qualitative
convergence guarantees.
Related papers
- Modeling the space-time correlation of pulsed twin beams [68.8204255655161]
Entangled twin-beams generated by parametric down-conversion are among the favorite sources for imaging-oriented applications.
We propose a semi-analytic model which aims to bridge the gap between time-consuming numerical simulations and the unrealistic plane-wave pump theory.
arXiv Detail & Related papers (2023-01-18T11:29:49Z) - Slow semiclassical dynamics of a two-dimensional Hubbard model in
disorder-free potentials [77.34726150561087]
We show that introduction of harmonic and spin-dependent linear potentials sufficiently validates fTWA for longer times.
In particular, we focus on a finite two-dimensional system and show that at intermediate linear potential strength, the addition of a harmonic potential and spin dependence of the tilt, results in subdiffusive dynamics.
arXiv Detail & Related papers (2022-10-03T16:51:25Z) - 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) - Mesoscopic M\"obius ladder lattices as non-Hermitian model systems [0.0]
We focus on two realizations of non-Hermitian physics in mesoscopic systems.
First, we consider spiral optical microcavities in which the asymmetric scattering between whispering gallery modes induces the non-Hermitian behaviour.
Second, for parity-time (PT) symmetric ladder lattices we compare circular and M"obius geometries.
arXiv Detail & Related papers (2022-05-03T17:10:36Z) - Dynamics of charge-imbalance-resolved entanglement negativity after a
quench in a free-fermion model [0.0]
We study the time evolution of charge-imbalance-resolved negativity after a global quench.
We derive and conjecture a formula for the dynamics of the charged R'enyi logarithmic negativities.
arXiv Detail & Related papers (2022-02-10T20:25:24Z) - Geometric phase in a dissipative Jaynes-Cummings model: theoretical
explanation for resonance robustness [68.8204255655161]
We compute the geometric phases acquired in both unitary and dissipative Jaynes-Cummings models.
In the dissipative model, the non-unitary effects arise from the outflow of photons through the cavity walls.
We show the geometric phase is robust, exhibiting a vanishing correction under a non-unitary evolution.
arXiv Detail & Related papers (2021-10-27T15:27:54Z) - Diffusive-to-ballistic crossover of symmetry violation in open many-body
systems [0.0]
We study the dynamics of textitsymmetry violation in quantum many-body systems with slight coherent (at strength $lambda$) or incoherent breaking of their local and global symmetries.
We show that symmetry breaking generically leads to a crossover in the divergence growth from diffusive behavior at onset times to ballistic or hyperballistic scaling at intermediate times, before diffusion dominates at long times.
arXiv Detail & Related papers (2020-09-30T18:00:00Z) - 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.