# Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

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

- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.05422/) (2023)
- [An Optimisation Framework for Unsupervised Environment Design](https://mlsanity.com/paper/2505.20659/) (2025)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games](https://mlsanity.com/paper/2106.03579/) (2021)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Transferable Reward Learning by Dynamics-Agnostic Discriminator Ensemble](https://mlsanity.com/paper/2206.00238/) (2022)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures](https://mlsanity.com/paper/2106.02615/) (2021)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)
- [Last-Iterate Convergence of Optimistic Multiplicative Weight Update](https://mlsanity.com/paper/2606.11773/) (2026)

## Abstract (arXiv)

In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, citeDISZ17, LiangS18 show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of textitunconstrained min-max optimization. Moreover, in citeMetal the authors show that Mirror Descent with an extra gradient step displays last iterate convergence for convex-concave problems (both constrained and unconstrained), though their algorithm does not follow the online learning framework; it uses extra information rather than textitonly the history to compute the next iteration. In this work, we show that "Optimistic Multiplicative-Weights Update (OMWU)" which follows the no-regret online learning framework, exhibits last iterate convergence locally for convex-concave games, generalizing the results of citeDP19 where last iterate convergence of OMWU was shown only for the textitbilinear case. We complement our results with experiments that indicate fast convergence of the method.