Title: CONVERGENCE ANALYSIS OF A MOMENTUM ALGORITHM WITH ADAPTIVE STEP SIZE FOR NONCONVEX OPTIMIZATION Anonymous

Abstract: 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.

1. INTRODUCTION:

Consider the unconstrained optimization problem

EQUATION

where f : R d → R is a differentiable map and d is an integer. Gradient descent is one of the most classical algorithms to solve this problem. Since the seminal work Robbins and Monro (1951) , its stochastic counterpart became one of the most popular algorithms to solve machine learning problems (see Bottou et al. (2018) for a recent survey). Recently, a class of algorithms called adaptive algorithms which are variants of stochastic gradient descent became very popular in machine learning applications. Using a coordinate-wise step size computed using past gradient information, the step size is adapted to the function to optimize and does not follow a predetermined step size schedule. Among these adaptive algorithms, ADAM (Kingma and Ba, 2015) is very popular for optimizing the weights of neural networks. However, recently, Reddi et al. (2018) exhibited a simple convex stochastic optimization problem over a compact set where ADAM fails to converge because of its short-term gradient memory. Moreover, they proposed an algorithm called AMSGRAD to fix the convergence issue of ADAM . This work opened the way to the emergence of other variants of ADAM to overcome its convergence issues (see Section 3 for a detailed review). In this work, under a bounded step size assumption, we propose a theoretical analysis of ADAM for nonconvex optimization.

Contributions.

• We establish a convergence rate for ADAM in the deterministic case for nonconvex optimization under a bounded step size. This algorithm can be seen as a deterministic clipped version of ADAM which guarantees safe theoretical step sizes. More precisely, we show a O(1/n) convergence rate by introducing a suitable Lyapunov function. • We show a similar convergence result to Zaheer et al. (2018, Thm. 1) for nonconvex stochastic optimization up to the limit of the variance of stochastic gradients under an almost surely bounded step size. In comparison to the literature, we relax the hypothesis of the boundedness of the gradients. We also improve the dependency of the convergence result on the dimension d of the parameters.

• We propose a convergence rate analysis of the objective function of the algorithm using the Kurdyka-Łojasiewicz (KŁ) property. To the best of our knowledge, this is the first time such a result is established for an adaptive optimization algorithm.

2. A MOMENTUM ALGORITHM WITH ADAPTIVE STEP SIZE:

Notations. All operations between vectors of R d are to read coordinatewise. The vector of ones of R d is denoted by 1. When a scalar is added to a vector, it is added to each one of its coordinates.

Inequalities are also to be read coordinatewise. If x ∈ R d , x ≤ λ ∈ R means that each coordinate of x is smaller than λ.

We investigate the following algorithm defined by two sequences (x n ) and (p n ) in R d :

EQUATION

where ∇f (x) is the gradient of f at point x, (a n ) is a sequence of vectors in R d with positive coordinates, b is a positive real constant and x 0 , p 0 ∈ R d .

Algorithm (2) includes the classical Heavy-ball method as a special case, but is much more general. Indeed, we allow the sequence of step sizes (a n ) to be adaptive : a n ∈ R d may depend on the past gradients g k := ∇f (x k ) and the iterates x k for k ≤ n. We stress that the step size a n is a vector of R d and that the product a n+1 p n+1 in ( 2) is read componentwise (this is equivalent to the formulation with a diagonal matrix preconditioner applied to the gradient (McMahan and Streeter, 2010; Gupta et al., 2017; Agarwal et al., 2019) ). We present in the following table how to recover some of the famous algorithms with a vector step size formulation:

Algorithm:

Effective step size a n+1 Momentum SGD (Robbins and Monro, 1985) a n+1 ≡ a b = 1 (no momentum) ADAGRAD (Duchi et al., 2011 ) Tieleman and Hinton, 2012 ) Kingma and Ba, 2015 )

