Newton-type Methods for Minimax Optimization
This work addresses a bottleneck in machine learning applications such as adversarial training and GANs by providing efficient algorithms for nonconvex-nonconcave settings, though it is incremental relative to existing convex-concave theory.
The authors tackled nonconvex-nonconcave minimax optimization by proposing two novel Newton-type algorithms, proving local convergence at strict local minimax points and demonstrating faster convergence and effectiveness on ill-conditioned problems like GAN training.
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.