# Alternating Mirror Descent for Constrained Min-Max Games

arXiv: https://arxiv.org/abs/2206.04160 · HTML: https://mlsanity.com/paper/2206.04160/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 8 Jun 2022.

## Builds on (most cited first, 18 of 18)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives](https://mlsanity.com/paper/2002.12493/) (2020)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System](https://mlsanity.com/paper/1903.01720/) (2019)
- [Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems](https://mlsanity.com/paper/2001.10006/) (2020)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)

## Built on by (most cited first, 13 of 13)

- [M3-JEPA: Multimodal Alignment via Multi-gate MoE based on the Joint-Embedding Predictive Architecture](https://mlsanity.com/paper/2409.05929/) (2024)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [LiteEFG: An Efficient Python Library for Solving Extensive-form Games](https://mlsanity.com/paper/2407.20351/) (2024)
- [Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games](https://mlsanity.com/paper/2505.19537/) (2025)
- [Mirror Descent-Ascent for mean-field min-max problems](https://mlsanity.com/paper/2402.08106/) (2024)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)
- [Barriers to Welfare Maximization with No-Regret Learning](https://mlsanity.com/paper/2411.01720/) (2024)
- [Minimax Alternating Regret for the Experts Problem and Online Convex Optimization](https://mlsanity.com/paper/2608.25182/) (2026)

## Abstract (arXiv)

In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as an alternating discretization of a skew-gradient flow in the dual space, and use tools from convex optimization and modified energy function to establish an O(K-2/3) bound on its average regret after K iterations. This quantitatively verifies the algorithm's better behavior than the simultaneous version of mirror descent algorithm, which is known to diverge and yields an O(K-1/2) average regret bound. In the special case of an unconstrained setting, our results recover the behavior of alternating gradient descent algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).