a n+1 = a n i=0 g 2 i -1/2 b = 1 RMSPROP (

a n+1 = a + c n i=0 (1 -c) n-i g 2 i 1/2 -1 b = 1 ADAM (

a n+1 = a + c n i=0 (1 -c) n-i g 2 i 1/2 -1 0 ≤ b ≤ 1 (close to 0)

In particular, ADAM (Kingma and Ba, 2015) defined by the iterates :

     x n+1 = x n - a + √ vn+1 p n+1 p n+1 = p n + b (∇f (x n ) -p n ) v n+1 = v n + c (∇f (x n ) 2 -v n ) (3) for constants a ∈ R + , b, c ∈ [0, 1]

, can be seen as an instance of this algorithm by setting a n = a + √ vn where the vector v n , as defined above, is an exponential moving average of the gradient squared. For simplification, we omit bias correction steps for p n+1 and v n+1 .

We introduce the main assumption on the objective function which is standard in gradient-based algorithms analysis. Assumption 2.1. The mapping f : R d → R satisfies the following

(i) f is continuously differentiable and its gradient ∇f is L-Lipschitz continuous, (ii) f is bounded from below, i.e., inf x∈R d f (x) > -∞ .

3. RELATED WORKS:



3.1. THE HEAVY-BALL ALGORITHM.:

Adaptive algorithms as Heavy Ball. Thanks to its small per-iteration cost and its acceleration properties (at least in the strongly convex case), the Heavy-ball method, also called gradient descent with momentum, recently regained popularity in large-scale optimization (Sutskever et al., 2013) . This speeding up idea dates back to the sixties with the seminal work of Polyak (1964) . In order to tackle nonconvex optimization problems, Ochs et al. (2014) proposed iPiano, a generalization of the well known heavy-ball in the form of a forward-backward splitting algorithm with an inertial force for the sum of a smooth possibly nonconvex and a convex function. In the particular case of the Heavy-ball method, this algorithm writes for two sequences of reals (α n ) and (β n ):

EQUATION

)

We remark that Algorithm (2) can be written in a similar fashion by choosing step sizes α n = ba n+1 and inertial parameters (Diakonikolas and Jordan, 2019) . In the same vein, in Section 4, we establish a similar convergence result for an adaptive step size instead of a fixed predetermined step size schedule like in the Heavy-ball algorithm (see Theorem 4.2).

β n = (1 -b)a n+1 /a n .

Convergence rates under the Kurdyka-Łojasiewicz property. The KŁ property is a powerful tool to analyze gradient-like methods. We elaborate on this property in Section 5. It is for example possible to derive convergence rates assuming that the objective function satisfies this geometric property. Indeed, some recent progress has been made to study convergence rates of the Heavy-ball algorithm in the nonconvex setting. Ochs (2018) establishes local convergence rates for the iterates and the function values sequences under the KŁ property. The convergence proof follows a general method that is often used in non-convex optimization convergence theory. This framework was used for gradient descent (Absil et al., 2005) , for proximal gradient descent (see Attouch and Bolte (2009) for an analysis with the Łojasiewicz inequality) and further generalized to a class of descent methods called gradient-like descent algorithms (Attouch et al., 2013) (see also for ex. Bolte et al. (2018, Appendix) ). KŁ-based asymptotic convergence rates were established for constant Heavyball parameters (Ochs, 2018) . Asymptotic convergence rates based on the KŁ property were also shown (Johnstone and Moulin, 2017) for a general algorithm solving nonconvex nonsmooth optimization problems called Multi-step Inertial Forward-Backward splitting (Liang et al., 2016) which has iPiano and Heavy-ball methods as special cases. In this work, step sizes and momentum parameter vary along the algorithm run and are not supposed constant. However, specific values are chosen and consequently, their analysis does not encompass adaptive step sizes i.e. stepsizes that can possibly depend on past gradient information. In the present work, we establish similar convergence rates for methods such as ADAM under a bounded step size assumption (see Theorem 5.3). We also mention Li et al. (2017) which analyzes the accelerated proximal gradient method for nonconvex programming (APGnc) and establishes convergence rates of the function value sequence by exploiting the KŁ property. This algorithm is a descent method i.e. the function value sequence is shown to decrease over time. In the present work, we analyze adaptive algorithms which are not descent methods. Note that even Heavy-ball is not a descent method. Hence, our analysis requires additional treatments to exploit the KŁ property : we introduce a suitable Lyapunov function which is not the objective function.

3.2. VARIANTS OF ADAM:

Theoretical guarantees of variants of ADAM .

We list most of the existing variants of the ADAM algorithms together with their theoretical convergence guarantees in the following table. The gradient is supposed L-lipschitz continuous in all the convergence results. g

1:T,i = [g 1,i , g 2,i , • • • , g T,i ] T . Algorithm Effective step size a n+1 b n c n Assumptions Convergence Result AMSGRAD (1)

, ADAMNC (2) (Reddi et al., 2018) a0

√ n 1 √ vn (1) vn+1 = max(vn, (1 -cn)vn + cng 2 n ) (2) vn+1 = (1 -cn)vn + cng 2 n 1 -b 1 λ n-1 or 1 -b1 n c n ≡ c 1 c1 n (for ADAMNC) • convex functions • bounded gradients • bounded feasible set • d i=1 v1/2 T,i ≤ d (AMSGRAD) • d i=1 g 1:T,i 2 ≤ √ dT • b 1 < √ c 1 (ADAMNC) R T /T = O( logT /T ) R T T = O(1/ √ T ) (ADAMNC)

ADAM (De et al., 2018) 

4 gn 2 η 3L(1-(1-b) n ) 2 (η+2σ) 2 1 + √ vn v n+1 = (1 -c 1 )v n + c 1 g 2 n b n ≡ b 1 = 1 -η η+2σ c n ≡ c 1 • σ-bounded gradients • = 2σ ∀η > 0 ∃n ≤ 9Lσ 2 (f (x2)-f (x * )) η 6 s.t. g n ≤ η PADAM,AMSGRAD (Zhou et al., 2018) 1 √ N 1 vp n 1 √ dN 1 v 1 2 n (AMSGRAD) vn = max(v n-1 , (1 -c)v n-1 + cg 2 n ) b n ≡ b c n ≡ c • bounded gradients For PADAM: • p ∈ [0, 1 4 ] • 1 -b < (1 -c) 2p • d i=1 g 1:N,i 2 ≤ √ dN AMSGRAD: p = 1 2 and 1 -b < 1 -c E[ g τ 2 ] = O( 1+ √ d √ N + d N ) = O( d N + d N ) (AMSGRAD) τ uniform r.v in {1, • • • , N } RMSPROP (1)

, YOGI (2) (Zaheer et al., 2018) 

a1 + √ vn (1) v n+1 = (1 -c)vn + cg 2 n (2) vn = v n-1 -csign(v n-1 -g 2 n ) b n ≡ b c n ≡ c • G-bounded gradients • a 1 ≤ √ 1-c 2L (YOGI) • a 1 ≤ 2L • c ≤ 2 16G 2 • σ 2 -bounded variance E[ g τ 2 ] = O( 1 N + σ 2 ) τ uniform r.v in {1, • • • , N } O( 1 N ) if minibatch Θ(N ) AMSGRAD (1)

, ADAFOM (2) (Chen et al., 2019) 

1 √ n 1 √ vn (1) vn+1 = max(vn, (1 -cn)vn + cng 2 n ) (2) vn+1 = (1 -1 n )vn + 1 n g 2 n ) non-increasing c n ≡ c 1 • bounded gradients • ∃c > 0 s.t. |g 1,i | ≥ c min n∈[0,N ] E[ g n 2 ] = O( logN +d 2 √ N ) GENERIC ADAM (Zou et al., 2019) αn √ vn v n+1 = (1 -c n )v n + c n g 2 n α n = α √ 1-(1-c) n 1-(1-b) n b n ≥ b > 0 0 < c n < 1 non-increasing lim cn = c > b 2 • bounded gradients in expectation • d n ≤ αn √ cn ≤ c 0 d n d n non-increasing E[ g τ 4 3 ] 3 2 ≤ C+C N n=1 αn √ cn N α N τ uniform r.v in {1, • • • , N } ADABOUND (1)

, AMSBOUND (2) (Luo et al., 2019 )

