Mirror Descent-Ascent for mean-field min-max problems

Razvan-Andrei Lascu, Mateusz B. Majka, Lukasz SzpruchSubmission to ICLR 2026 · Rejected

TL;DR

This paper establishes the first theoretical comparison between simultaneous and alternating mirror descent-ascent (MDA) algorithms for min-max games on the space of probability measures. By leveraging duality with function spaces and third-order Fréchet derivatives, the authors prove that alternating updates achieve a convergence rate of $\mathcal{O}(N^{-2/3})$ in Nikaidò–Isoda error compared to $\mathcal{O}(N^{-1/2})$ for simultaneous updates, providing theoretical justification for why alternating training works better in practice for Generative Adversarial Networks (GANs).

What Problem Does This Paper Address?

In machine learning, challenging non-convex/non-concave min-max optimization problems—such as training GANs, certifying adversarial robustness, and solving multi-agent zero-sum Markov games—can often be convexified by "lifting" parameter optimization into the space of probability distributions (the mean-field regime). On measure spaces, mixed Nash equilibria (MNEs) are guaranteed to exist under mild conditions.

However, discrete-time optimization on the space of measures remains poorly understood:

  1. Prior discrete-time mean-field convergence analyses focus almost exclusively on simultaneous updates (both players update their distributions at the same time).
  2. Practical applications (notably GAN training) almost always train the discriminator and generator in an alternating fashion.
  3. Existing mean-field analyses often assume simple bilinear payoffs and relative-entropy regularizers.

This paper closes the theory-practice gap by analyzing general convex-concave, non-linear payoff functionals regularized by general Bregman divergences, rigorously comparing simultaneous and alternating playing conventions.

Methods

The authors analyze infinite-dimensional Mirror Descent-Ascent (MDA) over spaces of probability measures:

  • Bregman Divergences via Flat Derivatives: Divergences $D_h$ on probability measures are constructed via the flat derivative (first variation) of an underlying potential $h$ that is strongly convex with respect to the squared Total Variation ($\text{TV}^2$) metric (e.g., Kullback–Leibler divergence or $\chi^2$-divergence).
  • Dual Function Space Formulation: To analyze alternating updates, the authors introduce a duality framework mapping the measure space onto the Banach space of bounded continuous functions $C_b(\mathcal{X})$. The asymmetry introduced by alternating updates results in "Bregman commutators" ($D_h(\nu^n, \nu^{n+1}) - D_h(\nu^{n+1}, \nu^n)$). By bounding the third-order Fréchet derivative of the convex conjugate $h^*$, these commutators are proved to decay as $\mathcal{O}(\tau^3)$.
  • Implementable Particle Scheme: Because ideal updates require computing distributions, practical implementation discretizes the dual updates via Langevin dynamics with exponential damping to sample parameter particles across iterations.

Datasets

The authors validate the theoretical convergence behavior on two synthetic 2D benchmarks widely used in the generative modeling literature:

  • 8-Gaussian Mixture: Eight symmetric 2D Gaussian modes arranged in a circle.
  • Swiss Roll: A continuous, non-linear 2D manifold with spiral geometry.

No new datasets were introduced.

Key Insights and Ideas

  • Why Alternating Updates Are Faster: In simultaneous play, the error caused by outdated gradient evaluations scales as $\mathcal{O}(\tau)$ per step, forcing a conservative stepsize $\tau = \Theta(N^{-1/2})$ and yielding an overall $\mathcal{O}(N^{-1/2})$ convergence rate. Alternating updates allow the second player to react immediately to the first player's move. The resulting residual cross-terms cancel out up to a third-order commutator $\mathcal{O}(\tau^3 / \tau) = \mathcal{O}(\tau^2)$. Balancing this with the $\mathcal{O}(1 / (N\tau))$ term allows a larger stepsize $\tau = \Theta(N^{-1/3})$, leading to the accelerated rate $\mathcal{O}(N^{-2/3})$.
  • Primal-Dual Geometric Bridge: Bounding commutators directly on the space of measures is challenging. Transporting the problem to the dual space of functions $C_b(\mathcal{X})$ allows standard calculus (Taylor expansion with integral remainders and Fréchet derivatives) to control higher-order terms cleanly.
  • Broad Scope Beyond Bilinear Games: Unlike prior work restricted to bilinear payoffs, the bounds accommodate general non-linear convex-concave objectives satisfying relative smoothness, extending directly to adversarial training of two-layer neural networks and zero-sum Markov games.

Key Results

  • Theoretical Convergence Rates (Nikaidò–Isoda Error):
  • Simultaneous MDA: Converges at rate $\mathcal{O}(N^{-1/2})$ with stepsize $\tau = \Theta(N^{-1/2})$.
  • Alternating MDA: Converges at rate $\mathcal{O}(N^{-2/3})$ with stepsize $\tau = \Theta(N^{-1/3})$.
  • Implicit MDA (Benchmark): An idealized, non-implementable implicit scheme achieves $\mathcal{O}(N^{-1})$, matching the continuous-time gradient flow.
  • Empirical Validation:
  • On both the 8-Gaussian mixture and the Swiss Roll datasets, the alternating variant captures multi-modal structures and non-linear spiral geometry substantially earlier (within 500 iterations) than the simultaneous scheme.
  • Alternating MDA consistently achieves a much lower $L^1$-Wasserstein distance $W_1(T_{\theta^n}\#\xi, \hat{\xi})$ between generated and target distributions throughout training.

Limitations and Future Work

  • Time-Averaged vs. Last-Iterate Convergence: Guarantees apply to the uniform time-averaged trajectory of measures ($\frac{1}{N}\sum_{n=0}^{N-1} \nu^n$), whereas deep learning practitioners typically use the last iterate.
  • Discretization and Sampling Noise: The theoretical rates assume exact computation of measure updates. The implementable particle implementation relies on inner-loop Langevin sampling, which introduces stochastic approximation errors that are not explicitly bounded in the main convergence theorems.
  • Extension to Extragradient / Mirror Prox: While deterministic Mirror Prox achieves $\mathcal{O}(N^{-1})$, alternating extensions of Mirror Prox on measure spaces remain an open direction for future exploration.

Summary updated

Abstract

We study two variants of the mirror descent-ascent algorithm for solving min-max problems on the space of measures: simultaneous and sequential. 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 show that the convergence rates to mixed Nash equilibria, measured in the Nikaidò-Isoda error, are of order $\mathcal{O}\left(N^{-1/2}\right)$ and $\mathcal{O}\left(N^{-2/3}\right)$ for the simultaneous and sequential schemes, respectively, which is in line with the state-of-the-art results for related finite-dimensional algorithms.
BibTeX
@misc{lascu2024mirror,
  author = {Razvan-Andrei Lascu and Mateusz B. Majka and Lukasz Szpruch},
  title = {{Mirror Descent-Ascent for mean-field min-max problems}},
  year = {2024},
  eprint = {2402.08106},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.08106},
}

Loading related content...

Figure