A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition
Not on the map. Why?
Abstract (arXiv)
We study a class of nonconvex-nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka-Lojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or Polyak-Lojasiewicz (PL) conditions commonly assumed in the literature -- which are significantly stronger and often too restrictive in practice -- this local KL condition accommodates a broader range of practical scenarios. However, it also introduces new analytical challenges. In particular, as an optimization algorithm progresses toward a stationary point of the problem, the region over which the KL condition holds may shrink, resulting in a more intricate and potentially ill-conditioned landscape. To address this challenge, we show that the associated maximal function is locally generalized H"older smooth. Leveraging this key property, we develop an inexact proximal gradient method for solving the minimax problem, where the inexact gradient of the maximal function is computed by applying a proximal gradient method to a KL-structured subproblem. Under mild assumptions, we establish complexity guarantees for computing an approximate stationary point of the minimax problem.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 23 of its 37 references that are in the map. First posted on arXiv 2 Jul 2025.
Builds on
23 of 37 references.
References · 23
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 337
- 2018Stochastic model-based minimization of weakly convex functionscited by 159
- 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 148
- 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
- 2019Distributionally Robust Optimization: A Reviewcited by 76
- 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
- 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
- 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
- 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
- 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
11 more
- 2014Splitting methods with variable metric for KL functionscited by 26
- 2024Distributionally Robust Optimization and Robust Statisticscited by 24
- 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
- 2019What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?cited by 20
- 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
- 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 12
- 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 11
- 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
- 2016Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteriacited by 5
- 2024Convergence of Descent Optimization Algorithms under Polyak-L ojasiewicz-Kurdyka Conditionscited by 4
- 2025Doubly Smoothed Optimistic Gradients: A Universal Approach for Smooth Minimax Problemscited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.