1 √ n clip( α √ vn , η l (n), η u (n)) η l (n) non-decreasing to α * η u (n) non-increasing to α * (1) v n+1 = (1 -c)vn + cg 2 n (2) v n+1 = max(vn, (1 -c)vn + cg 2 n ) 1 -(1 -b)λ n-1 or 1 -1-b n b n ≥ b c n ≡ c • bounded gradients • closed convex bounded feasible set • 1 -b < √ 1 -c R T /T = O(1/ √ T )

Discussion of theoretical results. The first type of convergence results uses the online optimization framework which controls the convergence rate of the average regret. This framework was adopted for AMSGRAD, ADAMNC (Reddi et al., 2018) , ADABOUND and AMSBOUND (Luo et al., 2019) .

In this setting, it is assumed that the feasible set containing the iterates is bounded by adding a projection step to the algorithm if needed. We do not make such an assumption in our analysis. (Reddi et al., 2018) establishes a regret bound in the convex setting. The second type of theoretical results is based on the control of the norm of the (stochastic) gradients. We remark that some of these results depend on the dimension of the parameters. Zhou et al. (2018) improves this dependency in comparison to Chen et al. (2019) . The convergence result in De et al. (2018) is established under quite specific values of a n+1 , b n and . Zaheer et al. (2018) show a O(1/n) convergence rate for an increasing mini-batch size. However, the proof is provided for RMSPROP and seems difficult to adapt to ADAM which involves a momentum term. Indeed, unlike RMSPROP, ADAM does not admit the objective function as a Lyapunov function. Although we assume boundedness of the step size by Condition (7), we do not suppose that a 1 ≤ ε 2L (see table in Section 3.2) which can impose a very small step size and result in a slow convergence. The step size assumption a 1 ≤ 2L imposes a very small step size which may result in a slow convergence. We also remark that all the available theoretical results assume boundedness of the (stochastic) gradients. We do not make such an assumption. Furthermore, we do not add any decreasing 1/ √ n factor in front of the adaptive step size as it is considered in Reddi et al. (2018) ; Luo et al. (2019) and Chen et al. (2019) . Although constant hyperparameters b and c are used in practice, theoretical results are often established for non constant b n and c n (Reddi et al., 2018; Luo et al., 2019) . We also mention that most of the theoretical bounds depend on the dimension of the parameter (Reddi et al., 2018; Zhou et al., 2018; Chen et al., 2019; Zou et al., 2019; Luo et al., 2019) .

Other variants of ADAM . Recently, several other algorithms were proposed in the literature to enhance ADAM . Although these algorithms lack theoretical guarantees, they present interesting ideas and show good practical performance. For instance, ADASHIFT (Zhou et al., 2019) argues that the convergence issue of ADAM is due to its unbalanced step sizes. To solve this issue, they propose to use temporally shifted gradients to compute the second moment estimate in order to decorrelate it from the first moment estimate. NADAM (Dozat, 2016 ) incorporates Nesterov's acceleration into ADAM in order to improve its speed of convergence. Moreover, originally motivated by variance reduction, QHADAM (Ma and Yarats, 2019) replaces both ADAM's moment estimates by quasihyperbolic terms and recovers ADAM , RMSPROP and NADAM as particular cases (modulo the bias correction). Guided by the same variance reduction principle, RADAM (Liu et al., 2019) estimates the variance of the effective step size of the algorithm and proposes a multiplicative variance correction to the update rule.

Step size bound. Perhaps, the closest idea to our algorithm is the recent ADABOUND (Luo et al., 2019) which considers a dynamic learning rate bound. Luo et al. (2019) show that extremely small and large learning rates can cause convergence issues to ADAM and exhibit empirical situations where such an issue shows up. Inspired by the gradient clipping strategy proposed in Pascanu et al. (2013) to tackle the problem of vanishing and exploding gradients in training recurrent neural networks, Luo et al. (2019) apply clipping to the effective step size of the algorithm in order to circumvent step size instability. More precisely, authors propose dynamic bounds on the learning rate of adaptive methods such as ADAM or AMSGRAD to solve the problem of extreme learning rates which can lead to poor performance. Initialized respectively at 0 and ∞, lower and upper bounds both converge smoothly to a constant final step size following a predetermined formula defined by the user. Consequently, the algorithm resembles an adaptive algorithm in the first iterations and becomes progressively similar to a standard SGD algorithm. Our approach is different : we propose a static bound on the adaptive learning rate which depends on the Lipschitz constant of the objective function. This bound stems naturally from our theoretical derivations.

Assumption 4.1. There exists α > 0 s.t. a n+1 ≤ an α .

Note that this assumption is satisfied for ADAM with α = √ 1 -c where c is the parameter in (3). Unlike in AMSGRAD (Reddi et al., 2018) , the step size is not necessarily nonincreasing.

We provide a proof of the following key lemma in Appendix A.1. Lemma 4.1. Let Assumptions 2.1 and 4.1 hold true. Then, for all n ∈ N, for all u ∈ R + ,

EQUATION

where

A n+1 := 1 - a n+1 L 2 - |b -(1 -α)| 2u - 1 -α 2b and B := 1 - |b -(1 -α)|u b -(1 -α)

We state now one of the principal convergence results about Algorithm 2. In particular, we establish a sublinear convergence rate for the minimum of the gradients norms until time n. Theorem 4.2. Let Assumptions 2.1 and 4.1 hold true. Suppose that

EQUATION

Then,

(i) the sequence (H n ) is nonincreasing and n p n 2 < ∞. In particular, lim x n+1 -x n → 0 and lim ∇f (x n ) → 0 as n → +∞. (ii) For all n ≥ 1, min 0≤k≤n-1 ∇f (x k ) 2 ≤ 4 nb 2 H0-inf f δε + p 0 2 .

We provide some comments on this result.

Dimension dependence. Unlike most of the theoretical results for variants of ADAM as gathered in Section 3.2, we remark that the bound (ii) does not depend on the dimension d of the parameter x k .

Comparison to gradient descent. A similar result holds for deterministic gradient descent. If γ is a fix step size for gradient descent and there exist δ > 0, ε > 0 s.t. γ > δ and 1 -γL 2 > ε, then ( see Appendix B.6) for all n ≥ 1:

