arXiv preprint ·
ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an $\varepsilon$-KKT point within $\mathcal{O}(\varepsilon^{-7/2})$ complete first-order oracle evaluations in the strongly concave setting and $\mathcal{O}(\varepsilon^{-4})$ in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a $\log(1/\varepsilon)$ factor, while retaining a single-loop update structure.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Non-asymptotic analysis of SGLD with discontinuous stochastic gradients: a new route to portfolio CVaR minimization
Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization
Conic Certification of Transformer Attention
Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
Log-Driven Semantic Tuning for Mixed Integer Programming Solvers
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.