Provable Adaptivity in Adam
Authors: Bohan Wang
Yushun Zhang
Huishuai Zhang
Qi Meng
Zhi-Ming Ma
Tie-Yan Liu
Wei Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Benefit of Adam
convergence
SGD
optimization

Abstract: Adaptive Moment Estimation (Adam) has been observed to converge faster than stochastic gradient descent (SGD) in practice. However, such an advantage has not been theoretically characterized -- the existing convergence rate of Adam is no better than SGD. We attribute this mismatch between theory and practice to a commonly used assumption: the gradient is globally Lipschitz continuous (called $L$-smooth condition). Specifically, compared to SGD, Adam adaptively chooses a learning rate better suited to the local gradient Lipschitz constant (called local smoothness). This effect becomes 
prominent when the local smoothness varies drastically across the domain.
In this paper, we analyze the convergence of Adam under a condition called $(L_0,L_1)$-smooth condition, which allows the gradient Lipschitz constant to change with the gradient norm. This condition has been empirically verified to be more realistic for deep neural networks \citep{zhang2019gradient}  than the $L$-smooth condition. Under $(L_0,L_1)$-smooth condition, we establish the convergence for  Adam with practical hyperparameters. As such, we argue that Adam can adapt to this local smoothness condition, justifying Adam's \emph{adaptivity}. In contrast, SGD can be arbitrarily slow under this condition.   Our result can shed light on the benefit of adaptive gradient methods over non-adaptive ones.

