On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
Authors: Yusu Hong
Junhong Lin
Venue: NeurIPS 2024 poster (2024)
Keywords: Adam
optimal rate
high probability convergence
relaxed assumptions
Primary area: optimization

Abstract: In this paper, we study Adam in non-convex smooth scenarios with potential unbounded gradients and affine variance noise. We consider a general noise model which governs affine variance noise, bounded noise, and sub-Gaussian noise. We show that Adam with a specific hyper-parameter setup can find a stationary point with a $\mathcal{O}(\text{poly}(\log T)/\sqrt{T})$ rate in high probability under this general noise model where $T$ denotes total number iterations, matching the lower rate of stochastic first-order algorithms up to logarithm factors. We also provide a probabilistic convergence result for Adam under a generalized smooth condition which allows unbounded smoothness parameters and has been illustrated empirically to capture the smooth property of many practical objective functions more accurately.

On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
Yusu Hong Center for Data Science
Junhong Lin"
Center for Data Science Zhejiang University junhongāzju. edw...uuuuuuu......... edu. cn
and School of Mathematical Sciences
Zhejiang University yusuhongōzju. edu.
Abstract
In this paper, we study Adam non-convex smooth scenarios with potential un- bounded gradients and affine variance noise. We consider a general noise model which governs affine variance noise, bounded noise, and sub-Gaussian noise. We show that Adam with specific hyper-parameter setup can find a stationary point with O(1 /T) rate in high probability under this general noise model where T denotes total number iterations, matching the lower rate of stochastic first-order algorithms up to logarithm factors. Moreover, show that under the same setup, Adam without corrective terms and RMSProp can find stationary point with a ÓL/TT+ oo/vT) rate which is adaptive to the noise level og. We also provide a probabilistic convergence result for Adam under generalized smooth condition which allows unbounded smoothness parameters and has been illustrated empir- ically capture the smooth property of many practical objective functions more accurately.
Introduction
Since its introduction by 34. the Stochastic Gradient Descent (SGD): Ø++1 2t ".gtt has achieved significant success solving the unconstrained stochastic optimization problems:
min f(x), where f(x)) [e[ E)
#ERd
where & is random variable, 9I is the stochastic gradients and fit is the step-size. From then on, numerous literature focused on the convergence behavior of SGD in various scenarios. Several studies focused on the non-convex smooth scenario where the stochastic gradient g(x:) is unbiased with affine variance noise, i.e., for some constants
2 0 and all æ E IRd E [[(]))) [=(=) < of +
provided an almost-sure convergence bound for SGD. 4 proved that SGD could reach stationary point with O rate when step-sizes are tuned by problem- parameters such as the smooth parameter L. The theoretical result also revealed that the analysis of SGD under (2) not essentially different from the bounded noise case [17
Under the noise assumption
In the popular field of deep learning, a range of variants based on SGD, known as adaptive gradient methods have emerged. These methods employ the past gradients adaptively tune their step- sizes and are preferred to SGD for minimizing various objective functions due to their efficiency. Among these methods, Adam (2 has been one of the most effective methods empirically. Generally
The corresponding author is Junhong Lin.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison for existing Adam analyses with ours.
PCT
Grad.
Noise
Smooth
81,
Cony. Rate
Conv. Type
49
Bounded
Bounded
1- 8g s
poly())
4
+
Bounded
Bounded
P2.
Bounded
poly D
Finite Sum Afline
(1) +0
10
Bounded
Bounded
L
91 < 92, 82
1- +
polyclog $) poly(
18
Bounded
Affine
L
01 == +/
E
Finite Sum
Finite Sum Affine
(La: L1)
< vi%
961
Sub- Sub-Gmussian
Lox T(a)
81 3
w.h.p.
20
Coordinate-win Affine
L
0. = by/02,
poly !
E
20
Coordinate wise Afline
9g. 83
poly
w.h.p.
Thm.
3.1
Affine
9g. 4
poly
w.h.p.
Thm.
Affine
(Lo, L1)
Sb.
4
poly
w.h.p.
ki
requires T(81, (2)) o ( (1 + +1) 0, which seems could only achieve when 811 O
Though not explicilly stated, the results in (Zhang et al., 2022) could imply convergence to the stationary point when with some calculations. "FCT" refers to "full corrective terms". 'The "Conv, rate" column presents the convergence rate omitting logarithm factors.
speaking, Adam absorbs some key ideas from previous adaptive methods such as AdaGrad 12 37 and RMSProp (38) while adding more unique structures. combines the exponential moving average mechanism from RMSProp and meanwhile adds the heavy-ball style momentum [30] and two unique corrective terms. This unique structure leads to a huge success for Adam in practical applications but at the same time brings more challenges to the theoretical analysis.
Considering the significance of affine variance noise and Adam in both theoretical and empirical fields, it's natural to question whether Adam can find a stationary point at a rate comparable to SGD under the same smooth condition and ( Earlier researches [14
have shown that AdaGrad- Norm, scalar version of AdaGrad, can find stationary point at the same rate as SGD, not tuning step-sizes based on by the correlation of adaptive step-sizes and noise from ( which does not appear in SGD's cases. However, since AdaGrad- Nord applies a cumulative step-sizes mechanism which is rather different from the exponential moving average step-sizes in Adam, the analysis for AdaGrad-Nome could not be trivially extended to Adam. Furthermore, the coordinate-win rather than the unified step-size for all coordinates in AdaGrad-Norm, brings more challenge when considering (2) In affine variance noise landscape, existing literature could only ensure the Adam's convergence with aandom-rehhffflig scheme under certain parameter restrictions [33 42 de- duce the convergence at the expense of requiring bounded gradient assumption and using problem- parameters tune the step-sizes [1], both of which ignored the corrective terms. Some other works proved convergence to a stationary point by altering the original Adam algorithm such as removing certain corrective terms and modifying (2) to stronger coordinate-wise variant 40
Moreover, they addressed an essential challenge brought
step-size architecture of Adam,
To the best of our knowledge, existing research has not yet fully confirmed the convergence of Adam under affine variance noise. To address this gap, conduct an in-depth analysis and prove that Adam with the right parameter can find a stationary point in high probability. We as- sume a milder noise model (detailed in Assumption (A3)), covering almost surely affine variance noise, the bounded noise, and sub-Gaussian noise. We show that the convergence rate can reach at
O (ooly(log T)/VT) matching the lower rate in I up to logarithm factors. Our proof employs the descent lemma over the introduced proxy iterative sequence and adopts techniques related to the new proxy step-sizes and error decomposition. Based on this, we are able to handle the correla- tion between stochastic gradients and adaptive step-sizes and transform the first-order term from the descent lemma into the gradient norm.
Finally, we apply the analysis to the (Lo, smooth condition 52 Several researchers have found empirical evidence of objective functions satisfying (L., Lg smoothness but out of L-smoothness
range, especially in large-scale language models [50 39 I1 8) Theoretical analysis of adaptive
methods under this relaxed condition is more complicated and needs further nontrivial proof tech- niques. Also, prior knowledge of moblem-parameter to tune step-sizes is needed, as indicated by the counter-examples from 41 for the AdaGrad. Existing works [3] 41 obtained a convergence bound for AdaGrad-Nom with and (25) considered Adam with sub-Gaussia noise. In this

---

Algorithm Adam
Input: Horizon T, x1 E RR $1. B2 E [0, 1), my = Do Os. 9, > 0, c = cld
for = -..... . do
Draw a new sample 2 and generate
2(
m, -mmm--- + B1 gsi
V, = 320.-1 + (1 $2)9.
7. = nV (1 Bi), 6, = --
1o+1 = 178 m (vu, + Ex);
end for
paper. we provide probabilisticc convergence result for Adam with the affine variance noise and the generalized smoothness condition.
We also refer readers to see the main contributions of our works and comparisons with the existing works in Table
Notations We use [T] to denote the set {1,2. ..... .T} for any positive integer T, I1-1 and ||-Ilss denote 12-norm, Iiorr and -norm respectively.
(b) and S (b)) denote Cib and (b)) denotes (b)). For any vector æ Rd,, x² and v denote coordinate- -iite square and
S C2b for some positive universal constants C1, C2 and b denotes square root respectively. æ; denotes the i-th coordinate of æ. For any two vectors æ, E Rd, use x @ y and z y to denote the coordinate- wise product and quotient respectively. O₂ and 1 represent zero and one d-dimensional vectors respectively.
(6) b).
2 Problem set up and algorithm
We consider unconstrained stochastic optimization I over Rd with norm. The objective function f RR I differentiable. Given æ R2d, assume gradient oracle that returns random vector g(,, z) E Rd dependent by the random sample z. The true gradient of ʃ at æ is denoted by ff(x) Rd.
Assumptions.
We make the following assumptions throughout the paper.
(A1) Bounded below: There exists f > -o such that f(x) 2 fr, Vo Rd;
(A2) Unbiased estimator: The gradient oracle provides an unbiased estimator of Vf(x), i.e.,
Ex [g( =]] = fxx), Væ E Rd;
(A3) Generalized affine variance noise: The gradient oracle satisfies that there are ([())
stants du, > 0, E [0, 4), E.
exp
o[+ )]
cxp(1), Va E Rd
The first two assumptions are standard in the stochastic optimization. The third assumption provides mild noise model that covers the almost surely bounded noise and sub-Gaussian noise. Moreover, it's more general than almost surely affine variance noise as follows
( 2) ff < of of f a.s.,
and enlarge the range of p to [0, Assumption (A3) with p = and 33 are also utilized in (2) to establish high probability results for AdaGrad-Norm. It represents stronger condition than the expected version of (2) that is commonly employed for deriving the expected convergence of algorithms. However, almost surely assumption enables the derivation of stronger high-probabilityy convergence guarantees for algorithms, while still ensuring expected convergence.
The affine noise variance assumption is important for machine learning applications with feature noise (including missing features) [15] (2), in robust linear regression (46), and generally whenever
the model parameters are multiplicatively perturbed by noise (e.g., multilayer network, where noise from previous layer multiplies the parameters in subsequent layers). We refer interested
readers to see e.g., 3 46. 4 [4
2 for more discussions about the affine variance noise.

---

Adam.
For the stochastic optimization problem. we study Algorithm I which is an equivalent
form of Adam [23] with the two corrective terms for m, and v, included into 77s for notation simplicity.
The iterative relationship in Algorithm 1 can be also written for any [T),
9s
Tolvo,-1+ c (a., 1.--))
+++1 1 D3 (1 31) Vo, c +1 7/-1(Vu, + 62)
(4)
where we let 4o and 7/0 1z. 4 plays key role in the convergence analysis, showing that Adam incorporates a heavy-ball style momentum and dynamically adjusts its momentum through 31 and B2, along with adaptive step-sizes. This inspires to learn from some classical analysis meth- ods for algorithms with momentum and provides some new estimations to fit in with the adaptive property.
3 Convergence of Adam with smooth objective functions
In this section, we assume that the objective function f is L-smooth satisfying that for any æ, y E Rd
[V - ff(ii) S L - =zl--
(S)
We then show that Adam has the following high probability results.
Theorem 3.1. Let T 2 and (eer) be the sequence generated by Algorithm 7 Assumptions (A1)-(A3) hold, and the hyper-purameters satisfy that
0 S B1 < B2 1, B2 - c/T, 7 CovI- 32 6 = 82,
(6)
for some constants c, Co > and eo > O, then for any given E (0,1/2), holds that with probability least 26,
T Σ [VF().))
1
=
(
(o8
o8 + of + G
60 log 88) }
+T
T
where G2 is defined by the following order with respect to T,
Eg.
8
G ~ 0 (10g² max 24م1
T
provides the nearly optimal convergence rate O polyy(og T)/VT) to find stationary point when setting the parameter probably: 33 = - O(1TT) It's worth noting that the setting requires 32 be closed enough to when T' is sufficiently large, which roughly aligns with the typical setting in [23 58 10, 40). For a more detailed comparison of our results to existing works, including assumptions, convergence rate, and dependency, we refer readers to Table
Theorem 3.1
Adam without corrective terms and RMSProp. We also consider simplified version of Adam that drops two corrective terms shown Algorithm 2 in Appendix. Algorithm [ with 81 can be directly reduced to RMSProp (38]. More importantly. the following result shows that the convergence rate of Algorithm 2 is adaptive to the noise level.
Theorem 3.2 (informal version of Theorem C.2 Let T and ( be generated by Algo- rithm 2 covering RMSProp. Following the assumptions and setup in Theorem 3.1 with probability at least - 26, Σ =11 [V S Ó(1T + 50/ vo).T).
4 Convergence of Adam with generalized smooth objective functions
In this section, we study the convergence behavior of Adam in the generalized smooth case, We first provide some necessary introduction to the generalized smooth condition.
The detailed expression of G2 could be found in 53 from Appendix.

---

4.1 Generalized smoothness
We consider the following (Lu, Lg) syyoothtsssssss condition: there exist constants g E [0, and Lo, Lg > satisfying that for any æ, y E I2 with || yll S L/
IVf - v f(x))l - (Lo + اug V f (x)]l x -ll-
(8)
The generalized smooth condition was originally put forward by [52] for any twice differentiable function f satisfying that
|<>)| S To + [x)])(
It has been proved that lot of objective functions in experimental areas satisfy (9) but out of L- smoothness range, especially in training large language models, see e.g. Figure 52 and
To better understand the theoretical significance of the generalized smoothness, 50 provided an alternative form in (8) with q 1, only requiring f to be differentiable. They showed that (8) is sufficient to elucidate the convergence of suudient-clipping algorithms.
There are three key reasons for opting for (8) Firstly, considering access is limited first-order stochastic gradients, it's logical to only assume that f is differentiable. Second, as pointed out by equivalent up constant factors when I is twice differentiable considering q = 1. Thus, (8) covers a broader range of functions than (9) Finally, it's easy verify that (8) strictly weaker than L-smoothness. A concrete example that the simple function f(x) = x² x E IK does not satisfy any global L-smoothness but (8). Moreover, the expanded range of j0, 2) is necessary all univariate rational functions ((z:)((xx) where P. Q are polynomials and double exponential functions (bb)) with a, b >
Lemma A.2 in [50] and Proposition 1 in [3]
and
(Lg. Lgg -smooth
with 1 < < 2 (see [25] Proposition 3.4)). We refer interested readers to see [52 50
13 25 for
more discussions of concrete examples of generalized smoothness.
4.2 Convergence result
We then provide the high probability convergence result of Adam with (Lo, L smoothness condi- tion follows.
Theorem 4.1. Let T 2 1 and E (0, 1/2). Suppose that {xx (eET)) is a sequence generated by
Algorithm| 7 f is (To: I.g) -moooth satisfying Assumptions (A (-33) hold, and the parameters satisfy
0 31 < 92 1,
82 1-TTT c/T, 6=60v B2, 7= CoVI- - 82,
Eg Eo
B₂ (1) 32/32)
Co S min
Ev.
(10)
H L L'V
4L2dd
where c, co. Eg, Co > O are constants, Á is controlled by (log
T
and H, H. are defined
eud
as
H = Lo/Lg + (4 + (ALu 3-
(ALolt) Algllt (ALgtt)
+
//LoHH,
cT
Lu T,q
H = / 22 + +oHHp + H2) log
(
L: Lo + Lig H H
(11)
Then it holds that with probability least - 26,
1 T ΣΣ [V)((2))) T
A =
2 + o HP +
H²
en T
T log
(12)
2
T
8
Note that in the above theorem, the order of log T in A and the final convergence bound is bet- ter than the one in Theorem 3.1 under the same noise assumption. This better dependency comes from the expense of using problem parameters to tune step-size Co. Since it is logarithm order
The specific definition of / can be found in 115 from Appendix.
5

---

of T. H. H,H, C are both polynomial logarithm order of T and the final convergence rate in (12) is (polyy(og T)) order. Note that Co I (1
7)) from TO)) when T > d. Hence, when 7 is large enough, possible optimal setting is that 1j = ci pollylll stant C1 > 0, which roughly matches the typical setting as mentioned before.
for some con-
Similarly, we also obtain a convergence bound that is adaptive to the noise level for Adam without corrective terms and RMSProp under generalized smoothness.
Theorem 4,2 (informal version of Theorem E.Ip. Let T 2 1 and {a.}.etr) be generated by Algo- rithm 2 covering RMSProp. Following the assumptions and the sume order of hyper-puramettes in Theorem with probability at least 26, Σ [V((z)] S
= Ó(1/T oo/VT).
Related works
There is large amount of works on stochastic approximations (or online learning algorithms) and adaptive variants, c.g., [5] 36 48 29 12
27 55) and the references therein. In this section, we will discuss the most related works and make comparison with our main results.
5.1 Convergence with affine variance noise and its variants
We mainly list previous literature considering (2 over non-convex smooth scenario. [ provided an asymptotic convergence result for SGD with (2. In terms of non-asymptotic results, 4 proved the convergence of SGD, illustrating that the analysis was non-essentially different from the bounded
noise case from 17
In the adaptive methods field, 14] studied convergence of AdaGrad-Nomn with (2) pointing out that the analysis is more challenging than the bounded noise and bounded gradient case in [44]. They provided a convergence rate of O(1/VT) without knowledge of problem parameters, and further improved the bound adapting to the noise level: when o1 ~ ~O1/VT),
T EIVS(E)
ou + + VT
(13)
T
113 matches exactly with SGD's case [4) showing a fast rate of ((/TT) when oo is sufficiently low. Later, [41] proposed deep analysis framework obtaining (L3) with tighter dependency to T
and not requiring any restriction over d1 They further obtained the same rate for AdaGrad under a stronger coordinate-wil wise version of (2: for all i E [d].
Eg 2): (=>)) < of + +
(14)
2 obtained a probabilistic convergence rate for AdaGrad-Norm with (3) using novel induction argument to estimate the function value gap without any requirement over σ as well.
In the analysis of Adam, line of works 35 53 42
considered Adam for finite-sum objective functions under different regimes while possibly incorporating natural random shuffling technique. They could ensure that this variant converged to a bounded region where
log T VT +Ci00
min E EE(T]
(15)
under the affine growth condition which equivalent to (2.. Though not explicitly concluded, when setting 3g (1/T)) [53]* 's work can also ensure a convergence rate of order ((1/VT) under certain settings. Besides, both 21 and [8] provided convergence bounds allowing for large heavy- ball momentum parameter that aligns more closely with practical settings. However, they relied on the assumption for step-sizes where G < voite, oloo S Cu,, Vt E [T]. 40 and (20 used distinct methods to derive convergence bounds in expectation and high probability respectively, without relying on bounded gradients. Both studies achieved a convergence rate of the form in (13) for Adam ignoring the corrective terms. [20] further achieved a ((IV/T) rate for Adam. However, the two works only studied coordinate- wise affine variance noise.
In this paper, we derive stronger high probability convergence rate for Adam with original cor- rective terms, relying almost surely noise assumption. The noise model is general enough to

---

cover bounded noise, sub- Gaussann noise, and (coordinate-wisst affine variance noise. Although we consider a stronger almost surely assumption, our probabilistic convergence result also stronger than the expected convergence.
5.2 Convergence with generalized smoothness
The generalized smooth condition was first proposed for twice differentiable functions by 12 (see
( to explain the acceleration mechanism of gradient-clipping. This assumption was extensively confirmed in experiments of large-scale language models [52]. Later, [50] further relaxed it to
more general form in (8) allowing for first-order differentiable functions. Subsequently, a series of works
33 studied different algorithms' convergence under this condition.
In the field of adaptive methods, 13 provided a convergence bound for AdaGrad-Norm assuming ( and (8) with q = 1, albeit requiring Ø1 < 1. Based on the same conditions, [41 improved the convergence rate to the form in 13 without restriction on σ1. 42 explored how Adam without cor- rective terms behaves under generalized smoothness with q and (). However, they could only
assert convergence to bounded region as shown in (5) g showed that an Adam-type algorithm converges to stationary point under stronger coordinate- wise generalized smooth condition. Re- cently, [25] provided a novel framework to derive high probability convergence bound for Adam under the generalized smooth and sub-Gaussian noise case.
In this paper, we consider a more general noise setup and investigate Adam's 's convergence under the generalized smooth landscape. We prove that Adam is powerful enough to find stationary point with properly tuned step-sizes even under these relaxed assumptions. Moreover, the convergence rate is not harmed by the relaxation of noise and smoothness, matching the optimal O1I/VT) rate up to logarithm factors.
5.3 Convergence of Adam
Adam was first proposed by (23 with empirical studies and theoretical results online convex learning. The original proof of convergence in (2 was later shown by 32) to contain gaps. [32] and the subsequent work [43 also showed that for range of momentum parameters chosen indepen- dently with the problem instance, Adam does not necessarily converge even for convex objectives. Many works have focused on its convergence behavior in non-convex smooth fields. A series of works studied Adam ignoring corrective terms, all requiring a uniform bound for gradients' norm. Among these works, [49] demonstrated that Adam can converge within specifie region if step-sizes and decay parameters are determined properly by the smooth parameter. (9] proposed a convergence result stationary point and required all stochastic gradients must keep the same sign. To circum- vent this requirement, (58) introduced a convergence bound only requiring apper-paraeetess to sat- isfy specific conditions. [0] conducted a simple proof and further improved the dependency on the heavy-ball momentum parameter. Recently, [56] introduced Nesterov- acceleration into Adam and Adam W (28) indicating their superiority in convergence over the accelrreee versions. For Adam-related works under 2 or generalized smoothness, we refer readers to Sections
We also want highlight that a series of works (24 45 51] investigated the geometry of Adam from an -nom perspective. (24) and (45) studied the geometry of Adam by regarding it as a variant of SignSGD and (51] showed that full-batch Adam converges towards linear classifier that achieves the maximum 1x -arrin when the training data are linearly separable.
Proof sketch under the smooth case
In this section, we provide proof sketch of Theorem 3.1
with some insights and proof novelty. Our The detailed proof is in Appendix B
proof borrows some ideas from 44 10
2
40
20
Preliminary. To start with, we let the stochastic gradient gs = (gs,));. the true gradient V (xx,) = g. = (0..:)s and E. = (5..s): 9, g.. We also let e, = cvI 33 and thus 1. For any positive integer 7 and 8 E (0, 1), we define Mr Vlog (eT We denote the adaptive part of the step-size as
b, = Vo
U + VBu0-1 +(1 82)9 c...
(16)
7

---

We define two auxiliary sequences {ps and {us 1.21
31
P1 = Od:
y1 = 21,
P. = - B1
(Is I x.-1), Ps
V8 2
2.
(17)
We follow from [6 47 which used to prove the convergence of SGD with momentum and later applied to handle many variants of momentum-based algorithms. Recalling the iteration of æ, in 44 we reveal that y, satisfies
9s + 1 B1 1s-
B1
( [1.bb-1 la @ (x.- x.-1))
yo+1 y 1/s
(18)
b.
In addition, given T 2 1, we define, bs E [T].
G2 max
(r = M 20 207 + 2G' Mr 20 207 + +2", (19) SE[s]
where is as Theorem 3.1 Both G, and Gr(s) will serve as upper bounds for gradients' norm before time s. We will verify their importance in the later argument.
Starting from the descent lemma. We fix the horizon T and start from the standard descent lemma of L-smoothness. Then, for any given E [T], combining with (18) and summing over E [t).
f(y++1) S f(x1) + Σ 1
Vyy=))
9g b.
B1
2 (x. 10-----11 xz-1), vf(
B1
L
9s
B
+ 2
(A, ② (x. D.
(20)
b
31
s=1
where we let A, B, and C respectively.
n.b.
1a and use yı σ1 from
17 In what follows, we will estimate A,
1 b.
Probabilistic estimations. To proceed with the analysis. we next introduce two probabilistic es- timations showing that the norm of the noises and related summation of martingale difference sequence could be well controlled with high probability. We show that with probability at least 26, the following two inequalities hold simultaneously for all & [2]:
| S My (o) ofllgelP)) and
(21)
E. (t) Σ
9x
7
DIGr.
(22)
a
4G ==1
Va,
where D2 is a constant defined in Lemma B.7 and a, will be introduced later. In what follows, we always assume that (1 and (22) hold for all [T] and carry out our subsequent analysis with some deterministic estimations.
Estimating A. We first decompose A
A
JNY
Σ 1/s
g. v (y()) by
A.2
Due to the correlation of the stochastic gradient gs and the step-size 7). b., the estimating A.1 challenging, as also noted in the analysis for other adaptive gradient methods, e.g., 44] 10 20 To break this correlation, the so-called proxy step-size technique introduced and variants of proxy step-size have been introduced in the related literature. However, to our best knowledge, none
14
2 40

---

of these proxy step-sizes could be used in our analysis for Adam considering potential unbounded gradients under the noise model in Assumption (A3). In this paper, we construct a proxy step-size ns/0s, with a, relying on (r(8) in (19), defined as for any E [7],
as 1 (1 111--)) B2) (sT()) +
(23)
With the so-called proxy step-size technique over 1/s/ as/a, and 6. = 9s
Js. we decompose A.1 as
9+ va,
A.1
73s
1/e
Jst
Js
aa
O.s
ba
A.1.1
A.1.2
In the above decomposition, the first term serves as a descent term. A.1.1 now a summation of
martingale difference sequence which could be estimated by (22)
A.1.2 is regarded
term when introducing a,, However, due to the delicate construction of as, the definition of local gradients' bound (r),), and using some basic inequalities, show that
n9 (t)v1 32
Σ
g: by
A.1.2
118
+
Va,
31
==1
The first RHS term can be eliminated with the descent term while the summation of the last term can be bounded by
m
m
m. b, B2
log
(24)
b.
37
due the step-size's adaptivity, the iterative relationship of the algorithm, the smoothness of the objective function, well as (2I). Here, m.
m.
Estimating B and C.
The key to estimate B is to decompose B
81
B
B
[ - 2.-1). ).)
(x. 23-1), Vf(y.) ge)
1
31
3
To estimate B.1, we use the updated rule and further decompose A, ① (I, 2.-1) 1) the following terms
1/4 b
1/
1)s
1)s
m.-1
m
3 m.-1
(1)s - 1)s
a2
b
b,-1
and upper bound the three related inner products. Using some basic inequalities, the smoothness, 24), and some delicate computations, one can estimate the three related inner products, B.2 and C, and thus get that
9. Va.
T 3T
B+C5
+ (b, + b2) log
where b and b2 are positive constants determined by B1, 32, d, L,
Bounding gradients through induction. The last challenge comes from the potential unbounded gradients' norm. Plugging the above estimations into 20).. we obtain that
(t)
gx
T
f( < f
4GT
7
Vas
+ +a + (c)Sr(t) 03) log
3
(25)
where C2, C3 constants determined by 31, B2, d, T., Then, we will first show that G G and suppose that for some E [T).
G, < G,
Ys [t] thus (s) s 9T, vs E [t]
(26)

---

It's then clear to reveal from 25 and the induction assumption that f(y(+1) ) is restricted by the first-order of Gr. Moreover, ((++) could be served the upper bound of [ Il since
1 v 2 V + 1++1 V vf(++1))
4L(f())+)))) - + g++1 V f -))l,
(27)
where we use a standard result use the smoothness control g Vf(y(+1)) and combine with (26) and (7 to derive that
in smooth-based optimization. We also
|| 1 di + d2(or GG,,
where d1, d2 are constants that are also determined by hyper-parameters and restricted by O T Tlog 32) with respect to T. Then, using Young's s inequality.
G
di 4 4-P p= (aida)
dd 2
0 |
Thus, combining with a proper construction G (detailed in 533 ) we could prove that
G² = 2d + 4-p p d0 2 (db)
2
which leads to 1 ? S G². Combining with the induction argument, we deduce that |lg.1? <
G2 1|.
Final estimation. Following the induction step for upper bounding the gradients' norm, we also prove the following result in high probability:
1g
2
77
9x Va
S G².
ag
We could rely on GT to prove that |a.||xo < in Algorithm to further deduce the desired guarantee for Σ |1g 1²/T.
GT GTV1
B5 + Ex.
Vs E [T]. and then combine with 7/s
7 Conclusion
In this paper, we investigate the convergence of the Adam optimization algorithm on non-convex smooth problems under certain relaxed conditions. We begin by considering mild noise assump- tion that encompasses several noise types, particularly the almost surely affine variance noise. Under this noise condition, we demonstrate that Adam can find a stationary point at rate of (poly(log /TT) with high probability. Within framework, we introduce novel proxy step- size to manage the entanglement of stochastic gradients and adaptive step-sizes, and we employ a new decomposition method to estimate the errors introduced by the proxy step-size, the momentum, and the corrective terms in Adam.
We also extend our analysis to the convergence of Adam when the objective function is generalized smooth. This relaxed assumption is empirically validated be more realistic in practical applica- tions. Our results indicate that, with appropriate hyper-pane paraame tuning, Adam can find stationary point at the same order of convergence rate as the smooth case.
Limitations. Our study has several limitations that warrant further exploration. First, it would be advantageous to provide experimental results to validate the aapeer-rrrmeter settings in our results. Second, the convergence bound is not strictly tight compared to the lower bound, leaving gap involving logarithmic factors, which may be improved future work.
Acknowledgement
This work was supported in part by the NSFC under grant number 12471096, and the National Key Research and Development Program of China under grant number 2021 YFA1003500.
10

---

References
[1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 1996112):165-214, 2023.
[2] Amit Attia and Tomer Koren. SGD with AdaGrad stepsizes: full adaptivity with high prob- ability to unknown parameters, unbounded gradients and affine variance. In International Conference Machine Learning, 2023.
[3] Dimitri P Bertsekas and John Tsitsiklis. Gradient convergence gradient methods with errors. SIAM Journal Optimization, 10(3):627-642, 2000.
[4] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale ma- chine learning, SIAM Review, 60(2):223-31, 2018.
[5] Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on- line learning algorithms. JEEE Transactions on Information Theory, (009)):255020577 2004.
[6] Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang. Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv: /806.06663. 2018.
[7] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
[8] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Ro- bustmess to unbounded smoothness of generalized signSGD. In Advances in Neural Informa- tion Processing Systems, 2022.
[9] Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for RMSProp and Adam in non-convex optimization and an empirical comparison to Nesterov acceleration. arXiv preprint arXiv: 1807,06666 2018.
[10] Alexandre Défossez, Leon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and Adagrad. Transactions on Machine Learning Research, 2022.
[11] Jacob Devlin, Ming- Heig-WWiile Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.0444 2018.
[12] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):2121-2159 2011.
[13] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: a stopped analysis of adaptive SGD. In Conference on Learning Theory, 2023.
[14] 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 afline variance. In Conference on Learning Theory, 2022.
[15] Wayne A Fuller. Measurement error models. John Wiley & Sons, 2009.
[16] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. European Control Conference, 2015.
[17] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[18] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence anal- ysis for algorithms of the Adam family. Annual Workshop on Optimization for Machine Learning, 2021.

