This paper considers a new variant of AMSGrad called Optimistic-AMSGrad. AMSGrad (Reddi et al. (2018)) is a popular adaptive gradient based optimization algorithm that is widely used in training deep neural networks. The new variant assumes that mini-batch gradients in consecutive iterations have some underlying structure, which makes the gradients sequentially predictable. By exploiting the predictability and some ideas from Optimistic Online learning, the proposed algorithm can accelerate the convergence and also enjoys a tighter regret bound. We evaluate Optimistic-AMSGrad and AMSGrad in terms of various performance measures (i.e., training loss, testing loss, and classification accuracy on training/testing data), which demonstrate that Optimistic-AMSGrad improves AMSGrad.
This paper proposes an online optimization method called Optimistic-AMSGrad, which combines two existing methods: (i) AMSGrad (Reddi et al 2018) and (ii) optimistic online learning where the prediction step is done with the extrapolation algorithm by Scieur et al 2016. The authors do a good job of presenting the method (by introducing the background in proper order), the paper seems self-contained and cites the relevant literature. The regret analysis of the proposed algorithm is provided, where the obtained regret can be smaller than AMSGrad depending on whether or not the guess of the gradient and the gradient are close.
In my opinion the boundedness assumption (footnote 2) is quite important here, and should be mentioned in the main text. 
It is not clear how the different ways of accelerations combined in this method interact when the guess is not good. In other words, if the guess is not good this method could be slower then AMSGrad. Moreover, AMSGrad has stability property allowed from the ratio between 1st and 2nd moment estimate. In Optimistic-AMSGrad if m_t is bad, obtaining next w_{t+1} (line 9) would include ratio between outdated/bad 1st mom. estimate and new 2nd-moment estimate. In short, the method’s stability and outperformance might rely on the selection of the algorithm for gradient prediction.
In my understanding, extragradient has clear advantages in games, as if considering simple bilinear examples it is the only method that converges. However, for a single objective, its advantages are not clear to me (after reading the paper). Thus, I think it would be useful if the authors could provide comparison over *wall clock time* as well as long-run comparisons when the compared methods converge (it would be interesting to see if Optimistic-AMSGrad obtains better final train/test accuracy?). In many of the experiments where Opt-AMSGrad outperforms, the accuracy of the baseline still goes up--whereas the latter is computationally cheaper, so it is not clear from the provided results why a practitioner should use this method.
Moreover, the experimental results would be much more convincing if the authors do multiple runs using different seeds and present mean and standard deviation of the methods.
In the context of games, using more computationally demanding optimizers makes sense as training is unstable. In this case, after reading the paper, it is not clear to me what is the problem that the proposed method solves (or its advantages). Indeed, its advantage depends on how good the guess of g_{t+1} is. However, the extra-computation cost to obtain a good guess needs to be justified, or proven empirically that gets better performances faster (wall-clock time), or final ones.
In summary: (i)  the paper is well-presented and provides hyperparameter sensitivity results; (ii) the paper is very interesting, but (imo) it should leave clearer message why one should use this method; (iii) the proposed method has tighter regret, but only in some (data-dependent) cases and combines existing methods, limiting novelty. Hence, given the pros and cons, I am not confident recommending acceptance, and I think improved experimental results (error bars & wall-clock, see above) would make the results more significant.
--- Minor ---
- Alg.2: maybe add input hyperparameter r to optimistic-AMSGrad and a line between lines 8-9 that calls function which obtains the guess m_{t+1} (r should be passed to it). It would make it more clear that your algorithm has parameter r (sec. D.2)
- I could be wrong, but in my opinion, using \theta as first moment est. is slightly confusing, as it is normally used to denote parameters; similarly, the authors could use hat/prime on top of a variable to denote the ‘guess’ of that same variable, making it easier to follow.
- maybe add init of \theta_0 in alg1&2
- if I am correct amsgrad also does bias correction of the initial values of 1st and 2nd moment estimates; if that’s the case it could be useful adding a note that this is omitted for clarity if a reader implements it
- pg2: we just would like -> we would like