A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems

• 成果类型: Article
• 署名作者: Xu, Zi; Zhang, Huiling; Xu, Yang; Lan, Guanghui
• 署名单位: Shanghai University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01919-z
• 发表日期: 2023
• 页码: 635-706
• 关键词: saddle-point; variational-inequalities; optimization; complexity

摘要

Much recent research effort has been directed to the development of efficient algo-rithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and dual variables alternatively at each iteration. We show that it can find an epsilon-stationary point of the objective function in O (epsilon(-2)) (resp. O (epsilon(-4))) iterations under nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its gradi-by O (epsilon(-2)) (resp., O (epsilon(-4))) under the strongly convex-nonconcave (resp., convex- ent complexity to obtain an epsilon-stationary point of the objective function is bounded nonconcave) setting. To the best of our knowledge, this is the first time that a simple and unified single-loop algorithm is developed for solving both nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. Moreover, the complexity results for solving the latter (strongly) convex-nonconcave minimax problems have never been obtained before in the literature. Numerical results show the efficiency of the proposed AGP algorithm. Furthermore, we extend the AGP algorithm by presenting a block alternating proximal gradient (BAPG) algorithm for solving more general multi-block nonsmooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. We can similarly establish the gradient complexity of the proposed algorithm under these four different settings.