# Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 10 Jan 2023.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games](https://mlsanity.com/paper/2106.03579/) (2021)

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

- [Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment](https://mlsanity.com/paper/2410.16714/) (2024)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Stable Nonconvex-Nonconcave Training via Linear Interpolation](https://mlsanity.com/paper/2310.13459/) (2023)
- [Linear Convergence in Games with Delayed Feedback via Extra Prediction](https://mlsanity.com/paper/2602.17486/) (2026)

## Abstract (arXiv)

In this paper we present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems while requiring a simple and intuitive analysis. Similarly to the seminal work of Nemirovski and the recent approach of Piliouras et al. in normal form games, our work is based on the fact that the update rule of the Proximal Point method (PP) can be approximated up to accuracy ε with only O(log 1/ε) additional gradient-calls through the iterations of a contraction map. Then combining the analysis of (PP) method with an error-propagation analysis we establish that the resulting first order method, called Clairvoyant Extra Gradient, admits near-optimal time-average convergence for general domains and last-iterate convergence in the unconstrained case.