Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria
of Continuous Games: A Mean-Field Perspective
- URL: http://arxiv.org/abs/2212.08791v1
- Date: Sat, 17 Dec 2022 03:44:35 GMT
- Title: Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria
of Continuous Games: A Mean-Field Perspective
- Authors: Yulong Lu
- Abstract summary: Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous game is an important and challenging problem in machine learning.
We first study the convergence of a two-scale Mean-Field GDA dynamics for finding the MNE of the entropy-regularized objective.
- Score: 5.025654873456756
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous
game is an important and challenging problem in machine learning. A canonical
algorithm to finding the MNE is the noisy gradient descent ascent method which
in the infinite particle limit gives rise to the {\em Mean-Field Gradient
Descent Ascent} (GDA) dynamics on the space of probability measures. In this
paper, we first study the convergence of a two-scale Mean-Field GDA dynamics
for finding the MNE of the entropy-regularized objective. More precisely we
show that for any fixed positive temperature (or regularization parameter), the
two-scale Mean-Field GDA with a {\em finite} scale ratio converges to
exponentially to the unique MNE without assuming the convexity or concavity of
the interaction potential. The key ingredient of our proof lies in the
construction of new Lyapunov functions that dissipate exponentially along the
Mean-Field GDA. We further study the simulated annealing of the Mean-Field GDA
dynamics. We show that with a temperature schedule that decays logarithmically
in time the annealed Mean-Field GDA converges to the MNE of the original
unregularized objective function.
Related papers
- Learning Surrogate Potential Mean Field Games via Gaussian Processes: A Data-Driven Approach to Ill-Posed Inverse Problems [1.4325734372991794]
Mean field games (MFGs) describe the collective behavior of interacting agents.
We tackle ill-posed inverse problems in potential MFGs, aiming to recover the agents' population, momentum, and environmental setup.
arXiv Detail & Related papers (2025-02-17T07:14:30Z) - Convergence of two-timescale gradient descent ascent dynamics: finite-dimensional and mean-field perspectives [6.740173664466834]
The two-timescale gradient descent-ascent (GDA) is a canonical gradient algorithm designed to find Nash equilibria in min-max games.
We investigate the effects of learning rate ratios on convergence behavior in both finite-dimensional and mean-field settings.
arXiv Detail & Related papers (2025-01-28T18:13:41Z) - 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) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift.
Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures.
We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
arXiv Detail & Related papers (2023-06-12T16:28:11Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games.
Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
arXiv Detail & Related papers (2023-03-02T05:08:15Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
Gradient Descent (SGD) has been the method of choice for learning large-scale non-root models.
An overarching paper is providing general conditions SGD converges, assuming that GF on the population loss converges.
We provide a unified analysis for GD/SGD not only for classical settings like convex losses, but also for more complex problems including Retrieval Matrix sq-root.
arXiv Detail & Related papers (2022-10-13T03:55:04Z) - 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) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation.
Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective.
We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
arXiv Detail & Related papers (2021-07-21T17:10:14Z) - An Optimal Multistage Stochastic Gradient Method for Minimax Problems [8.615625517708324]
We study the minimax optimization problem in the smooth and strongly convex-strongly concave setting.
We first analyze the Gradient Descent Ascent (GDA) method with constant stepsize.
We propose a multistage variant of GDA that runs in multiple stages with a particular learning rate decay schedule.
arXiv Detail & Related papers (2020-02-13T18:01:18Z) - Function approximation by neural nets in the mean-field regime: Entropic regularization and controlled McKean-Vlasov dynamics [7.1822457112352955]
We consider the problem of function approximation by two-layer neural nets with random weights that are "nearly Gaussian"
We show that the problem can be phrased as global minimization of a free energy functional on the space of paths over probability measures on the weights.
arXiv Detail & Related papers (2020-02-05T20:50:33Z)
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.