min 0≤k≤n-1 ∇f (x k ) 2 ≤ f (x 0 ) -inf f nγ(1 -γL 2 ) ≤ f (x 0 ) -inf f nδε .

When p 0 = 0 (this is the case for ADAM ), the bound in Theorem 4.2 coincides with the gradient descent bound, up to the constant 4/b 2 . We mention however that ε for Algorithm (2) is defined by a slightly more restrictive condition than for gradient descent : when b = 1, there is no momentum and

a sup = 1 L (1 -2ε) < 2/L.

Hence, under the boundedness of the effective step size, the algorithm have a similar convergence guarantee to gradient descent. Remark that the step size bound almost matches the classical 2/L upperbound on the step size of gradient descent. As it is already known for gradient descent, a large step size, even if it is adaptive, can harm the convergence of the algorithm.

4.2. STOCHASTIC SETTING:

We establish a similar bound in the stochastic setting. Let (Ξ, S) denote a measurable space and d ∈ N. Consider the problem of finding a local minimizer of the expectation F (x) := E(f (x, ξ)) w.r.t. x ∈ R d , where f : R d × Ξ → R is a measurable map and f ( . , ξ) is a possibly nonconvex function depending on some random variable ξ. The distribution of ξ is assumed unknown, but revealed online by the observation of iid copies (ξ n : n ≥ 1) of the r.v. ξ. For a fixed value of ξ, the mapping x → f (x, ξ) is supposed to be differentiable, and its gradient w.r.t. x is denoted by ∇f (x, ξ). We study a stochastic version of Algorithm (2) by replacing the deterministic gradient ∇f (x n ) by ∇f (x n , ξ n+1 ).

Theorem 4.3. Let Assumption 2.1 (for F ) and Assumption 4.1 hold true. Assume the following bound on the variance in stochastic gradients:

EQUATION

Then,

E[ ∇F (x τ ) 2 ] ≤ 4 nδb 2 α H 0 -inf f ε + √ a 0 p 0 2 + nā sup σ 2 2ε ,

where x τ is an iterate uniformly randomly chosen from {x 0 ,

• • • , x n-1 }.

The proof is defered to the appendix. In the special case where there is no momentum in the algorithm (i.e. RMSPROP) and assuming that the gradients are bounded, a similar convergence rate is obtained in Zaheer et al. (2018, Thm. 1) (see Section 3.2).

5. CONVERGENCE RATE ANALYSIS UNDER THE KŁ PROPERTY:

The KŁ inequality has been used to show the convergence of several first-order optimization methods towards critical points (Attouch and Bolte, 2009; Attouch et al., 2010; 2013; Bolte et al., 2014; Frankel et al., 2015; Li et al., 2017) . In this section, we use a methodology exposed in Bolte et al. (2018, Appendix) to show convergence rates based on the KŁ property. We modify it to encompass momentum methods. Note that although this modification was initiated in Ochs et al. (2014) ; Ochs (2018) , we use a different separable Lyapunov function. The first part of the proof follows these approaches and the second part follows the proof of Johnstone and Moulin (2017, Theorem 2).

Consider the function

EQUATION

Notice that 

H n = f (x n ) + 1 2b a n , p 2 n = H(x n , y n ) where (y n ) n∈N is

(i) ω(z 0 ) is a nonempty compact set. (ii) ω(z 0 ) ⊂ critH = critf × {0} . (iii) lim k→+∞ d(z k , ω(z 0 )) = 0.

(iv) H is finite and constant on ω(z 0 ).

We introduce the KŁ inequality which is the key tool of our analysis. We refer to Bolte et al. (2010) for an in-depth presentation of the KŁ property historically introduced by the fundamental works of Łojasiewicz (1963) and Kurdyka (1998) .

Define [α < H < β] := {z ∈ R 2d : α < H(z) < β} . Let η > 0 and define

Φ η := {ϕ ∈ C 0 [0, η) ∩ C 1 (0, η) : ϕ(0) = 0 , ϕ concave and ϕ > 0} .

where C 0 [0, η) is the set of continuous functions on [0, η) and C 1 (0, η) is the set of continuously differentiable functions on (0, η) . 

EQUATION

When H(z) = 0, we can rewrite Equation ( 9) as : ∇(ϕ • H)(z) ≥ 1 for suitable z points. This means that H becomes sharp under a reparameterization of its values through the so-called desingularizing function ϕ. The function H is said to be a KŁ function if it has the KŁ property at each point of the domain of its gradient. The KŁ property is satisfied by the broad class of semialgebraic functions including most objective functions in real applications ( • p for p rational, real polynomials, rank, etc.). (see Bolte et al. (2014, Appendix) for more examples). KŁ inequality holds at any non critical point (see Attouch et al. (2010, Remark 3.2 (b) )).

We introduce now a uniformized version of the KŁ property which will be useful for our analysis.

Lemma 5.2. (Uniformized KŁ property, Bolte et al. (2014, Lemma 6, p 478 )) Let Ω be a compact set and let H : R 2d → (-∞, +∞] be a proper l.s.c function. Assume that H is constant on Ω and satisfies the KŁ property at each point of Ω. Then, there exist ε > 0, η > 0 and ϕ ∈ Φ η such that for all z ∈ Ω, for all z ∈ {z ∈ R

d : d(z, Ω) < ε} ∩ [H(z) < H < H(z) + η], one has ϕ (H(z) -H(z)) ∇H(z) ≥ 1 (10)

Definition 5.3. (KŁ exponent) If ϕ can be chosen as ϕ(s) = c θ s θ for some c > 0 and θ ∈ (0, 1] in Definition 5.2, then we say that H has the KŁ property at z with an exponent of θ1 . We say that H is a KŁ function with an exponent θ if it has the same exponent θ at any z.

Furthermore, if H is a proper closed semialgebraic function, then H is a KŁ function with a suitable exponent θ ∈ (0, 1] . The slope of ϕ around the origin informs about the "flatness" of a function around a point. Hence, the KŁ exponent allows to obtain convergence rates. In the light of this remark, we state one of the main results of this work. Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Suppose moreover that H is a KŁ function with KŁ exponent θ. Denote by f (x * ) the limit of the sequence (H(z k )) k∈N where x * is a critical point of f . Then, the following convergence rates hold:

