mlsanityData to 13 Oct 2026

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

arXiv 2301.03931 ↗First posted 10 Jan 2023cs.GT cs.LG math.OCcited by 4

Not on the map. Why?

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.

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

Builds on

15 of 32 references.

References · 15

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,379
  2. 2022Generative Adversarial Networkscited by 5,614
  3. 2017Training GANs with Optimismcited by 217
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  5. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  6. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 134
  7. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 99
  8. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  9. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  10. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  11. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  12. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
3 more
  1. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  2. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  3. 2021Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Gamescited by 6

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 0; 2026: 1.

4 papers.

  1. 2024Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignmentcited by 20
  2. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  3. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  4. 2026Linear Convergence in Games with Delayed Feedback via Extra Predictioncited by 0