ON THE CONVERGENCE OF A CLASS OF ADAM-TYPE ALGORITHMS FOR NON-CONVEX OPTIMIZATION
This paper studies a class of adaptive gradient based momentum algorithms that update the search directions and learning rates simultaneously using past gradients. This class, which we refer to as the "Adam-type", includes the popular algorithms such as Adam (Kingma & Ba, 2014)  , AMSGrad (Reddi et al., 2018)  , AdaGrad (Duchi et al., 2011). Despite their popularity in training deep neural networks (DNNs), the convergence of these algorithms for solving non-convex problems remains an open question. In this paper, we develop an analysis framework and a set of mild sufficient conditions that guarantee the convergence of the Adam-type methods, with a convergence rate of order O(log T / √ T ) for non-convex stochastic optimization. Our convergence analysis applies to a new algorithm called AdaFom (AdaGrad with First Order Momentum). We show that the conditions are essential, by identifying concrete examples in which violating the conditions makes an algorithm diverge. Besides providing one of the first comprehensive analysis for Adam-type methods in the non-convex setting, our results can also help the practitioners to easily monitor the progress of algorithms and determine their convergence behavior.
Summary:
This paper presents a convergence analysis in the non-convex setting for a family of optimization algorithms, which the authors call the "Adam-type". This family incorporates popular existing methods like Adam, AdaGrad and AMSGrad. The analysis relies only on standard assumptions like Lipschitz smoothness and bounded gradients.
Individual Comments/Questions:
- In Table 1, the characterization of Adam ignores the fact that, in practice, Adam adds a positive epsilon to the $\hat{v}_t$ in the denominator. I would like the authors to at least comment on that in the paper. I assume that AdaFom and AMSGrad also need such an epsilon in practice. Could the author comment on whether (and how) this would affect their analysis of those methods? In particular, in Theorem 3.1, can we really assume the term $\Vert \alpha_t m_t / \sqrt{\hat{v}_t} \Vert$ to be bounded by a constant without such an epsilon?
- In the first bullet point in Section 3.1, the authors relate the term
$$ \sum_t \Vert \alpha_t g_t / \sqrt{\hat{v}_t} \Vert^2 $$ (*)
to the term $\sum_t \alpha_t^2$ in the analysis of SGD. I don't think this is a fair analogy. The effective step size of Adam-type methods is $\alpha_t / \sqrt{\hat{v}_t}$, while the aformentioned term also contains the magnitude of the stochastic gradient $g_t$. So, while the SGD analysis only poses a condition on the step sizes, bounding (1) also poses a condition on the magnitude of the stochastic gradient.
- In the experiments of Section 3.2.1, the authors use a step size of 0.01 for SGD (which really is gradient descent, since this is a non-stochastic problem). Existing theory tells us that GD only converges for step sizes smaller than 2/L where L is the Lipschitz constant of the gradient, which is L=200 in this example. So this is literally setting the method up for failure and I don't really see any merit in that experiment.
- The experiments in Section 4 are of course very limited, but this paper makes a significant theoretical contribution, so I don't really see the need for extensive experiments.
- To my knowledge, under similar assumptions, plain SGD has been show to converge at a rate of O(1/sqrt(T)). The convergence analysis presented here has an additional log(T) factor, so it is not really suitable to explain any possible benefits of these adaptive methods over SGD. This is totally fine in and of itself; after all the analysis of theses methods is hard and this is a great first step. The issue I have is that this is not mentioned in the paper at all. 
Originality:
To the best of my knowledge, the convergence analysis of the Adam-type methods (including established methods AdaGrad, RMSprop, Adam, AMSGrad) in the _non-convex_ setting is a novel, original contribution. The authors also propose a new algorithm, AdaFom. This exact algorithm is proposed in [1], which was uploaded to arXiv before the ICLR deadline. However, this can be considered concurrent work.
Significance:
The convergence properties of popular optimization methods in machine learning (e.g., Adam) are generally very poorly understood in "realistic" settings. The analysis presented in this paper is an important step to better theoretical understanding of these methods which, in my opinion, is highly significant.
Correctness:
This was a short-notice emergency review and I did not check any of the proofs in the appendix. I will try to verify at least parts of the proofs in the coming days.
Conclusion:
This is an original paper making a significant theoretical contribution. I can't comment on the correctness of the mathematical analysis (yet). I'm cautiously recommending acceptance for now, but would be willing to upgrade my rating if the authors respond to my comments/questions.
[1] Zou and Shen. On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks. https://arxiv.org/abs/1808.03408.
--------------------------------
Update
--------------------------------
The authors have provided a detailed response to my concerns and have fixed many of them in their revised version. I verified parts of the proofs in the appendix (Theorem 3.1 and its Corollaries). I congratulate the authors on their work and recommend acceptance!