(i) If θ = 1, then f (x k ) converges in a finite number of iterations.

(ii) If 1/2 ≤ θ < 1, then f (x k ) converges to f (x * ) linearly i.e. there exist q ∈ (0, 1), C > 0

s.t. f (x k ) -f (x * ) ≤ C q k . (iii) If 0 < θ < 1/2 , then f (x k ) -f (x * ) = O(k 1 2θ-1 ) .

Sketch of the proof. The proof consists of two main steps. The first one is to show that the iterates enter and stay in a region where the KŁ inequality holds. This is achieved using the properties of the limit set (Lemma 5.1) and the uniformized KŁ property (Lemma 5.2). Then, the second step is to exploit this inequality in order to derive the sought convergence results. We defer the complete proof to Appendix B.3.

We introduce a lemma in order to make the KŁ assumption on the objective function f instead of the auxiliary function H. Lemma 5.4. Let f be a continuously differentiable function satisfying the KL property at x with an exponent of θ ∈ (0, 1/2]. Then the function H defined in Equation ( 8) has also the KŁ property at (x, 0) with an exponent of θ .

The following result derives a convergence rate on the objective function values under a KŁ assumption on this same function instead of an assumption on the Lyapunov function H. The result is an immediate consequence of Lemma 5.4 and Theorem 5.3.

Corollary 5.5. Let (z k ) k∈N be the sequence defined for all k ∈ N by z k = (x k , y k ) where y k = √ a k p k and (x k , p k ) is generated by Algorithm (2) from a starting point z 0 . Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Suppose moreover that f is a KŁ function with KŁ exponent θ ∈ (0, 1/2). Denote by f (x * ) the limit of the sequence (H(z k )) k∈N where x * is a critical point of f . Then Supposing that ∇f is L-Lipschitz, using Taylor's expansion and the expression of p n in the algorithm, we obtain the following inequality:

f (x k ) -f (x * ) = O(k M.

f (x n+1 ) ≤ f (x n ) -∇f (x n ), a n+1 p n+1 + L 2 a n+1 p n+1 2 (11)

Moreover,

EQUATION

Observing that

p 2 n+1 -p 2 n = -b 2 (∇f (x n ) -p n ) 2 + 2bp n+1 (∇f (x n ) -p n )

, we obtain after simplification :

H n+1 ≤ H n + L 2 a n+1 p n+1 2 - b 2 a n+1 , (∇f (x n )-p n ) 2 -a n+1 p n+1 , p n + 1 2b a n+1 -a n , p 2 n . (13)

Using again p n = p n+1 -b(∇f (x n ) -p n ), we replace p n :

H n+1 ≤ H n + L 2 a n+1 p n+1 2 - b 2 a n+1 , (∇f (x n ) -p n ) 2 -a n+1 , p 2 n+1 + b a n+1 p n+1 , ∇f (x n ) -p n + 1 2b a n+1 -a n , p 2 n .

Under Assumption 4.1, we write:

a n+1 -a n , p 2 n ≤ (1 -α) a n+1 , p 2 n and using p 2 n = p 2 n+1 + b 2 (∇f (x n ) -p n ) 2 -2bp n+1 (∇f (x n ) -p n ), it holds that: H n+1 ≤ H n -a n+1 , p 2 n+1 - b 2 a n+1 , (∇f (x n ) -p n ) 2 + L 2 a n+1 p n+1 2 + (b -(1 -α)) a n+1 p n+1 , ∇f (x n ) -p n + 1 -α 2b a n+1 , p 2 n+1 + b(1 -α) 2 a n+1 , (∇f (x n ) -p n ) 2 .

Using the classical inequality xy ≤ x 2 2u + uy 2 2 , we have :

EQUATION

)

Hence, after using this inequality and rearranging the terms, we derive the following inequality:

H n+1 ≤ H n -a n+1 p 2 n+1 , 1 - a n+1 L 2 - |b -(1 -α)| 2u - 1 -α 2b - b 2 a n+1 (∇f (x n ) -p n ) 2 , 1 - |b -(1 -α)|u b -(1 -α) 1 .

This concludes the proof.

A.2 AN ADDITIONAL PROPOSITION:

Proposition A.1. Let Assumption 2.1 hold true. Suppose moreover that 1

-α < b ≤ 1. Let ε > 0 s.t. a sup := 2 L 1 -(b-(1-α)) 2 2bα -1-α 2b -ε is nonnegative. Let δ > 0 s.t. for all n ∈ N, a n+1 ≤ min a sup , a n α .

Then, for all n ≥ 1,

n-1 k=0 a k+1 , ∇f (x k ) 2 ≤ 4 b 2 α H 0 -inf f ε + a 0 , p 2 0

Proof. This is a consequence of Lemma 4.1. Conditions A n+1 ≥ ε and B ≥ 0 write as follow :

a n+1 ≤ 2 L 1 - b -(1 -α) 2u - 1 -α 2b -ε and u ≤ αb b -(1 -α) .

We get the assumption made in the proposition by injecting the second condition into the first one and adding the assumption an+1 an ≤ α made in the lemma. Under this assumption, we sum over 0 ≤ k ≤ n -1 Equation ( 5), rearrange it and use A n+1 ≥ ε, B ≥ 0 to obtain :

EQUATION

Moreover, from the Algorithm 2 second update rule, we get ∇f

(x k ) = 1 b p k+1 -1-b b p k . Hence, we have for all k ≥ 0 : ∇f (x k ) 2 ≤ 2 1 b 2 p 2 k+1 + (1 -b) 2 b 2 p 2 k ≤ 2 b 2 (p 2 k+1 + p 2 k ) .

We deduce that :

n-1 k=0 a k+1 , ∇f (x k ) 2 ≤ 2 b 2 n-1 k=0 a k+1 , p 2 k+1 + p 2 k = 2 b 2 n-1 k=0 a k+1 , p 2 k+1 + 2 b 2 n-1 k=0 a k+1 , p 2 k ≤ 2 b 2 n-1 k=0 a k+1 , p 2 k+1 + 2 b 2 α n-1 k=0 a k , p 2 k ≤ 2 b 2 α 2 n-1 k=1 a k , p 2 k + a n , p 2 n + a 0 , p 2 0 ≤ 4 b 2 α n k=0 a k , p 2 k ≤ 4 b 2 α H 0 -inf f ε + a 0 , p 2 0 . A.3 PROOF OF THEOREM 4.2

