Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper proposes to use optimistic gradient descent (OGD) for GAN training. Optimistic mirror descent is know to yield fast convergence for finding the optimum of zero-sum convex-concave games (when the players collaborate for fast computation), but earlier results concern the performance of the average iterate. This paper extends this result by showing that the last iterate of OGD also provides a good estimate of the value of bilinear games. Based on this new theoretical result (which is not unexpected but is certainly nice), the authors propose to use stochastic OGD in GAN training. Their experiments show that this new approach avoids the cycling behavior observed with SGD and its variants, and provides promising results in GAN training. (Extensive experiments show the cycling behavior of SGD variants in very simple problems, and some theoretical result is also provided when SGD diverges in solving a simple min-max game).

The paper is clearly written and easy to follow; in fact I quite enjoyed reading it. I have not checked all the details of the proofs, but they seem plausible.
All in all, this is a very nice paper.

Some questions/comments:
- Proposition 1: Could you show a similar example when you can prove the oscillating behavior?
- Theorem 1: It would be interesting to write out the convergence rate of Delta_t, which could be used to optimize eta. Also, my understanding is that you actually avoid computing gamma, hence tuning eta is not straightforward. Alternatively, you could also use an adaptive OGD to automatically tune eta (see, e.g., Joulani et al, "A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, and variational Bounds," ALT 2017). The non-adaptive selection of eta might be the reason that your method does not outperform adagrad SGD in 5 (b), although it is true that the behavior of your method seems quite stable for different learning rates).
- LHS of the second line of (6) should be theta.
- Below (6): \mathcal{R}(A) is only defined in the appendix.
review_title: Nice paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a simple modification of standard gradient descent -- called “Optimistic Mirror Descent” -- which is claimed to improve the convergence of GANs and other minimax optimization problems.  It includes experiments in toy settings which build intuition for the proposed algorithm, as well as in a practical GAN setting demonstrating the potential real-world benefits of the method.


Pros

Section 3 directly compares the learning dynamics of GD vs. OMD for a WGAN in a simple toy setting, showing that the default GD algorithm oscillates around the optimum in the limit while OMD’s converges to the optimum.

Section 4 demonstrates the convergence of OMD for a linear minimax optimization problem. (I did not thoroughly verify the proof’s correctness.)

Section 6 proposes an OMD-like modification of Adam which achieves better results than standard Adam in a practical GAN setting (WGANs trained on CIFAR10) .


Cons/Suggestions

The paper could use a good deal of proofreading/revision for clarity and correctness. A couple examples from section 2:
- “If the discriminator is very powerful and learns to accurately classify all samples, then the problem of the generator amounts to solving the Jensen-Shannon divergence between the true distribution and the generators distribution.” -> It would be clearer to say “minimizing” (rather than “solving”) the JS divergence. (“Solving” sounds more like what the discriminator does.)
- “Wasserstein GANs (WGANs) Arjovsky et al. (2017), where the discriminator rather than being treated as a classifier is instead trying to simulate the Wasserstein−1 or earth-mover metric” -> Instead of “simulate”, “estimate” or “approximate” would be better word choices.  And although the standard GAN discriminator is a binary classifier, when optimized to convergence, it’s also estimating a divergence -- the JS divergence (or a shifted and scaled version of it).  Even though the previous paragraph mentions this, it feels a bit misleading to characterize WGANs as doing something fundamentally different.

Sec 2.1: There are several non-trivial but uncited mathematical claims hidden behind “well-known” or similar descriptors. These results could indeed be well-known in certain circles, but I’m not familiar with them, and I suspect most readers won’t be either. Please add citations. A few examples:
- “If the loss function L(θ, w) ..., then standard results in game theory and no-regret learning imply that…”
- “In particular, it is well known that GD is equivalent to the Follow-the-Regularized-Leader algorithm with an L2 regularizer...”
- “It is known that if the learner knew in advance the gradient at the next iteration...” 

Section 4: vectors “b” and “c” are included in the objective written in (14), but are later dropped without explanation.  (The constant “d” is also dropped but clearly has no effect on the optimization.)


Overall, the paper could use revision but the proposed approach is simple and seems to be theoretically well-motivated with solid analysis and benefits demonstrated in real-world settings.
review_title: -

final_score: rating: 7: Good paper, accept
review_content: This paper proposes the use of optimistic mirror descent to train Wasserstein Generative Adversarial Networks (WGANS). The authors remark that the current training of GANs, which amounts to solving a zero-sum game between a generator and discriminator, is often unstable, and they argue that one source of instability is due to limit cycles, which can occur for FTRL-based algorithms even in convex-concave zero-sum games. Motivated by recent results that use Optimistic Mirror Descent  (OMD) to achieve faster convergence rates (than standard gradient descent) in convex-concave zero-sum games and normal form games, they suggest using these techniques for WGAN training as well. The authors prove that, using OMD, the last iterate converges to an equilibrium and use this as motivation that OMD methods should be more stable for WGAN training. They then compare OMD against GD on both toy simulations and a DNA sequence task before finally introducing an adaptive generalization of OMD, Optimistic Adam, that they test on CIFAR10. 

