Adaptive gradient algorithms perform gradient-based updates using the history of gradients and are ubiquitous in training deep neural networks. While adaptive gradient methods theory is well understood for minimization problems, the underlying factors driving their empirical success in min-max problems such as GANs remain unclear. In this paper, we aim at bridging this gap from both theoretical and empirical perspectives. First, we analyze a variant of Optimistic Stochastic Gradient (OSG) proposed in (Daskalakis et al., 2017)  for solving a class of nonconvex non-concave min-max problem and establish O( −4 ) complexity for finding -first-order stationary point, in which the algorithm only requires invoking one stochastic first-order oracle while enjoying state-of-the-art iteration complexity achieved by stochastic extragradient method by (Iusem et al., 2017). Then we propose an adaptive variant of OSG named Optimistic Adagrad (OAdagrad) and reveal an improved adaptive complexity O − 2 1−α 1 , where α characterizes the growth rate of the cumulative stochastic gradient and 0 ≤ α ≤ 1/2. To the best of our knowledge, this is the first work for establishing adaptive complexity in nonconvex non-concave min-max optimization. Empirically, our experiments show that indeed adaptive gradient algorithms outperform their non-adaptive counterparts in GAN training. Moreover, this observation can be explained by the slow growth rate of the cumulative stochastic gradient, as observed empirically.
--------------------------
After the revisions made by the authors, my main concerns about the paper have been removed. Therefore, I am raising my score to 6 (weak accept).
--------------------------
Summary
The present work is concerned with the development of algorithms for the solution of variational inequalities in the stochastic setting, that is when the gradient computations are corrupted by noise. In this setting, the authors propose a variation of the extragradient method which they call Optimistic Stochastic Gradient (OSG), and show that by using a suitable method of variance reduction, the convergence rate of the algorithm matches the state of the art rate of convergence while relaxing the assumptions on the VI from pseudomonotone to assuming that the associated minty variational inequality has a solution. The authors furthermore introduce an adagrad-version of the same algorithm and show that improved convergence rates can be obtained depending on the growth rate of the cumulative stocastic gradients. An extensive suite of experiments studies the empirical performance of the proposed algorithms and compares them to the commonly used Adam optimizer.
Decision
In its present form, while some of the contributions of the paper seem to be relevant contributions (theoretical analysis of adagrad version, state of the art performance of optimistic mirror descent), other contributions (some of which are advertised strongly in the abstract) are incremental or implicit in earlier work (optimistic stochastic gradient descent, relaxation from pseudomonotone to minty VI). Furthermore, while the experimental part is detailed, the connection to the theory could arguably be strengthened more. I believe that by more concisely focusing the paper on its innovative aspects while relating it more directly to existing prior work, it could make for a much more valuable contribution to the literature, which is why I vote for rejecting the paper in its present form.
Additional Detail on decision
Novelty of OSG
The authors themselves note that the difference between OSG and OMD of Deskalakis et al is the inclusion of a projection step and the variance reduction by averaging multiple gradient evaluation at each iteration (which corresponds to choosing a different batch size for different iterations). I don't think these modifications are major enough to warrant "introduction of a new algorithm". The fact that all experiments seem to be conducted without constraints and constant batch size further strengthens this impression.
Relaxation to Minty VI
Another claimed improvement of the paper is relaxing the assumption of pseudomonotonicity to the mere assumption of existence of a variational inequality. However, if I'm not mistaken (please correct me if this assesment is incorrect), the only part where the pseudomonoonicity assumption enters the proof in Iusem et al is on page 36, to prove the last inequality of Equation (105). Here, however, the assumption of a Minty VI could equally be used. Thus, the weakened monotonicity assumption is not related to the use of SGO as opposed to extragradient, which is not apparent from the paper.
Suggestions for revision
I do think that the material can make for a solid paper, but I think it would strengthen rather than weaken the contribution to point out in more detail the close precursors of some of the results in the paper. Notably, rather than inventing a new algorithm (OSG), the paper proposes a way to combine variance reduction with Optimistic mirror descent of Deskalakis et al such as to achieve state of the art convergence rates which so far were only known for the variance reduced extragradient method. Furthermore, it points out that these convergence results (just as in the case of variance reduced extragradient) hold as soon as the associated Minty variational inequality holds true. This latter point would be much stronger, if examples were given that illustrate why this is a meaningful extension. Finally, the paper derives improved rates of an OAdagrad. In my opinion this point should be made more prominent by deemphasizing the part on OSG.
There is a typo in the definition of pseudomonotonicity.
Questions for authors
(1) Does figure 1 show iterations or epochs on the x axis? In order to support the theoretical claims, wouldn't it need to show the epochs on the x-axis? Otherwise, a larger batch-size simply corresponds to having access to more calls of the stochastic gradient oracle.
(2) Is there a new technical difficulty to overcome when replacing the extragradient method with the OSG compared to the proof of Iusem et al? If yes, can you give a concise description of it?
(3)It is not "evident from the definition" to me, why pseudo-monotonicity implies the existence of a solution of the Minty variational inequality, even though I believe that this is true. Could the authors explain this to me?
(4) The main improvement of OSG over extragradient lies in it needing to compute half the number of gradients per iteration. Is it possible to  explicitly compare the constants in the bounds on the convergence rates of the two algorithms? It seems that this would be required to truly make the case of a reduced complexity of OSG.