First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Mingrui Liu;Hassan Rafique;Qihang Lin;Tianbao Yang
中科院分区：
文献类型：
--
作者：
Mingrui Liu;Hassan Rafique;Qihang Lin;Tianbao Yang
本文研究了一类非凸非凹极小极大鞍点问题的一阶收敛理论和算法，该问题的目标函数是极小化变量弱凸和极大化变量弱凹。它在机器学习中有许多重要的应用，包括训练生成性对手网(GANS)。提出了一种基于不精确邻近点方法的算法框架，通过在原梯度映射中添加一个强单调映象构造的强单调Vis序列的近似求解来求解与原Min-Max问题相对应的弱单调变分不等式(VI)。我们证明了通用算法框架下原最小-最大问题的一阶收敛到一个几乎稳定的解，并通过对每个强单调VI采用不同的算法来建立不同的速率。实验验证了收敛理论，也证明了所提出的方法在训练遗传算法上的有效性。
In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is weakly convex in the variables of minimization and weakly concave in the variables of maximization. It has many important applications in machine learning including training Generative Adversarial Nets (GANs). We propose an algorithmic framework motivated by the inexact proximal point method, where the weakly monotone variational inequality (VI) corresponding to the original min-max problem is solved through approximately solving a sequence of strongly monotone VIs constructed by adding a strongly monotone mapping to the original gradient mapping. We prove first-order convergence to a nearly stationary solution of the original min-max problem of the generic algorithmic framework and establish different rates by employing different algorithms for solving each strongly monotone VI. Experiments verify the convergence theory and also demonstrate the effectiveness of the proposed methods on training GANs.