Mirror Descent-Ascent for mean-field min-max problems
Abstract
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 Nikaidô-Isoda error, proving an rate for simultaneous MDA and an improved 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.
Figures & tables
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| Component | Condition | Scheme | Verified settings |
| Mirror | Assumption 2.1 | Both | Relative entropy and |
| Assumption 3.4 | Alternating | Relative entropy and | |
| Payoff | Assumptions 2.2 and 2.3 | Both | Propositions C.1 , C.2 , C.6 |
| Assumption 3.3 | Alternating | Propositions C.1 , C.2 , C.6 | |
| Initial data | Finite initial Bregman divergences | Both | Lemmas B.7 and B.8 |
Min-Max Optimization
Min-max optimization studies algorithms for objectives where one decision-maker minimizes loss while an adversary or opponent maximizes it.
See all 42 papers