mlsanityData to 7 Oct 2026

A first-order method for nonconvex-strongly-concave constrained minimax optimization

arXiv 2512.22909 ↗First posted 28 Dec 2025math.OC cs.LG cs.NAcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper we study a nonconvex-strongly-concave constrained minimax problem. Specifically, we propose a first-order augmented Lagrangian method for solving it, whose subproblems are nonconvex-strongly-concave unconstrained minimax problems and suitably solved by a first-order method developed in this paper that leverages the strong concavity structure. Under suitable assumptions, the proposed method achieves an operation complexity of O(varepsilon-3.5logvarepsilon-1), measured in terms of its fundamental operations, for finding an varepsilon-KKT solution of the constrained minimax problem, which improves the previous best-known operation complexity by a factor of varepsilon-0.5.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 40 of its 76 references that are in the map. First posted on arXiv 28 Dec 2025.

Builds on

40 of 76 references.

References · 40

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  6. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  7. 2016Variance-based regularization with convex objectivescited by 153
  8. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  9. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  10. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  11. 2020Perceptual Adversarial Robustness: Defense Against Unseen Threat Modelscited by 137
  12. 2015Distributionally Robust Logistic Regressioncited by 124
28 more
  1. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  2. 2018Multi-Agent Generative Adversarial Imitation Learningcited by 99
  3. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  4. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  5. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  6. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  7. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  8. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  9. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  10. 2019Adversarial Attack Generation Empowered by Min-Max Optimizationcited by 32
  11. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  12. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  13. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  14. 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
  15. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  16. 2020Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Conditioncited by 19
  17. 2019Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraintscited by 17
  18. 2021Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometrycited by 17
  19. 2020A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimizationcited by 14
  20. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  21. 2019On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimizationcited by 10
  22. 2021Convex-Concave Min-Max Stackelberg Gamescited by 9
  23. 2020Adversarial Classification via Distributional Robustness with Wasserstein Ambiguitycited by 8
  24. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  25. 2019Complexity and performance of an Augmented Lagrangian algorithmcited by 6
  26. 2020Optimality Conditions for Constrained Minimax Optimizationcited by 6
  27. 2022Optimality Conditions and Numerical Algorithms for A Class of Linearly Constrained Minimax Optimization Problemscited by 4
  28. 2019Network Interdiction Using Adversarial Traffic Flowscited by 1

Built on by

Not cited yet.