Closing the gap between the upper bound and lower bound of Adam's iteration complexity
Authors: Bohan Wang
Jingwen Fu
Huishuai Zhang
Nanning Zheng
Wei Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Adam
Convergence
Upper Bound
Lower Bound
TL;DR: We prove an upper bound of Adam's iteration complexity, which meets the lower bound for the first time.

Abstract: Recently,  Arjevani et al. [1]  establish a lower bound of iteration complexity for the first-order optimization under an $L$-smooth condition and a bounded noise variance assumption. However, a thorough review of existing literature on Adam's convergence reveals a noticeable gap: none of them meet the above lower bound. In this paper, we close the gap by deriving a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our results remain valid across a broad spectrum of hyperparameters. Especially with properly chosen hyperparameters, we derive an upper bound of the iteration complexity of Adam and show that it meets the lower bound for first-order optimizers. To the best of our knowledge, this is the first to establish such a tight upper bound for Adam's convergence. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate and to convert the first-order term in the Descent Lemma to the gradient norm, which may be of independent interest.

Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity
Bohan Wang Jingwen Huishuai Zhang? Nanning Zheng"! Wei Chen bhwangfy @ gmail.com
Nanninn
ful37 12520669 stu.xjtu.edu.en
huzhang @ microsoft.com com nnzheng mail.xjtu.ee kjtu.edu.cn chenwei2022 @ icct.ac.cnn
University of Science and Technology of China, 2Xi'an Jiaotong University,
Microsoft Research, "Institute of Computing Technology, Chinese Academy of Sciences
Abstract
Recently, Arjevani al. [1] establish lower bound of iteration complexity for the first-order optimization under an L-smooth condition and bounded noise variance assumption. However, thorough review of existing literature Adam's convergence reveals noticeable gap: none of them meet the above lower bound. In this paper, we close the gap by deriving new convergence guarantee of Adam, with only an L-smooth condition and bounded noise variance assumption. Our results remain valid across a broad spectrum of hyperparameters. Especially with properly chosen hyperparameters, we derive upper bound of iteration complexity of Adam and show that meets the lower bound for first-order optimizers. To the best of our knowledge, this is the first to establish such tight upper bound for Adam's 's convergence. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate and to convert the first-order term in the Descent Lemma to the gradient norm, which may be independent interest.
1 Introduction
First-order optimizers, also known as gradient-based methods, make use of gradient (first-order derivative) information to find the minimum of function. They have become cornerstone of many machine learning algorithms due to the efficiency as only gradient informaiton is required, and the flexibility as gradients can be easily computed for any function represented as directed acyclic computational graph via auto-differentiation [2, 25].
Therefore, it fundamental to theoretically understand the properties of these first-order methods. Recently, Arjevani et al. [1] establish lower bound on the iteration complexity of stochastic first- order methods. Formally, for a well-studied setting where the objective is L-smooth and stochastic oracle can query the gradient unbiasly with bounded variance (see Assumption 1 and 2), any stochastic first-order algorithm requires at least -4 queries (in the worst case) find an e-stationary point, i.e., point with gradient norm at most e. Arjevani et al. [1] further show that the above lower bound is tight matches the existing upper bound of iteration complexity of SGD [15].
On the other hand, among first-order optimizers, Adam [20] becomes dominant in training state- of-the-art machine learning models [3, 18, 11]. Compared vanilla stochastic gradient descent (SGD), Adam consists of two more key components: (i) momentum to accumulate historical gradient
"qqual Contribution
Conrespondigg Authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

information and (ii) adaptive learning rate to rectify coordinate-wiss step sizes. The psedo-code of Adam is given as Algorithm 1. While the sophisticated design of Adam enables its empirical superiority, it brings great challenges for the theoretical analysis. After examining a series of theoretical works on the upper bound of iteration complexity of Adam [33, 9, 10, 36, 16, 27, 34], we find that none of them match the lower bound for first-order optimizers: they not only consume more queries than the lower bound to reach e-stationary iterations but also requires additional assumptions (see Section for detailed discussion).
This theoretical mismatch becomes even more unnatural given the great empirical advantage of Adam over SGD, which incites us to think:
Is the gap between the upper and lower bounds for Adam a result of the inherent complexity induced by Adam's design, or could it be attributed to the proof techniques not being sharp enough?
This paper answers the above question, validating the latter hypothesis, by establishing new upper bound on iteration complexity of Adam for wide range of hyperparameters that cover typical choices. Specifically, our contribution can be summarized as follows:
We examine existing works that analyze the iteration complexity of Adam, and find that none of them meets the lower bound of first-order optimization algorithms:
We derive convergence guarantee of Adam with only assuming L-smooth condition and bounded variance assumption (Theorem 1), which holds for a wide range of hyperpa- rameters covering typical choices;
With chosen hyperparameters, we further tighten Theorem 1 and show that the upper bound on the iteration complexity of Adam meets the lower bound, closing the gap (Theorem 2). Our upper bound is tighter than existing results by a logarithmic factor, in spite of weaker assumption.
To the best of our knowledge, this work provides the first upper bound on the iteration complexity of Adam without additional assumptions other than L-smooth condition and bounded variance assumption. It is also the first upper bound matching the lower bound of first-order optimizers.
Organization of this paper. The rest of the paper is organized as follows: in Section 2, we first present the notations and settup of analysis in this paper: in Section 3, revisit the existing works on the iteration complexity of Adam; in Section 4, we present a convergence analysis of Adam with general hyperparameters (Theorem 1); in Section 5, tighten Theorem I with chosen hyperparameter, and derive an upper bound of Adam's 's iteration complexity which meets the lower bound; in Section 6, we discuss the limitation of our results.
2 Preliminary
The Adam algorithm is restated in Agorithm 1 for convenient reference. Note that compared to the orignal version of Adam in Kingma and Ba [20], the bias-correction terms are omitted to simplify the analysis, and our analysis can be immediately extended to the original version of Adam because the effect of bias-correction term decays exponentially. Also, in the original version of Adam, the adaptive learning rate is +T++ instead of n / However, setting is more challenging and our result can be easily extend to the original version of Adam, since the À term makes the adaptive learning rate upper bounded and eases the analysis.

---

