On the Convergence of Min-Max Langevin Dynamics and Algorithm

• URL: http://arxiv.org/abs/2412.20471v2
• Date: Fri, 07 Feb 2025 14:12:47 GMT
• Title: On the Convergence of Min-Max Langevin Dynamics and Algorithm
• Authors: Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono,
• Abstract summary: We study zero-sum games in the space of probability distributions over the Euclidean space $mathbbRd$ with entropy regularization. We prove an exponential convergence guarantee for the mean-field min-max Langevin dynamics to compute the equilibrium distribution.
• Score: 15.132772939268989
• License:
• Abstract: We study zero-sum games in the space of probability distributions over the Euclidean space $\mathbb{R}^d$ with entropy regularization, in the setting when the interaction function between the players is smooth and strongly convex-strongly concave. We prove an exponential convergence guarantee for the mean-field min-max Langevin dynamics to compute the equilibrium distribution of the zero-sum game. We also study the finite-particle approximation of the mean-field min-max Langevin dynamics, both in continuous and discrete times. We prove biased convergence guarantees for the continuous-time finite-particle min-max Langevin dynamics to the stationary mean-field equilibrium distribution with an explicit bias term which does not scale with the number of particles. We also prove biased convergence guarantees for the discrete-time finite-particle min-max Langevin algorithm to the stationary mean-field equilibrium distribution with an additional bias term which scales with the step size and the number of particles. This provides an explicit iteration complexity for the average particle along the finite-particle algorithm to approximately compute the equilibrium distribution of the zero-sum game.

Related papers

• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Exponential tail estimates for quantum lattice dynamics [1.2499537119440245]
  We consider the quantum dynamics of a particle on a lattice for large times. We show that the total probability of strictly outside the support of the measure goes to zero exponentially with $t$.
  arXiv  Detail & Related papers  (2024-08-04T18:35:36Z)
• Improved Particle Approximation Error for Mean Field Neural Networks [9.817855108627452]
  Mean-field Langevin dynamics (MFLD) minimizes an entropy-regularized nonlinear convex functional defined over the space of probability distributions. Recent works have demonstrated the uniform-in-time propagation of chaos for MFLD. We improve the dependence on logarithmic Sobolev inequality (LSI) constants in their particle approximation errors.
  arXiv  Detail & Related papers  (2024-05-24T17:59:06Z)
• 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)
• Fluctuation without dissipation: Microcanonical Langevin Monte Carlo [0.0]
  Langevin Monte Carlo sampling algorithms are inspired by physical systems in a heat bath. We show that the fluctuation-dissipation theorem is not required because only the configuration space distribution, and not the full phase space distribution, needs to be canonical. We propose a continuous-time Microcanonical Langevin Monte Carlo (MCLMC) as a dissipation-free system of differential equations (SDE)
  arXiv  Detail & Related papers  (2023-03-31T17:24:33Z)
• Non-asymptotic analysis of Langevin-type Monte Carlo algorithms [0.0]
  We study Langevin-type algorithms for sampling from Gibbs distributions with finite moduli of continuity not necessarily convergent to zero. We show that the Langevin Monte Carlo algorithm can approximate Gibbs distributions with arbitrary accuracy if the potentials are dissipative and their gradients are uniformly continuous.
  arXiv  Detail & Related papers  (2023-03-22T09:16:17Z)
• 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)
• 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)

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.