Adam Can Converge Without Any Modification On Update Rules
Authors: Yushun Zhang
Congliang Chen
Naichen Shi
Ruoyu Sun
Zhi-Quan Luo
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimization
deep learning
adam

Abstract: Ever since \citet{reddi2019convergence} pointed out the divergence issue of Adam, many new variants have been designed to obtain convergence. However, vanilla Adam remains exceptionally popular and it works well in practice. Why is there a gap between theory and practice? We point out there is a mismatch between the settings of theory and practice: \citet{reddi2019convergence} pick the problem after picking the hyperparameters of Adam, i.e., $(\beta_1,\beta_2)$; while practical applications often fix the problem first and then tune $(\beta_1,\beta_2)$.   Due to this observation, we conjecture that the empirical convergence can be theoretically justified, only if we change the order of picking the problem and hyperparameter.  In this work, we confirm this conjecture.  We prove that, when the 2nd-order momentum parameter $\beta_2$ is large and 1st-order momentum parameter $\beta_1 < \sqrt{\beta_2}<1$, Adam converges to the neighborhood of critical points. The size of the neighborhood is propositional to the variance of stochastic gradients. Under an extra condition (strong growth condition), Adam converges to critical points. It is worth mentioning that our results cover a wide range of hyperparameters: as $\beta_2$  increases, our convergence result can cover any $\beta_1 \in [0,1)$ including $\beta_1=0.9$, which is the default setting in deep learning libraries. To our knowledge, this is the first result showing that Adam can converge {\it without any modification} on its update rules. Further, our analysis does not require assumptions of bounded gradients or bounded 2nd-order momentum. When $\beta_2$ is small, we further point out a large region of  $(\beta_1,\beta_2)$ combinations where  Adam can diverge to infinity. Our divergence result considers the same setting (fixing the optimization problem ahead) as our convergence result, indicating that there is a phase transition from divergence to convergence when increasing $\beta_2$. These positive and negative results provide suggestions on how to tune Adam hyperparameters: for instance,  when Adam does not work well, we suggest tuning up $\beta_2$ and trying $\beta_1< \sqrt{\beta_2}$.