---

[19] Yusu Hong and Junhong Lin. Revisiting convergence of adagrad with relaxed assumptions. In The 40th Conference on Uncertainty Artificial Intelligence.
[20] Yusu Hong and Junhong Lin. High probability convergence of Adam under unbounded gradi- ents and affine variance noise. arXiv preprint arXiv:2311.02000 2023.
[21] Feihu Huang, Junyi Li, and Heng Huang. Super-Adam: faster and universal framework of adaptive gradients. In Advances in Neural Information Processing Systems, 2021.
[22] Fereshte Khani and Percy Liang. Feature noise induces loss discrepancy across groups. In International Conference on Machine Learning, pages 5209-5219. PMLR, 2020.
[23] Diederik P Kingma and Jimmy Ba. Adam: a method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[24] Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between SGD and Adam Transformers, but sign descent might be. In The Eleventh International Conference on Learning Representations, 2023.
[25] Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of Adam under relaxed assumptions. In Advances in Neural Information Processing Systems, 2023.
[26] Xiaoyu Li and Francesco Orabona. high probability analysis of adaptive SGD with momen- tum. In Workshop on International Conference Machine Learning, 2020.
[27] Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv:1912. 19440, 2019.
[28] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2019.
[29] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming. SIAM Journal on Optimization, 1944):15741169, 2009.
[30] Boris Polyak. Some methods of speeding up the convergence iteration methods. Ussr Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
[31] Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelli- gence and Statistics, 2021.
[32] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
[33] Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303. 200.00333.,088., 2023.
[34] Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathe- maticul Statistics, pages 400-407, 1951.
[35] Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. RMSProp converges with proper hyper-parameter. In International Conference on Learning Representations, 2020.
[36] Steve Smale and Yuan Yao. Online learning algorithms. Foundations of Computational Math- ematics, 6: 1450 2006.
[37] Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv: /002.4400 2010.
[38] Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSProp: Divide the gradient by run- ning average of its recent magnitude. COURSERA: Neural Networks for Machine Learning. 2012.
12

