Before revision: We present a first-order algorithm for nonconvex-nonconcave min-max optimization problems such as those that arise in training GANs . Our algorithm provably converges in time polynomial in the dimension and smoothness parameters of the loss function . To achieve convergence, we 1) give a novel approximation to the global strategy of the max-player based on first-order algorithms such as gradient ascent, and 2) empower the min-player to look ahead and simulate the max-player's response for arbitrarily many steps, but restrict the min-player to move according to updates sampled from a stochastic gradient oracle. Our algorithm, when used to train GANs on synthetic and real-world datasets, does not cycle, results in GANs that seem to avoid mode collapse, and achieves a training time per iteration and memory requirement similar to gradient descent-ascent  .
After revision: We present a first-order algorithm for nonconvex-nonconcave min-max optimization problems such as those that arise in training GANs . Our algorithm provably converges in time polynomial in the dimension and smoothness parameters of the loss function and independent of the dimension, and allows for loss functions that can be nonconvex and nonconcave in the parameters of the generator and discriminator. Empirically, GANs trained using our algorithm consistently learn a greater number of modes than gradient descent-ascent .