  The optimization problems associated with training generative adversarial
neural networks can be largely reduced to certain {\em non-monotone}
variational inequality problems (VIPs), whereas existing convergence results
are mostly based on monotone or strongly monotone assumptions. In this paper,
we propose {\em optimistic dual extrapolation (OptDE)}, a method that only
performs {\em one} gradient evaluation per iteration. We show that OptDE is
provably convergent to {\em a strong solution} under different coherent
non-monotone assumptions. In particular, when a {\em weak solution} exists, the
convergence rate of our method is $O(1/{\epsilon^{2}})$, which matches the best
existing result of the methods with two gradient evaluations. Further, when a
{\em $\sigma$-weak solution} exists, the convergence guarantee is improved to
the linear rate $O(\log\frac{1}{\epsilon})$. Along the way--as a byproduct of
our inquiries into non-monotone variational inequalities--we provide the
near-optimal $O\big(\frac{1}{\epsilon}\log \frac{1}{\epsilon}\big)$ convergence
guarantee in terms of restricted strong merit function for monotone variational
inequalities. We also show how our results can be naturally generalized to the
stochastic setting, and obtain corresponding new convergence results. Taken
together, our results contribute to the broad landscape of variational
inequality--both non-monotone and monotone alike--by providing a novel and more
practical algorithm with the state-of-the-art convergence guarantees.
