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

• URL: http://arxiv.org/abs/2512.22909v2
• Date: Mon, 05 Jan 2026 03:03:50 GMT
• Title: A first-order method for nonconvex-strongly-concave constrained minimax optimization
• Authors: Zhaosong Lu, Sanyou Mei,
• Abstract summary: We propose a first-order subproblems method for non-strongly-con constrained minimax problems.<n>We find an $epsilon$-KK solution which improves the previous best-known operation.
• Score: 2.735801286587348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.5}\log\varepsilon^{-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}$.

Related papers

• Solving bilevel optimization via sequential minimax optimization [2.735801286587348]
  We study a class of constrained bilevel optimization problems in which the part is a possibly non-smooth convex part.<n>We find that the SMO method improves the complexity of the lower-level objective functions.<n>Preliminary results compare to the recently developed first-order penalty performance.
  arXiv  Detail & Related papers  (2025-11-10T18:51:05Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  The minimax algorithms for neural networks have been developed to solve many problems. In this paper, we propose two types of minimax algorithms. For the setting, we propose DRSGDA and prove that our method achieves a gradient.
  arXiv  Detail & Related papers  (2023-02-08T01:42:45Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• A first-order augmented Lagrangian method for constrained minimax optimization [1.0742675209112622]
  In particular, we propose a first-order augmented Lagrangian method for solving constrained minimax problems. An emphoperation complexity of $O(varepsilon-4logvarepsilon-1)$, measured by its fundamental operations, is established for the first-order method.
  arXiv  Detail & Related papers  (2023-01-05T13:32:22Z)
• First-order penalty methods for bilevel optimization [1.2691047660244337]
  We show a class of $varepsilon$ complexity solution for unconstrained and constrained bilevel optimization problems. We also propose first-order penalty methods for finding an $epsilon$KKT solution of the unconstrained and constrained bilevel problems.
  arXiv  Detail & Related papers  (2023-01-04T17:29:04Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of emphconcave unconstrained problems.<n>Our method improves the existing line-search-based min-max optimization by shaving off an $O(loglog(1/eps)$ factor in the required number of Schur decompositions.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  In this paper, we propose an algorithm for nonsmooth zeroth-order minimax problems. We show that it can be used to attack nonconcave minimax problems.
  arXiv  Detail & Related papers  (2021-08-01T15:23:49Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.