Algorithm Adam
Input: Stochastic oracle O, learning rate > 0, initial point wi R initial conditioner Mu
initial momentum my, momentum parameter 81, conditioner parameter 32, number of epoch T
Sample r Unif
2: For f = 1 + T::
3: Generate a random 2t, and query stochastic oracle gt -O,(w;, 21)
4: Calculate P, 321411 + (1 32)g
5: Calculate m, 81m,
81)g
6:
Update Wi+1 = uh 1) vpc & m
7: EndFor
Output:
........,..66.. 16.,a+............ w, Rd, denote w O v as the Hadamard product (i.e., coordinate-wiss multiplication) between w and v. When analyzing Adam, we denote the true gradient at iteration as G. = V [((w),, and the sigma algebra before iteration l as Fr aggi. ,9:-1). 1). We denote conditional expectation as (+) F() We also use asymptotic notations O, S2 and O, where ha(ar) Ox-azo (hu (a))
Notations. For a, E z and a S b, denote 6] a
For any two vectors
means that lim Byy (x)
0 (when the context is clear, we abbreviate x + zo and only use o(h1(z))); h2(x)= = Oh1 (x)) means that there exists constant independent of æ such that (2(2) s
hy(#)
(h)( (x) (h (x)) means that h (x) (hh((z)); and h2(x) (hh, (2)) means that
h2(x) = (h1(()) and h2(x) = 22h (r)).
Objective function. In this paper, consider solving the following optimization problem: min f(w). We make the following assumption on the objective function f.
Assumption (On objective function). We assume f to be non-negative. We further assume that satisfies L-smooth condition, i.e,, f is differentiable, and the gradient of f is L-Lipschitz.
We denote the set of all objective functions satisfying Assumption 1 as F(L).
Stochastic oracle. As f is differentiable, we can utilize the gradient of (i.e., Vf) to solve the
above optimization problem. However, the Vf is usually expensive to compute. Instead, we query stochastic estimation of V through a stochastic oracle O. Specifically, the stochastic oracle O
consists distribution P over a measurable space 2 and a mapping O, :Rd x 2 Rd. We make the following asssumption on O.
Assumption 2 (On stochastic oracle). We assume that is unbiased, i.e., Ve Rd E (w, 2) f((w). We further assume O has bounded variance, i.e., Vw E Id Eg-p ||]0 (w, =) ([(w))
We denote the set of all stochastic oracles satisfying Assumption 2 with variance bound o² D(a²).
Algorithm. Adam belongs to first-order optimization algorithms, which is defined as follows:
Definition 1 (First-order optimization algorithm). An algorithm A is called firstorder optimization algorithum, if takes an input w and hyperparameter 6, and produces sequence of parameters as
A(O) follows: first sample a random seed r from some distribution P, set w w and then update the parameters as
A(0) = At(r, w/ A(0) w++1
O A(0)
Al) A(O) (0 x)),
where 21, 22," " 2t are sampled i.i.d. from P.
Iteration complexity. Denote the set of all first-order optimization algorithms as Agrst- We next introduce iteration complexity to measure the convergence rate of optimization algorithms. Definition (Iteration complexity). The iteration complexity of first-order optimization algorithm A is defined as
C(A
sup inf (T (T: / A(0) se). OED(a") FEF(L) wi:f(w))=d
sup
sup
"Such a random seed allows sampling from all iterations to generate the final output of the optimization algorithm. As example, Algorithm sets P, uniform distribution over [?']

---

Furthermore, the iteration complexity of the family ffrst optimization algorithms Anzst is
C²( sup
sup OED(a2) (L)
inf ww = AEA
sup
inf V A( S E
should be noticed that the iteration complexity of the family of first-order optimization algorithms is lower bound of the iteration complexity of specific first-order optimization algorithm, i.e., AA E Afirst, C. (A, L, 2 C,(A,L,
3 Related works: none of existing upper bounds match the lower bound
In this section, we examine existing works that study the iteration complexity of Adam, and defer discussion of other related works to Appendix Specifically, we find that none of them match the lower bound for first-order algorithms provided in [1] (restated as follows).
Proposition 1 (Theorem 3, [1]. A,, O, we have Co 1.)) = (
Note that in the above bound, we omit the dependence of the lower bound over A, L, and o², which is a standard practice in existing works (see Cutkosky and Mehta [8], Xie et al. [32], Faw et al. [13] examples) because the dependence over the accuracy can be used to derive how much additional iterations is required for smaller target accuracy and is thus of more interest. In this paper. when we say "match the lower bound", we always mean that the upper bound has the same order as the lower bound.
Generally speaking, existing works the iteration complexity of Adam be divided into cate- gories: they either (i) assume that gradient universally bounded or (ii) make stronger assumptions on smoothness. Below respectively explain how these two categories of works do not match the lower bound in [1].
The first line of works, including Zaheer et al. [33], De et al. [9]. Défossez al. [10], Zou al. [36], Guo et al. [16], assume that the gradient norm of f universally bounded, i.e., [V/(w))] s G, Ve E Red. In other words, what they consider is another iteration complexity defined as follows:
CAA,,,,,,0,,0 A sup OED(6") JEF(L))) SIl (f
sup inf (T : [ (()) S s
sup
This line of works do not match the lower bound due the following two reasons: First of all, the upper bound they derive is O (00_1//)) which has an additional log 1/s factor more than the lower (oo2,G) G). Note that F(L)n [V < G} bound; secondly, the bound they derive is for C. (A, A, o²
is a proper subset of F(L) for any G. where simple example in F(L) but without bounded gradient the quadratic function f(x) = |>|| Therefore, we have that
CA L o²) C, L, G), VG 2
and thus the upper bound on C_ A, L, 0² G) does not apply to (A, L, Moreover, their upper bound of (A, , A, L, 0² G) tends to oo as G + 0o, which indicates that if following their analysis, the upper bound C. (A, A, L, o²) would be infinity based on Eq. (1).
The second line of works [27, 34, 30] additionally assume a mean-squared smoothness property besides Assumption and 2, i.e., R.-p ( ( 2) - Oy, x) < [ - o1|2. Denote 5(o², L.) e {O E.-pllO (w, 0, 12 < L|w 1 Vw, v E (o) The iteration complexity
that they consider is defined follows:
(A,
sup in V |00) Se). O) FEF(L w
sup
sup
The rate derived in [27, 34, 30] is 0 log 1/e which is derived by minimizing the upper bounds in [27, 34, 30] with respect to the hyperparameter of adaptive learning rate 82 According to Arjevani et al. [1], the lower bound of iteration complexity of (, A, L. L,) is Ω and smaller than the original lower bound Q ) resulting in even larger gap between the upper and lower bounds.

---

Recently, there is a concurrent work [21] which does not require bounded gradient assumption and mean-squared smoothness property but poses stronger assumption on the stochastic ora- cle: the set of stochastic oracles they consider is 5 = {o Yw E Rd, Bew =) = ff(w), (1),((,, 2) f((w) <<² = 1}. Ô is a proper subset of D because simple example is that O,(w, 2) = f + 2 where is standard gaussian variable. Therefore, their result does not provide valid upper bound of C. (A A, L,
4 Convergence analysis of Adam with only Assumptions 1 and 2
As discussed in Section 3, existing works analyzing Adam require additional assumptions besides Assumption and 2. In this section, we provide the first convergence analysis of Adam with only As- sumption I and 2, which naturally gives upper bound on the iteration complexity Cg ( (A, A, L, o²). In fact, our analysis even holds when the stochastic oracle satisfies the following more general assumption.
Assumption 3 (Coordinate-wise affine noise variance). We assume that O is unbiased, i.e., Yw E Rd Ez (w, z) = V((w). We further assume O has coordinate-wise affine variance, i.e., Vw E Idd and Vi E [d]. 12-p [.--]1(O)(w, ()), S oă + o
One can easily observe that Assumption is more general than Assumption 2 since Assumption 2 immediately indicates Assumption 3 with op = a and Ø1 1. We consider Assumption 3 not only because it is more general but also because it allows the noise to grow with the norm of the true gradient, which is usually the case in machine learning practice [14, 19].
Our analysis under Assumption I and Assumption 3 is then given as follows.
Theorem 1. Let A be by Adam (Algorithm 1) and 0 = (17 31, 32) are the hyperparameters of A. Let Assumption I and 2 hold. Then, i S 31 S /B2 - 8o - 32) and B2 < 1, we have
[f((w))] S C2 221 Σ
d
In 2(T 1) Σ
d
vo.1 + + 24d 24d
0
In
0
12o
C2
V32
3
BB²
2(T++) Σ V Man + oB 24d
99 VBz
Ind
90
12
Cz.
(2)
V
v D2
where Voss is the i-th coordinate of vo-
C (1 32) (1
32Ln (1+ B1
v/TE
BIVI
16pfoo(1 - B1)
B2 -1
3
38 (1
64(1 + o
0011 B2)
//2
C2 1- f(u1) +
vP2
32
C
20
Σ In 1
)
T Iu B2
82 (1
v9
proof sketch is given in Section 4.2 and the full proof is deferred Appendix.
The rinht-hand side in Eq. (2) looks messy at the first glance. We next explain Theorem I in detail and make the upper bound's dependence over hyperparameters crystally clear.
4.1 Discussion on Theorem 1
Required assumptions and conditions. As mentioned previously, Theorem only requires Assump- tion I and 2, which aligns with the setting of the lower bound (Proposition 1). To our best knowledge, this is the first analysis of Adam without additional assumptions.
As for the range of B1 and 32. one can immediately see that the condition 31 S 8
degenerates to 31 < / Br in the bounded gradient case (i.e., σi = 0), the weakest condition required in existing literature [36]. When o & 0, such condition is stronger than 31 < VB.. We point out that this not due to technical limitations but instead agrees with existing counterexamples for Adam: Reddi et al. [26], Zhang et al. [34] show that when 01 * 0, there exists counterexample
5

---

satisfying Assumption and Assumption 3 and pair of (81, 32) with 31 < VB2 and Adam with (31, 52) diverges over such a counterexample.
Dependence over 82, 7, and T. Here we consider the influence of 8z. 77, and T while fixing 31 constant (we will discuss the effect of 81 in Section 6). With logarithmic factors ignored and coefficients hidden, C1, C2 and the right- hight-hadd-sie of Eq. (2) can be rewritten with asymptotic notations
Ci ===
C2 C== =
VI- +
1 +TV1
32
11"
T
VI
32
v(1
82)
V(1 32)
?
VI 32
E
V [w()))) = Ô (a1 (2++0++ + VTC VTC.).
where Ô denotes O with logarithmic terms ignored. Consequently, the dependence of Eq. (2) over 32, 1) and T becomes
E
[V((well =Ō
v1 32 +
11²
+
1
+
T
82 +
11 T
v(1
82)3
71
v1 B2
VT
VT +TVI 1-
- + vII 3)
V1 +
82
7
V1 52
Here consider two cases: (i). A32 and are independent over T, and (ii). A2 and 1) dependent over T. For case (i), based on the above equation, one can easily observe that the averaged gradient
norm 1. E [V](w;)]] will converge the threshold O -ーー 0'yi">5
VT 32 fí"m m5 with rate
OL/vVT). This aligns with the observation in [27, 34] that Adam will not converge the stationary point with constant 32.
For case (ii), in order to ensure convergence, i.e., minger IE G 1 + 0 as T' + co, sufficient condition is that the hight-hand-sid of the above equation is (T)). Specifically, by choosing
" = (TT and - B2 O(T~b), we obtain that
E
(w:)l = (T +T 2n T
+ + T --
+ - + T
T 2+ T + T-))))
By simple calculation, we obtain that the right-hand side of the above inequality is o(1) T co if and only if b > 0, 1 > > 0 and b b-a < 1. Moreover, the minimum of the right-hand side of the above inequality is Õ(1/T*), ). which is achieved at = and b = 1. Such minimum implies an upper bound of the iteration complexity which most differs from the lower bound by logarithmic factors as solving 0(1/T4)
& gives Ō ). Theorem 2, we will further remove the logarithmic factor by giving a refined proof when a = and = and close the gap between the upper and lower bounds.
Dependence over X. Our analysis allows À 0 in the adaptive learning rate 7) A contrast, some existing works [16, 21] require non-zero À and their iteration complexity has polynomial dependence over 3. which is less desired as X can be as small as 10- in practice (e.g., in PyTorch's default setting). Furthermore, compared to their setting, our setting is more challenging as non-zero immediately provides an upper bound of the adaptive learning rate.
4.2 Proof Sketch of Theorem
In this section, we demonstrate the proof idea of Theorem 1. Generally speaking, our proof is inspired by (i). the construction of the Lyapunov function for SGDM [22] and (ii) the construction of auxiliary function and the conversion from regret bound to gradient bound for AdaGrad [31], but the adaptation of these techniques to Adam is highly non-trivial, as SGDM does not hold an adaptive learning rate, and the adaptive learning rate of AdaGrad is monotonously decreasing. Below we sketch the proof by identifying three key challenges in the proof and provide our solutions respectively.
Challenge I: Disentangle the stochasticity in stochastic gradient and adaptive learning rate. For simplicity, let us first consider the case where B1 = 0, i.c. where the momentum m, degenerates to

---

the stochastic gradient Jt. According to the standard descent lemma, we have that
L
Ef(w++1) S f(w:) + E (Gt, W
-we)
110+1
We
||
2
O I Ef((w, + (GL v
+ 2
"
m
Order
Order
The first challenge arises from bounding the "First Order" term above. To facilitate the understanding of the difficulty, we compare the "First Order" term of Adam the corresponding "First Order" term of SGD, i.e., (G gt). By directly applying E g: Gt, we obtain that the "First-Order" term of SGD equals to - -, lla. However, as for Adam, we do not even know what B
d 3 gr is given that the stochasticity in 9: and is entangles. A common practice is to surrogate adaptive learning rate D, measurable with respect to Fr, to approximate the real adaptive learning rate V/. This leads the following equation:
E [K
G.. -1 V Og:
)
( VV .00)) +E {
+
gt
Vui
Vir
First Order
First Order Main
Ervor
One can immediately see that "First Order Main" terms equals to B[(G,, -" O G.). < 0, but now we need to handle the "Error" term. In existing literature, such a term is mostly bypassed by applying the bounded gradient assumption [10, 36], which, however, we do not assume.
Ve,
Solution to Challenge I. Inspired by recent advance in the analysis of AdaGrad [31], we consider the auxiliary function & (E /Pe+i + Gt)], where we choose i. 32 + (1 32) jo 1l..
In the following lemma, show that the error term can be controlled using & parallel to (Lemma 4. [31]).
Lemma (Informal version of Lemma with 31 = 0). Let all conditions in Theorem hold. Then,
VDr + G. ) + (
Error
7
G.
Et -
VB2 E1-1
+mall Error. (4)
In the fight-hand-sin of inequality (4), one can easily observe that the first term can be controlled by "First Order Main" term, and the third term is as small as the "Second Order" term. However, the second term seems annoying - in the analysis of AdaGrad [31], there is no 1/v32 factor, making the corresponding term telescoping, but this is no longer true due to the existence of the 1/V/ factor. We resolve this difficulty by looking the sum of
v7g ---1-1 & over t from T, which
gives O((1 - 32) TT- Et). By further noticing that D+t1 2 320r, we have
Vo, o .o..)) (
Σ VB2
(1 6-1 6-1 - )
(0 (1-32) 32)
s (1
E n (G,
1 (C.-LLoo
Gr,
t=1
The right-hand-side term can thus be controlled by the "First Order Main" term when 32 is close 1. Remark 1. Compared the analysis of AdaGrad in [31], our proof technique has two-fold novelties. First, our auxiliary function has an additional (1 - -2) L term, which is necessary for the analysis of Adam as it makes lower bounded from (AdaGrad does not need this, as V of AdaGrad itself is lower bounded). Secondly, as discussed above, the "AdaGrad version" " of second term in the fight-hand-sie of inequality (4) is a telescoping, the sum of which can be bounded straightforwardly
Challenge II: Handle the mismatch between stochastic gradient and momentum. In the anal- ysis above, we assume 31 O. Additional challenges arise when we move to the case where B1 * 0. Specifically, following the same routine, the "First Order Main" term now becomes (G. -,,.-1)- ② m. It hard to even estimate whether such term negative or not, given that m, and it still has entangled stochasticity, and the conditional expectation of m, also differs from Ge both due to the existence of historical gradient.
7

---

Solution to Challenge II. Inspired by the state-of-ar art analysis of SGDM [22], which leverage the potential function f(1)) with it -0, Bu-BBey- we propose to use the potential function f(u,) with 1-
w)
Vog W Applying descent lemma to f(tt), we obtain that
L E |1ut1 uell
& + ((V)( u++1 uz!
(5)
Order
Second Order
We again focus on the "First Order" term, which can be written as
E ((u)) u411 u.)l =E
V f(a))
W++1
31
W:
wi-1
vB2
vBg
v8g
f(we),
71
81
Vvc
3
m.
+
/
31
3
mi-1
v/2
V22
E
f(we),
8,
Vvc
m.
+
1
7
31
Vr
m
vP2
v
G.: (1 - 31)
O gt )
71 - 31)
E
G+:
v
v0g
vd2
Here approximate equation (*) is due to Assumption and that w. is close to u, and approximate equation (o) is due to Lemma I and i. = - + (1 32)a $29r-1 (of course, these are informal statements. Please refer to Appendix C for the detailed proof). With the above methodology, we arrive at the following lemma.
Lemma 2 (Informal Version of Lemma 8). Let all conditions in Theorem I holds. Then,
L o G.) G:)))= +0
(
(
Ef(( & B.((u) - Ω E G.,
V/2 E--1 - Et + Small Error.
Summing the above lemma over from 1 T, obtain
G.
< <0 + Σ o
EE
Ve.i
T'nn 82)
(6)
Vo.1
We then encounter the second challenge.
Challenge III: Convert Eq. (6) bound of gradient norm. Although we have derived regret bound, i.e., bound E [B[ Ves C G.l we need to convert it into a bound of [|]] In existing works [36, 10, 16] which assumes bounded gradient, such a conversion is straightforward because (their version of) i, is upper bounded. However, we do not assume bounded gradient and P, can be aribitrarily large, making E||l
VV. C G arbitrarily small than |||
Solution to Challenge III. As this part involves coordinate-wind analysis, we define gt.i. Gt,5, Mt,i- and DJ respectively as the 1-th coordinate of gt. GG, Vr, and o7 To begin with, note that due to Cauchy's inequality and Hölder's inequality.
111
M
|G
VD о GG.
(7)
Therefore, we only need to derive an upper bound of ET_ E|| vo which is achieved by the following divide-and--onque methodology. Firstly, when G.,, > of we can show 2 |gr..1
2),r, 2 Fo 1
Then, through direct calculation, we obtain that
V 3(1
32)07 E [ (irtau-VBetrn, 1 1,,,2.200
E
1
12
co
and thus
T E
Gr,l 2
V
T
Beris - BBbrss) 1G..112244
V
3(1
32
8

---

Secondly, when |Gr,ll < de define (Di,) Do,s VUl, Dr,; = D2-1, + 19c, 2 1 One
01
can easily observe that vt, S Ve,is and thus
T
Σ
E
1=1
E
V B2i1.3 + (1-1111) -22000
32(32P1-11 + (1 82)088
1=1
T
=Bv 320r, + 31) + +
v 32
E
Bour. + (1 -2)00 B 32(3200, + 32)0g)
Putting the above two estimations together, we derive that
(1-Val
T+1
Σ
E DL, S 3(1 7
T
E
Gr,rl
+ + (1-V3))(++ 1) vo.
V
Vi.
The above methodology can be summarized as the following lemma. Lemma 3. Let all conditions Theorem hold. Then.
T+1 ΣΣ
E PIA S 2(T+ +1) Σ Mo. + oß 24d 0i
o. In
C2-
VB2
32
Based on Lemma 3, derive the estimation of >>>>> E VM |2] since in is close to v.. The proof then completed by combining the estimation of Σ
1=1 E|| Vū, [] (Eq. (6) and Eq, (7).
Gap-closing upper bound on the iteration complexity of Adam
In this section, based on refined proof of Stage II of Theorem (see Appendix C) under the specific case 77 ((1/vT) and 32 removed and the lower bound can be achieved. Specifically, we have the following theorem.
O(1/T), we show that the logarithmic factor in Theorem can be
Theorem Let Assumption I and Assumption 2 hold. Then, select the hyperparameters of Adam as and $1 cv/2. where a, and 0 S are independent Tf T. Then, let w, be the output of Adam in Algorithm 1, and we have
1 v B2
V Vo.i + 3bo + 1D2oßb 256o
G
16D
1Dofb VT
2
E
+
In (et
VT
(1 - 2)
Vini
VT
2D:
VT
In
V
Pu.s + 300 + 1D2otb
VT
(1 (1- 2)
256oib
Σ
E
V
G
+
16Diobb
/T
In (e+ 1Doib /T
x
64
D2
E
c)
V 1i
VT
where
Dj A 32La (1 + c)3
3200
(1 (1+o))ofL'da da
(1- c DD { + Di bd Σ Emneos 1=1
b c)3
Vb(1-))
As a result, let A be Adam in Algorithm 1, we have C. (, = ( -
The proof of Theorem under the specific hyperparameter settings, and we defer the concrete proof to Appendix D. Below we discuss on Theorem 2, comparing with practice, with Theorem and existing convergence rate of Adam, and with the convergence rate of AdaGrad.
based on a refined solution Challenge II in the proof of Theorem

---

Alignment with the practical hyperparameter choice. The hyperparameter setting in Theorem 2 indicates that achieve the lower bound of iteration complexity, we need select small 1j and close-to-1 82, with less requirement over 31. This agrees with the hyperparameter setting in deep learning libaries, for example, 1) = 10-3, $2 0.999, and 31 = 0.9 in PyTorch.
Comparison with Theorem and existing works. To our best knowledge, Theorem 2 is the first to derive the iteration complexity ( Previously, the state-of-art iteration complexity is O log 1/5) [10] where they additionally assume bounded gradient. Theorem 2 is also tighter than Theorem 1 (while Theorem 1 holds for more general hyperparameter settings).
discussed in Section 4.1, if applying the hyperparameter setting Theorem (i.e., 1) v B2 =
and 31 cvB2) to Theorem I, we will obtain that f(WV)l I Oppoly / and C. (A, A, L, o²) O log 1/2), Proposition 1 by logarithmic factor.
(00))/ worse than the upper bound in Theorem 2 and the lower bound in
Comparison with AdaGrad. AdaGrad [12] is another popular adaptive optimizer. Under Assump- tions and 2, the state-of-art iteration complexity of AdaGrad is O (/o [13], which is worse than Adam by logarithmic factor. Here we show that such gap may be not due to the limitation of analysis, and can be explained by analogizing AdaGrad to Adam without momentum as SGD with diminishing learning rate to SGD with constant learning rate. To start with, the update rule of AdaGrad is given as
4 = V- + 9t C2
W1+1
we 1
④ gt-
(8)
We first show that in Algorithm 1, if we allow the hyperparameters to be dynamical, i.e.,
vs = 12, + (1 - f2 m = m1 + (1 - B1,t)ge, wi-1 = w. v
m.
m&
(9)
then Adam is equivalent to AdaGrad by setting = = B1, B1. = 0, and 82, =1 -- Specifically, by setting μ4 tv; in Eq. (9), we have Eq. (9) is equivalent to with Eq. (8) (by replacing Vs by μr in Eq. (8)). Comparing the above hyperparameter setting with that in Theorem 2, we see that the above perparameete setting can be obtained by changing T to and setting c = 0 in Theorem 2. This is similar to the relationship between SGD with diminishing learning rate e (1/vV) and SGD with diminishing learning rate ((I/VT). Recall that the iteration complexity of SGD with diminishing learning rate @(1 / ([//Vl) also has an additional logarithmic factor than SGD with constant learning rate, which may explain the gap between AdaGrad and Adam.
6 Limitations
Despite that our work provides the first result closing the upper bound and lower bound of the iteration complexity of Adam, there are several limitations listed as follows:
Dependence over the dimension d. The bounds in Theorem and Theorem 2 is monotonously
increasing with respect to d. This is undesired since the upper bound of iteration complexity of SGD invariant with respect to d. Nevertheless, removing such an dependence over d is technically hard since we need to deal with every coordinate separately due to coodinate-win learning rate, while the descent lemma does not hold for single coordinate but combines all coordinates together. To our best knowledge, all existing works on the convergene of Adam also suffers from the same problem. We leave removing the dependence over d as an important future work.
No better result with momentum. It can be observed that in Theorem I and Theorem 2, the tightest bound achieved when 3 = 0 (i.e., no momentum is applied). This contradicts with the common wisdom that momentum helps to accelerate. Although the benefit of momentum is not very clear even for simple optimizer SGD with momentum, we view this as limitation of our work and defer proving the benefit of momentum in Adam as a future work. Also, our result does not imply that setting 31 is not as critical as setting B2.. The primary objective of this paper to characterize the dependence on é and the importance of setting 81 might be justified in other ways or characterizations. To help readers gain a deeper understanding of this issue, we include experiments to illustrate the dependence of performance on 31 in Appendix E.
10

---

Acknowledgments and Disclosure of Funding
This work was founded by the CAS Project for Young Scientists in Basic Research under Grant No. YSBR-034 and the Innovation Funding of ICT, CAS under Grant No.E000000.
References
[1] Y. Arjevani, Y. Carmon, C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. pages 1-50, 2022.
[2] J. Bradbury, R. Frostig, P. Hawkins, M. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke,
J. VanderPlas, S. Wanderman-Miin
and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:: /ttttt://gtthti com/ www.coogle/////oooooooooooo.oole g
[3] A. Brock, Donahue, and K. Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2018.
[4] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,
G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[5] X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of a class of Adam-type algorithms for non-convex optimization. arXiv preprint ar0iv: 02941, 2018.
[6] X. Chen, Liang, D. Huang, E. Real, K. Wang, Y. Liu, H. Pham, Dong, T. Luong, C.-J. Hsieh, et al. Symbolic discovery of optimization algorithms. arXiv preprint arXiv:2302.06675 2023.
[7] M. Crawshaw, M. Liu, F. Orabona, W. Zhang, and Z. Zhuang. Robustness unbounded smoothness of generalized signSGD. arXiv preprint arXiv:2208. 1/95, 2022.
[8] A. Cutkosky and H. Mehta. Momentum improves normalized SGD. In International conference on machine learning, pages 2260-2268. PMLR, 2020.
[9] S. De, A. Mukherjee, and E. Ullah. Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration. arXiv preprint arXiv:1807.06760 2018.
[10] A. Défossez, Bottou, Bach, and N. Usunier. A simple convergence proof of Adam and Adagrad. Transactions on Machine Learning Research, 2022.
[11] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani,
M. Minderer, G. Heigold, S. Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2020.
[12] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[13] M. Faw, I. Tziotis, C. Caramanis, A. Mokhtari, S. Shakkottai, and R. Ward. The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pages 313-355. PMLR, 2022.
[14] W. A. Fuller. Measurement error models. John Wiley Sons, 2009.
[15] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[16] Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. A novel convergence analysis for algorithms of the Adam family. arXiv preprint 1rXiv:2112.03455) 2021.
[17] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[18] D. M.M.W. C. Kenton and L. K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLL HLT, pages 4171-4186, 2019.
[19] Khani and P. Liang. Feature noise induces loss diserepancy across groups. In International Conference on Machine Learning, pages 5209-5219, PMLR, 2020.
[20] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980, 2014.
11

---

[21] H. Li, A. Jadbabaie, and A. Rakhlin. Convergence of Adam under relaxed assumptions. arXiv preprint arXiv:2304. 3972, 2023.
[22] Y. Liu, Y. Gao, and W. Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271, 2020.
[23] L. Luo, Y. Xiong. Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv:1902.0999 99999220944,, 2019.
[24] S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer sentinel mixture models. arXiv preprint 16Xivv6609.0780 07843, 2016.
[25] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin,
N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. volume 32, 2019.
[26] S. Reddi, S. Kale, and S. Kumar. On the convergence of Adam and beyond. arXiv preprint 1rXiv 09230,9977222 2019.
[27] N. Shi, D. Li, M. Hong, and R. Sun. RMSprop converges with proper hyper-parameter. In International Conference on Learning Represenlations, 2021.
[28] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556. 2014.
[29] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and
I. Polosukhin. Attention is all you need. Advances neural information processing systems, 30, 2017.
[30] B. Wang, Y. Zhang, H. Zhang, Q. Meng. Z.-M. Ma, T.-Y. Liu, and W. Chen. Provable adaptivity Adam. arXiv preprint arXiv:2208. 09900, 2022.
[31] B. Wang, H. Zhang. Z. Ma. and W. Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pages 161-190. PMLR, 2023.
[32] X. Xie, P. Zhou, H. Li, Z. Lin, and S. Yan. Adan: Adaptive nesterov momentum algorithm for faster optimizing deep models. arXiv preprint arXiv:2208. 06677, 2022.
[33] M. Zaheer, S. Reddi, D. Sachan, S. Kale, and Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
[34] Y. Zhang, C. Chen, N. Shi, R. Sun, and Z.-Q. Luo. Adam can converge without any modification on update rules. arXiv preprint arXiv:2208. 09630, 2022.
[35] Z. Zhou, Q. Zhang, G. Lu, H. Wang, W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint 18 2018.
[36] Zou, Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of Adam and RMSProp. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 11127-11135, 2019.
12

---

A Other Related works
Section 3 has provided a detailed discussion over existing convergence analysis of Adam. In this section, we briefly review other related works. Adam is proposed with convergence analysis in online optimization [20]. The proof, however, is latter shown to be flawed in Reddi et al. [26] as requires the adaptive learning rate of Adam to be non-increasing. This motivates a line of works modifying Adam to ensure convergence. The modifications include enforcing the adaptive learning rate to be non-increen non-increasing [26, 5], imposing upper bound and lower bound of the adaptive learning rate [23], and using different approach to estimate second-orde momentum [35, 7]. Recently, Chen et al. [6] discover new optimizer Lion through Symbolic Discovery, which uses sign operation to replace the adaptive learning rate in Adam, achieving comparable performance of Adam with less memory costs.
B Auxilliary Lemmas
The following two lemmas are useful when bounding the second-order term.
Lemma 4. Assume we have O < Bg < 1 and sequence of real numbers (an)m= Let bo > 0 and
bn = 82bn-1 + (1 - 32)aa Then, we have
T
1 In
bt bu
-Tin 82
1 B2
n=
Lemma 5. Assume we have 0- < B3 B2 1 and a sequence of real numbers (an) Let by >
bn = B2bnn1 + (1 - B2)0n Co = 0, and Cn = B1cm-1 1 + (1 - (1 an Then, we have
call 1
(1 - 31)
bT bp
In
- 32
on
(1
84 (2 ;32)
v32
Proof. To begin with,
lcal
S (1 - B1)
Σ
< (1
31)
Σ
n
37 |asl
I (1
- B1) n
Σ
3
B-
ag
vbn
bbn
bn
VB2
/b:
Applying Cauchy's inequality, we obtain
Cn On
B
n
ag
< (1 11--81 31)2
12
v
hb
B1
31
12
las12
(1
31)
31
n-i
lai1
S(1 - <(1-81)²
Σ
<
B2
b;
B1
vB2
v
b;
vin2
Summing the above incquality over n from to T then leads to
call 2
(1
31
8
n-8
la
1
(1-
B1)²
T
lan 12
T-n
31
)
Σ
by
1 - 81
B
b;
81
bn
vibe)
v92
n=l
vB2
n=
(1 31)²
T
12
(1 81)2
bt
In
T
In 32
8
On
(1
(2 - 12)
bn
n=
The proof is completed.
The following lemma bound the update norm of Adam.
Lemma 6. We have Vt 2 1, |10+1,5 we,i
S "
1-0
S n
1-0
vI 30
13

---

Proof. We have that
ma,i
Li=
(1 81) 9 i.
W(+,1
W1,sl= = -
S
(2))8199-5..1 + B3g0.
i=
1 1 31
i== 1u19
i==
1-1 P
1
- 31
1)
VI 32
Di=
v1
32 1
Here the second inequality is due Cauchy's inequality. The proof is completed.
C Proof of Theorem 1
This section collects the proof of Theorem 1. As a part of the proof, we first provide formal descriptions of Lemma 1, Lemma 2, and Lemma 3, and their corresponding proofs. We then proceed to prove Theorem 1 leveraging these lemmas.
C.1 Formal description of Lemma 1, Lemma 2, and Lemma 3 and their proof
Lemma 7 (Formal version of Lemma 1). Let all conditions in Theorem I hold. Then, we have
1/
1
5 d
1-
31
Gr 2
21/1
B200
d
L...
G B1
1
Vi
Vv,
m
1
31
+
82
2
E
Vtii
V
i=1
vDh
82
4(1 - 31)
d Σ E
Gi-1s
G2,
d
21 /
320
12
+ 1]
01
(1
81
12
BB
Vo+L.
81)
31
Vt,i
1=1
1=1
64(1 + of L
1
+
E
m,-1
(1 31)oo/T 1-
B2
Proof. To start with.
1
1
B F
G
mi
1
Vv:
VDr
V
(1-33)
32) 11 22)
F
G
11
m,
1
6
V Di (2 U1 + vvx)
V32
d
(1- (2) + 92.1) VDriv Vr.1 (V,v vvrit)
GG
m
1=1
V
(1- - B2)9ř,
1)
F
G
m
8
Veriv Vr. (Vr, vir,))
V92
11.1
d
(1 32)08
F
|Gral
meal
VuLaa Vi Vi.iivieillv Me,i + virs))
1m
1.1.2
14

---

As for I.1.1, we have
d
(1- - B2)
Bl
Grall
|mall
91
Veriy Vr ves + v
1=1
V12
d
7(1 - 31)
v1 -22
BBIA
GGall
(V1- - 8,
3
Vee.sypes + (ex)))
V
7(1 - 31)
GLal
E gi.
EEJ.
(V1- - 81
V
(vDL. + v (1.a) )2
v
n11 - ((1--1)- -B1III- B5 |Gr
V
08 + oo
E
01 (V1-
VeL.
(VDr, + vi..)2
- ((1-B1)vI-
B2 |Gall
9i,
(00 + toiGGr,ly
51 (V
v Vu,
(Vir, + v1.3)
v02
where
inequality (+) uses Lemma is due
inequality Assumption n1 MLL-BMM-E
6,
(0)
due to Holder's inequal- Applying mean-value in-
ity, and inequality (o)
to
3.
equality respectively
ii=
E
F.
G..l Vini
E 2
and (
Vi2
Ei n/1 11-8)1-1- Bo F
GG.d
Vir, o
|Gr,ll
EIF.
oº. (vBr,tt )2,
we obtain that the right-hand-side of
A the above inequality can be bounded by
3
2n/1 B200
Blus
gi.
11
31
3200
D1,i
+
4.
VV. / (D..) 2
V22
vit2
d
1- B1
G.
(1 - 31 - 31)
G
d
g
+
Σ
+ -211
E
F
Vora
(1
)2
VDr
(W/O,s + v )
1=1
v
1-
81
2n/ - B20
B Pi,
2
7
(1-
81
Vt,
V32
v3n)
d
31
Gr,l 22
(1 (1
B1)
Grall 2
d E Σ
gi. (VPr. + 2
+
8
Σ
7
Vt,i
+ +21
(1
9 )2
Vi,i
(10)
V82
vzn
i=l
Here the inequality is due to Dr, = (1 :2)0z + 1211-11 2 (1 -32)aB. Meanwhile, we have
Gh
(32r ViLti.)
P.,((1 - -02)208 + B2(1 - B2)
G2,82(1 - 32.
BB2r, v (Dr+1,d v BBūr, + / (etii)
( (ooiiiii/BBii B2ire + (
/B2 C2,(1 - B2)
2 VDril + 22
15

---

Applying the above inequality back to Eq. (10), we obtain that
d
(1 32)
Σ
Bl
|G
m
1-
31
Vuri
+ vvrs))
2m1
1 31
1r,112
21/1
- 3200
B Fr I
11
Vi
(1
1P
V,,i
v182
B2
+ 1)
4(1
31)
01
d
E
1
G2,y
(1I)
81
12
v
V VP+11$
Furthermore, due to Assumption 1, we have (we define Go - G1)
G SG + G Gc-1,l + 2(G - 1,)
<G 2T Gr,il/ w.-1|l + 2T.² ||,, WT 11-111? 11?
which further leads to
1
G2
(G
+ +L
w. 2T,2 ww -2,1112)
/B20r.
(9)
(1 &
(1 1-13
16I
G² Gi-1,
vBn
+ 3
1w0, w1-1l1
1
(Di
(2
8.
(1 - 31)/
v8,
2T,2
[w: - w1-111
B222
(1- B
- B1)BBB
16L209n1
G2 Gi-1,t
+
vB2
+
2 m
1607
Vūr.i
B2
(1
-3, (1 -3)000/ 1 - B2
2T2
1
+
3 m
σOV
32(1
3²)
VDt-1
1
G2
G
+
(1
Vina
(1
F2
G
16(1 16(1+07)L31
m:-1
B2ir
16a7
Viss
BI)oo II (1-
32 1
Applying the above inequality back to Eq. (11) leads to that
11-32)973
L1.1
17
E
Fi
|ma
1
B1
Vi.i Vrrii /i,i Mi.5 + vi.s)
f=1
1
d
1- 31
Gr.l
2n - 3200
Fr gi.
Σ
2
11
31
Vūr.
+
(1-
82 2
1=1
4(1 31)
G2
G
0. Σ F
+
(1
/2 v8,
V
v /D+11.
i=1
64d(1 + of
1
2
C mm-1
(12)
88
(1 331
B1)
Bz
VV--1
16

---

As for I.1.,, we have
1.1.2
d
7
E
Gr,ll
(1- 82)08
mi.el
91
/u,iv (1Ms + vDri)
vBa
d
11-
E
Gr,l
|
i=1
v92
d
G
20/ 1 3200
[
|m, 12
]
+
B
(13)
811
#1
B1)
B1
Ve.5
v/2
With Inequalities (12) and (13), conclude that
d
31
G
2
20/1 - 3200
gh.
1.1 5
17
E
+
1=1
Vt,
1
8i
Vt,i
4(1 - 31)
Gi-
G.,,
21p 1
3200
|ma..l?
Ve,s )
+1
E
Σ
E
(1
v 12
v
Vi+1,,
(1 81)(1
V
1=1
==1
V32
64(1 + of oi)
1
E
2 m
83
8, (1 31 3000v/1133
-
VV-1
Lemma 8 (Formal version of Lemma 2). Let all conditions in Theorem 1 holds. Then.
Ef(ue+1)
<Ef(u:)
7)
31
E
17
G.,
G.
21/v 1 3200
E
g
2
41
31
Vir
(1
84
Vt,i
v82
B2
d
d
21/y 3200
+ +11
0
Σ
Et-1
-c
+ Σ
E
B1
1
\B2
VB2
(1 B1)(1
Vzii
VM2
1=1
iml
v
64(1 I.
27 1
32
m 27
E
m
E
0:
(3(1
B1)d0v -
V
(1 B1)(1
)
V
v
i=1
2
2
+ LE
4
3
m
+3
n?
4 m
B
V
1
b
VDz
y3,
/ 73
17

---

Proof. According to the definition of Uy we have
W
wt
31
wt
w
U1+1
U1
1
V
VB2
1
1
7
1
m, + 31
m
1
31
Vu
1
01
v
12
v/2
v
7
1
7
81
Vii
m. + 81
1-
V
mmp-1
V
V/22
1
1
1
3 m, + 3
o m
31
Vv:
vin
1
91
VB221-1
vv.
V
v12
31
7
81
Di
3 gt
1
1
(Vismmi
④ m. + 31
3 m4-1:
VD:
Vi,
v/2
vP2
where Eq. (+) is due to m.
B1 m (1 31)gt.
Applying the above equation to the "First Order" term, we find that can be decomposed as
E [VV [u:), u++1 ux))
=E (G,,, U4+1
ut)l + +E ([(()((
Ge, 21:4411 ui)l
-E K
Ge: -1
1
1i
+
G
1
11
B1
VVI
1
Vv,
2 m
33g
)
+ E
G
81
11
④ m++
+ [V[ - Gr, U-114-1-11 -11)
81
(B2u1-1
Vi,
V3
1 1
91
17
1
17
E
G2
+
GG,
3 m
1
B1
Vir
91
vu: vir
11
+E
Go, 91
71
3 m
+ +E((f(()) G.,, U++1 - ui)
VB2u.-1
Vv.
1.2
Here we apply Lemma to bound I.1. We proceed by bounding 1.2 and 1.3 respectively. As for 1.2, we have
1.2 E
Gr,
3
17
C mm-1
1
31
/2
Vv:
V
d
Σ
E
|Gr,
m
v 12
Vūri
7 1=1
n
(1 32)08
Σ
E
GLa
1 8
/ 1r,1
12
V3,
8
VI- 1--3
Σ
E
Gra
Mi-1al
1 V
/ 12 / Vind
1=1
1
31 d
G2 12
21 T
32 32
0o
mm--1,1 12
+
E
8
Vi.6
(1 31)(1
V/-15
VB2
18

---

As for L.3, we directly apply Assumption 1 and obtain
1.3 =B ((u))
G1.
Ux-1 ut)
<B
V [(u))
G.
U1+1 Ut
<E
1|/
U1+1
Uxll
81
=LE
V3g
Ww
Wi-1
v/2
|i++1 well +
vBa
1|
wi-1
1
1
8/2
v92
81
<LE
vPg
W:
wi-1ll
1
wi++1 will +
vB2
wi-1ll
1
VP2
3/2
3
81
2
STR
2
V/2
|10,
14-1
112
1
1
|
wrel2
4
2
v/2
8
2
2
<LE
2
V32
11²
m
1
17²
1
mi
1
V
1
Vui
292
v
All in all, we summarize that the "First Order" term can be bounded by
1
91
2n
2m
3200
E L
E
2 G.
+
41
8
VV.
(1-
89
Vt,i
V
1=1
4(1 31)
Gi-L
G
21/51 3200
| 2
+ 1]
0
E1
(1
B
12 12
B2Ur.i
V
(1 31)(1
B1
Vi,i
VO
i=1
v
64(1 + 1220d
1
2// 1 - B28300
m 12
E
① m
+
I
31
f
33(1 - 31)00v1- - B2
VD-1
(1 - B1)(1
8n
)8
V1-1.i
VBg
v3,
1=1
2
2
LIE
2
V
11²
1
m,-1
1
1
m
9
Dt-1
01
VDr
Furthermore, the "Second Order" term can be directly bounded by
2
L
E
u4+1
u1/1
=
L
2
W1++1
1
81
Wt
VB2
B1
We W1:11
8,
v32
VB2
2
W1++1
ut
B1
Wi 10;-1
<2LE
+ 2LE
1
8,
13
1
8
v82
19

---

Applying the estimations of the first-order term and the second-orde term to the descent lemma then gives
Bf(u++1)
1 1 - $1
21
3200
E 9i.
<Bf(4)
B
4
31
(1
8
V4,5
vP2
i=1
82
d
Gi-1s
21/ /1 B200
m 2
]
+
01
Σ
E
(1
81
32
Vi++1.
(1 B1) /B²
91
Vi
V
i=1
64(1 + f L
2// 1 - 32. 00
m
+
E
mi-1
+
E
33
B
)3(1
31)00vl
$2
VV-1
(1 - B1)(1
B1
)8
1t-1
VB2
v9,-
2
2
+ LE
v82
112
m
+3
172
1
3
m,
f
V
1
V1z
v 3
The proof is completed.
Lemma 9 (Lemma 3, restated). Let all conditions in Theorem I hold. Then,
T+1 d Σ
E 5 2 d Σ v Vusi + o + +4d 9c ooo 120, vB2
In
+
Cz.
vB2 VB2
1=1
Proof of Lemma 3. To begin with, we have that
G
2
G
E
1
50
E
(14)
V
On the other hand, we have that
G 2
81
Bl
19r, 12
1-82 ad oj
30
Gr.
2
78
10.112.77 d0
Vt.i
Vin
30
9t.6
12 1- 307
0
2 VRRl
30
gr, 1
1- 30f
0u
Vir.i
GG.22
Vi++.. +
/B2ūr.
G..s 2.
As a conclusion,
T
Gral
T
30 gt.
32
+ 1-82 oō
30
E
GG "0
2 V B2
EE
1z,
V
Ve+1. + B22u
1=1
V
T
>
E
- B2irs
110
3(1
t=1
20

---

On the other hand, as stated in Section 4.2, we define {2 as Du, = Vo.s. Dr, = B201 One can easily observe that 24, S 2,,, and thus
(1 32) 2
G.
Σ
E
1G of
T
Σ
VV 18v1111 + 32(1 - --233 9e, 2 +1 (1- - 32)08 - (1- Gr.l
182 + -
3o)lon,, -1
+ -2 (2)1--3))lgr..)) GG.,l< + (1 - 82)0 18 + 32)
E
T
Σ
E
+ (1-8))03 +1
B2( + (1 -B2)08)
1=1
T-1
=B B2U1, + (1 (1- (1--3))0 + - 33)
BV 8201, + - 30-
B 32(3200. +(1 -
+11-+111100 -3200))
All in all, summing the above two inequalities together, we obtain that
3V 111. + (1 (2a) Σ Rv
/ Bi. v 12
(ve.. Vi2ei 1.1
F.
T.
(voL.
/o 1:) 1 12, 24
(Vo - V 1.1
3(1 A2)0
G 27
+ BB + (1 82)08 (1 vBa) Σ B B200, (1 B2)08
BalBoo., + (1 02)0g)
v
Since Vt,
E B B2ūr, + (1 - 11-000 S BBEEL (1 32)0 < v + Vo.i
combining
with
B2U1,i
B2(DDo. (1- --)00)))) and E EVieL = /
E BB (1 - 02)07 E B2 + (1 B2)0g we obtain
(1 v 32
T+1
E D4
3(1 B2)07
Σ V
T
E
G..
E + +(1 VB2) Σ 1=1
T
Brens + (1 B2)o8
V
2=2
1=2
3(1
32)07
Σ 1=2
E
|G.,1 ?
+ (1 /ByTI VoB Vo. Vo.
(15)
V
Vi..
21

---

Leveraging Eq. (16), we then obtain that
T+1 4
Bv
Miii
(1 + 1
G Mi.:
33
+ (T + 1)
Vo,i + o
v 32
t=1
6
8,
d
G
Pr. Vo.i
f(u)) +
+
CIE
E
In
T
VB2
- B1
$2 (1-
9 V92
1=1
i1,
1=1
(T+
Vo.s o
Go7
vBg
=((1) +
32
E
G
+ 20
Σ
In [
T+ v Vni
T In B2
VB2
1 - 31
82 (1
8
11
v B2
(T+1) 1)
V Mo. + o3
1
UB2
8
{uu) +
32
G
+ 2C Σ
In
EE
E
Ej=1 v Vuss
T In 32
VB2
1 Bi
82 (1
81
v 11.
/2v0,
v
+ 11'+1)
Σ
V
Mo,s + o..
where in the last inequality we use the concavity of hxx) = In.z. Solving the above inequality with
respect E Σd Dr then gives
T+1 d
d
o9
In dl oiG
Σ
E
Vus S 2(T + +1
Σ
V
Vo.i + oz
+ 24d
VB2
v
1=1 1=1
1=1
1-
-Tnn (32 ))
+ 12
v
8
{())
+
32
R
+ 2C
Σ
In
V
1 31 17
82 (1
v Mi,i
\32u0
The proof is then completed by applying the definition of C2.
22

---

C.2 Proof of Theorem 1
Proof of Theorem I. Summing the inequality in Lemma 8 over from 1 to T and collecting the terms, we obtain
[((+++
<((u)
17
31
T
E
G
+
+1
4(1
31)
0
T
d
E
Gi-1, V32r3
G. V
4
(1
4
32
Vi2
1=1
i=1
1=1
T
C
E
my
M
1=1
<i(u1)
7
31
T
d
E
G
+
4(1
31)
01
d Σ>
E
Gi
41
$1
V
(1
///
13201
V
t=l
i=1
V
t=1
1
1
T-1
Σ
E
G
+C
E
1
C
m
32
12U1+111
Vur
(4)
S
f(u))
7
31
T
E
1]
4(1
31)
G
41
9.
j2
12
12
V
[=1
i=1
v
17 1 - 81
T-1
G2
1
81 8
Σ
E
E
m
VSL 1=1
1=1
(0)
7 1 3
T
d
G
4(1 31)
d
G
f((1))
E
8
5
(1
12
ViD
t=1 i=1
J
1=1
(1 - B,)²
In
VTa Vo,3
-T'I 11
(1 91 22 B2)
i=1
where we define
2
21
32 To
64(1 + o7)o
+
(1-3:1(1-1
8 v3g
33
3
8 )8 - 31)oovI- B2
to simplify the notations, inequality (*) is due to that #(41. 2 328t+1, and B1 S vB 80 32)85²2 and inequality (o) is due to Lemma 5. Simple rearrangement of the above inequality then gives
Σ
B
1 vv.
G
1
vB2
B. 8
f(u))
+
32
E
1,
1
31
17
82
1
91
1=1
d
VTg
+ C1
E
In
-''n 32
(16)
Vo.i
i=1
Then, according to Cauchy's inequality, we have
T
{){E
||
1
E
Gelli
E
о
G.
E
(17)
Vo!
1=1
6=1
Meanwhile, by Lemma 3, we have
T d Σ
Vu.i + oz + 24d ofC, of
ofC,
12o?
E Vu.
S 2(T +1)
Σ
v
In d
+
Cz.
VB2
BB2
vB2
1=1
1=1
23

---

Combining the above inequality and Eq. (17) gives
10
|G::l11
1=1
v02
f(u))
32
E
G
C1
Σ
In
MT.s
Tin - (2)
31 17
B2
81
V
1=1
Vu,i )
V32
91C
90
1209 C2
x
2(T + 1) Σ
+ +oo
+ +4d
In d
vB2
V
vB2
d
T d
o90
09C
120
C2 + 201
Σ
In Σ
V
x 2(T + 1)
Σ
V Mooi + toj + 24d
In d
+
v C2
V
vB2
1=1
1=1
t=1
1=1
Vu, + oz + 24d o9G1
ofCi
1207
C2 + 2C1
Σ
In
2(T
In d
C2
V
v
i=1
Vo. + of 24d RG
In d 9
1207
x 2(T + Σ
C2
vB2
v
VB2
The proof is then completed.
D Proof of Theorem 2
Proof. To start with, we have that
Gr,ll 2
R.
I9t.1
20
1
G..22
2
Vinii
12,
F
20
1G,,11200
B2 1,5 (1
82)00
1
1 12
20? V1 - B2
Mo.i +
Σ/=
19
+
G.
where the last inequality is due that
T Σ #=1
82 -1 (1 B2) Σ
19..
2
(1 (22)
1g 2 + Vo.s.
(18)
Furthermore, we have
00 +
Mo.6
T
9t.a 2
I-38
1 GG
Mo.1
2 190.
2
12
0
Po.1
>>=
T
|0,,1
o
1-
I-B2
0
No.s -4
1gr. 2
Gr 20
Ma.
+ -azl 1 |G.. +
Mo.1
+
Σi=1
I0 21 Ga +
1-82
1-3;
E
Va,i
+ Σ
19 121
G.
10
30 +00
Va.i
+ E
90. | PI|.., <3 + +
1 B2
32
Vo.i
+ 2o + o
(19)
32
24

---

Conclusively, we obtain
T
Vu,s
E
19
2
+
82
==1
0
gr,il
I-p2
+
E
1
G.,1 20
1-
MD.L
+
==
19
0
Ma. 1-
+ E
D0.1 12 + 000
91.2 12
E
12,1 24
Vosi
00,1 + +00
[=1
1-92
Vo,i
+ +20hT + 00 + 2/1 - 8
T
Gri 2
1 Gr.12
1 B2
Vi,i
Vo,i
+ +00 00 + +221 $
T
Gr,il
1 B2
Vi,5
Secondly, as B2 + 1 - 80 - B2) holds for large enough T, and thus Theorem holds. Applying the value of B1, $2, and 17 to Eq. (16), we obtain that
T
64
d
G
E
@
G.
DDVT+
E Envrr +
E
(20)
Vi
(1 - c)2
VV1
1=1
Summing Eq. (19) with respect to then gives
T
Vo,i
1 + +o0
32
d
T
M0js
+207T + og +2 ]
1 B2
/
E In 1n + 12807vb
d
G
Vo.i
+ +207T + o6 2b+ 2D
1 B2
(1 c)
+ 1280 Vb
Vo,i
+20 08
2D +
4D
Eln Vera
E
1 B2
(1 11-0) 2)2VT
Vi
1=1
T
Vo.i
20 + +
+D /b+ 1D Eln Σ 1 B2
Vo.i
+
Σ
g 22 + of
I B2
32
128a Vb
G2
+
c)2
Vi,
1=1
d
T
Vo.i
+
20 of +
2D
Vb
4D V
In
Σ v1
82
Vo,i
+
>
1 12 + +03
1 A3
32
G V
+
E
(1 CT
where the second inequality is due to Eq. (20), the second-to-last inequality is due to Eq. (18), and the last incquality is due to Jensen's inequality. Solving the above ineqaulity with respect to
25

---

-1- Σi= i=1
E
Mo.; 1-12
+
E==
10,s + og then gives
Vo.i
32
E2
go,s
1 B2
4D20fb
25
G
16D
4Do
2
Vo.i + 360g +
E
in
e
VT
c)2T
Di,i
VT
vT
i=1
(21)
Therefore, by Cauchy's s inequality, we have
2
T
1]
Σ G. 11
s
Σ
G.
Σ
Σ
1=1
i=1
Since
T
T
d T Σ
T
12 + (1 - 32)00
/
B
Vo,i
+
19,,a ? + o..
82
1=
1=1 1=1
1=1
8=1
have
T
E
Gell
1=1
256o
Gi,
16D (et
4Do
2T
Vo.s + 3bog + +1D2oBbVT
(1
2)²
Von
JT
i=1
64
Gi,s
x
D2VT - DIVT)
Elner +
c)2
Vi,y
d
256o
Gi
(et 4Do70
27
Σ
V Mo.i + 30o
4D2otbVT
16DiotbVThn
(1 c)2
v Mi,
VT
1=1
1=1
2D VT
Σ In 2 Σ Mo.1 3003
+
1D20bb
VT
256oib 2T
v Di.
G
16Dioit
vT
In ( (e+
1Doit
VT
1=1
64
+ D2VT)
Vnn
The proof is completed.
E
Experiments
Table 1: Exploring effect of 81 of Adam. We explore the dataset of Cifarl0 using VGG13[28] and
ResNet18[17] and [2K using Transforemer(29]. We show the training loss after 50 epochs
0.1
02
0.3
0.4
0.5
0.7
0.8
0.
0.99
0.999
0.9999
ResNet8
0.2268
02197
0,1158
0.2197
0.182
0.2198
0.2117
0.2204
0.2218
0,2322
0.331
0.3620
0.6137
Cifar10 VGGL3
0.1416
0.1428
0.1391
0.1421
0.1457
0.1419
WikiText2
3,3600
3,3589
3.3586
3.3573
3.3565
3.3599
3,3627
3.3634
3.3659
3.3749
3.4314
6,3274
7,5384
As mentioned in Section 6, one of the limitations of our theory is that it can not provide better results when momentum present. To complement such a limitation, we initialize a empirical study of the effect of momentum in Adam as follows.
Experimental setting. We use Adam training on Cifar 10 with ResNet18 [28] and VGG13 [17] and wikitext2 with lwyer Transformer [29] for 50 epoch and record its training loss at 50 epoch
26

---

as measure for the optimization speed. Smaller loss indicates better optimization. The batch size is 1024 for Ci dataset and 100 for WikiText2 Dataset.
The results are given in Table 1. Our discoveries are:
Momentum can benefit the optimization when the 3 is not too large.
For all datasets, larger $1 (Setting 31 close to 1) will worse the optimization.
Connection with Theorem One can easily observe that in Theorem 1 both C1 and C2 polyno- mially depend on I- and thus so does E Σ [V[(())] || = O ( Therefore, Theorem is aligned with the experimental results in the sense that both our theory and the experimental However, Theorem cannot explain the benefit of using momentum (by setting 31 larger than 0). This may be due to that our Theorem is worst-case analysis. We conjecture that theoretically deriving the benefit of momentum requires restricting the underlying objective function to a more specific range, which we leave as a future work.
results indicate that the Adam will become worse when the 31 close
27


Reviews:
[{"review_id": "eY1QuyKT3E", "reviewer": "Reviewer_oCro", "summary": "This paper gives a new analysis of the Adam algorithm intended to close the gap between the upper bound of Adam's iteration complexity and the existing lower bound for first-order nonconvex optimization. The authors show that existing analysis of Adam either uses the bounded gradient assumption, achieves a suboptimal iteration complexity, or relies on the mean-squared smoothness assumption. Afterwards, they give a novel analysis of the algorithm that meets the lower bound in dependence on the desired accuracy $\\epsilon$.", "questions": "1. Please address my concern in the weaknesses section.", "limitations": "N/A.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The new analysis of Adam is conducted under the same assumptions as standard SGD, unlike most prior work.\n- The new analysis of Adam achieves the optimal $\\frac{1}{\\epsilon^{4}}$ complexity with no additional log factors.\n- The authors introduce several technical tools that can be helpful in the analysis of adaptive algorithms more generally, for example the stochastic surrogates used are new.", "weaknesses": "- My main problem with this paper is that the proof, as it is, is very complicated to check. It would be very helpful if the authors included a section in the deterministic case (no stochasticity) with their full proof in this simplified setting.\n- The bounded variance condition is a bit restrictive (see [1]), can the convergence of Adam be derived under any of the more general conditions mentioned in [1]?\n- (Minor typos) line 134 should be log 1/\\epsilon not log \\epsilon.  Line 198 $G_{t-1}$ not $G_{t-2}$. Please use \\left and \\right for braces in line 229.\n\n[1] Ahmed Khaled & Peter Richtárik, Better Theory for SGD in the Nonconvex World, TMLR 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for your constructive comment and positive feedback. The raised typos have been corrected and below we dually respond to your comments.\n\n**Q1**: Proof in the deterministic case will be helpful.\n\n**A1**: Thanks for the helpful suggestion. We will take your advice and reorganize Section 4.2 by (i). first providing the proof in the deterministic case and then (ii). introducing the additional challenges in the stochastic case and how to solve it. Below we sketch the proof in the deterministic case.\n\n**Stage I.** We no longer need surrogate conditioner $\\tilde{\\nu_{t}^i}$ to disentangle the correlation between $m_t$ and $\\nu_t$ and we only need to handle the mismatch between $m_t$ and $G_t$ in the first-order term $-\\eta \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot m_t\\rangle$. To handle this, we first apply the definition of $m_t = (1-\\beta_1) (G_t+\\beta_1 G_{t-1}+ \\beta_1^2 G_{t-2}+...) $, and write $$-\\eta \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot m_t \\rangle= -\\eta (1-\\beta_1)( \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_t\\rangle + \\beta_1 \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_{t-1}\\rangle+\\beta_1^2\\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_{t-2}\\rangle+...).$$\n\nWe proceed by approximating $G_{t-i}$ by $G_t$ in the above equation, and have \n\n$$-\\eta \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot m_t \\rangle= -\\eta (1-\\beta_1)( \\langle G_t, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_t\\rangle + \\beta_1 \\langle G_{t-1}, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_{t-1}\\rangle+\\beta_1^2\\langle G_{t-1}, \\frac{1}{\\sqrt{\\nu_t}}\\odot G_{t-2}\\rangle+...) +\\text{Error Term}.$$\n\nIn the right-hand-side of the above equation, all terms except the \"Error Term\" (which is in the same order as the second-order term in the descent lemma) are negative. Applying the above equation to the descent lemma and summing it over iterations gives a bound of $\\sum_{t=1}^T\\sum_{l=1}^d \\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}}$.\n\n**Stage II.** Based on the observation that $(1-\\beta_2)G_{t,l}^2= \\nu_{t,l}-\\beta_2 \\nu_{t-1,l}$, we have $\\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}} = \\Omega (\\sqrt{\\nu_{t,l}}-\\sqrt{\\beta_2} \\sqrt{\\nu_{t-1,l}})$, which can transfer the bound of $\\sum_{t=1}^T\\sum_{l=1}^d \\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}}$ into a bound of $\\sum_{t=1}^T\\sum_{l=1}^d \\sqrt{\\nu_{t,l}}$. Due to $$ (\\sum_{t=1}^T\\sum_{l=1}^d \\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}})(\\sum_{t=1}^T\\sum_{l=1}^d \\sqrt{\\nu_{t,l}})\\ge (\\sum_{t=1}^T \\sum_{l=1}^d  \\vert G_{t,l} \\vert )^2,$$ applying bounds of $\\sum_{t=1}^T\\sum_{l=1}^d \\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}}$ and $\\sum_{t=1}^T\\sum_{l=1}^d \\sqrt{\\nu_{t,l}}$ provides the estimation of gradient norm and concludes the proof.\n\n**Remark**: Compared to the stochastic case, Stage I is much more simplified and no longer needs to disentangle the randomness in $m_t$ and $\\nu_t$, and Stage II is also much more simplified when transforming the bound of $\\sum_{t=1}^T\\sum_{l=1}^d \\frac{\\vert G_{t,l} \\vert^2}{\\sqrt{\\nu_{t,l}}}$ into a bound of $\\sum_{t=1}^T\\sum_{l=1}^d \\sqrt{\\nu_{t,l}}$.\n\n**Q2**: Can the assumption on noise be weakened to more general conditions mentioned in [1]?\n\n**A2**: Thanks for asking. A brief answer is that the proof can be extended to the more general noise assumption \"$E \\Vert O_f(w,z) -\\nabla f(w) \\Vert^2 \\le \\sigma_1^2 \\Vert \\nabla f(w) \\Vert^2+\\sigma_0^2$\" (called \"affine noise variance assumption\" in [Faw et al., 2022]), but we are not sure if it can be further generalized under the noise assumption \"$E \\Vert O_f(w,z) -\\nabla f(w) \\Vert^2 \\le \\sigma_2^2 (f(w)-f^*)+\\sigma_1^2 \\Vert \\nabla f(w) \\Vert^2+\\sigma_0^2$\".\n\nBelow we sketch how to extend the proof under the affine noise variance assumption (**we will provide detailed proof in the appendix of the revised paper**). The core difference of the proofs under different noise assumptions is the way to estimate the first-order term in Stage I. We leverage an auxiliary function $\\xi_t=\\sum_{l=1}^d\\frac{\\vert G_{t,l} \\vert^2 }{\\sqrt{\\tilde{\\nu_{t,l}}}}$ to handle the affine variance noise, where $\\tilde{\\nu_t}$ is defined as $\\tilde{\\nu_t}=\\beta_2\\nu_{t-1}+(1-\\beta_2) \\sigma_0^2$.\n\nFor simplicity, we focus on the case where $\\beta_1=0$, i.e., no momentum.  To disentangle the stochasticity between $g_t$ and $\\nu_t$, we use $\\tilde{\\nu_t}=\\beta_2\\nu_{t-1}+(1-\\beta_2) \\sigma_0^2$ to approximate $\\nu_t$ and thus the first-order term can be written as $$E [\\langle G_t,-\\eta \\frac{1}{\\sqrt{\\nu_t}}\\odot g_t \\rangle]=-\\eta E [\\langle G_t, \\frac{1}{\\sqrt{\\tilde{\\nu}_t}}\\odot G_t \\rangle]+E [\\langle G_t,\\eta (\\frac{1}{\\sqrt{\\tilde{\\nu}_t}}-\\frac{1}{\\sqrt{\\nu_t}})\\odot g_t \\rangle].$$ The first term on the right-hand side is the main term (which is negative) and we need to tackle the first term. By leveraging a similar routine as the proof of Lemma 1, we can arrive at the following estimation of the approximation error.\n\n$$\\textbf{Approximation Error} \\le  \\frac{1}{4}\\eta E [\\langle G_t, \\frac{1}{\\sqrt{\\tilde{\\nu_t}}}\\odot G_t \\rangle]+O(\\text{Second Order Term})+O(\\sum_{l=1}^dE(1-\\beta_2)\\frac{ g_{t,l} ^2 G_{t,l}^2}{(\\sqrt{\\nu_{t,l}}+\\sqrt{\\tilde{\\nu_{t,l}}})^2\\sqrt{\\tilde{\\nu_{t,l}}}} ).$$\nIn the right-hand-side of the above equation, the last term takes close resemblance to $\\frac{\\xi_{t-1}}{\\sqrt{\\beta_2}}-\\xi_t$ (after expansion), and indeed can be directly bounded by $O(\\frac{\\xi_{t-1}}{\\sqrt{\\beta_2}}-\\xi_t)$ plus some error term by direct calculation (recall that $\\xi_t=\\sum_{l=1}^d\\frac{\\Vert G_{t,l} \\Vert^2 }{\\sqrt{\\tilde{\\nu_{t,l}}}}$). The sum of $O(\\frac{\\xi_{t-1}}{\\sqrt{\\beta_2}}-\\xi_t)$ across t gives $(\\frac{1}{\\sqrt{\\beta_2}}-1)O(\\sum_{t=1}^T \\xi_t)$, which is small than the sum of the main term in the first-order term $-\\eta E [\\langle G_t, \\frac{1}{\\sqrt{\\tilde{\\nu}_t}}\\odot G_t \\rangle]$ when $\\beta_2$ is close to $1$, and thus we succeed to control the approximation error. The rest of the proof should be the same as under the original noise assumption."}, {"review_id": "kymxkPrBoY", "reviewer": "Reviewer_tjB4", "summary": "Adam is one of the most popular stochastic optimization algorithms especially in deep learning, the existing convergence theories do not achieve a tight upper bound that meets the lower bound. Moreover, many of them require additional assumptions, such as bounded gradient. This paper shows that Adam can achieve the tight bound of $O ( \\epsilon^{-4} )$ without such additional assumptions. This result closes the gap between the practical success of Adam and the theoretical sub-optimality.", "questions": "**Relation to [1]**\n\nAs I mentioned in the weaknesses section, I would like to know the relation between the results of this paper and [1].\n\n**What happens when using diminishing step size?**\n\nIn the analysis on SGD, diminishing step size (e.g., $\\eta_t = \\Theta ( 1 / \\sqrt{t} )$ is often used, because it is close to practical situations. Is it easy to extend this result to the case of diminishing step size? ", "limitations": "The limitations are mentioned in Section 6, which is clear to me.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical result is strong. Although there are many existing works that analyze the convergence of Adam, this paper is the first one that proves that Adam can converge with $\\mathcal{O} ( 1 / \\sqrt{T} )$, or equivalently $\\mathcal{O} ( \\epsilon^{-4} )$.\n- Technical improvements for deriving the result are interesting and clearly explained.\n- This paper is easy to read, and the presentation is also clear at least to the experts on the convergence theory of stochastic optimization.", "weaknesses": "**Relation to [1] is not clear**\n\nAlthough I am basically positive about the result of this paper, I am not sure about how it relates to the well-known result about the non-convergence behavior of Adam by [1]. They showed that there always exits a problem in which Adam fails to converge, but the authors' result seems that Adam can always converge with the optimal rate (i.e., $\\mathcal{O} ( \\epsilon^{-4} )$). In my current understanding, this is because Theorem 2 requires $1 - \\beta_2 = \\Theta ( 1 / T )$, which means that, in order to ensure the convergence of Adam, we need to choose the hyper-parameter $\\beta_2$ depending on the total number of parameter updates $T$. I think it would be better to clarify the relationship clearly in Section 7. Though the authors mention [1] in the section, the relation to their theoretical result is not clear to me. When it becomes clear in the rebuttal period, I will raise my score.\n\n**There are no experiments**\n\n- I think the condition of $1 - \\beta_2 = \\Theta ( 1 / T )$ is crucial to achieve the optimal convergence rate, so it would be better to demonstrate it experimentally (I think a toy experiment is enough).\n\n**Minor comments**\n\n- The notations of the output of Adam are inconsistent in Algorithm 1 ($\\boldsymbol{w}_r$) and Theorem 2 ($\\boldsymbol{w}_\\tau$), which is a little confusing.\n- Finishing a paper with Related work is not common in my opinion.\n- It would be better to add equation numbers to all the equations for the ease of communication between the reviewers and the authors.\n\n**Typos**\n\n- line 20: uderstand -> understand\n- line 198: $\\boldsymbol{G_{t-2} \\rightarrow G_{t-1}}$\n- line 248: pratice -> practice\n\n**References**\n\n[1] Reddi, Sashank J., Satyen Kale, and Sanjiv Kumar. \"On the Convergence of Adam and Beyond.\" International Conference on Learning Representations. 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the constructive comment and positive feedback. The raised typos have been dually corrected, and other concerns are dually addressed below.\n\n**Q1**: Relation to [1] is not clear.\n\n**A1**: Thanks for asking. We did not include a discussion on this because there has been a existing work [2] explaining why one can still establish a convergence result of Adam given the counterexample in [1] (**please see Section 4 in [2] for details, and we will include a discussion on this in the revised paper**). The counterexample in [1] is constructed by first choosing the hyperparameters of Adam ($\\beta_1$ and $\\beta_2$) and then **adversarially** choosing the objective function  for the chosen $\\beta_1$ and $\\beta_2$. Note that the noise variance $\\sigma$ of the chosen objective function has a dependence over the chosen $\\beta_1$ and $\\beta_2$.  One the contrary, if the objective function is fixed, then one can choose appropriate $\\beta_1$ and $\\beta_2$ so that Adam converges. This is exactly the setting in our paper (which is also in most optimization papers), where convergence results are provided after the configs of the objective function (including $L$ and $\\sigma$) are fixed. Therefore, there is no contradiction between [1] and our result.\n\n\n**Q2**: There are no experiments.\n\n**A2**: Thanks for the suggestion. We will include the following discussion in the revised paper.\n\n1. We conduct an experiment over the same toy example in (Figure 4, [2]) and plot the result in the pdf of the general rebuttal. Concretely, the objective function is defined as $f(x)=\\frac{\\sum_{i=0}^9 f_i(x)}{10}$, where $f_0(x)=(x-3)^2$ and $f_i(x)=-0.1(x-\\frac{10}{3})^2$ for $ 1\\le i\\le 9$. In each iteration, we uniformly sample $i$ from $[0,9]$ and use $\\nabla f_i$ as the gradient. We compare Adam with different schedulers of $\\beta_2$, respectively $\\beta_2 = 1- \\frac{0.1}{t}$, $\\beta_2 = 1- \\frac{0.1}{t^{0.5}}$, and $\\beta_2 = 1- \\frac{0.1}{t^2}$ (where $t$ is the number of iteration), and observe that Adam with  $\\beta_2 = 1- \\frac{0.1}{t}$ maintains the fastest convergence, which aligns with our observation.\n\n2. Also, we notice that there are real-world experiments in [3], which show that Adam with $\\beta_2=1-\\Theta(1/T)$ converges the fastest. We also include their result in the pdf of the general rebuttal.\n\n**Q3**: The notations of the output of Adam are inconsistent in Algorithm 1 and Theorem 2.\n\n**A3**: Thanks for pointing it out. We will revise the paper and use the notation of the output of Adam in Algorithm 1 in both two places.\n\n**Q4**: Finishing a paper with Related work is not common in my opinion.\n\n**A4**: Thanks for pointing it out. We will reorganize the paper and put Related Work after Section 3.\n\n**Q5**: Is it easy to extend this result to the case of diminishing step size?\n\n**A5**: Thank you for the question. Indeed, it is straightforward to extend the result to Adam with a diminishing learning rate by following a similar approach as in Theorem 2 (Theorem 1) and the corresponding rate will only differ from that in Theorem 2 by a $\\log T$ factor. This is because, in the proof of Theorem 2, we first analyze the descent lemma for each iteration and subsequently sum them together across iterations. To accommodate a diminishing step size, we can simply replace the learning rate in the analysis of the descent lemma and make minor adjustments when summing them together. We will include this discussion in the revised version of the paper.\n\n**References**:\n\n[1]. Reddi et al., On the Convergence of Adam and Beyond, 2019\n\n[2]. Zhang et al., Adam can converge without any modification on update rules, 2022\n\n[3]. Zou et al., A Sufficient Condition for Convergences of Adam and RMSProp, 2018\n"}, {"review_id": "nqddahyEpR", "reviewer": "Reviewer_ncBJ", "summary": "This paper analyzes the iteration complexity of Adam. It Is first pointed out that upper bounds in prior work do not match existing lower bound; the reason is that the lower bound is proved under smoothness and bounded noise variance, while prior upper bounds make more assumptions. This paper then proves a general upper bound (Theorem 1) which only requires smoothness and bounded noise variance and matches the lower bound up to a logarithmic factor. Later in Theorem 2, a refined analysis is given which further removes the logarithmic factor, and thus giving an upper bound that matches the lower bound exactly.", "questions": "Can SGD match the lower bound? Alternatively, can we show that Adam converges faster than SGD, which is usually observed in practice?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper analyzes the iteration complexity of Adam, which is a very important problem given Adam's popularity. Moreover, it is pointed out that existing upper bounds do not match lower bound, and this paper closes this gap, which is a nice contribution. The proof techniques may be of independent interest, such as the peeling-off strategy to handle the dependency between the momentum and the adaptive learning rate.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the positive feedback. Your concern is dually addressed as follows.\n\n**Q**: Can SGD match the lower bound? Alternatively, can we show that Adam converges faster than SGD, which is usually observed in practice?\n\n**A**: Thanks for asking. SGD can also meet the lower bound according to [1], and thus our results show that Adam can achieve the same order of convergence rate as SGD (which is the first time to our best knowledge). We acknowledge that our result can not be used to show that Adam converges faster than SGD since both meet the lower bound, but conjecture that this is because our analysis is a worst-case analysis. In order to show that Adam converges faster than SGD, we might need to carefully model the structure of neural networks and restrict ourselves to a more specific subset of the objective function space. We leave this as a future work.\n\n**Reference**:\n\nGhadimi et al., Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming, 2013"}, {"review_id": "p9LWBrwSh0", "reviewer": "Reviewer_b4JJ", "summary": "This paper presents a convergence analysis of Adam under only the smoothness and bounded variance conditions. ", "questions": "I have the following concerns. If the authors could address the concerns, then I think that the paper has the contribution and novelty.\n- Theorem 1/Theorem 2 implies the upper bounds of the gradient norm of Adam using a constant step-size $\\eta$/a diminishing step-size $\\eta = a/\\sqrt{T}$. The theorems lead to the finding that, e.g., (Lines 159--162) \"Theorem 1 holds for general choices of hyperparameters since the only condition posed on hyperparameters is $\\beta_1 < \\beta_2$. Such condition covers a wide range of hyperparameters, e.g., the default setting $\\beta_1 = 0.9$ and $\\beta_2 = 0.999$ in PyTorch [19].\" I understand that using $\\beta_1$ and $\\beta_2$ close to 1 is useful to implement Adam. However, I cannot understand that Theorem 1 implies the claims in (Lines 159--162). Does Theorem 1 imply that $\\beta_1, \\beta_2 \\approx 1 \\Rightarrow$ the right-hand side of (2) is small? Can the authors show that the right-hand side of (2) is a decreasing function with respect to $\\beta_1$ and $\\beta_2$?\n- The above discussion holds for Theorem 2 and Lines 250--253. Does Theorem 2 imply that $a, b \\approx 0 \\Rightarrow$ the upper bound of the gradient norm is small? Can the authors show that it is decreasing when $a$ and $b$ are small?\n- The above two concerns mean that there is a gap between theory (Theorems 1 and 2) and practice ($\\beta_1 = 0.9$ and $\\beta_2 = 0.999$). Can the authors bridge the gap?\n- Can the authors provide lower bounds of the gradient norm of Adam, such as $\\mathbb{E}\\sum_{i=1}^T \\Vert \\nabla f(w_t) \\Vert \\geq$ $C \\times$  (the right-hand side of (2))?\n- Paper [25] and its references are sufficient for both theory and practice.  Can the authors show more novelty and contributions from Theorems 1 and 2?\n- Related to the above concern, I believe that practical results (e.g., numerical results and new setting of hyperparameters) are provided based on the novelty and contributions of the paper. Can the authors provide such practical results? For example, it would be nicer to compare numerically Adam using $\\beta_1 = 0.9$ and $\\beta_2 = 0.999$ with Adam using the new setting of $\\beta_1$ and $\\beta_2$ based on Theorems 1 and 2.", "limitations": "There is no potential negative societal impact.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The strength of the paper is to present a convergence analysis of Adam under only the smoothness and bounded variance conditions, in contrast to the existing analyses (Section 3). We are interested in the analysis of Adam under only the two conditions, since the conditions are more natural and realistic than the boundedness of the gradient norm of the objective function and the Lipschitz continuity of the stochastic gradient.  \n-  The abstract indicates that \"Especially with properly chosen hyperparameters, we derive an upper bound of iteration complexity of Adam and show that it meets the lower bound for first-order optimizers.\" Proposition 1 shows that the iteration complexity $\\mathcal{C}$ of a first-order optimizer is $\\Omega (1/\\epsilon^4)$, that is, there exist $c_1, c_2 > 0$ such that $c_1/\\epsilon^4 \\leq \\mathcal{C} \\leq c_2/\\epsilon^4$. Theorem 2 implies that Adam satisfies that $\\mathcal{C} = O(1/\\epsilon^4)$. Hence, the paper concludes the claim of the abstract. ", "weaknesses": "I understand the motivation of the paper. Meanwhile, many theoretical and practical results of Adam have been presented. Hence, unfortunately, I do not find that the results in the paper are surprised as compared with the existing ones. Please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and time. After reading the review, we realize that there could be misunderstandings over our contribution, which we try to clarify as follows.\n\n**On the novelty and contribution.** From the theoretical perspective, characterizing the upper bound and lower bound of iteration complexity of an algorithm is the most fundamental problem in ML/optimization community. Thus, closing the gap between the upper bound and lower bound should be considered as a significant contribution, as also acknowledged by other reviewers. We argue that it becomes more than novel by addressing a critical gap in the understanding of Adam's performance given that Adam is currently one of the mainstream optimizers for deep learning.   \n\nOther concerns are dually addressed below.\n\n**Other concerns:**\n\n**Q1**: I cannot understand that Theorem 1 implies the claims in (Lines 159--162). \n\n**A1**: There could be a misunderstanding. \" Theorem 1 holds for general choices of hyperparameters\" means that for a wide range of hyperparameters, you can apply Theorem 1 to get an estimation of gradient norm (i.e., Eq. (2)). Such a claim has nothing to do with when right-hand side of (2) is small and is only about the applicable region of Theorem 1. \nHowever, we thank the reviewer for asking an interesting question that \"Does Theorem 1 imply that $\\beta_1,\\beta_2\\approx 1\\rightarrow $  the right-hand side of (2) is small\", which we try to answer in **A3**.\n\n**Q2**: Does Theorem 1 imply that $\\beta_1,\\beta_2\\approx 1\\rightarrow $ the right-hand side of (2) is small?\n\n**A2**: Thanks for asking. Below we discuss the parameter settings of $\\beta_1$ and $\\beta_2$ respectively, and we will include the discussion in the revised paper.\n\n **As for $\\beta_2$**: Our result does indicate that \"to make the right-hand-side of (2) small, $\\beta_2$ needs to be chosen close to 1\". Specifically, according to Lines 169-178 in our paper, $\\beta_2$ needs to be picked as $1-O(1/T)$ to to minimize the  the right-hand-side of (2), which is close to $1$ when $T$ is large (which is the case in practice). Therefore, our Theorem 1 agrees with the practical use of $\\beta_2$.\n\n**As for $\\beta_1$**: Our result does not indicate that \"setting $\\beta_1$ close to $1$ is necessary to ensure the right-hand-side is small\". This agrees with practice, where $\\beta_1$ is not necessarily chosen close to $1$. As an example, in the well-worned work \"Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks\", $\\beta_1$ is chosen as $0.5$, which is not close to $1$.\n\n**Q3**: Similar question for Theorem 2. Does Theorem 2 imply that $a,b\\approx 0$ leads to a small bound?\n\n**A3**: Thanks for asking. We guess that the reviewer is talking about $b$ because $a$ is the hyperparameter of the learning rate. Here we do not require $b\\approx 0$ because we set $\\beta_2 = 1-\\frac{b}{T}$, which is already close to $1$ when $T$ is large.\n\n**Q4**: The above two concerns mean that there is a gap between theory (Theorems 1 and 2) and practice.\n\n**A4**: Based on **A2** and **A3**, we respectfully argue that there is no such gap between theory and practice. Instead, our theorem agrees with the practice where $\\beta_2$ is close to $1$ and $\\beta_1$ is less constrained.\n\n**Q5**: Can the authors provide lower bounds of the gradient norm of Adam as the right-hand-side of (2)?\n\n**A5**: We thank the reviewer for the suggestion, but have to point out that such kind of bound is missing even for SGD to our best knowledge. This is beyond the scope of our paper and should be treated as a challenging future direction.\n\n**Q6**: Paper [25] and its references are sufficient for both theory and practice.\n\n**A6**: There could be a misunderstanding. As stated in Section 3, \"None of existing upper bounds match the lower bound\", including Paper [25] and its references. Specifically, Paper [25] can only get a sub-optimal iteration complexity $O(1/\\varepsilon^6)$, which is even slower than SGD. Our paper is the first to obtain an upper bound of iteration complexity of Adam matching the lower bound, which, as discussed ealier, is a novel contribution.\n\n**Q7**: Can authors provide empirical evidence for this paper? For example, it would be nicer to compare numerically Adam using  and  with Adam using the new setting of $\\beta_1$ and $\\beta_2$.\n\n**A7**: We thank the reviewer for the suggestion. However, as pointed out in **A2, A3, and A4**, there is no such a gap between the practical setting of $\\beta_1$ and $\\beta_2$ and \"the new setting\". Nevertheless, we include a toy example conducted by us and a real-world experiment by existing works to demonstrate the superiority of the choice $\\beta_2=1-\\Theta(\\frac{1}{t})$ over other choices (please see the pdf in the general rebuttal).\n"}]

Author rebuttal:
We thank ACs, SACs, PCs, and reviewers for the efforts and time spent in handling our paper. According to the suggestions of Reviewer oCro and Reviewer b4JJ, we include several experiments to support our theoretical claims. The plots can be found in the attached pdf file. Specifically:

1. We run Adam with different schedulers of $\beta_2$ over a toy example proposed in [1];

2. We adapt a figure from [2], which train ResNet 18 over CIFAR-100 using Adam with different schedulers of $\beta_2$.

All of the experiments indicate that Adam with scheduler $\beta_2=1-\Theta(1/T)$ maintains the fastest convergence, which supports our Theorem 3.

**References**

[1]. Zhang et al., Adam Can Converge Without Any Modification On Update Rules, 2022

[2]. Zou et al., A Sufficient Condition for Convergences of Adam and RMSProp, 2018

Meta-review: The paper tries to develop a proof of Adam for non-convex problems under only two standard assumptions bounded gradient and smoothness of the objective function. It either removes bounded gradient or stochastic gradient assumption or the individual smoothness assumption and manages to prove the standard convergence rate.

There was intensive discussion between the authors and one reviewer about the setting of  $\beta_1$. The result seems to suggest that the smaller $\beta_1$ the better the convergence, which seems to contradict to empirical results and prior works. The authors agree to provide more empirical results to justify the limitations of the theoretical results regarding the value of $\beta_1$. Given the contribution and discussion, AC thinks the paper makes enough contributions to be published at NeurIPS conference. The new proof techniques might inspire new works for analyzing Adam algorithms. The authors are encouraged to add more empirical results about the $\beta_1$ issue, including generalization and training curves.
Decision: Accept (poster)