Although ADAM is a very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex optimization examples. Several variants of ADAM have been proposed to circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonconvex optimization under a boundedness assumption on the adaptive learning rate. The bound on the adaptive step size depends on the Lipschitz constant of the gradient of the objective function and provides safe theoretical adaptive step sizes. Under this boundedness assumption, we show a novel first order convergence rate result in both deterministic and stochastic contexts. Furthermore, we establish convergence rates of the function value sequence using the Kurdyka-Łojasiewicz property.
In this work, the authors consider a variation of ADAM with a boundedness assumption on the step size and focus on unconstrained, smooth, non-convex minimization setting.
The authors provide non-asymptotic convergence rates for deterministic and stochastic settings, with respect to the gradient norm. Moreover, they also prove convergence in function value for a class of functions that satisfy Kurdyka-Lojasiewicz (KL) property. To the best of my knowledge, this is the first work that utilizes KL property and respective analysis for ADAM-like methods. I have to note that I disagree with your statement of being “adaptive”.
I summarize my comments step by step below:
I find the presentation and organization of the paper clear and structured. Related work is sufficient, the authors cite relevant papers with respect to convergence in deterministic and stochastic setting and present detailed comparison between their framework. Similarly, the momentum idea is motivated through Polyak’s Heavy ball. The known rates for KL functions are provided in conjunction with momentum-based methods.
Zaheer et al. (2018) assume \beta_1 = 0, meaning their proof works for RMSProp. However for this paper, given that Theorems 4.2 and 4.3 are provided for Algorithm (2), then the algorithm in question is not exactly the same as ADAM either, in my opinion. The bias correction steps are missing. The authors should clarify this point in the paper.
Definition of adaptivity is a little vague for me. There exist different notions of adaptivity (adaptation to global/local smoothness without knowing L, adaptation to non-smooth & smooth problems simultaneously etc.) The authors define adaptivity as “computing step size using gradient history”. However, their upper bound for the step size requires knowledge of L. Also, they assume a uniform lower bound for step size. These make their framework rather non-adaptive in my opinion.
Follow up comment: How would one apply this method to neural networks, or any class of problems where Lipschitz constant is virtually unknown?
Convergence rate in deterministic oracle setting, provided in Theorem 4.2, is plausible. The proof is nice and easy to read. Compared to De et al., the authors show faster rates with respect to number of iterations. But the rate depends on upper/lower bounds of the step size.
Convergence rates in the stochastic setting suggest the quantity does not go to zero, but converges to some noise dominated region (equivalently to some neighborhood) of stationary points. Zaheer et al. has a similar rate characterization for RMSProp, but this paper considers first order moment accumulation on top Zaheer et al. I am not sure about the impact of this results compared to existing ones for ADAM variants. Similar to deterministic case, the analysis is nice and clean. The rate has no dependence on dimension, but so does the analysis of De et al. (2018) and Zaheer et al. (2018). It is not new, but it is a desirable property of the analysis.
I have doubts about “not having bounded gradient assumption”. There exists a uniform lower bound for a_n, which implies the sum of square of each coordinate of gradients are bounded, which implies the infinity norm of gradients is bounded. I believe there is an implicit assumption of bounded gradients. It also makes me question if somehow the dimension dependence is hidden under this step size lower bound. I would expect the authors to address the concerns about bounded gradient and dimension dependence.
Convergence characterization for KL functions with (sort of) adaptive step size is new also to the best of my knowledge. The convergence analysis is based on PALM (Bolte et al. (2014)) and Bolte et al. (2018) and these previous results are adapted to ADAM. My concern about this direction is whether neural networks belong to this class of functions. If not, how useful it is to use ADAM for this class of functions?
Overall, authors approach ADAM-like methods from a generalized scheme based on Heavy Ball, and provide analysis for smooth, non-convex functions with deterministic/stochastic gradients. Having dimension-independent rates is a positive trait of the analysis, but I would like to see a clarification regarding my previous point. In the stochastic setting, dimension-free rate for ADAM (which has very similar characterization to RMSProp in Zaheer et al.) seems to be an important results of this paper. I think the KL function analysis is a new result for “adaptive”, evolving step sizes, as well. However, I do not agree with the claim that the authors do not make bounded gradient assumption. In a way, the uniform lower bound on the step size implies it. Knowledge of Lipschitz constant (through step size upper bound) is a restriction for “highly non-convex” neural network optimization problems. Considering that ADAM is a classical optimizer for neural networks, I also doubt KL property holds for complex networks. Also, I am not convinced that the algorithm is truly adaptive (upper bounding step size with a function of Lipschitz constant.) 
I am inclined to give a weak reject to this paper because I am not convinced that the results presented in the paper are compatible with the application. I would also like to see the justification/clarification of the authors for my previous concerns before making the final decision.