mlsanityData to 14 Oct 2026

Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems

arXiv 2302.09831 ↗First posted 20 Feb 2023math.OC cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. This observation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures as we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require a less restrictive parameter range in the weak MVI compared to what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive stepsize allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles.

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

Builds on

21 of 44 references.

References · 21

  1. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  2. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  3. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  4. 2017Cycles in adversarial regularized learningcited by 124
  5. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  6. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  7. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  8. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  9. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  10. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  11. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
  12. 2019On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Gamescited by 35
9 more
  1. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
  2. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 32
  3. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  4. 2019Generalized monotone operators and their averaged resolventscited by 27
  5. 2020Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separationcited by 10
  6. 2016Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operatorscited by 8
  7. 2020Two steps at a time -- taking GAN training in stride with Tseng's methodcited by 8
  8. 2021Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problemscited by 6
  9. 2019Nonlinear Forward-Backward Splitting with Projection Correctioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 8; 2024: 1; 2025: 7; 2026: 5.

21 papers.

Sort:

By area:

  1. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  2. 2025Worst-case generation via minimax optimization in Wasserstein spacecited by 7
  3. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  4. 2025Expected Variational Inequalitiescited by 5
  5. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  6. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 5
  7. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  8. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  9. 2023Generating Less Certain Adversarial Examples Improves Robust Generalizationcited by 3
  10. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  11. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  12. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
9 more
  1. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1
  2. 2023Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicitycited by 1
  3. 2025A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz conditioncited by 1
  4. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 1
  5. 2025Spingarn's Method and Progressive Decoupling Beyond Elicitable Monotonicitycited by 0
  6. 2025A first-order method for constrained nonconvex-nonconcave minimax optimizationcited by 0
  7. 2026Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalitiescited by 0
  8. 2026Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusionscited by 0
  9. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0