This is a consequence of Lemma 4.1. Conditions A n+1 ≥ ε and B ≥ 0 write as follow :

a n+1 ≤ 2 L 1 - b -(1 -α) 2u - 1 -α 2b -ε and u ≤ αb b -(1 -α) .

We get the assumption made in the proposition by injecting the second condition into the first one and adding the assumption an+1 an ≤ α made in the lemma. Under this assumption, we sum over 0 ≤ k ≤ n -1 Equation ( 5), rearrange it and use A n+1 ≥ ε, B ≥ 0 and a k+1 ≥ δ to obtain :

n-1 k=0 δ ε p k+1 2 ≤ H 0 -H n ,

Then, observe that H n ≥ f (x n ) ≥ inf f . Therefore, we derive :

EQUATION

Moreover, from the algorithm 2 second update rule, we get ∇f

(x k ) = 1 b p k+1 -1-b b p k . Hence, we have for all k ≥ 0 : ∇f (x k ) 2 ≤ 2 1 b 2 p k+1 2 + (1 -b) 2 b 2 p k 2 ≤ 2 b 2 ( p k+1 2 + p k 2 ) .

We deduce that :

EQUATION

Finally, using Equations ( 16) and ( 17), we have :

min 0≤k≤n-1 ∇f (x k ) 2 ≤ 1 n n-1 k=0 ∇f (x k ) 2 ≤ 4 nb 2 H 0 -inf f δε + p 0 A.4 PROOF OF THEOREM 4.3

The proof of this proposition mainly follows the same path as its deterministic counterpart. However, due to stochasticity, a residual term (the last term in Equation ( 18)) quantifying the difference between the stochastic gradient estimate and the true gradient of the objective function (compare Equation ( 18) to Lemma 4.1). Following the exact same steps of Appendix A.1, we obtain by replacing the deterministic gradient ∇f (x n ) by its stochastic estimate ∇f (x n , ξ n+1 ) :

EQUATION

)

Using the classical inequality xy ≤ x 2 2 + y 2 2 and the almost sure boundedness of the step size a n+1 , we get :

∇f (x n , ξ n+1 ) -∇F (x n ), a n+1 p n+1 ≤ 1 2 (∇f (x n , ξ n+1 ) -∇F (x n )) 2 + 1 2 p 2 n+1 , a n+1 ≤ a sup 2 ∇f (x n , ξ n+1 ) -∇F (x n ) 2 + 1 2 a n+1 , p 2 n+1 .

Therefore, taking the expectation and using the boundedness of the variance, we obtain from Equation ( 18) :

E[H n+1 ] -E[H n ] ≤ -E a n+1 p 2 n+1 , 1 - a n+1 L 2 - |b -(1 -α)| 2u - 1 -α 2b + a sup σ 2 2 .

Then, the proof follows the lines of Appendix A.2. Hence, we have

E[H n+1 ] -E[H n ] ≤ -E a n+1 p 2 n+1 , ε1 + a sup σ 2 2 .

We sum these inequalities for k = 0, • • • , n -1 and rearrange the terms to obtain

E n-1 k=0 a k+1 , p 2 k+1 ≤ H 0 -inf f ε + na sup σ 2 2ε .

Then following the derivations in Appendix A.2 using ∇f (x k , ξ k+1 ) = 1 b p k+1 -1-b b p k , we establish the following inequality

E n-1 k=0 a k+1 , ∇f (x k , ξ k+1 ) 2 ≤ 4 b 2 α H 0 -inf f ε + a 0 , p 2 0 + na sup σ 2 2ε .

Finally, we apply Jensen's inequality to • 2 , we inject the assumption a n+1 ≥ δ and we divide the previous inequality by n to obtain the sought result

1 n n-1 k=0 E ∇F (x k ) 2 ≤ 4 nδb 2 α H 0 -inf f ε + a 0 , p 2 0 + na sup σ 2 2ε .

B APPENDIX B 

H(z k+1 ) -H(z k ) ≤ -ρ 1 x k+1 -x k 2 ∀k ∈ N.

(ii) There exists a positive scalar ρ 2 s.t. :

∇H(z k+1 ) ≤ ρ 2 ( x k+1 -x k + x k -x k-1 ) ∀k ≥ 1.

(iii) (continuity condition) If z is a limit point of a subsequence (z kj ) j∈N , then lim j→+∞ H(z kj ) = H(z).

Remark 1. Conditions in Bolte et al. (2018, Appendix) corresponding to Lemma B.1 are more general. Authors consider a nonsmooth objective function and introduce the Fréchet subdifferential instead of the gradient. For our purposes, this is sufficient.

Proof.

(i) From Lemma 4.1 and theorem 4.2, we get for all k ∈ N:

H(z k+1 )-H(z k ) ≤ -ε a k+1 , p 2 k+1 ≤ -ε a k+1 , x k+1 -x k -a k+1 2 ≤ - ε a sup x k+1 -x k 2 .

We set ρ 1 := ε asup .

(ii) First, observe that for all k ∈ N

EQUATION

Now, let us upperbound each one of these two terms. Recall that we can rewrite our algorithm under a "Heavy-ball"-like form as follows:

x k+1 = x k -α k ∇f (x k ) + β k (x k -x k-1 ) ∀k ≥ 1.

where α k := ba k+1 and β k = (1 -b) a k+1 a k are vectors. On the one hand,

