We consider new variants of optimization algorithms. Our algorithms are based on the observation that mini-batch of stochastic gradients in consecutive iterations do not change drastically and consequently may be predictable. Inspired by the similar setting in online learning literature called OPTI-MISTIC ONLINE LEARNING, we propose two new optimistic algorithms for AMSGrad and Adam, respectively, by exploiting the predictability of gradients. The new algorithms combine the idea of momentum method, adaptive gradient method, and algorithms in OPTIMISTIC ONLINE LEARNING, which leads to speed up in training deep neural nets in practice.
The paper proposes new online optimization algorithms by adding the idea of optimistic updates to the already popular components of adaptive preconditioning and momentum (as used in AMSGrad and ADAM). Such optimistic schemes attempt to guess the yet-unseen gradients before each update, which can lead to better regret guarantees when the guesses are accurate in a certain sense. This in turn can lead to faster convergence when the resulting algorithm is used in an optimization framework. The specific contribution of the present paper is proving formally that optimistic updates can indeed be combined with advanced methods like ADAM and AMSGrad, also providing a regret analysis of the former algorithm. On the practical front, the authors also propose a method closely resembling Anderson acceleration for guessing the next gradient, and the eventual scheme is shown to work well empirically in training deep neural networks.
The idea of optimistic updates has been popular in recent years within the online-learning literature, and has been used with particularly great success for achieving improved convergence guarantees for learning equilibria in games. More recently, optimistic updates have also appeared in more "practical" settings such as training GANs, where they were shown to improve stability of training. The present paper argues that the idea of optimism can be useful for large-scale optimization as well, if the gradient guesses are chosen appropriately.
I have lukewarm feelings about the paper. On the positive side, the proposed method is a natural and sensible combination of solid technical ideas, and its theoretical analysis appears to be correct. As the authors point out, their algorithm incorporates the idea of optimism in a much more natural way than the related optimistic ADAM algorithm previously proposed by Daskalakis et al. (2018) does. The experiments also indicate some advantage of optimism in the studied optimization problems.
On the other hand, the theoretical contribution is marginal: the algorithm and its analysis is a straightforward combination of previous ideas and the result itself doesn't strike me as surprising at all. Then again, perhaps this is more of a presentation issue, as it may be the case that the authors did not manage to highlight clearly enough the technical challenges they needed to overcome to prove their theoretical results. Furthermore, I find the method for guessing the gradients to be rather arbitrary and poorly explained---at least I'm not sure if anyone unfamiliar with the mentioned gradient extrapolation methods would find this approach to be sensible at all.
I am not fully convinced by the experimental results either, since I have an impression that the gradient-guessing method only introduces yet another knob to turn when tuning the hyperparameters, and it's not clear at all that this new dimension would indeed unlock levels of performance that were not attainable before. Indeed, the authors seem to fix all hyperparameters across all experiments and only switch around the optimistic components, rather than finding the best tuning for each individual algorithm and comparing the respective results. Also, I don't really see any qualitative improvements in the learning curves due to the new components---but maybe I just can't read these graphs properly since I have more of a "theorist" background.
The writing is mostly OK, although there is room for improvement in terms of English use (especially on the front of articles which seem to be off in almost every sentence).
Overall, I don't feel very comfortable about suggesting acceptance, mostly because I find the results to be rather unsurprising. I suggest that the authors try to convince me of the nontrivial challenges arising in the analysis, or about the definite practical advantage that optimism can buy for large-scale optimization.
Detailed comments
=================
- pp.1, abstract: "We consider new variants of optimization algorithms."---This sentence is rather vague and generic. I guess you wanted to refer to *convex* optimization algorithms, which is actually what you consider in the paper. No need to be embarrassed about assuming convexity...
- pp.1: A general nuisance with the typesetting that already shows on the first page is that italic and small capital fonts are used excessively and without any clearly identifiable logic. Please simplify.
- pp.1: "AdaGrad [...] exploits the geometry of the data and performs informative update"---this makes it sound like other algorithms make non-informative updates.
- pp.1: Regret was not defined even informally in the introduction, yet already some regret bounds are compared, highlighting that one "can be much smaller than O(\sqrt{T})". This is not very friendly for readers with no prior experience in online learning.
- pp.1: "Their regret analysis are the regret analysis in online learning."---What is this sentence trying to say?
- pp.2: For this discussion of FTRL, it would be useful to remark that this algorithm really only makes sense if the loss function is convex. Also related to this discussion: you mention that the bound for optimistic FTRL can be much smaller than \sqrt{T}, but never actually say that \sqrt{T} is minimax optimal---without this piece of context, this statement has little value.
- pp.3: "ADAM [...] does not converge to some specific convex functions."---I guess I understand what this sentence is trying to say, but it certainly doesn't say it right. (Why would an *algorithm* converge to a *function*?)
- pp.3, bottom: This description of "extrapolation methods" is utterly cryptic. What is x_t here? What is the "fixed point x^*"? Why is this scheme applicable at all here? (Why would one believe the errors to be near-linear in this case? Would this argument work at all for non-convex objectives?)
- pp.5, Lemma 1: Why would one expect D_\infty to be finite? In order to ensure this, one would need to project the iterates to a compact set.
- pp.5, right after lemma 1: "it does matter how g_t is generated" -> "it does *not* matter how g_t is generated"
- pp.6, top: "we claimed that it is smaller than O(\sqrt{T}) so that we are good here"---where exactly did this claim appear, and in what sense "are we good here"? Also, the norms in this paragraph should be squared.
- pp.6, Sec 3.2: While this section makes some interesting points, its tone feels a bit too apologetic. E.g., saying that "[you] are aware of" a previous algorithm that's similar to yours and doubling down on the claim that "the goals are different" makes the text feel like you're taking a defensive stance even though I can't see a clear reason for this. In my book, the approach you propose is clearly different and more natural for the purpose of your study.