A Convergent and Dimension-Independent Min-Max Optimization Algorithm
A Convergent and Dimension-Independent Min-Max Optimization Algorithm
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Vijay Keswani;Oren Mangoubi;Sushant Sachdeva;Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
Vijay Keswani;Oren Mangoubi;Sushant Sachdeva;Nisheeth K. Vishnoi
我们研究了最近推出的最小最大优化框架的一个变体，其中最大玩家被约束以贪婪的方式更新其参数，直到它达到一阶稳定点。我们对这个框架的均衡定义取决于一个建议分布，最小玩家使用它来选择更新参数的方向。我们表明，给定一个光滑和有界的非凸非凹目标函数，访问任何建议分布的最小球员的更新，和随机梯度预言的最大球员，我们的算法收敛到上述近似的局部平衡在一些迭代，不依赖于尺寸。我们的算法找到的平衡点取决于建议分布，当应用我们的算法训练GAN时，我们选择建议分布为随机梯度分布。我们根据经验评估我们的算法对GAN训练中出现的非凸非凹测试函数和损失函数的挑战。我们的算法在这些测试函数上收敛，当用于训练GAN时，在合成和真实世界的数据集上稳定训练，并避免模式崩溃。
We study a variant of a recently introduced min-max optimization framework where the max-player is constrained to update its parameters in a greedy manner until it reaches a first-order stationary point. Our equilibrium definition for this framework depends on a proposal distribution which the min-player uses to choose directions in which to update its parameters. We show that, given a smooth and bounded nonconvex-nonconcave objective function, access to any proposal distribution for the min-player’s updates, and stochastic gradient oracle for the max-player, our algorithm converges to the aforementioned approximate local equilibrium in a number of iterations that does not depend on the dimension. The equilibrium point found by our algorithm depends on the proposal distribution, and when applying our algorithm to train GANs we choose the proposal distribution to be a distribution of stochastic gradients. We empirically evaluate our algorithm on challenging nonconvex-nonconcave test-functions and loss functions arising in GAN training. Our algorithm converges on these test functions and, when used to train GANs, trains stably on synthetic and real-world datasets and avoids mode collapse.