Title: Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile,
Abstract: Owing to their connection with generative adversarial networks (GANs),
saddle-point problems have recently attracted considerable interest in machine
learning and beyond. By necessity, most theoretical guarantees revolve around
convex-concave (or even linear) problems; however, making theoretical inroads
towards efficient GAN training depends crucially on moving beyond this classic
framework. To make piecemeal progress along these lines, we analyze the
behavior of mirror descent (MD) in a class of non-monotone problems whose
solutions coincide with those of a naturally associated variational inequality
- a property which we call coherence. We first show that ordinary, "vanilla" MD
converges under a strict version of this condition, but not otherwise; in
particular, it may fail to converge even in bilinear models with a unique
solution. We then show that this deficiency is mitigated by optimism: by taking
an "extra-gradient" step, optimistic mirror descent (OMD) converges in all
coherent problems. Our analysis generalizes and extends the results of
Daskalakis et al. (2018) for optimistic gradient descent (OGD) in bilinear
problems, and makes concrete headway for establishing convergence beyond
convex-concave games. We also provide stochastic analogues of these results,
and we validate our analysis by numerical experiments in a wide array of GAN
models (including Gaussian mixture models, as well as the CelebA and CIFAR-10
datasets).