This paper is relatively well-written and clear, and the authors do a good job of introducing the problem of GAN training instability as well as the OMD algorithm, in particular highlighting its differences with standard gradient descent as well as discussing existing work that has applied it to zero-sum games. Given the recent work on OMD for zero-sum and normal form games, it is natural to study its effectiveness in training GANs.The issue of last iterate versus average iterate for non convex-concave problems is also presented well.  

The theoretical result on last-iterate convergence of OMD for bilinear games is interesting, but somewhat wanting as it does not provide an explicit convergence rate as in Rakhlin and Sridharan, 2013. Moreover, the result is only at best a motivation for using OMD in WGAN training since the WGAN optimization problem is not a bilinear game. 

The experimental results seem to indicate that OMD is at least roughly competitive with GD-based methods, although they seem less compelling than the prior discussion in the paper would suggest. In particular, they are matched by SGD with momentum when evaluated by last epoch performance (albeit while being less sensitive to learning rates). OMD does seem to outperform SGD-based methods when using the lowest discriminator loss, but there doesn't seem to be even an attempt at explaining this in the paper. 

I found it a bit odd that Adam was not used as a point of comparison in Section 5, that optimistic Adam was only introduced and tested for CIFAR but not for the DNA sequence problem, and that the discriminator was trained for 5 iterations in Section 5 but only once in Section 6, despite the fact that the reasoning provided in Section 6 seems like it would have also applied for Section 5. This gives the impression that the experimental results might have been at least slightly "gamed". 

For the reasons above, I give the paper high marks on clarity, and slightly above average marks on originality, significance, and quality.

Specific comments:
Page 1, "no-regret dynamics in zero-sum games can very often lead to limit cycles": I don't think limit cycles are actually ever formally defined in the entire paper.  
Page 3, "standard results in game theory and no-regret learning": These results should be either proven or cited.
Page 3: Don't the parameter spaces need to be bounded for these convergence results to hold? 
Page 4, "it is well known that GD is equivalent to the Follow-the-Regularized-Leader algorithm": For completeness, this should probably either be (quickly) proven or a reference should be provided.
Page 5, "the unique equilibrium of the above game is...for the discriminator to choose w=0": Why is w=0 necessary here?
Page 6, "We remark that the set of equilibrium solutions of this minimax problem are pairs (x,y) such that x is in the null space of A^T and y is in the null space of A": Why is this true? This should either be proven or cited.
Page 6, Initialization and Theorem 1: It would be good to discuss the necessity of this particular choice of initialization for the theoretical result. In the Initialization section, it appears simply to be out of convenience.
Page 6, Theorem 1: It should be explicitly stated that this result doesn't provide a convergence rate, in contrast to the existing OMD results cited in the paper.   
Page 7, "we considered momentum, Nesterov momentum and AdaGrad": Why isn't Adam used in this section if it is used in  later experiments?
Page 7-8, "When evaluated by....the lowest discriminator loss on the validation set, WGAN trained with Stochastic OMD (SOMD) achieved significantly lower KL divergence than the competing SGD variants.": Can you explain why SOMD outperforms the other methods when using the lowest discriminator loss on the validation set? None of the theoretical arguments presented earlier in the paper seem to even hint at this. The only result that one might expect from the earlier discussion and results is that SOMD would outperform the other methods when evaluating by the last epoch. However, this doesn't even really hold, since there exist learning rates in which SGD with momentum matches the performance of SOMD.
Page 8, "Evaluated by the last epoch, SOMD is much less sensitive to the choice of learning rate than the SGD variants": Learning rate sensitivity doesn't seem to be touched upon in the earlier discussion. Can these results be explained by theory?
Page 8, "we see that optimistic Adam achieves high numbers of inception scores after very few epochs of training": These results don't mean much without error bars.
Page 8, "we only trained the discriminator once after one iteration of generator training. The latter is inline with the intuition behind the use of optimism....": Why didn't this logic apply to the previous section on DNA sequences, where the discriminator was trained multiple times?


After reading the response of the authors (in particular their clarification of some technical results and the extra experiments they carried out during the rebuttal period), I have decided to upgrade my rating of the paper from a 6 to a 7. Just as a note, Figure 3b is now very difficult to read. 


review_title: Natural and interesting work with some questionable experimental results 

Meta-review: The reviewers thought the paper provides an interesting line of research.
Decision: Accept (Poster)