∇f (x k+1 ) 2 ≤ 2 ∇f (x k+1 ) -∇f (x k ) 2 + ∇f (x k ) 2 ≤ 2 L 2 x k+1 -x k 2 + ∇f (x k ) 2 (L-Lipschitz continuity of the gradient) Moreover, ∇f (x k ) 2 = x k -x k+1 α k + β k α k (x k -x k-1 ) 2 ≤ 2 x k -x k+1 ba k+1 2 + 2 1 -b b 1 a k (x k -x k-1 ) 2 ≤ 2 b 2 δ 2 x k+1 -x k 2 + 2(1 -b) 2 b 2 δ 2 x k -x k-1 2 ≤ 2 b 2 δ 2 ( x k+1 -x k 2 + x k -x k-1 2 ). Hence, ∇f (x k+1 ) 2 ≤ 2 L 2 x k+1 -x k 2 + ∇f (x k ) 2 ≤ 2 L 2 + 2 b 2 δ 2 x k+1 -x k 2 + 4 b 2 δ 2 x k -x k-1 2 ≤ 2 L 2 + 2 b 2 δ 2 ( x k+1 -x k 2 + x k -x k-1 2 ) .

Therefore, the following inequality holds :

∇f (x k+1 ) ≤ 2 L 2 + 2 b 2 δ 2 ( x k+1 -x k + x k -x k-1 ) .

On the otherhand,

y k+1 = √ a k+1 p k+1 = x k+1 -x k √ a k+1 ≤ 1 √ δ x k+1 -x k .

Finally, combining the inequalities for both terms in Equation ( 19), we obtain

∇H(z k+1 ) ≤ ρ 2 ( x k+1 -x k + x k -x k-1 ) ∀k ≥ 1 . with ρ 2 := 2 L 2 + 2 b 2 δ 2 + 1 b √ δ .

(iii) This is a consequence of the continuity of H. Hence, for all ε > 0, there exists k 1 ∈ N s.t. d(z k , ω(z 0 )) < ε for all k > k 1 . Moreover, ω(z 0 ) is a nonempty compact set and H is finite and constant on it. Therefore, we can apply the uniformization Lemma 5.2 with Ω = ω(z 0 ). Hence, for any k > l := max(k 0 , k 1 ), we get

EQUATION

This completes the first step of the proof. In the second step, we follow the proof of Johnstone and Moulin (2017, Theorem 2). Using Lemma B.1 .(i)-(ii), we can write for all k ≥ 1,

∇H(z k+1 ) 2 ≤ 2ρ 2 2 ( x k+1 -x k 2 + x k -x k-1 2 ) ≤ 2ρ 2 2 ρ 1 (H(z k-1 ) -H(z k+1 )) .

Injecting the last inequality in Equation ( 21), we obtain for all k > k 2 := max(l, 2),

2ρ 2 2 ρ 1 ϕ (H(z k ) -H(z)) 2 (H(z k-2 ) -H(z k )) ≥ 1 .

Now, use ϕ (s) = cs θ-1 to derive the following for all k > k 2 :

EQUATION

Let r k := H(z k ) -H(z) and C 1 = ρ1 2ρ 2 2 c2 . Then, we can rewrite Equation ( 22) as

EQUATION

)

We distinguish three different cases to obtain the sought results.

(i) θ = 1 : Suppose r k > 0 for all k > k 2 . Then, since we know that r k → 0 by Equation ( 20), C 1 must be equal to 0. This is a contradiction. Therefore, there exist k 3 ∈ N s.t. r k = 0 for all k > k 3 (recall that (r k ) k∈N is nonincreasing).

(ii) θ ≥ 1 2 : As r k → 0, there exists k 4 ∈ N s.t. for all k ≥ k 4 , r k ≤ 1 . Observe that 2(1 -θ) ≤ 1 and hence r k-2 -r k ≥ C 1 r k for all k > k 2 and then

EQUATION

)

where p 1 := k-k4 2 . Notice that p 1 > k-k4-2

2:

. Thus, the linear convergence result follows. Note also that if θ = 1/2, 2(1 -θ) = 1 and Equation ( 24) holds for all k > k 2 .

(iii) θ < 1 2 : Define the function h by h(t) = D 1-2θ t 2θ-1 where D > 0 is a constant. Then,

h(r k ) -h(r k-2 ) = r k r k-2 h (t)dt = D r k-2 r k t 2θ-2 dt ≥ D (r k-2 -r k ) r 2θ-2 k-2 .

We disentangle now two cases :

(a) Suppose 2r 2θ-2 k-2 ≥ r 2θ-2 k . Then, by Equation ( 23), we get

EQUATION

)

(b) Suppose now the opposite inequation 2r 2θ-2 k-2 < r 2θ-2 k . We can suppose without loss of generality that r k are all positive. Otherwise, if there exists p such that r p = 0, the sequence (r k ) k∈N will be stationary at 0 for all k ≥ p . Observe that 2θ -2 < 2θ -1 < 0, thus 2θ-1 2θ-2 > 0 . As a consequence, we can write in this case r 2θ-1 k > q r 2θ-1 k-2 where q := 2 2θ-1 2θ-2 > 1 . Therefore, using moreover that the sequence (r k ) k∈N is nonincreasing and 2θ -1 < 0, we derive the following This completes the proof.

h(r k )-h(r k-2 ) = D 1 -2θ (r 2θ-1 k -r 2θ-1 k-2 ) > D 1 -2θ (q-1)r 2θ-1 k-2 > D 1 -2θ (q-1)

:

FIRST ORDER CONVERGENCE RATE 4.1 DETERMINISTIC SETTING Let (H n ) n≥0 be a sequence defined for all n ∈ N by H n := f (x n ) + 1 2b a n , p 2 n .We further assume the following step size growth condition.

2θ-1 ) .1 α := 1 -θ is also defined as the KŁ exponent in other papers(Li and Pong, 2018).

Figures and Tables:

a sequence defined for all n ∈ N by y n = √ a n p n . Notations and definitions. If (E, d) is a metric space, z ∈ E and A is a non-empty subset of E, we use the notation d(z, A) := inf{d(z, z ) : z ∈ A} . The set of critical points of the function H is defined by crit H := {z ∈ R 2d s.t. ∇H(z) = 0} . Definition 5.1. (Set of limit points) The set of all limit points of (z k ) k∈N initialized at z 0 is defined by ω(z 0 ) := {z ∈ R 2d : ∃ an increasing sequence of integers (k j ) j∈N s.t z kj → z as j → ∞} . Assumption 5.1. f is coercive. Lemma 5.1. (Properties of the limit point set) Let (z k ) k∈N be the sequence defined for all k ∈ N by z k = (x k , y k ) where y k = √ a k p k and (x k , p k ) is generated by Algorithm (2) from a starting point z 0 . Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Then,

