论文标题
统一的单环交替梯度投影算法，用于非convex-concave和convex-nonconcave minimax问题
A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems
论文作者
论文摘要
由于这些问题与一些新兴应用的相关性，最近针对有效算法来开发用于解决最小值问题的有效算法的许多研究工作。在本文中，我们提出了一种统一的单环交替梯度投影（AGP）算法，用于求解平滑的非凸 - （强烈）凹面，并且（强烈）凸出 - 毫无疑问minimax问题。 AGP采用简单的梯度投影步骤来更新每次迭代时的原始变量和双变量。我们表明，它可以找到目标函数的$ \ VAREPSILON $ - 定位点，以$ \ MATHCAL {O} \ left（\ var varepsilon ^{ - 2} \ right）$（rep. $ \ mathcal {o \ nathcal {o} {o} \ left（\ varepsilon ^nort（\ varepsilon ^nortion）concrange（\ varepsilon ^nortrang）concrange（cont）。 NONCONVEX-CONCAVE）设置。此外，获得目标函数的$ \ VAREPSILON $ - 定位点的梯度复杂性由$ \ Mathcal {O} \ left（\ varepsilon ^{ - 2} \ right）$（wortepsilon ^{-2} \ right）$（rep. （分别，凸 - 孔concave）设置。据我们所知，这是第一次开发出一种简单而统一的单循环算法来解决非convex-（强烈）凹面和（强烈）凸出 - 非concave minimax问题。此外，在文献中从未获得过解决后者（强烈）凸线 - 非孔洞最小问题的复杂性结果。数值结果表明所提出的AGP算法的效率。此外，我们通过提出块交替近端梯度（BAPG）算法来扩展AGP算法，以求解更通用的多块非块nonmooth nonmooth nonmooth noncovex-（强）凹面和（强烈）convex-nononconcave minimimax问题。我们可以在这四种不同的设置下类似地确定所提出算法的梯度复杂性。
Much recent research effort has been directed to the development of efficient algorithms 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 $\varepsilon$-stationary point of the objective function in $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) iterations under nonconvex-strongly concave (resp. nonconvex-concave) setting. Moreover, its gradient complexity to obtain an $\varepsilon$-stationary point of the objective function is bounded by $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp., $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under the strongly convex-nonconcave (resp., convex-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.
