Research map / Optimization / Nonconvex and smooth optimization
Mirror Descent-Ascent for mean-field min-max problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes simultaneous and alternating mirror descent-ascent for convex-concave mean-field min-max games over probability measures, proving O(N^-1/2) NI-error rate for simultaneous and an improved O(N^-2/3) rate for alternating MDA via a dual-space commutator argument.
Problem
Computing mixed Nash equilibria of convex-concave min-max games over spaces of probability measures (mean-field games/GANs/RLHF), where non-asymptotic guarantees for alternating updates are missing and Bregman geometry on measures lacks an inner product.
Approach
Extends mirror descent to two-player measure-space min-max games using flat-derivative Bregman divergences, and shows alternating updates' asymmetric Bregman commutator terms can be transported to a dual space of bounded continuous functions, where a third-order smoothness bound of the dual mirror map gives cubic control and a faster rate.
Key results
- Simultaneous MDA attains NI error O(N^-1/2) with step size tau = Theta(N^-1/2) under convexity-concavity, relative smoothness and bounded flat derivatives.
- Alternating MDA attains improved NI error O(N^-2/3) with tau = Theta(N^-1/3), using a third-order smoothness bound on the dual mirror map.
- For bilinear games the alternating rate O(N^-2/3) matches known finite-dimensional MDA rates, and the analysis generalizes to nonlinear convex-concave payoffs.
Limitations
- Alternating analysis requires a third-order smoothness assumption on the dual mirror map, verified only for relative entropy and chi-squared (self-concordance only for chi-squared).
- Convergence is shown only for time-averaged iterates, since monotonicity of the objective is lost in min-max settings.
- Requires boundedness of flat derivatives and initialization with finite sup Bregman divergence, which must be checked case by case.
Experimental setup
Metrics: Nikaido-Isoda error
Baselines: simultaneous MDA entropic mirror-prox Fisher-Rao gradient flow
Builds on: mirror descent mirror-prox measure-space mirror descent (Lascu et al. / Ghosh-style infinite-dimensional MD Fisher-Rao gradient flow for mean-field min-max
Closest papers by meaning
- Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity (NeurIPS 2026 · similarity 0.87)
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.87)
- Fundamental Benefit of Alternating Updates in Minimax Optimization (ICML 2024 · similarity 0.86)
- Convergence of Policy Mirror Descent Beyond Compatible Function Approximation (ICML 2025 · similarity 0.86)
- Last-iterate Convergence in Regularized Graphon Mean Field Game (AAAI 2025 · similarity 0.85)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.