论文标题
关于非convex-nonconcave minimax问题的额外梯度方法的线性收敛
On the Linear Convergence of Extra-Gradient Methods for Nonconvex-Nonconcave Minimax Problems
论文作者
论文摘要
最近，由于现代化的机器学习，强大的优化和强化学习，Minimax优化获得了重新焦点。这些应用的规模自然会导致使用一阶方法。但是，这些问题中存在的非概念性和非cove性阻止了典型梯度下降的应用，即使在双线性问题中也存在差异。最近，结果表明，对于非Convex-Nonconcave问题的家族，近端方法（PPM）线性收敛。在本文中，我们研究了阻尼版本的额外梯度方法（EGM）的收敛性，该方法避免了潜在的昂贵近端计算，仅依靠梯度评估。我们表明，EGM线性收敛，以实现平滑的最小优化问题，该问题满足了PPM所需的相同非Convex-Nonconcave条件。
Recently, minimax optimization received renewed focus due to modern applications in machine learning, robust optimization, and reinforcement learning. The scale of these applications naturally leads to the use of first-order methods. However, the nonconvexities and nonconcavities present in these problems, prevents the application of typical Gradient Descent-Ascent, which is known to diverge even in bilinear problems. Recently, it was shown that the Proximal Point Method (PPM) converges linearly for a family of nonconvex-nonconcave problems. In this paper, we study the convergence of a damped version of Extra-Gradient Method (EGM) which avoids potentially costly proximal computations, only relying on gradient evaluation. We show that EGM converges linearly for smooth minimax optimization problem satisfying the same nonconvex-nonconcave condition needed by PPM.
