Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Nonconvex Optimization
Authors: Anas Barakat
Pascal Bianchi
Venue:  (2020)
Keywords: nonconvex optimization
adaptive methods

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. Therefore, several variants of Adam have been proposed to circumvent this convergence issue. In this work, we study the 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-Lojasiewicz property.

Under review as a conference paper at ICLR 2020
CONVERGENCE ANALYSIS OF A MOMENTUM ALGORITHM WITH ADAPTIVE STEP SIZE FOR NONCONVEX OPTIMIZATION
Anonymous authors Paper under double-bling blind review
ABSTRACT
Although ADAM is very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex op- timization examples. Several variants of ADAM have been proposed circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonconvex optimization under 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 novel first order convergence rate result both deterministic and stochastic contexts. Furthermore, we establish convergence rates of the function value sequence using the Kurdyka-Lojasie property.
INTRODUCTION
Consider the unconstrained optimization problem
min f(x), #ER
(I)
where f IRd + 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 (2018) for recent survey). Recently, a class of algorithms called adap- tive 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 predetermined step size schedule, Among these adaptive algorithms, ADAM (Kingma and Ba, 2015) is very popular for op- timizing the weights of neural networks. However, recently, Reddi et al. (2018) exhibited simple convex stochastic optimization problem over a compact set where ADAM fails to converge because of its short-term gradient memory. Moreover, they proposed algorithm called AMSGRAD 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 detailed review). In this work, under bounded step size assumption, we propose a theoretical analysis of ADAM for nonconvex optimization.
Contributions.
We establish a convergence rate for ADAM the deterministic case for nonconvex optimization under bounded step size. This algorithm can be seen deterministic clipped version of ADAM which guarantees safe theoretical step sizes. More precisely, we show a ((1/n) convergence rate by introducing a suitable Lyapunov function.
We show similar convergence result to Zaheer al. (2018, Thm. 1) for nonconvex stochastic optimization up to the limit the variance of stochastic gradients under an almost surely bounded step size. In comparison the literature, 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.

---

Under review as a conference paper at ICLR 2020
We propose convergence rate analysis of the objective function of the algorithm using the Kurdyka--ojassewiicz (KL) property. To the best of our knowledge, this is the first time such result is established for an adaptive optimization algorithm.
2 A MOMENTUM ALGORITHM WITH ADAPTIVE STEP SIZE
Notations. All operations between vectors of Ie are to read coordinatewise. The vector of ones of R is denoted by 1. When a scalar is added to a vector, is added to each one its coordinates. Inequalities also be read coordinatewise. If Rd, S À R means that each coordinate of x is smaller than X.
We investigate the following algorithm defined by two sequences (I:,) and (pn) in R
In+1 In On+1Pn+1
(p++1 Pn + (V)(xn) Pn)
where fz( is the gradient of f at point (a,,) is sequence of vectors in R with positive coordinates, is a positive real constant and To. Pn
Algorithm (2) includes the classical Heavy-ball method as special case, but is much more general. Indeed, we allow the sequence of step sizes (a,, to be adaptive O, E I may depend on the past gradients 9& == (=*x) and the iterates Ią for k I We stress that the step size 0,, is vector of I2 and that the product 1 in (2) read componentwise (this is equivalent to the formulation with 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 vector step size formulation:
Algorithm SGD
Effective step size an+1
Momentum
(Robbins and Monro, 1985)
an+1
(no momentum)
ADAGRAD (Duchi al., 2011)
0n+11 (Ei= 96 112
= 1
RMSPROP
6 + (c Di=n( (1 - m))= 1/2
(Ticleman and Hinton, 2012)
ap+1 = a
b = 1
ADAM
ax+1 = c+ (e En - c)- -g) 1/2
0 < b b 1
(Kingma and Ba, 2015)
(close to 0)
In partieular, ADAM (Kingma and Ba, 2015) defined by the iterates
In-1 In ct ctven4 Pn+1
Pn+1 Pr b (Vf(In) Pn)
(3)
Un+1 = vn + e (V(xx,) v.)
for constants a I4,, b, E [0, can seen as an instance of this algorithm by setting an ct where the vector Un. defined above, is an exponential moving average of the gradient squared. For simplification, we omit bias correction steps for Pa+1 and u2+1.
We introduce the main assumption on the objective function which is standard in gradient-based algorithms analysis.
Assumption 2.1. The mapping f Rd - R satisfies the following
d
ii f is continuously differentiable and its gradient V.f is L L-Liscchitz continuous,
iii) f is bounded from below, i.e., inf f(x) -0.
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
2

---

Under review as a conference paper at ICLR 2020
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 al. (2014) proposed iPiano, generalization of the well known heavy-ball in the form of a forward-backwardt splitting algorithm with an inertial force for the sum of smooth possibly nonconvex and convex function. In the particular case of the Heavy-ball method, this algorithm writes for two sequences of reals (ap) and (Bn):
In+1 = Zp an (f())) + ( In-1)
(4)
We remark that Algorithm (2) can be written in a similar fashion by choosing step sizes on bax++ and inertial parameters 8n = (1 -)),,+1/mm.... Ochs et al. (2014) only consider the case where On and Bn, are real-valued. Moreover, the latter does not consider adaptive step sizes, ie step sizes depending on past gradient information. We can show some improvement with respect to Ochs 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 an (see Proposition A.
is shown in Ochs et al. (2014) that the sequence of function values converges and that every limit point is critical point of the objective function. Moreover, supposing that the Lyapunov function has the KL property at a cluster point, they show the finite length of the sequence of iterates and its global convergence to critical point of the objective function. Similar results are shown in Wu and Li (2019) for more general version than iPiano (Ochs et al., 2014) computing gradients at an extrapolated iterate like in Nesterov's ' acceleration.
Convergence rate. Ochs et al. (2014) determines a ((1/n) convergence rate (where n is the num- ber of iterations of the algorithm) with respect the proximal residual which boils down to the gradient for noncomposite optimization. Furthermore, a recent work introduces a generalization of the Heavy-ball method (and Nesterov's acceleration) constrained convex optimization in Banach spaces and provides a non-asymptotic hamiltonian based analysis with (11/n) convergence rate (Diakonikolas and Jordan, 2019). In the same vein, in Section 4, we establish a similar conver- gence result for an adaptive step size instead of a fixed predetermined step size schedule like in the Heavy-ball algorithm (see Theorem 4.2).
Convergence rates under the Kurdyka-E.ojasivvin property. The Kt. 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) 8) establishes local convergence rates for the iterates and the function values sequences under the KE property. The convergence proof follows a gen- eral 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 class of descent methods called gradient-like descent algorithms (Attouch et al., 2se3)(see also for ex. Bolte et al. (2018, Appendix)). KE-based asymptotic convergence rates were established for constant Heavy- ball parameters (Ochs, 2018). Asymptotic convergence rates based on the KE property were also shown (Johnstone and Moulin, 2017) for a general algorithm solving nonconvex nonsmooth opti- mization problems called Multi-step Inertial Forward- -ackwaadd splitting (Liang et al., 2016) which has iPiano and Heavy-ball methods as special cases. this work, step sizes and momentum pa- rameter 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.c. stepsizes that can possibly depend on past gradient information. In the present work, we establish similar conver- gence 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 non- convex programming (APGnc) and establishes convergence rates of the function value sequence by exploiting the Kł property. This algorithm 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 KE property: we introduce a suitable Lyapunov function which not the objective function.
3.2 VARIANTS OF ADAM
3

---

Under review as a conference paper at ICLR 2020
Lf f )
[l 1 S C+O' DN aayen Nax
/T
RI. T = -(L/VT) (ADANNC)
V. + )
(AMSORAD)
7 uniform r.v {1, 11.....,y
Bllg= 11 = O + o²)
uniform ry (I, ,I,...,N NN3 ( if minibatch (N)
LogNN+ V.
uniform n. f1,... .N.
Convergence Result
/T/T= =
Theoretical guarantees of variants ADAM. We list most of the existing variants of the ADAM algorithms together with their theoretical convergencee guarantees in the following table. The gradient is supposed L- L-lipschitz continuous in all the convergence results. 91:,, =
R = = 0
Bilg- = 0
min Blllgn [12] = O
= =V( / + #)
19
D &
Aл >
ne [o.N)
.9r.""" I".
d 11/2 < d (AMSGRAD
19r. & ddT L1=1
For PADAM: E [0, 4l
ll S vdN
ANSGRAD: p = f and - 6-1-c
bounded feasible set
r-bounded gradients
G-bounded gradients
c C T6G?
22-bounded variance
Assumptions
convex functions
bounded gradients
bounded gradients
E 1- 6< (1- 2)
24 (YoG))
bounded gradients
Be > s.L. 191,i 2
bounded gradients
. d, < dng S cod,
bounded gradients closed convex
bounded feasible set
1- b < v1 v1-c
d, non-iiccreasing
(1, 92,5
a1 S T
expectation
a1 S 27.
c= 20
Li=1
bn
0 < Gn < 1 non-incrcasing
62
Gn = C1
Gn = C1
Gn. = c
Gu = c
On ci
Cr = c
en.
non-increasing
1- n=
or orl- b1
n
b b1
1 91
On = b
bx 1>b0
1- (1 6:w
or 1-b
b,.
b =
4n 2
Gn = max max(mn 0p-11 (1 - en + c
(17 max(On (1 cnjos cua
(3) sw+1 - max (9.x (1 on)on + (a
(111-(1001)00) b P(n+2a) +tve
Un++1 U + -19m
(2) 9 ca 2
Un + engh
clip( a [ (n)) v/s yor, Mi ()) non-deereasing a.
(1 c)v. com)
Effective step size 0p111
020 = (1 co + ense
(0 (1 - ejen + co
(2) R = (1 16n + 19)
1ha (n) non con-incceasing to
wa++1 = (1 - o)% ogn
(AmtGGaA))
On = à av (1((1e)) (-(1-)-- by
dg 1 vn Von
V 02
clyoe
vi
VaN
Uni1 = (1
(20
AMSGRADO), "FBRADD),ADMNCCC A (Reddi et al., 2018)
RMSPROPO) Yoar (Zaheer et al., 2018)
AMSGR ADU), AnxPox (Chen et al., 2019)
IDABOUND(3) AMSBOUND (Luo at. 2019)
PAADA..MMSRR. (Zhou et al., 2018)
GENERIC ADAM (Zou al. 2019)
ADAM (De ct al., 2018)
Algorithm

---

Under review as a conference paper at ICLR 2020
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 assumption in our analysis. (Reddi et al., 2018) establishes a regret bound in the convex setting. The second type of theoretical results 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 + b, and e. Zaheer et al. (2018) show a ((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 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 aj S 2T. (see table in Section 3.2) which can impose a very small step size and result in a slow convergence. The step size assumption 01 S 27. imposes very small step size which may result in 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/ 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 and are used in practice, theoretical results are often established for non constant bn and en (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 en- hance 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 quasi- hyperbolic 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 correc- tion 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 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 poor performance. Initialized respectively 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.
order to
and cc, lower and upper bounds
4 FIRST ORDER CONVERGENCE RATE
4.1 DETERMINISTIC SETTING
Let (Hn))20 be sequence defined for all n E N by H, := f((()) + 2 (an..Pp)
We further assume the following step size growth condition.
5

---

Under review as a conference paper at ICLR 2020
Assumption 4.1. There exists 0 s.t. an+1 S en.
Note that this assumption is satisfied for ADAM with a = vT- c where c the parameter (3).
Unlike in AMSGRAD (Reddi et al., 2018), the step size is not necessarily nonincreasing.
provide a proof the following key lemma Appendix A.I.
Lemma 4.1. Let Assumptions 2.1 and 4.1 hold true. Then, for all n E for all R4.
Hut1 H (An+ Ant1) ( pa)) P,B1.
(5)
where
Au+1 = an+iL L b (1 a:)
a
and B == (1 a))
(1 a)
2
2u.
2b
We state now one of the principal convergence results about Algorithm 2. In particular, we establish 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 a b Let S.t.
(6-(1-)))² 1-a
asup L
E) is nonnegative. Let 5 > S.t. for all n E N,
2bo
2b
8 S ant1 S min (sup: ag )
(6)
Then,
(i) the sequence (H₂) is nonincreasing and En ||pa In particular, lim Tn+1 - In - and lim V (((nn)
- 0 as n + +00.
(ii) For all n 2 1, minosksn-1 f < nb dc + l|pol?
(Hn-inf
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 of the parameter zx.
Comparison to gradient descent. A similar result holds for deterministic gradient descent. If is fix step size for gradient descent and there exist 0, E > S.t > 8 and 1 - >h > then ( see Appendix B.6) for n 2
2
[V S f(x0) inf ((xo) inf ny(1 2
min 0skEn-1
nde
When po 0 (this is the case for ADAM), the bound in Theorem 4.2 coincides with the gradient descent bound, up to the constant 4/12. 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 asup = (1 - 2x) < 2/L. Hence, under the boundedness of the effective step size, the algorithm have similar convergence guarantee gradient descent. Remark that the step size bound almost matches the classical 2/ upperbound on the step size of gradient descent. As it is already known for gradient descent, large step size, even if it is adaptive, harm the convergence of the algorithm.
4.2 STOCHASTIC SETTING
We establish similar bound in the stochastic setting, Let (E, G) denote measurable space and E N. Consider the problem finding a local minimizer of the expectation F F(x) := [xf(xx]) w.r.t. Rdd, where f Rd = IR is measurable map and f(., () is a possibly nonconvex function depending on some random variable &. The distribution of g is assumed unknown, but revealed online by the observation of iid copies (E,, n 1) of the r.v. &. For fixed value of &, the mapping I + [xx, 5) is supposed to be differentiable, and its gradient w.r.t. æ is denoted by v fxx E). We study stochastic version of Algorithm (2) by replacing the deterministic gradient Vf(xn) by fz En+1).
Theorem 4.3. Let Assumption 2.1 (for F) and Assumption 4.1 hold true. Assume the following bound the variance in stochastic gradients: ( Fxx))] o² for all E Rd

---

Under review as a conference paper at ICLR 2020
Suppose moreover that 1 - a < - 1. Let E 0 s.t. dsup == (1
(b-(1-a))
1-a - -
is
box
nonnegative. Let 8 s.t. for all 1, almost surely,
On ô S an+1 I min @sups
Then,
4 Ho inf nob2a
nu o²
Ilaooool
E
2
where 2,, is an iterate uniformly randomly chosen from ( In-1).
The proof is defered to the appendix. In the special case where there is no momentum in the algo- rithm (i.e. RMSPROP) and assuming that the gradients are bounded, a similar convergence rate is obtained Zaheer al. (2018, Thm. 1) (see Section 3.2).
CONVERGENCE RATE ANALYSIS UNDER THE KE PROPERTY
The KF. 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 al., 2017). In this section, we use methodology exposed in Bolte et al. (2018, Appendix) to show convergence rates based on the Kt. property. We modify it to encompass momentum methods. Note that although this modification was initiated in Ochs 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
IRd x TRd + defined for all z = (x, y) E Rdd x R2d by
H(=) H(: [(x) + 2b |1yl
Notice that Hn = [(x)) + 25 (an, p = H (In, Un) where (ym MnN is sequence defined for all N by yn VanPn.
Notations and definitions. If (F, d) is a metric space, 2 E E and a non-empty subset E, we use the notation d(z, A) [d( 2.2 )):
A}. The of critical points of the function H is defined by crit /1 := {z E Rdd s.t. (z) = 0}.
Definition 5.1. (Set of limit points) The set of all limit points of (#k)een initialized zo is defined by w(z)) = {a E 2d2d an increasing sequence of integers (ky (ey)een S.L + Eas + oo). Assumption 5.1. f coercive.
Lemma 5.1. (Properties of the limit point set) Let (zz)keN be the sequence defined for all & E N by 2 (2g, where y4 = aaPPk and (Ig, P&) is generated by Algorithm (2) from a starting point Zy- Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Then,
(i) ((2) ) is nonempty compact set. (zo) C critff = critf {0).
iiii) lim d( d(zz,w(z))
0.
k-++00
(iv) is finite and constant on (2))).
We introduce the KE. inequality which is the key tool of our analysis. We refer to Bolte et al. (2010) for an in-depth presentation of the KL property historically introduced by the fundamental works of Lojasiewicz (1963) and Kurdyka (1998).
Define Ja < 5] {2 2d
H() < 8) Let >> 0 and define
n) c) (0)) where CO v)) is the set of continuous functions on [0, .7) and (*,(0, 17) the set of continuously differentiable functions on (0, 17)
P (4p
0, >p concave and y > 0)
Definition 5.2. (KL property, Bolte et al. (2018, Appendix)) proper and lower semicontinuous
(Ls.c) function H R22d - (-o0, +oo] has the KE. property locally at z E dom H if there exist n > vp E 4, and neighborhood (2) s.t. for all E (3) n (H(3) H < H())+ + 7)
sp (((((=) H())) [+)[] 2
7

---

Under review as a conference paper at ICLR 2020
When (2) O, we can rewrite Equation (9) as VV Hz)2 2 1 for suitable points. This means that H becomes sharp under a reparameterization of its values through the so-called desingularizing function y. The function H is said to be a KL function if it has the Kł property at each point of the domain of its gradient. The Kt. property is satisfied by the broad class of semialgebraic functions including most objective functions in real applications (l) ||p for p rational, real polynomials, rank, etc.). (see Bolte et al. (2014, 4, Appendix) for more examples). KE inequality holds at any non critical point (see Attouch et al. (2010, Remark 3.2 (b))).
We introduce now a uniformized version of the Kt 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 : R2dd + (-xc, +ox be a proper Iss.c function. Assume that H is constant on Ω and satisfies the Kt. property each point of Ω. Then, there exist 0, n > 0 and yp E Q, such that
for all 2 Ω2 for all 2 E (2 E Rd d(z, < a) (H()) H < (2) + m), one has
of (H(2) - VH 21
(10)
Definition 5.3. (KE exponent) If sp can be chosen (p(s) = " for some ē E> 0 and 0 E (0, 1] in Definition 5.2, then we say that H has the KL property at 2 with exponent of 0 1, We say that H is a Kt. function with an exponent 0 if it has the same exponent at any E.
Furthermore, if H is a proper closed semialgebraic function, then H is a KE function with a suitable exponent 0 E (0, 1]. The slope of ip around the origin informs about the "flatness" of a function around point. Hence, the KE. exponent allows to obtain convergence rates. In the light of this remark, we state one of the main results of this work.
Theorem 5.3. (Convergence rates) Let (z&) be the sequence defined for all k N by 2 (Irs y&) where V/s Va&Ps, and (Iy, Ps)) generated by Algorithm (2) from a starting point 20- Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Suppose moreover that is a KE function with KE exponent 0. Denote by (xx)) the limit of the sequence (H (*x)) )een where x, is critical point of f. Then, the following convergence rates hold:
(i If 1. then f(*)) converges in a finite number of iterations. (ii) If 1/2 < 0 < 1, then f(xx) converges to f(x)) linearly i.e. there exist E 1), C 0 s.t. f(xx)= - ffxx) S Cq"
(iii) If0 < 0 < 1/2, then f(xx) - f(z.) = 0(k
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 KE inequality holds. This is achieved using the properties of the limit set (Lemma 5.1) and the uniformized KE 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 Appendix B.3.
We introduce lemma in order to make the KE 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 t with an exponent of 0 (0, 1/2). Then the function H defined in Equation (8) has also the KE property at (I,, 0) with an exponent of 0.
The following result derives convergence rate on the objective function values under KL assump- tion 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 (ex) be the sequence defined for all & E N by m = (æx, 9h) where y = VokP& and (IK, P&)) is generated by Algorithm (2) from starting point 2p- Let Assumptions 2.1, 4.1 and 5.1 hold true. Assume that Condition (6) holds. Suppose moreover that f is a KE function with Kt. exponent 0 E (0, 1/2). Denote by fxx.)) the limit of the sequence (H )seN where x.
is a critical point of f. Then f(*)) f(x.) = Ol:=-.)
1 0 is also defined as the KF. exponent in other papers (Li and Pong, 2018).
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
P-A. Absil, R. Mahony, and B. Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimizaation, 16(2):531-547, 2005.
N. Agarwal, B. Bullins, X. Chen, E. Hazan, K. Singh, C. Zhang, and Y. Zhang. Efficient full-matrix adaptive regularization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learming Research, pages 102-110, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http:/ http://pocceedeeee ngs m press v9 aga
9b. html.
H. Attouch and J. Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1-2):5-16, 2009.
H. Attouch, J. Bolte, P. Redont, and A. Soubeyran. Proximal alternating minimization and projec- tion methods for nonconvex problems: An approach based on the hurdyka-lojasiewic inequality. Mathematics of Operations Research, 35(2):438 457, 2010.
H. Attouch, J. Bolte, and B. F. Svaiter. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backer backward splitting, and regularized gauss- seidel methods. Mathematical Programming, 137((-2):91-129) 2013.
J. Bolte, A. Daniilidis, O. Ley, and L. Mazet. Characterizations of lojasiewicz inequalities: sub- gradient flows, talweg, convexity. Transactions of the American Mathematical Society, 362(6): 3319-3363, 2010.
J. Bolte, S. Sabach, and M. Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1-2):459-4444 2014.
Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd. First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal Optimization, 28(3):1131-215 2018.
L. Bottou, Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31,, 2018.
X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019. URL https: wwwpeeeeeewwe..cco///o/.. net forum?id-Hix xt0mxxxx39mmmmmmmmmmm
S. De, A. Mukherjee, and E. Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders. arXiv preprint arXiv: 1807.0680.. 2018.
J. Diakonikolas and M. I. Jordan. Generalized momentum- wooeettum-based methods: A hamiltonian perspec- tive. arXiv preprint
2019.
T. Dozat, Incorporating nesterov momentum into adam. 2016.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):212122155 2011.
P. Frankel, G. Garrigos, and J. Peypouquet. Splitting methods with variable metric for kurdyka- tojasiewicz functions and general convergence rates. Journal of Optimization Theory and Appli- cations, 165(3):874 900,,44--00000 2015.
V. Gupta, T. Koren, and Y. Singer. A unified approach to adaptive regularization in online and stochastic optimization. arXiv preprint 1xXxv:770.0633 2017.
R. Johnstone and P. Moulin. Convergence rates of inertial splitting schemes for nonconvex com- posite optimization. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4716-4720. IEEE, 2017.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization. In International Conference Learning Representations, 2015.

---

Under review as a conference paper at ICLR 2020
K. Kurdyka. On gradients of functions definable in o-minimal structures. In Annales de l'institut Fourier, volume 48, pages 769-783, 1998.
G. Li and T. K. Pong. Calculus of the exponent of tions to linear convergence of first-order methods. Foundations of computational mathematics, 18(5): 199-1232, 2018
inequality and its applica-
Qunwei Li, Yi Zhou, Yingbin Liang, and Pramod Varshney. Convergence analysis of proximal gradient with momentum for nonconvex optimization. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2111-2119 19. JMLR. org, 2017.
J. Liang, J. Fadili, and G. Peyré. A multi-step inertial bowaaddbbckweer splitting method for non- convex optimization. In Advances in Neural Information Processing Systems, pages 4035-4043, 2016.
L. Liu, H. Jiang, P. He, W. Chen, X. Liu, Gao, and J. Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv: /00.::6000.03265, 2019.
S. Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Les équations aux dérivées partielles, 117:87-89 1963.
L. Luo, Y. Xiong, and Y. Liu. Adaptive gradient methods with dynamic bound of learning rate. In International Conference on Learning Representations, 2019. URL https: openreview. net/forum? Eorum
Ma and D. Yarats. hupri-hyp momentum and adam for deep learning. In International Conference on Learning Representations, 2019, URL /wwp///eeeee.nneeeeee http://wwwwee/ffrurrrtee forum? id=S1 FUP
H. B. McMahan and M. Streeter. Adaptive bound optimization for online convex optimization. In COLT, pages 244-256, 2010.
Ochs. Local convergence of the heavy-ball method and ipiano for non-convex optimization.
Journal of Optimization Theory and Applications, 177(1):153-18) 2018.
Ochs, Y. Chen, Brox, and T. Pock. ipiano: Inertial proximal algorithm for nonconvex optimiza-
tion. SIAM Journal on Imaging Sciences, 7(2):1388 1419, 2014. doi: 10.1137/130942954, URL
https: http:///dooooogg//// wtt.://///0.1113//3999999999009
R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-1318, 2013.
B. T. Polyak. Some methods of speeding the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 4(5):1-17, 1964.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018. htthttps:// //tpn////e/eeeeeeee//// net www.enetttoooreooeeee forum? id-ryQu7f-- RZ.
H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statis- tics, pages 400-407, 1951.
H. Robbins and S. Monro. A stochastic approximation method. In Herbert Robbins Selected Papers, pages 102-109. Springer, 1985.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139-1147, 2013.
T. Tieleman and G. Hinton. Lecture 6.5 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. Coursera: Neural networks for machine learning, 4(2):2-31, 2012.
Z. Wu and M. Li. General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems. Computational Optimization and Applications, 73(1):129-15) 2019.
10

---

Under review as a conference paper at ICLR 2020
M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimiza- tion. In Advances Neural Information Processing Systems, pages 9793-9803, 2018.
D. Zhou, Tang, Z. Yang, Cao, and Q. Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 1808. 0567|, 2018.
Z. Zhou, Q. Zhang, G. Lu, H. Wang. W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. In International Conference on Learning Representations, 2019. URL https: / www.review.ee.e....ep..w...eww.e net forum? Hkg.kkkRKK
Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pages 11127-11135, 2019.
A APPENDIX A
A.1 PROOF OF LEMMA 4.1
Supposing that Vf is Lipischhiz, using Taylor's expansion and the expression of pn. in the algo- rithm, we obtain the following inequality:
L
f(xn+1) S f(xn) - (Vf(z,), 1n+1pm+1) + |nn+1Ptt1ll
(11)
Moreover,
2b (0++1, (an p2.)
1
1
2b (1 -
1
2b (ant1 On, P?))
1
(12)
2b
Observing that pa+ - ph. = (V - pn)) + +bbbn++11 ( (Vf(zn) - pn), we obtain after sim- plification:
T.
Hnt1 & H + ||antiPatal22 1| (ant1, (Vf(xx) ((nhh)))--))))----tthtttt pn)
26 (an-1 an pa)-
(13)
Using again Pa Pnt1 - b(V)f(xn) Pn), we replace Pr.
b Hnt1 Hn + L Ilanntipa+11 (ant1 (Vf(xn) (Vf(z) p)
1
-(ant1, + b(ant1Put1, vf(xn) pm) + (ant1 On, Ph)
2b
an, p.. < (1 a) p2) and using ph = p. + Under Assumption 4.1, write: (an+1 an
8² (V((((z) p.)² - (bp.+z(V((zn) Pn). it holds that:
Hat1 S H - (an+1, pht1) (a (Vf(xn) p2)
+ 1 Ilan+ 1p 112 (b- (1-a)) Vf(xn) pm)
1-a
b(1 (x) (ant1> (Vf(x,)) -P.))
+ 2h
(an+1,
p2
Using the classical inequality zy
<
x2 2y² we have
2n
|b (1 a)l
(an-1, P p b (1 a)lu
(b- (1-1aa))a 1P (V
-Pm) -
(an+1, (V(xx))PPa) p3.
2u
2
(14)
11

---

Under review as a conference paper at ICLR 2020
Hence, after using this inequality and rearranging the terms, derive the following inequality:
Hnt1 S Hn (an+ 1io+1Pp+1:11 an+1L
66 (1 a)l
1 1 a
2
2u
2h
b (ontt
(1
1 1b - a))l
pn)?
(1 10-0 a) 1).
2
This concludes the proof.
A.2 AN ADDITIONAL PROPOSITION
Proposition A.1. Let Assumption hold true. Suppose moreover that -a < S Let is nonnegative. Let d >> s.t. for all N.
asup 2 (1
(b-(1-a))²
I-a
2ba
an )
an+1 S min Asup:
Then, for all n 2 1,
4
Ho inf f
(ok+1, Vf(xx)3) S Pa
+ (ao, po))
E
Proof. This a consequence Lemma 4.1. Conditions Ant1 2 E and B 2 0 write as follow
2 (1 b (1 an+1 S L
1 a
ab
and < b - a)
2u
26
We get the assumption made in the proposition by injecting the second condition into the first one and adding the assumption dntt
da S made in the lemma. Under this assumption, we sum over < n Equation (5), rearrange and use Ant1 2 E, 2 0 to obtain
(0x+1, S Ho Hn,
Then, observe that H, f(x)) 2 inf f. Therefore, derive
( 5 Ho inf f
(15)
Moreover, from the Algorithm 2 second update rule, get vf(xx) have for all 2 0:
1/p4111 1-0 ps. Hence,
(
(1-b)2
b)2
2
2 =2
p +
53 ph
<
(Ph+1 + +12)
b
12

---

Under review as a conference paper at ICLR 2020
We deduce that
R
2 n-1
Σ
(axt1,
))(
<
ak+1, (i+11,Pi+1 Ph + +pk)
b²
2
n-1
ax+1 Pk++1) +
2 n-1
Σ
(a++1. pk)
6²
R=
k=0
2
2
(ak+1,Pk+ll pk+1)
+
(ak:Pá)
62
B2a
k=0
k=0
2
2
(aks pk)
(an, phn) (10: Po)
P
k=1
4
(ax. (k)
12a
k=0
4
Ho inf f
+ (au. pâ)
A.3 PROOF OF THEOREM 4.2
This is a consequence of Lemma 4.1. Conditions An+1 2 E and B 2 write as follow:
2 (1 6 (1 (1-a) 0n+1 S T,
1
ab
and u S b (1-a)
2u
2h
We get the assumption made in the proposition by injecting the second condition into the first one and adding the assumption dxt1 I a made in the lemma. Under this assumption, we sum over
0 < k < n - Equation (5), rearrange it and use An+1 2 B > 0 and dx+1 2 5 to obtain
12 S Hy Hn, Σ E8 11
Then, observe that Hn 2 f(x)) 2 inf f. Therefore, we derive:
Ho inf
(16)
de
Moreover, from the algorithm second update rule, we get vf(xx) = 1 1-0pe. Pk- Hence, we have for all & 2 0:
| 2 (fe + (1 - b)2
llpall? 1
82 (11p6+111= +11x)1?))
2
b²
We deduce that
2 1
4
V f((x)))
<
2
1lp + 11p.112 + |l
||
12
6z
k=
k=0
k=1
k==
(17)
Finally, using Equations (16) and (17), we have
4 (
Ho inf
min 0Ck5n-1
[
<
[f(xx))
+ l120112)
no²
85
k=
13

---

Under review as a conference paper at ICLR 2020
A.4 PROOF OF THEOREM 4.3
The proof of this proposition mainly follows the same path as its deterministic counterpart. How- ever, due to stochasticity, 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.I, we obtain by re- placing the deterministic gradient (zx,) by its stochastic estimate V (=n)
Hnt1 S Hn (an+1P an+
1b (1 -a]]
2u
2b
1 (1 -a)]u (1 - a) 1)
- -pn)?
b
(VI(nn, En+1) (F(n))) an+ an+1Pn+1).
(18)
=² Using the classical inequality xy I + 4 and the almost sure boundedness of the step size dx++ we get:
(Tin Sa+1) (F(n)) an-an-1100 12241)111112-- S (V (Vs En+1) V p 12 un+1)
asup
Vf En+1) VF(x)) ( P
s
2
Therefore, taking the expectation and using the boundedness of the variance, we obtain from Equa- tion (18):
[[ [[ < -E (on+1ph-11,1
an+iL
|b - (1 a)l
a
Asup
2u
2b
2
Then, the proof follows the lines of Appendix A.2. Hence, have
H - E[Hn] < -E [(nnt1Ph+t + Asupo?
2
We sum these inequalities for k O. ... ,n and rearrange the terms to obtain
Hu - inf nasupo
E
(
8
28
Then following the derivations in Appendix A.2 using V (((,, lish the following inequality
tpx+1 1 Ps. we estab-
4 b2aa
Ho inf
+ (ao. po) + na
E
(a4+1, 11
<
2s
Finally, we apply Jensen's 's inequality to || 11, we inject the assumption an+1 2 and we divide the previous inequality by to obtain the sought result
< nob2a ( Ho inf
na
VF
+ (av, pā) +
7
2
14

---

Under review as a conference paper at ICLR 2020
B APPENDIX B
B.I CONDITIONS SIMILAR TO "GRADIENT-LIKE DESCENT SEQUENCES" CONDITIONS (BOLTE AL., 2018, (PPENDIX)(OCUS ET AL., 2014)
Lemma B.I. Let (#N) be the sequence defined for all & E N by = (Ite y&) where ys Vappa and (Kk, Pa) is generated by Algorithm (2) from a starting point 20- Let Assumptions 2.1 and 4.1 hold true. Assume moreover that condition (6) holds. Then,
(sufficient decrease property) There exists a positive scalar p
H (z++1) 11 (zx) < -PI || (ii) There exists positive scalar P2 s.t.
xxl
Vk E.
[+++1))) S P2 (1]=++1 xxll + || xk-1ll) Wk 2 1.
(iii) (continuity condition) If z a limit point of a subsequence (zk, )je,, then lim H(z,)) j-++oc
=
(=))
Remark 1. Conditions in Bolte al. (2018, Appendix) corresponding Lemma B.1 are more general. Authors consider nonsmooth objective function and introduce the Fréchet subdifferential instead of the gradient. For our purposes, this is sufficient.
Proof.
From Lemma 4.1 and theorem 4.2, we get for all N:
Tk+1 J.
H ((2x+))-((z)) - - pk+1) -e(ax+1,
)
| xxl1?.
-0++1
asup
We set := Goup"
(ii First, observe that for all k E N
|[H((=+)1)| s [*+((+)))] + ||
(19)
Now, us upperbound each one of these two terms. Recall that we can rewrite our algorithm
under salvy-ball"-like form as follows:
F+++1 3. (xx) + Ba( - xR-1) 4k: 2 1.
where og = box+1 and fBg = (1 - b) ds+1 are vectors.
On the one hand,
$ V (//p=)))))// (L-Lipschitz continuity of the gradient) [V/(=++)|| 5
2 (I? |, xx [
Moreover,
[
Th Tk+1
BK
(In xZ-1)
Ok
Ok
Fk 1k+1
1 -
2
+
(Øx xk-1
ba
b aj.
2
2(1 b)²
<
||
xx 112
|| 2k 11
1282
8282
2
<
(1|24411
x2
+ || 11²)
1282
15

---

Under review as a conference paper at ICLR 2020
Hence,
[V((=+))
2 =xxl2 +
2
2
1,2
|
8282 3 x6 112
1182
2
2
I,2
(|] xxll² + 11:08 5k- 112)
82822
Therefore, the following inequality holds
[V[(<++)|| & 2
1,2 +
(1 xxll + 11000 Ik xk)-
6252
On the otherhand,
Ik+1 26
|| [Vo++1p++1
|,0+1 xull-
/ak+1
Finally, combining the inequalities for both terms in Equation (19), we obtain
V+(+++1)) [=*++)]| S
122051221aaaaa p2[1 - x&ll + || - xk-1ll) Vk 2 1.
with P2 = 2 -+ b/8
(iii) This is a consequence of the continuity of H.
B.2 PROOF OF LEMMA 5.1
(i) By Theorem 4.2, the sequence (H(zx) ))n nonincreasing. Therefore, for
N. (=z.) < (=o) and hence 2n E {=: (2) S H(zo)}. Since J is coercive, H is also coercive and its level sets are bounded. As a consequence, (an)neN bounded and there exist 2 E Rd and subsequence (EEN s.t. 2h, 2, as j + co. Hence, w(2o) & 0. Furthermore, w(20) = NuENN Uk2Ø [= is compact as an intersection of compact sets. sets.
iii) First, critH fritf x {0} because VH(2) (f)) y/b)T. Let E w(2)). Recall that Ik+1 2g - 0 as & - oo by Theorem 4.2. We deduce from the second assertion & co. As 2, E w(2)). there exists subsequence (zz, )se converging to z.. Then, by Lipschitz continuity of VH, we get that VH + and (=H()a)))sen
of Lemma B.1 that V (z()))
VH as j - xo. Finally, VH((.)) 0 since VH(zz) subsequence of (2H(2)))nEN
(iii) This point stems from the definition of limit points. Every subsequence of the sequence converges to zero consequence of the definition of w(o).
(iv) The sequence (H(zn)) is nonincreasing by Theorem 4.2. is also bounded from below because (xxx) 2 f(xx) > inf for all E N. Hence can denote by its limit. Let E w(z).. There there exists a subsequence JjeN converging to z as j + oc By j--
the third assertion of Lemma B.1, lim Hzx,)) H()). Hence this limit equals since
(Z,)))ne converges towards I. Therefore, the restriction of H to w(z)) equals 1.
B.3 PROOF OF THEOREM 5.3
The first step of this proof follows the same path as Bolte et al. (2018, Proof of Theorem 6.2, Appendix). Since f is coercive, H is also coercive. The sequence (H(*z) ([(=R)))N is nonincreasing. Hence, (zx) bounded and there exists subsequence (Zk,)eeN and E RR2d s.t. 2k, -> as q - Then, since (H (Zx)) is nonincreasing and lowerbounded by inf f. is convergent and we obtain by continuity of H,
lim H(zx) H()).
(20)
k-+0000
16

---

Under review as a conference paper at ICLR 2020
If there exists & E N s.t. H(zx) H(),, then (2*+1) ( and by the first point of
Lemma B.I, 2k+1 zg and then (oR) is stationary and for all & 2 k, H(*x) H(z) and the results of the theorem hold in this case (note that ž E critH by Lemma 5.1). Therefore, we
assume now that (2) (zz))bk: > 0 since (H*))))eN is nonincreasing and Equation (20)
holds. One more time, from Equation (20), we have that for all > 0, there exists ko E N s.t. (=x) (=) + 7) for all k ko. From Lemma 5.1, we get ((D)) - 0 as + 400. Hence, for all > O, there exists h1 s.t. d (zo)) < for all k >> k1 Moreover, w(2o) is and H is finite and constant on it. Therefore, we can apply the uniformization Lemma 5.2 with ? = w(z)). Hence, for any k > I = max(kg. K1), we get
nonempty compact
('(((z)) H()))² (*+)) 21.
(21)
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 2 1,
2p
[V( S 2p (1|*4+1 2xll + | Fk-
H 2R (2k-1) H(2++1))
P1
Injecting the last inequality Equation (21), we obtain for all k > l22 == (1.
2p o (H(=)) - (H( - H(zx)) 21.
P1
Now, use (s() 01 to derive the following for all k K2:
(H(2k-2) H()] (H())) H())] 2 P1
H(2)) - (()))((1-0)
(22)
2p
01 Letra := (=x))- (z) and C₁ 2p p. Then, we can rewrite Equation (22) as
2(1-0)
rk-2 rk Cirk
vk hg.
(23)
We distinguish three different cases obtain the sought results.
(i) 0= ==
Suppose тı > for all > 12. Then, since we know that rı -> 0 by Equation (20), C1 must be equal to 0. This is contradiction. Therefore, there exist ks E N s.t. F& = 0 for all k: > hs (recall that (Fa)eeN is nonincreasing).
(ii) 0 2
As rk + 0, there exists ha N s.t. for all ls 2 ka: T& S 1. Observe that 2(1 - 0) S 1 and hence r 2 Cirk for all k > ko and then
Th S (1 + C1) rk-2 S (1 C11-P1PP
(24)
where P1 = | Notice that p1 > k- Thus, the linear convergence result follows. Note also that i 1/2, 2(1
2
1 and Equation (24) holds for all k > lz.
(iii) 0< {
Define the function h by h(t) D 28-1 where D >>> 0 is constant. Then,
1-20
h(rx) - h((k-2) = 1 J
ht(t)dt= D Jm 20- dt 2 D Dr - -22) 28-2
We disentangle now two cases:
(a) Suppose 20-2- 2 r
20 Then, by Equation (23), we get
C1 D
h((k)) h(rk-2) = D (rx-2 Tx)
r
28-2
2
(25)
2
17

---

Under review as a conference paper at ICLR 2020
(b) Suppose now the opposite inequation 2r
T 20-2 We can suppose without loss
of generality that rkK are all positive. Otherwise, if there exists such that 7p = 0, the sequence (Fk)ReN will be stationary at 0 for all k 2 p. Observe that 20 2 < 20 - 1 < 0,
thus 28-1
0. As a consequence, we can write in this case -00-1 gr where
28 2
q := 2 1. Therefore, using moreover that the sequence (rk)KeN nonincreasing
and 20 < O, we derive the following
D 20
D
D
h(rx)) h(rx))h((k-2)) 1
20
20
20 1 (q (g-1)mk=2
(q 1)r
20-1 = C2.
1-20
2-2
1 1-20
(26)
Combining Equation (25) and Equation (26) yields h(rx) 2 h(rx-2) + C3s where C3 ==
min(C2. C P) Consequently, h(rk) 2 h((k-2p2) + P2 C3 where P2 = 8-k2
We
deduce from this inequality that
h(rx) 2 M((+)) h(rk-2 2p2) 2 p2 C3.
Therefore, rearranging this inequality using the definition of h, we obtain rk 11-20 s D
1-20 (Cap2)-* Then, since p2
2-
k - 1/2 - 2 28 I
Th S C1P2
S C₁
2
where C₁ := CC (1-29) 26-1
D
We conclude the proof by observing that f(*x) (zx) and recalling that 2 critH.
B.4 PROOF OF LEMMA 5.4
Since f has the KL property at a with an exponent 0 E (0,1 there exist e, and v > 0 s.t.
[V -o 2 cff f())
(27)
for all H s.t. || =|| Se and f(x) f()) + v where condition f(z) fxx is dropped because Equation (27) holds trivially otherwise. Let z (z, y) E R2dd be s.t. || El| S E, |lvil S
and (H, 0) < H (z. 3) < H (I, 0) +v. We assume that < b (e can be shrunk if needed). We
have f(x) H v) H 0) + v = f(z) + v. Hence Equation (27) holds for these x.
By concavity of u + কাं we obtain
[H( Co (1V
where Co : 22(1-)
Hence, using Equation (27), we get
[ 2 Co (c(S()))(E)) 1 )+)
Observe now that - > 2 and | S 5 5. Therefore, =| /1126/12
Finally,
(((())) - f())) + 2 1
w'1l 2 Co
b 2b |0>
2) (s(z) - f(x) +
1
2 Co min
(
|1
2b
2 (H(x,)) - H(T, 0))
= Co min
( b
This completes the proof.
18

---

Under review as a conference paper at ICLR 2020
B.5 COMPARISON TO OCHS ET AL. (2014)
We recall the conditions satisfied by on and Bn in Ochs et al. (2014) in order to traduce them in terms of the algorithm (2) stake. Define
L
8m
Yn = On Bn
6n
On 2
20h
20n
Conditions of Ochs et (2014) write: Oh e1 An 2
8n 2 7n 02 where Cı, 02 are positive
constants and (6,) is monotonically decreasing.
One can remark that algorithm (2) can be written as (4) with step sizes on ban+1 and inertial fut1 Conditions on these parameters can be expressed in terms of ax.
parameters 8n, (1 b) on
Supposing = 0, the condition C2 is equivalent to
an+1 <
2
(28)
b(2 a, Note that the classical condition dn S 2/T. equivalent to
On
shows up consequently. Moreover, the condition on (6.)
1
b
for
n 2 1.
(29)
On+1
2 On
2a.-1
Note that we get rid of condition (29) while allowing adaptive step sizes an (see Proposition A.1).
B.6 A CONVERGENCE RESULT FOR GRADIENT DESCENT IN THE NONCONVEX SETTING.
Consider the gradient descent algorithm defined by: 2*+1 IA (xxx). Assume that y and 24 0.
Supposing that V is -- Lipscchii using Taylor's expansion and regrouping the terms, we obtain the following inequality:
((x+t) ((xx) -7 (1- 74 2 [VV](ax)
Then, we sum the inequalities for 0 < k S 1. lower bound the gradients norms in the sum by their minimum and we obtain:
f(x0) inf ny(1 2
min ocksn-1
|V [+
B.7 ABOUT THE KE-PROPERTY
simple example for more intuition. For building intuition, let consider the 1D function defined by g(x) = | for 2 as exposed in Johnstone and Moulin (2017). The function (p(t) = / is desingularizing function. When is flat around the origin (large p), gradient methods are slower to converge. Therefore, a smaller KI. exponent encodes slower convergence behavior near critical point.
Remark 2. Definition 5.2 can be generalized to a nonsmooth function by introducing the notion of the Fréchet subdifferential (which is set) and replacing the norm by the distance set.
19


Reviews:
[{"review_id": "SJxODyRTtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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”.\n\nI summarize my comments step by step below:\n\nI 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.\n\nZaheer 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.\n\nDefinition 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.\n\nFollow up comment: How would one apply this method to neural networks, or any class of problems where Lipschitz constant is virtually unknown?\n\nConvergence 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.\n\nConvergence 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.\n\nI 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.\n\nConvergence 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?\n\nOverall, 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.) \n\nI 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1exRRr0FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work analyzes the performance of ADAM algorithm under a bounded step size assumption. it proves convergence rate for the deterministic setting and prove a convergence result for the stochastic setting.\n\n\nHowever, I have a few concerns as follows. The first two comments are the major reasons of my rating.\n1. the convergence in Theorem 4.2 is not standard. It is about \"the minimum of the gradients norms\", which does not imply the algorithmic convergence. it should be more clearly stated in the introduction.\n2. The author should include simulations to show whether the theoretical result matches the empirical performance, for both deterministic setting and stochastic setting.\n\n3. Small comment: In section 2, g_i should be a d-dimensional vector since it is the gradient of f. But then what is g_i^2?\n4. For comparison, can you set b=1 and compare with the existing theoretical results of RMSPROP?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlNQLdatS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides convergence analyses for momentum methods using adaptive step size for non-convex problems under a bounded assumption on learning rates. Concretely, a sublinear convergence rate under a general setting and improved convergence rates under KL-condition are provided.\n\nAn interesting point of the paper is that (i) the boundedness assumption on the domain or gradient is not required and that (ii) shows faster convergence rates under KL-condition for non-descent methods. However, a major concern is a uniform boundedness assumption on learning rates. A lower bound is a matter because this condition is verified a posteriori after running methods. This kind of condition is not preferred in general. Indeed, most studies provide convergence analyses without such assumptions. In addition, there are several missing references (listed below) that attempt to analyze the convergence of adaptive methods. To make the position of the paper clear, it would be better to provide a theoretical comparison with these studies. Especially, [LO2019] and [XWW2019] are related to this study. [LO2019] has provided convergence analyses without boundedness assumptions on the domain or gradient and [XWW2019] has provided a linear or better convergence rate of an adaptive method by utilizing the KL-condition. Note that a method treated in [XWW2019] is also a non-descent method because there is no theoretical limitation on the initial step size.\n\n[WWB2018] X.Wu, R.Ward, and L.Bottou, WNGrad: Learn the Learning Rate in Gradient Descent. arXiv, 2018. \n[WWB2019] R.Ward, X.Wu, and L.Bottou. AdaGrad Stepsizes: Sharp Convergence Over Nonconvex Landscapes. ICML, 2019.  \n[XWW2019] Y.Xie, X.Wu, and R.Ward. Linear Convergence of Adaptive Stochastic Gradient Descent. arXiv, 2019. \n[Levy2017] K.Y.Levy, Online to Offline Conversions, Universality and Adaptive Minibatch Sizes. NIPS, 2017.\n[LYC2018] Y.K.Levy, A.Yurtsever, and V.Cevher, Online Adaptive Methods, Universality and Acceleration, NeurIPS, 2018.\n[LO2019] X.Li, and F.Orabona. On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes. AISTATS, 2019.\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have reached consensus that while the paper is interesting, it could use more time.  We urge the authors to continue their investigations.
Decision: Reject