ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints

We study smooth strongly convex--strongly concave minimax optimization in the deterministic unconstrained setting, without assuming a bilinear or separable structure. Although existing multi-loop methods attain near-optimal condition-number dependence, standard single-loop methods generally exhibit a substantial complexity gap. To close this gap, we propose the Single-Loop Predictor--Corrector Extragradient Method with Damped Momentum (PCE-DM), which combines an extragradient prediction--correction scheme with a novel auxiliary feedback recursion for the weaker-curvature variable. PCE-DM uses fixed parameters and two new full-gradient evaluations per iteration after one initialization query, while requiring no inner solves, accuracy schedules, or staged restarts. We develop a Lyapunov analysis that controls the predictor--corrector mismatch through corrected-gradient increments and establish last-iterate linear convergence. Specifically, PCE-DM computes an $\varepsilon$-accurate relative solution, measured by the squared Euclidean distance to the saddle point, within $\mathcal{O}\!\left(\sqrt{κ_xκ_y} \log(2κ_xκ_y/\varepsilon)\right)$ full-gradient queries. This result closes the condition-number complexity gap between standard single-loop methods and near-optimal multi-loop methods, matching the known lower-bound order up to logarithmic factors while retaining fixed, explicit single-loop updates. Numerical experiments on regularized linear regression and AUC maximization demonstrate the computational efficiency of PCE-DM.

We introduce a new single-loop algorithmic framework for smooth nonconvex--concave minimax optimization. The resulting projected damped extragradient method combines projected extragradient updates, dual momentum, and a moving proximal center. Under both the optimization-stationarity and game-stationarity criteria, our method achieves the best-known complexity among single-loop first-order methods. For optimization stationarity, our method achieves a gradient complexity of $O(L^2D_Y\barΔ_0\varepsilon^{-3})$, where $L$ is the gradient Lipschitz constant, $D_Y$ bounds the diameter of the dual feasible set, and $\barΔ_0$ is an initialization quantity involving the value-function gap and the initial gradients. Moreover, by incorporating a fixed-center warm-up phase, the complexity can be improved to $O(L^2D_YΔ_φ\varepsilon^{-3})$, up to an additive lower-order cost, where $Δ_φ:=φ(x_0)-\inf_xφ(x)$. We further establish a lower bound of $Ω(L^2D_YΔ_φ\varepsilon^{-3})$ for optimization stationarity over projected zero-respecting first-order methods. This lower bound proves that the warm-started version of our algorithm is optimal up to a constant factor for optimization stationarity within this oracle class. For game stationarity, our method achieves $\mathcal{O}\!(L^{3/2}D_Y^{1/2}Δ_φ\varepsilon^{-5/2})$ gradient complexity. This matches the best-known complexity of multi-loop first-order methods, thereby establishing the same complexity with a single-loop algorithmic structure. Under dual strong concavity, the proposed framework achieves $O\!(\sqrtκ\,LΔ_φ\varepsilon^{-2})$ leading complexity for both stationarity criteria, where $κ=L/μ$ is the dual condition number, up to an additive initialization cost. The $\varepsilon^{-2}$ accuracy dependence is optimal under fixed regularity and initialization bounds.

We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems under local multiplier regularity. Both the objective and functional inequality constraints are compositions of convex Lipschitz outer functions with smooth nonlinear mappings. Unlike existing analyses requiring regularity globally or along the entire iterate sequence, we impose multiplier regularity only near the feasible set. Using an auxiliary minimax problem with a compact dual set, we derive Lyapunov estimates that identify nearly feasible iterates under feasible initialization and a sufficiently large penalty, without assuming multiplier boundedness. Local regularity then bounds the associated multipliers and makes dual truncation inactive, yielding approximate KKT certificates for the original problem. The smoothed prox-linear augmented Lagrangian method with dual regularization yields an $O(K^{-1/3})$ KKT residual rate. Without regularization, piecewise linear outer functions and additional local structural assumptions yield a local dual error bound and the sharper $O(K^{-1/2})$ rate.