AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems

2024/06/20 by Xuan Zhang, Zhang, Xuan, Qiushui Xu +3 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2406.14371

openalex publication_date 2024/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider double-regularized nonconvex-strongly concave (NCSC) minimax problems of the form (P):min_x\inX max_y\inYg(x)+f(x,y)-h(y), where g, h are closed convex, f is L-smooth in (x,y) and strongly concave in y. We propose a proximal alternating gradient descent ascent method AGDA+ that can adaptively choose nonmonotone primal-dual stepsizes to compute an approximate stationary point for (P) without requiring the knowledge of the global Lipschitz constant L and the concavity modulus μ. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out by its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyper-parameters. AGDA+ achieves the optimal iteration complexity of O(ε^-2) and it is the first step-size search method for NCSC minimax problems that require only 3 calls to ∇ f on average per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency.

Cited by

• An Accelerated Primal Dual Algorithm with Backtracking for Decentralized Constrained Optimization
• A Retraction-free Method for Nonsmooth Minimax Optimization over a Compact Manifold

Related

• A Stochastic GDA Method With Backtracking For Solving Nonconvex (Strongly) Concave Minimax Problems
• Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Fundamental Benefit of Alternating Updates in Minimax Optimization