Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems
Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Junchi Yang;N. Kiyavash;Niao He
中科院分区：
文献类型：
--
作者：
Junchi Yang;N. Kiyavash;Niao He
非凸极大极小问题经常出现在新兴的机器学习应用中，例如生成对抗网络和对抗学习。简单的算法，如梯度下降上升（GDA）是解决这些非凸博弈的常见做法，并获得了大量的经验成功。然而，它是已知的，这些香草GDA算法具有恒定的步长可以潜在地发散，即使在凹凸设置。在这项工作中，我们证明了，对于一个子类的非凸非凹目标满足所谓的双边Polyak-Jasojasiewicz不等式，交替梯度下降上升（AGDA）算法全局收敛在一个线性速率和随机AGDA达到一个次线性速率。我们进一步开发了一个方差减少算法，当问题具有有限和结构时，该算法可以比AGDA获得更快的速度。
Nonconvex minimax problems appear frequently in emerging machine learning applications, such as generative adversarial networks and adversarial learning. Simple algorithms such as the gradient descent ascent (GDA) are the common practice for solving these nonconvex games and receive lots of empirical success. Yet, it is known that these vanilla GDA algorithms with constant stepsize can potentially diverge even in the convex-concave setting. In this work, we show that for a subclass of nonconvex-nonconcave objectives satisfying a so-called two-sided Polyak-Łojasiewicz inequality, the alternating gradient descent ascent (AGDA) algorithm converges globally at a linear rate and the stochastic AGDA achieves a sublinear rate. We further develop a variance reduced algorithm that attains a provably faster rate than AGDA when the problem has the finite-sum structure.