---

[39] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances in Neural Infor- mation Processing Systems, 2017.
[40] Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and lower bound of Adam's 's iteration complexity. In Advances in Neural Information Processing Systems, 2023.
[41] Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of AdaGrad for non-convex objectives: simple proofs and relaxed assumptions. In Conference on Learning Theory, 2023.
[42] Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie-Ya Liu, and Wei Chen. Provable adaptivity in Adam. arXiv preprint ar arXiv:2208.0990 09900, 2022.
[43] Ruiqi Wang and Diego Klabjan. Divergence results and convergence of variance reduced version of adam. arXiv preprint arXiv:2210.05007, 2022.
[44] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(1):9047-9076 2020.
[45] Shuo Xie and Zhiyuan Li. Implicit bias of adamw: lorm constrained optimization. In International Conference on Machine Learning, 2024.
[46] Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and Lasso. In Advances in Neural Information Processing Systems, 2008
[47] Yan Yan, Tianbao Yang. Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018.
[48] Yiming Ying and D-X Zhou. Online regularized classification algorithms. IEEE Transactions on Information Theory, 52(1 (1(11)):775-77000 2006.
[49] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, 2018.
[50] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algo- rithms for non-convex optimization. In Advances in Neural Information Processing Systems, 2020.
[51] Chenyang Zhang, Difan Zou, and Yuan Cao. The implicit bias of Adam on separable data. In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning. 2024.
[52] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
[53] Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can con- verge without any modification on update rules. In Advances in Neural Information Processing Systems, 2022.
[54] Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochas- tie normalized gradient descent. Science China Information Sciences, 64:1-13, 2021.
[55] Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. In Annual Workshop on Optimization for Machine Learning. 2020.
[56] Pan Zhou, Xingyu Xie, and Shuicheng Yan. Win: weighn-decay-innegraeed Nesterov acceler- ation for adaptive gradient algorithms. In International Conference on Learning Representa- tions, 2023.
13

---

[57] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint vrXiv:2108.1177/ 2021.
[58] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSProp. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
14

---

The appendix is organized as follows. The next section presents some necessary technical lemmas, some of which have appeared in the previous literature. In A and Appendix[] the detailed proofs for Theorem and and (eeorem[4.1]ar presented respectively. in Appendix Caand Appendix F.] we provide detailed results and proofs for Theorem 3.2 and Theorem 4.2] respectively. Finally, Appendix Fe Appendix Ci provide all the omitted proofs in previous sections.
A Complementary lemmas
We first provide some necessary technical lemmas as follows.
Lemma A.I. Suppose that {21 is a non-negative sequence. Given B2 E (0, 1] and E > we define 0g = Ei=183 P... Then, for any t 2 1,
Σ
1
a
S log
1+ 0. +log 82.
s
0j
Proof. See the proof of Lemma 5.2 in 10
Lemma A.2. Suppose that {as).2) is real number sequence. Given 0 S 31 < <B2 S 1 and e > 0,
we define So = Σj=ı 39-aa,
agj 7s= = 1ー E 2a ag and 0₂ = Σÿ= 83-3 a3G then
C
1
02 log 1+
+log 82
5+0 0g
(1 31)(1 3r/
1s
1
O2 log Ba).
<
log
1
14 2 1.
E ++0 0s
(1 - (1) - /3/
Proof. The proof for the first inequality can be found in the proof of Lemma A.2 second result, let AM- Σj=1 B Then using Jensen's 's inequality, we have
10
For the
2
2
Σ 3 333
=
MM
3 M
aj
S
M2 Σ
B
o
=
M
30
(28)
M
1=1
j=1
Hence, we further have
2 s ++0 0
M
8
a
S (1 - (1-39)²
3
3
6 + 0g
(1 (1-B1 31)(1 - B1) j=1
+ 0.
j=1
Recalling the definition of 6,, we have + 02 with 1
2 $2 10 83 ' (E + 0,). Hence, combining
31 <
1
-3.
2 E + 0
S (1- (1-31)(1- - 34)
1
31 a²
S
Σ
1 8-ン a
32
++
0 (1- - 31)
Bg
E Oj
j=1
Summing up both sides over s E [t], and noting that 31 < B2.
2
1
B1 8-
a²
1
Σ
E E 0.
(1
31)
32
E E 0g
-1- 31)((111111) 31/32)
+
0g
8=1
1=1
Finally applying Lemma
A.I
we obtain the desired result.
Then, we introduce a standard concentration inequality for the martingale difference sequence that is useful for achieving the high probability bounds, see (26) for proof.
15

---

Lemma A.3. Suppose {Z, |a is martingale difference sequence with respect to G1. Sr. Assume that for each s E [T], oa is a random variable only dependent by C1, . Se-1 and satisfies that
E [(exp(Z)/o3) -,, -
then for any > O, and for any (0, 1), it holds that
T
1
3
P
7
log
S 8.
8
4
B Proof of Theorem 3.1
The detailed proof Theorem
corresponds to proof sketch in Section
B.1 Preliminary
To start with, we introduce the following two notations,
m. 1 39
(29)
3
which include two corrective terms for m, and Ug. is easy that 7,s satisfies
35
17
n
<
(30)
1 8i
31
We follow all the notations in Section
6 which we present here for the convenience of reading,
eT ())
Mr 1108
G. max jE(s]
|g
(T(() -Mr 20 + 20 + 2G3,
GT = Mry 20 + 207 + 2G2,
b, = V B20.- + -1- (1- c
a, 320.-1 + (1- (Gr(s) 6..
(31)
The following lemmas provide some estimations for the algorithm-dependen terms, which play vital roles in the proof of Theorem 3.1] The detailed proofs could be found in Appendix F.
Lemma B.l. Let ns be given in Algorithm 7 and (T6), then
n,
la
Emax =
Vs 2.
1b-
VB2
The following lemma could be found similarly in 57 Lemma A.2].
Lemma B.2. Let m,, b, be given in Algorithm 7 and 16 with < 81 82 1, respectively. Then,
m, b
(1 - 31)(1 -3)
<
Vs 1.
B2)(1 B1/12))
Consequently, if f is L-smooth and set 17 CovI for some constant Co > O, then
d
|g.1l
@ |l + LCos
V
1-B1//2'
The following lemma is necessary for deriving
(24 in the proof sketch.
16

---

Lemma B.3. Let 9s. m, be given in Algorithm ! and m. b. be defined in
29 and
16
If0
31 < B2 < and (t( = 1 +
Σ
F2. then for any t 2 1,
s=
9x
1
d
(i(
log
b,
32
1=1
1 B1
Fi(t)
log
(1
B2)
-11/2))
1=1
m.
2
1 B1
Σ log
d
Fi((t)
bs+1
B2(1 - B2) 31/
33
m
d
Fi(t)
log
b
(1 32)(1 - -11322
The following lemmas are based on the smooth condition.
Lemma B.4. Suppose that f is L-smooth and Assumption (A1) holds, for any x E Rd.
(x)]l & 2L(1(z) f*).
Lemma B.5. Let By be given in Algorithm 7 and ys be defined in 17 If J is L-smooth, "
CovT B2 and 0 < Br < B2 < 1, then
LCoVd
V (V))) +M, M [V)(),))
Vs 1.
-1- B--1 - 81/32
B.2
Start point and decomposition
Specifically, we fix the horizon T and start from the descent lemma of L-smoothness,
L
((y++1) S f(y)) (VI(y.). ys)
2 y=1l?
yy+t
vs E [T].
(32)
For any given E [T] combining with 18 and 32 and then summing over E [t]. we obtain the
same inequality in 20
f(y++1) S f(x))
7
V)(y),,
b
B1
+ (a,, .. x.-1), V((.)))
9e
B1
(Ae
(x,
xz 13)
(33)
b
1- B
#=1
where we use A, into A and B
20
and y1
C1.
We then further make decomposition by introducing g.
ns
Jst
b.
g+
11
g.
V
b.
go
(34)
A.I
A.2
and
B1
81
(x.
1)).)))
(A. (w. B.- 1), Vs(y.) -ga)
31
31
(35)
17

---

