论文标题
一类非Convex-Nonconcave minimax问题
Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems
论文作者
论文摘要
在本文中，我们考虑了一类非convex-nonconcave minimax问题，即NC-PL minimax问题，其目标函数满足了相对于内部变量的Polyak-łojasiewicz（PL）条件。我们提出了一个零阶交流梯度下降（ZO-AGDA）算法和一个零级方差降低，可在确定性和随机设置下分别解决NC-PL Minimax问题，以求解NC-PL Minimax问题的交替梯度下降（ZO-VRAGDA）算法。获得ZO-AGDA和ZO-VRAGDA算法的$ε$ - 定位点的功能值查询总数用于求解NC-PL minimax问题的上限是由$ \ Mathcal {O}（O}（O}（O}（\ varepsilon^{ - 2}}} { - 2}}）$和$ \ MATHCAL CAL CAL CAL CALCAL {O}（\ VAREPSILON 分别。据我们所知，它们是前两个零件算法，具有迭代复杂性Gurantee用于解决NC-PL Minimax问题。
In this paper, we consider a class of nonconvex-nonconcave minimax problems, i.e., NC-PL minimax problems, whose objective functions satisfy the Polyak-Łojasiewicz (PL) condition with respect to the inner variable. We propose a zeroth-order alternating gradient descent ascent (ZO-AGDA) algorithm and a zeroth-order variance reduced alternating gradient descent ascent (ZO-VRAGDA) algorithm for solving NC-PL minimax problem under the deterministic and the stochastic setting, respectively. The total number of function value queries to obtain an $ε$-stationary point of ZO-AGDA and ZO-VRAGDA algorithm for solving NC-PL minimax problem is upper bounded by $\mathcal{O}(\varepsilon^{-2})$ and $\mathcal{O}(\varepsilon^{-3})$, respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with the iteration complexity gurantee for solving NC-PL minimax problems.
