The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
C. Daskalakis;Ioannis Panageas
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Ioannis Panageas
受到优化，游戏理论的应用以及生成对抗网络的培训的动机，在最小问题问题中，一阶方法的收敛属性已获得了广泛的研究。人们已经认识到他们可能会循环，并且当他们没有时，对其限制点没有很好的了解。当它们融合时，它们会收敛到本地的最低最大解决方案吗？我们表征了两种基本一阶方法的极限点，即梯度下降/上升（GDA）和乐观的梯度下降上升（OGDA）。我们表明，这两种动态避免了几乎所有初始化的不稳定关键点。此外，对于小步骤尺寸和在温和的假设下，\ {ogda \}的集合 - 稳定的关键点是\ {gda \}的超集 - 稳定的关键点，这是本地最小 - 最大解决方案的超集（严格在有些情况）。连接线程是可以从动态系统的角度研究这些动力学的行为。
Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they do not. When they converge, do they converge to local min-max solutions? We characterize the limit points of two basic first order methods, namely Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA). We show that both dynamics avoid unstable critical points for almost all initializations. Moreover, for small step sizes and under mild assumptions, the set of \{OGDA\}-stable critical points is a superset of \{GDA\}-stable critical points, which is a superset of local min-max solutions (strict in some cases). The connecting thread is that the behavior of these dynamics can be studied from a dynamical systems perspective.