Mirror Descent-Ascent for mean-field min-max problems
Not on the map. Why?
Abstract (arXiv)
We study two variants of the mirror descent-ascent (MDA) algorithm for solving min-max problems on the space of measures: simultaneous and alternating. We work under assumptions of convexity-concavity and relative smoothness of the payoff function with respect to a suitable Bregman divergence, defined on the space of measures via flat derivatives. We establish non-asymptotic convergence rates to mixed Nash equilibria, measured in the Nikaido-Isoda error, proving an O(N-1/2) rate for simultaneous MDA and an improved O(N-2/3) rate for alternating MDA. The main technical contribution is an infinite-dimensional dual space analysis that relates Bregman divergences on measures to dual Bregman divergences on spaces of bounded continuous functions, allowing us to control asymmetric commutator terms created by alternating updates. The results substantially generalize prior analyses restricted to bilinear objectives and also apply to nonlinear convex-concave problems on measure spaces, thereby providing a unified theoretical foundation for MDA in mean-field min-max optimization.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 19 of its 49 references that are in the map. First posted on arXiv 12 Feb 2024.
Builds on
19 of 49 references.
References · 19
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
- 2014Convex Optimization: Algorithms and Complexitycited by 569
- 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
- 2017MMD GAN: Towards Deeper Understanding of Moment Matching Networkcited by 251
- 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
- 2022Mean-Field Langevin Dynamics: Exponential Convergence and Annealingcited by 60
- 2022Convex Analysis of the Mean Field Langevin Dynamicscited by 53
- 2019Mean-Field Langevin Dynamics and Energy Landscape of Neural Networkscited by 49
- 2018Finding Mixed Nash Equilibria of Generative Adversarial Networkscited by 48
- 2022Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EMcited by 33
- 2021Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measurescited by 19
7 more
- 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
- 2022An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Gamescited by 14
- 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
- 2022Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspectivecited by 13
- 2023Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problemscited by 11
- 2023On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce itcited by 4
- 2024Mirror Descent for Stochastic Control Problems with Measure-valued Controlscited by 2
Built on by
Citing papers per year: 2024: 1.
1 paper.