mlsanityData to 14 Oct 2026

Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion

arXiv 2206.05248 ↗First posted 10 Jun 2022math.OC cs.DS cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

We study constrained comonotone min-max optimization, a structured class of nonconvex-nonconcave min-max optimization problems, and their generalization to comonotone inclusion. In our first contribution, we extend the Extra Anchored Gradient (EAG) algorithm, originally proposed by Yoon and Ryu (2021) for unconstrained min-max optimization, to constrained comonotone min-max optimization and comonotone inclusion, achieving an optimal convergence rate of Oleft(frac1Tright) among all first-order methods. Additionally, we prove that the algorithm's iterations converge to a point in the solution set. In our second contribution, we extend the Fast Extra Gradient (FEG) algorithm, as developed by Lee and Kim (2021), to constrained comonotone min-max optimization and comonotone inclusion, achieving the same Oleft(frac1Tright) convergence rate. This rate is applicable to the broadest set of comonotone inclusion problems yet studied in the literature. Our analyses are based on simple potential function arguments, which might be useful for analyzing other accelerated algorithms.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 21 of its 51 references that are in the map. First posted on arXiv 10 Jun 2022.

Builds on

21 of 51 references.

References · 21

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  3. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  4. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  5. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  6. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  7. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  8. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  9. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  10. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  11. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  12. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
9 more
  1. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
  2. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  3. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  4. 2019Generalized monotone operators and their averaged resolventscited by 27
  5. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  6. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  7. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 21
  8. 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 20
  9. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 2; 2025: 8; 2026: 5.

20 papers.

Sort:

By area:

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  2. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  3. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 16
  4. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  5. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 12
  6. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  7. 2025An Optimisation Framework for Unsupervised Environment Designcited by 10
  8. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  9. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  10. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  11. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  12. 2025Expected Variational Inequalitiescited by 5
8 more
  1. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  2. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  3. 2025EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimizationcited by 1
  4. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 1
  5. 2025Characterizing Nash Equilibria in Zero-Sum Games: A Physics-Inspired, Parallelizable Approach with a Linear Number of Gradient Queriescited by 0
  6. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0
  7. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0
  8. 2026Optimal Oracle Complexity for Finite-Sum Monotone Inclusionscited by 0