Theorem 5.3. (Convergence rates) Let (z k ) k∈N be the sequence defined for all k ∈ N by z k = (x k , y k ) where y k = √ a k p k and (x k , p k ) is generated by Algorithm (2) from a starting point z 0 .

25) and Equation (26) yields h(r k ) ≥ h(r k-2 ) + C 3 where C 3 := min(C 2 , C1 D 2 ) . Consequently, h(r k ) ≥ h(r k-2 p2 ) + p 2 C 3 where p 2 := k-k22. We deduce from this inequality thath(r k ) ≥ h(r k ) -h(r k-2 p2 ) ≥ p 2 C 3 .Therefore, rearranging this inequality using the definition of h, we obtainr 1-2θ k ≤ D 1-2θ (C 3 p 2 ) -1 . Then, since p 2 > k-k2-proof by observing that f (x k ) ≤ H(z k ) and recalling that z ∈ critH .B.4 PROOF OF LEMMA 5.4Since f has the KŁ property at x with an exponent θ ∈ (0, 1/2], there exist c, ε and ν > 0 s.t.∇f (x) 1 1-θ ≥ c(f (x) -f (x))(27)for all x ∈ R d s.t. x -x ≤ ε and f (x) < f (x) + ν where condition f (x) -f (x) is dropped because Equation (27) holds trivially otherwise. Let z = (x, y) ∈ R 2d be s.t. x -x ≤ ε , y ≤ ε and H(x, 0) < H(x, y) < H(x, 0) + ν . We assume that ε < b (ε can be shrunk if needed). We have f (x) ≤ H(x, y) < H(x, 0) + ν = f (x) + ν . Hence Equation (27) holds for these x. By concavity of u → u C 0 min c, 2 b f (x) -f (x) + 1 2b y 2 = C 0 min c, 2 b (H(x, y) -H(x, 0)) .

Ochs et al. (2014) only consider the case where α n and β n are real-valued. Moreover, the latter does not consider adaptive step sizes, i.e step sizes depending on past gradient information. We can show some improvement with respect toOchs et al. (2014) with weaker convergence conditions in terms of the step size of the algorithm (see Appendix B.5) while allowing adaptive vector-valued step sizes a n (see Proposition A.1).It is shown inOchs et al. (2014) that the sequence of function values converges and that every limit point is a critical point of the objective function. Moreover, supposing that the Lyapunov function has the KŁ property at a cluster point, they show the finite length of the sequence of iterates and its global convergence to a critical point of the objective function. Similar results are shown inWu and Li (2019) for a more general version than iPiano(Ochs et al., 2014) computing gradients at an extrapolated iterate like in Nesterov's acceleration.

Table content: <table/>

Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 9793-9803, 2018. D. Zhou, Y. Tang, Z. Yang, Y. Cao, and Q. Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:1808.05671, 2018.

Table content: <table><tr><td>Z. Zhou, Q. Zhang, G. Lu, H. Wang, W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence</td></tr><tr><td>of adaptive learning rate methods. In International Conference on Learning Representations,</td></tr><tr><td>2019. URL https://openreview.net/forum?id=HkgTkhRcKQ.</td></tr><tr><td>F. Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of adam and</td></tr><tr><td>rmsprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,</td></tr><tr><td>pages 11127-11135, 2019.</td></tr><tr><td>A APPENDIX A</td></tr><tr><td>A.1 PROOF OF LEMMA 4.1</td></tr></table>

B.1 CONDITIONS SIMILAR TO "GRADIENT-LIKE DESCENT SEQUENCES" CONDITIONS (BOLTE ET AL., 2018, APPENDIX)(OCHS ET AL., 2014) Lemma B.1. Let (z k ) k∈N be the sequence defined for all k ∈ N by z k = (x k , y k ) where y k = √ a k p k and (x k , p k ) is generated by Algorithm (2) from a starting point z 0 . Let Assumptions 2.1

Table content: <table><tr><td>and 4.1 hold true. Assume moreover that condition (6) holds. Then,</td></tr><tr><td>(i) (sufficient decrease property) There exists a positive scalar ρ 1 s.t. :</td></tr></table>

j∈N is a subsequence of (∇H(z n )) n∈N . (iii) This point stems from the definition of limit points. Every subsequence of the sequence (d(z k , ω(z 0 ))) k∈N converges to zero as a consequence of the definition of ω(z 0 ).(iv) The sequence (H(z n )) n∈N is nonincreasing by Theorem 4.2. It is also bounded from below because H(z k ) ≥ f (x k ) ≥ inf f for all k ∈ N.Hence we can denote by l its limit. Let z ∈ ω(z 0 ). There there exists a subsequence (z kj ) j∈N converging to z as j → ∞ . By the third assertion of Lemma B.1, lim If there exists k ∈ N s.t. H(zk) = H(z) , then H(zk +1 ) = H(z) and by the first point of Lemma B.1, xk +1 = xk and then (x k ) k∈N is stationary and for all k ≥ k , H(z k ) = H(z) and the results of the theorem hold in this case (note that z ∈ critH by Lemma 5.1). Therefore, we can assume now that H(z) < H(z k )∀k > 0 since (H(z k )) k∈N is nonincreasing and Equation (20) holds. One more time, from Equation (20), we have that for all η > 0, there exists k 0 ∈ N s.t. H(z k ) < H(z) + η for all k > k 0 . From Lemma 5.1, we get d(z k , ω(z 0 )) → 0 as k → +∞ .

Table content: <table><tr><td>B.2 PROOF OF LEMMA 5.1</td><td/></tr><tr><td>(i) By Theorem 4.2, the sequence (H(z j→+∞</td><td>H(z kj ) = H(z) . Hence this limit equals l since</td></tr><tr><td colspan="2">(H(z n )) n∈N converges towards l. Therefore, the restriction of H to ω(z 0 ) equals l .</td></tr><tr><td>B.3 PROOF OF THEOREM 5.3</td><td/></tr><tr><td/><td>(20)</td></tr></table>

Peer review (iclr2020):
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 _x0008_eta_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.