Optimistic Mirror Descent in Saddle-Point Problems: Going the Extra (Gradient) Mile
Owing to their connection with generative adversarial networks (GANs), saddlepoint problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convexconcave (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 provable 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, and the CelebA and CIFAR-10 datasets).
This work provides the converge proof of the last iterates of two stochastic methods (almost surely) that the author called  mirror descent and optimistic mirror descent under an assumption weaker than monotonicity called coherence. 
Roughly, the definition of coherence is the equivalence between being a  saddle point and the solution of the Minty variational inequality. 
Overall, I think that this paper try to tackle an interesting problem which is to prove convergence of saddle point algorithms under weaker assumption than monotonicity of the operator.
However, I have some concerns: 
- I think that the properties of coherent saddle point could be more investigated. For instance is the set of coherent saddle point connected ? It would be very relevant for GANs. You claim that "neither strict, nor null coherence imply a unique solution to (SP)," but I do not see any proof of that statement (both provided examples have a unique SP). I agree that you can set $g$ to $0$ in some directions to get an affine space a of saddle points but is there examples where the set of solution is not an affine space (intersected with the constraints) ? 
- First of all the results are only asymptotic. (I agree that it can be mitigated saying that there is (almost) no results on non-monotone VI and it is a first step to try to handle non-convexity of the objective functions.)
- One big pro of this work might have been new proof techniques to handle non-monotonicity in variational inequalities but the coherence assumption looks like to be the weakest condition to use the standard proof technique of convergence of the (MD) and (OMD). Nevertheless, this work is still interesting since it handles in a subtle way stochasticity (I did not have time to check Theorem 2.18 [Hall & Heyde 1980], I would be good to repeat it in the appendix for self-completeness)
- This work could be easily extended to non zero-sum games which is crucial in practice since most of the state of the art GANs (such as WGAN with gradient penalty or non saturating GAN) are non zero-sum games. 
- Are you sure of the use of the denomination Optimistic mirror descent ? What you are presenting is the extragradient method. These two methods are slightly different, If you look at (5) in (Daskalaki et al., 2018) you'll notice that the updates are slightly different from you (OMD), particularly (OMD) require two gradient computations per iteration whereas (5) in (Daskalaki et al., 2018) requires only one. (it just requires to memorize the previous gradient)
Minor comment: 
- For saddle point (and more generally variational inequalities) Mirror descent is no longer a descent algorithm. The name used by the literature is mirror-prox method (see Juditsky's paper) 
- in (C.1) U_n is not defined anywhere but I guess it is $\hat g_n - g(X_n)$.
- Some cited paper are published paper but cited as arXiv paper. 
- Lemma D.1 could be extended to the case (\sigma \neq 0) but the additional noise term might be hard to handle to get a result similar as Thm 4.1
for $\sigma \neq 0$.