Submitted on 25 Jun 2020
Newton-type Methods for Minimax Optimization
Guojun Zhang, Kaiwen Wu, Pascal Poupart, Yaoliang Yu
Differential games, in particular two-player sequential zero-sum games
(a.k.a. minimax optimization), have been an important modeling tool in applied
science and received renewed interest in machine learning due to many recent
applications, such as adversarial training, generative models and reinforcement
learning. However, existing theory mostly focuses on convex-concave functions
with few exceptions. In this work, we propose two novel Newton-type algorithms
for nonconvex-nonconcave minimax optimization. We prove their local convergence
at strict local minimax points, which are surrogates of global solutions. We
argue that our Newton-type algorithms nicely complement existing ones in that
(a) they converge faster to strict local minimax points; (b) they are much more
effective when the problem is ill-conditioned; (c) their computational
complexity remains similar. We verify the effectiveness of our Newton-type
algorithms through experiments on training GANs which are intrinsically
nonconvex and ill-conditioned. Our code is available at
https://github.com/watml/min-max-2nd-order.
https://arxiv.org/abs/2006.14592