Under review as a conference paper at ICLR 2023
PROVABLE BENEFIT OF ADAPTIVITY IN ADAM
Anonymous authors
Paper under double-blind review
ABSTRACT
Adaptive Moment Estimation (Adam) has been observed converge faster than stochastic gradient descent (SGD) in practice. However, such an advantage has not been theoretically characterized the existing convergence rate of Adam is no better than SGD. We attribute this mismatch between theory and practice to a commonly used assumption: the smoothness globally upper bounded by some constant L (called L-smooth condition). Specifically, compared to SGD, Adam adaptively chooses a learning rate better suited to the local smoothness. This advantage becomes prominent when the local smoothness varies drastically across the domain, which however is hided under L-smooth condition. In this paper, we analyze the convergence of Adam under condition called (In, [1) -sm-smhoth condition, which allows the local smoothness to grow with the gradient norm. This condition has been empirically verified be more realistic for deep neural networks (Zhang et al., 2019a) than the L-smooth condition. Under (Lo. L1) -smoothh condition, we establish the convergence for Adam with practical hyperparameters. As such, we argue that Adam can adapt to the local smoothness, justifying Adam's 's benefit of adaptivity. In contrast, SGD can be arbitrarily slow under this condition. Hence, we theoretically characterize the advantage of Adam over SGD.
INTRODUCTION
Machine learning tasks are often formulated as solving the following finite-sum problem.
min f(w)
Σ f((w),
(I)
weRd
1=0
where (w) 1,-1 is lower bounded, n denotes the number of samples or mini-batches, and w denotes the trainable parameters. Among various gradient-based optimizers, Stochastic Gradient Descent (SGD) is a simple and popular method to solve Eq. (1). However, Adaptive gradient methods including Adaptive Moment estimation (Adam) (Kingma Ba, 2014) is recently observed to outperform SGD in modern deep neural tasks including GANs (Brock et al., 2018), BERTs (Kenton & Toutanova, 2019), GPTs (Brown et al., 2020) and ViT' (Dosovitskiy al., 2020). For instance, as reported in Figure 1. (a): SGD converges much slower than Adam during the training of Transformers. Similar phenomena are also reported in BERT training (Zhang et al., 2019b).
The empirical success of Adam comes from its special update rules, Firstly, it uses the heavy- momentum mechanism controlled by hyperparameter 31. Second, it uses an adaptive learning rate strategy. In particular, the learning rate of Adam contains exponential moving averages of past squared gradients, which weighted by 32. Larger 3, and 32 will bring more gradient information of historical steps into the update. The update rule of Adam is given in Eq. (2) (presented later in Section 3).
Despite its practical success, the theoretical understanding of Adam is limited. For instance, the existing convergence rates Adam are no better than that of SGD (Zhang et al., 2022; Shi et al., 2021; Défossez et al., 2020; Zou et al., 2019; De et al., 2018; Guo al., 2021). As such, there is mismatch between Adam's superior empirical performance and its theoretical understanding.
To close the gap between theory and practice, revisit the existing analyses for Adam. Current setups for the analysis of Adam fail to model the real-world applications: all of the convergence analyses of Adam based on T-smooth condition, i.e., the Lipschitz coefficient of the gradient is

---

Under review as a conference paper at ICLR 2023
globally bounded. However, it has been recently observed that L-smooth condition does not hold in many deep learning tasks (Zhang et al., 2019a; Crawshaw et al., 2022). This gap in setting can obscure Adam's superiority: different local Lipschitz coefficients of the gradient (local smoothness) may require different optimal learning rates in terms of convergence. However, the learning rate of SGD is ignorant of the local smoothness along the training trajectory. If the local smoothness does not change sharply along the trajectory, the optimal learning rate does not change much. Then SGD can work well by selecting a learning rate through grid search. However, when the local smoothness varies dramatically, a learning rate fits some points well may fit other points along the trajectory arbitrarily badly, which indicates SGD may converge arbitrarily slow (detailed discussions can be found in [Theorem 4, (Zhang et al., 2019a)] and Section 4.3 in this paper). In contrast, Adam adapts the update according to the local information and does not suffer from such an issue.
Following the above methodology, we analyze the convergence of Adam under (To, I-)-mmooth condition, which assumes the local smoothness (the spectral norm of the local Hesssian) to be upper bounded by L1 (local gradient norm) + Lo (Assumption 1). As the gradient norm can be unbounded, (Lo, L1 -smothh condition allows the local smoothness to grow fiercely with the gradient norm. Moreover, it has been demonstrated by (Zhang et al., 2019a; 2020a; Crawshaw et al., 2022) that for many practical neural networks, Lo. -smooohhh condition more closely characterizes the optimization landscape (as illustrated by Figure (b)) along the optimization trajectories.
(a) Training loss
(b) Gradient norm vs. smoothness
Figure I: For Transformer (Vaswani et al., 2017) the WMT 2014 dataset, we plot (a) the training loss of SGD and Adam and (b) the gradient norm vs. the local smoothness on the training trajectory. The blue line stands for olocal smoothness) log( graddent norm) + 1.4. It can be observed that all the (log( (gradient norm), log (local smoothness)) points lic under this line, and thus the training process obeys (0, - -mooohhhh condition.
Under (Lg, L1 smooth condition, we successfully establish the convergence of Adam. Meanwhile, in contrast, under the same assumption, it is proved that SGD can be arbitrarily slow in (Zhang et al., 2019a) or even diverge (see Section 4.3). Therefore, our theory demonstrates that Adam can provably converge faster than SGD. The main contribution of this paper is summarized as follows.
We derive the first convergence result of Adam under the more realistic (Lo, I, -mmoohh condition (Theorem 1). First, our convergence result is established under the mildest assumption so far:
(Lo, L1) smooth condition is strictly weaker than L-smooth condition. More importantly,
(Lo, L1) smoohhh condition is observed to hold in practical deep learning tasks. Relaxing the smoothness condition is important characterize the advantage of Adam over SGD.
Our result does not require the bounded gradient assumption (i.e. [ < C). Removing such a condition necessary, as otherwise (Io, In I -mooohh condition will degenerate to L-smooth condition. Our result does not need other strong assumptions like bounded adaptor or large (see Eq. (2)), either.
Furthermore, the conclusion of our convergence result is among the strongest.
Our convergence result holds for every possible trajectory. This is much stronger than the common results of "convergence in expectation" and is technically challenging.
In our convergence results, the setting of hyperparameters (31, 32) is close practice. Specifically, our result holds for any 31 and any 83g close to 1, which matches the practical settings (for example, 0.9 and 0.999 in deep learning libraries).
2

---

Under review as a conference paper at ICLR 2023
We also provide counter-example where SGD diverges under the same setting in Theorem 1. Therefore, our results can shed new light on why Adam outperforms SGD in deep learning tasks.
The rest of this paper is organized follows: Section 2 summarizes the related works; Section 3, introduces notations and assumptions; Section presents our convergence result of Adam along with the proof ideas.
RELATED WORKS
Convergence analysis for Adam. When Adam is firstly proposed in (Kingma & Ba, 2015), the authors provide convergence proof. However, Reddi al. (2019) point out that the proof in (Kingma & Ba, 2015) has flaws. They further provide simple counterexamples with which Adam diverges. Ever since then, there have been many attempts to modify the update rules of Adam to ensure convergence: c.g., AMSGrad (Reddi et al., 2019) and AdaBound (Luo et al., 2019). Due to the limited space, we introduce more details of the Adam-variants in Appendix A.
On the other hand, vanilla Adam works well in practice, and the divergence is not reported unless for carefully constructed examples. This empirical phenomenon motivates researchers to rethink the counterexamples. The counterexamples states "for every 31 < vB2, there exists problem that Adam diverges". That to say, the divergence statement requires picking (3,, (2) before fixing the problem, while in practice, the algorithmic parameters are often picked according to the problem. Based on this observation, a recent work (Zhang et al., 2022) proves that Adam can converge with (81,8) B2) picked after the problem is given.
Similar analyses on vanilla Adam and RMSProp are also shown under various conditions (Zaheer et al., 2018b; Zou et al., 2019; Défossez et al., 2020; De et al., 2018; Guo et al., 2021; Shi et al., 2021). We list and compare these results in Table for convenience. summary, we emphasize that all the above works (including those for Adam- variants) require L-smooth condition. In addition, most of them require stronger assumptions such as bounded gradient or large
[Lo Ly |-Smoothuness
Allow 3, * g(9) Allow g19) Allow unbounded gradient
Trajectorywiise convergence
Zabeer (20186)
De et al. (2018)(4
x
Délosezz (2020)
Guo et al. (2021)(*)
x
V
Huang et (2021)66)
Shi et al. (2021)
X
Zhing (2022)
This work
Table 1: Comparison of existing convergence result of Adam. All the literature requires L-smooth condition, which is strictly stronger than (Lo, -moothh condition. We provide some explanation
on the upper footmarks: (a): When 31 = 0, Adam is reduced to RMSProp (Hinton et al., 2012), the analysis of which is essentially simpler due to the lack of the momentum term; (b): the stability hyperparameter in Adam (see Eq. (2)). In practice, & is often a small number such as 10-8, In theory, should be arbitrarily small, including (c): Zaheer et al. (2018b) further requires the signs of the gradients to remain the same along the trajectory: (d): Guo et al. (2021); Huang et al. (2021) require 0.
/Dk, E be lower bounded, which is equivalent to requiring
In this work, we focus on the convergence of vanilla Adam. In particular, our result is the first to relax L-smooth condition for Adam. Moreover our convergence analysis of Adam is proved under the mildest assumptions so far and with the strongest conclusions, which can be easily extended to other Adam-variants as well.
Generalized smoothness assumption. There are several attempts on relaxing I-smooth condition. Zhang et al. (2019a) propose LI) -mooohh condition to thcoretically explain the acceleration effect of clipped SGD over SGD. Similar results are also extended to clipped SGD with momentum (Zhang al., 2020a) and differentially privvate SGD (DP SGD) (Yang al., 2022). Through extensive experiments, these works empirically showed that (Lo, L, smooth condition holds when Adam outperforms SGD. However, they did not theoretically analyze Adam in this setting.
Theoretical comparison between adaptive gradient methods and SGD. The comparison between adaptive gradient methods and SGD is popular topic. There several theoretical works from
3

---

Under review as a conference paper at ICLR 2023
different perspectives. Ward et al. (2020); Défossez et al. (2020); Faw al. (2022) show that AdaGrad can converge with any constant learning rate. They argue that duming-free- is one advantage of AdaGrad over SGD. This line of works has the following differences with us. First, they analyze AdaGrad while we focus on Adam. Second, they require I-smooth, while we do not have this condition. Third, their proposed convergence rate is no better than SGD, while we show Adam can converge faster.
Xie et al. (2022) study the escaping rate from saddle points of the continuous dynamics approximation of Adam and SGD. They show that adaptive learning rate can help escape saddle points efficiently. This work is orthogonal to ours: they compare the behavior of Adam and SGD after certain stationary point is reached, while we focus on comparing the iteration complexity of approaching the stationary points.
Zhang et al. (2020b) prove that the (adaptive) clipped gradient method converges faster than SGD when the stochastic noises are heavy-tailed. As such, they argue that the heavy-tailed noise is one cause of SGD's poor performance. However, recent work (Chen et al., 2021b) shows that (S)GD still performs poorly even when the stochastic noise is removed in the training process (by using the full-batch gradient). which shows that the effect of the stochastic noise may not be crucial. There are also recent works (Zhou et al., 2020; Zou et al., 2021) trying to compare the generalization behaviors of adaptive gradient methods and SGD. These works are orthogonal to the topic of this work. More detailed discussion is deferred to Appendix A.
3 PRELIMINARIES
This section introduces notations, definitions, and assumptions that are used throughout this work. Notations. We list the notations that are used in the formal definition of the randomly-shuffled Adam and its convergence analysis.
(Vector) We define a @ b the Hadamard product (i.e., component-wise product) between two vectors and b with the same dimension. We also define (a, b) as the l² inner product between a and b, and ||a|]] as the l norm of a (specifically, we abbreviate the l² norm of a as []a[]. We define La as an all-one vector with dimension d.
(Derivative) For a function f(w): Rd + I. we define V f(w) as the gradient of f at point w, and (w) as the (-th partial derivative of f at point w. i.e., 0. (Vf(w)).
(Array) We define [mi, m2] A {m...... .m²). Vmn, m2 N, m1 m2. Specifically, we use [m] e .1.....m..
Formal Definition of Adam. Based on the n-sum problem Eq. (1), we provide the update rule of Adam as follows. We initialize w1.0, 11,-1, and 11,-1 as any point in Rd. At the beginning of every outer loop & E NT, we sample {Tk.0, ... n as a random permutation of {0, 1, ,n - 1}. Then, in each inner loop i E [0, n 11, we respectively calculate the 1st-order momentum mg,i, the 2st-order momentum Vk.i, and the parameter Wk,i+1 as
M = -. + (1 V (wk.)):
Vk.s 32 + (1 Vra. (We,s) O V ffr.:(Wk.l)
(2)
WRit+1 = Wkki Wkittela
De C m
In the end of the outer loop k Adam updates Wk+1.0 Wkins 1k+1,-1 Mk M
M as a preparation for the next outer loop. my, and Va,i are weighted averages with hyper- paramter B1 [0,1) and [3 [0, 1), respectively. We choose Mi to be diminishing learning rate T = 21 In practice, E is adopted for numerical stability and it is often chosen to be 10- in practice. V In our theory,
allow be arbitrary non-negative constant including O. We further emphasize that that our analysis holds for any random permutation order used to generate Tk,i. In the default setting in deep learning libraries, the pure Adam is implemented in the random shuffling fashion and it is the default setting for computer vision, NLP, and generative models.
We make mild assumptions the objective function (Eq. (1)).
4

---

Under review as a conference paper at ICLR 2023
Assumption 1 (Lo, -smoohh condition). f((w) satissies (Lg, L1) -smoohh condition, i.e., there exist positive constants (Lo, L1), such that, Ves, W2 E R satisfying |m w2ll $ 1
En'
( v - (Lo + f:llvi((w))l)) I w2ll.
(3)
Eq. (3) is firstly introduced by Zhang al. (2019a). It is strietly weaker than the classical L- smooth condition (i.e., L1 = O in Assumption 3, see [Remark 2.3. (Zhang et al., 2020a)] for details). For instance, Eq. (3) holds for wide range of polynomials and even the exponential functions, while I-smooth condition does not hold for polynomials with degree larger than 2. More importantly, empirical observation in (Zhang et al., 2019a; 2020a) demonstrates that Eq. (3) is better characterization of the loss landscape of neural networks than L-smooth condition, especially the tasks where Adam significantly outperforms SGD.
Assumption 2 (Affine Noise Variance). V'w E IR, the gradients of (fi(w) has the following connection with the gradient of f(w))
& D:llVf(w)]1++ Do.
Assumption 2 is quite general, which covers the "bounded variance" assumption (Ghadimi et al., 2016; Zaheer et al., 2018a; Huang et al., 2021) and the "strongly growth condition" existing literature (Schmidt & Roux, 2013; Vaswani et al., 2019). Compare to the "bounded variance" assumption where the noise diminishes when the gradient is large, Assumption allows the noise variance to grow with the gradient norm, and thus applies to a rich variety of problems (e.g., (Khani & Liang, 2020)). Furthermore, combining Assumptions and 2, we conclude that f satisfies (nLo + LA /nv/ Do, L1 Aan////D) -ssmooothhh condition. The proof is immediate and we defer it to Lemma 2 in the appendix.
MAIN RESULT
4.1 ADAM CONVERGES WITH (Lo, L.LLLI-SSMOOI CONDITION
We formally present our main result as follows:
Theorem 1. Consider Adam defined as Eq. (2) with diminishing learning rate nk =
Let
vi"
Assumptions 1 and 2 hold. Suppose that 31 and B2 satisfies S8 < B2 <
and
8(32) 2 Vddmax
1
B2
1, 1, 1,822//
1,
v 32
n
2(1 82
15-1 + 8n 33.
P4
32
T
(4)
2(4+ D2) 11 11
1+81 T-52
Then, we have that
[. [V]](w)))]
log
min kE
S o
+ O(VDoo min ((3)),((8))
(S)
VD
VDo
VT
Theorem 1 shows that Adam converges to the neighborhood of stationary points under (Lo, L1)- smooth condition. The coefficient of log is O + [2] with respect (Lg, L1). In Section 4.2, VT
we present a proof sketch to illustrate our proof idea.
Remark (The choice of hyperparameters (81, 82)). In Theorem 1, the feasible range of (B1,8) subject to the two constraints: 3 < B2 < and Inequality (4). emphasize that the intersection of these two constraints is not empty. One can easily observe that 5(ß2) - 0 as 3n + 1, and thus the constraints hold when 31 is fixed and B2 approaches 1. Therefore, Theorem indicates that Adam can work when 32 close enough to 1. On the other hand, there is little restriction on B1 except 33 < 32 (discussed in Appendix B). This agrees with B2 selection in deep learning libraries (e.g.. 0.999 in Pytorch). On the other hand, there are counterexamples in (Zhang et al., 2022), where Adam is showed to diverge if 3g are chosen improperly (i.e., not close to 1). Therefore, the condition that Ba is close to 1 is both sufficient and necessary for the convergence of Adam.
5

---

Under review as a conference paper at ICLR 2023
Remark 2 (Convergence to the neighborhood of stationary points). When Do + O, theorem can only ensure that Adam converges to neighborhood of stationary points. As discussed under Assumption 2, convergence to the bounded region is common for Adam analysis: even with L-smooth condition, Zhang et al. (2022) can only show that Adam with diminishing learning rates converges to bounded region. This is because even with diminishing 7h the effective learning rate Ser.
fik
may not decay. We further conduct experiments and observe that Adam cannot reach the stationary point over a simple quadratic function with Do * 0. Specifically, we run Adam on a synthetic optimization target which is given as follows:
fu(z) = (3
1 10
f(())
1 10
10
+ 10'
9 [1,9), f(x) f((x))
11
1
3
10"
Such an example is proposed by (Shi et al., 2021). One can easily observe that f(x) and (f(( satisfies Assumption and Assumption 2 with D 208, Do = g g' thus Theorem I applies. With the diminishing learning rate T = ve we plot the distance between Adam's 's trajectory and the unique minimum 0 of f in Figure 2. It can be observed that Adam does not converge to the unique minimum O, but gets closer to the minimum if choosing 32 closer to 1, which supports Theorem 1.
0.700
0.175
0.300
0.175
0.575
0.000
0.000
Figure 2: Performance of Adam on a synthetic objective satisfying (Tog Lm)-shooth condition. Adam converge to the unique stationary point, but gets closer to the stationary point as 822 + 1.
The good news is the neighborhood shrinks as 32 + 1, which explains the practical use of large 32-
Furthermore, we refine the bounded region {w min { [[W)(
((vDo5(B2)))
VD.
DD
in existing literature (Shi et al., 2021; Zhang et al., 2022) to {w : min{ [V
VD, VDo
(DD min(8(32). {( through a more careful analysis. We emphasize that this change contributes to sharp improvement since 6(32) is required to be close to O.
Remark 3 (Dependence on the dimension d). The convergence rate and the neighborhood have polynomial dependence over the dimension d, which is not desired as the convergence rate of SGD under L-smooth condition does not have such a dependence. We conjecture that such dependence may be due to the limit of proof techniques. However, such a result suffices to provide a convergence rate separation between Adam and SGD since will latter show that SGD may converge arbitrarily slow under (Log I,)- -mmoshhhhh condition. Furthermore to the best of our knowledge, all the existing convergence analysis of Adam has the dependence of even under L-smooth condition e.g., (Défossez et al., 2020; Shi et al., 2021; Zhang et al., 2022). Though we believe that removing the dependence on is possible and worthy studying. it is technically difficult and deserves an independent work.
Remark& 4 (Constant learning rate). Following the same proof strategy of Theorem 1, one can show that with constant learning rate т}, the conclusion (Eq. (5)) of Theorem 1 changes into min [ f(w>.)). (ww < O log O(VDo min ( (8(3)), 8(22) +(().. In other vDr
VDo
words, Adam will converge faster to the neighborhood (with rate 1/v - 1/t), but the size of neighborhood is enlarged by an additional term O()) due to the constant step-size.
Remark 5. Theorem allows both 31 = 0 (RMSprop) and B > 0 (Adam). However, the convergence rate of these two cases are not distinguished, showing no benefit of momentum so far, At the current

---

Under review as a conference paper at ICLR 2023
stage, take first step compare RMSProp & Adam SGD. A more detailed comparison between RMSprop and Adam will be considered as future work. For completeness, we briefty discuss on the difficulty in analyzing the effect of momentim in Appendix B.
4.2 PROOF IDEAS
Here, we briefly explain our proof idea for the convergence result. We will first prove Theorem 1 for RMSProp (i.c., 31 0) show the challenge brought by (Lo, Lm)-smooth condition and how tackle it. We then show the additional difficulty when extending the result to general Adam and our corresponding intuition solve it.
Stage I: Convergence of RMSProp. We start with the following descent lemma:
Tioe || 11+110 wx
f(=x+100) f(wx,o) <(W++1,0 Wk,o. (s(wL))))
(6)
First Order
Second Order
where Lioe is the local smoothness. We first bound the second order term by noticing that the norm
of the epoch-k update of RMSProp is in order ((T))) when 0 = 88 < 32 < (a standard property
with proof deferred to Lemma 3 in the appendix). When large enough, the epoch-k update is
small enough and (Lo, -smmoohh condition applics, leading to Lioe O(1) + (w))ll and
the second order term = (n + V ff())]l). Therefore, in order to show f(w).0) decreases,
we need to prove the first order is negative and dominates the term O +
In other words, we need to lower bound the alignment between the update Wx+1,0 Wh.0
Ei ETatyPEs @ VT (WERk) and the negative gradient - V((wk,.)). It is easy to prove such property when Pk,s does not change, i.e.. if are analyzing SGD with preconditioning, which case E, Elttinn fTr. (wk,)) = E: elatvero 3 fr.. (wx,)) Σi elatvveoo f (wx,o)
slatvmoo f(ww..)) Can we extend the above methodology to RMSProp? We give an affirmative answer when $2 is close to 1 and the gradient is large by providing the following lemma.
Lemma (Informal). For any 1 [d]] and [0, 1). if maxpe(0.n-1] (ur,,
OE k-1 B2 (k-1-) Th [Vf(w,,o)l + m.), then |ILA, Vt,.oul = ((8(32)
The proof idea is that (1). the squared maximum gradient can be bounded by PLA.O with error term. Thus when the maximum gradient larger than the error term, it can be only bounded by
Vr,x.o: (3). thus Vr, = 3 V),,0000 o + (1 3,3 VVS + +... 33 + (1-33)) (vt,,)))) gets close VI,A00 when 32 is close to 1. The detailed proof is sophisticated due the presence of
(Lo, L1 -smooth condition and we defer it to Corollary 2 for details. Therefore, if we denote those
dimensions with large gradients (i.e., satisfying the requirement of Lemma 1) as Liarge and the rest as L
smoll Lemma 1 indicates
(w1,+11,0 o1,k (ww.o) Oh
PeAT +
Vi,.o Lerge
(, (we,o))
[[V VDr
my min
Large
max
vDo
Here in the second "R=", large. formal derivation of the above result can be seen Appendix D.2. How about the dimensions in L immal? We will treat them error terms. Specifically, I IL Immall indicates that
again the squared maximum gradient is close v1,00 if it is
R-1 P2 (k-1-r)
Mr / + m)). One can easily observe that 01Sre, (me,,) (WL,+110 0.. equals
0.f(wk,o) = O(E*-) bounded, and thus EIELs
is +te
Orf(wnno)
B (w-1-r)
The m ( )
Σ ar (wn.))) = VVLk. +e
Σ
JEL
Putting all the estimates together, we conclude that f(w++1.0) f( (w is smaller than -m( min (W [V/(ww)))l + O' - $2 (k
7 (f( + + The accumula- tion of O11)) is in order log 7 and grows slowly. To derive the convergence result, we need to show
DD: /Do
7

---

Under review as a conference paper at ICLR 2023
the first term dominates. However, the second term contains historical gradient information, which not necessarily smaller than the first term in absolute value. How to deal with it? We observe that while the first and the second terms are not comparable for single k, summing over leads to 1 [( is smaller than
mh min!
Vi(l VDD
II 1VS(ww,))l") /Du
T Σ 96
Σ
With a sum order change, one can easily observe that the last term equals to O k=1 v IV which is also O 1 mh min [ alll VD.
W + O due to the
VDo ( Thus the last term is dominated by the last to second term. This completes the proof for RMSProp.
mean value inequality v V (urx,o))) S O(n) + O
DL
Do
Remark 6 (Difficulty compared to L-smooth case). First of all, the change of Vn, is easier to bound without the historical gradient term. Secondly, under L-smooth condition, the error does not contain historical gradient information and is only in order of O(i)), which is easy to bound.
Remark 7 (Intuition why SGD converges slowly). If we replace Adam with SGD in the above analysis, the first order term may no longer dominates the second order term. This explains why SGD converges slowly. A detailed discussion can be found in Appendix B.
Stage I:: Extend the proof to general Adam. For Adam, the update norm is still bounded and the second order term can be bounded similarly. However, the analysis of the first order term becomes more challenging even though we still have MR s Ms.0- Specifically, even with constant Pk, Mk,0- -Mp <mx(E; +t f((kk,))) > 0 is not necessarily correct, the momentum mygi contains heavy historical signal, and may push the update away from the negative gradient direction. How to deal with this challenge?
We observe that the alignment of #1-110 4%.0 and f is required due to that our analysis
is based on the potential function f(w.ko). However, while this potential function is suitable for the analysis of RMSProp, it is longer appropriate for Adam based on the above discussion and we need to construct another potential function. Our construction of the potential function is based on the following observation: we revisit the update rule in Eq. (2) and rewrite it in the following manner:
M 81m VT.. (W.,)
31
Notice that the night-hand-stee of the above equation contains historical gradients but only the gradient of the current step! We then get 1/ /PK. into the play, leading to
0k
31 W..
Wh.1
B1
Wh.s+1 Wh., (1w... wh.1-1)
1 1- B1
1-B1
1- 33
meZi - 8.mmg.-11
+ V (w..)).
Va.0 + eld
1 1-3
Vi.a ella
One can see that the sequence (ug, we, epoch (with coordinate-wise but constant learning rate M*.i)! Further notice that UR = Wk, + 31 Mig.: Wik.: is close to Wk.i. Therefore, we choose our potential function as f(u,,)) The Taylor's expansion of f at u4o0 then provides a new descent lemma, i.e.,
are (approximately) doing SGD within one
1-
Lo Li [([Wo))))))
[(u41100) ((x < <(uR+1.0 uk,o, vf(uu,)))
|14+100
2
First Order
Second Order
By noticing Wk,i F3 Ugii R5 Ug.0, the first order term can be further approximated as follows, (u U0 vf(uu,))) -(
mi
Vf(Ww,o)) Vf(ww,o)),
VKko + eld
which is negative, and the challenge is addressed.
Remark 8. Zhang et al. (2022) also encounter the misalignment between Wk+1.0 WK. and
-V but they do not use the potential function and can only derive in-expectation convergence. A detailed discussion can be found in Appendix B.
Remark 9. There are similar potential functions in existing works for other optimizers, but none of them succeeds to derive the result for Adam. We defer detailed discussion to Appendix B.
8

---

Under review as a conference paper at ICLR 2023
4.3 SGD MAY CONVERGE ARBITRARILY SLOW WITH (Lu, (L1)-SMMOTH CONDITION
As the (Lo, L-mmmhoth condition appears to be a more precise characterization of the landscape of neural networks than L-smooth condition, one may wonder how SGD performs under such circumstance. Here, we find examples that satisfy (Lo, -smosho condition, but GD and SGD diverges. This implies that under this realistic smoothness assumption, (S)GD can be arbitrarily slow.
GD may converge arbitrarily slow with (Lo, 41 -smoohh condition. To begin with, we notice that Zhang et al. (2019a) have already provided counterexamples over which GD converges arbitrarily slowly. However, their examples use constant learning rate GD, which, unfortunately, does NOT match the setting of Theorem 1 (i.e., diminishing learning rate and stochastic update), and thus does not suffice to provide fair comparison between GD and (full-batch) Adam. To fill this gap in setting, we provide the following example:
Example 1. There exists a domain X' and target function f R. - E. such that for every initial learning rate Th, there exists a region & C. X with infinite measure, such that GD with diminishing learning rate T)+ = Vi
m and initialized in will drive f'(w:) and || (ww))) to infinity.
We defer a concrete construction of the example to Appendix C.1. We emphasize here that it is a classification problem with linear model, which shares similar properties with practical classification problems. The intuition of this example is that with a fixed initial learning rate, a bad initialization may lead to arbitrarily worse local smoothness due to globally unbounded smoothness, and make the first-step stepsize relatively large. This leads to even worse (larger) local smoothness at the next step. Also, the increase of the local smoothness can be rapid enough to offset the decrease in learning rate, and eventually drive the loss to divergence. On the contrary, the update norm of Adam is bounded regardless of the initialization, and thus Adam does not suffer from the same problem. One may notice that the divergence issue in the above example can be equivalently viewed as "given initialization, a large learning rate will bring divergence". A natural question is that whether reducing the learning rate will lead convergence. The answer could be yes, but it is true only if some additional assumption is provided (for example, Assumption 4 in (Zhang et al., 2019a), which assumes the gradient is bounded over a loss sub-level set). However, in this case, the feasible initial learning rate depends on the local smoothness over the trajectory. Since the initial gradient can be arbitrarily large, the initial learning rate needs to be arbitrarily small, which thus leads to a slow convergence rate if bad initialization is picked. This is exactly the intuition of the lower bound in (Zhang et al., 2019a). Please refer to a detailed discussion in Appendix B.
Similar negative results also apply to SGD. Actually, the situation is even worse: SGD still suffer from divergence for learning rate 1/L, which can lead to convergence for GD.
There exists a domain X. initial point wo X and target target function f Ei=o fo over which SGD with initial learning rate Mh = T. and diminishing learning rate tJ. = Mh, diverges while GD with the same setting converges. where is the smoothness upper bound of the loss sub-level set {w E X: f(w) S f(wo)).
Example 2.
vt
We defer the concrete construction to Appendix C.2. The intuition of this example is that even with learning rate 1/L., non-full-batch update can step out the loss sub-level set and increase the local smoothness coefficient. Similarly as before, keep keep reducing the learning rate might lead to convergence. But this only happens when additional assumptions is imposed. Even if so, the convergence rate could be arbitrarily slow.
5 CONCLUSION
In this paper, we take the first step to theoretically understand the adaptivity in Adam. Specifically, we prove that Adam can converge arbitrarily faster faster than SGD. Our assumption is realistic and close to practical settings. On the other hand, there is still a lot to explore for Adam's 's performance. For example, it is interesting to analyze how momentum helps in Adam's optimization. Further, it is interesting to investigate whether Adam can handle more sharp smooth conditions, e.g., smoothness bounded by a high order polynomial of the gradient norm.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2018.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu. Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration. arXiv preprint arXiv:2101.05771, 2021a.
Jacques Chen, Frederik Kunstner, and Mark Schmidt. Heavy-tailed noise does not explain the gap between sgd and adam on transformers. 2021b.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.06765 2018a.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: /808. 02941, 2018b.
Dami Choi, Christopher J Shallue, Zachary Nado. Jachoon Lee, Chris J Maddison, and George E Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint 2019.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. arXiv preprint arXiv:2208.1 //95, 2022.
Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration. arXiv preprint arXiv:1807.006766, 2018.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of adam and adagrad. arXiv e-prints, pp. arXiv-2003, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Timothy Dozat. Incorporating nesterov momentum into adam. 2016.
Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. arXiv preprint arXiv:2202.05779, 2022.
Sébastien Gadat and loana Gavra. Asymptotic study of stochastic adaptive algorithm in non-convex landscape. arXiv preprint arXiv:2012.05640, 2020.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pp- 310-315. IEEE, 2015.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1))267-305 2016.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint 1rXiv:21/2.03495 2021.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2023
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview mini-batoh batch gradient descent. Cited on, 14(8), 2012.
Feihu Huang, Junyi Li, and Heng Huang. Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 34:9074-9085, 2021.
Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLLT, pp. 4171- 4186, 2019.
Fereshte Khani and Percy Liang. Feature noise induces loss discrepancy across groups. In Interna- tional Conference on Machine Learning, pp. 5209-5219, PMLR, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 444266988, 2014.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance the adaptive learning rate and beyond. In International Confer- ence on Learning Representations, 2020a. URL https::///// /opp/revieeeeeeeeeeeeeeeeee net. formmidd= rkgz2aEKDz
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33, 2020b.
Ily Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.0100,, 2017.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 1902.0949, 2019.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: 092337 2019.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint 130. 63700 2013.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper- parameter. In International Conference Learning Representations, 2021.
Suvrit Sra. Advanced optimization: Lecture 18 proximal methods, monotone operators. https://www.cs.cmm..dd edu/ suwrivheacchleee118.dd. 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp.
2017.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and accelerated perceptron. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1195-1204. PMLR, 2019.
Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference on Machine Learning. pp. 10849-10858. PMLR, 2021.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9047-907, 2020.
11

---

Under review as a conference paper at ICLR 2023
Zeke Xie, Xinrui Wang, Huishuai Zhang, Issei Sato, and Masashi Sugiyama. Adaptive inertia: Disentangling the effects of adaptive learning rate and momentum. International Conference on PMLR, 2022.
Machine Learning, pp.
Xiaodong Yang, Huishuai Zhang, Wei Chen, and Yan Liu. Normalized/clipped sgd with per- turbation for differentially private non-convex optimization. arXiv e-prints, pp. arXiv-2206, 2022.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint 1at.::0088.88888 2017.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garmett (eds.), Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018a. URL https: //poce/eecoc//////////ee../ .nw.rrreeeeeninnn...........p..s cc/ 2owoeeee77771110000066666eeee http:///000./eee/000311111111///
Paper.per
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018b.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 13:15511-15521 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019a.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adam beats sgd for attention models. 2019b.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systemx, 33: 33:15383-15391 2020b.
Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems, 2022.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the conver- gence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 180.:018...0671, 2018a.
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Hoi, and Weinan. Towards theoretically understanding why sgd generalizes better than adam in deep learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pp. 21285-21296, 2020.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint 13 2018b.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2 //37,,
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
12

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL RELATED WORKS
In this section, we provide discussions on more related works.
New variants of Adam. Ever since Reddi et al. (2019) pointed out the non-convergence issue of Adam, many new variants of Adam are designed. For instance, Zou et al. (2019); Gadat & Gavra (2020); Chen et al. 8b; 2021a) replaced the constant hyperparameters by iterate-dependent ones e.g. B1 or 32.. AMSGrad (Reddi al., 2019) and AdaFom (Chen et al., 2018b) enforced { to be an non-decreasing. Similarly, AdaBound (Luo et al., 2019) imposed constraints 7t E [Ct, C.] to prevent the learning rate from vanishing or exploding. Similarly, Zhou et al. (2018b) adopted new estimate of Ut to correct the bias. In addition, there are attempts to combine Adam with Nesterov momentum (Dozat, 2016) well as warm-up techniques (Liu et al., 2020a). There also some works providing theoretical analysis on the variants of Adam. For instance, Zhou et al. (2018a) studied the convergence of AdaGrad and AMSGrad. Gadat & Gavra (2020) studied the asymptotic behavior of a subclass of adaptive gradient methods from landscape point of view. Their analysis applies to Adam-variants with 81 0 and 32 increasing along the iterates. In summary, all these works require L-smooth condition. Though the new variants of Adam can probably converge, the convergence rate is no better than SGD.
Generalization ability of Adaptive gradient methods. The generalization ability of Adam is hot debate topic. For instance, Wang et al. (2021) studied the implicit bias of adaptive optimization algorithms on homogeneous neural networks. They proved that the convergent direction of Adam and RMSProp is the same as SGD. Zhou et al. (2020); Xie et al. (2022); Zou et al. (2021) argue that Adam preferred sharp local-min while GD prefers the wide ones. As such, they argue that Adam generalizes worse than SGD. Zou et al. (2021) prove that Adam generalizes worse than SGD over a specific model. There are also several attempts to improve the generalization ability of Adam. For instance, Padam (Chen et al., 201 8a) introduced a partial adaptive parameter to improve the generalization performance. Adam W (Loshchilov & Hutter, 2017) improved regularization in Adam by decoupling the weight decay from the gradient-based update.
B ADDITIONAL DISCUSSIONS
B.1 RESTRICTION OF 31 IN THEOREM
We discuss a bit more on 31. First, The requirement 33 < B2 is standard condition in Adam-family literature (Reddi et al., 2018; Zou al., 2019; Défossez al., 2020; Shi et al., 2021). Since &g is suggested to be large, this condition covers flexible choice B1 E [o. 1). Second, although the dependency between 31 and (3 in Inequality (4) seems complicated, the effect of 31 on Inequality (4) can be omitted when adopting the practical value such as 31 0.9. This is because the term a1+8, " is way smaller than the term (n 1)" in the right-hand-side of Inequality (4). For example, 1-3;
1+:11 19. This number is much smaller than on real datasets (for instance, on CIFAR-10 (He et al., 2016), 50k/128 = 390; on ImageNet (You et al., 2017), a = 1.2m/ SSk = 150). As a result, constraint (4) is inactive for practical choice of B1.
when 31 = 0.9 (the default setting in deep learning libraries), I-
B.2 COMPARISONS OF OPTIMIZERS OVER THE -UNEIGU TASK
For the case where the gradient along the trajectory is small, (Lo, L, )-smooth condition will degener- to L-smooth condition, and thus SGD works well. This may explain the phenomenon that SGD is also adopted in some finetuning tasks, as pretraining can be viewed as selecting good initialization (and we can expect that the gradient is small along the trajectory). While the above discussion is highly intuitive, it is an interesting future work to formally prove it.
B.3 ON THE EFFECT OF MOMENTUM
Since Adam and RMSProp both converge under (Lo, L1) smooth condition, a natural question is what the effect of momentum is in Adam. However, this is highly non-trivial question. The effect
13

---

Under review as a conference paper at ICLR 2023
of momentum is not clear even for momentum SGD in non-convex optimization, let alone for Adam. We believe that this question is interesting yet beyond the scope of this paper and leave as a future work.
B.4 CONVERGENCE RESULT OF RMSPROP
As mentioned in Section 4.2, we provide the convergence result of RMSProp as a corollary of Theorem here.
Corollary 1. Let all the conditions in Theorem I hold. Then, for RMSProp, if
8(82) 2 @vdmax
32
1,85
1,
32
n
201 8.
vm
82 10-1- + 8n
P2
82
(9)
2(4+ V2)D
then, we have that
[V [V))))) VD
log T VT
min RE[LT]
O(VDD min ((8))
(10)
DD
Since Adam and RMSProp both converge under (Lo, -m)osh condition, a natural question is what the effect of momentum is in Adam. However, this highly non-trivial question. Theoretically, the effect momentum is not clear even for momentum SGD in non-convex optimization, let alone for Adam. Practically, there are existing experiments suggesting that the performance of well-tuned RMSProp can match that of well-tuned Adam (Choi et al., 2019), We believe that this question is interesting but beyond the scope of this paper and leave future work.
B.5 ADVANTAGE OF ADAM OVER THE GD/SGD WITH GRADIENT CLIPPING
(Zhang et al., 2019a) shows that GD/SGD with gradient clipping converges under (Zo, L1) smooth condition. A natural question is that what is the benefit of Adam over GD/SGD with gradient clipping. Honestly, we are not able to answer this question yet, but one potential advantage may be that Adam can handle more complex noise. It is not known whether SGD with gradient clipping can converge in our setting, as the existing analyses of GD/SGD with gradient clipping under (Lu, L1 -mmoohh condition all assume that the distance between stochastic gradient and true gradient are bounded with probability 1 ([Zhang et al., 2019] and [Zhang al. 2020J), which is strictly stronger than affine variance noise assumption. It will be interesting to either provide counterexample that SGD with clipping does not converge under (Lo, L1 s-smohhh condition with affine noise assumption, or prove that SGD with clipping does converge and find other perspective to demonstrate the advantage of Adam over SGD with clipping.
B.6 INTUITION WHY ADAM CONVERGES FASTER THAN SGD
We first illustrate this from the proof. If we analyze SGD following the same methodology of Section
4.2 for SGD, the first order term in Eq. (6) for SGD is (-7k Σi= (wk.s), fr,, (ww,)) so
(-1k Σr= fir., (w).,)) V fT (wx,o)) = 7 || f (wl, However, when it comes to bound the second order term, we will encounter two problems. First, it is not known whether the update of SGD is bounded, and thus whether we can bound Lioe using (Lo, L,) -smoohh condition. Second, even if succeed to bound Lioe by O(I [[]VV[(w,. I) + O(1), the second order term has the form On V f(w,,) 113) O f Il?). and may be larger than the first order term when the gradient is large. We invite the readers to see the counterexample in Section 4.3 to learn more.
We then provide example. When the local smoothness constant coefficientL varies drastically in the domain, it is difficult to decide a pre-decide stepsize that guarantees to work along SGD trajectories. There are two cases:
When entering a sharp local region, the pre-determined steps might be too large and cause divergence of SGD. 2. When entering flat region, the pre-determined steps might be too small to
14

---

Under review as a conference paper at ICLR 2023
make progress. It will cause slow convergence of SGD. Situation gets worse when using diminishing steps.
For Adam, the effective stepsize involves +Mss+eta which is adaptive changing along the trajectory. Adam can better handle the above two cases: 1. When entering the sharp local region, the gradient usually large and yos,tell, will gradually decrease in this region. Finally it will reach small enough 1
stepsize to slip into the sharp region. 2. When entering the flat region, the gradient is consistently small and thus voaitela will gradually increase, leading larger stepsize and thus Adam will converge faster.
B.7 DISCUSSION ON THE POTENTIAL. FUNCTION
We notice that similar potential functions have already been applied in the analysis of other momentum-ben based optimizers, c.g., momentum (S)GD in (Ghadimi et al., 2015) and (Liu et al., 2020b) and Adam-type optimizers (except Adam) in (Chen et al., 2018b). However, extending the proof to Adam is difficulty lies in showing that the first order expansion of ff (uu,,) is positive, which further requires that the adaptive learning rate does not change much within one epoch. This is hard for Adam as the adaptive learning rate of Adam proof even challenging due to the unbounded error brought by gradient norms.
and fails to provide a convergence result for Adam. The key
be nonmonotonie. The lack of L-smooth condition makes the
B.8 DISCUSSION ON THE IN-EXPECTATION RESULT IN (ZIIANG ET AL., 2022)
Zhang al. (2022) handle the misalignment between # 47,0 and V f(wg,o) by additionally assuming that the random permutation to generate {Fk.o. ... T } is uniformly sampled from all possible permutation orders. Based on this additional assumption, the expectation of the momentum can be shown close to the gradient and thus they derive an in-expectation result. In contrast, we do not need such an assumption. Further, their proof is more complex than ours as they need to deal with the historical gradient signal in the momentum. Our potential function allows to offer trajectory-wii convergence result with simplified proof.
B.9 INSIGHT FOR PRACTITIONERS
First, Adam receives great popularity among practitioners (with more than 100k citations). It is important to theoretically understand this current algorithm.
Second, provide new suggestions for practitioners: When running experiments tasks such as Transformers and LSTM training, we suggest using Adam instead of SGD. Though this is a folk result based on engineering experience. It firstly theoretically justified. Third, we provide suggestions for hyperparameter tuning (based on the convergence conditions in Theorem 1): when running Adam, suggest tune up beta2 and try different 31 < /B2. This suggestion would save much effort of grid- rrid-searching the ($1, B2) combination.
C DIVERGING EXAMPLE FOR (S)GD
In this section, we discuss the divergence issue for (S)GD under the (Lo, L-)-smooth condition. This section is organized as follows: we will first consider the simple full-batch case, i.e., 1 and f(w) = fo(w) (therefore there is no random reshuffling and no randomness in the process of training). in which case will show GD may suffer from divergence under the (Lo, L1) assumption while Adam converges to the stationary point, We then step further to the random reshuffling case and show that the randomness may brought additional divergence issues.
C.I COMPARE GD AND FULL- FULL-BATCH ADAM
To start with, we notice there is an example in Zhang et al. (2019a) over which GD will converge arbitrarily slow. We re-state their result as follows:
Property (Theorem 4, Zhang et al. (2019a)). For every fixed learning rate 17 E and tolerate error bound E R+, there exists a domain X, optimization problem f X R. and
15

---

Under review as a conference paper at ICLR 2023
initialization point w1 X satisfying f is lower with (Lo, L1) smoothness and satisfying M - suplll (w))ll Il w such that f(w) I f(wo)} < ca, such that GD over f starting from w1 with constant learning rate such that any t Zt smaller than M(((w))) ( f(w))5e/8) satisfies [I=]( e.
Beo M+11
By Property 1, know that the convergence of GD can be arbitrarily slow depending on the gradient upper bound M of the loss sub-level set {w f(w) S f(wi)}, which further depends on the initialization. In other words, the performance of GD sensitively relies the initialization.
However, Property does not suffice to show Adam performs better than GD, as in Property the learning is constant while in Theorem 1, it is decaying. To fill this gap in setting, provide the following example satisfying Assumptions 2 and 1, on which GD with decaying learning rate diverges if initialized badly.
Example 3 (Example 1, restated). Let n and p 2 with fol(w' w²)) -
- 22 1/2
Fu' b and f((w" , fo((w", w²)). Then, satisfies Assumptions I and 2. However, for every initial learning rate th. there exists a region & with infinite measure over IR²2 such that, with and start point in E, and f diverge infinity.
GD with decaying learming rate Th vE
Proof. Notations. To simplify the notation, we define #1 -2 2) and x2 (- (3 2) It can be observed that ||: ||
|| and ( 22)
We also denote the parameter given by the
k-th iteration of GD as wy. By definition, we have
(e) wkk I1 + ThE (el,we)
W
wk + The
We further define g(z) _ mes 17x 1 1. As g(x) + 00 as I + co, there exists a large
enough positive constant C' >> 1, such that for every C.g(z) > O.
Verify the assumptions. Assumption immediately follows as n = 1. We then check Assumption 1. We have
V Vi(nn) - (10,01)) m11 (2) 22, V2 f(w) a are (w.m))) + 222 x22 (w,
Therefore,
2 fo S (mnai) m2) while
1 (watt)) ) + 76 -e-(w.))) (w.w2) [V](w)]| (w0,))) - (w, 22 (0, 1)) 2
1
2
As conclusion, Assumption is satisfied with L, = 0 and L1 2.
Initialization. We define region as
3 é {a + +b, > C,a > b, U {arz + b, a) > C.a > 16]b,
It should be noticed that & has infinite measure.
Iteration. As {a + bo : ai > C,ai 16 ||} is symmetric with 22g bi : ai > C, a1 > 16 b1 ||. we analyze the case when wi is in the former set without loss of generality, i.e., wi 01 b1 with 0₃ and a₁ b6]|bi
We will prove by induction that Ak 2 1. wt = ag + bR. where in equals to 1 if k is odd and 2 if is even. ag and by satisfies ag 2 1 and a 2 17.-IC.
For A 1, the proof directly follows by the initialization. For k * suppose that the above property holds for all the iterations before the k-th iteration. Suppose is even. Then,
Wh-1 = ak-101 b
which leads to
17
[kk 1|1 ax + |
0k-1
16
15
(wk-1,
20-11 | >
4k-1s
16
16

---

Under review as a conference paper at ICLR 2023
and
1 12) S ax--
7
1 --
16 k
Consequently,
Wk Ww--1 -1--1e (2) ((::))))) x0 7/ -1 (02, (02,
-1
(022 1) 02 + wk-1 + 7 1 (00 1) x1
The norm of 1 + ak- -k- (m 21 can be bounded
17 S [ + 1 (mians 5
| Ths-16" (mi 1)
dk-1 + 1]k- 10
while the coefficient of 22 can be lower bounded as
Uk 16 102. (02. 17k-16 ak-1 2 memer - llog--1 11 1-- 2 m
Therefore,
T (12,1-(02, (02, 2g(0)-1).
16/| 77-11 10 (0) 12 x1ll mesar- 17ax + 16m Har-1
As by the induction condition 0x-1 and by |m= Tß 1e (21, xn completes the proof for k.
17* C, we have that g(a=-()) 0. Therefore, choosing
ag f/K-16 (0e-1e-(22:000 (222
The proof of the case that & is odd follows the same routine by simply exchanging æ and 22 in the above proof.
Consequently, for [V(w))) |]. we have that when & is even
[V 2 | [
(es,ee))) - ||02e (w)) 2 e -
11 ac _ co.
Similar claim holds for the case k is odd. We then complete the proof that [ ) 20. The claim that f(wx) oo k oo can derived following the same routine.
+ oo as
The proof is completed.
On the other hand, as f in Example satisfics Assumption and Assumption 2 (with Do 0), Theorem 1 applies and full batch Adam will converge to stationary point regardless of the initialization. Example indicates that even for the full-batch case, Adam appears to less sensitive the initialization compared with GD under (Lo, Li)-mmooth condition.
However, under the same setting and fixing the initialization point, tuning down the initial learning rate ?n may help GD converge. Specifically, when gradient norm of the loss sub-level set (w f(w) < f(w))} is upper bounded, if we choose the learning rate to be sufficiently small (for example, smaller than 2/ + M) where M is the gradient norm upper bound of the loss sub-level set), we can make the loss keeps decreasing as GD iterates, and the parameter stays in the loss sub-level set. However, such learning rate can be rather small when M large and leads to slow convergence of GD, which is exactly the intuition behind Property 1.
Furthermore, when and SGD adopted, tuning down the learning rate may not help any more. We will discuss such an issue in the following section.
C.2 COMPARE SGD AND ADAM
First of all, Example can be simply extended provide divergent example for SGD.
22oLo + J, M) serves the largest reasonable setting of the learning rate for GD, over the loss
sub-level has smoothness upper bound (Lo + M)
17

---

Under review as a conference paper at ICLR 2023
Example 4 (Example 1, restated). Let n and p 2 with Sol(w², w²)) e 2--ful -
fi (x) = Fu - t and f((w', = fol(w', , Then, satisfies Assumptions and (with Da = 0). However, for every initial learning rale 7h, there exists a region & with infinite measure over TR2 such that, with SGD with decaying learning rate Ui v
and start point in E, and V
diverge to infinity.
The proof follows the similar routine as Example and we omit here. Note as Do = in this case, Adam still converges the stationary point.
On the other hand, as discussed in the previous section, for SGD over (Lo, Lm)-mootth condition, a small learning rate may no longer help and SGD will still diverge. We illustrate this idea by consider the following example.
Example (Diverging Example for SGD with Small Learning Rate), Specifically, we rescale the æ and 22 in Example 3 as 1 1 and ã² 50x2. We choose initialization point w 31 and choose learning rale as = 1/ L with decaying learning rate ne
mn where is defined as the Vt
smoothness upper bound of the loss sub-level set, i.e.
arg max (1 f(w)ll2 f(w) S f(w))}
By the definition of the previous section, GD on such example will converge to the stationary point, as the iterates will stay in the sub-level set, the smoothness will be small, and the loss will decrease. However, run SGD this example and find that the loss and gradient norm will explode in three steps (Figure 3).
2.
(a) Training Loss
(b) Gradient Norm
Figure 3: Example on which SGD with decaying learning rate and small initial learning rate diverges. We only plot the first two steps because the values exceed the math range in python in the third step.
The intuition behind Example 5 is that the update caleulate from a batch in SGD does essentially reduce the loss and may no longer keeps the iterates stay in the loss sub-level set. This can eventually make the loss diverging, or keep the parameter away from the saddle point in the training of neural networks.
D PROOF OF THEOREM
This appendix provides the formal proof of Theorem 1. Specifically, we will first make some preparations by O showing notations and @ proving lemmas which characterize several basic properties of the Adam optimizer, and then prove Theorem I based on the lemmas.
Remark 10. In the remaining proof of this paper, assume without the loss of generality that vn is small enough, such that the following requirements are fulfilled (with notations explained latter):
202 S S. This will latter ensure that can directly apply the definition of (Lo, Li)- smooth condition (Assumption 1) to parameter sequence {u0k,)kks
18

---

Under review as a conference paper at ICLR 2023
VDiCuu-- This will latter ensure the second-order term is smaller than the first-order term at the end of the proof.
4(2/2+1)
The proof can be easily extended to general cases (while certainly more cumbersome) by selecting large enough K and using the epoch K as new start point and derive the results after epoch K (this is due to Ti is decaying, and K is finite, the epochs before epoch can be uniformly bounded and we then derive the desired result for all epochs).
Without the loss of generality, we also take the following initialization: W1,0 = WD. m1,-1
I (wn) (Ti.-1 can be any integer in [0, n 1)), and V1,1.-1 = max; max;{Off { (wo))) Vl (here the maximum is taken component-oe wiieel)). We take the initialization to have a more concise proof. while the proof can be easily extended to all the initialization as the information of the initialization the exponentially decayed average of Adam (both in ma, and Vk.a) decays rapidly with l increasing.
D.1 PRELIMINARIES
D.1.1 NOTATIONS
Here we provide a complete list of notations used in the appendix for a clear reference.
We use (k1, < (<) 12) for Vki, hi2 e N+ and i, E (.,.... ,n 1}. if either
k < l2 or h = k2 and i S (<)12
We define function g(x) [0. 1] + R/- as
88
g(32) -
max
00-1
VB,
1
(1- (1 - 32) 2n
1
82 + 8n
We define constants {C)) 10 follows:
81)²
C 2
88 +1,
1 B2
1/2
C2 2 nC + 1-
81
C1 (1 vT)
C2 2
+2V2(L + L1 Do)
VT-
v
+ 8/22L
1- vB2 1
vB2
1- 84
---
C D1
V3
Co A 4 D1)
C4
dC4vDD
1- V
Co 2 dCss + 1-
CiRyD,
2
1/1
Cr _ 3n
C. 1- /
dC,
(nto LIVAVDD) n² n²Vdoin
C.C.nND (d0s
1 V3T
2na
La DiVDinyTe dg({t)
(n-1+ 1+91
V2n 1.CiVD
[+ 1-
(n VdCiViddmciaee +2 11mm
31
JaCI.
1- 31
B
2nn
d(n
Da)C +((b))
RR-1- 1+9 91
2v28,
Ci I L Dojavani
T- A
3
T- 31
C1o 3dg((22)
n- (n-1+
1 Bi
VZn
LIVID
1
n
(nto + Ia LIvRT
avaCin + Co.
B
On A (
C2)Cs Cs
2 C2 + Oo++ nlo + Li V 3c
Ga
Caa 2 1
- +C, + Cio+
nho In lnyay Do 30
19

---

Under review as a conference paper at ICLR 2023
D.1.2
AUXILIARY LEMMAS
Here we provide auxiliary lemmas describing basic properties of Adam and the descent lemma under (Lo, -smoohh condition.
Smoothness of f
Lemma With Assumptions and satisfies (nLo - L1 LIVTVDo L1 LITTDii condition.
Proof. Ven, u2
Rd satisfying [w w2ll S fn"
n-1
[V](w:)- - (f(W2)]
Σ
[V vi((w2))1
Σ
(Lo L.IVV(( [))[[ w2
x=
k=
$ nlo + LIvn
Σ
[
||w - w2ll
S(nLa LI LIVTV Do Dí /V [;)]] w2ll
<(nTa + TIv + (mm ((m)))) well
<(nTa + LAyTy + I (/ w2ll
The proof is completed.
Basic Properties of Adam
The following lemma characterizes the update norm of Adam.
Lemma 3 (Bounded Update). If 11 < Vz, we have Vk E N+, E (0. .n 1}.
Vikki + St,,
where
9 A (1- 81 (1-3))2
28 + 1.
1 - 32
1
Furthermore, have (1i,kii11 w.... S Ci and thus [|ark wk.ill S Cin. vd.
20

---

Under review as a conference paper at ICLR 2023
Proof. By the definition of ma,i, we have
(mi,ks)²
(1- (1) Σ
( a(l-1)nnti ((A (1k-1)+t5) (1 Oifre. (wkss)
j=0
+ +1 (1- - 31) Σ
( 101-))m- - O15mm. (20m)) + 31 ((k-1)1--) 1)-++++ (
m= 1=0
<
(1- B1)
81
(k 1)ntt ((k- ((==))++
1 1erS (wo..))
j=0
2
(1 B1)
( OrsTm. (Wma)l + g(t-1)ntit
max (w.s((wpp)) *E (m(r
1=0
(k- 1m (1--))-- 10:5T.. )
(1 - B2)
1=0
-1- 82)
10r5 (wmm))? 38h 111-1)++++1 max (w1,0)
sE(m)
m== 1=0
(1 - B1)²
(A- 1)n+t
87
8
(k- +11
+
1 - 32
B2
32
0
(1 B1)
(k- Dj++i
87
89
(k-1)n+i+1
Σ
+
VIKK
1 B2
82
32
j=0
(1 31)²
+1
Vi,k, = Civiks.
1 - 32
1
where Eq. (+) is due to the Cauchy-Schwartz's s Inequality, and Eq. (+) is due to the definition of
V1,1-1- We complete the proof of the first claim. The second claim then follows directly from the update rule
WLkki+1 WILKi
TJK
VLL.A +
+E
The proof is completed.
Based on Lemma 3, we then provide estimations for the norms the momentum and the adaptor.
Lemma 4 (Estimation of the norm of the momentum). We have for all l [d], k E Zt E [n].
2/281
)'(( |m.. max ( +
C. (. + L, / D me | fww,,))
n I- 31
+ +L.C D
- g V
Similarly, E [d] k E Z+ ft1},
Cim--eVdL ( 2v2(Lo + LiVDo) ViVan
|mj,-11n-1| < max Z
0r fv (wx,o)l+
Σ
Σ
3 1
1- 31
1=1 1=
21

---

Under review as a conference paper at ICLR 2023
Proof. To begin with, for any E [k 1] and any E [0, n 11. we have the following estimation for f. ((
Orfi(Werttil (+)
n-11
- @rfi(Wxx,0)+ +
(if((wk-(.p) - -.f(( +
(rrf(wx-np)) - - (wk.((w-r..p)
< <(0rf((uaoo1+
(Lo L1 V| ( - wh-rp+1l
p=j
(Lo L Vi (10) - wk-r.ptill
n-1
t- t-n--
< 2(0
+
(Lo + 41 +0 Σ
ΣΣ
(Lo L1
p=j
p=0
Σ
La Li
| Se (wx- Cin-
p=j
PE(m
Lo L1 Lı
Σ PE(N]
(f
Cin--ivd
S {(0rs((WE))+++
Tio ( In Ln Cim-
ΣΣ
Lo + LI \ Cink-rVd
()) +
Σ
ΣΣ
D=1
p=
+2(Lo + LIV (mn
<10.5((WE.o)1+ +
Σ L -
La DD
+2V2(Lo + LI Do) j).
where Inequality (+) is due to (Lu, L1) smooth condition, and Inequality (+) due to Va, b N+ a > b, Ei -o= < 2
Similarly, we have that for any [0, n 1].
[0.f(wwk)) & (0rf((w.o))
aa - -rf( Σ
p=
<( +
Lo + fl
Cinvvd
5-1
=10,f( +
Li L La
p=
22

---

Under review as a conference paper at ICLR 2023
Therefore, the norm of mi,k, can be bounded as
mi.kil
8 (k- 1)-t1in+----0 (1-- 1or ( (1 (1-1)) (
5(1 (1) Σ
81 1
-100 Fn- (wk-t.))
1=0
(=1
+ 1/4 1+n-i++11110
10 (w)
k- 1 n-1 Σ
5(1 - 31)
(k- 1n--l)+t-(i (1- (wx,o))
+ +1 (1-
31
g 3 1n (wk.o))
1=0
t= ==
(k- 111 18.s (20koo)
+ -11 B1) Σ
8(t 1)n+ ())-)ii((e-)))))))
Σ
C (Lo LI Do)
5=0
k-1n-1
+ (1 31)
3 gittijj
Σ C
1=0
- 1/0
L L/ + LLV 1)n
P=U
2/231 n 1- 31
max 18 [0.s( iE(m]
VLCi + LA v DOYma L,Ci DiTE
V J (wxk,))l
k-
L.CV D
f V (Wx
where Inequality (+) is due to a exchange in the sum order.
Following the same routine, we have
<(1 1
fmn-1-110 1-1
100
10 (Wk-rs)) g 1((--1)1ars (
(=1
k-
<(1 - B1)
gtm-1-j 110 (wx,o)) +
(k-1)m 10
[=l 1=0
k-In-1
+ +(1 81)
ghn
Σ L L.D ΣΣ L D
1=0
+ 2V2(LL + L1 D1))iVddmiaaa -))
R- n-
+ 1))
ΣΣ
L Di
+ In Do) 1)m
0
< max (0.fi(wk..)) + sE|n|
1=
2v2(Ln + DiVDo Vdn
1- 31
23

---

Under review as a conference paper at ICLR 2023
The proof is completed.
Lemma (Estimation the norm of the adaptor). We have for all I [d], k E Zt,
1- 1- Σ |LL,,ol 28
1 32
Orfilun,o) -
1rfi(eux.0))
(82mTT C₁ Lo
(1 13/2 32
1 1- 122 iE(n)
iEin]
+ C1, 1 - $2 v1 -/
P2
vB2
Σ
32
12
1--1)m
n
1
VillVf(uxx + vDo
1=1
5=0
and
22 max @rJi(uk;,)) + 22(2VnR ( + 11 v Do)
/1 B2 vB2
sE|n]
3/2
v
LI
D1
7j
-I- 82
Σ
32
[1-1)n
B2
1=0
Proof.
By the definition of v1,.0, we have
K1,00
k-1n-1
=(1 - f22)0 (20k,)
(00 + ΣΣ
(1 B2)
stm
+ //4 1)++1)++1__ max 0m1 <E(u)
k-1
2(1 (11-B2)0rmn... (wk.o)* 22
ΣΣ (1 B in (wk-e,))
+ 1/2 10++1 0
n
k-1
=(1 - 11-3))0r-2..mm (2),0)) +
ΣΣ -2) (0.r (wn.o) + (w)-s)), - aif (10,0))
+ 0 1)4-1))+11 1 Σ
(0 + a.S((wo)) - (w
2(1- - 2(1-32)0r5 12)
Σ (1- 3.)
1=1 5=0
1/ 1)0+1
1)041 1 Σ 0
k-1n-1
ΣΣ (1 - B2) (1 Orfru-ss (wk-ts)
8 11-1)++1 1
n
3
1)x
g 1)++1 110+1
82
(1- 32)
a.f(ww)))
37
n
1-1-1
Σ (1 - 32) (0rfm i. (wo.o))
ΣΣ
WWWNI//ffw...........4443/1 + + LLVDo)C (ono)i/vdny ddnatn
A-In-1
80 (4-11)0 1)041 1 Σ (0f((
ΣI SW ( 1)n
p=
24

---

Under review as a conference paper at ICLR 2023
28
1 82
Σ w.r.)
32 LE[m]
k-1n-1
ΣΣ (1 32) f
ΣΣ LAv / + I. Co 1ocCCiadyp dnitn
k-In-1
8 Mk 11
Σ>
L 1. L.VD 1)m
p=
28
32
Σ
d.
8V2
1 A2
Σ
@if((wwoo)
32 iE[n]
32)2
:E(m)
4L,C
82
@irf(wwaull
1-11
Σ
M
(
82 iEfm)
1 82
1 B2
288
8//2T/ Lo
(rfi(wkoo)
(1
iE(m)
8E (m)
-
1 1
82
le (wx.))
Σ
B2 M/-- Σ
(VDi / ([ + VD)
3
28
82
Σ
8v 2nna
1- B2
32 =E[m]
(1 y2
aE(m)
-1
82
k-1
Σ
3 T
VVDilV VDu)
1
32
kE(m)
1=0
2,8
1 82
Σ
d. (.w.,))))) 8N 2mme Ci
1 B2
35
(u
3
(1
iE(m)
-LL.C1
1 1 32
VI B2
Σ
(8.f((w).))))
Σ
33 / B2
Σ
+ vDo)
1
33
/32
1=0
The first claim is proved.
25

---

Under review as a conference paper at ICLR 2023
As for the upper bound, we have V1,k,0
k=1m-1
=(1 B2)0 nw. (Wa,o)
ΣΣ
(1 1000))00-00000 1, (wn-ts)
1=1 J
1/20 - 1)++1 max iE
52(1 - 52(1-3a)0)f-p o (w..)) +2 >E (1 10) (w0.
+ +200 -2ph--1mmt 13m+1
max Se (wUL,))))) iE(m]
Σ (1 12) ==
Li 1 (m
k-in-1
2 112++
11++1
11 M 1)n
r=1p=0
22 max O.fi(wu,o)) +2 i6(n)
-1- B2
1=0
Li Li /L + Lo)
k-in-1
B2
(K 1)n+1
ΣΣ LVDD / + + LaVDo) 1)ml)
vT
332
2 max (( 1E(m]
+2 2v 2n2 + LIVDo)
1 1
VB2
-I 32 n-1
L. Di
!
Σ
B2
[[[(w=155]|
1- V32 1=0
vI 32 332
max (2k,))) FE(m)
+2
2v 22 C2 + LIVDo)
3 - BB2
-1
/32 (1-10
LCVVD
7h-1
12
j=0
The proof is completed.
L
We then immediately have the following corollary when maxie(n) (0.f( is large enough. Corollary 2 (Lemma 1, formal). If
VI 3r max (w,, 24L, C *E[n]
B2
(r 1)m
nh
D V (w) (W DD)
1 VB2
1=0
32
2222m + L1
Do)
+ 8y 2nT Oj Lo
F2
VB2
1-37 B
V f (wx,))l) )
Ci nn(L (n(Lo +n(LobLVVD + Di
(II)
then
83 1
Σ
a < V1,k0 S 4 max (.
2 VE(n)
iEjn)
26

---

Under review as a conference paper at ICLR 2023
Furthermore, Eq. (1I) holds, we have Vi {0,-.. , ,n-1} 1}.
p0-1 + 8n 1- -1111
1 VIK.UU V1,Ki
Vi,KU.
5g
and
1- (1- (2)
2n 33
VI,k.0 S V1,k- S
VL,.D.-
52
82
Proof.
The first claim is derived by directly applying the range of max4e(1) ( into Lemma
As for the second claim, have
VL, f3,,,,0 + (1 (1- (2) (wk,;) 4... 11....1--011111 (1111))
On the other hand, since Vj E (0,... -
[0.f( S max 1.fp((wkpp)) (Wk + Ci j(Lo +(Lo+LiV +LVD
(wkkp))
pē(n)
V ((W )
max (2x nnLa LIV Lo) + LIVD D pE(n]
Σ
have
87 11000 E Mt,
28/M1,00 + 2(1 - 92) max (..b(ww,))) +
(( 1
pE[m)
+ +2(11 -Ba)(1 + 3 n2c
n(Lo LIVDo) + LIVDi
=82,,,0 + 1-21--3) B1) max max (1 2(1 S n([oo + LIVDo)
LIVDI
Σ
V V (wn)))l)
pE[m]
p=0
Therefore, if Eq. (11) holds, we then have
PLKK S.,,,000 + 4(1 - (3) max Or (wR,))
pE[n)
< L..LL + +4 (1- 82) Σ
@ifp(wk.u) 2 (85 (8 8n
1 1-3
Vi.kO
B
PE|n]
1 B1
< 3 1 + 8n
V1,k00
87
Following the same routine, we have
32 S 11,000
and if Eq. (11) holds,
Vi,k-
(VIn.O 10:00011110 (1-
82
Vi,K,0 - -(1 (1-B2) max Sr (1
32
1- -12)
2n
24,,00 Bg
3
The proof of the second claim is completed.
27

---

Under review as a conference paper at ICLR 2023
Remark 11. For brevity, denote
C3 e C. (m(lo LoV +222(L0 LI Do)
v1 B2 vB2
8v 2nLg
v 1 v
33
VI 32
C. 4LACIV D1
332
The right-hand-size of Eq. (II) is smaller than
max (0.f:( Cam + C4
Σ B2
(r-
Me
|V fww--n))
2E(m)
k-1
Can
B2
(1-1)m 1)m
- + 7cCs
Σ V f(wwa)))
(12)
Furthermore, we define ((32) as
32
((3)) A max
1,1
V B2,
V "
82
8n
8T
B
(1
(1
B2))
2n
13g
and the conclusion of Corollary 2 can be translated into that if Eq. (12) holds.
1
1
S {3(32)
Vur
/
and
1
S {
v VLL
VL,k.0
In the end of this section, we draw the connection of the gradients across the epoch. Lemma 6. vk E N+ i {0, (0,........ 1}.
[V < (1 + W
(nIo - LIVnnDD Do) nvdcimn.
Proof. By Assumption 1, we have
([(wx;))
Vf(ww,))l
nLo + L, D
V f1
|| wvooll
iml
nLo + L1
v (u
iddCin
n
Vf(
nLo + L vn,
(ww.))))
ivaC
V (nLu Lıvn D LvVn/Do) indCin
<(1 + b + (nLo + Liva Do) nvdcim.
The proof is completed.
Descent Lemma Under (Lo, -smoohhh condition We need a descent lemma assumiin (Ln, L1)- smooth condition similar as the case assuming To smoothness. Specifically, for function h X IR.
28

---

Under review as a conference paper at ICLR 2023
satisfying L-smooth condition and two points and v in the domain X, by Taylor's expansion, have
L 1/ - -112.
h(w) - h(w) + (Vh(v), w v)
This is called "Descent Lemma" by existing literature Sra (2014), as it guarantees that the loss decreases with proper parameter update. Parallel to the above inequality, we have the following Descent Lemma under (Lu, L1) smoothness.
Lemma 7. Assume that function X' IR satisfies (Lo, L1)-smotth condition, i.e., Vw, X satisfying I - v11 S LT
[Vh(w) Vh(v)]l & (Lu V 2/11-
Then, for any three points u, w, v E satisfying || - ull - + and || - ull S L. Then,
1 22 [ - ul + 1|w - =lIi w v/|- h(w) & h(w) + (Vh(u), w v) +
Proof. By the Fundamental theorem of calculus, we have
h(w) =h(w)= [ (Vi(v a(w v)), v)da
=M(b) (Vh(u); u - -0) +)}
(Vh(v + a(w -)) v)) Vh(u), w - v)da
<M(D) (Vh(u), w - uv) +
[Vh(u aaw - 0) vh(u)]llw vv|da
(1(v) - (Vh(u), u) +
(Lo L V/(l a(w v) - -ull|w vl|da
<h(v) (V)(u), 0) +
(Lo [.]l[ a) u| + allw ull) 1/ vl|da
<h(D) Vhh(u), w - v) + 2
Lo + L, [Vb())))(( ull + |/ w|I) w
vll.
where Inequality (+) is due to
1
a + a(w v) ull [[1 a) u) + a(w u)ll s (1 -a]l ull + a w ull s L1
and thus the definition of (Lo, L1) -smooth condition can be applied.
The proof is completed.
D.2 PROOF OF ADAM'S CONVERGENCE
Proof of Theorem 1. We define us
wh.0 9lmn. -1
(with W1,-1 W1,0 wp), and let W1 be
the i-th component of ug. Yk N+, E [d]. Then, by Lemma 3, we immediately have VI e [d]. Juik Wi,koo is bounded
WL.K. BIWiiKk-1 Wi.K0
|ui
Wi.b
1 1- 31
31
31 C1T
|wi,k,0 wiik-
(13)
1
B1
1- 31
Vk
/231
1
V232
Cim
<
Cim C2Tl.
(14)
31
Vk
1-
On
29

---

Under review as a conference paper at ICLR 2023
and
U1,4+1 [1,k
W1, 31 110011111--
WI.k. B1
1- B1
1
31
81
31
(wi,++1.0 - w1.K00) +
(11,++100 wIA+1,-1)
(Wi,k. - wi,k--1
1
31
1
- B1
B1
< (wr,++10 - w1,,,0) +
(10,++10
wIA+1,-1)
(Wi,.0 wi,k,11)
31
1 B1
+ B1
1
v2
1
SnCin 11 Vk 1 - 31
Cim
+
-C2m
C2TR
(15)
vk
VT
where C2 is defined as C2 - nC1 +
B 1-3
C1 (1 + v2).
We then analyze the change of the Lyapunov function f f(ux) along the iterations. Specifically, by Lemma 7, we have
f(Ux+1)
nLo + L1 Eieini
V V
<f(us) + (Vf(wk,o)) us+1 - us) +
(112kk00 uxll + |lwk,o - ux+1ll) 22
2
nLo + L1 Eie(n]
[V
<f(ux) + V f(wx,o), uk+1 ux)
3C
nLa + I1 LL
Eie(n)
<f(us) + V f(wwwo) ux+1 Us}
302dnj
2
nTa + I LIvn
Do + D1 (
<f(ux) + V f(w..)) u8+1 us) +
3n?
2
nLo + LIvn(v Do Vf 3C
<f(ue) + (V us+1 ux)
2 f(us)= + Σ 0rf(we.o)(uLRHH) wik) +
Σ
O.f ([Wxho) - u1,)) u1,
IELturge
IEL small
nLoo + In LLViVD 3C2 +
3L, V Di C2
| [V
2
Here Eq. (+), Ltarge and Lamall are respectively defined as
k Large = {1: : E [.]. Eq, (12) holds), L = (1: 1 [d], Eq. (12) doesn't hold).
Apparently, Liarge T.small [d]. We then tackle Eiet, ( u1.e) and EiEL: 0 ( u.,x) respectively.
@Analysis for EiELk D. - un,)) By directly applying the range of max4e(m) (i:f(uwk,o)), we have
1
Σ au((w).)(uLL111 war
n
RELE
<dCank
4-1 Csmi +C4 Σ
132
1]- 1jm
m
n-
V Vwn (o))-)))l +Csn Σ VBz
k-1 (--
m McCs
Σ V (wxx,)))
))
D
30

---

Under review as a conference paper at ICLR 2023
Summing over k from to f then leads to
0rf(wa..)(au).tt1 mlk)
n
RE
dC2Cami dC2Cs)
E
7
17
R-1
32
1)- 1)a
7--7
n-
| [V C2C4n
T
k-1
32
Th-
C2C4
T
76
k=1
1=0
p-u
dC2Cami + dC2C4
C2Cin
vf(W)))]l+
2
C2Cs
1h
V
Vf(ww.,)) w..
V
1
1=
k=1
h=1
p=0
dCaC's + C2Can
dO2Cs C2C++
ni In
[f(w)))
1 V
1- 13
==
which by Lemma further leads to
FeLimail
Sn C2Css + 1
JC2Cs
[L= + (nLo + LAVieDDo nvdcii))
1=0
C2Can
+n dO2Os - v
(1
dC2Cs
T
V Vf(Ww.)) + /dC2O'+ C2Cin
C2C++ 1- V
n
m1(1m17)
1- --V3 3
dC2Cs tn C2C++ 1- /B
(nIo + Do
n Vdc Σ
m
dC2CavDi C.C, 1- VBF
|Cscss C.CanyDi
<n² (idti
m ((w.o)))
nn +1(1+ITT)
/
3n (osci+ dC2C4
(nIu+ LIVEVDD) n² VdCinn
(16)
We further define
Ca dCavD,
Cs +
Di Co dCss + 1- /By
n/
dC's )
(nTo + TaVaVDo) n² /ddcm + dCss CaCaneDi
Cr 2 3n
C4 + 1 /
n.
1 /3z
and thus
T
T
(( u.n) u(,
<C²
Cs
2 m 1=1
C Ci Cc.)
Small
Analysis for Eist. a.f -4, (( This term requires a more sophisticated analysis.
To begin with, provide decomposition of ug+1 uy- According to the definition of ug.
31

---

Under review as a conference paper at ICLR 2023
have
Mh+1
(w6+1.0 - B1 1,- (WE,0 - -1)
1 B1
(wk+110 10.00 BI (11( 11..-1
1 B1
2a-1 (wx,s+1 wk.s) - 31 Lind (wxxs wk.i-1)
1 81
[Wk41.0 1,-1 1) (1 (1) "
(Wi,141 Wk.s) -1( wk.
31
m + (1 - -B11) 2i=0
C max B1 9h-1
m1-1,m11
n-
31
1k
m + (1 - B1) Σ1=0
n-
81m--1a11
((
V2,00
1- 81
WV,n-1
/VK.0
1
2
31
81
Vuks
VVk.0
I- Bi
31
(1K-1
1166
VVK-1,n-1
mi
1=0
(17)
Here equation (+) is due to a direct application of the update rule of whei We then analyze the above three terms respectively, namely, we define
m + (1 B1)
> 12 =-D
3.MLk
dj
Sr (wn.)),
Vi,K,0
1- S1
Vi..D
(( ((rertm
n-2
af -ns
Mickn-1
mikki
1 81
Vuiki
VVLk../
(m0
B1
mis-I1--1)
1
VV1,0,
B1
A
(1)-
ma)
Mik-In-11
31
Vi,k-1,n-1
One can then easily observe that by Eq. (17),
Σ
a.l(wn)o)at+ Σ
OrJ(w,.oaff+ Σ
a.((w)))
IEL
LET targe
1EL
@. (A) Tackling Term Eierk
a.f(w),o)ot:
We have
Σ Orf(wso))af
TEliogge
0 n
O.((wro)
Σ
Σ
Or (www))))))))
( (ww.)) -iSTo, (w2,,)) -.
Vi.kD
Vi.kko
LELk large
LELE
Σ
a.f(wro))=
Σ
0. (w..)
Σ
(Erfse, (wi.s) - -..ve, (ws.o))
VI.ED
Mi.uo
JeLk targe
IELK
targe
Σ
Th VL.ED
0.f(wl,o) + (n + O (n
V (wwx
JELK large
32

---

Under review as a conference paper at ICLR 2023
where Eq. (+) is due
The Ve
Σ ( fn ( (20x.0))
IELK large
2n²
Σ
1er (wors) -es=e. (wok (20k,00))
1/6
1EL. large
2n²
ST7k
V V. TT (wa.d) V.rr, (wma,o))
(6)
2n
n-1
776
Vd
(To + LA VV. (1r.a)))) wx.ol
1=0
2n²
Sm
Vi(nLo + LLDDI//II/V/V//o + VVLL
BT
(9)
2n²
2n²
d(n" 2 Lo + wnnn Wo)LiiDDoCinn + nād
I (.VDiinnllV//(xuu.)
35
By
Here Eq. (*) is due to Corollary 2, Eq. (c) is due to fi is (Lo, Lmm-ohhthh Vi, and Eq. (+) is due to Lemma 3.
@. (B) Tackling Term EiEt, 0.f(w,,o)af
We have for any E llmazs
(
mi.kn-
1
mi.xa
V
v Vi,kk
31
Vi,ki
ViLko
1=
B1
1
1
1711,-1.8-11
1- B1
VVLk---n-1
@if(wk)o))
1|
2
B1
332)
Mi.k.l
1-
1-
t=U
(
1 B1
(8.f(ur,,))
n 1+
max (E(m)
(0.f((0kko)))
1
31
V1.KO
1+ 31
V2n
2/231
+ 132(32)
n n-1+ +
n
CilLa + LI LIV Do
- 31
Az
1- 31
+ (22)(32)
n-1+ 1+ 1
V2n
L,Civ D Σ
[VF(WE)))
1 1- -1
$7
j=0
1 31
V2n L Ci
k-1
R-1
+ m)g(32)
n- n- +
C
D2
7k
Σ
8
[V
1
31
1=0
where Inequality (x) is due to Corollary 2, and g is defined in Lemma 11 and Inequality (x) is due to Lemma 4, by which we have vi E 1-, .......,, 1}
2/23 + n+ 1- 31
(mLRal S max (0..v( FE(m
Ci + L Do) + L Ci / Dame V (w.k.))
n-1
LLCVVDA D
Σ
1-j
1=0
33

---

Under review as a conference paper at ICLR 2023
Therefore, summing over Largg and l leads to
Σ
drf(wx,o)af
k=1 RETlaagge
1+ 31
@rrf(wk.o)]
1k3(32)
11 1 (--1+
max (rJi( ieln]
I-31)
VVL,30
k=1 lelgagge
T
1 1+ $1
22n
2v231 1 $1
(2g(32)
11
n
C2(Lo + LIV Do)dva
1 $1
$2
km
1+33
V2n
T
+ dg(
n--1+ 1- B1
D1 L
Σ
2
[f((x)))]
B2
k=
+ =dg(3>)
n1 n- 1+
1+
V2n LICIV D1 >
T
1/6
k-1
(t--1)n
1-
$3
k=1
[=1
j=0
1 31
00:5
Σ
(k2(
1+ 1+
max (+f(( iEfn)
1- 31
LELA
large
11 n- 4 1 31
V2n
2/2281
+ (B22
11 +
Ci + In Tn Do)dDo dm (1 +In
1 B1
1- 1
1+ 31
V2n L1CIVDD DD
d2g(32)
n- 1+ +
11 1- B
1 31
B3
T
1 1+
(irf(wkoo)l
(B2)
n- 1 +
max @.fi(ww)oo)) (sE(n)
1- 31
VVLA.0
k= IEL
1 31
V2n
2/2.81
+ (B2)
n 1
n +
Ci + In Do)d (1+ T)
31
333
1 1-31 32
1 31
V2n
+ +gg(3))
11 1 +
L.C Di
[1 1- 13
1-
T
( + (nTo + IA LAvan/ Do) mvdCmnn)
Th
k=1
1+
(8.S(w)))))
max (..f(( (iE(n)
(kg(32)
n n- +
1- 31
VVL,K.D
k=1 IEL/erge
1+ 31
v2n
2V2.81
+1((2)
1-1+
n +
Ci(La L Do
1 31
B3
1-31
+ dg(
1 1 31
1- 31
V2n L.C DD/
11 1 3r
(1
1
(n V Dj)
T
m
V (w
A=1
1+ 81
V2n LI C Di
1
n (nto + LIVEIV nvdcmn'.
(32)
n- + 1- 31
1
B
1- 53g
where Inequality (+) is due Lemma 6.
2 (C) Tackling Term Eiet, a.S(wa,)
34

---

Under review as a conference paper at ICLR 2023
For any E Large.
10t 10:f(
- 11
M7k-1
17
VVl,k-,n-1 1 ( (mx
B1
Bi7I
Ci Ci(Or
(1 B1)
Vlvlk T(V + 1k-1)
BiTKK
1
Ci C:
(1 31) Vk I(V] Vk
Summing over k and large then leads to
Σ
(
LE
Targe
B1
T4
31
vk
I(Vk +
IELL larger
2
B1
VdCa
V ((w.k)))
(1
B1)m
Put (2(A), @.(B), and @C( together. We have
Σ
Σ ( u..))
#=llch
Σ
Tik Orf(wr,o))
na0(32)
n-
1+ B1
10 f
max fi
1 1- B,
Vi,..
k=1 1EEggaang
LeLt telharge
C.
[l In Cias
(18)
where C5 CB. and C7 are constants defined as
Cs
2n LI LivDin dg(82) n nn-1+ 1+
1+
V2n
LI DD (1+ 33
(n n
ViC + "11 (1 10-Bp Bi)m
99 Va
1-
2n2
1 1+ 81
/2n
2/23
Co
d(n 1n
14
n
3r
1- 3
8
1 3
Cio 2 3dg((32)
nn-1+ 1+ B1
V2n
LIVDD 87
(1+1-33)
(nLo LIVaVDo) nvdCinitCa.
1- B1
35

---

Under review as a conference paper at ICLR 2023
We then analyze the first two terms in Eq. (18) here. Specifically, we have
(w
1+ 9r ( max (m (e(())
+
Br
Vii.k. +
(E)
Zarge
Jarge
1 1+ B.
@
Σ
Σ
mex((2)
1
+
max (orfi(me,,))) (v((s)
B1
tellarge
teLgagge
2m
maxie[m]
welwa a)) +
m.w.f(wLo
1+
10: (w)
me0(i2)
(n-1+ 1111 n2
max 8. (wo..0)))))) (EiM)
m 10t (i
Large
LEL tElgarge
max
(: (ww. t
<o)
marf(wr..)) o)
me((32)
11-1+ 1+ 81
@
max (
2 gnj (0 o]1 +
1- 31
(c(d]
Iel
maX [
+ o
P2
ni)1l 9 Σ
v02
(V((m.)))l
2
r=1
Σ
m )
Σ
nn- n1=1+
1 81
max (0
2 c/u (c[a]
(
+
1- Bi
maxie(n]
(1mm.))).)) +
mi
1)m
Th
[V ra)il mh
13m
[
j-0
where Inequality (+) is due Corollary 2 and Equality (a) is due to
o)
max (l
2maxxie (we,
mma ( 2
iciml
IEL
rel
small
S
ndni
Cane C₁
h-1 Σ
VB
ne-r
Σ
IV Can Σ V33
1)at
n/
+ m
C2
Σ
[V
Parallel Eq. (16) and summing the right-hand-side of the above inequality over from 1 to we
have
T
redikk
Call +
C4
k-1
V B2
(r-
1jn
m
V [ r5)1 11 + Can
Σ
k-1
v 32
(r- 1)m
m)--, + C.
V
((xx)))))
2
1=0
T
C
2
Vf(
+
2
A=
Suppose now there does not exist an iteration k E [7], such that
1 1 81
2n
[Vf < 2vd(222 (2g(
n n
1 1 B1
since otherwise, the proof has been completed. By Lemma 8, we then have f
1 81 f
Σ
Σ (eg(32)
n 111
max 10: fc(w.x.))) (tE())
VL +e
1- Br Vil,a. +e
LELgang
[V/(w>))]
2(2 + 7h
min
vDi
+ VDo
R-1
E-1 (r- 1)m
n-
0 The
B2
[V(We-r))) + me
B
-
1/k
| ((wa))))
1=0
Putting @ and @ together and summing over k. we have
f(ur+1) - [(ui)
Th 2(2v2+1) min [V /
(5+Co)0
T Σ
& + /D }
m
vD,
k=1
+ ((5+ + +2) + Co In + ( +2) + +
T M
nLo + Li 30 302dm
3L1 / Dr Di
| [
k=l
36

---

Under review as a conference paper at ICLR 2023
1 min
[
[V((wo))1)) + +2)ss + 3L1 3LIvAVDiCRd
ma ((W,o))
2(2v2+
VDi
+ Vo
2
C2)Cs Co
nLo + LivavD
3C
ln
2
C2)C++ Cio nho Liviy 3C2dmi
2
2
[V
U1 2(2v2+1) min
(w o) C12 C13. 7 C
VDi
+ VDo
where C11, C12, and C13 defined as
3L1 3LIVAVDiCCd
Cn 2 +2 C2
2
2 - C2)Cs + nLo + I1 LIVTY Do dc
1
C12 _
2
C1a ~ 2 C2)Cr + Cio nLo Liven Do
3C2dn
2
On the other hand, as for vk [T].
1 1vDo +E
VD
+
(
4 VDi VDo +
we have that
DDo +
VDi [V
The (
11
-
n + π
min [Vf(ww,))):
4 vD1
VDo +E
1
DD
+
8 2
V
Dink min
[V [[V/(o)))))l VD1
4
vD1
VD +E
and thus,
f(ur+1) f(uz)
T Σ
Tl 2(222 + 1)
min
Cn
Mh
/f Cialn Cis
vD
E Voo
1=1
k=1
$ Σ
Th 2(2 1)
min
[VVf(wx,))
[Vf(w)))))
Do + Cn Σ
n + C1aln Cia
vD
8 DDo
4vDr
[
+ VD
mh
min
VD
e Vo
A=1
T
[f(Ww)))1 [(
VDo + 4vD,
Σ Tjk k=1
VDICIIMT
min
+ Cia
Cumi ln
2(2v2+1)
VD
e Do
VDo +e Cuvi
Cia +
4vDi
[V
[V((wn)))) VDo
VDo +o & lu
1(2v2+1) min
(O1a
VD,
4/D,
(1a+
VDo +
4vDi Cuvit
The proof is completed.
Remark 12. By the definitions Cn, C12, and C13, one can easily observe that the hidden coefficient of O 4f) is in the order of 2/2 for d and for n. For completeness, would like to emphasize that our contribution is "providing the first convergence bound Adam withou the L-smooth condition" but we agree the bound itself can be tighten. Proving tighter bound is an interesting topic and we leave it as a future work.
37

---

Under review as a conference paper at ICLR 2023
Lemma 8. Let Assumptions and hold. Let 31 < B2 and Eq. (4) hold. Then, either there exists iteration l E [T], such that either
1 1 B1
2n 32
|V 2Vdd(222+ 1)v Dog(32)
n n--1+
B1
or for all iteration E [1,T], we have that
( 2 (m) [0:f( +
12 1-1+ 11
|0 (woso)
Σ (o)(32)
max (aff( (FE(m)
Lc(d]
1-
S 2m
max]g[1]
@r.i(ww +
V (V]((w))))
27t
min
222 1)
vDi
E + VDb
Proof.
To begin with, have my (wwko)
Σ (Eg((3))
1+
1+ B1
f
max [0 (0.f((ur))))) (iEnn
Ic/4
max
o) +
IE|4
1 1- B1
(0:fi(wo..)) + max:e(m)
2n
1 $1
(0rf(wa..)
mo((32)
n 1+
max | (orfi(wa.u)) <E|N]
(Eld
V/ wL
Do +e
[E|d
1 - 31
35 max
( +
2m
1 81
[arf(uk,o))
Σ
mag(3a)
n-
max (otf(
V Du +E
2E/4
8g
max:e/u) (0.f(
(iEln
where Inequality (+) is due to that
max (0WW: iE|n|
max (. dEim)
(10k
V V < (ullV/(wxx,)]1=== + Do-
REIN
ME mp]
We respectively consider the case E S Do and E > VD..
Case I S DD. In this case, we have that
ms V oll
Tkg(32) LE
Σ
n2 1
1
|0: (ww,(
max (c) (( (<Elm)
2 V. 1 Do +e
31
maxie in| (0.f( +
2m
nxl [
+ 91
(8.f(wk.v)
(33(32)
1
max ( iE(m)
2 Vi 12 + Do + VDo
LE14
-
31
maxie(a] (fw.())
2m
7h [(
1 31
2n (.s(wwk)))
(13)32)
n1 1-14
2. V/ 1 Do VDn
- 31
B
IE ml
1 31
2n
n- 1 1
|
[W
2 V Do DT
1 3r
85
We further discuss the case depending on whether | f (wxxo))l <
Di or not.
Case L1: [[V
Du In this case, the last line of the above equations can further lower
Di
bounded by
V f wx,0)|l
1+ 1
2n 33
2 F 2 + Do + VD.
Vdmag(32)
n
V
v f(ww,))l
V f(
1 3
2n
vdnag(32)
n-11
V ff( f(ww.o))l
(2v2 + 1)
1 1- 3r
V
33
[V vdg(B2)
1 B1
2n
n-
[
(2V2+1)VT6
Bg
38

---

Under review as a conference paper at ICLR 2023
Case 12: [W
Do D.
7 VV5(wx 12
1 31
2n
(dnug(32)
11 1 n1-1+
V f(ww)))
2 ( + Do + VDo
1
B1
33
mk [V
1 + B1
2n
Vdnng(32)
n 1
VV(ww,)))
(2v2 - 11vDD ((wn,)))
1 B2
V
52
=IK
(2v2 + (2v2+1)VDi
vag((2)) n 1n=
1 31
- B1
V
2n 13
| [
2 11k (12/2+1)VD) [
where Inequality (*) due to the constraint on 82. Therefore, we have either (I). there exists iteration & E [2]. such that
[Vf( S 22v0(222+ D)/(3)(3)) 1+ 1 B1 )
2n
1 - B1 )
or (2).for all & E [1,T],
(
1 B1
1 (ws,o)
Σ (32(
1
max (0.f((ux.o)) [F((
Ie(4]
2 max
+
le[d]
1 81
max;g[[] (.f.(wr,o)) +
[[(WK))]
[VS(w.
27h 212v2+11)
min
VDi
VDo
Case 11: VDn. In this case, have that
Σ m3((32)
1+
1 $1
max (0. ( (E|n]
2vDi D V Do +e
1- 3r
00 max ( +
[E(d]
In
1 1 B1
mgg(32)
n- 1 +
max (0 ( (<[()
2 Di Dil
1 B1
ON maxie(n) (otf( +
[e|d]
2n
Similar as Case we further divides the case regarding the value of [V
Case I111:
< c.,
In this case, we have
n || [f(ww,)))l
710(33) [e|d]
Σ
1
1+
(w.k
max fi [<E]a]
2 V/Di|V/[wx. + +e
1- B1
[o 2n
maxiem)
(0.f( +
Σ 1ag)(B))
TC- 1+
1
(0rf())))))
(0.f. (0.((w))))) (6.n)
maxx
(2v2 + 1)s
1- Bn
KE|4
nA (
1+ 81
122)(22)
- 1
Di [wwk)) Do
(2v2 1)e
1- 3n
174 ((wa,))
1 31
((32) n
Di (Dil/V((mx.)))1- Do
2/2 +1
I- 3r
39

---

Under review as a conference paper at ICLR 2023
Case I1.2: Dill (2
2..
This case is quite similar to Case 12,, and we have
7 n (
Σ
11 1- 1-
1+1
[ f
max (a) fi fi(2,,))) (E(m)
2 Dr | Vf(ww.)) + +E
le|d
B1
max.e(n)
(Onf( +
Th (V
1 81
@0.f(wr.o))
Tc((B2)
1
max (0.((ww..))) sE(n]
22v2 1)/D1 V[(Wko))]
1 Br
1E(4
max.g[m] (mr.o
1k V ((WWko))
2n
1 11
vdg
1- +
v f'wxaoll
(2v2 Di
B1
Vdg(32)
n2 n-
1 $1
2n
V o(ww))))
(2v2+ 1)VDI
1 31
27h 2(2v/ + 1)
Therefore, we have either (I). there exists iteration & [T]. such that
1+
81 B1
'n
[V s
n 1
+
1
(2). for all & [1,
m
Σ (32(32) IE(4
n + 1+
1 (wF.)
max (0.l((we.))) (tE(n)
2 maxie(n) [O.S(
+E
1- 31
V
max:g[m] @.fi(ms.o) +
min ( [
20h
2(2 1)
vDi
As conclusion Case and Case II, we have that either there exists a iteration E [T], such that
1 31
2n
[V s 2V 22d((222222222222222222222222222 11 1)/
B1
V
33
or for all iteration & E [1, we have that
(
Σ (x2(32)
1-1+ 1+
1 B1 1- 2m
(w..o)
max (rf((wo.))) [E(m)
2 ma)] ( +
le
[E(d]
max;e(n]
(zw,))) +
[V((w.)))
27%
min
2(2 1)
VDi
+ VDo
The proof is completed.
E EXPERIMENT DETAILS
This section collects experiments and their corresponding settings, and is arranged as follows: to begin with, we show that Adam works well under the different reshuffling order; we then provide the experiment settings of Figure 1.
E ADAM WORKS WELL UNDER DIFFERENT RESHUFFLING ORDER
We run Adam on ResNet 110 for CIFAR 10 across different random seeds and plot the 10-run mean and variance in Figure 4. One observe that the performance of Adam is robust with respect to random seed, and support Theorem in terms trajectory-wisg convergence. The experiment is based this repo, where we adopt the default hyperparameters settings.
40

---

Under review as a conference paper at ICLR 2023
Traniin
Thklre
Denations
Becations
Figure 4: Performance of Adam with different shuffling orders. We respectively plot the training loss and the training accuracy of Adam together with their variances over 10 runs with different random shuffling order. The result indicate the performance of Adam is robust w.r.t. the shuffling order.
E.2 LOCAL SMOOTINEESS VS. GRADIENT NORM
In this section, provide the models and hyperparameter settings of Figures 1. We will also illustrate how we evaluate the local smoothness.
Models and hyper-parameter settings in Figures 1. In Figure 1, exactly the setting Vaswani et al. (2017) on WMT 2014 dataset, based on this repo
How evaluate the local smoothness. We the same method Zhang et al. (2019a). Specifi- cally, with a finiteddifference step a, we calculate the smoothness at wy as
[Vww 7(wx+1 wxk
V V[(ww))
local smoothness
max (E,,,20....) (1)
7|| wt
41


Reviews:
[{"review_id": "zY-B92Ipmdp", "reviewer": "Reviewer_Ydg4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "ADAM has been observed to have better convergence properties than SGD in property, but the existing theoretical analysis cannot distinguish them, under the standard L-smooth setting. This paper considers a strictly broader class of loss functions, that is, the functions satisfy $(L_0, L_1)$-smoothness (Zhang et al., 2019), and rigorously show that ADAM can find an approximate first-order stationary point for any $(L_0, L_1)$-smooth loss function, while there is some $(L_0, L_1)$-smooth function that SGD will diverge.\n", "summary_of_the_review": "This paper studies an open problem that lies at the core of the interest of the ICLR community, that why ADAM can have better faster convergence than SGD. The authors give a theoretical rigorous treatment for convergence of ADAM to approximate the first stationary point under the recent proposed $(L_0,L_1)$-setting, where SGD is not guaranteed to converge, even with $1/\\sqrt{t}$ learning rates. This is a good paper and thus I suggest acceptance.\n\n\n======= \n\nUpdate after rebuttal: After discussion with AC, I realize that the current bound in Theorem 1 also hides factors like $poly(1/(1-\\beta_2))$ in $O(\\cdot)$. This dependency should be mentioned explicitly and discussed in detail because it affects the optimal choice of $\\beta_2$. Therefore I decreased my score to 6.\n\n", "strength_and_weaknesses": "##Pros:\n\n1. This paper tackles an important problem in optimization theory, regarding the superior convergence of ADAM over SGD. Despite the empirical success of ADAM, no theoretical separation on convergence rate has been made before. This paper first made such separation rigorously, in the $(L_0,L_1)$-smooth setting, which is arguably more realistic than the standard $L$-smooth setting for deep learning loss. \n\n2. This paper is well-written and easy to follow. I really appreciate the effort made by the authors to clearly explains the motivation, setting and proof ideas. \n\n3. The paper also points out a necessary condition for ADAM to converge, that is, $\\beta_2$ has to be sufficiently close to $1$. This is reflected through both  their upper bounds for gradient norm and their simulation.\n\n4. Though the indivual insights from the proofs are not compeletely novel, like the construction of the new poenntial function highlighted in Insight 1 is well-known (e.g., Ghadimi et al. 2015, equation (7)), combnining those technques and applying them correctly on a new setting is still non-trivial and needs a lot of effort.\n\n##Cons:\n\n1. Momentum seems not useful at all in the analysis. Indeed the existence of momentum seems only to make the analysis more complicated. To achieve the separation against SGD, it seems RMSProp (setting $\\beta_1=0$) is already enough. I note the authors do mention understanding the effect of momentum in future work, but it would be more useful to spell out or give a related discussion in the main paper as it can help the readers to understand.\n\n2. In the abstract, the authors claim that \"Adam can adapt to local smoothness, justifying Adam's adaptivity\". It is not clear what this sentence actually means in the algorithm level, e.g., does it mean the effective lr always maintains a certain relationship to the hessian? It seems the adaptivity of the moment estimation in ADAM holds by definition. This paper is really about the benefit of adaptivity. Same issue exists for the title, that is, instead of provable adaptivity, it should be the provable benefit of adaptivity.\n\n2. It is not clear to me whether Figure 1(b) satisfies the claimed relationship of 'local smoothness = $e \\times$ gradient norm'. It seems to me the slope is larger than 1, e.g., the right-top point is close to (1.0,2.5). I suggest the authors run a linear regression to decide the slope, which would be more convincing.\n\n##Detailed comments:\n\n1. In modern networks like ResNet and Transformer, normalization layers are ubiquitous. But unfortunately, the normalization layers doesn't quite satisfy the $(L_0,L_1)$-smoothness, because if one keeps the parameter before some normalization layer while keeping its direction, the gradient is proportional to the inverse of parameter norm and the hessian is proportional to the inverse of the squared parameter norm, which means that the local smoothness of any neural networks grows provably at the order of squared gradient norm. Thus a related question is, what is the limit of the current approach? Can it be used to deal with an even broader class of loss functions, which allow the smoothness to grow as a higher degree polynomial of gradient norm? \n\n2. typo, in Assumption 1, \"there exists positive constants\" should be there exist.  \n\n\n3. typo, on page 5, \"Assumption 2 is quite general. When $D_1 = 1/n$\". I think it should $D_1=0$.\n\n#References\n\n- Ghadimi, Euhanna, Hamid Reza Feyzmahdavian, and Mikael Johansson. \"Global convergence of the heavy-ball method for convex optimization.\" In 2015 European control conference (ECC), pp. 310-315. IEEE, 2015.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ptlQczSIXLS", "reviewer": "Reviewer_8djk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Adam is a popular optimizer for training neural networks in deep learning. This paper analyzes the convergence of Adam under the so-called ($L_0, L_1$)-smooth condition, and shows that Adam has a convergence guarantee without the bounded gradient assumption. They also provide counter-examples where GD/SGD can diverge under the ($L_0, L_1$)-smooth condition. A toy example is used to test the main theory. ", "summary_of_the_review": "The paper works on an important problem related to the convergence of Adam and shows the potential advantages over GD/SGD. I hope the authors add more experiments and more analysis in the revision for better reading and deeper understanding.", "strength_and_weaknesses": "Strengths:\n\nS1. The work establishes the convergence property of Adam under the ($L_0, L_1$)-smooth condition that is weaker than the $L$-smooth condition.\nS2.  It provides counter-examples where GD/SGD can diverge under the ($L_0, L_1$)-smooth condition, which shows the advantage of Adam over GD/SGD.\n\nWeakness:\n1. The main issue lies in the experimental part although the main point of the paper is its theoretical analysis. At the beginning of the paper, it mentions the examples of deep neural networks that satisfy ($L_0, L_1$)-smoothness requirements. But, the experiments only consider a quadratic function that is also $L$-smooth. It should add some more complex experiments that match the motivations of the paper.\n\n2. The paper should give a detailed comparison with recent related works including [1,2,3,4,5]. In [1], similar convergence results are established under the same choice of ($\\beta_1,\\beta_2$). It should clarify the technical difficulty under this new smoothness constraint. In [2], the weakness of SGD under the ($L_0, L_1$)-smooth condition has been studied. Though this work considers the diminishing stepsize, the significance should be discussed. The potential function in Section~4.2 is a widely-used trick in the analysis of the momentum-based methods, e.g., see [3,4,5]. The authors could provide some intuitive ideas behind the construction of the potential function and analyze its difference from other momentum-based methods.\n\n3. More theoretical comparisons between Adam and GD/SGD can be discussed.:1) both GD/SGD and Adam use the constant learning rate; 2) If the hyperparameters of Adam are chosen improperly, the convergence of Adam can be arbitrarily slow; 3) The convergence rate of Adam in Theorem~1 depends on the dimension $d$, while GD/SGD does not depend on it.\n\n4. As the paper contains many lemmas and theorems. It can be better organized for readers, especially for the appendix part. More details can be added for some inequalities e.g. the first inequality in the proof of Lemma 2.\nIn the second paragraph on Page 1, the statement ``larger $\\beta_1$ and $\\beta_2$ will bring more historical information into the update'' is rather vague. The authors can add explanations for the historical information.\n\n5. It could be good if the author can add some discussions on below questions:\n\n(1) The theorem suggests that $\\beta_2 = 1$ is superior for Adam since $\\delta(\\beta_2) = 0$ in this case. Does it mean $\\beta_2$ is redundant for Adam? If not, can you provide more evidence of the effect of $\\beta_2$ in theory or with experiments?\n\n(2) In practice, it is common to use a constant learning rate in a stage and it is known that GD converges with constant stepsize. So what is the convergence result of Adam when a constant learning rate is used?\n\n(3) Since gradient clipping is proven to be beneficial for GD/SGD [2], what is the advantage of Adam over the GD/SGD with gradient clipping or normalized gradient?\n\n(4) Since pretrained model is common, where the initialization is good, what is the advantage of Adam over SGD in this case? Note that in the last equality of Page 7, it may assume that $\\|\\nabla f(w_{k,0})\\|_2$ is large, so the cubic term of the gradient is dominant. \n\nBut, in practice, when the initialization is good, i.e. $\\|\\nabla f(w_{k,0})\\|_2$ is small, more discussion can be added.\n\n(5) In Page~7, the paragraph above Inequality (8): ``further notice that $u_{k,i}$ is close to $w_{k,i}$''. Can you give more explanation of this insight?\n\n\n[1] Yushun Zhang, et al. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems, 2022.\n\n[2] Jingzhao Zhang, et al. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.\n\n[3] Euhanna Ghadimi, et al. Global convergence of the Heavy-ball method for convex optimization.  European Control Conference, 2015.\n[4] Yanli Liu et al. An Improved Analysis of Stochastic Gradient Descent with Momentum. Advances in Neural Information Processing Systems, 2020.\n\n[5] Xiangyi Chen, et al. On the convergence of a class of Adam-type algorithms for non-convex optimization. International Conference on Learning Representations, 2019.\n\n[6] Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. RMSProp converges with proper hyper-\nparameter. In International Conference on Learning Representations, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6rPa7W7S1l-", "reviewer": "Reviewer_z7aZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper studies well-known Adam algorithm. Previous work shows that Adam can converge to a neighborhood of stationary point if the gradients are bounded (functions are smooth). In this paper, the authors show that, Adam can guarantees a even better results under a milder condition, i.e., L_0,L_1 smoothness, under which the gradients can be unbounded. Moreover, SGD may diverge under this condition. \n\n\n", "summary_of_the_review": "I do like this paper, but I have several concerns about this paper, which are listed above. ", "strength_and_weaknesses": "I have the following problems/concerns, and I hope the authors could help me understand these points:\n\n\na) For Theorem 1, I have the following problems/concerns:\n\n1.\tRandomness of the algorithm: In page 4, the authors say that the algorithm is actually a double-loop algorithm with stochastic shuffling. However, Theorem 1 holds without expectation or high probability, which is odd. Moreover, in which part of the proof the shuffling is used? The authors say “random shuffling is not a key factor in our analysis. The proof also works for other settings.”Can the authors be more specific about what are the “other settings”? Finally, isn't shuffling also a modification of Adam, which makes the algorithm not a pure Adam algorithm?\n\n2.\tDependance on n and d: From the Appendix, it seems that the upper bound is linear wrt n and d. Can the authors be clearer about this? \n\n3.\tThe inequality in (4): It is not clear to me why we can get this inequality. Where is rootd and n? Moreover, delta is upper bounded by 1/sqrt{D_1}. Thus, when D_1=0 in Assumption 2 (which only means the sum of the norm of the gradients is upper bounded), delta will explode? \n\n\n4.     Theorem 1 does not assume beta_2<1, which seems incorrect. \n\n\nb) **I have the following major concern** about writing: After a comparison, I find that many paragraphs here are basically copied/paraphrased from a previous paper (Zhang et al., 2022). For example, one can compare the two paragraphs of this paper under Assumption 2 and those under Assumption 2.2 of Zhang et al, (2022). Although the two papers are strongly related, I do not think this way of writing is appropriate. \n\nc. Other problems: \n\n\n1. Proof of Lemma 1: second equality: I do not see how to obtain this equality. Why is v_l (second order momentum of the l-th dimension) related to the max_{[n]} of abs(gradient)? \n\n\n2. Relation between Assumptions 1 and 2: when n=1, then Assumption 2 implies \\emph{bounded gradient} when D_1\\in(0,1] (it can also extend to n with D_1\\leq 1/n). So Assumption 1 only makes sense when D_1 is large. \n\n3. In page 17, it seems that all C_i are non-decreasing wrt n_1. So in this case why don't one just set eta_1=0? Is there a term related to 1/eta_1?\n\n4. The experiments are not very sufficient. As mentioned before, the authors did make some modifications to Adam (the shuffling and double-loop), which makes it not exactly the original Adam.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "46tkojP2ziy", "reviewer": "Reviewer_8ES2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "In this work, the authors mainly prove the convergence of Adam under the (L0,L1)-smoothness condition which is borrowed from existing work. Moreover, they use examples to show that GD and SGD can converge much slower than Adam under this assumptions. The reason behind for this advantage of Adam contributes to its usage on the local smoothness which is called “adaptivity”. ", "summary_of_the_review": "Although this work provides some good theoretical analysis under the (L_0, L1) smoothness assumptions, it does not provide good new insights and practical improvements.  Moreover, some key points are not well explained. ", "strength_and_weaknesses": "Strength: \nThere are main two contributions in this work. \n1)It proves the convergence of Adam under the (L0,L1)-smoothness condition.\n\n2)Under the same assumption, it uses examples to show the advantage of Adam over GD and SGD.\n\nWeaknesses:\n1)The main assumption is borrowed from other works but is actually rarely used in the optimization field. Moreover, the benefits of this assumption is not well investigated. For example, a) why it is more reasonable than the previous one? B) why it can add  gradient norm L_1||\\nabla f(w_1)|| in Eqn (3) or why we do not add other term?  It should be mentioned that a milder condition does not mean it is better, since it may not reflect the truth. For me, problem B) is especially important in this work, since the authors do not well explain and investigate it. \n\n2)Results in Theorem 1 show that Adam actually does not converge, since this is a constant term O(D_0^{0.5}\\delta) in Eqn. (5). This is not intuitive, the authors claim it is because the learning rate may not diminish. But many previous works, e.g. [ref 1],  can prove Adam-type algorithms can converge even using a constant learning rate.  Of course, they use the standard smooth condition. But (L0,L1)-smoothness condition should not cause this kind of convergence, since for nonconvex problem, in most cases, we only need the learning rate to be small but does not care whether it diminishes to zero. \n\n[ref 1] Dongruo Zhou, Jinghui Chen, et al. On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization\n\n3)It is not clear what are the challenges when the authors analyze Adam under the (L0,L1)-smoothness condition. It seems one can directly apply standard analysis on the (L0,L1)-smoothness condition.  So it is better to explain the challenges, especially the difference between this one and Zhang et al. \n\n4)Under the same assumption, the authors use examples to show the advantage of Adam over GD and SGD. This is good. But one issue is that is the example reasonable or does it share similar properties with practical problems, especially for networks. This is important since both SGD and ADAM are widely used in the deep learning field.\n\n5)In the work, when comparing SGD and ADAM, the authors explain the advantage of adam comes from the cases when the local smoothness varies drastically across the domain. It is not very clear for me why Adam could better handle this case. Maybe one intuitive example could help. \n\n6)The most important problem is that this work does not provide new insights, since it is well known that the second order moment could help the convergence of Adam. This work does not provide any insights beyond this point and also does not give any practical solution to further improve. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject