Convergence of Adam Under Relaxed Assumptions
Authors: Haochuan Li
Alexander Rakhlin
Ali Jadbabaie
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Non-convex optimization
Adam
Convergence
Variance reduction
TL;DR: We provide a new analysis of Adam and prove its convergence without assuming boundedness of gradients, under a generalized smoothness condition. We also propose a variance-reduced version of Adam with convergence guarantees.

Abstract: In this paper, we provide a rigorous proof of convergence of the Adaptive Moment Estimate (Adam) algorithm for a wide class of optimization objectives. Despite the popularity and efficiency of the Adam algorithm in training deep neural networks, its theoretical properties are not yet fully understood, and existing convergence proofs require unrealistically strong assumptions, such as globally bounded gradients, to show the convergence to stationary points. In this paper, we show that Adam provably converges to $\epsilon$-stationary points with $\mathcal{O}(\epsilon^{-4})$ gradient complexity under far more realistic conditions. The key to our analysis is a new proof of boundedness of gradients along the optimization trajectory of Adam, under a generalized smoothness assumption according to which the local smoothness (i.e., Hessian norm when it exists) is bounded by a sub-quadratic function of the gradient norm. Moreover, we propose a variance-reduced version of Adam with an accelerated gradient complexity of $\mathcal{O}(\epsilon^{-3})$.

