On the Convergence of Min-Max Langevin Dynamics and Algorithm

Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:677-754, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-cai25a, title = {On the Convergence of Min-Max Langevin Dynamics and Algorithm}, author = {Cai, Yang and Mitra, Siddharth and Wang, Xiuyuan and Wibisono, Andre}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {677--754}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/cai25a/cai25a.pdf}, url = {https://proceedings.mlr.press/v291/cai25a.html}, 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. } }
Endnote
%0 Conference Paper %T On the Convergence of Min-Max Langevin Dynamics and Algorithm %A Yang Cai %A Siddharth Mitra %A Xiuyuan Wang %A Andre Wibisono %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-cai25a %I PMLR %P 677--754 %U https://proceedings.mlr.press/v291/cai25a.html %V 291 %X 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.
APA
Cai, Y., Mitra, S., Wang, X. & Wibisono, A.. (2025). On the Convergence of Min-Max Langevin Dynamics and Algorithm. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:677-754 Available from https://proceedings.mlr.press/v291/cai25a.html.

Related Material