B.3 Probabilistic estimations
We will provide two probabilistic inequalities with the detailed proofs given Appendix F.2 The
first one establishes an upper bound for the noise norm, which we have already informally presented
in (T..
Lemma B.6. Given T 2 suppose that for any (T), E. 9. 9s satisfies Assumption (A3). Then for any given E (0, 1), it holds that with probability at least 6,
|| = MG (o] + "fllg.""). vs E [T].
(36)
We next provide a probabilistic upper bound as shown in for summation of the inner product, where we rely on the property of the martingale difference sequence and the proxy step-size a, in
23
Lemma B.7. Given T 2 1 and ā E (0, 1). If Assumptions (A2) and (A3) hold, then for any X > 0,
with probability at least 1 5,
E. a, 4(1 3111- - s=1
3An9r(1)
9: Va,
T 7 VI E (7].
9sr
+
log
(37)
As consequence, when setting X (1 -1 v1 82/(3n9r). it holds that with probability at -B1)
least 1 1-8, 8,
9s E.
gr(
Σ
77s
gs
Digr,
Vt [T]
(38)
ag
4GT
va.
s=1
where D1 (1-91)v1-B2 log (3))-
B.4 Deterministic estimations
In this section, we shall assume that (36) or/and (38) hold whenever the related estimation is needed. Then obtain the following key lemmas with the detailed proofs given in Appendix F3
Lemma B.8. Given T 2 1. If (36) holds, then we have
max JEls]
| < Gr (8),
max jE(s]
| S Gr(s),
max
11, llx S (GT()))) jE(s]
As E (T].
Lemma B.9, Given T 2 1. b, = (b,.); and a, (a.,)): follow the definitions in 16 and 23 respectively, and (36) holds, then for all E [T] [d].
(T(3)VI-B B2
(GT(s) + v B2
ba.i S
and
a,,i b
ag dg
Lemma B.10. Given T 2 1. Under the conditions in Lemma B.3 and Lemma B.5 if then the following inequality holds,
36 holds,
Fi(l) < F(T), VI [T) [d]
where M = M(1 - B1) and M follows the definition in Lemma B.5 F(T) is define by
2M2 e
TT + oîT (lsill + TMJ)
(I TNT)
F(T) = +
(39)
We move to estimate all the related terms in Appendix B.2 First, the estimation for A.1 relies both the two probabilistic estimations in Appendix B.3
Lemma B.11. Given T 2 suppose that (36) and 38
hold. Then for all t [T'.
A.I
Gr(
3
1
g.
DiGr D2Gr (t)
g+
(40)
4g
Va
b,
where Dj is given as in Lemma B.7 and D2
n-1-22
1-8
18

---

We also obtain the following lemma to estimate the adaptive momentum part B.1.
Lemma B.12. Given T 2 if 36) holds, then for all E [T].
B.1
S
73 s=1
9x
+ (Dagr(t) D4)
ma-1
+
m.
+
DDGr,
(41)
va,
b
b
where
D3 2 / B2
2nvd
D₃ = cD3
D3
(42)
(1-31)3
B2) - 31/
Proposition B.13. Given T 2 1. If is L-smooth, then the following inequality holds,
2
{f(x)) + A.1 B.1 D6
m,
+
D
9x
ve E [T)
b
b.
where Mmax is as in Lemma B. and
L1f + 4
3Lm²²
De
Dj
(43)
2(1 31)²
2(1
31)
Proof. Recalling the decomposition in Appendix of f and (17). we have
B.2
We first estimate A.2. Using the smoothness
L
[V g= L
-xal
[x, xz-1
(44)
Hence, applying Young's s inequality, 44 and (30
17s gs
(yy.))
9s I 1) llg.
ff(y)))
9x
bg
b
1 g.
Ln 2
L
Ln
9x
vf(.))11
||00
Iz-1|1
+
(45)
2L
b.
2(1
31)
2(1
31
b,
Recalling the updated rule in Algorithm
and applying (9) as well as (30).
m
x
xz-1
1--1
n
(46)
b__
Therefore, applying
455
(46) and 31 E 10, 1). and then summing over & E [4]
LTj²
m
Lij²
gg
A.2 <
(47)
2(1
B1
b
2(1 31
b.
Applying Cauchy-Schward inequality. Lemma B.I B1 E 1)
and combining with
(46) Emax 2 and
81
B.2
| | - .z- -1,-111lV/ (gy.) - gall
1 31
L Xmax
Σ [x, CG x1-1112 <
L
max 11
m
(48)
(1
)
11
31
b
==1
Finally, applying the basic inequality, Lemma
B.I and 446
C
L
1/
9s by
T
A 2 ||,,, 12-1
(1
81)²
s=1
Ln²
g2
2
Lnj 22 max
m b__
(49)
(1
31)
b
(1
3
Recalling the decomposition in the desired result.
(34 and
(35
then plugging
(48 and
(49 into
33
we obtain
19

---

B.5 Bounding gradients
Based on all the results in Appendix B.3 and Appendix B.4 we are now ready to provide global upper bound for gradients' norm along the optimization trajectory.
Proposition B.14. Under the same conditions in Theorem 3.1 for any given ó (0, 1/2), holds
that with probability at least 1 28,
|| S G. s G²,
|| s (9T(1))² 9j,
WE [T+[+1]] +1,
(50)
and
| < - Σ
1/5
9x
VI E [T],
(51)
va.
where G is as in Theorem 3.1 and Gt, G, GT are given by 19
Proof. Applying Lemma B.6 and Lemma B.7
we know that (36 or 38 hold with probability at
least 1 - 8. With these two incqualities, could deduce the desired inequalities (50) and (5I).
Therefore, (50) and (51) hold with probability at least result in Proposition B.13 which leads to that for all & E [T],
26, We first plug (40) and into the
(r(t)
9s Vag
2
9s
f(y++1) f(x1) +
+ Digr + (D291 (t)
4GT
2
b,
==1
1') + DGG, + Do
1-1
+ (DDGT(1)+
Σ
m b
+
m.
Σ
m
(52)
b
b,
Next, we will introduce the induction argument based on (52). We first provide the specific definition of G2 as follows which is a constant determined by the horizon and other hyper-parameters but not relying on! t
G = (T(((a) - -1+)+ + 48M log
T
16M, LCoond
F(T)
log
1 1-31 B1
1
37
3T.Co 8(Mr0o + tco)
L.od
(((T)
+8
log
B2
(1- B1) - B1/32)
4 P-p
72M Lo, .nd
(T+F(T) )
+
2
-p--7
33 31)²(1 - -B1/32)
log
832
18M I.Cnd
(++((T) )
12
4T2C3d
+2
log
+ (1 (1- (1 -31/32)
(53)
B₂(1 - 31) - -B1/32)
554
The induction then begins by noting that G ||@ 12 (T((((x) - fr) s G2 from Lemma
B.4
and 53). Then we assume that for some / E [T].
G, S G,
Vs [t]
consequently Gr(s) s Gr. vs E [t].
(54)
Using this induction assumption over (52)
and subtracting with f on both sides,
1
9$
f(u++)- - s f(x1) fr
+ +DGGr (D2gr + +7)
4
v a,
b
s=1
2
+ +DaGr + DA)
Σ
m,-1 b.
+
m
+ D&G + DB
m&g
(55)
b
#=1
Further, we combine with Lemma B.3 and Lemma B.10 to estimate the four summations defined in
Lemma B.3 and then use G < Gr I 2Mr (oo + o1 GP/2 + G) to control the RHS of (55)
f( f < 4
g+ Va
+ D. + D2 + DzH(G),
(56)
s=l
We further deduce
in Theorem 3.1 based on 53
20

---

where H(G) = 51 GP/2 + G and D1, D2, D's are defined as
D1 (xx1 - / + 2M
D2 2M + Dj
4 (Mrro + D.) (1 11-13 31)
D6
F(T)
dlog
1- 82
Ba - B2) -31/32)
(1 (1- B11B2)
D3 = 2MT D1+ + 1 B2
D2d
2Dy(1 31)d
[(TT)
18 ]] + D3.
+ 32(1 82)(1- - -11/32)
log
Applying Lemma
B.5 and Lemma B.4
| 11 I 2//V f fy + +MM² S <4L(f()(+1) - f*) + 2MM.
(57)
Then combining 56 with (57).
9++1 1 < L
9s
+
4L(11 + D2) 4LD+H((G) + 2M2.
va
Applying two Young's ss inequalities where ab
I
a²
b²
and ab I 4-p -ー + b² Va, 20,
2
2
G
G²
|1 5
L
1/8
+ +4L(D, - D2)
4
Va,
s=1
4-
+ 161,2
+
p
4Loy D3)
2M
(58)
Recalling the definitions of D,, E [7] in 38
and
43
With a simple calculation relying could deduce that G2 given
on n CovI- - B2, S 60; Emax 1/ 32 and
B
B2
in 53) satisfies
4 4-p - (4Lo)
G = DD 12) + 321.2 +
+ 4M2.
(59)
2
Based on (58) and (9)) we then deduce that || < G². Further combining with G.+1 in and the induction assumption in (54).
[9]
G S max( G.) < G.
Hence, the induction is complete and we obtain the desired result in (50) quence of (58), we also prove that (5T) holds.
Furthermore, conse-
B.6 Proof of the main result
Now we are ready to prove the main convergence result.
Proof of Theorem
3.7
We set T
(51) to obtain that with probability at least 25,
T
|g
7
gx
S G
||g++112 G
(60)
Then, in what follows, we will assume that both (50) and (60) hold. Based on these two inequalities,
we could derive the final convergence bound. Since (50) and (60) hold with probability at least
1 - 28, the final convergence bound also holds with probability at least 1 - 25. Applying a, in (23
and (0). we have
||a.||x0 max EE/d]
(1- (2)(G(())) +
max ic d]
(1 32)
85 93, (gr(s)) +
<
(1 - 32) Σ
Gr /1 1
cx
Vs E (T).
(61)
j=1
21

---

Then combining with the setting and in (6, we have for any E [T},
Cov 3:)(1 82
Covl - B2
a 00
Grvi- 1 192 +
92] (1
1-
GT + EOV $2
We therefore combine with (60) to obtain that with probability at least - 20,
T
G
20 + 20fG" +
2G
cT
9g 12
+ +co
log
(62)
T
TLC1
V1 B2
s=1
Since 82 (0. we have
B2
log 32 log
5
32
32
T32
where we apply log(1/a) S (1 a)/a, Va E (0, 1).
With both sides multiplying T, we obtain that
log (1/3I) c/B2. Then, we further have that when B2 c/T,
log T
log T + 32
(63)
Since 0 31 < 82 < 1, there exists some constants E,, E1, > such that
(64)
32
3/2 82
Therefore combining 63 and 53
could verify that G ~ O (poly(log 7)) with respect to T. Finally, using the convergence result in (62). we obtain the desired result.
C Convergence of Adam without corrective terms and RMSProp under smoothness
In this section, we will prove the convergence bounds in Theorem 3.2 for Adam without corrective terms and RMSProp, which are adaptive the noise level σg. We first present the algorithm.
Algorithm Adam without corrective terms
Input: Horizon T, I1 E Rdd 31, B2 [0, mg = vo = 0a, n, 0, = eld
for 1.... .T' do
Draw new sample 2, and generate g. = g(x,,
m, 81 m + B1 gs;
V, = 820,-1 + (1 -1 32)g.:
#++1 = V. 11 m. (v EE;;
end for
Remark C.I. Setting 31 0, Algorithm 2 reduces RMSProp.
Then, will state the formal version for Theorem
Theorem C.2 (Adam without corrective terms/RMSProp). Let T 2 1 and (xs) be the se- quence generated by Algorithm [ Assumptions (AI)-(3) hold, and the hyper-parameters are given in (6, then for any given ó (0, 1/2), holds that with probability at least 1 - 28,
T
GA (P(++o8)) + 62 + to o + G Eo)
6
T [V(())))
so
(65)
T
/T
where G is defined by the following order with respect to T,E0.
(
log 2/2 (T/(co)))
max
(
(66)
1-31
'The detailed expression of 6 could be found in
88
22

---

Remark C.3. (I). Setting 31 = 0. Theorem then shows that RMSProp with the hyper- parameter setup O can also find stationary point with the convergence rate given in (65).
(2). The convergence rate in Theorem C.2 is of order O (1/T + ou/VT) which can be accelerated to (11/T) rate when dg is sufficiently low. This form matches the ones SGD 4 and AdaGrad 2 [9]. well the lower bound for first-order gradient method [ non-convex smooth opti-
mization with affine variance noise up to logarithm factors.
C.1 Proof details
To start with, we follow the same notations of Mr, GT, in 31 and define
b. (bn,e); v 1/2,-1111 (1 82)g +
a (ās,i); V B2
B2) (9T (1)
(67)
We also follow the definition of ye in 17 and obtain from Algorithm 2 that
9x
31
b
y y -
+
1d
2 (x. x2-1).
(68)
b.
1 B1
b
Then, we have the following claims. Proposition C.4.
Setting 1)- and = CovI- the results in Lemma B. Lemma B.2
Lemma B.3 Lemma B.5 Lemma B.6 Lemma [.8 and Lemma B. 10 remain unchanged.
Proof. Using 7)s =1 and following the proof for the above lemmas, it's easy to verify that these lemmas still hold.
The result in Lemma
B.9 can be improved to the following one.
Lemma C.5. Given T > 1. b. (ba.c)s and ā, (ā.,i): are defined in 67 and 336 holds,
then for all E [T], E [d].
CT(s)/I-Br B2 and
1
1
Gr(s)VI- 82
bu.i
b
Based on these results, process generated by Algorithm 2
able to show that the gradient norm is bounded along the training
Proposition C.6. Under the same conditions in Theorem C.2 for any given 5 (0, 1/2), it holds that with probability at least 25,
| 2 < G2,
1 GT()) s G.
We + +1].
(69)
and
1g++ s -2 Lm
9z
Vt [T].
(70)
Vā.
where GR, &r are in 88
Proof. Let á, 6.-1
la. We also start from the descent lemma and and use (68
f(v++)) S f(x1) + Σ
Vz..).
g+
31
c (x. x 1), vf(H.)
b.
sml
sm
B
{ ①
(x.
Fz
(71)
b
The following estimation is based the probability event in Lemma B.6
23

---

Bounding A.
We first have
ys
b
94 V Vy..))
b,
(72)
am
A.1
A.
Introducing à defined in 67 into A.1
S.
A1
got
9
9x
(73)
va
as
a,
b.
A.1.1
Á.1.2
Following the proof for Lemma
B.7 with 7)s
17. obtain that with probability at least 8,
A.1.1
(t((
Σ
9x
log
T
vt [T].
(74)
4V1
32
Setting À vI /2/ (3m9r), we obtain that with probability at least - 8,
log Using Lemma C.5 and following the similar deduction for bounding (A.1.2) in Lemma B.11 have
A.1.1 <
(t)
(t)
Σ
9.
3n9T
T
Vt E [T).
(75)
49T
V..
2
1.1.2
11
+ +
1
9+
(76)
Va.
b
Plugging
75 and 76)
into
73
we obtain that
A. S
(T(
3
Σ
gs
3
log
T
+ nT
329T(()
Σ
9r
49T
Va.
B2
6,
(77)
The estimation for A.2 similar
(45)
and 47
Using
and Young's inequality,
17 g.
fzy.),
g=
1
vf(.))11
Lnj²
g
b.
2L
ba
L1j²
9r
<
I xx--111
+
2(1 B,)
2
6,
Thereby,
A.2 <
Ln²
m
Lr
9.
(78)
2(1
B1 )2
b
b
Bounding B, Č.
Following the same decomposition
35
with A, replaced by Å.,
3
3
B
A C (x. - 2.-1).0.)
+
(a. Fz- Vf(vs) g.
1- 31
1
B
s=1
B1
B.2
(79)
We define
0
Å (x, xz-1).g.).
Since 7) = 77, have the following decomposi-
1-3,
tion
1
n13
1
Σ
1 B1
b
à
m,-1.99 9+
31
a
b
m
1
9.
(80)
Σ>
24

---

The additional Σg in 159
vanishes. Then, using Lemma C.5
and Young's s inequality
51
(Gr(s) - B2
Σ
M
i=1
21 82)
(s))
m 1,
"1
(1
B1)²
17
9.
(t)r(( VI 132
m,
1/
(81)
8
vd, a
(1-B1)²
b
Similarly, using Lemma
C.5
and Young's s inequality
Σg
7
9x
(t) B2
m
(82)
8
(1-31)
-
Then, summing up
81
and
82
over E [1] and combining with (80)
B.
7
9x
2T)T(() 32
Ma-11
M
2
(83)
vā.
11)
b
ba-1
Following the similar deduction in
488
and using Lemma B.I
we have
B.2
LE
max max""
m
Laj²
(84)
31)2
b
32
B1)
Using Young's inequality and Lemma
B.
Č S
Lm
9a
LB?
A
12-1
6
(1 B1) #=1
8=1
Laj² 2
< L1)²
+
max
m.
b
(1 B1
b
$=
#=1
< Ln 2
Σ
9s
Ln²
m
(85)
b.
B2 B1)²
b
8=1
Putting together. Lemma B.6 and 75
Noting that the above results are established based on probability events in
and
Hence, plugging (77). (78)
83
84
into and using /3 < and
85
holds that with probability at least 1 - 20, for all [T'.
Gr(() 1
37/
T ④
f(U++1) < f(x1) +
+
log
49T
2
V
32
s=1
121V1-B329r 32Gr(t)
L12
m
(1-31)2
2,3(11
B1)3
b
s=
2 W - (2
m
+
7V - B2Gr(t) +
3T,/²
gx
(1 (1-31))
b,
b.
Then, combining with Lemma B.3 and Lemma 10 using 7) = CovT A2, we obtain that with
probability at least 1 - 25, for all f E [7].
f(y++1) < f(x1) +
(T(() 4GT
g=
+ +EG + E2G + Es.
(86)
Va.
where the coefficients are defined as
T
4Co
F(I'
Ei 3C0 log
E2 d
Co +
log
32(1 31)(1 31132)
37
5LC2
3LC/
F(TT)
Fig d
log
(87)
21 - 31)(1 B11
2(1 - -31/32)
33
25

---

An induction argument. Noting that (86) holds with probability at least 1 20 for all t E [T], then we will provide an induction prove the desired result based on (86). which also holds with probability least 1 26. We first provide the detailed expression of G² and Gr as follows:
(4-1) p) F (8 Ra))
=== =8)((())))))) 1*) + 128T F2)²
+ +16LMT(B) + E2)0o + 8LE + +4M?
Gr - Mr MMMMV02 20g + 2070r + +20
(88)
where E1, E2, EE are defined in 87 and M is as in Lemma B.5 The induction then begins by noting that G. || 1| S ( ( - (*) s G from Lemma B.4 Then, we assume that for
some E [7],
G. C. e [t]
consequently Gr(s) S Gr.
As E [t].
Using this induction assumption over (6) and G - 2Mr (oo + to o, Gp/2 + +
f(g(+1) f(x1)
+ 2M Bz) (on + Gp/2 + +0) E3.
(89)
Va.
Following the same result in 57 we have
19:+1 1|2 < (L(((((+1) - f²) 2M2.
(90)
Combining with (89) and 90
1 212 S (L()(a))- Ln
9x
Va.
+ SMTL(Ei + Eb) (00 + o
GP/2 G + 4LE3 2M
(91)
Using two Young's 's inequalities where ab s q² and
ab < 12 - + 2. Va,
G 4L(f(x)) - f*) Ln
1g.- 112 s
+
Σ
g=
+ 64LL + E2)²
2
Va.
a=1
+ (4
p)
गー
(SLo) + Ea))= 8LM + E2)ou + 4LE3 + 2M
4
< 62
(92)
where the last inequality comes from the definition of G in 88 and we obtain the desired result in 669 Furthermore, consequence of (92), also prove that
Hence, the induction complete
70 holds.
C.2
Proof of the main result
Now are ready to prove the main convergence result.
Proof of Theorem C.2 In what follows, we will assume that Proposition (.oiiion//C6oohldee Hence, the final convergence bound also holds with probability at least 1 26. We set t = T in (70) to obtain that with probability at least 25.
T Ln
T
Lm
g$
< 6
g 5
(93)
V
8=1
Using Lemma B.6
we derive that Vs E [T].
|g.11² < 11 + 2M + +2 +o))
(94)
26

---

Applying ā, in 67 [T].
Proposition
C.6
994 and CovI-52 coVI- - B2, we have for any
E
0 l0c
12 (1- (1-
max iE(d)
1)
17
(1 - 32)
3 |l 1|2 v1 B29r +
"
Mr
Mro v 2T GT + E0
2(1 + of) Σ
|لا1 +
(95)
Co
Co
j=l
We therefore combine with 93 to obtain that
G
2
\
Mr.
2(1 of) Σ
19;12 Mroooo/1 2T Gr + 60
LCo
f=1
G'M3 + +of)
$
9
(MrooV2II
Gr + tG0
120
LCg
which leads to
T Σ 10
2G*M2 of)
-GT + +co)
2 2v2G2
(96)
T
L2C]
LCo
VT
LCo
Following the result in 633 and 664. we show that when .3 = 10l-l-cTT G2, Ôr ~ O (poly (log T))
with respect to Finally, using the convergence result (96). we obtain the desired result.
D Proof of Theorem 4.1
In this section, shall follow all the notations defined in Section 6 Further, will add two non-decreasing sequences (c(=2) Ja21 and (c(') 222 follows
cla) =o LgG L Lo + Lg G. Lo/L,), 1 1.
(97)
D.1 Preliminary
We first mention that Lemma B.1 Lemma [.2 and Lemma BB3 in Appendix B. remain unchanged since they independent of the smooth condition. Then the first essential challenge is that need to properly tune 7 to restrict the distance between #2+1 and æ. ys+1 and ys within L/ for all 2 1. The following two lemmas then ensure this point. The detailed proofs could be found in Appendix G
Lemma D.1. Let x., Ys be defined in Algorithm 7 and 121,
17
1f0 S
31
<
32 < 1, then for any
4d
max{[les41 - xoll. 1ly. 2xll. 2.l1,113e411 4oll3 S VV
(98)
B² B1) - 82) -31/82)
As consequence, when
4d
S F
F
(99)
82 (1)(13))
then for any 1. all the three gaps in 98 smaller than L/
27

---

Lemma D.2. Ler I 1/( where F is as in Lemma D.1 If f is (Lo, Lg) Lg)-smothh. then for any
$21. 1,
[V/(,))I v To/ + IV/ + [ (/(l))); ||| [V(x,)] 1 Lo (3.) + V y )||
As a consequence, for any 1,
[V)().) - vf(x,))l S () yy xzl1: [Vf(v++1) - vf(y))l - C. |1y,41
Voll. (100)
((,) f(w++1) f(y.) (Vf(g.). v.) - 2 yst1 yzll.
(101)
In the generalized smooth case, Lemma B.4 does not hold. In contrast, we provide a generalized smooth version of (50] Lemma A.5], which establishes a different relationship between the gradi-
ent's norm and the function value gap. Noting that when 1, Lemma D.3 reduces A.5].
50 Lemma
Lemma D.3. Suppose that f is (Lo, Lg) -mooohh and Assumption (Al) holds. Then any æ E R
[ max (T f"), (AL,) (4)
D.2
Probabilistic estimations
The probabilistic inequalities in 36 and (37) remain unchanged since they do not rely on any smooth-related conditions. However, shall rely different setting of X in (37) follows.
Lemma D.4. Given T 2 and 5 E (0, 1). Under the same conditions of Lemma B.7 if we set
A - (1-3))vl /2/(3171 where H. as in (II), then with probability least 1 0,
Σ
Jo: E.
9r(1)
Σ
9s
+ D2H.
AA T)
(102)
a2
47
Va
where Dj is given in Lemma B.7
The bounds the four summations in Lemma B.3 also remain unchanged. However, the upper bound for (t) should be revised by the following lemma. The detailed proof could be found in Appendix G
Lemma D.5. Given T Under the conditions and notations of Lemma B.3 if f is (Lo, Lg)-
smooth, 1j = CovI 32. (36) and (99) hold, then the following inequalities hold,
Fi(1) S I(), V (T) 8 [d].
(103)
where J(t is defined as
2M
ogt + 07 [1g + +(M))* + (1 + (.,))
I(1) = 1+
(104)
2
and M, = Coc( V 1//
It's worth noting that [tt still random relying on the random variable c.a).
D.3 Deterministic estimations
Note that (11 in Appendix [B.4]remain unchanged since it's independent from any smooth-related condition. In terms of A.1, the only difference is using H. to replace in (40) choose different À in (37), leading to
A.1 5
Gr(()
3
7
g+
+ + + D2GT
Σ
ga b
(105)
4H
Va
We also establish the following proposition which a generalized smooth version of Proposition
B.I
28

---

Proposition D.6. Given T 2 1. If is (Lo, Lg)- smooth and 999
holds, then
f((+)) A.1 B.1
Da(s)
m
D7
8))
gx
vA E (T),
(106)
b,
b,
where Emax is in Lemma B.1 and De(s), Dr(s) are defined as 6
C. vf m
32 172
De(s) = 2(1 31)2
D7(s) = 2(1 31)
Proof. The proof follows some parts in proving Proposition lemma [01]] in Lemma D.2 and sum over 8 E [4] to obtain that
B.14
We start from the descent
f(yo+1) f(x1) +
V ffy)), Mett
ye) +
Σ
Mott - -yll2
2
==1
==1
((3)
9.
B1
17/ (1bbo-1 -
= =f(x1) + A
?7
Eg o (x,
E3 x3-1)
2
b.
1 -
31
m--1b=
(107)
where A and B follow the same definitions in (33). We also follow the decompositions in 34 and 35 We could also rely on the same analysis for the smooth case in (47) but the smooth parameter replaced by c(*), Hence, we obtain that
(x))
(x) n
m
gg
A.2
(108)
2(1
31
b b
2(1
31)
b.
Similarly,
2 CL 17²
max
m
B.2 <
(109)
(1
B1)
b
Noting that C' differs from with L replaced by c.u) we obtain that
Hence, relying on similar analysis in
49
((1) 17²
ga
m
C
max
(110)
B1
)
b
B1)2
b
Combining 107 with (108),
(109 and 110
and noting that LL
<
(())
from 97 we thereby
obtain the desired result.
D.4 Bounding gradients
Based on the unchanged parts in Appendix B.3 and Appendix B.4 and the new estimations in (105) and (O6),, we are now ready to provide the uniform gradients' bound in the following proposition.
Proposition D.7. Under the same conditions in Theorem that with probability at least 28,
4.1 for any given 8 E (0, 1/2), it holds
|lgel S H, Gr(t) < H.
c.a) < (1) < C, Vt [ + +1,,
(111)
and
f(y++1) -
n
9x
+ Å,
W W (T),
(112)
Va.
where H, H, L are given in and A is given in 115
'The notations are different from De and Dy detined in
43
29

---

Proof. Based on the two inequalities 33) and 102). we could deduce the final results in 111 and
(12).. Since (36) and (I02) hold with probability at least 28, we thereby deduce the desired
result holding with probability at least
25. To start with, we shall verify that (99) always holds.
Recalling 1) in 10 and F Lemma D.1
B2 - - 32) - 31/B2) FS
1 Lω
F = Cov 82F S
4I3dd
Hence, we make sure that the distance requirement in Second, plugging (T05) and (T) into the result in (T06).
(8) always holds according to Lemma D.1
Gr(()
t
9x
gs
f(y++1) $f(x1) +
+ +DHH + (2
47H
2
Va
ba
1=1
9g
m
m,
+
(s)s)
+ (Dagr(t) + D4)
+
b,
b
b
+ D&G,
+
Do(s)
m&g
(113)
We still rely on an induction argument to deduce the result. First, we provide the detail expressions of H. H as follows which determined by seper-parameters $1, B2 and constants Eg, d, T, 6, Mr.
M log
Mrd
(TT
A : f(x1) - f + 1- B1
log
8
1
31
3/
(MT + e)d
((T)
2Egd
log
B₂(1 - 31) - 31132)
OT
V(1 31) B1132)
3E
{(T)
5EGd
(TT)
2(1 - 32 log
212(1 - (3 - B3) log
(114)
13
2 + (ALoHt) 3 + 4L + (ALgA)
H = Lo + ( (
+ (LL
2-q
+
V
//LoH.
(115)
where Eo > is a constant and ((T is a polynomial of given as
2MG oh + ofT (lIs + TMO" + T (19 +1 "
J(T) = 1+
(116)
and M = Eog 1-8:/35 The induction then begins by noting that from Lemma D.3 and H in
115..
G1 1= < (f f*) + (4I,(((Z))) ر) (To((((m)) H.
Suppose that for some E [T'.
G, S H, Ys E [t]
(117)
Consequently, recalling Gr in
[(a) ((y) in 97 and H. L in (1I.
Gr(s) S H,
C(a) < (()) L,, Vs E [4]
(118)
We thus apply 118 to 113)
g: |
f(u++1) <f(z1)
17s
gs
+ DDH + D2H Σ
+
Dr(s)
Va.
b,
b,
sm1
am1
+ +D2H + D4)
m,s11
+
m, 1 b,
11)
2)
+
DrM +
Da(s)
m,
b,
b.
s=1
(119)
30

---

Further recalling the setting of Co in 10 with simple calculation it holds that,
CoH S CoH v En,
CoL En,
C/ Fg:
Cocn S Egeo-
(120)
Therefore, combining with 118 120) and M, in (104) we could use the deterministic polynomial (t) to further control J in (104.
d
d
M, Coly
Bay
M, J(I) < 30)
B1/B2
1 1-31//2
Fi(t)
[(t)
((T)
log
S log
I log
W < T,i [d].
B2
B1
Then, we could use (T) to control the four summations Lemma
B.3 which emerge in (19).. In
addition, we rely on = CovI- B2 and the induction assumptions of (117) and (118) to further upper bound the RHS of (119), leading
f(y(+1) Sf(a1) f
1
Σ
1
178
9x
3COH
log
T
Co B1
log
(T)
Vaa
- 31
4Co(H cn)d
((T)
2C Hd
log
32(1 - 31 )3(1 - -3)
B2
V(1 B1 )
-31/32)
3C Cd
(((T)
5C3 Ld
[(T)
2(1 - 31)2 log
+ 232
log
B1) - -11132)
35
(121)
Then, combining with 120 and the definition of /1 in (14). we obtain that
gx
A = ((041)) 8r
7
+ H
(122)
a,
Then, further using Lemma D.2 Lemma D.3 and H in 1115
|| || S Lo/ Lng + [V](++))]| + (y++))
s Lo/ L, + (4I,
(4I A
+ (4Ig 41, A c+1 + (4 (14)) VAL + S.
We then deduce that G max G2, |g < H. The induction is then complete and obtain the desired result Finally, as an intermediate result of the proof, we obtain that (112) holds well.
D.5 Proof of the main result
Proof of [4. The proof for the final convergence rate follows a similar idea and some same estimations in the proof of Theorem 3.1 Setting t = T in (112), holds that with probability at
least 1 - 26,
aa Ioo
||g.1]
<
7
Va
9+
í.
(123)
Then, in what follows, we would assume that 111 and (13) always hold. Relying on the two inequalities, we thereby deduce the final convergence result. Furthermore, since (111) and (13)) hold with probability least 1 28, the final convergence result also holds with probability at least
1 26. Using
[1II and following the same analysis in (61).
1-1
aay 1oo < max
(1 B2)
Σ
B 9g, (Gr(1)) + S (H++)VI- 85
Ys [T].
#E|d]
31

---

Combining with the parameter setting in (10)
a
1/ 32
CoVI-
aa
(1 -1- [i) d. 1o0 H. + c0v -2
We then combine with 123 and H. in
obtain that with probability at least 25,
4H
V2 + 0j +²)
cf
T
Σ
g.
TCo
v1
82
+ c0
V
log
55)
we could derive that ft ~ O (log" 1oo
Finally, following the same deduction in
663 and 664
from 114 and the desired results in Theorem
E Convergence of Adam without corrective terms and RMSProp under generalized smoothness
this section, we will provide the detailed result and proof for the convergence of Algorithm 2 under generalized smoothness. First, will provide the formal version of Theorem 4.2
Theorem E.1. Let T 2 1 and 5 E 1/2). Suppose that fxz sE(T is a sequence generated by Algorithm
f is (To, Trg) -mmoohhh satisfying Assumptions (A (A3)) hold, and
S 31
32
1,
B2 = =1 c/T, <= B2
7= Co 32.
Eg
Eo
Be(1 B1) 31/32)
Go S min
Ev.
(124)
H
L
4L3d
where c, c, Eo, Co > 0 are constants, H is controlled by O (log
T
)
and H, H. E are defined
as
Lo/Ta + (1 + (4L, H) x' + (4 - + (4L,p H) I' + v VLLHH,
=
eT c= Lo + Tug [79 H
Lu
H. V2(08 of of H25) log
(125)
Ltg
Then, holds that with probability at least 1 25,
T (v.
H H (6)
Hou
<
(126)
T
T
VT
Remark E.2. (1). The convergence rate in Theorem C.2 is of order Ô (1/T + on/ ////T) which can
be accelerated to ((1TT)) rate when og is sufficiently low.
(2). Setting 3n 0. Theorem E.1 then shows that RMSProp with the hyper-parameter setup in 124
can also find stationary point with the convergence rate of Ō (//T + 0o/ v order.
E.1 Proof detail
To start with, we follow all the notations defined in Appendix C and Appendix
D particularly
G,GGr (r() in 31 and c!²), _(()) in (97.. Then, we have the following claims.
Proposition E.3. Setting ne = and n CovI- Bz, the results in Lemma D.1 Lemma D.2 and
Lemma D.3 remain unchanged.
Proof. Using 7 17 and following the proof for the above lemmas, it's easy to verify that these lemmas still hold.
The specific definition of H can be found in 138
32

---

Based on these results, we are able to show that the gradient norm is bounded along the training process generated by Algorithm@undde generalized smoothness.
Proposition E.4. Under the same conditions Theorem that with probability at least
C.2
for any given E (0, 10,1 it holds
28,
9ell I H, gr(1) H.
c s c LC +
(127)
and
2
7
9s
A+11 S
+ H vt vt [T].
(128)
Va.
Proof. To start with, we shall verify that (99) always holds. Recalling 1 in 124 and F in Lemma D.I
B2 (1) (2) 31/32) F Lg
nF Cov1- 32F S
4L2d
Hence, make sure that the distance requirement in (8) always holds according to Lemma D.I Then, using the descent lemma [IOI] and (68). leads to for any 2 1,
f()++1) S f(a)
gs (y));
A + (atx x.- 1), VS(3))
b,
B1
9x
B1
(Ao
(x.
8. 1))
(129)
2
b
1
B1
The following estimation is based the probability event in Lemma B.6
Bounding A. We first have the same decomposition as in Then, setting À v1 (2/(3))
in (74), we obtain that with probability at least 1 - 8,
A.1.1 <
( Σ
9x
3
log
T
14 E [T).
(130)
4H
VI
32
Using Lemma C.5 and following the similar deduction for bounding (A.1.2) in 76). we have
Á.1.
7
gx
+ +
Σ
g,
(131)
Va.
b
Combining with (130) and
131
we obtain that
A.1 <
(1
3
Σ
g+
31
log
T 1 +n
+ +.y
Σ
4H
Va.
VI
B2
8
b.
(132)
The estimation for A.2 is similar to (108 and 78).
With L replaced by ((3) in 78
(z) 2
2
(x)
A.2 <
m. 1
9x
(133)
2(1 - )
b
2
b
==1
==1
33

---

Bounding B, C².
Following the same decomposition in remains unchangedl.
79 and 80
we first note that the esti-
mation for B.1 in
9+ 2ngr(1) 32
m
m
B.1 S
(134)
vV
(1 (1-B1 31)
b
b b
Following the similar deduction in that
84 and using Lemma
B.1
we can replace I. with L!a)
to obtain
max Cs
(z) 1
m b
m
2
B.2
(135)
31) )
B2
B1)
b
Following the similar deduction in (TO).
we indeed replace with ((0)
in
85
O' S
C
9x b
C
m.--
(136)
31)²
b b
Putting together. Noting that the above results are established based on probability events in
Lemma B.6 and (130). Hence, plugging (132) (33)). 134). (135) and (366) into (129) and using
B2 < and C. ( from 97. holds that with probability at least 26, for all E [T].
Gr(t)
37H
T log
f(y41) S f(x1) +1
+
4H
2
Va.
v1
32
s=1
2m 1 - (2
5C(00 172
m
(1 B1)
31) 2,32
b b,-1
2n/ 1 (1
ma-1
+
Σ
n (2G +
3.
172
g:
31)2
b
2
b,
(137)
An induction argument.
We first provide the detailed expression of i1:
T
H = =f(x)) 5r + 3Eo log
2Fo
5F3
I(T)
dlog
B1)(1 B1/32)
28
81)(1
B1/B2)
B1
2End
I(T")
Eo + 3E3
d
I((T)
log
log
31 31)(1 - 31/32)
13
1
B1/32
13
2M2
+t ||و:|]| + +1i1) )
I(t) 1+
out + oft (1911l + ++M))
.M''= Boy 1 1 B1/32
(138)
The induction then begins by noting that from Lemma D.3 and H in 125).
G = || < 4f f*) + (fI.(f - z"))==z + /Lo(f((11) - ff) < H.
Suppose that for some E [T],
G, S H. Vs E [4]
(139)
Consequently, recalling (8()) in 19 _(u) (v) in 97 and H, L in (1I.
Gr(s) < H.
((0) c(u) < E. vs [t]
(140)
Further recalling the setting of Co in 10P. with simple calculation it holds that,
Č.H < NoH < Eo. C Eo, og < Eq. Coco & Esco-
(141)
34

---

Using 140p.
141
[tt), Mj defined in Lemma D.5
and I(t), M' defined in 138
log Fi((t)
((t)
I(T)
M, s M
S
log
log
Vt S
T.iE.
Using Lemma
B.3
Lemma
B.
and Lemma
D.5
we have
m
d(1
31)
I(T)
log
b
(1 82)(1 B1/
m
d(1 - 31)
[(T)
log
b
82(1 B2) - -B1/32)
31
8mm
I(T)
82) (1 B1/B2) log
(142)
(1
s=1
Then, plugging
140p and
(122) into
137 and using 17
CovT
B2 and
(141
9.
T
A f(y(+1) f <A
A
3Fg log
Vā.
2F
SE3
I(T)
+ (1 (1- 31)(1 B2/B2)
dlog
23 - 31)((1 B1/B22
2Epd
I(T)
3E
I(T))
+ 3₂(1 - 8:)(1 81/32)
log
+
Eo +
log
S H,
2
31/32
(143)
where we use H defined in (18).. Further using Lemma D.2 Lemma D.3 and H
125
10++1|| ll < To/Ta Tu + (4T.g 1++1)* + (4T. 2
+ (4L0A # 4Lg + A441) - VL S H.
We then deduce that G max { Gt, | v Å. The induction is then complete and we obtain the desired result in 127 Finally, as an intermediate result of the proof, we obtain that (143) holds as well.
E.2
Proof of the main result
Now we are ready to prove the main convergence result.
Proof of Theorem C.2 In what follows, will assume that Proposition E.4 holds. Hence, the final
convergence bound also holds with probability at least 1 25. We set = T in 127
2
1
T
9.
< H - A I H.
(144)
Va.
#=1
Following the similar deduction in E [T).
95 with 7j Covi B2 covl -1, we have for any
[ 8o
Mr
1 Mroo 2T + + +
2(1 of) Σ
(145)
1
Co
Co
We therefore combine with 144 and 145
to obtain that
T
4H
1|
<
Mr
2(1 + of)
Σ
|g 112 + M.Too + A
Co
==1
8/12M (1 + of)
411
||gm ||
+
+
(146)
C3
To
s=1
35

---

which leads to
(16FFM + + ( +o)) + 8 (147)
T Σ
g 2
COT
CoVT
Following the result in
63) and (4).. show that when 32 = 11 c/T, H. O (poly(log') T))
with respect to T. Finally, using the convergence result in [177. we obtain the desired result.
F
Omitted proof in Appendix B
F.1
Omitted proof in Appendix B.1
Proof of Lemma B.1
We fix arbitrary E [e]] and have the following two cases. When neba-id 1,
To- 1ba,
we have
nobs-1, = 17. nobg-1. 1.
77-11 bgg
1/5-1 1bgi
When Boba-id Tb.
2 1, let = =3²
Since 0
< 1 - 89 < 1 - 89. Vs 2 2, then we have
7
1 B3
1-
82 (1 - 32) 1
(1- V1+ 32) T-r"
1/-1 1
V 1
132
95-1
31
32
Since ((r)) (Ir) is increasing as grows and r takes the maximum value when s 2. Hence, it holds that
Y
1+ B2)
(1
B2
V 1+ 32.
(148)
1- 32
Then, since 6x-1 S Ex. we further have
by-
6 + 00-1,
+ Vo-
1
(149)
Ex + / B22.-11. 1,5 + (1 - B2)g3a1
E. + 120
vB2
Combining with (148) and 149 we have
b.b,-1. 1, -
11 11bh-111 - 15
1 B2
1.
1/-1ba,4
1b-1
32
Combining the two cases and noting that the bound holds for any i E [d], we then obtain the desired result.
Proof of Lemma B.2 Denoting M = Ej=1 89-2-1 and applying 28 with M and ay replaced by
M and Ij.; respectively,
2
s-1
8-1
Σ
9j.
S M
Σ
g
(150)
1=1
j=1
Hence, combining with the definition of by.s in
(6), we further have for any E [d] and s 2 2,
M 1,1
my 1,2
(1 - 81)
Σ
1=
2a-1-1
93.
/ 1,0
(1 - B2) Σ3
35 1--1-1 09.3
1 3
M グ== $4 00-1-1
03
1 - 31
8-1-j
<
M
VI 12
ビj=1 18-1-3
VI 52
B
j=1
1- 3
1- 8--1 1
1- (311B2)
(1 B1)(1 31-1)
5
V1 - 3
B
1 1
-B1/82
(1 - 31) - B1/B2)²
36

---

where the last inequality applies 31 < S2. We thus prove the first result. To prove the second result, from the smoothness of f.
g - 11g--1 + 9. -9--11 s 9 111 + L xz-1/1-
(151)
Combining with 30 and = CovI - 522
m
1
|00,- - Tz 10c S 975-1
S /m1
Co
(152)
bg-1
(1 32)(1 - B11B2)
1 81/B2
Using
|2,- - xz-1ll S vd - Iz--llaa and (151).
|g < 9- || + LC 1 1 31/B2
S 1111 + LC
1 B1/32
Proof of Lemma B.3
Recalling the updated rule and the definition of b,,s in (16 using c = c2
33) 2 (1 - 82),
02 2 2 + 2 2 (1
-22
Σ
52
3 93.
and m,,s (1 31) Σ 85- -j.- (153)
Proof for the first summation.
Using
I53 for any i [d].
1
Lh. 2 ビラ=1 0 g
S
1-
32
Applying Lemma A.1 and recalling the definition of Fi(t),
log
1+ 2
Σ
1 1- 2 log B2
1
log
Fi(())
1 B2
1 32
.35
s=1
Summing over i E [d]. we obtain the first desired result.
Proof for the second summation.
Following from 153
2
E 39 9js
m
(1 11-3p 32
1 - 82
2
+
Σ 83
s=1
Applying Lemma A.2 and 32 1,
m
(1 - 31)2
1
1
log
1+
3 2 Ja.1
-tlog 32
1 32
(1 3:)(1 B1/B2)
2
s=1
1- 31
((((t)
log
32) 32)
13
Summing over i E [d]. we obtain the second desired result.
Proof for the third summation. Following from 153
2
(1- 31) E5 31 タi
#=1
b2
111
==1
22 - 32) + (1 - B2) ΣØ+1 j= B
3e+1-1
93,
(1 - 3:)² (Ei=1 31 98-5 93.3
20 - 32) + (1 - B2)32 Ej 88
37

---

Applying Lemma
A.2 and using $2 S 1,
2j=1 81 88-3
m od
(1 -1)²
9j.1)
82
1+1,
(1 82)
+ 2===1 82 02- 97.1
5
(1 B1)²
1
82
log
1
Σ
82 fzi
-loog 33
(1 82)
(1 - 31)(1 B1/
31 log
((((t)
82(1 - 32)(1 32)
Summing over i E [d]. we obtain the third desired result.
Proof for the fourth summation. Following the definition of m, from and combining with
153
1- 2j=1 81 93.
m
(1 31)
62
- 82
22 + Di=1 32 97.1
Applying Lemma A.2 and using $2 S 1.
m
(1 11-31p 31)3
log
1+ c
B/ a 2 95.1
-tlog 32
62
1 - B2
(1 (1-B1) B1) 31/32)
8=1
8=1
1
[F((()
log
(1 32)(1 /1/B2)
18
Summing over i [d]. obtain the fourth desired result.
Proof of Lemma B.4 Let a = V Then using the descent lemma of smoothness,
L || 1 < f(z) 2L |/()))]
f()) < (ax) (v)()), x²)
Re-arranging the order, and noting that f()) 2 fr,
[V](=)]] < (f((()) f())) < 2l( f*).
Proof of Lemma B.S
Applying the norm incquality and the smoothness of f.
[v)()))] < [V/((>>]| + (vx.) vs(y,) < [V |ll + Ll æzll-
Combining with the definition of y, in and 152 and using B1 E [0, 1), obtain the desired result that
LB1
LCOld
Vf I + 1- 3
Ix xz-1ll 111 $ [f + (1- 310 31/B2
F.2 Omitted proof in Appendix B.3
+ a. p. Vs E [T]. Then from Assumption (A3), first have Ez, /exp (7)) < exp(1). Taking full expectation,
Proof of Lemma B.6 Let denote 74
||
E [exp(1))] < exp(1).
38

---

By Markov's inequality, for any A E R.
2 exp(A)) - exp(-AA) exp
max [T
Ys 2 =
exp
max % +E|2]
max Y (E(2)
- eepp(AA))
exp (7)) Eexp(-A)7 <exp(-4)7exx(()) exp(1),
which leads to that with probability at least 6,
cT
|I& I log
(oō + oillg.1"). e [T].
8
Proof of Lemma B.7 E (T), i E (d..
Recalling the definitions a, in and 6, Algorithm
we have for any
Gr(s)/I- B2 + Ev 1 B3 (GT(s) +eV 32
S gr(s)v1-13
(154)
Vol + of
92 -
Then given any i E [d], we set
E. Is: 02
gs
X, 7
1/3
o ofllg.11,
As [T).
a
Noting that 9ss a and 7) are random variables dependent by x1 ... 2.-1 and &s is only dependent 2g. We then verify that X, is martingale difference sequence since
E. a,
)
1)s Is: E2, [S.] = 0.
E [x, 21,
= Ez, 7
gs.
a,
Noting that w. is a random variable only dependent by 21, ... 1o-1 and applying Assumption (A3) and Meuchy-Schward incquality, we have
E
exp
21
E
exp
1 Z
0 + of 9
Ex,
exp
of + 1
exp(1), Vs [T].
Applying Lemma
A.3 and 154)
we have that for any A >> O, with probability at least 1 - 5,
31
X,
w
log
4
8
1=1
s=1
<
31
2
92
( +
(g) +
log
4/1 8g
==1
<
31
2
g=
1
log
1
(155)
4
32
Va.
8
Note that for any / E [7]] (155) holds with probability at least 1 - 8. Then for any fixed À > 0, we could re-scale ô to obtain that with probability at least 6, for all E [7).
Σx.
X,
31
Σ
g=
o
ofllg~11 log
T (T)
32
Va
8
Using Vo + of gz P < (r( 8 < from
19
together with (30). we have that with probability
least 1 6,
Σ
17
E. Jo:
< 3 (1)
n
g-
+
log
-
T
Vt E [T].
a.
4(1 3, 31)vI
32
v
==1
s=1
Finally setting x= = (1 v / (3nGT), we then have the desired result in 38
39

---

F.3
Omitted proof of Appendix B.4
Proof of Lemma
B.8 First directly applying 360 and G2 in 19 for any [s].
||& S Mr of +
of [9 || Mr V 0 o. < Mr oB + off S (r(s).
Applying the basic inequality, (36 and My 2 1, for any j E [s]
102 - 2 1 e I 2 (o
कं و 11 |gا I (GT
Finally, we would use an induction argument to prove the last result. Given any E [d] noting that
01,1 (1 (1-11111000000 -2) (sr( Suppose that for some s' [s), U/ & (Cr (s)) / Vj [s'].
U B2 a + 32)ge' S (2(GT (1 (2) (Gr(s))²
We then obtain that v/,a & ( vj E [s]. Noting that the above inequality holds for all i E [d.
we therefore obtain the desired result.
Proof of Lemma
B.9 Recalling the definition of by.; in (6) and letting asii V + in 23
1
No.i
1 A2 19. (GT(s))²
0g,5
baci
V + 00,i
1 32
(GT()))2
9r(S) 32
as Da.s Vusii + B22,-1.1 + (1 B2)
where we apply Lh, & 11 < (s)) from Lemma B.8 in the first inequality since 36 holds. The second result also follows from the same analysis. We first combine with E. SEV1 8 obtain that
to
lE+ - 16-6--1/56 5E 11- (01
32 v 1- 1--1 S Se 21 32) S S B2,
(156)
where we apply va vb Va - b, 40 Sbs a. Applying the definition of b and 0g
V0s.i V0 + (Eg E3-1)
b az.i
b
1
(1 - 32) (gT(s))² - -0--18
+ les E--1
b 1,500
v V0,s + v Ug-1,5
b
(1 (Gr(
+ c/1 - B2 (gr()) +c)11 32
b b
Vūsit + U0-1,
b
15-1,
where the second inequality applies 1,-1, S (G)( in Lemma B.8 and the last inequality comes from (x) < 0s.i-
L
Proof of Lemma 1.10
Applying the basic inequality and 36). for all t [T] E [d].
9
2
1g.11 2 < 2
(1g.1
+ - 2M oft of
| I
||0.11
sm1
(157)
Combining with Lemma B.2 we have
LCovds
LCavdl
gall
P
< Σg ||g
St. ||91||
V1 B1/B2
V1-
LC
Σ 1gg.1 2
t.
|| |l
/1 - 1/1-B1/8 B1/B2
Further applying the definition of Fi(t) in Lemma B.3 it leads to Fi(1) S F(1,, E [d]. Finally, since F(t) is increasing with we obtain the desired result.
40

---

Proof of Lemma B.17
First, we have the following decomposition,
gx
A.1
7
T]s
9s:
7
Jos
9x
(158)
a2
as
a2
b,
A.1.1
A.1.2
Since 36
holds, we could apply Cauchy-Schwand inequality, Lemma B.9 and GT(S) 19 to obtain that for all & E (T).
S
(t), vs S t from
(T(S) 32
A.1.2
<
1s
10,,90,1
as
by.i
1=1
8m
im
NsHadd
d
(sT(
(1 - 32)
i=
i=1 a=1
30
gx
n/T (1) I 32
9s
1
a
31
b
Finally, combining with 38
for estimating A.1.1, we deduce the desired result in (40
Proof of Lemma B.12
Let us denote
(A.
(x, F, -))))
where A, is defined in
1-
We have
31
7--171811
9s )
31
(
?e
7--1
2 mm.-199. )
Σ <
A
B1
b
31
b,
b
31
fle
8
1)s
17
mm-
+
3 M2 mm=-1.9h Io
Bi
b
1
B1
b
Σ
E>
81
(16-1 - na)
m,,1
(159)
B1
by-
Eg
Since (36) holds, we could apply Lemma
B.9 and Young's incquality and then use (14)).
30
B1 [0. 1) and (s) & (t( < (t + St.
B
(r(s) VI B2
Σ <
Do.
B1
ag.bbas
i=1
37 32)
(ST(
m 1,
1/8
Σ
0g
(1 (1-8,)2
ag
D2
1=1
1=1
gs
2( (t) + +E) I Br
m
+
(160)
VO,
(1 {1-3))3
b
Using the similar analysis for Σ,, we also have
31
VI- 32 (s) +c) -0a, m,-
Σg
31
i=1
7
g
2 2 + +c) = BB
m
<
(161)
8
a,
(1- B,)
b
41

---

Then we move to bound the summation of Σ3 over 12, since mo = 0. Recalling in we have the following decomposition.
71
1-
52
m 9s>
Σg -
31
96-1
1
59
b
23.1
m131
B2
82
9s:
m
(162)
1
B1)(1 191 98-1)
bz-1
32.2
Noting that gs ll I G. & Gt. Vs S t.
Then further applying Cauchy-Schward inequality and
Lemma B.2
(1- (1-B1)(1 - 18- (1 32)(1 31/32)
V 32
m go!
S -V-11150 311lga11
m
S Vdday
b--
ba-1
Hence, summing Σs.1 up over s E [t]. applying $1 E (0, and noting that Σs.1 vanishes when
VdnGGr
1- 1
1
Ex1 <
1 1- 1 (1-B2)(11 -2)(1-B1/36
1 - B7
1 - 89
VdnGG
$ V(1- /(1-31)3(1 B2) - 811B2)
(163)
Similarly, using |g S G. s G., Vs < and -55-1
2 1- -1.
go.
m
$
m
$ <VdG,y (1- (1/3-)
1- 88-1
b,_
Hence, summing Σ3.2 up over [t] and still applying 31 E [0,1).
VdnGG.
3a. S 1- 31
1 35
v - 32 83-1
V (1-32)(1 - 31)
x=2
VanG.
VdniG.
(164)
- (1- BL (1) - 31/32)
V(- B2) - 31/82)
Combining with 162 b.
163) and 164). we obtain an upper bound for Σt= Ez. Summing 159
(60) and [16] up over E [4] and combining with the estimation for Σ. 2==1 Eg. we obtain the desired inequality (41).
G Omitted proof in Appendix D
Proof of Lemma D.I Recalling in [52 we have already shown that
d
| x. S Vdlx 2x s <n/ B1) 81/32)*
As 2 1.
(165)
Applying the definition of y, in 17 an intermediate result in (65) and 31 [0,
B
d
ly. x.,
xr x. ill 1 31 (1 B2) 81/32)
1 1.
(166)
31
'The inequality still holds for since 211 y1
42

---

Recalling the iteration of y, in
18
and then using Young's 's inequality
1 -v - 2m
gs
+
2
I Tab.-1
1
1 2, 111
b
(1
B1
)
T/s-10 b
(*a)
Noting that 90.1/Da.5 S 1/v1 32
from (16
we then combine with 30 to have
d
2n
(+) - 2m,
1- B2
(1 - B1) (1 32)
Applying Lemma B.1 where 522 "max
1/B2 and (165)
2n 87 2 maxd
2nfd
(**)
(1 - (1) (2)(1
-31/32)
-
Summing up two estimations and using 0 S B1 < 32 < 1, we finally have
4d
|yy+1 - yull 1 7 3,(1 31) 82) 31/
(167)
Combining with (165). [66) and (16]). and using < B1 < B2 < 1, we then deduce a uniform bound for all the three gaps.
Proof of Lemma D.2 Under the same conditions in Lemma D.I
we have
ly. x.ll
1 - yol S Ln
L
Then, using the generalized smoothness in
[v/(' <
v((x))) (40 / (=))(()ll))))) xx
< <
+ Lo/ Lgg
We could use a similar argument to deduce the bound for V ffx,)) Further, combining with ((#)
and (y) in 197,, could bound the generalized smooth parameters as
Lo + L, V f(=))) S Lo + L.G = c()),
Lo Lg (y.))) < Lo + (g [V Lo)Lo)
Lo L(v).
(168)
We could then deduce the first two incqualities in (TOO). Finally, (TOT) could be deduced by using the same argument in the proof of [00 Lemma A.3].
Proof of Lemma
D.3 Given any x E Rd, we let
-= x -VVf(x)
Lp + Lg max (r)
From the definition of could easily verify that || x -[ 1/Lg. Since f is (Lu, smooth,, we could thereby use the descent lemma in 50 Lemma A.3] such that
Lo + Lgl [f(())))]
f()) < f(x) (Vf(z), x)
| - 2=||2
- -f(x)=7[Vf())) (Lo L,IlV[(=))1)))
|V < f(z) [Vf(2))
2
Since f(i) 2 f", when [ 0, the desired result is trivial. Let suppose Vf(x)] 0.
43

---

Case [Vf(z)] > ||V](=)]
fx) 1
[ 2L
21.9 f((x) f()) f(x) - s"
2
When [[f(=)]] < Lo/ Lg. it leads to
[V](2)]1 [Vf(z)]12
| f=)))1112
2L [ + 2L, S f((x) -f.
4ho
/Lo
When [Vf(()] 2 Lo/ Lig. leads to
V (x)) 12-
2L (xx)) 8 2Lg (1(x)- - --
4Lg
We then deduce that
[V)(=)]
& max
-f -ALo(f(=)-f-)) - -
(169)
Case 2 [V]
[V)(]]] We could rely the similar analysis to obtain that
[V/())] max {sL,(f(=) f*), (4Lo(f())
(170)
Combining (169) and 170). then deduce the desired result.
Proof of Lemma D.5 Recalling 152
then obtained that when 17 Cov1 B2,
d
| x.-1 all vdllz, x.-11lo0 S Cop.
(171)
-B11/2
Noting that when (99 holds, we have
|g < 9 || + gg ---1
S 11g.- + (Lo + L,11ga-11(7]11 x2-1ll
| || + CoC (x)
d
|| + Co./
d
c/
8-1 V
1- B1/B2
1-31/10 j=1
Using c) S ((() Vj < L, we have
Σ ga I |ل + Coy. 1 B1/32 (s 1)
St (1(10111 + +Co(((
V
11-11111 B1
Similarly, we also have
d
1 <t || c(
1 B1/B2
Further combining with (i) in Lemma B.3 and J(t) in 104).
Fi(1) S 1
||g.11 s I(),, VI (T [d].
We refer readers
122 Lemma A.5] for detailed proof under this case.
44

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency. research ethics, and societal impact. Do not re- move the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- ation. While "[Yes] is generally preferable to "[No] it is perfectly acceptable to answer "[No] provided a proper justification is given (e.g.. "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset general, answering "[No] or "[NA] not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer is often more nuanced, so please just your best judgment and write a justification to elaborate. All supporting evidence can appear either the main paper the supplemental material, provided in appendix. If you answer [Yes]] to question, in the justification please point to the section(s) where related material for the question can be found.
used"). In
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [NA]
45

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-tens system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
46

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primanily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
Stw.m//SSooSSSiiiiiiiiaaaia ssionPolicy) for more details. //ipss.cc/pbbic//uuccee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
47

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
48

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://wwwpp..ccooo.o.c.ccccccaa
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
49

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, pataussssspperswiiiii paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: [NA]
50

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (i applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "MmXOEDAXVs", "reviewer": "Reviewer_J5iU", "summary": "This paper studies the high-probability convergence of Adam in the non-convex setting under relaxed assumptions. The authors consider a general noise condition that governs affine, sub-Gaussian, and bounded noise conditions. They also consider a generalized smoothness condition motivated by language model experiments. Under these assumptions, they obtain a convergence rate of $\\text{poly}(\\log T/\\delta)/T$, where $T$ is the number of iterations and $\\delta$ is the confidence level.", "questions": "1. The term “affine variance noise\" is confusing to me. I think it should only refer to Equation (2), not Equation (3), as \"variance\" is defined as an expectation. If I understand correctly, the term in Line 3 refers to (3), which means the condition (A3) is actually stronger than (2), right?\n2. Why in Table 1 you did not include [19] which you discussed in Section 5.1?\n3. The rate in Theorem 4.1 is dimension dependent, whereas the rate in Theorem 3.1 is dimension free. Do you think it is something fundamental in the relaxed smoothness condition?", "limitations": "See weaknesses and questions above", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Their result look novel and significant. They have shown the high-probability convergence of Adam under relaxed conditions than all previous papers.\n2. The proofs look correct. \n3. The paper is well-written and results are clearly presented.", "weaknesses": "1. One major concern is, by choosing $\\beta_2=1-1/T$, does the author essentially reduce Adam to SGD with momentum, as this makes $v_t$ almost a constant? Btw, I think for [18] and [23] in Table 1, $\\beta_1$ should be $1-1/\\sqrt{T}$. Please also check other rows more carefully.\n\nI will increase the score if this concern is addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks a lot for the reviewer's effort and valuable suggestions on our manuscript.\n\n**Response to Weakness: We clarify as follows, and we will revise the presentation issue accordingly.**\n\n- First, in the non-asymptotic analysis (see Table 1) which we follows from, the total iteration number $T$ is treated as finite and fixed. Thereby, during the proof, the following two facts are essential:  $\\beta_2=1-1/T$ as a constant that is not equal to 1; $v_t$ as the exponential moving average of past gradients instead of a constant. Several of our key results, such as Lemma B.2, Lemma B.3, Lemma B.7, and Lemma B.12, are based on these premises. This configuration distinguishes our approach from merely reducing Adam to SGD with momentum, as the proof techniques applicable to SGD with momentum do not directly extend to Adam.\n\n-  Second, as we mention in Table 1, at least two works [10, 38] consider the same setup of $\\beta_2$ as ours. In addition, [49] have indicated that a $\\beta_2$ value closed to one facilitates convergence, whereas a smaller $\\beta_2$ may lead to divergence. This observation also somehow supports the validity of our choice for $\\beta_2$.\n\n-  We will revise $\\beta_1$ setup in two references accordingly.\n\n**Response to Questions**\n\t\n1. Indeed,  \"affine variance noise\" is originally of expected version in Eq. (2). In this paper, in order to derive a stronger high-probability convergence bound instead of an expected bound, we require the stronger almost surely version in Eq. (3), which has been studied in, e.g., [2, 23].  We will add  'almost surely' in Line 3 to distinguish from the expected affine variance noise.\n\t\n2. Thanks a lot for the reminder of this citation, which will be included in Table 1 in the revision.\n\t\n3. We ignore the $d$ factor in the two upper bounds of the main theorem, to make the results concise.  All these two results are dimension dependent, see the proof parts. Furthermore, in Theorem 3.1, if $C_0\\sim \\mathcal{O}(1/d) $, then $G^2 \\sim \\mathcal{O}(1)$ and the convergence bound is of order $\\mathcal{O}(d)$ w.r.t. $d$. In Theorem 4.1, if $E_0\\sim \\mathcal{O}(1/d)$, then $\\hat{H} \\sim \\mathcal{O}(1)$ and the convergence bound is of order $\\mathcal{O}\\left(d\\right)$ w.r.t. $d$. In this sense, there is no fundamental difference between the standard and relaxed smoothness. We will add these remarks in the appendix of the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y1aZkavbI5", "reviewer": "Reviewer_4Xir", "summary": "In this paper, the authors analyze the convergence of Adam under milder noise conditions (affline variance) and milder smoothness conditions (both $L$-smoothness and $(L_0,L_q)$-smoothness) and propose a $O(\\text{polylog}(T)/\\sqrt T)$ convergence rate.", "questions": "1. I suggest the authors could recall the readers of the definitions in the proof part, since numerous variables are introduced for proof, like $\\mathcal{G}_t$, $M$, $\\hat M$, $a_t$, $b_t$ and so on. It's a little inconvenient to check the definition in the previous pages each time.\n2. Since coordinate-wise calculations are commonly used in the proof, I suggest the authors could also consider demonstrating their results based on the $L_\\infty$ smoothness condition, as discussed in [1]. Also, I wonder about the difference of $(L_0,L_q)$-smoothness and local smoothness. \n3. For lemma B.2, I happened also to use this result before and I suggest the author cite [2], as I found this result in lemma A.2 of [2].\n4. How do the authors use the Cauchy-Schwarz inequality in the third inequality of line 740? Is this simply derived from $ab \\leq 1/4a^2 + b^2$ ? (Here $a, b$ are both scalars).\n5. In formula (58), line 557, where the last $\\sqrt{\\log}$ term comes from?\n6. What's the meaning of formulas (59) and (60) since $G^2 \\sim O(\\text{polylog}T)$ has been claimed in formula (7)\n\n[1] Balles, Lukas, Fabian Pedregosa, and Nicolas Le Roux. \"The geometry of sign gradient descent.\" arXiv preprint arXiv:2002.08056 (2020).\n\n[2] Zou, Difan, et al. \"Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization.\" The Eleventh International Conference on Learning Representations.", "limitations": "No limitations.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper analyses the convergence of Adam under milder smoothness conditions compared to the previous work. The result is relatively solid and convincing. The writing structure is also relatively clear.", "weaknesses": "1. As the author claimed in their paper, they did not provide numerical experiments in this paper. While this paper is a theoretical paper focusing on the convergence analysis of Adam, some simple numerical experiments aligning with the results will make it more convincing.\n2. This paper exhibits a slight lack of novelty. Since after checking out the proof details, I found that the crucial techniques were almost proposed by the previous related works.  However, this weakness is trivial, especially for a theoretical paper, and as I claimed in the Strength part, the result of this paper is solid.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your valuable feedback and suggestions!\n\n**Response to Weakness**\n\t\n1. Indeed, numerical results on Adam with/without corrective terms could be found in [10]. We also perform a simple experiment in Table 1 (the attached PDF), which roughly aligns with the result.\n\t\n2. Thanks a lot for your suggestions and understanding of our paper.  For the proof novelty of this paper, please refer to the global rebuttal.\n\n**Response to  Question**\n\t\n1. We will recall the notational definitions at the beginning of each proof part accordingly in the revision.\n\t\n2. We appreciate the suggestion of the interesting topic to study convergence under $L_{\\infty}$-smooth and the interesting work [1] you mentioned, which will be carefully cited and commented in the revision. Due to the limited time and space, we are not able to prove convergence under $L_{\\infty}$-smoothness, and we shall leave it as a future work. \\\nThe major difference between local smoothness and  $(L_0,L_q)$-smoothness arises from the additional gradient norm in $(L_0,L_q)$-smoothness. If the gradient norm is globally bounded such that $||\\nabla f(x)||\\le G$, then $(L_0,L_q)$-smoothness implies local smoothness of $f$ as far as we understand, since following from $(L_0,L_q)$-smoothness: for any $x$ and $y \\in B(x,1/L_q)$, \n\t$$\n\t||\\nabla f(y) - \\nabla f(x)|| \\le (L_0 + L_q G^q)||y - x||.\n\t$$\nBut in general case, $(L_0,L_q)$-smoothness could be considered weaker than local smoothness.\n\t\n3. Thanks a lot for your reminder. We will add its citation in front of Lemma B.2 in our paper accordingly.\n\t\n4. It's exactly derived from $ab \\le a^2/4 + b^2$.  We will change 'Cauchy-Schwarz inequality' as '$ab \\le a^2/4 + b^2,\\forall a,b>0$' in Line 740 of the revision.\n\t\n5. Note that there is $\\mathcal{G}_T$ in Line 556, and recalling the definition from Eq. (18) in Line 229, the additional $\\log$ term comes from $\\mathcal{M}_T = \\sqrt{\\log(eT/\\delta)}$. We will make this clearer in the revision.\n\t\n6. [Eq. (59), Eq. (60)] prove that when $\\beta_2 = 1-c/T$, $\\log (T/\\beta_2^T)$ in (49) is smaller than $\\mathcal{O}(\\log T)$ and further prove $G^2 \\sim  \\mathcal{O}(\\text{poly}(\\log T))$. In Line 562, we will revise as \"Therefore combining (59), (60) and (49), we could verify the order in (7). Also, in Line 525, we will replace \"as in  Theorem 3.1\" with \"given by (49)\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HfzLk8kYm1", "reviewer": "Reviewer_hewP", "summary": "This paper provides two probabilistic convergence rates for Adam with generalized affine variance noise under smoothness and generalized smooth condition, respectively, which achieves comparable results to many prior results.", "questions": "1. What is the symbol $\\xi$ in Equation (1)? It should be explained in the main text.\n\n2. What are the meanings of “right parameter” mentioned in line 4 (Abstract) and “problem parameter” in line 19?\n\n3. Although, in line 139, authors denote “it’s easy to verify that (8) is strictly weaker than L-smoothness” and provide a concrete example $f(x)=x^4$, can detailed proof be given to verify this argument?\n\n4. In Table 1, authors make comparisons with some prior work. However, the forms of some results (such as [33, 40, 49]) are not in the same form as the average form $\\frac{1}{T} \\sum_{t=1}^T ||\\nabla f(x_t)||^2$ in this paper. Therefore, are these comparisons appropriate?", "limitations": "The contribution of this paper is a bit weak. Although authors weaken some assumptions, such as noise and smoothness, the form of their results is also weakened. Therefore, I don’t ensure the weakened assumptions are their advantages.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Please see the above Summary.", "weaknesses": "1. I suggest that authors should provide detailed formulas for some notations including $\\textbf{g}_t, g(\\textbf{x}), \\nabla f(\\textbf{x})$. Is $\\nabla f(\\textbf{x})$ the gradient with the form of expectation.\n\n2. In line 118, the reference [10] is cited repeatedly.\n\n3. Section 5 is used to discuss the most related works and make comparisons with the main results in this paper. However, authors only discuss the most related works without any comparison with their main results. \n\n4. As mentioned in 1., if $\\nabla f(\\textbf{x})$ is the gradient with the form of expectation, the two results (Theorems 3.1 and 4.1) in this paper are not fully high probability since $\\frac{1}{T} \\sum_{t=1}^T ||\\nabla f(x_t)||^2$ is equivalent to $\\frac{1}{T} \\sum_{t=1}^T ||E_{z_i}[\\nabla f(x_t,z_i)]||^2$ ($z_i$ is the training data defined by me) which is smaller than $\\frac{1}{T} \\sum_{t=1}^T E_{z_i}[||\\nabla f(x_t,z_i)||^2]$. In other words, the results with the form $\\frac{1}{T} \\sum_{t=1}^T E_{z_i}[||\\nabla f(x_t,z_i)||^2]$ can directly derive the corresponding results with the form $\\frac{1}{T} \\sum_{t=1}^T ||E_{z_i}[\\nabla f(x_t,z_i)]||^2$, to say nothing of the one with additional high probability. Therefore, from my perspective, high probability is not an advantage for this paper, but rather weakens $\\frac{1}{T} \\sum_{t=1}^T ||E_{z_i}[\\nabla f(x_t,z_i)]||^2$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks a lot for the reviewer's effort invested on our paper. Below are our responses to the major concern.\n\t\n**Response to Weaknesses 1-3: Thank you for the suggestions on the presentation. We will revise as follows accordingly.**\n\n1. In Line 14, we will replace '$g_t$' with '$g_t = \\frac{\\partial f_\\xi(x,\\xi_t)} {\\partial x}|_{x=x_t}$'.\\\nIn Line 16, we will replace '$g(x)$ is unbiased' with '$g(x,\\xi)$ is an unbiased estimate of $\\nabla f(x)$ such that $E [g(x,\\xi)|x] = \\nabla f(x)$'. \\\nIn Eq. (2), we will replace '$E[\\|g(x) - \\nabla f(x)||_2^2]$' with '$E[\\|g(x,\\xi) - \\nabla f(x)||_2^2|x]$'.  \\\nIn general,  $\\nabla f(x)$ does not need to be of the expectation form, while for Eq. (1) , \n\n$$\n\\ \\  \\ \\ \\  \\ \\ \\ \\nabla f(x) =  E \\left[\\frac{\\partial f_{\\xi}(x,\\xi)}{\\partial x}\\mid x \\right]\n$$\n\n2. In Line 118, we will replace '[22, 10, 53, 10, 38]' with '[22, 10, 53, 38]'.\n\n3. To accomplish Table 1, we could add some detailed comparisons on convergence for Adam as follows.  \\\nIn Line 189, we will add 'In comparisons with these works, our hyper-parameter setup could be relatively simpler than [49],  while our results do not need the assumption on bounded gradients from [18, 20]. Moreover, we study Adam with two corrective terms which were overlooked in these works.' \\\nIn Line 203, we will add 'In comparisons, our hyper-parameter setup on $\\beta_2$ is simpler than [40] while involving the natural corrective terms. Moreover, we consider a milder noise assumption than the sub-Gaussian noise assumption in [23], with different hyper-parameter setups on $\\beta_1$ and $\\beta_2$.' \n\n**Response to Weakness 4: We clarify as follows.**\n- **High-probability convergence can ensure expected convergence:** \\\nLet $\\Sigma =  \\sqrt{T} \\times \\frac{1}{T}\\sum_{t=1}^T||\\nabla f(x_t)||^2.$\nOur result shows that $$Prob\\left(\\Sigma \\gtrsim { \\log{1\\over \\delta}}\\right) \\leq \\delta.$$ \nThen for some constants $c, C$, \n$$ E[\\Sigma] =  \\int_{0}^\\infty Prob(\\Sigma \\geq y) dy \\leq \\int_{0}^\\infty e^{-cy} dy \\simeq C.$$\n- *$  \\frac{1}{T}\\sum_{t=1}^T E_{z_i}||\\nabla f(x_t,z_i)||^2$ (you mentioned) is the average of **conditional** expectations, while $\\frac{1}{T}\\sum_{t=1}^TE ||\\nabla f(x_t)||^2$ is the average of **full/total** expectations.* \\\nPrevious expected convergence results are on $\\frac{1}{T}\\sum_{t=1}^TE ||\\nabla f(x_t)||^2$. We think that the form you mentioned could be meaningful for the future work. However, no results are given for $  \\frac{1}{T}\\sum_{t=1}^T E_{z_i}||\\nabla f(x_t,z_i)||^2$, to our knowledge.\n\n**Response to Questions 1-4**\n\n1. $\\xi$ is the random vector following a probability distribution $\\mathcal{D}$. We will add this statement in Line 14 of the revision.\n\n3. The 'right parameter' means the hyper-parameter setup such as (6) in Theorem 3.1. The 'problem parameter' here refers to the (generalized) smooth and noise level parameters. We will make this clearer in the revision.\n\n3. Proof for '(8) weaker than $L$-smoothness':  If $f$ is $L$-smooth, i.e., $|| \\nabla f(x) - \\nabla f(y)|| \\leq L ||x-y||$ for all $x,y$, then $(8)$ is trivially satisfied for $L_0 = L$ and any $L_q>0$. \\\nProof for `$f(x)=x^4$ satisfies (8)':  First, $|f'(y)-f'(x)| = 4|y^3-x^3| =4 |y^2+xy+x^2||y-x| $. Observe that for any constant $L >0$, there always exist $x,y \\in \\mathbb{R}$ such that $4|y^2+xy+x^2 |> L$ and thus the $L$-smoothness condition does not hold. However, when restricting $|x-y| \\le 1/L_q$, we could derive that\n$$\n4|y^2+xy+x^2| \\le 6(y^2 + x^2) \\le 6(2x^2+\\frac{2}{L_q^2} + x^2) \\le 18x^2+\\frac{12}{L_q^2} \\le \\frac{18}{4^{\\frac{2}{3}}}  (4x^3)^{\\frac{2}{3}} +\\frac{12}{L_q^2},\n$$\nwhere we set $L_q = 18/(4^{3/2})$, $q= 2/3$ and $L_0 = 12/L_q^2$, which leads to (8).\n\n3. [33, 40, 49] study Adam with random-reshuffling samplings and  their results are w.r.t. $\\min_{k \\in [T]}||\\nabla f(x_{k,0})||$. Here $x_{k,0}$ denotes the output of the $k$-th epoch (i.e. $kn$-th iteration) of Adam, and  $n$ is the number of training data. We will add this remark after Table 1 in the revision.\n\n**Response to Limitations: We clarify that our high probability bounds are stronger than the expected bounds**, following from the 'Response to Weakness 4'. The brief introduction of our proof novelty could be seen in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their comments and suggestions! In the global rebuttal, we have:
- **summarization of proof novelty**
- **a simple experiment in the attached PDF as supplementary material for our main results.**

While our proof borrows some ideas from [42, 10, 14, 2, 38, 19] as we mention in Line 221, **our proof novelty** lies in the following points  (and a few others):
- a new type of proxy step-size in Eq. (22) to break the entanglement of stochastic gradients and adaptive step-sizes in Eq. (21), and to handle the error brought by the affine variance noise in Line 256;
- a new decomposition to handle the mismatch between stochastic gradients and the momentum, please also refer to Eq. (19), Line 261 and Line 262;
- some new estimations to handle the corrective terms in Adam, which are seldom considered in previous works, please also refer to Lemma B.12;
- an induction argument to control the potential unbounded smooth parameter in the generalized smooth case, please also refer to Proposition C.6 and Proposition C.7.

Meta-review: All reviewers think the paper is interesting.  I recommend an acceptance.
Decision: Accept (poster)