Convergence of Adam Under Relaxed Assumptions
Haochuan Li MIT hd.
Alexander Rakhlin
Ali Jadbabaie MIT jadbabai @mi edu
MIT rakhlin@mit edu
Abstract
In this paper, we provide a rigorous proof of convergence of the Adaptive Moment Estimate (Adam) algorithm for wide class of optimization objectives. Despite the popularity and efficiency of the Adam algorithm in training deep neural networks, theoretical properties are not yet fully understood, and existing convergence proof's require unrealistically strong assumptions, such as globally bounded gra- dients, to show the convergence to stationary points, In this paper, we show that Adam provably converges to e-stationary points with O(e gradient complexity under far more realistic conditions. The key to our analysis edness of gradients along the optimization trajectory of Adam, under generalized smoothness assumption according which the local smoothness (i.e., Hessian norm when it exists) is bounded by sub-quadratic function of the gradient norm. Moreover, we propose a variance-reduced version of Adam with an accelerated gradient complexity of ((E-))
new proof of bound-
Introduction
In this paper, we study the non-convex unconstrained stochastic optimization problem
min(f(x) = Eg [f))
(I)
x
The Adaptive Moment Estimation (Adam) algorithm 23 has become of the most popular optimizers for solving ( when ff is the loss for training deep neural networks. Owing to its efficiency
and robustness to hyper- parepeaareeeess, is widely applied
sometimes the default choice in many
machine learning application domains such as natural language processing 44 13], generative
adversarial networks [35] 55), computer vision [14), and reinforcement learning
28 33 40)
also well known that Adam significantly outperforms stochastic gradient descent (SGD) for certain
models like transformer [50]
Despite its success practice, theoretical analyses of Adam are still limited. The original proof of convergence in [23 was later shown by [37 to contain gaps. The authors in (37) also showed that for range momentum parameters chosen independently with the problem instance, Adam does not necessarily converge
for convex objectives. However, in deep learning practice the rrper-parameters are in fact momblem-depender as they are usually tuned after given the problem and weight initialization. Recently, there have been many works proving the convergence of Adam for non-convex functions with various assumptions and problem-dependent hyper-parameter choices. However, these results leave significant room for improvement. For example, [12] 19] prove the convergence to stationary points assuming the gradients are bounded by constant, either explicitly or implicitly. On the other hand. [5] consider weak assumptions, but their convergence results are still limited. See Section for more detailed discussions of related works.
To address the above-mentioned gap between theory and practice, we provide
convergence analysis of Adam without assuming bounded gradients, or equivalently, Lipschitzness of the objective function. In addition, also relax the standard global smoothness assumption, i.e., the Lipschitzness of the gradient function, as is far from being satisfied in deep neural network training. Instead, we
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

consider a more general, relaxed, and non-uniform smoothness condition according to which the local smoothness (i.e., Hessian norm when it exists) around is bounded by sub-quadratic function of the gradient norm || [a))l (see Definition 3.2 and Assumption 2 for the details). This generalizes the (To. I1) smoothness condition proposed by [49 based on language model experiments. Even though our assumptions are much weaker and more realistic, we can still obtain the same ((("))
gradient complexity for convergence to an e-stationary point.
The key to our analysis is a new technique to obtain high probability, constant upper bound on the gradients along the optimization trajectory of Adam, without assuming Lipschitzness of the objective function. In other words, it essentially turns the bounded gradient assumption into result that can be directly proven. Bounded gradients imply bounded stepsize at each step, with which the analysis of Adam essentially reduces to the simpler analysis of AdaBound [B. Furthermore, once the gradient boundedness is achieved, the analysis under the generalized non-unt non-uniform smoothness assumption not much harder than that under the standard smoothness condition. We will introduce the technique in more details Section We note that the idea of bounding gradient norm along the trajectory of the optimization algorithm can be use in other problems as well. For more details, we refer the reader to our concurrent work [26) in which we present a set of new techiniques and methods for bounding gradient norm for other optimization algorithms under a generalized smoothness condition.
Another contribution of this paper is to show that the gradient complexity of Adam can be further improved with variance reduction methods. To this end, we propose Adam by modifying its momentum update rule, inspired by the idea of the STORM algorithm (9] Under additional generalized smoothness assumption of the component function f(- <) for each &. we show that this provably accelerates the convergence with a gradient complexity of O ((c-3). This rate improves upon the existing result of [47] where the authors obtain an asymptotic convergence of their approach to variance reduction for Adam in the non-convex setting, under the bounded gradient assumption.
ceriance-rdduce version of
1.1 Contributions
In light of the above background, we summarize our main contributions as follows.
We develop new analysis show that Adam converges to stationary points under relaxed assumptions. In particular, we do not assume bounded gradients or Lipschitzness of the objective function. Furthermore, we also consider generalized non-uniform smoothness condition where the local smoothness or Hessian norm is bounded by a sub-quadratic function the gradient norm. Under these more realistic assumptions, we obtain a dimension free gradient complexity of O(e-4) )) if the gradient noise is centered and bounded.
We generalize our analysis to the setting where the gradient noise is centered and has sub- Gaussian norm, and show the convergence of Adam with a gradient complexity of O Ogg~a 3.25 (1/c)).
We propose a variance-reduced version of Adam (VRAdam) with provable convergence guarantees. In particular, we obtain the accelerated O(e (3) gradient complexity.
2 Related work
In this section, we discuss the relevant literature related to convergence of Adam and the generalized smoothness condition, and defer additional related work on variants of Adam and variance reduction methods Appendix A
Convergence of Adam. Adam was first proposed by Kingma and Ba 23 with a theoretical convergence guarantee for convex functions. However, Reddi et al. 37 found gap in the proof of this convergence analysis, and also constructed counter-examples for a range of hyper- on which Adam does not converge. That being said, the counter-examples depend on the hyper- parameters of Adam, i.e., they are constructed after picking the does not rule out the possibility of obtaining convergence guarantees for problem-depente hyper- parameters, as also pointed out by (T].
Therefore,
Many recent works have developed convergence analyses of Adam with various assumptions and hlpper-paramete choices. Zhou al. (54) show Adam with certain hyper-parameters can work on the counter-exxne examlees of [37]. De et al. [10] prove convergence for general non-convex functions

---

assuming gradients are bounded and the signs of stochastic gradients are the same along the trajectory.
The analysis in [2] also relies on the bounded gradient assumption. Guo et al.
[9] assume the
adaptive stepsize is upper and lower bounded by two constants, which is not necessarily satisfied
[5] consider very weak assumptions. However, they show either 1) "convergence" only to some neighborhood of stationary points with a constant radius, unless assuming the strong growth condition; or 2) convergence stationary points but with slower rate.
unless assuming bounded gradients or considering the AdaBound variant [31.
Generalized smoothness condition. Generalizing the standard smoothness condition in a variety of settings has been a focus of many recent papers. Recently, [4 proposed a generalized smoothness condition called (Lo, L1) smoothness, which assumes the local smoothness or Hessian norm is bounded by an affine function of the gradient norm. The assumption was well-validated by extensive experiments conducted on language models. Various analyses of different algorithms under this condition were later developed [88 (4, 52
38 8 One recent closely-related work is 45] which studies converges of Adam under the (Lo, I1) smoothness condition. However, their results are still limited, we have mentioned above. In this paper, we consider an even more general smoothness condition where the local smoothness is bounded by a sub-quadratic function of the gradient norm, and prove the convergence of Adam under this condition. In our concurrent work [26], we further analyze various other algorithms in both convex and non-convex settings under similar generalized smoothness conditions following the same key idea of bounding gradients along the trajectory.
17
3 Preliminaries
Notation. Let ||-|| denote the Euclidean norm of vector spectral norm of matrix. For any given vector x, we use (I); to denote its i-th coordinate and x², var [x|] to denote its coordinate-wise square, square root, and absolute value respectively. For any vectors and y, and z/y to denote their coordinate-wise product and quotient respectively. We also write x I or x Σ y to denote the coordinate-wise inequality between x and y, which means (z); S (y); or (x); 2 (y); for each coordinate index i. For two symmetric real matrices A and B, we say A 3 B or A B if B A or A B is positive semi-definite (PSD). Given two real numbers a, IR we denote a A b == min a, 63 for simplicity. Finally, we use (.), ((-), and (2(-) for the standard big-O, notation.
y
Big-Theta, and
3.1
Description of the Adam algorithm
Algorithm 1 ADAM
1: Input: B, Baq. 1) X, T, Tinit
2: Initialize mg = f1 and F = Finit
3: for tort= 1,... .T' do
4: Draw new sample & and perform the following updates
5: my (1 3)m + 3V &x)
6:
Ut = (1 01 + Beq V f()).
7:
my i-(1-B3
8:
0f 1-(1-Bau) Bea)
9:
T++1 = Vo.-X ① m
10:
end for
The formal definition of Adam proposed in 23] is shown in Algorithm ! where Lines 5-9 describe the update rule of iterates {at (se)- Lines 5-6 are the updates for the first and second order re-scaled to mn and 0n in order correct the initialization bias due to setting my = up = 0. Then the iterate updated by J4+1 = I2 - hy O my where h; (/(i,
momentum, m, and v., respectively. In Lines 7-8, they
i, +
A) is the adaptive stepsize vector for some parameters 17 and X.
3.2
Assumptions
In what follows below, will state our main assumptions for analysis of Adam.
3.2.1
Function class
We start with standard assumption in optimization on the objective function f whose domain lies in Euclidean space with dimension d.
3

---

Assumption 1. The objective function f is differentiable and closed within its open domain dom(f) _ I2d and bounded from below, i.e., f := inf,, f(x) -00.
Remark 3.1. A function f is said to be closed if its sub-level set {ir E dom(f) f(x) S a} is closed for each E IR. In addition, a continuous function over an open domain is closed if and only f()) tends to infinity whenever x approaches to the boundary of dom((") which is an important condition to ensure the iterates of Adam with small enough stepsize 1) stay within the domain with high probability. Note that this condition is mild since any continuous function defined over the entire space I is closed.
Besides Assumption [ the only additional assumption we make regarding f is that its local smooth- ness is bounded by a quaddataaiiic function of the gradient norm. More formally, we consider the following (p, Lo. Lp) smoothness condition with 0 S p < 2.
Definition 3.2. A differentiable real-valued function f is (p. Lo, Lp) smooth for some constants p. Lo. Lp 2 if the following inequality holds almost everywhere in dom(f)
[>) S + (z))
Remark 3.3. When p Definition 3.2 reduces to the (To: I1) smoothness condition in [9 When = 0 or I.p = 0, it reduces to the standard smoothness condition.
Assumption 2. The objective function f is (p, Lo, Ly) smooth with 0 S p <
The standard smooth function class is very restrictive as only contains functions that are upper and lower bounded by quadratic functions. The (Lu, L1) smooth function class is more general since it also contains, c.g., univariate polynomials and exponential functions. Assumption 2 is even more general and contains univariate rational functions, double exponential functions, etc. See Appendix D.I for the formal propositions and proofs. We also refer the reader to our concurrent work 26 for more detailed discussions of examples of (p. Lo, I.p) smooth functions for different ps.
turns out that bounded Hessian norm at a point x implies local Lipschitzness of the gradient in the neighborhood around x. In particular, we have the following lemma.
Lemma 3.4. Under Assumptions and 2 for any a > O and two points dom dom(f), (f),y y E RRd such that |y x=I| S L=+L,IIV/()) we have E dfm(() and
(V( S (Lo + (o.IIIS(x)) + a))) 11y x
Remark 3.5. Lemma 3.4 can be actually used as the definition of (p. Lo, Lp) smooth functions in place of Assumption 2 Besides the local gradient Lipschitz condition, it also suggests that, as long as the update at each step is small enough, the iterates will not go outside of the domain.
For the special case of 1. choosing a = ma fx))] Lo/ L1 one can verify that the required
locality size in Lemma 3.4 satisfies L. (| 2 31," In this case, Lemma 3.4 states that
1
|| y < 1/(3)) implies [Vf V fxx)l < 2(Lo + L1 || fI) Ily =I| Therefore, it
reduces to the local gradient Lipschitz condition for (Lo, L1) smooth functions in (49 48 up to
numerical constant factors. For & 1, the proof is more involved because Grönwall's inequality used
in 49 48
no longer applies. Therefore we defer the detailed proof of Lemma 3.4 to Appendix D.2
3.2.2
Stochastic gradient
We consider one of the following two assumptions on the stochastic gradient fz in our analysis of Adam.
Assumption 3. The gradient noise is centered and almost surely bounded. In particular, for some and all 2
[x] Ed)
-V(a)l So, a.s.,
where E--1[-]= :- EE,, [t- is the conditional expectation given EI...., Assumption 4. The gradient noise is centered with sub-Gaussian norm. In particular, for some R 2 0 and all t 1,
E- ( (()),,)))= Ex)]= Vf(ae). PA-1 (IIV Ex) V 2 8) 8) 2e 2R_ Vs E R
where E.-1l 1.1 == IE..E..... E--1 and Pr, 1 == P(. ..., E(-11 are the conditional expecta- tion and probability given Ei....,E1-1

---

Assumption is strictly weaker than Assumption 3 since almost surely bounded random variable clearly has uub-Gaussian norm, but it results in a sligtlly worse convergece rate up to poly-log factors (see Theorems 4.1 and 4.2 Both of them are stronger than the most standard bounded variance
[f(=))] S o² for some o 2 O, although Assumption 3 actually common assumption in existing analyses under the (Lo, L1) smoothness condition (see c.g. 48). The extension to the bounded variance assumption is challenging and very interesting future work as it is also the assumption considered in the lower bound B1. We suspect that such an extension would be straightforward if we consider mini-bated batch version of Algorithm [ with batch size of = (e ?), since this results in a very small variance of O(e") and thus essentially reduces the analysis the deterministic setting. However, for practical Adam with ((1) batch size, the extension challenging and we leave it as a future work.
assumption [||| V (az,
Results
In the section, we provide our convergence results for Adam under Assumptions 1 and To keep the statements of the theorems concise, we first define several problem-dependent constants. First, we let A f(z1)=
co be the initial sub-optimality gap. Next, given a large enough
constant G > 0, we define
r:
5(L ",)'
: 3L0 + GL,
(2)
where L can be viewed the effective smoothness constant along the trajectory if one show for more detailed discussions). We will also use C1, C2 to denote some small enough numerical constants and C1. C2 denote some large enough ones. The formal convergence results under Assumptions the following theorem, whose proof deferred in Appendix
[x))( < G and | zz S r at each step (see Section 5
and are presented in
Theorem 4.1. Suppose Assumptions
and 3 holld. Denote i = log 16) for any 0 < 5 < 1. Let
G be constant satisfying G 2 max 2x, 20, VCJALLo, (CIA1 - }. Choose
0. B 1 BS min {1,
GA o
( rx
oAB 23/2
n min min
{
G LGVI' LVG
Let T max
1 30,
G
ne J. Then with probability least 1- 6, we have [V S for every
1 1 t S T, and & EL [V E
Note that G, the upper bound of gradients along the trajectory, is a constant that depends on X, G. Lo. Lp. and the initial sub-optimality gap A but not on There is requirement the second order momentum parameter Beq, although many existing works like 12 restrictions on it. We choose very small 3 and 7). both of which are Oce2). Therefore, from the choice of it is clear that we obtain a gradient complexity of ( ((e where only consider the leading term. We are not clear whether the dependence on c is optimal or not, as the 12(c lower bound in 3 assumes the weaker bounded variance assumption than our Assumpion 3 However, it matches
51 45 need certain
the state-of-the-ee art complexity among existing analyses of Adam.
One limitation of the dependence of our complexity on À is O(A-²), which might be large since is usually small in practice, e.g., the default choice = 10-8 in the PyTorch implementation. whose rates do not depend explicitly on À or only depend on Iog(1/A). However, all of them depend on poly whereas our rate is dimension free. The dimension d is also very large, especially when training transformers, for which Adam is widely used. We believe that independence on d is better than that on X, because di is fixed given the architecture of the neural network but À is hyper- parameter which we have the freedom to tune. In fact, based on our preliminary experimental results on CIFAR- 10 shown in Figure the performance of Adam is not very sensitive to the choice of X. Although the default choice of À 10 increasing it up to 0.01 only makes minor differences.
There are some existing analyses on Adam 12, 511 45
As discussed in Section 3.2.2 we can generalize the bounded gradient noise condition in Assumption 3 the weaker sub-Gaussian noise condition Assumption The following theorem formally shows the convergence result under Assumptions 2 and whose proof is deferred in Appendix E.6
5

---

60
Am1o-
A-1e8
A-1o-8
A-1o4
A-1o4
A-1o4
Test Freeer (80)
60
A-1o3
A-0.01
80
A-1o3
A-0.01
Test Frewe (90)
60
A-1o3
A-0.01
40
A-1
A-0.1
80
A-0.1
40
A-1
A-0.1
20
100
200
300
200
100
200
300
400
100
200
300
100
#poch
Ppoch
Epoch
(a) CNN
(b) ResNettSmall
(c) ResNerl
Figure Test errors of different models trained on CIFAR-10 using the Adam optimizer with = 0.9, Beg 0.999, = 0.001 and different Äs. From left to right: (a) a shallow CNN with
layers: (b) ResNet-Smal with 20 layers; and (c) ResNetl 10 with 110 layers.
Theorem 4.2. Suppose Assumptions
2 and 4 hold.
Denote I == log(2/5) and Let G be a constant satisfying G z
= Rv logg(T//) for any 0 < ò
<
1.
max 2x, 20, Lo (C)A) Choose
CIAE² oQGV
r2 I.Vii'
13/2
0 Psg S 1,
B S min
S min
G
LGG
Let T = max
G G 32
Then with probability at least 1 6, we have [f((x))] I G every
np
1 1st T, and ΣL_
[+x))) Se
Note that the main difference of Theorem 4.2 from Theorem 4.1 is that now O(vlog T') instead of a constant. With some standard calculations, one can show that the gradient complexity in Theorem 4.2 is bounded by
(1/c)), where max {3, 9+22 < 3.25.
5
Analysis
5.1
Bounding the gradients along the optimization trajectory
want to bound the gradients along the optimization trajectory mainly for two reasons. First, as many existing analyses of Adam rely on the assumption of bounded gradients, because unbounded gradient norm leads to unbounded second order momentum é, which implies very small stepsize, and slow convergence. On the other hand, once the gradients are bounded, it is straightforward to control é as well as the stepsize, and therefore the analysis essentially reduces to the easier one for AdaBound. Second, informally speaking" under Assumption 2 bounded gradients also imply bounded Hessians, which essentially reduces the (p, Los Lp) smoothness to the standard smoothness. See Section 5.2 for more formal discussions.
discussed in Section 2
In this paper, instead of imposing the strong assumption of globally bounded gradients, we develop new analysis show that with high probability, the gradients are always bounded along the trajectory of Adam until convergence. The essential idea can informally illustrated by the following "cireular" reasoning that we will make precise later. On the one hand, if / [v;(())] || < G for every 2 1, it is hard to show the gradient converges to zero based on our discussions above. On the other hand, know that converging sequence must be upper bounded. Therefore there exists some G' such that [xx)l < G' for every t 2 1. In other words, the bounded gradient condition implies the convergence result and the convergence result also implies the boundedness condition, forming circular argument.
This circular argument is of course flawed. However, we can break the circularity of reasoning and rigorously prove both the bounded gradient condition and the convergence result using a contradiction
'The statement is informal because points, which only implies local smoothness near the neighborhood of each iterate point (see Section (5.2). However, the standard smoothness condition is stronger global condition which assumes bounded Hessian at every point within convex set.
can only show bounded gradients Hessians at iterate

---

argument. Before introducing the contradiction argument, we first need to provide the following useful lemma, which is the reverse direction of generalized Folyak-Lojasiern (PL) inequality. whose proof is deferred in Appendix D33
Lemma 5.1. Under Assumptions
and
we have [V[())] 5 +47, (V/0))))))00))))))))000))))
Define the function ((u) (2, over u 2 0. is easy to verify that if p < Ç is increasing and its range is oo). Therefore, Ç is invertible and (-1 is also increasing. Then, for any constant G > 0, denoting F ((G), Lemma 5.1 suggests that fxx - f S F, we have
|V)(')] s ()(()) 1*) S (F)
In other words, if < 2, the gradient is bounded within any sub-level set, even though the sub-level set could be unbounded. Then, let T be the first time the sub-optimality gap is strictly greater than F, truncated at T + 1, or formally,
T = min(t ("
(3)
Then at least when & < T, we have f(x)) f² < F and thus [[V](=)]] < G. Based on our discussions above, it not hard analyze the updates before time т, and one can contruct some Lyapunov function to obtain an upper bound on -(x,,) - On the other hand, if r S T, we immediately obtain lower bound on f(z)), that f( F. by the definition of r in (3). If the lower bound is greater than the upper bound, it leads to a contradiction, which shows T = + 1. i... the sub-optimality gap and the gradient norm are always bounded by F and G respectively before the algorithm terminates. We will illustrate the technique in more details in the simple deterministic we introduce several prerequisite lemmas on the
setting Section [5.3] but first, in Section 5.2 (p, Lo, Lp) smoothness.
5.2 Local smoothness
informally mentioned that (p. Lo. Lp) smoothness essentially reduces to the standard smoothness if the gradient is bounded. In this section, we will make the statement more precise. First, note that Lemma 3.4 implies the following useful corollary.
In Section 5.1
Corollary 5.2. Under Assumptions and 2 for any G > 0 and two points & E dom(s), y E IRd
such that [[x]l S G and 1yy - æl1 S r = min 5L,Gr-T, 6(Lg 6(Lg-LL,P }. denoling = 3Lg + GL, we have y E dJo(() and
(v) -
- ff(()]l = fly - x1, f(y) S f(x) + (Vf(x). - -x)
2 11 x1
The proof of Corollary 5.2 is deferred Appendix [D.] Although the inequalities in Corollary 5.2 look very similar to the standard global smoothness condition with constant L, it is still a local condition as requires | y/l S r. Fortunately, at least before т, such a requirement is easy to satisfy for small enough 17, according to the following lemma whose proof is deferred in Appendix E.5
Lemma 5.3. Under Assumption 3 if < T and choosing G 2 a, we have || - xz S 1/D where D = 2G/2.
Then as long as 7) S Sr/D, we have | - xx, S which satisfies the requirement in Corollary 5.2 Then we can apply the inequalities in it in the same way as the standard smoothness condition. In other words, most classical inequalities derived for standard smooth functions also apply to (p, Lo. Lp) smooth functions.
5.3 Warm-up: analysis in the deterministic setting
In this section, we consider the simpler deterministic setting where the stochastic gradient V V.(zz, Ee)
in Algorithm or (18) is replaced with the exact gradient V As discussed in Section 5.1 the key in contradiction argument is to obtain both upper and lower bounds f(x-) f In the following derivations, we focus on illustrating the main idea of our analysis technique and ignore minor proof details. In addition, all of them are under Assumptions
2 and
In order to obtain the upper bound, we need the following two lemmas. First, denoting e, = m fz(x), we can obtain the following informal descent lemma for deterministic Adam.
7

---

Lemma 5.4 (Descent lemma, informal). For any t < T, choosing G 2 X and small enough
(( ((x)
" AG
[[(())]|
7 2A ||el1
where " omits less importani terms.
Compared with the standard descent lemma for gradient descent, there is additional term of ||e/]] in Lemma 5.4 the next lemma, we bound this term recursively.
Lemma 5.5 (Informal). Choosing 3 = @(nGe+1/2) ift < т, we have
X
||e2+1 1| s 3/4) ||e||
V [Vx))]
16G
The proof sketches of the above two lemmas deferred in Appendix f"
Now combine them to
get the upper bound on f(xx)) -". Define the function &. =- [(x)) any <
22
||ea|] 1e. Note that for
A8
2m
5
gives
P+t1 0
[V((,))]
8G
The above inequality shows o, is non-increasing and thus Lyapunov function. Therefore, have
f(x,) - ff S 4, < 11 = -1 where in the last inequality we use 41 = f(x1) - f =1 since E1 mi (f(x)) 0 in the deterministic setting.
As discussed in Section 5.1 if 7 S T, we have F f(xx)) S A1. Note that able to
choose a large enough constant G so that F 313to+4hp6 greater than A,, which leads to contradiction and shows 7 = T' + 1. Therefore, over < T' and re-arranging terms, we get
(6) holds for all 1 < t < T. Taking summation
[Vf(2)) 8G( DT+1) T
1
8GA1 T/T
<e?
choosing T 2 SGA1 i.c., it shows convergence with a gradient complexity of O since both 1je²
G and 1) are constants independent of c in the deterministic setting.
5.4 Extension to the stochastic setting
In this part, we briefly introduce how to extend the analysis to the more challenging stochastic setting. becomes harder to obtain an upper bound on f(x+) f" because 4 is no longer non-increasing due to the existence of noise. In addition, defined in is now random variable. Note that all the derivations, such as Lemmas and [5.] are conditioned on the random event < т. Therefore, one can not simply take a total expectation of them to show E[D.]] is non-increasing.
Fortunately, T in fact stopping time with nice properties. the noise is almost surely bounded as in Assumption 3 by more careful analysis, we can obtain a high probability upper bound on fx+)) - f using concentration inequalities. Then we can still obtain contradiction and convergence under this high probability event. If the noise has aah-Gaussian norm as in Assumption 4 one can change the definition of to
min(t f(x)) f F) A min(t (xx)) V f (z., &il > of (T+
for appropriately chosen and a. Then at least when t < т, the noise bounded by a.. Hence we get the same upper bound f(x,) f as if Assumption ( still holds. However, when t T. the lower bound f(z,) f > does not necessarily holds, which requires some more careful analyses. The details of the proofs are involved and we defer them in Appendix
Variance-reduced Adam
In this section, we propose variance-reduced version of Adam (VRAdam). This new algorithm depicted in Algorithm 2 Its main difference from the original Adam is that in the momentum update

---

rule (Line 6), an additional term of (1- 3) (V.( (.( is added, inspired by the STORM algorithm ( This term corrects the bias of m, so that is an unbiased estimate of fx;, in the sense of total expectation, i.e., [[[m+] = V (2x).. We will also show that it reduces the variance and accelerates the convergence.
Aside from the adaptive stepsize, one major difference between Algorithm 2 and STORM is that our hyper- parameters 7) and / fixed constants whereas theirs are decreasing as a function of t. Choosing constant hyper-parameters requires a more accurate estimate at the initialization. That is why we use mega-bated S to evaluate the gradient at the initial point to initialize my and t1 (Lines 2-3). In practice, one can also do a full-batch gradient evaluation at initialization. Note that there is no initialization bias for the momentum, so we do re-scale my and only re-scale 2t. We also want to point out that although the initial mega-batch gradient evaluation makes the algorithm bit harder to implement, constant nyper-parametent are usually easier to tune and more common in training deep neural networks. It should be not hard to extend our analysis to time-decreasing and B and we leave it as an interesting future work.
Algorithm 2 MARIANCE-REDUCHS ADAM (VRADAM)
1: Input: B, Peq. n, >, T, S1, Finit
2: Draw a batch of samples S₁ with size Si and use them to evaluate the gradient V (Xintt S.).
3: Initialize my
(Jinii,, 01 m. and 22
Tiit
me I
1781
4: for 2, ........ ,T do
5: Draw new sample &. and perform the following updates:
6: my = (1 3)m;-1 + 3V &x) 3) (VI(z,, - V (((
7:
Vt (1 Bu + Beg (V))
8:
0t 1- Pma
9: It+1
Jh- ① m
end for
In addition to Assumption 1 we need to impose the following assumptions which can be viewed as stronger versions of Assumptions 2 and respectively.
Assumption 5. The objective function f and the component function f(r+E) for each fixed are (p. Lo, Ip) smooth with S 2.
Assumption 6. The random variables (EthgieT are sampled i.i.d. from some distribution P such that for any E dom((f)
[V-r(V/(E,E)) (s))., [) Vs(x)]| a. a.s.
Remark 6.1. Assumption is stronger than Assumption 3 Assumption aappiio applies only the iterates generated by the algorithm, while Assumption 6 is pointwise assumption over all æ E dom(f) and further assumes an i.i.d. nature of the random variables {EthşıST. Also note that, similar to Adam, it is straightforward to generalize the assumption to noise with sub-Gaussian norm as in Assumption
6.1 Analysis
In this part, we briefly discuss challenges in the analysis of VRAdam. The detailed analysis is deferred in Appendix F Note that Corollary 5.2 requires bounded update || .t. S rr at each step. For Adam, it is easy satisfy for small enough r) according to Lemma [.3 However, for VRAdam, obtaining a good enough almost sure bound on the update is challenging even though the gradient noise is bounded. To bypass this difficulty, we directly impose a bound on f m; by changing the definition of the stopping time similar to how we deal with the sub-Gaussian noise condition for Adam. In particular, we define
T min ( G} min(t [z.) m,ll G) A (T++).
Then by definition, both [ and [[V[(xz) - m. are bounded by before time т, which directly implies bounded update || x= Of course, the new definition brings new challenges to lower bounding [xx f* which requires more careful analyses specific the VRAdam algorithm.
Please see Appendix F for the details.

---

6.2 Convergence guarantees for VRAdam
In the section, we provide our main results for convergence of VRAdam under Assumptions and We consider the same definitions of problem- -ebeeddddepenentt constants AI, L those in Section 4 make the statements of theorems concise. Let e be a small enough numerical constant and C be a large enough numerical constant. The formal convergence result is shown in the following theorem.
Theorem 6.2. Suppose Assumptions I and For any ô let G be constant
satisfying G 2 max { where a = 40Lv/G> 3/2, Choose
222,20 VCA1
Choose 0 S 9eq S 1 and 3 = a²m1²
X
X
X2
64GA1 nōe²
7 c- min
T
S 2 25²T
G
L'
A,L2'
oGL
Then with probability at least 1 6, we have [[
S G for every 1 S T. and
+ +E= [Vf(()) Se.
Note that the choice of G, the upper bound of gradients along the trajectory of VRAdam, is very similar to that in Theorem[4. for Adam. The only difference is that now it also depends on the failure probability 5. Similar to Theorem [.I] there is no requirement on Seq and we choose a very small (G²). However, the variance reduction technique allows us take larger stepsize rj O(e) (compared with Oc²²) for Adam) and obtain an accelerated gradient complexity of O(E )) where we only consider the leading term. We are not sure whether optimal as the Q 3) lower bound in 3 assumes the weaker bounded variance condition. However, our result significantly improves upon 47 which considers a variance-reduced version of Adam by combining Adam and SVRG [22) and only obtains asymptotic convergence in the non-convex setting. Similar to Adam, our gradient complexity for VRAdam is dimension free but its dependence on À is O(A 2) Another limitation is that, the dependence on the failure probability 8 is polynomial, worse than the poly-log dependence
in Theorem for Adam.
7 Conclusion and future works
In this paper, proved the convergence of Adam and its variance-reduced version under less restrictive assumptions compared to those in the existing literature. We considered a generalized non- uniform smoothness condition, according to which the Hessian norm is bounded by sub-quadratic function of the gradient norm almost everywhere. Instead of assuming the Lipschitzness of the objective function as in existing analyses of Adam, we use new contradiction argument to prove that gradients are bounded by a constant along the optimization trajectory. There are several interesting future directions that one could pursue following this work.
Relaxation of the bounded noise assumption. Our analysis relics on the assumption of bounded noise noise with sub-Gaussian norm. However, the existing lower bounds in [3] consider the weaker bounded variance assumption. Hence, it is not clear whether the ((c O(c-4) complexity we obtain for Adam is tight in this setting. It will be interesting to see whether to the bounded variance setting. One may gain some insights from recent papers such as [16] 46] that analyze AdaGrad under weak noise conditions. An alternative way show the tightness of the O( complexity is to prove lower bound under the bounded noise assumption.
can relax the assumption
Potential applications of our technique. Another interesting future direction is to see if the techniques developed in this work for bounding gradients (including those in the the concurrent work (26)) can be generalized to improve the convergence results for other optimization problems and algorithms. We believe it is possible so long as the function class is well behaved and the algorithm is efficient enough so that fIr)) f can be well bounded for some appropriately defined stopping time T.
Understanding why Adam is better than SGD. We want to note that our results can not explain why Adam better than SGD for training transformers, because (26] shows that non-adaptive SGD converges with the same O(e -1) gradient complexity under even weaker conditions. It would be interesting and impactful if one can find a reasonable setting (function class, gradient oracle, etc)
under which Adam or other adaptive methods provably outperform SGD.
10

---

Acknowledgments
This work was supported. in part, by the MIT-IBM Watson AI Lab and ONR Grants N00014-20-1 2394 and N00014-23-1-2299. We also acknowledge support from DOE under grant DE-SC0022199, and NSF through awards DMSS2031882 and DMSS1953182
References
[1] Kwangjun Ahn, Xiang Cheng. Minhak Song. Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). arXiv preprint arXiv:2310.01082, 2023.
[2] Zeyuan Alh and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707. PMLR, 2016.
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199
11-2):165-214, 2023.
[4] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger. T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Rad- ford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. ArXiv, abs/2005. 14166, 2020.
[5] Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu. Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration. The Journal of Machine Learning Research, 23(1):00411-1445,, 2022.
[6] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of udam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808. 02941, 2018.
[7] Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smoodt nonconvex opti- mization is as efficient smooth nonconvex optimization. arXiv preprint arX1v:2303.02854, 2023.
[8] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35:9955-9999 9963,996,22222 2022.
[9] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. ArXiv, ahs/1995.10018. 2019.
[10] 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: Learning, 2018
[11] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradi- ent method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
[12] Alexandre D' D'efossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv: Machine Learning, 2020.
[13] Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. ArXiv, abs/1810.04805, 2019.
[14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 1 16x16 words: Transformers for image recognition at scale. ArXiv, ab9/2010.11929, 2020.

---

[15] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
[16] Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pages 313-355. PMLR, 2022.
[17] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.06570, 2023.
[18] Sébastien Gadat and Ioana Gavra. Asymptotic study of stochastic adaptive algorithms in
non-convex landscape. The Journal of Machine Learning Research, 23()):0037-10411, 2022.
[19] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. ArXiv, abs/21 12.03459, 2021.
[20] Hideaki liduka. Theoretical analysis of adam using hyperparameters close to one without lipschitz smoothness. Numerical Algorithms, pages 1-39, 2023.
[21] Phillip Isola, Yan Zhu, Tinghui Zhou, and Alexei A. Efros. Image-to- to-image translation with conditional adversarial networks. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5967-5976, 2016.
[22] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.
[23] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2014.
[24] Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint arXiv: 13960, 2023.
[25] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via sesg methods. Advances Neural Information Processing Systems, 30, 2017.
[26] Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaic, Convex and non-convex optimization under generalized smoothness. arXiv preprint arXiv:2306.0123 012644 2023.
[27] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International conference on machine learning. pages 6286-6295, PMLR, 2021.
[28] Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. CORR, abs/1509 509.02971, 2015.
[29] Deyi Liu, Lam M Nguyen, and Quoe Tran-Dinh. An optimal hybrid variance-reduced algorithm for stochastic composite nonconvex optimization. arXiv preprint arXiv:2008. 09055, 2020.
[30] Zijian Liu, Perry Dong, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal high- probability convergence for non-convex stochastic optimization with variance reduction. arXiv preprint 2.X.::2302200032.. 2023.
[31] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. ArXiv, abs/ 09049902209 2019.
[32] Julien Mairal. Optimization with first-order surrogate functions. In International Conference on Machine Learning, pages 783-791. PMLR, 2013.
[33] Volodymyr Mnih, Adrià Puigdomênech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lill- icrap, Tim Harley, David Silver, and Koray Kavukeuoglu. Asynchronous methods for deep reinforcement learning, ArXiv, abs/1602.01188,, 2016.
12

---

[34] Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelligence and Statistics, 2021.
[35] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. CORR, atbs/1511.06444 2015.
[36] Sashank J. Reddi, Ahmed Hefny,, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic vari- ance reduction for nonconvex optimization. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pages 314-323, New York, New York, USA, 20-22 Jun 2016. PMLR. URL httLihtps://// htttps://procceddnggg mlr. ppwss///8/redaiiii.ee .hmml
[37] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ArXiv, abs/ (tos/1944.09237, 2018.
[38] Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprini wrXiv:2303.008833 2023.
[39] Nicolas Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with expo- nential convergence .rate for finite training sets. F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012. URL httptt/t///prrcceeeinga.s www. wwtpcc/pppppp...ccc seaaperffllespppppppea hhtp://22000666ccaaaaaa446666662
[40] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/ abbs/1777003344 2017.
[41] Shai Shalev-Shee Sawlar-Shwwrtz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1), 2013.
[42] Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper-parameter. In International Conference on Learning Representutions, 2021.
[43] Quoe Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv: 2019.
[44] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. ArXiv, abs/1706.03762, 2017.
[45] Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhirui Ma, Tie- Yan Liu, and Wei Chen. Provable adaptivity in adam. ArXiv, 2wwp/2208.09900. 2022.
[46] Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pages 161-190. PMLR, 2023.
[47] Ruiqi Wang and Diego Klabjan. Divergence results and convergence of a variance reduced version of adam. ArXiv, abs/2210.05607, 2022.
[48] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511- 15521, 2020.
[49] J. Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv: Optimization and Control, 2019.
[50] Jingzhao Zhang, Sai Pranceth Karimireddy, Andreas Veit, Scungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393, 2020.
[51] Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhimin Luo. Adam can converge without any modification on update rules. ArXiv,
2022.
13

---

[52] Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64, 2021.
[53] Dongruo Zhou, Jinghui Chen, Yuan Cao. Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 10X1: 2018.
[54] Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. ArXiv, abs/18104 11000144,, 2018.
[55] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A. Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. 2017 IEEE International Conference on Computer Vision (ICCV), pages 2242-22222222222 ,
[56) Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of adam and rmsprop. 2019 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 11119-11127, 2018.
14

---

A Additional related work
In this section, we discuss additional related work on variants of Adam and variance reduction methods.
Variants of Adam. After Reddi et al. 37 pointed out the non-convergence issue with Adam, various variants of Adam that can be proved to converge were proposed [56]
31
For example, AMSGrad [37 and AdaFom [6 modify the second order momentum so that it is non-decreasing. AdaBound [3 explicitly imposes upper and lower bounds on the second order momentum so that the stepsize is also bounded. AdaShift [54] uses new estimate of the second order momentum to correct the bias. There are also some works (53 18 20 that provide convergence
guarantees of these variants. One closely related work to ours is 47 which considers variance-
reduced version of Adam by combining Adam and SVRG [2] However, they assume bounded
gradients and can only get asymptotic convergence in the non-convex setting.
Variance reduction methods. The technique of variance reduction was introduced to accelerate convex optimization in the finite-sum setting [39 [2] 41 32] [T. Later, many works studied
variance-reduced methods in the non-convex setting and obtained improved convergence rates for standard smooth functions. For example, SVRG and SCSG improve the O(c-²) gradient
complexity of stochastic gradient descent (SGD) to O(c [2] 36 [5]. Many new variance reduction methods [1]] 43 29 27:
9 30 were later proposed to further improve the complexity to Ole ())=), which is optimal and matches the lower bound 3 Recently, [38 obtained the
(e complexity for the more general (Lo, L1) smooth functions. Our variance-reduced Adam motivated by the STORM algorithm proposed by [9), where an additional term is added in momentum update correct the bias and reduce the variance.
B Proof sketches of informal lemmas in Section 5.3
In this section, provide the proof sketches of the informal lemmas in Section 5.3 illustrating the ideas rather than rigorous proof details. Please see Appendix for more rigorous and detailed proofs of Adam in the stochastic setting.
We focus
Proof Sketch of Lemma 5.4 By the definition of 7, for all t < т, we have ((z f < F which implies
V
(xx) G. Then from the update rule (18) in Proposition E. provided later in
Appendix E
it is easy to verify ú, < G since ú; is a convex combination of [(V (xx))) " Let
hy = /
A) be the stepsize vector and denote H₃ == diag(he). We know
1 G HI 1
As discussed in Section 5.2 when 7j small enough, we can apply Corollary 5.2 to obtain
f(x+11) - f(xz) ~ (vf(zz) x++1 - =1)
vs(x)) Hiee
1
1
< 2
| (xx))
H. + ||eal1
7 [VV
+ 2X 1|
7
4G
where in the first (approximate) inequality ignore the second order term _ | 12 1/2 in Corollary 5.2 for small enough 7); the equality applies the update rule F++1 24 = H,m, =
- (Vf(() + e); in the second inequality we use 2a Ab < ||a] + ||b]]3 for any PSD matrix A
and vectors a and 6; and the last inequality is due to
Proof Sketch of Lemma 5.3
By the update rule (8 in Proposition E. we have
4+1 = (1 - a.+1) (4 + fz( - - f((44)))
(8)
15

---

For small enough 7) we can apply Corollary 5.2 to get
(V < |1141-111
2 +leaal1)
(9)
where the second inequality is due to = O(G)) and | zt1l = (n) || ||: and the last inequality uses vi, V)(x)) - e, and Young's inequality ||a + bll < ||a|| + 2 |6] Therefore,
|4+1|| <(1 0++1) m2+1/2) 1a1l2 + (1 + 2/a4+1) (++++) V fxx))l <(1 02+1 ||, (1)"(((()))))0 /os+1) (IV +
||ea|) ||alll))
AB
<(1 B/4) ||e||
16G
where the first inequality uses (8) and Young's s inequality ||a + b12 1 (1+ ||a|] (1 111+1/u/ 1/u) |1b12
for any > the second inequality uses (1 - 044 (1 0/+1 /2) - 12 and (9: and in the
last inequality we use 3 0++11 and choose ((1Ge+1/2) which implies 011 G2o /a441) S
Xa 2 3/4.
T6G
C Probabilistic lemmas
In this section, we state several well-known and useful probabilistic lemmas without proof. Lemma C.1 Soeffi-Ho inequality). Let (74)21 be a martingale with respect to a filtration (Fi)220 Assume that 1/= Z4-1/ S Ct almost surely for all t 2 O. Then for any fixed T, with probability at least - 8,
T
ZT Zo S
Σ
c log(1/8).
Lemma C.2 (Optional Stopping Theorem). Let (Ze)221 be a martingale with respect to a filtration (Fi 120- Let be bounded stopping time with respect to the same filtration. Then we have BiZ, = ZZoo.
D Proofs related to (p, Lo, Lp) smoothness
In this section, provide proof's related to Lo, smoothness. In what follows, first provide a formal proposition in Appendix D.II showing that univariate rational functions and double exponential functions (p, Lo, Lp) smooth with 2, as we claimed in Section 3.2. and then provide the proofs of Lemma 3.4 Lemma 5.1 and Corollary [.22 in Appendix D.2 respectively.
D.3 and D.4
D.1 Examples
Proposition D.1. Any univariate rational function P(z)/Q(x), where P,Q Q are two polynomials, and any double exponential function (,)", where a, are (p, Lo, Lp) smooth with < However, they are not necessarily (Lo, L2) smooth.
Proof of Proposition D.1 We prove the proposition in the following four parts:
Univariate rational functions are (p, Lo, Lp) smooth with < < 2. Let /(x) P(x)/((a) where P and Q are two polynomials. Then the partial fractional decomposition of f(z) is given by
Air 0;)"
B Car
-
4 bir + c:)"
where u=(x)) polynomial, Air, Bir, Cir, ai bi, e are real constants satisfying 13 44; each 1 5 i < n which implics z b,x C₁ 0 for all R. Assume Aij. * 0 without loss of
4c; < 0 for
16

---

generality, Then we know f has only finite singular points fa: and has continuous first and second order derivatives at all other points. To simplify notation, denote
Air
B + Cir
(ir (x ar)
(rr(z) (22 + +6,0 + c.)"
Then we have f(x w(x) + > ii= E Par (z) + - Ex (z) For any 3/2 < < 2, we
know that p r+2 for any 2 1. Then we can show that
r+I
[[((')" 3- [f((x]
Ply, (2) 30, (()((a)
lim
lim 2-;
(10)
where the first equality is because one can easily verify that the first and second order derivatives
of Pij. dominate those of all other terms when x goes to ag, and the second equality is because
Ply, (2) O ((x - a,) -))=+(+++)) Ip") (x)] = O ((x a.) 21++2)) and p(j: + 1) > ji + 2 (here
we assume 2 1 since otherwise there is no need to prove (O)) for i). Note that (T0) implies that,
for any Lp > 0, there exists 6, > such that
[f"(x)) S (x)'' if -- a,l < 6; |(x)]
(11)
Similarly, one can show lim
[f(()) oc, which implies there exists M > 0 such that
[x) < (x) if | M.
(12)
Define
B [= |2| S M and I - a 2 84 ViJ.
We know B is compact set and therefore the continuous function f bounded within B, i... there exists some constant Lo > 0 such that
[/(x)) S Lo, E
(13)
Combining
and
we have shown
[x)( $ Lu + (f))' Vo E dom(f),
which completes the proof of the first part.
2. Rational functions not necessarily (Ln, I1) smooth. Consider the ration function f(x)
1 1/2. Then we know that f((x) = -1/x² and f"(x) = 2/x². Note that for any < x S
min + 1) 1/3 (L1 + 1)- we have
If" = x3 1f(x))) > Lu + L (f(x))
which shows f is not (Lo, L1) smooth for any Lo, L1 20. 0.
3. Double exponential functions are (p. Lo. Lp)) smooth with < < Let f(x) = (tt), where
a, b > 1, be a double exponential function. Then we know that
f((x) = log(a) log(b) (0") f"(x) = (l (2)).
For any p > 1, we have
lim ['((')) lim 18
lim (log(a) (og())) 1 ((p-1)v 1)y
[f"()] +oo (log))()
+00000
log(b)(log(e)) (ay + +1
00;
where the first equality is direct calculation; the second equality uses change of variable y 6"; and the last equality is because exponential function grows faster than linear function. Then we complete the proof following a similar argument that in Part
4. Double exponential functions are not necessarily (Lo, L1) smooth. Consider the double exponential function f(x) = e(c"), Then we have
f((x) = ee()", f"(x)= - (e" 11) (6))
For any x 2 max LLog(Lo Lo 1), log(L) + +1), we can show that
15" (L1 1)f (x) Lo In (x)),
which shows f is not (Lo, L1) smooth for any Lo. L1 0.
17

---

D.2 Proof of Lemma 3.4
Before proving Lemma 3.4 we need the following lemma that generalizes (a special case of)
Grönwall's 's inequality.
Lemma D.2. Let u: la, bj + [0, oo) and : [0, xc) - (0, 2o) be two continuous functions. Suppose
u' (t) S ((u(t)) for all E (a. b). Denote fumetion <(w) == S B(w) dw. We have for all t [a.b].
o(u(t)) S <(u(a)) - a +
Proof of Lemma D.2 First, by definition, we know that Φ is increasing since ø' = > 0. Let function be the solution of the following differential equation
(t) = f(v(t)) Vt E (a, b), v(a)= = u(a).
(14)
It is straightforward to verify that the solution (4 satisfies
((v(t)) - t <(u(a)) - a.
Then it suffices to show <(u(t)) s (()(t)) A bl. Note that
vt) v'(t)
(o(u(t))
= d'((()) d' o' d'(u(t))
((((t) [(((t)) 00
where the inequality is because (1) S {(u(t)) by the assumption of this lemma and v'(1) {(v(())
by (14). Since d(u(a)) <(v(a)) 0, we know for all E [a, 6]. o(u(t)) s d(v(t)).
With Lemma D.2 one can bound the gradient norm within a small enough neighborhood of a given point as in the following lemma.
Lemma D.3. Suppose f is (p, Lo, Lp) smooth for some Lo, Lp 2 O. For any a > 0 and points y dfm(f) satisfying |yy x|| S Tooth,(1V//())00000 we have
|V < [Vf())++
Denote functions z(t) == (1 (1-t)a t)r + and u(t) = [V] for st$1. 1. Note that for any 0 < t s < 1, by triangle incquality,
Proof of Lemma D.3
u(s) utt s [Vf{((()) (=)((t)
We know that u(t)= have
|| f (= (=))] is differentiable since second order differentiable Then we
u(s) - u(()
VV(((s)) - - lim ([((s)))V[(((0))
(1) = lim
< lim ait
aie
8
8-t
8-t
< 2 (=((t) |1 - x1| < (Lo + (pu(t)p) |1y - =x||.
Let ((w)= = J0 [1=+1,""]<~= dv. By Lemma D.2 we know that
$ ((V] = (1((1)) s ((n(O)) + = & (IVV(=))I + 1.
Denote ((w)= == fe w dp (ww) 11y - x|1. We have
(IVS(()I) AΦ (1) 11l x11
Lo [f((v)())) +a
vf(ii
1
[V
1
(To Iaper) du +
(To L du
[+V) +a)
Since &b is increasing, we have [Vf(y)] < [f(x))++a
Heee we assume u(t) > 0 for 0 < < 1. Otherwise, we can detine t... = sup <t<1 u(t)= 0) and consider the interval [tm, instead.
18

---

With Lemma D.3
we are ready to prove Lemma 3.4
Proof of Lemma 3.4 Denote 2(t) == (1 - t) + ty for some y E R satisfying ll æll I We first show y dom(f) by contradiction. Suppose y & dom(f), let us define la == i0 < x(t) $ ) and 2b == 2(t)). Then we know 2 is a boundary point of X. Since f is closed function with open domain, we have
lim f(((t)) cc. rtt
(15)
On the other hand, by the definition of ba we know z(1) E X for every 0 < < b.. Then by Lemma D.3 for 0 S < ln we have [[((( S [[V[())] + a. Therefore for all 0 S t lb
[(=(()) + + / (V](=(>)), - 2)) ds
<f(x) + (I]] + +a) 1l xll <00,
which contradicts with 15
Therefore we have shown E dom(s). We have
V/(x)) = / {²I(((1)) (y - x) di
\V(0)
$ 1ly - z|| ( (Lo + L, [V dt
< < - x|| (Lo + Lp (IIV/(()) + +a)
where the last inequality is due Lemma D33
D.3
Proof of Lemma
Proof of Lemma 5.7
Denote G := |V](()] and L == 3Lo + Go, Let y = x - 2 Vf(x).
Then we have
6Lo + G S min 5L,,Ge-I. 5(L6 (p) =
2T.
where the inequality can be easily verified considering both cases of G (Lo/ and G > (Lo/ Me, Then based on Corollary 5.2 we have y E dom(f) and
3LG² LG
f - (xx < f(v) f(x) < V)(c),
+ = lly x 2
<
2
8
3
which completes the proof.
D.4 Proof of Corollary 5.2
Proof of Corollary
5.2 First, Lemma 3.4 states that for any a 0,
|y æ|| < Lo
|V VV/=) (
((V/]) (IV/(z)]+a)))
|/ æ||
Then is straightforward verify that If | < G. we choose a max (Lo/
1
To + I.p (IV](())] + a) 2 min 5L, 5(I6-1I,))) 1/0
=r
Lp (IV + a) < 3l0 4L =: L.
Therefore we have shown for any I, y satisfying |y z|| Sr,
[Vf(v) fx))) < L 1ly x:|
(16)
19

---

Next, let a(t) = (1 10-ttx=+a t.x 0 sts 1. We know
f()) - / (Vf(z(t), - z) dt
(Vf(o).v - 2) + (V)(2(t)) - Vf(x), - 2) dt
<Vff(2), da + / L||x(t) x|| lly -x dt
(Vf(x), 1) + L y1y x1| f dt
(Vf(z). 2) + L 11y - x 2|?
where the inequality due to (16
E
Convergence analysis of Adam
In this section, we provide detailed convergence analysis of Adam. We will focus on proving Theorem 4.1 under the bounded noise assumption (Assumption 3 in most parts of this section except Appendix E.6 where we will show how to generalize the results to noise with auh-Gaussian norm (Assumption and provide the proof of Theorem 4.2
For completeness, we repeat some important technical definitions here. First, define
m fz(
(17)
as the deviation of the re-scaled momentum from the actual gradient. Given a large enough constant G defined in Theorem 4.1 denoting F
GF, we formally define the stopping time 7
G2
min f(x)) ff (}+
iee. r is the first time when the sub- sub-optimality gap is strictly greater than F, truncated at T + 1 to make sure it bounded in order apply Lemma C.2 Based on Lemma 5.1 and the discussions below it, we know that if f < we have both fa,) <
V fz, that r a stopping time with respect to (Er)22 because the event { 2 1) is function of {Ex)sce and independent of f52. Next, let
F and
G. It is clear to see
h
be the stepsize vector and H, diag(h:) be the diagonal stepsize matrix. Then the update rule can be written as
T141 = Ht - h1 O me = xt - Ham..
Finally, as in Corollary 5.2 and Lemma 5.3 we define the following constants.
min
5L,
5(T S(T--11,,)11 8
L 3Lo + OL
D = 2G/A.
E.1 Equivalent update rule of Adam
The bias correction steps in Lines 7-8 make Algorithm I bit complicated. In the following proposition, we provide an equivalent yet simpler update rule Adam.
IIndeed, 1 is also stopping time because V (x(x)) only depends on fE-hase but that is unnecessary for analysis.
20

---

Proposition E.1. Denote at 1-(1- and at
Bug -m
Then the update rule in Algoritim /
equivalent to
mr (1 - ai ( 04 az
6 (1 ai (1)
0 13 (V)
(18)
7
2(+1 2t
m
vū= + X
where initially we set m. = Vz(11 (1) and i1 = (Vf(21, Note that since 1-a1 = 11-aj there is need to define mg and Bo.
Proof of Proposition E.
Denote Z; = -1 - By Then we know a; = 3/7z and my Zen
By the momentum update rule Algorithm | we have
Zi = (1 - -) (V
Note that Z, satisfies the following property
(1 3) = - (1-B)² = Zt 3.
Then we have
7, -3
B
mh
-m4-1
Zz
Z
=(1 0i ( O4 (x),
Next, we verify the initial condition. By Algorithm I since we set mo = 0. we have mi
3V (i), Therefore we have m = m1/21 V((11()) since Zi B. Then the proof is completed by applying the same analysis and 0z.
E.2
Useful lemmas for Adam
In this section, we list several useful lemmas for the convergence analysis. Their proofs are all deferred in Appendix E.5)
First note that when & T, all the quantities in the algorithm well bounded. In particular, we have the following lemma.
Lemma E.2. 1ft T, we have
[V](=))) SG,
[V &t)l S SG |m.|| S G G+a+1 h4 x 7
(G+
Next, we provide a useful lemma regarding the time-dependent re-scaled momentum parameters in (88). Lemma E.3. Let at 1- then for all T 2 we have ΣT of 3 3TT).
8
In the next lemma. we provide an almost sure bound on et in order apply Azuma-Hoefdding inequality (Lemma C.I.
V/(x-11) vs(x;)). Choosing rj S min { D DE S
Lemma E.4. Denote 7h-1 (1 ift S T, we have |cell < 2a and 1 20.
Finally, the following lemma hides messy calculations and will be useful in the contradiction argument.
Lemma E.S. Denote
1 4,d + 802 (7
8G
(7+ n 22002 +T7)
FGF
8G3
L =
3nL
Under the parameter choices in either Theorem 4.1 Theorem
4.2
have 1 S l2 and L1TT < 2.
21

---

E.3
Proof of Theorem 4.1
Before proving the main theorems, several important lemmas are needed. First, we provide descent lemma for Adam.
Lemma E.6. Ift < T, choosing G 2 a + and S min
{D. A GL we have
((1+1)- - S 40
Vf(z,))
+ X ||,.11
Proof of Lemma E.6 By Lemma
E.2
we have if < T,
n
n
3 H. 3 171
(19)
2G
G+o+A
X
Since we choose 17 S 5- by Lemma
5.3
we have || - Jell S r if < T. Then we can apply
Corollary 5.2 to show that for any
L
(1(+1) - ((x)) < (VS(()) 041 - 02) + || - xell
I.
(Vf(x))) Heme +
2 m H2me
S / - (Vf(xz)) Hee + nL
2A | Ii.
2 [ + 3 1leellia. + nL x (IVI(=;)) + +leelle..)
S
3
1
< 2
[ + +|ceel1a.
S 4G [V/())) 1| X |eelll
where the second inequality uses
17 and 19 the third inequality is due to Young's inequality
T Ab S ||al/ + ||6]3 and ||a 612 S
||a|| + lbbll for any PSD matrix A; the second last
inequality uses v S A and the last inequality is due to 19
The following lemma bounds the sum of the error term ||l|| before the stopping time r. Since its proof is complicated, we defer it in Appendix E.4
Lemma E.7. IfG 2 2a and 1j S min D.
6LVG DL S. with probability
x3/28
A 8G
|4
80² (1/B(1114))) BT) 20o² + (T)
Combining Lemma E.6 and Lemma E.7 we obtain the following useful lemma, which simultaneously bounds f(x) - f and Σ [x
Lemma E.8. G 2 max(A, of and n S min { r x a8 } then with probability at least 1-8, 8,
D: BLVO DI.
80 [VS(E))11
-((xx))
"
8G
(3 4 nBT
S0?
Proof of Lemma
E.8
By telescoping, Lemma E.6 implies
8G 2 [[
X ||e < (f(zi) (f(zi)-f(x-) f(xx)) 84,G
8G
(20)
17
22

---

Lemma E.7 could be written as
8G | [V < X (80² (1/3+ (808 8T) + 20o² (11/2² + lo8(1/))
(21)
20
gives the desired result.
With Lemma E.8. we are ready to complete the contradiction argument and the convergence analysis. Below provide the proof of Theorem 4.1
Proof of Theorem 4.1 According to Lemma that conditioned on &, we have
E.8 there exists some event & with P(E) 2 1 - 5, such
8G 8G (f(x+) f*) v nn
A1d (
+ 802
[ + nBT)) (
+ "0002//(1/88) (o) log(1 =: 11.
"
(22)
By the definition of r, if T, we have
8G
8GF
8G
" ([(++)-
12
7
3nD
Based on Lemma E.S we have 1 < 12. which leads to contradiction. Therefore, must have T + conditioned on Then, Lemma also implies that under E,
4 Σ [V)(a))]
S
Se,
where the last inequality is due to Lemma
E.5
E.4 Proof of Lemma E.7
In order to prove Lemma E.7 we need the following several lemmas.
Lemma E.9. Denote Nh-1
a-)((11111 + Vf(xx-1) vf(xx)). IfG 2 2o and n S
x/22 )
min D 6LVE j. we have every 2 155T.
|er]] 2 $ (1
2
a1)
||o_1|| 11 +
AB 16G
vf(x,=)]| +aj0² + 2az 7--1 - -V(la))
Proof of Lemma
E.9
According to the update rule (88. we have
=1
ff(x)) + on (Vf((n)) vf(zz))
-/-- a. (V)(z,, -V((z.))))))(
(23)
Since we choose 7/ 5 5, by Lemma 5.3 we have - S r if 1 S т. Therefore by
Corollary 5.2 for any 2 < SS T,
n n (IV] (10-1))), (24)
||V[(==11) -/(xx)] I|at x-1
|
X
X
Therefore
1h = + (1-a)) - -
<(1 s11=2,)² (1 + a.) | 2 - a1) (1+ 1
a.
1
5(1 (1)) |||- || +
[[ {((x))1
0n.
2n L2
<(1 ar)
||r 1|
))[ + ||e--1 113)
X23
< (1 0t
||4-1|1
X3
[
2
16G
23

---

where the first inequality uses Young's 's inequality |/a + 611² _ (1+ ||ll + (1 + 1/u) [bb] for any 0; the second inequality is due
(1 (1-xx)² (1 + ov)) = (1 1-= -a²) S (1 - a1),
(1 - (1-oa)² 1 1 1 - (1- a1-a))² 3 (1 + ax) - - (1 o4) S
1
0+
at
a2
19/2g 6LvG'
the third inequality uses
(24 and Young's inequality; and in the last inequality we choose 11 S
which implies
2n²²²²
S
A0
2. Then by (23). we have
16G
2
|cell = -110-111 201
2-11 Vf( vf(x)) of VV -
$ - 01)
2) ||ea_1||
AB
Vf(x+11)]1 + +aj0² + 200 7 Vf(on)(( - -V(le))
16G
Lemma E.10. Denote 7--1 =1 (1- (1-(a))--11-- + - If G 2 20 and n s a8 min B DL
j. with probability 1 -,
aar n- VI(),, Vf(x+) 1 /10 log(1/2 (1)))
1=2
Proof of Lemma E.10
First note that
Σ ai 1- Vf Ex) -V((z)
Vf( - V((a).
Since 7 is stopping time, we know that 1,26 is function of (Ex)ace Also, by definition, we know T--1 is a function (Es) Then, denoting
X, = 17-11120 Vf(x,, Ex) Vf(a)).
we know that E, [,] = 0, which implies {ST is a martingale difference sequence. Also, by Assumption 3 and Lemma E.4 we can show that for all 2 < TT,
[xel S 04a 1 S 20
Then by the Azuma-Hogfiding inequality (Lemma C.I we have with probability at least 1 - 8,
Σ X,
< 20
2
of log(1/8) s 502 v B2T) log(1/8),
t=2
where in the last inequality we use Lemma
Then we are ready to prove Lemma
E.7
Proof of Lemmal
E.
By Lemma
E.9 we have for every 2 < SSSTT
B
4
2
at
|
< 111--1112 ||<.
+ 16G
A3
| [ (x+ + afo0
2
2
+ +aa 7-11. Vf(x,, vf(xi)
Taking a summation over from T, we have
A3
||--112
16G [[(a=))]]]
< ||eIl| - || + 0²
Σ t=2
2 + 10o² (1+ log(1/8)
2
<4o2 + B2T) + 10o²
v(++ (o))
where the first inequality uses Lemma E. and the second inequality uses Lemma E.3 and ||
[ vf(x1)]l < o². Then complete the proof by multiplying both sides by 2/8. 0
24

---

E,5
Omitted proof' for Adam
In this section, we provide all the omitted proofs for Adam including those of Lemma 5.3 and all the lemmas in Appendix E.2
Proof of Lemma
5.3
According to Lemma
E.2 if < T,
" || xell S x | S
n/G +
2g/
A
Proof of Lemma E.2 By definition of 7, we have [=+() G T. Then Assumption
directly implies
Vf {x]l < G + a. || can be bounded by a standard induction argument as
follows. First note that [ia [ S G Supposing || S G for some k < T, then we have
| $ (1 (+)) | + os ( &a)l S SGoa.
Then we can show 6 I (G + x²² in similar way noting that (Vf(z,, (1)² = &V)( (G + o)?. Given the bound on é is straight forward to bound the stepsize h4
Proof of Lemma E.3 First, when & 2 1/3, we have (1 -)) - 1/e. Therefore,
Σ 1/8SIST
(1- $ (1 1/e) 2T 3T.
Next, note that when 1/3, we have (1 -3- S
St.
Then we have
Σ -1-(1 (1-(1-3)1) <
4
Σ
3
5
32
251<1/3
122
Therefore we have Et= of s 3(1 + B3T)..
Proof of Lemma E.4 We prove ||e/|| S 20 for all < by induction. First, note that for = 1, we
have
|al = [Vf fz1))) < < 2o.
Now suppose ||e-- < 2a for some 2 < / 5 According to the update rule 18 we have
E =(1
( (V ff())),
which implies
vf(x;)]]- ||l|| s (2-aa) a1) + [
Since we choose 7, < 5. by Lemma 5.3 we have || x1-1 < n/D < rrift < Therefore by
Corollary 5.2 we have for any < T.
[V)(z)) v f( I|l < L |0, z,-ill SnDL oat
where the last inequality uses the choice completes the induction. Then it is straight forward to show
and / I ag Therefore we have |eall S 2a which
|| & (1 - ar)) (2o + (g0) S 2x.
Proof of Lemma
E.5 We first list all the related parameter choices below for convenience.
{1, ad
G 2 max
22, 20, / C, (CAAL
B min
PGVlS'
rA aYB 13/2
(1
C2G
5 02 min
T max
G LGVi' WG
g2
ne²
25

---

We will show 1 S 1 first. Note that if denoting W
32 XG
we have
1/12- W ( n3T)) + 20W V (1R//32 + TTT),,
Below are some facts that can be easily verified given the parameter choices.
(a) By the choice of G, we have G² 2 (L + 44, = 6 for large enough C₁ which implies W S 2A,7'
(b) By the choice of T, we have n/T's < B + 6²
(c) By the choice of I', we have r² = max (3)
Candi
(3) )3)² + <
C.A
3 5
CoAyog 2
(d) By the choice of 7, we have n/3 z small enough cg.
caa LGVE"
which implies Wo² Vi
2
3c G
I
for
B
200
(c) By the choice of 3 and (a), we have WoRA
0²G 2Ac
for small enough e₁.
6²
100C₂
Therefore,
CA4GGB 1/12 S + +WW2
1 2m
5n72
C2A1013
+
20W
(V
+
2
2,32
2
62
1 4 V1. +
2CC:W0A
8
2
11,
where the first inequality is due to Facts (a-c); the second inequality uses S G, 2 1, and va+bs vā + vb for b 2 0; and the last inequality is due to Facts (d-e).
Next, we will show 4/T S e2. We have
8GA,
64o2G
640²GB A
+ 1600
1
1/T
1/T
A3T
BTT T
8
224
64o2GB
1600
C2
A3T
AVT
8ea
450g GVBB
C2
A
450cl
2
C2
<2.
where in the first inequality we use 2 CeSر and Va+bs Va+ Vb for a, 2 0; the second inequality uses T ; the second equality uses the parameter choice of 3; and in the last inequality choose large enough C2 and small enough c1.
E.6 Proof of Theorem
Proof of Theurem
4.2
We define stopping time 7 as follows
=min( f(x)) - f F) AT
72 = min(! [[V[[|]/V[((x))) VS(2,, &i) > (T+1),
7 min(TI.72}
26

---

Then it is straightforward to verify that 71, 72: T are all stopping times.
Since want show P(rr S 7) is small, noting that {T <T) 1 U = ST). suffices to bound both (P( = 71 S T) and IP(T = T2 - T)-
First, we know that
( S1P(T T)
U [Vf( V
1SIST
P(IVf(I;) -//(E >0)
1TST
E B (1 vf(r., > >o)
ISST
E
2e 2R
ISIST
=27e 222
56/2,
where the fourth inequality uses Assumption and the last inequality uses /looog/4T// Next, if r = 5 T, by definition, we have f(x,) f > F, or equivalently,
8G (f(x+)
SGF SG
12.
7
7
3ryL
On the other hand, since for any < т, under the new definition of r, we still have
f(x)) - f F, [[ G, [V - (f Et) So. Then we know that Lemma E.8 still holds because all of its requirements are still satisfied, i.e., there exists some event & with P(E) S 8/2, such that under its complement 8
[+((2)) + 8G (f(x,) ( s n
8G
(3 3
A1A+ + 80²
n + 22000n (118++
I
E.5 we know I < I2, which suggests that 8d n fr Ti $ T) 0, i.e. fo T1 S T) E. Then we can show
By Lemma
P(EU(T S + P(7 12 S ST) S..
Therefore,
P( (f 2 - P(E P 7)) 2 - 5,
and under the event 8 n (f==== 1}. we have + = T + and
T Σ
< L/T & 2²
where the last inequality is due to Lemma E.5
F
Convergence analysis of VRAdam
In this section, we provide detailed convergence analysis of VRAdam and prove Theorem 6.2 To do that, we first provide some technical definitions] Denote
:= V (xx))
'Note that the same symbol for Adam and VRAdam may have different meanings.
27

---

as the deviation of the momentum from the actual gradient. From the update rule in Algorithm can write
we
4 (1- -111-) W
(25)
where we define
W₁ :-vV/ (z) Et) ((())) (1- 3) (VI(I+-1,,)) Vf((==-)).
Let G be the constant defined in Theorem 6.2 and denote F 313Lo+44,60P following stopping times as discussed in Section 6.1
G²
We define the
71 == min(t f(x)) f" > (T+++
min(t ||elll (T+)),
(26)
т = (in T2]
is straight forward to verify that T1, 72, are stopping times. Then if < т, have
f f F, [V[(z))] G, ||||| & G.
Then we can also bound the update | z1 S n where D = 2G/X if < T (see Lemma F33 for the details). Finally, we consider the same definition of and those for Adam. Specifically,
1
min
L == 3Lo 4L,
(27)
5L,
5(16-1 L,) f
F.1 Useful lemmas
We first list several useful lemmas in this section without proofs. Their proofs are deferred later in Appendix F3
To start with, we provide lemma on the local smoothness of each component function f(:E) when the gradient of the objective function f is bounded.
Lemma F.1. For any constant G 2 a and two points æ E dom(f). IRd such that [[V S G and [yy z|| S r/2, we have dom(f) (f) and
[V) - f((x)] s bly =||
[v)() - fzz E) < 4L 11 =|| AE. f(v) S f(x) (V/(z). =) -
where r and L are defined in 27
With the new definition of stopping time r in 26). all the quantities in Algorithm 2 are well bounded before 7. In particular, the following lemma holds.
Lemma F2. Ift < we have
[V)(z)) SG G. [V &i) SGo
||m|| s 2G,
i = (G+
" G+a+A h4 7
Next, we provide the following lemma which bounds the update at each step before 7.
Lemma F33. ift < || x S nD where D = 2G/X.
The following lemma bounds ||Wll when 6. T. Lemma E.4 Ift < r, G 20, and 1) S 2D'
|| < Bo + 5nL ([V]((,- + I|e.-
X
Finally, present some inequalities regarding the parameter choices, which will simplify the calculations later.
Lemma F.5. Under the parameter choices in Theorem 6.2
have
2A
XA13
3
AA
3/2 3
F
<
4'
G2
<
4'
nST
802
1) <
400 V
C
28

---

F.2 Proof of Theorem 6.2
Before proving the theorem, we will need to present several important lemmas. First, note that the descent lemma still holds for VRAdam.
Lemma F6. Ift T, choosing 2 a + X and n S min
I A J. we have
- S 4G [(+)a]| |1e.1l
Proof of Lemma F.6 The proof is essentially the same as that of Lemma E.6
Lemma F.7. Choose G 2 max {2o, 2A}, S 2 2 and 17 S min
27):
400
33/2
V
We have
E
A
|
S 202 - -
16G
Proof of Lemma F.7
By Lemma F.4
we have
||: $20²3² + 100g²
(IV + 11ee-111))
X²
A
<20² +
16G
where in the second inequality choose 1j S we have
3/22
40t V G- Therefore, noting that 16G
AB
S 3/2, by 25
||ee|12 =(1 110-,,)) :3)² 1|t--111 I1W11 (1 3) c--1. (.-,,W,
<(1 (11-8/2) 3(1- ||
16G [
A
202 3² + (1 B) c--1,
Taking a summation over 1.5 T and re-arranging the terms, we get
Σ
X6
|
[vf(z))1
||||| - ||, 202 +1 Σ ee,,
16G
1=1
Taking expectations on both sides, noting that
){
E
6-11. We
=0
by the Optional Stopping Theorem (Lemma C.2 we have
X3
E
|
vf(x,))1
< 20 20T Ell E[[le,11] ~ 402 - 1|]
16G
where in the second inequality we choose S 2 2Ø2T which implies [[]||]1/ < <0///
Lemma F88 Under the parameter choices in Theorem 6.2 we have
16GA, E[f(x+)
XA,3 Eiile 11
E
f7 2A1.
<
7
Proof of Lemma
First note that according to Lemma F5 it is straight forward to verify that the parameter choices in Theorem 6.2 satisfy the requirements Lemma F.6 and Lemma E7
F.8
Then by
Lemma F.6
if <,
f(x+11) f(x)) - 4G
[f((1)) + X
12
29

---

Taking summation over 1 t < 7, re-arranging terms, multiplying both sides by 8G and taking an expection, we get
8G x ||ell? 1 21
8G
8G (AI - B[f(x+) f (28)
Σ
- f(x+))
7
By Lemma
E.7
we have
E
Σ
|
64
16G
Bl 12 5
8GA1
16G
E
E||ee 12 (29)
A
AB
where the last inequality is due to Lemma
F.5 Then
28
29
gives
8G
16G
16GA
Σ |V(())|
+
E[f(x,) f +
Bille, 11
"
X
which completes the proof.
With all the above lemmas, we are ready prove the theorem.
Proof of Theorem 6.2 First note that according to Lemma F.5 it is straight forward to verify that the
parameter choices Theorem 66.2 satisfy the requirements in all the lemmas for VRAdam.
Then, first note that r = T2 S T, we know f(++) - f > F by the definition of T. Therefore,
F) B[
24 5
P(r n T) < P()a,))
F
4
where the second inequality uses Markov's inequality; the third inequality is by Lemma F8 and the last inequality is due to Lemma E.5
Similarly, if 72 = S T. we know ||e/|| > G. We have
|1
3 AA,
8
P(T2 = < 7) < P([|=] G) 1[]|=112 > G2)
S
G
G2 4'
where the second inequality uses Markov's inequliaty: the third inequality is by Lemma F8 and the last inequality due to Lemma F.5 where the last inequality is due Lemma
F.5 Therefore,
P(T S T) S P(r = + P(re = S T) s
Also, note that by Lemma
F.8
16GA
>E
V {
2P(( = T + 1)B
V ((())) 7 7=
-=
(xx))) 1 T= +
where the last inequality is due to ( + 1) 1 P(7 <T) get
2 1 - 8/2 2 1/2. Then we can
32GA;
8c2
E
[vf(21)11
T = --T++
<
1/T
Let = { [+>+IV((<)))) 2) be the event of not converging to stationary points. By
Markov's 's inequality, we have
[[= 8 2
Therefore.
P(FU < P
i.c., with probability at least 1 - 6, we have both = T + and + Σ. 2 Se
30

---

F.3 Proofs of lemmas in Appendix F.1
Note that by Assumption 6 we have [z, I G + d Σ 2G. Hence, when computing the locality size and smoothness constant for the component function f(r,), we need to replace the constant in Corollary (5.2 with 2G, that is why we get a smaller locality size of r/2 and larger smoothness constant of 47..
Proof of Lemma F.1 This lemma direct corollary of Corollary 5.2
Proof of Lemma F.2 The bound on ||m, by the definition of in (26). All other quantities for VRAdam are defined in the same way as those in Adam (Algorithm) so they have the same upper
bounds as in Lemma E.2
Proof of Lemma F.3
[+++1 xzll S 1 m /X & 2nG/A=
where the first inequality uses the update rule in Algorithm 2 and he I n/a A by Lemma F2: the second inequality is again due to Lemma F.2
Proof of Lemma
F.4
By the definition of W,, it is easy to verify that
W. ((V vf(())) + (1 3)6,,
where
5. Vf(z,, Et) - vf( fzx))) + ff((x-))..
Then we can bound
|| < [ Et) Vf(II-1, + [f(x)) vf(=x-1)]
<5L |0g 11-111
5
V [[] + ||),,
where the second inequality uses Lemma F1 and the last inequality is due to || x4-1 s
7 [|lm--11| / ([]]](x+)))) (1-11l)) A. Then, we have
5nL (IVS( + ||e--1)))
| S Bo +
Proof of Lemma
E.5 These inequalities can be obtained by direct calculations.
31


Reviews:
[{"review_id": "QdP78788Gm", "reviewer": "Reviewer_hwio", "summary": "This paper provides convergence results for Adaptive Moment Estimate (Adam) and its variance-reduced variant under generalized smooth and bouned-noise assumptions.", "questions": "see the weakness part", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper mainly studies the convergence of Adaptive Moment Estimate (Adam) under a generalized smooth assumption. The authors drop the commonly used globally bounded gradients assumption and provide a new analysis framework, which is based on a contradiction argument, to show that gradients are bounded along the optimization trajectory. Based on this, the authors could deduce a high probability convergence bound of $\\mathcal{O}(\\epsilon^{-4})$ for Adam under the generalized smooth assumption. The paper also provides a variance-reduced version of Adam and improves the gradient complexity to $\\mathcal{O}(\\epsilon^{-3})$. \n\nIn general, the assumptions are standard in the analysis of adaptive methods including unbiased gradient estimate and bounded noise. The convergence results make sense and are highly valuable since the convergence result of Adam under unbounded gradients still leaves empty, to my best knowledge. As Adam is a widely used optimizer in deep learning field, the theoretical results (like parameter setting in Theorem 4.1 and Theorem 4.3) in this paper could help practitioners to better understand and use the algorithm. The central idea of analysis is inspiring.", "weaknesses": "First, the convergence result requires a dedicated tuned step-size and momentum parameters, specifically requiring prior knowledge such as generalized smooth parameter $(L_0, L_1)$ and the noise level $\\sigma$. However, in most realistic situations, these parameters could be unknown or hard to obtain. Thus, the result is more valuable in the theoretical aspect but may not be so useful in the experimental aspect.\n\nSecond, the parameter setting in Theorem 4.1 contradicts the real-one default setting on deep learning packages (such as Pytorch or Tensorflow) where $\\beta_1 = 0.9 $ is smaller than $\\beta_2 = 0.999$. It may be more persuasive to do some experiments showing the convergence under this new parameter setting.\n\nThird, the high probability convergence result in Theorem 6.2 does not provide an optimal rate to the probability margin $\\delta$, leaving space for further improvement. In addition, since VRAdam is a new algorithm, it better requires some experiments to show its convergence under the parameter setting in Theorem 6.2 and its faster convergence rate than Adam. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback. Below we will have some discussions about the weaknesses in the comments.\n\n- First, it is true that our hyper-parameters depend on problem-dependent parameters like $\\rho,L_0,L_\\rho,\\sigma$, and the theory does not provide many insights regarding how to choose hyper-parameters in practice in a better way than e.g. grid search. However, the main focus of this paper is to bridge the gap between theory and practice by providing convergence guarantees of Adam under more realistic assumptions than previous works.\n- Second, regarding the choice of momentum parameters $(\\beta,\\beta_{\\text{sq}})$, we let $\\beta=\\beta_{\\text{sq}}$ in Theorem 4.1 to make the proof easier. We have some (relatively clear) ideas on how to get rid of this requirement and will try to make it formal in the revision. In addition, Adam is not sensitive to the momentum hyper-parameters based on our preliminary experimental results (see Figure 1 in the PDF attached to our global rebuttal to all reviewers), which shows our hyper-parameter choice is as good as the default one. We will add results for more models and datasets in the revision.\n- Finally, we leave the improvement of the dependence on $\\delta$ as an interesting future work, and also thank the reviewer for the suggestion about adding experiments for VRAdam, which we will consider doing in the revision."}, {"review_id": "55yrivku7Z", "reviewer": "Reviewer_d5Nv", "summary": "This paper studies the convergence of the Adam algorithm. Under a more general local smoothness assumption, the convergence of Adam to stationary points is proved without assuming boundedness of the loss gradient. Here the key technique is to show that the loss gradient along the trajectory is indeed bounded, using a proof by contradiction. A variance-reduced variant of Adam is proposed to achieve an accelerated gradient complexity.", "questions": "- Under the current local smoothness condition, how do we compare the performance of Adam and other algorithms like SGD? Does the current result suggest any advantage of Adam?", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The convergence of Adam is definitely an important question, and this paper seems to be a significant contribution by relaxing the bounded gradient assumption. The argument of bounding the gradients along the optimization trajectory looks neat and easy to understand. Overall the result of the paper is solid and novel, and the writing is also easy to follow.", "weaknesses": "It seems that the proof doesn't suggest the benefit of the momentum. It would be helpful if the authors can comment on this and provide some insights on the theoretical understanding of the momentum term.\n\nIt would also be helpful if the authors can summarize the recent results on Adam convergence in the form of a table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback! Below we will try to address the concerns and questions of the reviewer.\n\nAlthough our analysis of Adam relaxes the assumptions made in previous papers, it does not provide a better theoretical understanding of the benefit of momentum or the advantage of Adam over SGD, in the nonconvex setting. We will provide some of our insights about them below.\n- 1. For the former, momentum can accelerate training for convex objective functions (e.g. Nesterov's accelerated gradient method). However, since Adam is usually applied to highly nonconvex functions like the loss for deep neural networks, we do not find it interesting or important to study Adam for convex functions. For neural network training, momentum might also help escape from sharp minima and improve generalization, which we believe is an interesting and important future direction.\n - 2. For the latter, our intuition is that, to theoretically prove the advantage of Adam over SGD, one may need to consider different geometries other than Euclidean geometry with $\\ell_2$ norm. The reason is that Adam uses coordinate-wise stepsize, which may be helpful for functions with certain geometric properties that favor coordinate-wise updates. We had some preliminary attempts like changing the $\\ell_2$ norm in the definition of $(\\rho,L_0,L_\\rho)$ smoothness (Definition 3.2) to other norms, which unfortunately does not directly work. We will leave it as an important future work as well.\n\nWe also thank the reviewer for the suggestion on summarizing the results for Adam in the literature in a table, and will do it in the revision."}, {"review_id": "0PSWAGjkt6", "reviewer": "Reviewer_Rvyw", "summary": "This paper studies the convergence of Adam over non-convex objectives. To begin with, this paper proposes a new non-uniform smoothness condition called $(\\rho, L_0,L_1)$ smoothness condition, which generalizes $(L_0,L_1)$ smoothness condition proposed in [Zhang et al. 2019]. The authors then prove the high-probability convergence rate $\\mathcal{O}(1/\\sqrt{T})$ of Adam under $(\\rho, L_0,L_1)$ smoothness condition and affine noise variance assumption. The authors then propose Variance Reduced Adam (VRAdam) by combining the gradient estimation of STORM into Adam, and derive the convergence rate $\\mathcal{O}(1/\\sqrt[3]{T^2})$ of VRAdam.", "questions": "I will consider increasing my score according to the responses to the questions.\n\n1. Although the studied smoothness assumption is more general, what is the motivation to study it? Specifically, according to [Zhang et al. 2019], $(L_0,L_1)$ smoothness condition seems to be enough to capture the training process of neural networks.\n\n2. The convergence rate has a dependence on the initial gradient norm $\\Vert \\nabla f(x_1) \\Vert $. Does this mean that Adam is sensitive to the initialization? I expect some explanations here.", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides the first $O(1/\\sqrt{T})$ convergence rate of Adam without the bounded gradient assumption.\n\n2. The constructed stopping time is interesting and can be of independent interest. ", "weaknesses": "1. Although this paper provides the first $O(1/\\sqrt{T})$ convergence rate of Adam without the bounded gradient assumption, the analysis is somewhat restricted because it requires a non-zero $\\lambda$ and the convergence rate has a polynomial dependence over $1/\\lambda$. However, in the previous analyses of Adam including [Défossez et al., 2020; Zhang et al., 2022, Wang et al., 2022], it is allowed that $\\lambda=0$ or the rate has a logarithmic dependence over $1/\\lambda$. I treat this as a weakness of this paper because, in practice, $\\lambda$ is set to very close to $0$ (for example, $10^{-8}$ as the default value in PyTorch) and may result in very loose bound.\n\n2.  As mentioned in this paper, the assumed noise condition is still stronger than the assumptions used for the analysis of other optimizers, for example, affine variance assumption.\n\n**Minor Issue**:\n\nThe statement with respect to [Zhang et al., 2022; Wang et al., 2022] in line 28 is not inproper. In fact, if you pick $\\beta_{sq}$ according to $\\epsilon$ in [Zhang et al., 2022; Wang et al., 2022] just as this paper does, you can derive the convergence to stationary points (but with a slower rate). Therefore, a proper statement should be \"but the convergence rate of [Zhang et al., 2022; Wang et al., 2022] is slower\".\n\n**References**\n\nDefossez et al., A Simple Convergence Proof of Adam and Adagrad, 2019\n\nZhang et al., Adam Can Converge Without Any Modification On Update Rules, 2022\n\nWang et al., Provable adaptivity in Adam, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We will try to address the concerns and questions of the reviewer below.\n\n**For the weaknesses:**\n- First, regarding the dependence on $\\lambda$, although it is worse than that in the papers mentioned by the reviewer, a non-zero $\\lambda$ allows us to get a dimension-free rate while the existing papers mentioned by the reviewer obtain dimension-dependent rates. Given that the dimension in neural networks are usually large (especially for large language models), we think depending on $\\lambda$ is at least better than depending on the dimension, because 1) $\\lambda$ is a scalar hyper-parameter which is much easier to tune than the dimension; and 2) Adam is not very sensitive to $\\lambda$, and a reasonably larger $\\lambda$ does not make the performance worse, based on our preliminary experiments (see Figure 2 in the PDF file attached to our global rebuttal to all reviewers). \n\n- Second, regarding the noise assumption, we will leave the relaxation of it as an interesting and important future work. We also thank the reviewer for pointing out our improper statement about [Zhang et al., 2022; Wang et al., 2022] in Line 28, and will make it more precise in the revision.\n\n**For the two questions:**\n- 1. Regarding the motivation of our paper, note that Figure 1 in [Zhang et al. 2019] shows that $\\log$(Hessian norm) is roughly a linear function of $\\log$(gradient norm), whose slope is actually a bit larger than 1, which means Hessian norm should be a polynomial function of the gradient norm, instead of an affine function. Therefore, we believe our $(\\rho,L_0,L_\\rho)$ smoothness condition can better capture such relationship than the $(L_0,L_1)$ smoothness.\n- 2. Regarding the dependence on the initial gradient norm, we think it is from our analysis approach instead of the Adam algorithm , and thus does not suggest Adam is more sensitive to initialization. We want to also point out that, such dependence is not a bad thing for the following two reasons. First, for neural network training, the initial gradient norm is usually a numerical constant if you apply e.g. Kaiming initialization. Second, the initial gradient norm can be bounded by the initial sub-optimality gap $f(x_1)-f^*$ (Consider the reverse-PL inequality $\\\\|\\\\nabla f(x)\\\\|^2\\le 2L(f(x)-f^*)$ for classical $L$-smooth functions for example, which can actually be extended to our generalized smooth function).  so the dependence on $\\\\|\\nabla f(x_1)\\\\|$ can be viewed as dependence on $f(x_1)-f^*$. Most convergence results in the optimization literature do depend on $f(x_1)-f^*$.\n"}, {"review_id": "63wphg3ZwG", "reviewer": "Reviewer_rhLM", "summary": "The paper proposes a new proof strategy for the convergence of Adam in the\nnon-convex setting. The new analysis relaxes the typical assumptions\nin the following ways: 1) it assumes relaxed smoothness, where the norm of the Hessian\ngrows sub-quadratically with the gradient norm; 2) it does not require\nbounded gradients. With a deterministic gradient oracle, the obtained rate is $O(1/\\epsilon^2)$.\nFor the stochastic setting, the author shows a convergence rate of $O(1/\\epsilon^4)$\nwith high probability.\n\nFurthermore, the author proposes a variance-reduced version of Adam and proves\na rate of $O(1/\\epsilon^3)$. The above rates in stochastic setting is dimension-dependent\nand can be dimension-free if the Hessian norm is sub-affine on the gradient norm.\n\nThe main limitation is that although the bounded gradient assumption is removed,\nthe bounded noise is still needed.", "questions": "1. In Theorem 4.1, the same value of $\\beta_{sp}$ and $\\beta$ are selected,\nwhich differ from conventional choice of $(1 - \\beta)^2 < 1 - \\beta_{sp}$.\nCould the author please explain the reason behind this?\n2. Why do we have a dependence on $d$ in the convergence result when $\\rho \\geq 1$\nand suddenly become dimension-free when $\\rho < 1$? Also, some results for Adam\nassume the infinity norm of the gradient is upper bounded by a constant [1], which\nnatural leads to dimension dependence. It seems that by assuming bounded 2-norm, the\nresults become dimension-free [2, 3]. Could the author provide further elaborate on this matter?\n3. It seems that if we have access to problem-dependent parameters and the initial conditions (e.g., the gradient norm at the first iteration), SGD can also converge with the optimal rate [4]. What is the benefit of adaptive methods (if they also require tuning) compared to SGD in the more generalized smoothness setting?\n\nReferences:\n1. Défossez, A., Bottou, L., Bach, F., & Usunier, N. (2020). A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02395.\n2. Chen, X., Liu, S., Sun, R., & Hong, M. (2018). On the convergence of a class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808.02941.\n3. Guo, Z., Xu, Y., Yin, W., Jin, R., & Yang, T. (2021). A novel convergence analysis for algorithms of the adam family and beyond. arXiv preprint arXiv:2104.14840.\n4. Li, H., Qian, J., Tian, Y., Rakhlin, A., & Jadbabaie, A. (2023). Convex and Non-Convex Optimization under Generalized Smoothness. arXiv preprint arXiv:2306.01264.", "limitations": "The limitations are addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow. Specifically, the technical\nchallenges and the intuition behind the new analysis are discussed comprehensively.\n2. Removing the bounded gradient assumption is generally challenging. Although\nthere are a few works for AdaGrad that address this, existing work targeting\nthe removal of this assumption for Adam only converges to a neighborhood of\nstationary points.\n3. The paper considers the smoothness condition where the norm of the\nHessian is bounded by a sub-quadratic function of the gradient norm, which\nis more general than $(L_0, L_1)$-smoothness.", "weaknesses": "1. Although the work relaxes the bounded stochastic gradient assumption\n   commonly required in the analysis of Adam, assuming almost surely bounded\n   noise is still somewhat strong and impractical. Since the proof technique,\n   the contradiction argument, heavily relies on this assumption, it is\n   unclear whether it can be used in more realistic settings.\n2. It is difficult to assess the usefulness of the proposed variance reduction method\nsince the convergence result does not improve upon previous methods and there\nis no experimental evidence.\n\n\nMinor:\n\nThe result presented for the deterministic setting is not formal. It would be\nbetter to have a formal theorem, at least in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback! Below we will try to address the concerns and questions in the comments.\n\n**For the weaknesses:**\n- Regarding the bounded noise assumption, we want to first clarify that, it is not hard to generalize it to sub-Gaussian noise, as we discussed around Line 165. The contradiction argument is not really the bottleneck of further generalizing it to more heavy-tailed noise like noise with bounded variance.  The challenging part is that, when noise is heavy-tailed, there is an unignorable probability that $v_{t}$ becomes very large due to a very large noise in the gradient, which may result in a small learning rate and slow convergence. If this challenge can be overcome, we can replace the contradiction argument with something similar to the proof of convergence of VRAdam to make it work.\n\n- We also thank the reviewer for the suggestions on adding experimental results for VRAdam and formal statement in the deterministic setting and will consider adding them in the revision.\n\n**For the questions:**\n\n- 1. We choose $\\beta=\\beta_{sq}$ because it guarantees $\\hat{v_t}\\succeq\\hat{m_t^2}$ (where \"$\\succeq$\" denotes coordinate-wise inequality, see Proof of Lemma 5.2 for why it holds), which gives a uniform bound on the update $\\\\|x_{t+1}-x_t\\\\|$ and makes our analysis easier. Also, based on our preliminary experiments, Adam is not very sensitive to the momentum parameters (see Figure 1 in the PDF file attached to our global rebuttal to all reviewers).\n\n- 2. Roughly speaking, the difference is due to how we upper bound the stepsize $\\frac{\\eta}{\\sqrt{\\hat{v_t}}+\\lambda}$. For $\\rho<1$, the problem is relatively more smooth, and we can simply use $\\frac{\\eta}{\\sqrt{\\hat{v_t}}+\\lambda}\\le \\frac{\\eta}{\\lambda}$, which to some extent makes the analysis a bit similar to SGD whose rate is dimension-free. When $\\rho\\ge1$, we need to also consider the $\\sqrt{\\hat{v_t}}$ term in the denominator and use it to bound ${\\\\|x_{t+1}-x_t\\\\|}\\_{\\infty}\\le \\eta$ as we discussed in the response to your previous question, which implies $\\\\|x_{t+1}-x_t\\\\|\\_{2} \\le \\eta \\sqrt{d}$, and gives a dimension-dependent rate. We think what we discussed here also at least partially explains why the rates in related works mentioned by the reviewer are dimension-free or dimension-dependent. Finally, we want to mention that we have some ideas on obtaining a dimension-free rate for $\\rho\\ge1$ with a more careful analysis and will try to make it formal in the revision.\n- 3. Since SGD already obtains an optimal rate, our results can not theoretically explain the advantage of Adam over SGD observed in practice. We will leave it as an interesting and important future work to find a reasonable condition where Adam is provably better than SGD. "}, {"review_id": "6pNk1R4FF2", "reviewer": "Reviewer_LKzM", "summary": "The paper removes the Lipschit gradient assumption for the adaptive SGD (ASGD), making the ASGD broader to wide applications. Under the weak assumption, the authors still proved the optimal convergence rate. Moreover, they propose a variance-reduced version  with an accelerated complexity. The results are interesting and novel.", "questions": " There are very recent works on using bounded variance noises [Matthew Faw et al. COLT 2022, Bohang Wang et al. COLT 2023]. Can the results in this paper be extended to that case?", "limitations": "YES", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. They further relaxed the ($L_0,L_1$)  Lipschit gradient assumption, which is more relastic.\n\n2. They  develop a new analysis to show that ASGD can be convergent under the weak Lipschit gradient assumption but still with the same rate as existing works on ASGD. The results and techniques are novel.\n\n3. A variance-reduced version of  ASGD is proposed with provable acceleration.\n\n4. The authors show that the rates of ASGD and its variance-reduced version is dimension-free under certain cases.", "weaknesses": "1. The proof of variance-reduced version is interesting but without any numerical demonstrations. If the authors proposed an accelerated algorithm, it is convening to present some numerics because the theory is not the focus now.\n\n2. In the contribution part, the authors claim that they do not assume bounded gradients. This is because you assume the a.s. bounded noise. which has been studied by previous work [Li and Orabona, 2019].\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback! Below we will try to address the concerns and questions.\n\n- First, we thank the reviewer for the suggestion about numerical demonstrations for VRAdam. We will consider empirically comparing the performances of Adam and the variance-reduced version of it in the revision.\n- The assumption of bounded gradient is actually independent of that of bounded noise. Even in the deterministic setting with zero noise, previous analyses of Adam cited in our paper still require strong assumptions like bounded gradients. For the paper [Li and Orabona, 2019], they are studying AdaGrad which is different from Adam, and therefore not directly comparable to our results.\n- The recent works  [Matthew Faw et al. COLT 2022, Bohang Wang et al. COLT 2023] also study AdaGrad (or AdaGrad-Norm) instead of Adam. Based on our understanding, they actually rely on some properties of AdaGrad to relax the noise assumption to bounded variance. Our approach is general and can also be applied to get a convergence result for AdaGrad. However, it may not be as good as their analyses designed for AdaGrad (e.g., we may still require the bounded noise assumption for AdaGrad). \n\nNote that the reviewer did not provide enough details for us to precisely identify the references in the comments. We assume they refer to the following three papers. Please let us know if not. We will also cite them in the revision.\n\n[1] Li and Orabona. \"On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes.\" AISTATS 2019\n\n[2] Faw et al. COLT 2022. \"The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance.\" COLT 2022\n\n[3] Wang et al. \"Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions.\" COLT 2023\n"}]

Author rebuttal:
In the global rebuttal, we prove some preliminary experimental results to help address the concerns of some reviewers regarding the hyper-parameters of Adam, including $\beta,\beta_{\text{sq}}, \lambda$. We train a small MLP on the Cifar10 dataset with Adam. The default parameters are $\eta=0.001, \beta=0.9, \beta_{\text{sq}}=0.999, \lambda=10^{-8}$. In the attached PDF file, we show the evolution of test errors (%) with the number of epochs. 

Figure 1 shows that Adam is not sensitive to $ \beta_{\text{sq}}$, which suggests that choosing $ \beta_{\text{sq}}=\beta=0.9$ as in our Theorem 4.1 is as good as the default choice $ \beta=0.9, \beta_{\text{sq}}=0.999$. Figure 2 shows Adam is not sensitive to $\lambda$, either. So we think the dependence on $\lambda$ in our rate is not too bad, given that $\lambda=0.1$ still gives a good convergence in Figure 2.

Meta-review: This paper shows a new analysis of Adam. Unlike standard analysis of Adam which typically requires bounded gradient and smoothness assumption, the key novelty in the analysis is a new proof of bounding gradient along the trajectory of the Adam update under a generalized smoothness condition. A variance-reduced version of Adam is also provided with a better complexity when the individual function (w.r.t. the random sample) is generalized smooth. 

The reviewers unanimously supported this paper. I have read the proof sketch of the paper by myself and find the stopping time analysis novel and interesting. One minor comment is that I suggest the authors explain the order of the hyperparameters ($\eta$, $\beta$, $\lambda$, $T$) in each theorem to make readers easier to understand the complexity results. It seems that $\lambda$ has to be constant and cannot be very small (e.g., $10^{-8}$ as chosen in practice).

I recommend accepting this paper.
Decision: Accept (spotlight)