Adam Can Converge Without Any Modification On Update Rules
Yushun Zhangl Congliang Chen', Naichen Shi?, Ruoyu Sun 13- Zhi-Quan Luo 13 'The Chinese University of Hong Kong, Shenzhen, China University of Michigan, US SShenzhen Research Institute of Big Data {yushunzhang, cww.:uulaaann.cnnniinnnnnaiieae loongllangchen)(l1. inkk. cuhk. edu. en, naichens cencchnn@@uicc..cr umichh.du {sunruoyu, luozq] @cuhk. edu. cn
Abstract
Ever since Reddi et al. (2018) pointed out the divergence issue of Adam, many new variants have been designed to obtain convergence. However, vanilla Adam remains exceptionally popular and works well practice. Why is there a gap between theory and practice? We point out there is mismatch between the settings of theory and practice: Reddi et al. (2088) pick the problem after picking the hyperparameters of Adam, ie.. (81, B2): while practical applications often fix the problem first and then tune (81, B2). Due to this observation, we conjecture that the empirical convergence can be theoretically justified, only if we change the order of picking the problem and hyperparameter. In this work, confirm this conjecture. We prove that, when the 2nd-order momentum parameter B3 is large and 1st-order momentum parameter 31 VB2 1, Adam converges to the neighborhood of critical points. The size of the neighborhood is propositional to the variance of stochastic gradients. Under an extra condition (strong growth condition). Adam converges critical points. It worth mentioning that our results cover a wide range of hyperparameters: as B3 increases, our convergence result can cover any B1 [0, 1) including 31 0.9, which is the default setting in deep learning libraries. To our knowledge, this is the first result showing that Adam can converge without any modification on its update rules. Further, our analysis does not require assumptions of bounded gradients or bounded 2nd-order momentum. When 32 is small, we further point out a large region of (31, 32) combinations where Adam can diverge to infinity. Our divergence result considers the same setting (fixing the optimization problem ahead) as our convergence result, indicating that there a phase transition from divergence to convergence when increasing 32- These positive and negative results provide suggestions on how to tune Adam hyperparameters: for instance, when Adam does not work well, we suggest tuning up 32 and trying B1 < VB2.
Introduction
Modern machine learning tasks often aim to solve the following finite-sum problem.
min f(x) = Σ f((x), RCRd
f(x)=
(1)
7=0
where n is the number of samples mini-batches and x denotes the trainable parameters. In deep
learning, Adam (Kingma & Ba 2014) is one of the most popular algorithms for solving (T) It
has been applied various machine learning domains such natural language processing (NLP)
(Vaswani et al. 2017 Brown et al. 2020; Devlin et al. 2018), generative adversarial networks (GANs)
(Radford et al. 2015 Isola et al. 2017; Zhu al. (017)) and computer vision (CV) (Dosovitskiy
et al.] 2021). ). Despite its prevalence, Reddi et (0018) point out that Adam can diverge with wide
range of hyperparameters. main result (Reddi al. 2018 states that
*Correspondence author
We formally re-state their results Appendix D.2
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

For any B1, B2 s.t. 0 31 < V < L, there exists problem such that Adam diverges.
Here, 31 and 32 are the hyperparameter to control Adam's Ist-order and 2nd-order momentum. More description of Adam can be seen in (eprrithmm[pppeeeee
later in Section 2.1). Ever since (Reddi et al. 2018) pointed out the divergence issue, many new variants have been designed. For instance, AMSGrad (Reddi al., 2018) enforced the adaptor it (defined later Algorithm I to be non-decreasing; AdaBound (Luo et al. 2019) imposed constraint it E [C2. Cu] to ensure the boundedness on effective stepsize. We introduce more variants in Appendix [.]
On the other hand, counter-intuitively, vanilla Adam remains exceptionally popular (see evidence at (Scholar)). Without any modification on its update rules, Adam works well in practice. Even more mysteriously, we find that the commonly reported hyperparameters actually satisfy the divergence condition stated earlier. For instance, Kingma & Ba (2014) claimed that (31, (82 = (0.9, 0.999)
is a "good choice for the tested machine learning problems" and it is indeed the default setting in deep learning libraries. In super-large models GPT-3 and Megatron (Brown
al. 2020 Smith
et al. 2022). ($1. (2g) is chosen to be (0.9, 0.95). GAN researchers (e.g. Radford et al. (2155 Isola
al. (201h) use ($1, 32) (0.5, 0.999). All these hyperparameters live in the divergence region 31 VB.. Surprisingly. instead of observing the divergence issue, these hyperparameters achieve good performances and they actually show the sign of convergence.
Why does Adam work well despite its theoretical divergence issue? Is there any mismatch between deep learning problems and the divergent example? We take closer look into the divergence example and find out the mismatch does exist. In particular, we notice an important (but often ignored) characteristic of the divergence example: (Reddi et al. 2018) picks (8i, B2) before picking the sample size n.. Put in another way, to construct the divergence example, they change for different (32, 32). For instance. for (31, 32) = (0. 0.99), they use one n to construct the divergent example; for (31, (2)) = (0, 0.9999). they use another n to construct another divergent example, On the other hand, in practical applications of Adam listed above, practitioners tune the hyperparameters (81, (82) after the sample size is fixed. So there is gap between the setting of theory and practice: the order of picking n and (31, (82) is different.
Considering the good performance of Adam under fixed n, we conjecture that Adam can converge in this setting. Unfortunately, the behavior of vanilla Adam far less studied than its variants (perhaps due to the criticism of divergence). To verify this conjecture, we run experiments for different choices of (3,, 32) a few tasks. First, we run Adam for convex function ( with fixed n (see the definition in Section 3.2). Second, we run Adam for the classification problem on data MNIST and CIFAR-10 with fixed batchsize. We observe some interesting phenomena in Figure ! (a), (b) and (c).
First, when 3g is large, the optimization error is small for almost all values of 3 Second, when 31 B2 are both small, there is red region with relatively large error. On MNIST, CIFAR-10, 10, the error in the red region is increased by 1.4 times than that in the blue region. The situation is a lot worse function (2) (defined later in Section 3.2): the error in the red region is 70 times higher.
Converge (ours)
Diverge (ours)
82
111
81 (d) Our contribution Figure 1: (a), (b), (c): The performance of Adam on different tasks. For each task, we show the results with
(a) Function
(b) MNIST
(c) CIFAR-10
31 and B2 in grids {(k 1/k//50, /50, kz/50)(k 0, 49, la = 0, ; 49). (a): the optimality gap æ x² the convex function (2). (b) (c): The training loss on MNIST and CIFAR-10. (d): An illustration of our contribution in (81, (2) phase diagram. The shape of the region follows the solution our analytic conditions. The size of the region depends on n. The dotted curve satisfies 81 = /32. In all figures, is fixed before picking (81. 92).
While Adam's performances seem unstable in the red region, find that Adam always performs well in the top blue region in Figure 7 This seems to suggest that Adam can converge without any algorithmic modification, long 31 and 32 are chosen properly. We ask the following question:

---

Can Adam provably converge without any modification on its update rules?
In this work, theoretically explore this question. Our contributions are visualized in Figure (d). We prove the following results when n is fixed (or more rigorously, when the function class is fixed);
We prove that when $2 is large enough and 31 < /32, Adam converges to the neighborhood of critical points. The size of the neighborhood propositional the variance of stochastic gradients. With an extra condition (so-called strong growth condition), we prove that Adam can converge to critical points. As 82 increases, these results can cover any momentum parameter 31 [0. 1) including the default setting 31 = 0.9. In particular, our analysis does not require bounded gradient assumption.
We study the divergence issue of small-32 Adam. We prove that: for any fixed n (or more rigorously, for any fixed function class), there exists a function such that, Adam diverges to infinity when ( 82) is picked the red region in Figure | (d). The size of the red region increases with n. The shape of the region follows the solution to our analytic conditions.
We emphasize few characteristics of our results. (1) phase transition. The divergence result considers the same setting as our convergence result, indicating that there a phase transition from divergence to convergence when changing B2. (2) problem-dependent bounds. Our convergence and divergence regions of (31, 33) are problem-dependent, which is drastically different from (Reddi et al. 2018) which established the
worst-case choice of (32, 32). (3) non- non-asymptotic characterization. the "divergence region" ($1, 32) expands increases and converges to the whole region [0, 1)² n goes to infinity, which recovers (actually stronger than) the requires 81 VBg. In this sense, we view the divergence result of (Reddi et al. 2018 an
divergence result of (Reddi et al.) 2018 that
asymptotic characterization of the divergence region (as n - oc) and our divergence result as a non-asymptotic characterization (for any fixed n). We provide more discussion in Section 4
Our positive and negative results can provide suggestions for tuning B1 and 82: for instance,
Adam does not work well, we suggest tuning up 32 and trying 31 < v /22 We provide more tuning suggestions in Appendix C
We believe our results can boost new understandings for Adam. While Reddi et al. (2018) reveal that "Adam can diverge", our results show the other side of the coin: when n is fixed (or when function class is fixed), Adam can still converge without any modification on its update rules. Our results suggest that Adam is still theoretically justified algorithm and practitioners can use it confidently.
We further emphasize that our convergence results cover any 31 [0, 1). which allows the algorithm to bring arbitrarily heavy momentum signals. It turns out that large- rrgee-mmmentmm Adam is not easy to analyze. Even with stronger assumptions like bounded gradient (=)]l C, Vx), its convergence is not well understood (see related works in Section 2.2p. To our best knowledge, this is the first result that proves vanilla Adam with any 81 converge without any assumption of bounded gradient or bounded 2nd-order momentum. The proof contains a new method to handle unbounded momentum in the stochastic non-linear dynamics system. We will highlight our technical novelties in Section 5
2 Preliminaries
2.1 Review of Adam
We consider finite-sum problem [I. We use x to denote the optimization variable. We denote V as the gradient of fj and let be the component-wise product. The division and square-root operator are component-wise as well. We present randomly shuffled Adam in Algorithm
In Algorithm | m denotes the Ist-order momentum and denotes the 2nd-order momentum. they are weighted averaged by hyperparameter $1, 32, respectively. Larger B1, B2 will adopt more history information. We denote TR.i, my..; Uk, Rd the value of xx, m, at the k-th outer loop (epoch) and i-th inner loop (batch), respectively. We choose T)2-
0i as the stepsize. In practice, is
Vnk
adopted for numerical stability and is often chosen to be 10 10-8 88 our theory, we allow c to be an arbitrary non-negative constant including 0.
In the original version of Adam in (Kingma & Ba 2014), it has an additional "bias correction" step.
V1-33
This "bias correction" step can be implemented by changing the stepsize 7p into Tie = 1- nk
3

---

Algorithm Adam
Initialize 31.0 To. m1,-1 (z(0 and v1,-1 max; Vf((zo) V.(((z)).
for k === + 00 do
Sample {Tk.u> Tk.1>".. -kk,n-13 random permutation of {0,1,2, , do
for = -0
ma. 3 (1 31 V (Fk,.)
Uk = f2 (1 B2) V rm (T) V VJrn (Tx,e)
2R,1+1 Fki Vhi,t mk,i
end for
2,0+1,0 Tk,n Uk+1,-1 Uk 1; m4+1,-1 Mk,n-1 end for
and using zero initialization. In Algorithm T the "bias correction" step is replaced by special initialization, which corrects the bias as well. Note that re E [vI- 327h. I-3, mkl is well-bounded near 7),, 7% and fis brings the same convergence rate. In addition, as the effect of initialization becomes negligible when the training progresses, Adam with zero our initialization will have the same asymptotic behavior. In the main body of our proof, we follow the form of Algorithm [ which makes results cleaner. For completeness, we add the proof on the convergence of Adam with "bias correction" steps in Appendix G.11
In our analysis, we make the assumptions below.
Assumption 2.1. we consider I and fi()) satisfies gradient Lipschitz continuous with constant L. We assume fz) is lower bounded by finite constant f*
Assumption 2.2. (x(z) and [(x) satisfy: Σn [V((()) (=) + Do, Vo E Rdd
Assumption 2.2 is quite general. When D1 1/n, it becomes the "constant variance" with constant Da/n. "constant variance" condition is commonly used in both SGD and Adam analysis (e.g. (Ghadimi al. 2016 Zaheer et al. 20188] HHuan et al. (02TT). Assumption 2.2 allows more flexible choices of D1 7 ni and thus it is weaker than "constant variance".
When Do > 0, the problem instance is sometimes called "non-realizable" (Shi et al. 2020). In this case, adaptive gradient methods are not guaranteed to reach the exact critical points. Instead, they only converge to bounded region (near critical points) (Zaheer et al., 2018 (Shi et al. 2020). This phenomenon indeed occurs for Adam in experiments, even with diminishing stepsize (see Figure (a)). The behavior of SGD is similar: constant stepsize SGD converges to bounded region with its size propositional to the noise level Do (Yan et al. 2018 Yu et al. 2019 Liu et al. 2020b).
When Do 0. Assumption 2.2 is often called "strong growth condition" (SGC) (Vawwani et al. 2019). When || fx)]l O. under SGC we have (z)] 0 for all j. SGC is increasingly popular recently e.g. (Schmidt & Roux [2013] Vaswani et al. 2019). This condition is known to be reasonable the overparameterized regime where neural networks can interpolate data points (Vaswani et al. 2019). We will show that Adam can converge to critical points if SGC holds.
When f*, L, Do, Dj are fixed priori, use FT:f" (IRd) to denote the function class con- taining / (x) satisfying Assumption 2.1 and 2.2 with constant n, f", etc.. Since is fixed when the function class Fn.l" D.D.. (IRd), we introduce this notation to clearly present the divergence result in Without this pre-defined function class, the claim of divergence might be confusing.
Proposition 3.3
2.2 Related Works
Ever since Reddi et al. (2018) pointed out the divergence issue, there many attempts designing new variants of Adam. Since we focus on understanding Adam without modification on its update rules, we introduce more variants later in Appendix D.I
Compared with proposing new variants, the convergence of vanilla Adam is far less studied than its variants (perhaps due to the criticism of divergence). There are only a few works analyzing vanilla Adam and they require extra assumptions. Zhou al. (2018b) analyze the counter-example in (Reddi et al.] 2018) and find certain hyperparameter can work. However, their analysis is restricted to the counter counter-example, /Zaheer et al. (2018) study the relation between mini-batch sizes and (non- )convergence of Adam. However, this work require 31 0 and Adam is reduced to RMSProp

---

(Hinton et al. 2012). De et al. (2018) analyze RMSProp and non non-zero--1 Adam, but they assume the sign of all stochastic gradients keep the same. It seems unclear how to check this condition a priori. Additionally, they require 31 to be inversely related to the upper bound of gradient, which forces 31 to be small (as a side note, this result only applies to full-batch Adam). Défossez et al. (2020) analyze Adam with 81 < B2 and provide some insights on the momentum mechanisms. However, their bound is inversely proportional to e (the hyperparameter for numerical stability) and the bound goes to infinity when goes to O. This is different from practical application since small such as 10 often works well. Further, using large e is against the nature of adaptive gradient methods because Vē no longer dominates in the choice of stepsize. In this case, Adam is essentially transformed back to SGD. Two recent works (Huang et al., 2021) and (Guo et al.) 2021) propose novel and simple frameworks to analyze Adam- Aamm-l with large 31. Yet, they require the effective stepsize of Adam This boundedness condition changes Adam into AdaBound (Luo et a (2119) and thus they cannot explain the observations on original Adam in Section [] To summarize, all these works require at least one strong assumption (e.g. large <). Additionally, they all (including those for new variants) require bounded gradient assumptions.
to be bounded in certain interval, i.e., Vorte E Cu]
recent work (Shi et al. 2020) takes the first attempt to analyze RMSProp without bounded gradient assumption. They show that RMSProp can converge to the neighborhood of critical points. g We believe is important to study Adam rather than RMSProp: Numerically, Adam often outperforms RMSProp on complicated tasks (c.g. on Atari games, the mean reward is improved from 88% to 1 110% (Agarwal et al. 2020)). Theoretically, literature on RMSProp cannot reveal the interaction between 31 and B2: or how these hyperparameters jointly affect (or jeopardize) the convergence of Adam. However, are at least three challenges, First, it seems unclear how to control the massive momentum m, of Adam. Second, m, is multiplied by 1/ //V causing non-linear perturbation. Third, my and 1/ /o are statistically dependent and cannot be decoupled. We propose new methods to resolve these issues. We highlight our technical novelties in Section 5
non-trivial to jointly analyze the effect of 3, and 33- We point out there
2.3 The Importance and Difficulties of Removing Bounded Gradient Assumptions
Here, we emphasize the importance to remove bounded gradient assumption. First, unlike the assumptions in Section 2.T] bounded gradient not common SGD analysis. So it of theoretical interests to remove this condition for Adam. Second, bounded gradient condition rules out the chances of gradient divergence a priori. However, there are numerical evidences showing that Adam's s gradient can diverge (see Section 6 Appendix (B. Removing the boundedness assumption helps us point out the divergence and convergence phase transition in the (31, diagram.
However, it is often difficult to analyze convergence without bounded gradient assumption. First, it is non- non-trivial to control stochastic momentum. Even for SGD, this task is challenging. For instance, An early paper Bertsekas & Tsitsiklis (2000) analyzed SGD-type methods without any boundedness condition. But it is not until recently that Yu et al. 2019); Liu et al. (2020b); Jin et al. (2022) prove SGDM (SGD with momentum) converges without bounded gradient assumption. Such attempts of removing boundedness assumptions are often appreciated for general optimization problems where foouned-asssupption
is considered
major contribution.
Secondly, for Adam, the role of momentum m, is even more intricate since it is multiplied by 1/ Combined with ut the impact of previous signals not only affect the update direction, but also change the stepsize for each component. Further, both momentum m, and stepsize 1/ / are random variables and they are highly correlated. Such statistical dependency causes trouble for analysis. In summary. the role of momentum in Adam could be much different from that in SGDM or GDM. Even with boundedness conditions, the convergence of large-3; Adam is still not well understood (see related works Section (.2). In this work, we propose new techniques to handle Adam's 's momentum under any large 31, regardless of the gradient magnitude. These techniques are not revealed in any existing works. We introduce our technical contribution in Section
For completeness, we explain why they require this condition in Appendix D.I
*We notice that they also provide a convergence result for Adam with 8n close enough to O. However, a simple calculation by Zhang et al. (2022) shows that they require 31 < 10-7. Thus their result does not provide much extra information other than RMSProp.
5

---

3 Main Results
3.1 Convergence Results
Here, we give the convergence results under large $2.
Theorem 3.1. For any f(z) E Fm.l" FL,Do., (RO). we assume the hyperparameters in Algorithm 1
satisfy: B1 v32 <1; B2 is greater or equal to a threshold "n (n); and Tn satisfies km 2 and g/ 11mmm11n S
Vnk Let km E
n
87
we have the following results for any T > km:
2 Do
}
log VT
min AE(Nm 23]
E min
V Vf
+ +((DD))
Remark 1: the choice of $2. Our theory suggests that large 32 should be used to ensure conver- gence. This message matches our experimental findings in Figure [ We would like to point out that the requirement of "large 32" is neccessary, because small B2 will indeed lead to divergence (shown later in Section
3.2). p. We here comment a bit on the the threshold 71 (n). 71 (n) satisfies
32 122100
1-88
(see inequality (34 and Remark G.7 where p constant that depends on the
training trajectory. In worst cases, p upper bounded by n 2.5 but we find the practical p be much smaller. In Appendix B we estimate on MNIST and C10AR-10. In practical training process, we
empirically observe that p R (n), thus the required " (n) Rs 1 - O (n 3) Note that our threshold of (32 is sufficient condition for convergence, so there may be gap between the practical choices and the theoretical bound of 32. Closing the gap will be an interesting future direction.
We find that (n) increases with This property suggests that larger 32 should be used when n large. This phenomenon is also verified by our experiments in Appendix B We also remark that Ti (n) slowly increases with 31 This property is visualized in Figure I (d) where the lower boundary of blue region slightly lifts up when $1 increases.
Remark 2: the choice of 31. Theorem 3.1 requires 31 < /B2. Since 32 is suggested to be large,
our convergence result can cover flexible choice of 31 E [0, 1). For instance, 82 0.999 brings the threshold of 31 < 0.9995, which covers basically all practical choices of 31 reported in the literature (see Section D. including the default setting 31 0.9. This result is much stronger than those in the
RMSProp literature (c.g. (Shi et al. 2020; Zaheer et al. 2018)). To our knowledge, we are the first to prove convergence of Adam under any /31 E (0,1) without bounded gradient assumption.
Remark 3: convergence to a bounded region. When Da > 0, Adam converges to a bounded
region near critical points. As discussed in Section 2.1 converging bounded region is common
for stochastic methods including constant-stepsize SGD 2020b) and himiiishing-stepsizz RMSProp (Zaheer al.
Yan et al. 2018 Yu et al. 2019 Liu et al.
2018 Shi al. 2020). This phenomenon
is also observed in practice: even for convex quadratic function with Do > 0. Adam with diminishing
stepsize cannot reach exactly zero gradient (see Figure (a) in Section 6). This is because: even though Th is decreasing, the effective stepsize 1jK/ /UK.i might not decay. The good news is that, the constant O( DD))) vanishes to 0 as 33 goes to 1 (both in theory and experiments). The relation between 82 and constant O(VDo, are introduced in Remark [.. 14 in Appendix G.9 The size shrinks to 0 because the movement of /Uk,i shrinks as 32 increases.
As corollary of Theorem 3.1 we have the following result under SGC (i.e., Dv- 0).
Corollary 3.2. Under the setting in Theorem 3.1 When Do 0 for Assumption 2.2 have
E f o log
min kE RRm,T
Under SGC (i.e. Do = 0), Corollary 3.2 states that Adam can converge to critical points. This is
indeed the case in practice. For instance, function (2) satisfies SGC and we observe 0 gradient norm after Adam converges (see Section 6 and Appendix B The convergence rate in Corollary 3.2 is
comparable that of SGD under the same condition Vaswani al. 2019
When 31 0.9, Am
15 for any n 2 1.

---

3.2 Divergence Results
Theorem 3.1 shows that when 82 is large, any 31 < <3 ensures convergence, Now we consider the case where B2 is small. We will show that in this case, a wide range of 31 is facing the risk of diverging infinity. The divergence of small-8y Adam suggests that "large 32 is necessary in the convergence result Theorem
3.1
We construct a counter-example in DL.D..D. (R*). Consider
f(x) = Ei= (z)
for E R, we define f((z) as:
fi(x) = nz,
I 2 -1
for = 0,
( 4
I
2 -1
fi(z) = (x 222 +
for i > 0.
(2)
+
x <
Summing up all the fi)),, we can see that
[(x) 2; (x 2)
x 22
x<
a lower bounded convex smooth function with optimal solution x² = 2. Function 2 allows both iterates and gradients to diverge to infinity. As shown in Figure [ (a). when running Adam on (2. there exists a red large-error region. This shows the sign of divergence. We further theoretically
verify the conjecture in Proposition 3.3
Proposition 3.3. For any function class FL. Do.. Dj (Rd). there exists a f(x E Fi.ff"
L, .D., (R"). s.s.
when (31, 32) satisfies analytic condition (12). (13). (1] in Appendix E Adam's 's iterates and function values diverge to infinity. By solving these conditions in NumPy, we plat the orange region in Figure 2 The size of the region depends on n and it expands to the whole region when n goes to infinity.
The proof can be seen in Appendix E We find the "divergence region" always stays below the "convergence threshold" ri (n) in Theorem 3.1 so the two results are self-consistent (see the remark in Appendix Proposition 3.3 states the divergence of iterates and function values. Consistently, our experiments also show the divergence of gradient (see Section 6 Appendix [B). These sults characterize Adam's 's divergence behavior both numerically and theoretically.
We emphasize that the orange region is not discussed in (Reddi et al. 2018) because consider fixed while they allow changing. When a allowed to increase, our orange region will expand to the whole region and thus we can derive a similar (actually stronger) result as (Reddi et al., 2018). We provide more explanation in Section Combining Theorem Jan Propositions..3 we establish a clearer image on the relation between (31, (2) and qualitative behavior of Adam.
On function P with 20, Adam diverges in the col- ored region. The region is plotted by solving condition (12). [3)
Figure 2:
[4) in NumPy. The blue curve satisfies f3t = /B2.
Reconciling Our Results with (Reddi et al. 2018)
We discuss results. The divergence result shown in Section
the relation between (Reddi et al. 2018) and our
Diverge (Reddi et (8)8)) Diverge (ours)
does not contradict with our convergence results in Theorem 3.1 Further, it is different from our divergence result in Proposition
3.3 The key difference
lies in whether (81, (31,3)) is picked before or after picking the function class FL.D..,, (Rd). We discuss the following two cases.
82
Case I: When (31,82) is picked before picking F" D, (IRd). As discussed Section the divergence result requires different for different (81, B2). In this sense, the considered function class constantly changing. It does not contradict with our Theorem 3.1 which considers a fixed function class with fixed n. For Case I, we illustrate Adam's 's behavior in Figure The red region is proved by (Reddi al. 2018). For completeness, remove the condition
0
81
Figure 3: Adam's behavior when
(G1, 32) in Case I.

---

"B1 < VB22" and further prove that Adam will diverge to infinity for any (.) E [0, 1)2. The result is shown in the following Corollary Corollary 4.1. For any (51, 52) E [0, 1)². there exists a function satisfying Assumption 2.1 and 2.2 that the Adam's 's iterates and function values diverge to infinity.
4.1
In the proof, we also require different cause divergence for different (81, 32). So the function class is constantly changing. As result, in Case I, we cannot prove any convergence result.
Proof of Corollary 4.1 can be seen in the final paragraph in Appendix E
Table 1: Possible algorithmic behaviors of Adam in Case II.
Sctting
Hyperparameters
Adam's 's behavior
Vf E F... (ue*)
B2 is large and 91 < VB2
converge to critical points (Ours)
with Do =
Vf E Fr,
Fr. (R*")
converge to a bounded region with size (Do) (Ours)
B2 is large and 31 < 322
with Du #0
Ff E FE.
Di (R.)
The orange region in Figure
diverge to infinity (Ours)
Case I:: When 32) is picked after picking Filf"" P2
(IR)). When the function class is picked
in advance, sample size will also be fixed. This case is closer to most practical applications. In this case, we find that Adam's 's behavior changes significantly in the different region of Figure 3
First, vf(x) E FEE (Rd) will converge when B1 < vB2 and 32 is large. Second, [z)
FD. D, (R") will diverge to infinity when (2) are in the orange region in Figure Since Case
is closer to practical scenarios, these results can provide better guidance for hyperparameter tuning for Adam users. We provide some suggestions for practitioners in Appendix C
We also illustrate our convergence and divergence results in Figure (d). Note that there some blanket areas where Adam's ' behavior remains unknown, this part will be left as interesting future work.
For Case II, we summarize the possible behaviors of Adam in Table T
5 Proof Ideas for the Convergence Result
We now (informally) introduce our ideas for the convergence result in Theorem 3.1 Simply put, we want control the update direction mg,s/ Vuk,i inside the dual cone of gradient direction. Namely:
f(2,,))
Σ
mai >. O.
UK,
However, directly proving (3) could be difficult because both my.i and Uk, distort the trajectory. To start with, we try to control the movement of 2k by increasing B2 (similar idea as (Shi al. 2020 Zou et al. Chen Bhokko. a. we have Uk. RS Ukk0 when B2 is large. In this case, we have:
Chen et
al. 2021)) Recall Uk,i = (1-32) Σj=1 - " VTr (xE V V (o
((FRO)) vf(2n.o) > 0,
E
v (IL.,))
= E
Σ mi.s = E
Vuk.o
where the first "se" is due to the large 32 and the second "se" is our goal. Now we need show:
V (aTK.o)
d n-1
(
B
Σ
ma,
v((a))))
E
ΣΣ 2
(mi.x.- aif (Fw.o)) Re 0,
VUR.D
ULA.D
(4) where (xx is the (-th component of ff similarly for mı,k00 and vt (*) is due to the finite-sum structure. However, it is not easy to prove (4. We point out some technical issues below.
Issue massive momentum. Directly proving 4 is still not easy. We need first consider simplified problem: for every ( E [d]. assume we treat f. /Ui,k.0 as constant, how to bound E (mu,,.) a fr.rf...... (z
turns out that this simplified problem still non-trivial. When 31 large, my,k. contains heavy historical signals which significantly distort the trajectory from gradient direction. Existing literature
8

---

Zaheer et al. 2018 De et al. 2018 Shi et al. 2020) take a naive approach: they set 81 = 0 so that mI,k3 R Tn. ( Then we get (4) = However, this method cannot be applied here since we are interested in practical cases where 31 is large in [0. 1).
Issue II: stochastic non-linear dynamics. Even if we solve Issue I, it is still unclear how to prove is a.v. instead of constant. With this term involved, we are facing with a stochastic non-linear dynamics, which could be difficult to analyze. Further, Ōt (r /"r,., is statistically dependent with (mL,a T., (I2,,)),, so we are not allowed handle the expectation E(O: ((0rf( VoLx,o) separately.
(4) This is because: for every E (d], (ax /i,.
Unfortunately, even with additional assumptions like bounded gradient, there no general approach to tackle the above issues. In this work, we propose solutions regardless of gradient magnitude.
Solution to Issue I. We prove the following Lemma to resolve Issue I. Lemma 5.1. (Informal) Consider Algorithm For every [d] and any 31 E [0, 1), we have the following result under Assumption 2.1
6(3:)
E
(ma OeTr (Fx.O)) =0
Vk
where 0 (f is the 1-th component of V (( mLk, = (1 (:)):iTT. (Tk,s) + 8
We present the proof idea in Appendix A Simply put, we construct a simple toy example called "color-ball" model (of the 1st kind). This toy model shows special property of 8(3)). We find out: for Algorithm| 1 error terms from successive epochs can be canceled, which keeps the momentum roughly the descent direction. This important property not revealed in any existing work.
Remark 4: When assuming bounded gradient [()|| & G, naive upper bound would be 6(31)= = (G)) However, such constant upper bound does not imply 8(3,) close to O. will not help prove the convergence. This might be partially the reason why large-$1 Adam is hard to analyze even under bounded gradient (see related works in Section 2.2]. We emphasize Lemma [5. J.TTholds holds true regardless of gradient norm, so it could be deployed in both bounded or unbounded gradient analysis.
Solution to Issue II. We try show 44 by adopting Lemma 5.1 However, the direct application cannot work since (fF.oo))) is random. Despite its randomness, we find out that when B3 is large, the Vii.k.o
Vo1,,,0 brings extra perturbation, the quantity in (4) share the similar asymptotic behavior as 5(31). We prove the following Lemma
changes of 0)5(rr.)) shrinks along iteration. As such, although fix(x)))
Lemma 5.2. (Informal) Under Assumption 2.7 and 2.2 consider Algorithm X with large B2 and
31 < B2. For those with gradient component larger than certain threshold, we have:
@.f(.x.0)
Oc 01f(
=
(Tb)
(5)
Vūk,o
V0L-1.0
0: (
R-1
(
1
F
(mL,k.)
Si5 (z.o0)) =0
(6)
Vk
In Appendix A. "color-ball" model (we call it color-ball of the 2nd kind) which adopts the random perturbation of f(f.oo)) Vii.k.
we introduce how to derive (6) from (5) To do so, we introduce a new type of
Understanding color-ball model of the 2nd kind is crucial for proving Lemma 5.2
We conclude the proof of by some additional analysis on "those with small gradient component".. This case is bit easier since it reduces to bounded gradient case. For readers who wants to learn more about the idea of tackling Issue I and II, please refer to Appendix where we formally introduce the 1st and 2nd kind ballr-ball models. Since the whole proof is quite long, we provide a proof sketch in Appendix G.I The whole proof is presented in Appendix G
6 Experiments
To support our theory, we provide more simulations and real-data experiments. All the experimental settings and hyperparameters presented in Appendix B.I We aim to show:

---

(I), When $2 is large, large range of 31 gives good performance, including all B1 < VD2
(IT). When 32 is small, large range of (31 performs relatively badly.
200 cson B8o 880
D000 GdB 1900
(a) Function
with Pg
Function
with
Do
(c) The mejoectoiiis amall-P2 Adam
(d) WikTTen-11
Figure 4: The performance of Adam different tasks. (a) (b): large-92 Adam converges bounded region
when Do > 0 and converges to critical points when Do = 0. We use diminishing stepsize ny = =0.1/vk (c):
When 82 is small, gradient norm of Adam iterates can be unbounded. We use function 2 with initialization
x -5 and n = 20. The legends in (b) and (c) stand for [81, 82]. (d): The training loss under diffcrent (81, B2)
on NLP lasks. use Adam to train Transformer XL on WikiText- dataset.
Convergence to bounded region when Do > 0. In Figure 4 we run large-32 Adam on function (9) (defined later in Appendix BB. This function satisfies with Do > 0. We find that even with diminishing stepsize 17s = 1/Vk, Adam may not converge to an exact critical point. Instead, converges a bounded region. This is because: even though T)s is decreasing, the effective stepsize m// Tk, / might not decay. Further, the size of the region shrinks when .2 increases. This is because the movement of Voz,i shrinks 82 increases. These phenomena match Remark 3 and claim (I).
Convergence to critical points when Do = 0 Since function (2 satisfies Dg = O, we run more experiments on ( with initialization x = 5 and 5, 10, 15, 20. We show the result of 20 in Figure 4 (a), (b); the rest are shown in Appendix [ We find that: when 3g is large, Adam converges
critical points for 31 /2.. These phenomena match claim (I).
Gradient norm of iterates can be unbounded when 32 is small. On function 2
We further Adam with small B2 initialization x -5. In this case, gradient norms of iterates increase dramatically. This emphasizes the importance of discarding bounded gradient assumptions. These phenomena match claim (II).
(b)& (c) in Section D the training results match MNIST and CIFAR-10. As shown in Figure (b)& both claim (I) and (II). In addition, there is convex-shaped boundary the transition from low loss to higher loss, this boundary roughly matches the condition in Theorem 3.1
NLP. We use Adam to train Transformer XI. (Dai et al. 2019 on the WikiText-100 103 dataset (Merity et al. 2016). This architecture and dataset is widely used in NLP tasks (e.g. (Howard & Ruder 2018 See et 2017)). As shown in Figure 4 (d), the training results match both claim (I) and (II).
Conclusions
In this work, we explore the moonooconveeeence of Adam. When (3 is large, we prove that Adam can converge with any 31 < /B2. When B2 is small, we further show that Adam might diverge to infinity for wide range of 31. One interesting question is to verify the advantage of Adam over SGD. In this work, we focus on the fundamental issue of convergence. Proving faster convergence of Adam would be our future work.
Acknowledgments and Disclosure of Funding
Yushun Zhang would like to thank Bohan Wang, Reviewer xyuf, Reviewer UR9H, Reviwer tmNN and Reviewer V9yg for the careful proof reading and helpful comments. Yushun Zhang would like to thank Bohan Wang for the valuable discussions around Lemma G.3. Yushun Zhang would also like to thank Reviewer UR9H for the valuable discussions around Lemma 1. This work is supported by the Internal Project Fund from Shenzhen Research Institute of Big Data under Grant J0022022000.. This work supported by NSFC-A101201 70016, NSFC-617310011 and the Guandong Provincial Key Laboratory of Big Data Computing.
10

---

References
Agarwal, R., Schuurmans, D., and Norouzi, M. An optimistic perspective on offline reinforcement learning. In International Conference Machine Learning, pp. 104 114. PMLR, 2020.
Bertsekas, D. P. and Tsitsiklis, J. N. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):627-642, 2000.
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P.. Sastry, G., Askell, A., et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Chen, C., Shen, L., Zou, F., and Liu, W. Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration. arXiv preprint atXiv:2101.054: 2021.
Chen, J., Zhou, D., Tang, Y., Yang, Z., Cao, Y., and Gu, Q. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.00 06763, 201 8a.
Chen, X., Liu, S., Sun, R., and Hong, M. On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 888.02941 2018b.
Dai, Z., Yang. Z. Yang, Y., Carbonell, J., Le, Q V., and Salakhutdinov, R. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901. 1.02660000 2019.
De, S., Mukherjee, A., and Ullah, E. Convergence guarantees for rmsprop and adam in non-convex op- timization and an empirical comparison nesterov acceleration. arXiv preprint 2018.
Défossez, A., Bottou, L., Bach, F., and Usunier, N. On the convergence of adam and adagrad. arXiv e-prints, pp. arXiv-2003, 2020.
Deng, L. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 14-0::4411142211 142, 2012.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810000805, 2018
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL https:
www. teete/forunndd-iicoiitii
Dozat, T. Incorporating nesterov momentum into adam. 2016.
Gadat, S. and Gavra, I. Asymptotic study of stochastic adaptive algorithm non-come non-convex landscape. arXiv preprint arXiv:2012.05640 2020.
Ghadimi, S., Lan, G., and Zhang, H. Mini-batch stochastic approximation methods for nonconvex
stochastic composite optimization. Mathematical Programming, 155(1):267-305 2016.
Guo, Z., Xu, Y., Yin, W., Jin, R., and Yang, T. A novel convergence analysis for algorithms of the adam family. arXiv preprint arXiv:21 12.03459, 2021.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Hinton, G., Srivastava, N., and Swersky, K. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012.
Howard, J. and Ruder, S. Universal language model fine-tuning for text classification. arXiv preprint arXiv: 18011 801.06146, 2018
Huang, F, Li, J., and Huang, H. Super-adam: Faster and universal framework of adaptive gradients. arXiv preprint arXiv:2 082088, 2021.

---

liduka, H. Theoretical analysis of adam using hyperparameters close to one without lipschitz smoothness, arXiv preprint arXiv:2206.13299 13290, 2022.
Isola, P., Zhu, J.-Y.,
Y. Zhou, T., and Efros, A. A. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1125-1134, 2017.
Jin, R., Xing, Y., and He. X. On the convergence of msgd and adagrad for stochastic optimization. arXiv preprint arXiv:2201. 1204, 2022.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint
#tXiv:1412.6988 2014.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Liu, L., Jiang, H., He, P., Chen, W. Liu, X., Gao, J., and Han, On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2020a. URL htttps://openrevier net ftnt/forummid-zeee rrrge2aadr
Liu, Y., Gao, Y., and Yin, W. An improved analysis of stochastic gradient descent with momentum. arXiv preprint arXiv:2007.07990 2020b.
Luo, L., Xiong, Y., and Liu, Y. Adaptive gradient methods with dynamic bound learning rate. In International Conference on Learning Representations, 2019. URL https:://pppaarrevieee net/ forum?id Borgm22ddB
Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint arXiv:1609.07443 2016.
Radford, A., Metz, L.,, and Chintala, S. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06444 2015.
Reddi, S. J., Kale, S., and Kumar, S. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. http:/tpss//ogeeeeeeeeeeeee////s TyQu7f-RZ
Schmidt, M. and Roux, N. L. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint MxXiv:130.66377 2013.
Scholar, G. Adam: A method for stochastic optimization. https://scholar sorochollar.gggleee
it/citations'viee.oprvea hww.yy/OQQuAAAAAAAARAAAAAaaaaaaa
2022.
See, A., Liu, J., and Manning, C. D. Get to the point: Summarization with pointer-generator networks. arXiv preprint arXiv: S..iv:1774.046600 2017.
Shi, N., Li. D., Hong, M., and Sun, Rmsprop converges with proper Syper-parameter. In International Conference on Learning Representations, 2020.
Smith, S., Patwary, M., Norick, B., LeGresley, P., Rajbhandari, S., Casper, J., Liu, Z., Prabhumoye, S., Zerveas, G., Korthikanti, V., et al. Using deepspeed and megatron to train megatron-turme -uuring nlg 530b, large-scale generative language model. arXiv preprint arXiv:2201.. 1990. 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, I.., Gomez, A. N., Kaiser, F.., and Polosukhin, I. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Vaswani, S., Bach, F., and Schmidt, M. Fast and faster convergence of sgd for over wer-parameterized mod- cls and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1 1195-2004 PMLR, 2019.
Yan, Y., Yang, T., Li, Z., Lin, Q., and Yang, A unified analysis of stochastic momentum methods for deep learning. arXiv preprint arXiv:1800) 10396, 2018.
12

---

Yu, H., Jin, R., and Yang. S. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning. pp. 7184-7193. PMLR, 2019.
Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S.
Adaptive methods for nonconvex optimization. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.). Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL /
h/tp://e//.gcc.g.......o hewprroeeeennnnnn.reerrprp..p..p neurips. cctpappeer//11//iilll. 90655311000777711100666444422223
pdf
Zhang. Y., Chen, C., and Luo, Z.-Q. Does adam converge and when? In ICLR Blog Track, 2022.
URL URL httpttts:///crrblloooeeeo track. htw.llootrracc.gttuu.tooo/////ee wttp.u....//22/////////aaa adam https://iclr-blog- wrakkiahhb...222222555555esaaaa
Zhou, D., Chen, J.. Cao, Y.. Tang, Y., Yang. Z., and Gu, Q. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 00661,, 2018a.
Zhou, Z., Zhang, Q. Lu, G., Wang, H., Zhang, W. and Yu, Y. Adashift: Decorrelation and convergence of adaptive learning rate methods. arXiv preprint
2018b.
Zhu, J.-Y., Park, T., Isola, P., and Efros, A. A. Unpaired image-to-image translation using cycle- consistent adversarial networks. In Proceedings of the IEEE international conference on computer vision, pp. 2223-2232, 2017.
Zou, F., Shen, L., Jie, Z., Zhang, W. and Liu, W. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11127-11135, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(C) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "g6J4d9nSOQ5", "reviewer": "Reviewer_tmNN", "summary": "In this paper, the authors provide a solid convergence analysis which suggest Adam can converge to stationary points by picking proper $\\beta_1$ and $\\beta_2$ after fixing $n$. The conclusion is proved without assumption of bounded gradient.  The analysis can provide new insights for tuning Adam. ", "questions": "In the unconvergence counterexample provided by Reddi et al, 2018, the gradient variance is coupled with the number of target functions, i.e. $n$. Can authors explain more about how to decouple $n$ and gradient variance in your analysis? ", "limitations": "Some prior works have provided similar conclusion that tuning large $\\beta_1$ and $\\beta_2$ can make Adam converge. Even so, this paper provides a more solid and through analysis on generalized function class. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n+ The authors provide a through convergence analysis for the well-known unconvergence issus of Adam.  By picking large $\\beta_1$ and $\\beta_2$ after fixing $n$, the authors prove Adam can converge to stationary point of the specific function class given by Assumption 2.1 and Assumption 2.2. \n+ Compared to the divergence counterexamples provdied by [1], the target function is generalized to a larger class.  \n\nWeaknesses: \n+ However, some prior works [2] have provided the similiar conclusion that, after fixing the unconvergen counterexamples in [1], tuning larger $\\beta_1$ and $\\beta_2$ can make Adam converge. Meanhwile, they provide an equation to descibe the relation between $\\beta_1$, $\\beta_2$ and $C$ (the divergence cirtical point in [1]). Even so, their analysis is contrained on the convex finite-sum problem in [1] and not generalized. The analysis in paper would be more general. Can authors explain more comparison and strengths over them? \n+ Theorem 3.1 depends on Assuption 2.2 which contrain the variance of stochastic gradients. However, the unconvergence of Adam emerges only when variance is large [1]. Would Theorem 3.1 mean that Adam converge when gradient variance is within the constrains in Assumption 2.2? Can author analyze the behavior of Adam and how to tune $\\beta_1$ and $\\beta_2$ when gradient variance is large enought to diverge Adam? \n\n[1] On the Convergence of Adam and Beyond. ICLR 2018. \n[2] AdaShift: Decorrelation and Convergence of Adaptive Learning Rate Methods. ICLR 2019. \n[2] Adaptive Gradient Methods with Dynamic Bound of Learning Rate. ICLR 2019. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OzLbehhEgES", "reviewer": "Reviewer_V9yg", "summary": "This manuscript studied the Adam algorithm in the finite-sum setting: the number of samples is fixed in advance and Adam can pick $(\\beta_1,\\beta_2)$ according to it. The authors showed that under the case $\\beta_1<\\sqrt{\\beta_2}<1$ and large $\\beta_2$, Adam can converge to the stationary point under strong growth conditions and without bounded gradient assumption. When $\\beta_2$ is small, the authors also identified a region of $(\\beta_1,\\beta_2)$ such that Adam diverges. Some simple experiments on standard benchmark datasets are provided to justify the theoretical findings.", "questions": "1. Why this paper's message is important compared with Reddi et al. 2018? Why the knowledge of $n$ in finite-sum optimization is so important? What does the result look like in the online nonconvex optimization and finite-sum convex optimization setting?  \n\n2. The regret minimization might fail in certain regimes of $\\beta_1,\\beta_2$, but it might also converge to a stationary point without the knowledge of $n$ or even in an online setting. I don't know why Theorem 3.1 is so important since it is not comparable with Theorem 4 of Reddi et al. 2018. To establish the importance of the finite-sum setting, the authors need to provide a hardness result in an online learning setting in terms of non-convergence to a stationary point in polynomial time. \n\n3. What is the relationship between $D_0=0$ in Assumption 2.2 and the bounded gradient? We know that Adam can converge if we have a bounded gradient (e.g., Guo et al. 2021).\n\n4. How does the knowledge of $n$ affect the results theoretically and empirically?\n\nIf these concerns can be addressed, I am happy to increase my score.\n\n\n======POST REBUTTAL======\n\nThank you for the authors's response. I have read other's reviews as well. My main concern still remains with the finite-sum structure, but I  decided to change my evaluation a bit after reading the rebuttal.", "limitations": "N/A", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper studied an important problem: the convergence of Adam in the finite-sum setting and the number of summands in the objective function is known in advance.\n2. The paper is generally well-written.\n3. The proof idea is clearly presented.\n\nWeaknesses:\n1. While the results are interesting, I doubt the significance and the logical flow of this result. \n\n(1). The paper does not convey important messages about the convergence of Adam compared with Reddi et al. 2018. In particular, Reddi et al. 2018 studied Adam in the online convex optimization setting: they provided regret guarantees and non-convergence of average regret. However, this paper can only guarantee Adam's convergence with the strong growth condition and only to a stationary point. I don't see why the framework of finite-sum optimization and the knowledge of $n$ (i.e., the number of samples) would be so important to differentiate this paper from Reddi et al. 2018. \n\nFor example, it might be possible that in the particular case of  $\\beta_1<\\sqrt{\\beta_2}<1$ for Adam, the average regret does not converge but Adam indeed converges to a stationary point in the online learning setting such as Reddi et al. 2018 (where $n$ is not available). To show the fundamental advantage of finite-sum optimization and the knowledge of $n$, the authors are expected to show something like this: for an online nonconvex optimization problem, Adam with $\\beta_1<\\sqrt{\\beta_2}<1$ with large $\\beta$ and any other parameter choice (i.e., learning rate) cannot even converge to a stationary point in polynomial time, but the finite-sum version of this problem can indeed converge in polynomial time.\n\n(2). The convergence to stationary point only when $D_0=0$ in Theorem 3.1. What is the relationship between $D_0=0$ in Assumption 2.2 and the bounded gradient? We know that Adam can converge if we have a bounded gradient (e.g., Guo et al. 2021).\n\n2. Experiments are rather weak. The authors did not perform an ablation study in terms of $n$ (i.e., the number of training samples). Since this is the main message of the paper, the authors are expected to show that without the knowledge of $n$, Adam would diverge due to inappropriate hyperparameter choice (e.g., learning rate, $\\beta_1$ as in Theorem 3.1).\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AtMKyAEWYwD", "reviewer": "Reviewer_xyuf", "summary": "This paper proves that Adam with hyper-parameters $\\beta_1 \\leq \\sqrt{\\beta_2}<1$ and large $\\beta_2$ converges to a neighborhood of stationary points under mild assumptions on the function class and if Strong Growth Condition is satisfied, it converges to stationary point. Specifically, they argue that analyzing Adam with large $\\beta_1$ which results in large momentum is harder and previous works could not manage to handle non-zero $\\beta_1$. ", "questions": "Question:\n1) in lines 123-124, can you tell me (intuitively) why SGC is reasonable in overparametrized regime?can you point out to more literature (if any) regarding SGC?\n\n2) You say in line 98 that in your theoretical analysis you let $\\epsilon$ be an arbitrary non-negative constant including 0, but in proofs I couldn't catch that. It seems to me you just set it to 0. Please explain.\n \n3) in line 625, is it like you can $\\beta_1=0$ and large $\\beta_2$ can converge repeating the proof of Reddi? or is it a fundamentally different approach?\n\n4) in lines 196-199, I can't understand why smaller batchsize needs a larger $\\beta_2$. The bound $\\gamma_1(n)$ increases with n, so it seems to me that smaller $n$ has smaller $\\gamma_1(n)$ hence smaller $\\beta_2$ is okay.\n \nGrammatical Typos:\n\nline 93, randomly. line 125, converge \"to\". line 161, require. line 205, \"and\". line 262, \"red\". line 328, \"reduces\". line 509, \"some more\". line 597 and 622, \"require\".  line 658, \"as\". line 677, \"an\". line 690, converge\"s\". line 732, this. line 732, \"a\" instead of \"an\". \n\nMath typos:\n\nline 225 and 699, I think for $i>0$, $f_i(x)=1/2(x+2)^2\"+\"3/2$. \n\nline 291, equation 3, why there is no sign of $v_{k,0}$ in r.h.s (which is the case in equation 4) ?\n\nline 311, definition of $m_{l,k,i}$ should have $f_\\tau$ rather than $f$.\n\nbottom of page 22, $\\beta_2$s in nominators may change to $\\beta_1$.This also occurs in line 734, first line.\n\nline 725, first line, $j=0$.\n\nline 739, I feel a missing $1\\sqrt{k}$ in r.h.s. Also in line 740, there might be a missing $n$ in r.h.s. because of the summation.\n\njust above line 789, definition of $v$ should have $\\beta_2$ rather than $\\beta_1$.\n\nline 793, eq 17, $f_{\\tau_{k,i+1}}(x_{k,i})$ should change to $f_{\\tau_{k,i}}(x_{k,i+1})$, which is corrected in line 795.\n\nline 815, $x_k - x_{k+1}$ instead of $x_{k+1} - x_{k}$.\n\nline 837, 2nd line, based on eq (18) there might be a missing $\\frac{1}{\\sqrt{1-\\beta_2}}$, which just affects $F_1$.\n\nin the lines following line 1052, the subscript $\\ell$ is missing. you can note that in the beginning of Appendix $G_3$ to prevent confusion.\n\nequation at the bottom of page 40, based on Lemma F.3 you may have an extra factor of $n$, as Lemma F.3 deals with $f_\\tau$ rather than $f$.\n\nbottom of page 46, $-\\frac{1}{\\sqrt{k}}$.\n\nin equation 45, I feel like $f_0$ should cancel out in all epochs, just like epoch 0.\n\nin lines 1159 and 1166, Lemma G.12 gives $\\beta_2^n$ in denominator rather than nominator. Please correct it.\n\nline 1163, second equation, it is $ (F_{l,k}) _{k-1}$.", "limitations": "regarding negative societal impact, as authors pinpoint, training neural nets for illegal use is the main concern of this kind of work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is superbly written and the proofs, although being long, are managed to be as clear as possible. The writing style is excellent and helps reader understand the main ideas, specially the long proofs. I checked all the proofs, except for pages 56-58 and 60-64. Except for some typos, which do not affect the results, I could not find any flaw. I really like how you manage to use color-ball method and finite vs infinite sum argument in your work. Also as pointed out in several places, you explain the short-comings of previous work in analyzing non-zero $\\beta_1$.The removal of bounded gradient assumption and sticking to Assumption 2.1 which encompasses SGC and constant variance assumptions also looks entertaining. Example of giving convex functions in prop. 3.3 when Adam diverges in a relatively large region is also instructive: small $\\beta_2$ is dangerous. examples on practical networks also corroborate the analytic results. This piece of work seems to have important contribution for analyzing methods with momentum like Adam and as pointed in conclusion, it paves the way for much more intricate convergence analysis of Adam and its effectiveness compared to SGD. I highly recommend this paper to be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7FePaQmNb-", "reviewer": "Reviewer_UR9H", "summary": "This paper studies the Adam algorithm and proves that randomly shuffled Adam converges to the neighborhood of stationary points when 1st and 2nd-order momentum parameters satisfy that $\\beta_1 < \\sqrt{\\beta_2} < 1$ and $\\beta_2$ is sufficiently large. The analysis does not rely on the bounded gradient assumption. The divergence behavior of Adam is also studied, where it is shown that when $\\beta_2$ is small, Adam can diverge to infinity for a large region of $(\\beta_1, \\beta_2)$.", "questions": "Some comments and questions are as follows.\n\n1. The font of some figure legends is too small, e.g., Figure 1(a, b, c), Figure 2, and Figure 4. The axis labels like beta1 and beta2 should be replaced with $\\beta_1$ and $\\beta_2$.\n2. In Theorem 3.1, is $T$ fixed? What is the dependence of $\\beta_2$ on $T$?\n3. Theorem 3.1 only shows that the loss gradient will become smaller in expectation, and there is still a gap between the convergence of $\\mathbb{E}[||\\nabla f(x_{k,0})||]$ and the actual convergence of $x_{k,0}$. How to resolve this?\n4. As shown in Figure 4(c), the training loss does not seem to converge even for large $\\beta_2$?\n5. In the statement of Lemma G.6, $\\alpha$ is a random variable, but the left-hand-side of the equations after line 996 are expectations, so why can they be bounded by a random variable?\n6. In Appendix G.3 for the proof of Lemma G.3,  $\\frac{\\partial_\\ell f(x_{k,0})}{\\sqrt{v_{k,0}}}$ should be $\\frac{\\partial_\\ell f(x_{k,0})}{\\sqrt{v_{\\ell,k,0}}}$ instead? Similarly for the subsequent proofs.\n7. When controlling term (a) in the equation after line 1156, in the first inequality where Lemma G.12 is applied, there is a problem with the second term. Due to the indicator $\\tilde I_{k, k-1}$, we have $\\max_i |\\partial_\\ell f_i(x_{k,0})| \\geq Q_k$ which is a lower bound on the absolute value, and this does not lead to an upper bound on the absolute value of the second term, so the inequality is wrong here. Did I miss anything? If not, how to fix this?\n\n\n---\nMinor issues:\n\n1. In the statement of Lemma F.3, it should be $|\\partial_\\ell f_{\\tau_k, i}(x_{k, i+1}) - \\partial_\\ell f_{\\tau_k, i}(x_k,i)|$?\n2. Unify terms like $1+\\beta_1+\\beta_1^2 + \\cdots$ and $1 + \\beta_1 + \\cdots + \\beta^\\infty$ (define this properly).\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The convergence analysis of Adam is an important topic, and the claim made in this paper advances the understanding in this regard. The paper is well-written and easy to follow, and the graphic illustrations are nice. Some discussions on the comparison with existing works look redundant, especially those repeatedly emphasizing the removal of the bounded gradient assumption and the difference between the current work and the result in Reddi et al. (2018). I think these should be more condensed. \n\nThe theoretical analysis seems to be novel, though there might be some issues as will be discussed below. I'm willing to adjust the score if the questions are addressed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept