论文标题
全局收敛和降低方差的优化，用于一类非convex-nonconcave minimax问题
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
论文作者
论文摘要
NonConvex Minimax问题经常出现在新兴的机器学习应用程序中，例如生成对抗网络和对抗性学习。简单的算法（例如梯度下降（GDA））是解决这些非convex游戏并获得很多经验成功的常见实践。然而，众所周知，这些具有恒定步长的香草GDA算法即使在凸设置中也可能有所不同。在这项工作中，我们表明，对于不满足所谓的两边的Polyak-olojasiewicz不平等的非convex-Nonconcave目标的子类，交替的梯度下降（AGDA）算法以线性速率和随机的AGDA实现了sublineAre速率。我们进一步开发了一种降低的算法，当问题具有有限的-AM结构时，该算法比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 step size can potentially diverge even in the convex 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.
