On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions

Authors: yusu  hong
junhong  lin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:43:24

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.

Main paper: 
 introduction: 
 Since its introduction by [33] , the Stochastic Gradient Descent (SGD): x t+1 = x t -η t g t has achieved significant success in solving the unconstrained stochastic optimization problems:EQUATIONwhere ξ is a random variable, g t is the stochastic gradients and η t 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 σ 0 , σ 1 ≥ 0 and all x ∈ R d ,EQUATION)Under the noise assumption (2), [3] provided an almost-sure convergence bound for SGD. [4] proved that SGD could reach a stationary point with a O(1/ √ T ) rate when step-sizes are tuned by problemparameters such as the smooth parameter L. The theoretical result also revealed that the analysis of SGD under (2) is not essentially different from the bounded noise case [17] .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 to adaptively tune their stepsizes and are preferred to SGD for minimizing various objective functions due to their efficiency. Among these methods, Adam [22] has been one of the most effective methods empirically. Generally speaking, Adam absorbs some key ideas from previous adaptive methods such as AdaGrad [12, 36] and RMSProp [37] while adding more unique structures. It combines the exponential moving average mechanism from RMSProp and meanwhile adds the heavy-ball style momentum [29] and two unique ✗ Bounded Bounded L 1 -β 2 ≤ cϵ 2 poly( 1 ϵ ) 1 T + σ 2 E [7] ✗ Bounded Bounded L β 1,t < β 1 , β 2 = 1 -1 T - 1 √ T E [57] ✗ Bounded - L β 2 = 1 -c T poly(log 1 ϵ ) 1 √ T E [34] ✗ - Finite Sum Affine L T (β 1 , β 2 ) → 0 1 - - E [10] ✗ Bounded Bounded L β 1 < β 2 , β 2 = 1 -1 T poly(log 1 ϵ ) 1 √ T E [18] ✗ Bounded Affine L β 1 = 1 -c √ T poly( 1 ϵ ) 1 √ T E [52] ✗ - Finite Sum Affine L β 1 < √ β 2 , β 2 = 1 -c T [3] - 1 √ T E [41] ✗ - Finite Sum Affine (L 0 , L 1 ) β 1 < √ β 2 - - E [24]✓ -Sub-Gaussian (L 0 , L 1 )β 1 = 1 -c √ T 1 √ ϵ 1 √ T w.h.p. [39] ✗ - Coordinate-wise Affine L β 1 = b √ β 2 , β 2 = 1 -c T poly(log 1 ϵ ) 1 √ T E [19] ✓ - Coordinate-wise Affine L β 1 < β 2 , β 2 = 1 -1 T poly(log 1 ϵ ) 1 √ T w.h.p. Thm. 3.1 ✓ - Affine L β 1 < β 2 , β 2 = 1 -c T poly(log 1 ϵ ) 1 √ T w.h.p. Thm. 4.1 ✓ - Affine (L 0 , L 1 ) β 1 < β 2 , β 2 = 1 -c T poly(log 1 ϵ ) 1 √ Tw.h.p.1 [34] requires T (β1, β2) = Oβ 1 β n 2 1-β 1 1-β n 1+ 1 → 0, which seems could only achieve when β1 = 0 .2 Though not explicitly stated, the results in (Zhang et al., 2022) could imply convergence to the stationary point when with some calculations. 3 "FCT" refers to "full corrective terms". The "Conv. rate" column presents the convergence rate omitting logarithm factors.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 (2) . Earlier researches [14, 40, 2] have shown that AdaGrad-Norm, a scalar version of AdaGrad, can find a stationary point at the same rate as SGD, not tuning step-sizes based on problem-parameters. Moreover, they addressed an essential challenge brought by the correlation of adaptive step-sizes and noise from (2) which does not appear in SGD's cases. However, since AdaGrad-Norm applies a cumulative step-sizes mechanism which is rather different from the exponential moving average step-sizes in Adam, the analysis for AdaGrad-Norm could not be trivially extended to Adam. Furthermore, the coordinate-wise step-size architecture of Adam, 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 random-reshuffling scheme under certain parameter restrictions [52, 41] , or deduce the convergence at the expense of requiring bounded gradient assumption and using problem-parameters to tune the step-sizes [18] , 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 a stronger coordinate-wise variant [39, 19] .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, we conduct an in-depth analysis and prove that Adam with the right parameter can find a stationary point in high probability. We assume 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 poly(log T )/ √ T matching the lower rate in [1] 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 correlation 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 (L 0 , L q )-smooth condition [51] . Several researchers have found empirical evidence of objective functions satisfying (L 0 , L q )-smoothness but out of L-smoothness range, especially in large-scale language models [49, 38, 11, 8] . Theoretical analysis of adaptive methods under this relaxed condition is more complicated and needs further nontrivial proof techniques. Also, prior knowledge of problem-parameters to tune step-sizes is needed, as indicated by the counter-examples from [40] for the AdaGrad. Existing works [13, 40] obtained a convergence bound for AdaGrad-Norm with (2) , and [24] considered Adam with sub-Gaussian noise. In this paper, we provide a probabilistic convergence result for Adam with the affine variance noise and the generalized smoothness condition.Input:Horizon T , x 1 ∈ R d , β 1 , β 2 ∈ [0, 1), m 0 = v 0 = 0 d , η, ϵ > 0, ϵ = ϵ1 d for s = 1, • • • , T doDraw a new sample z s and generate g s = g(x s , z s );m s = β 1 m s-1 + (1 -β 1 )g s ; v s = β 2 v s-1 + (1 -β 2 )g 2 s ; η s = η 1 -β s 2 /(1 -β s 1 ), ϵ s = ϵ 1 -β s 2 ; x s+1 = x s -η s • m s / √ v s + ϵ s ;end forWe also refer readers to see the main contributions of our works and comparisons with the existing works in Table 1 . x denote coordinate-wise square and square root respectively. x i denotes the i-th coordinate of x. For any two vectors x, y ∈ R d , we use x ⊙ y and x/y to denote the coordinate-wise product and quotient respectively. 0 d and 1 d represent zero and one d-dimensional vectors respectively. 
problem set up and algorithm: 
 We consider unconstrained stochastic optimization (1) over R d with l 2 -norm. The objective function f : R d → R is differentiable. Given x ∈ R d , we assume a gradient oracle that returns a random vector g(x, z) ∈ R d dependent by the random sample z. The true gradient of f at x is denoted by ∇f (x) ∈ R d .We make the following assumptions throughout the paper.f * > -∞ such that f (x) ≥ f * , ∀x ∈ R d ;• (A2) Unbiased estimator: The gradient oracle provides an unbiased estimator of ∇f (x), i.e., E z [g(x, z)] = ∇f (x), ∀x ∈ R d ; • (A3) Generalized affine variance noise: The gradient oracle satisfies that there are some constantsσ 0 , σ 1 > 0, p ∈ [0, 4), E z exp ∥g(x,z)-∇f (x)∥ 2 σ 2 0 +σ 2 1 ∥∇f (x)∥ p ≤ exp(1), ∀x ∈ R d .The first two assumptions are standard in the stochastic optimization. The third assumption provides a 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 followsEQUATIONand enlarge the range of p to [0, 4). Assumption (A3) with p = 2 and (3) are also utilized in [2] to establish high probability results for AdaGrad-Norm. It represents a 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-probability 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, 21] , in robust linear regression [45] , and generally whenever the model parameters are multiplicatively perturbed by noise (e.g., a multilayer network, where noise from a previous layer multiplies the parameters in subsequent layers). We refer interested readers to see e.g., [3, 45, 4, 14, 40, 2] for more discussions about the affine variance noise.Adam For the stochastic optimization problem, we study Algorithm 1, which is an equivalent form of Adam [22] with the two corrective terms for m s and v s included into η s for notation simplicity.The iterative relationship in Algorithm 1 can be also written as for any s ∈ [T ],EQUATIONwhere we let x 0 = x 1 and η 0 = η. (4) plays a key role in the convergence analysis, showing that Adam incorporates a heavy-ball style momentum and dynamically adjusts its momentum through β 1 and β 2 , along with adaptive step-sizes. This inspires us to learn from some classical analysis methods for algorithms with momentum and provides some new estimations to fit in with the adaptive property. 
convergence of adam with smooth objective functions: 
 In this section, we assume that the objective function f is L-smooth satisfying that for any x, y ∈ R d ,EQUATIONWe then show that Adam has the following high probability results. EQUATIONfor some constants c, C 0 > 0 and ϵ 0 > 0, then for any given δ ∈ (0, 1/2), it holds that with probability at least 1 -2δ,1 T T s=1 ∥∇f (x s )∥ 2 ≤ O G 2 σ 2 0 + σ 2 1 G p + G 2 T + ϵ 0 T log T δ ,where G2 is defined by the following order with respect to T, ϵ 0 , δ: 2EQUATIONTheorem 3.1 provides the nearly optimal convergence rate O poly(log T )/T to find a stationary point when setting the parameter probably:β 2 = 1 -O(1/T ).It's worth noting that the setting requires β 2 to be closed enough to 1 when T is sufficiently large, which roughly aligns with the typical setting in [22, 57, 10, 39] .For a more detailed comparison of our results to existing works, including assumptions, convergence rate, and dependency, we refer readers to Table 1 .Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
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.For a differentiable objective function f : R d → R, we consider the following (L 0 , L q )-smoothness condition: there exist constants q ∈ [0, 2) and L 0 , L q > 0, satisfying that for anyEQUATIONThe generalized smooth condition was originally put forward by [51] for any twice differentiable function f satisfying thatEQUATIONIt has been proved that a 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 1 in [51] and [8] .To better understand the theoretical significance of the generalized smoothness, [49] 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 gradient-clipping algorithms.There are three key reasons for opting for (8) . Firstly, considering our access is limited to first-order stochastic gradients, it's logical to only assume that f is differentiable. Second, as pointed out by Lemma A.2 in [49] and Proposition 1 in [13] , ( 8) and ( 9) are equivalent up to constant factors when f is twice differentiable considering q = 1. Thus, (8) covers a broader range of functions than (9) . Finally, it's easy to verify that ( 8) is strictly weaker than L-smoothness. A concrete example is that the simple function f (x) = x 4 , x ∈ R does not satisfy any global L-smoothness but (8) . Moreover, the expanded range of q to [0, 2) is necessary as all univariate rational functions P (x)/Q(x), where P, Q are polynomials and double exponential functions a (b x ) with a, b > 1 are (L 0 , L q )-smooth with 1 < q < 2 (see [24, Proposition 3.4] ). We refer interested readers to see [51, 49, 13, 24] for more discussions of concrete examples of generalized smoothness.We then provide the high probability convergence result of Adam with (L 0 , L q )-smoothness condition as follows. Theorem 4.1. Let T ≥ 1 and δ ∈ (0, 1/2). Suppose that {x s } s∈[T ] is a sequence generated by Algorithm 1, f is (L 0 , L q )-smooth satisfying (8), Assumptions (A1)-(A3) hold, and the parameters satisfyEQUATIONwhere c, ϵ 0 , E 0 , C0 > 0 are constants, Ĥ is controlled by O log T ϵ0δ 3 , and H, H, L are defined asEQUATION)Then it holds that with probability at least 1 -2δ,EQUATIONNote that in the above theorem, the order of log T in Ĥ and the final convergence bound is better 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 C0 . Since Ĥ is logarithm order of T , H, H, L are both polynomial logarithm order of T and the final convergence rate in (12) is also polynomial logarithm order of T . Note that C0 ≤ O(1/poly(log T )) from (10) when T ≫ d. Hence, when T is large enough, a possible optimal setting is that η = c 1 /( √ T poly(log T )) for some constant c 1 > 0, which roughly matches the typical setting as mentioned before.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 conclusions 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.• 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 a dataset and/or model, the authors should describe the steps taken 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 to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 authors are 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
related works: 
 There is a large amount of works on stochastic approximations (or online learning algorithms) and adaptive variants, e.g., [5, 35, 47, 28, 12, 4, 6, 26, 54] and the references therein. In this section, we will discuss the most related works and make a comparison with our main results.We mainly list previous literature considering (2) over non-convex smooth scenario. [3] 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-Norm with (2), pointing out that the analysis is more challenging than the bounded noise and bounded gradient case in [43] . They provided a convergence rate of Õ(1/ √ T ) without knowledge of problem parameters, and further improved the bound adapting to the noise level: whenEQUATION(13) matches exactly with SGD's case [4] , showing a fast rate of Õ(1/T ) when σ 0 is sufficiently low. Later, [40] proposed a deep analysis framework obtaining (13) with a tighter dependency to T and not requiring any restriction over σ 1 . They further obtained the same rate for AdaGrad under a stronger coordinate-wise version of (2): for all i ∈ [d],EQUATION)[2] obtained a probabilistic convergence rate for AdaGrad-Norm with (3) using a novel induction argument to estimate the function value gap without any requirement over σ 1 as well.In the analysis of Adam, a line of works [34, 52, 41] considered Adam without corrective terms 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 whereEQUATIONunder the affine growth condition which is equivalent to (2) . Though not explicitly concluded, when setting β 2 = 1 -O(1/T ), [52] 's work can also ensure a convergence rate of order Õ(1/ √ T ) under certain settings. Besides, both [20] and [18] 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 whereC l ≤ ∥ 1 √ vt+ϵt ∥ ∞ ≤ C u , ∀t ∈ [T ]. [39] and [19] 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. [19] further achieved a Õ(1/ √ T ) rate for Adam. However, the two works only studied coordinate-wise affine variance noise.In this paper, we derive a stronger high probability convergence rate for Adam with original corrective terms, relying on an almost surely noise assumption. The noise model is general enough to cover bounded noise, sub-Gaussian noise, and (coordinate-wise) affine variance noise. Although we consider a stronger almost surely assumption, our probabilistic convergence result is also stronger than the expected convergence.The generalized smooth condition was first proposed for twice differentiable functions by [51] (see (9) ) to explain the acceleration mechanism of gradient-clipping. This assumption was extensively confirmed in experiments of large-scale language models [51] . Later, [49] further relaxed it to a more general form in (8) allowing for first-order differentiable functions. Subsequently, a series of works [30, 53, 32] studied different algorithms' convergence under this condition.In the field of adaptive methods, [13] provided a convergence bound for AdaGrad-Norm assuming (2) and ( 8) with q = 1, albeit requiring σ 1 < 1. Based on the same conditions, [40] improved the convergence rate to the form in (13) without restriction on σ 1 . [41] explored how Adam without corrective terms behaves under generalized smoothness with q = 1 and (2). However, they could only assert convergence to a bounded region as shown in (15) . [8] showed that an Adam-type algorithm converges to a stationary point under a stronger coordinate-wise generalized smooth condition.In this paper, we consider a more general noise setup and investigate Adam's convergence under the generalized smooth landscape. We prove that Adam is powerful enough to find a 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 O(1/ √ T ) rate up to logarithm factors.Adam was first proposed by [22] with empirical studies and theoretical results on online convex learning. The original proof of convergence in [22] was later shown by [31] to contain gaps. [31] and the subsequent work [42] also showed that for a range of momentum parameters chosen independently 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, [48] demonstrated that Adam can converge within a specific region if step-sizes and decay parameters are determined properly by the smooth parameter. [9] proposed a convergence result to a stationary point and required all stochastic gradients must keep the same sign. To circumvent this requirement, [57] introduced a convergence bound only requiring hyper-parameters to satisfy specific conditions. [10] conducted a simple proof and further improved the dependency on the heavy-ball momentum parameter. Recently, [55] introduced Nesterov-like acceleration into Adam and AdamW [27] indicating their superiority in convergence over the non-accelerated versions. For Adam-related works under (2) or generalized smoothness, we refer readers to Sections 5.1 and 5.2.We also want to highlight that a series of works [23, 44, 50] investigated the geometry of Adam from an l ∞ -norm perspective. [23] and [44] studied the geometry of Adam by regarding it as a variant of SignSGD and [50] showed that full-batch Adam converges towards a linear classifier that achieves the maximum l ∞ -margin when the training data are linearly separable.Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
proof sketch under the smooth case: 
 In this section, we provide a proof sketch of Theorem 3.1 with some insights and proof novelty. Our proof borrows some ideas from [43, 10, 14, 2, 39, 19] . The detailed proof can be found in Appendix B.Preliminary To start with, we let the stochastic gradient g s = (g s,i ) i , the true gradient ∇f (x s ) = ḡs = (ḡ s,i ) i and ξ s = (ξ s,i ) i = g s -ḡs . We also let ϵ s = ϵ 1 -β s 2 and thus ϵ s = ϵ s 1 d . For any positive integer T and δ ∈ (0, 1), we define M T = log (eT /δ). We denote the adaptive part of the step-size asEQUATIONWe define two auxiliary sequences {p s } s≥1 and {y s } s≥1 ,EQUATION)We follow from [16, 46] which was used to prove the convergence of SGD with momentum and later applied to handle many variants of momentum-based algorithms. Recalling the iteration of x s in (4), we reveal that y s satisfiesEQUATIONIn addition, given T ≥ 1, we define, ∀s ∈ [T ],EQUATION)where G is as in Theorem 3.1. Both G s and G T (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 t ∈ [T ], combining with ( 18) and summing over sEQUATIONwhere we let ∆ s = ηsbs-1 ηs-1bs -1 d and use y 1 = x 1 from (17) . In what follows, we will estimate A, B, and C respectively.Probabilistic estimations To proceed with the analysis, we next introduce two probabilistic estimations showing that the norm of the noises and a related summation of martingale difference sequence could be well controlled with high probability. We show that with probability at least 1 -2δ, the following two inequalities hold simultaneously for all t ∈ [T ]:EQUATIONEQUATIONwhere D 1 is a constant defined in Lemma B.7 and a s will be introduced later. In what follows, we always assume that ( 21) and ( 22) hold for all t ∈ [T ] and carry out our subsequent analysis with some deterministic estimations.Estimating A We first decompose A asA = t s=1 -η s ḡs , g s b s A.1 + t s=1 η s ḡs -∇f (y s ), g s b s A.2.Due to the correlation of the stochastic gradient g s and the step-size η s /b s , the estimating of A.1 is challenging, as also noted in the analysis for other adaptive gradient methods, e.g., [43, 10, 14, 2, 39, 19] . To break this correlation, the so-called proxy step-size technique is introduced and variants of proxy step-size have been introduced in the related literature. However, to our best knowledge, none 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 η s /a s , with a s relying on G T (s) in ( 19), defined as for any s ∈ [T ],EQUATIONWith the so-called proxy step-size technique over η s /a s and ξ s = g s -ḡs , we decompose A.1 asA.1 = - t s=1 η s ḡs √ a s 2 - t s=1 η s ḡs , ξ s a s A.1.1 + t s=1 η s ḡs , 1 a s - 1 b s g s A.1.2 .In the above decomposition, the first term serves as a descent term. A.1.1 is now a summation of a martingale difference sequence which could be estimated by (22) . A.1.2 is regarded as an error term when introducing a s . However, due to the delicate construction of a s , the definition of local gradients' bound G T (t), and using some basic inequalities, we show thatA.1.2 ≤ 1 4 t s=1 η s ḡs √ a s 2 + ηG T (t) √ 1 -β 2 1 -β 1 t s=1 g s b s 2 .The first RHS term can be eliminated with the descent term while the summation of the last term can be bounded byEQUATIONdue to the step-size's adaptivity, the iterative relationship of the algorithm, the smoothness of the objective function, as well as (21) . Here, ms = ms1-β s 1 .Estimating B and C The key to estimate B is to decompose B asB = β 1 1 -β 1 t s=1 ⟨∆ s ⊙ (x s -x s-1 ), ḡs ⟩ B.1 + β 1 1 -β 1 t s=1 ⟨∆ s ⊙ (x s -x s-1 ), ∇f (y s ) -ḡs ⟩ B.2 .To estimate B.1, we use the updated rule and further write ∆ s ⊙ (x s -x s-1 ) asη s b s - η s a s ⊙ m s-1 + η s a s - η s b s-1 ⊙ m s-1 + (η s -η s-1 ) m s-1 b s-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 thatB + C ≤ 1 4 t s=1 η s ḡs √ a s 2 + (b 1 G T (t) + b 2 ) log T β T 2 ,where b 1 and b 2 are positive constants determined by β 1 , β 2 , d, L, η.The last challenge comes from the potential unbounded gradients' norm. Plugging the above estimations into (20) , we obtain thatEQUATIONwhere c 1 , c 2 , c 3 are constants determined by β 1 , β 2 , d, L, η. Then, we will first show that G 1 ≤ G and suppose that for some t ∈ [T ],EQUATIONIt's then clear to reveal from (25) and the induction assumption that f (y t+1 ) is restricted by the first-order of G T . Moreover, f (y t+1 ) -f * could be served as the upper bound of ∥ḡ t+1 ∥ 2 sinceEQUATION)where we use a standard result ∥∇f (x)∥ 2 ≤ 2L(f (x) -f * ) in smooth-based optimization. We also use the smoothness to control ∥ḡ t+1 -∇f (y t+1 )∥ 2 and combine with ( 26) and ( 27) to derive that∥ḡ t+1 ∥ 2 ≤ d1 + d2 (σ 1 G p/2 + G),where d1 , d2 are constants that are also determined by hyper-parameters and restricted by O(log T -T log β 2 ) with respect to T . Then, using Young's inequality,∥ḡ t+1 ∥ 2 ≤ G 2 2 + d1 + 4 -p 4 • p p 4-p d2 4 4-p + d2 2 .Thus, combining with a proper construction G 2 (detailed in ( 52)), we could prove thatG 2 = 2 d1 + 4 -p 2 • p p 4-p d2 4 4-p + 2 d2 2 , which leads to ∥ḡ t+1 ∥ 2 ≤ G 2 . Combining with the induction argument, we deduce that ∥ḡ t ∥ 2 ≤ G 2 , ∀t ∈ [T + 1].Final estimation Following the induction step for upper bounding the gradients' norm, we also prove the following result in high probability:L T s=1 η s ∥a s ∥ ∞ ∥ḡ s ∥ 2 ≤ L T s=1 η s ḡs √ a s 2 ≤ G 2 .We could rely onG T to prove that ∥a s ∥ ∞ ≤ G T 1 -β s 2 + ϵ s , ∀s ∈ [T ], and then combine with η s in Algorithm 1 to further deduce the desired guarantee for T s=1 ∥ḡ s ∥ 2 /T .Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type optimizer, etc.) necessary to understand the results?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
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 a mild noise assumption 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 a rate of O(poly(log T )/Question: Does the paper report error bars suitably and correctly defined or other appropriate 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 are accompanied by error bars, confidence 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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 are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 make it into the paper). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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 out 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 is 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or 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?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation 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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: [NA] 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 (if applicable), such as the institution conducting the review. 
 
 Appendix: T ) with high probability. Within our framework, we introduce a 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 to be more realistic in practical applications.Our results indicate that, with appropriate hyper-parameter tuning, Adam can find a stationary point at the same order of convergence rate as in 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 hyper-parameter settings in our results. Second, the convergence bound is not strictly tight compared to the lower bound, leaving a gap involving logarithmic factors, which may be improved in future work.The appendix is organized as follows. The next section presents some necessary technical lemmas, some of which have appeared in the previous literature. In Appendix B and Appendix C, the detailed proofs for Theorem 3.1 and Theorem 4.1 are presented respectively. Finally, Appendix D and Appendix E provide all the omitted proofs in previous sections.We first provide some necessary technical lemmas as follows.Lemma A.1. Suppose that {α s } s≥1 is a non-negative sequence. Given β 2 ∈ (0, 1] and ε > 0, we define θ s = s j=1 β s-j 2 α j . Then, for any t ≥ 1,t s=1 α j ε + θ j ≤ log 1 + θ t ε -t log β 2 .Proof. See the proof of Lemma 5.2 in [10] .Lemma A.2. Suppose that {α s } s≥1 is a real number sequence. Given 0 ≤ β 1 < β 2 ≤ 1 and ε > 0, we define ζ s = s j=1 β s-j 1 α j , γ s = 1 1-β s 1 s j=1 β s-j 1 α j and θ s = s j=1 β s-j 2 α 2 j , then t s=1 ζ 2 s ε + θ s ≤ 1 (1 -β 1 )(1 -β 1 /β 2 ) log 1 + θ t ε -t log β 2 , ∀t ≥ 1, t s=1 γ 2 s ε + θ s ≤ 1 (1 -β 1 ) 2 (1 -β 1 /β 2 ) log 1 + θ t ε -t log β 2 , ∀t ≥ 1.Proof. The proof for the first inequality can be found in the proof of Lemma A.2 [10] . For the second result, let M = s j=1 β s-j 1. Then using Jensen's inequality, we haveEQUATIONHence, we further haveγ 2 s ε + θ s ≤ M (1 -β s 1 ) 2 s j=1 β s-j 1 α 2 j ε + θ s = 1 (1 -β 1 )(1 -β s 1 ) s j=1 β s-j 1 α 2 j ε + θ s .Recalling the definition of θ s , we have ε+ θ s ≥ ε + β s-j 2 θ j ≥ β s-j 2 (ε + θ j ). Hence, combining with 1 -β 1 ≤ 1 -β s 1 , γ 2 s ε + θ s ≤ 1 (1 -β 1 )(1 -β s 1 ) s j=1 β 1 β 2 s-j α 2 j ε + θ j ≤ 1 (1 -β 1 ) 2 s j=1 β 1 β 2 s-j α 2 j ε + θ j .Summing up both sides over s ∈ [t], and noting thatβ 1 < β 2 , t s=1 γ 2 s ε + θ s ≤ 1 (1 -β 1 ) 2 t s=1 s j=1 β 1 β 2 s-j α 2 j ε + θ j ≤ 1 (1 -β 1 ) 2 (1 -β 1 /β 2 ) t j=1 α 2 j ε + θ j .Finally applying Lemma A.1, 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 [25] for a proof.Lemma A.3. Suppose {Z s } s∈[T ] is a martingale difference sequence with respect to ζ 1 , • • • , ζ T . Assume that for each s ∈ [T ], σ s is a random variable only dependent by ζ 1 , • • • , ζ s-1 and satisfies that E exp(Z 2 s /σ 2 s ) | ζ 1 , • • • , ζ s-1≤ e, then for any λ > 0, and for any δ ∈ (0, 1), it holds thatP T s=1 Z s > 1 λ log 1 δ + 3 4 λ T s=1 σ 2 s ≤ δ.B Proof of Theorem 3.1The detailed proof of Theorem 3.1 corresponds to the proof sketch in Section 6.To start with, we introduce the following two notations,EQUATIONwhich include two corrective terms for m s and v s . It is easy to see that η s satisfiesEQUATIONWe follow all the notations in Section 6, which we present here for the convenience of reading,M T = log eT δ , G s = max j∈[s] ∥ḡ j ∥, G T (s) = M T 2σ 2 0 + 2σ 2 1 G p s + 2G 2 s , G T = M T 2σ 2 0 + 2σ 2 1 G p + 2G 2 , b s = β 2 v s-1 + (1 -β 2 )g 2 s + ϵ s , a s = β 2 v s-1 + (1 -β 2 ) (G T (s)1 d ) 2 + ϵ s .The following lemmas provide some estimations for the algorithm-dependent terms, which play vital roles in the proof of Theorem 3.1. The detailed proofs could be found in Appendix D.1. Lemma B.1. Let η s , b s be given in Algorithm 1 and (16), thenη s b s-1 η s-1 b s -1 d ∞ ≤ Σ max := max 1, 1 + β 2 β 2 -1 , ∀s ≥ 2.The following lemma could be found similarly in [ with 0 ≤ β 1 < β 2 < 1, respectively. Then, m s b s ∞ ≤ (1 -β 1 )(1 -β s 1 ) (1 -β 2 )(1 -β 1 /β 2 ), ∀s ≥ 1.Consequently, if f is L-smooth and we set η = C 0 √ 1 -β 2 for some constant C 0 > 0, then ∥ḡ s ∥ ≤ ∥ḡ 1 ∥ + LC 0 s d 1 -β 1 /β 2 , ∀s ≥ 1.The following lemma is necessary for deriving (24) in the proof sketch.Lemma B.3. Let g s , m s be given in Algorithm 1 and ms , b s be defined in (29) and (16) .If 0 ≤ β 1 < β 2 < 1 and F i (t) = 1 + 1 ϵ 2 t s=1 g 2 s,i , then for any t ≥ 1, t s=1 g s b s 2 ≤ 1 1 -β 2 d i=1 log F i (t) β t 2 , t s=1 m s b s 2 ≤ 1 -β 1 (1 -β 2 )(1 -β 1 /β 2 ) d i=1 log F i (t) β t 2 , t s=1 m s b s+1 2 ≤ 1 -β 1 β 2 (1 -β 2 )(1 -β 1 /β 2 ) d i=1 log F i (t) β t 2 , t s=1 ms b s ≤ 1 (1 -β 2 )(1 -β 1 /β 2 ) d i=1 log F i (t) β t 2 .The following lemmas are based on the smooth condition. Lemma B.4. Suppose that f is L-smooth and Assumption (A1) holds, then for anyx ∈ R d , ∥∇f (x)∥ 2 ≤ 2L(f (x) -f * ).Lemma B.5. Let x s be given in Algorithm 1 and y s be defined in (17) .If f is L-smooth, η = C 0 √ 1 -β 2 and 0 ≤ β 1 < β 2 < 1, then ∥∇f (x s )∥ ≤ ∥∇f (y s )∥ + M, M := LC 0 √ d (1 -β 1 ) 1 -β 1 /β 2 , ∀s ≥ 1.Specifically, we fix the horizon T and start from the descent lemma of L-smoothness,EQUATIONFor any given t ∈ [T ], combining with ( 18) and (31) and then summing over s ∈ [t], we obtain the same inequality in (20) ,EQUATIONwhere we use ∆ s in (20) and y 1 = x 1 . We then further make a decomposition by introducing ḡs into A andEQUATIONandEQUATION)We will provide two probabilistic inequalities with the detailed proofs given in Appendix D.2. The first one establishes an upper bound for the noise norm, which we have already informally presented in (21) . Lemma B.6. Given T ≥ 1, suppose that for any s ∈ [T ], ξ s = g s -ḡs satisfies Assumption (A3). Then for any given δ ∈ (0, 1), it holds that with probability at least 1 -δ,EQUATIONWe next provide a probabilistic upper bound as shown in (22) for a summation of the inner product, where we rely on the property of the martingale difference sequence and the proxy step-size a s in (23) . Lemma B.7. Given T ≥ 1 and δ ∈ (0, 1). If Assumptions (A2) and (A3) hold, then for any λ > 0, with probability at least 1 -δ,EQUATION)As a consequence, when setting λ = (1 -EQUATIONwhereD 1 = 3η (1-β1) √ 1-β2 log T δ .In this section, we shall assume that (35) or/and (37) hold whenever the related estimation is needed.Then we obtain the following key lemmas with the detailed proofs given in Appendix D. ∥ξ j ∥ ≤ G T (s), max j∈[s] ∥g j ∥ ≤ G T (s), max j∈[s] ∥v j ∥ ∞ ≤ (G T (s)) 2 , ∀s ∈ [T ].Lemma B.9. Given T ≥ 1. If b s = (b s,i ) i and a s = (a s,i ) i follow the definitions in ( 16) and ( 23) respectively, and (35) holds, then for all s∈ [T ], i ∈ [d], 1 a s,i - 1 b s,i ≤ G T (s) √ 1 -β 2 a s,i b s,i and 1 a s,i - 1 b s-1,i ≤ (G T (s) + ϵ) √ 1 -β 2 a s,i b s-1,i .Lemma B.10. Given T ≥ 1. Under the conditions in Lemma B.3 and Lemma B.5, if (35) holds, then the following inequality holds,F i (t) ≤ F(T ), ∀t ∈ [T ], i ∈ [d],where M = M (1 -β 1 ) and M follows the definition in Lemma B.5, F(T ) is define byEQUATION)We move to estimate all the related terms in Appendix B.2. First, the estimation for A.1 relies on both the two probabilistic estimations in Appendix B.3. Lemma B.11. Given T ≥ 1, suppose that (35) and (37) hold. Then for all t ∈ [T ],EQUATION)where D 1 is given as in Lemma B.7 andD 2 = η √ 1-β2 1-β1 .We also obtain the following lemma to estimate the adaptive momentum part B.1. Lemma B.12. Given T ≥ 1, if (35) holds, then for all t ∈ [T ],EQUATIONwhereEQUATION)Proposition B.13. Given T ≥ 1. If f is L-smooth, then the following inequality holds,f (y t+1 ) ≤f (x 1 ) + A.1 + B.1 + D 6 t-1 s=1 ms b s 2 + D 7 t s=1 g s b s 2 , ∀t ∈ [T ],where Σ max is as in Lemma B.1 andEQUATION)Proof. Recalling the decomposition in Appendix B.2. We first estimate A.2. Using the smoothness of f and ( 17), we haveEQUATIONHence, applying Young's inequality, ( 43) and (30) ,EQUATION)Recalling the updated rule in Algorithm 1 and applying (29) as well as (30) ,EQUATION)Therefore, applying (44) , (45) and β 1 ∈ [0, 1), and then summing over sEQUATION)Applying Cauchy-Schwarz inequality, Lemma B.1, and combining with ( 43), (45) , Σ max ≥ 1, andEQUATIONFinally, applying the basic inequality, Lemma B.1 and (45),EQUATION)Recalling the decomposition in (33) and (34) , then plugging ( 46), ( 47) and ( 48) into (32) , we obtain the desired result.Based on all the results in Appendix B.3 and Appendix B.4, we are now ready to provide a 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), it holds that with probability at least 1 -2δ,EQUATIONandEQUATIONwhere G 2 is as in Theorem 3.1 and G t , G, G T are given by (19) .Proof. Applying Lemma B.6 and Lemma B.7, we know that (35) or (37) hold with probability at least 1 -δ. With these two inequalities, we could deduce the desired inequalities ( 49) and (50) . Therefore, ( 49) and ( 50) hold with probability at least 1 -2δ. We first plug (39) and ( 40) into the result in Proposition B.13, which leads to that for all t ∈ [T ],EQUATIONNext, we will introduce the induction argument based on (51) . We first provide the specific definition of G 2 as follows which is a constant determined by the horizon T and other hyper-parameters but not relying on t,4 EQUATIONThe induction then begins by noting that (52) . Then we assume that for some t ∈ [T ],G 2 1 = ∥ḡ 1 ∥ 2 ≤ 2L(f (x 1 ) -f * ) ≤ G 2 from Lemma B.4 andEQUATIONUsing this induction assumption over (51) and subtracting with f * on both sides,EQUATIONFurther, we combine with Lemma B.3 and Lemma B.10 to estimate the four summations defined in Lemma B.3, and then useEQUATIONwhere H(G) = σ 1 G p/2 + G and D1 , D2 , D3 are defined asD1 = f (x 1 ) -f * + 2M T σ 0 D 1 , D2 = 2M T σ 0 D 2 + D 7 1 -β 2 + 4 (M T σ 0 D 3 + D 4 ) (1 -β 1 ) β 2 (1 -β 2 )(1 -β 1 /β 2 ) + D 6 (1 -β 2 )(1 -β 1 /β 2 ) d log F(T ) β T 2 , D3 = 2M T D 1 + D 2 d 1 -β 2 + 2D 3 (1 -β 1 )d β 2 (1 -β 2 )(1 -β 1 /β 2 ) log F(T ) β T 2 + D 5 .Applying Lemma B.5 and Lemma B.4,EQUATION)Then combining (55) with (56) ,∥ḡ t+1 ∥ 2 ≤ -L t s=1 η s ḡs √ a s 2 + 4L( D1 + D2 ) + 4L D3 H(G) + 2M 2 .Applying two Young's inequalities where ab ≤ a 2 2 + b 2 2 and abEQUATION)Recalling the definitions of D i , i ∈ [7] in ( 37), ( 39), (41) , and (42) . With a simple calculation relyingEQUATION)Based on ( 57) and (58), we then deduce that ∥ḡ t+1 ∥ 2 ≤ G 2 . Further combining with G t+1 in (19) and the induction assumption in (53) ,G t+1 ≤ max{∥ḡ t+1 ∥, G t } ≤ G.Hence, the induction is complete and we obtain the desired result in (49) . Furthermore, as a consequence of (57), we also prove that (50) holds.Now we are ready to prove the main convergence result.Proof of Theorem 3.1. We set t = T in (50) to obtain that with probability at least 1 -2δ,EQUATION)Then, in what follows, we will assume that both ( 49) and (59) hold. Based on these two inequalities, we could derive the final convergence bound. Since ( 49) and (59) hold with probability at least 1 -2δ, the final convergence bound also holds with probability at least 1 -2δ. Applying a s in ( 23) and ( 49), we haveEQUATIONThen combining with the setting η s and ϵ s in (6), we have for any s ∈ [T ],η s ∥a s ∥ ∞ ≥ C 0 (1 -β s 2 )(1 -β 2 ) G T 1 -β s 2 + ϵ 0 (1 -β s 2 )(1 -β 2 ) • 1 1 -β s 1 ≥ C 0 √ 1 -β 2 G T + ϵ 0 √ 1 -β 2 .We therefore combine with (59) to obtain that with probability at least 1 -2δ,EQUATION)Since β 2 ∈ (0, 1), we have-log β 2 = log 1 β 2 ≤ 1 -β 2 β 2 = c T β 2 ,where we apply log(1/a) ≤ (1 -a)/a, ∀a ∈ (0, 1). With both sides multiplying T , we obtain that log 1/β T 2 ≤ c/β 2 . Then, we further have that whenEQUATIONEQUATION)Therefore combining (62), ( 63) and ( 52), we could verify that G 2 ∼ O (poly(log T )) with respect to T . Finally, using the convergence result in (61), we obtain the desired result.In this section, we shall follow all the notations defined in Section 6. Further, we will add two non-decreasing sequences {Ls } s≥1 and {L (y)EQUATIONWe first mention that Lemma B.1, Lemma B.2, and Lemma B.3 in Appendix B.1 remain unchanged since they are independent of the smooth condition. Then the first essential challenge is that we need to properly tune η to restrict the distance between x s+1 and x s , y s+1 and y s within 1/L q for all s ≥ 1. The following two lemmas then ensure this point. The detailed proofs could be found in Appendix E. Lemma C.1. Let x s , y s be defined in Algorithm 1 and (17) .EQUATION)As a consequence, whenEQUATIONthen for any s ≥ 1, all the three gaps in (65) are smaller than 1/L q . Lemma C.2. Let η ≤ 1/(L q F ) where F is as in Lemma C.1. If f is (L 0 , L q )-smooth, then for any s ≥ 1, ∥∇f (y s )∥ ≤ L 0 /L q + ∥∇f (x s )∥ q + ∥∇f (x s )∥, ∥∇f (x s )∥ ≤ L 0 /L q + ∥∇f (y s )∥ q + ∥∇f (y s )∥. As a consequence, for any s ≥ 1,∥∇f (y s ) -∇f (x s )∥ ≤ L (x)s ∥y s -x s ∥, ∥∇f (y s+1 ) -∇f (y s )∥ ≤ L (y) s ∥y s+1 -y s ∥, (67)EQUATIONIn the generalized smooth case, Lemma B.4 does not hold. In contrast, we provide a generalized smooth version of [49, Lemma A.5], which establishes a different relationship between the gradient's norm and the function value gap. Noting that when q = 1, Lemma C.3 reduces to [49, Lemma A.5 ].Lemma C.3. Suppose that f is (L 0 , L q )-smooth and Assumption (A1) holds. Then for anyx ∈ R d , ∥∇f (x)∥ ≤ max 4L q (f (x) -f * ), [4L q (f (x) -f * )] 1 2-q , 4L 0 (f (x) -f * ) .The probabilistic inequalities in (35) and ( 36) remain unchanged since they do not rely on any smooth-related conditions. However, we shall rely on a different setting of λ in (36) as follows.Lemma C.4. Given T ≥ 1 and δ ∈ (0, 1). Under the same conditions of Lemma B.7, if we setλ = (1 -β 1 ) √ 1 -β 2 /(3ηH)where H is as in (11) , then with probability at least 1 -δ,EQUATIONwhere D 1 is given in Lemma B.7.The bounds of the four summations in Lemma B.3 also remain unchanged. However, the upper bound for F i (t) should be revised by the following lemma. The detailed proof could be found in Appendix E.Lemma C.5. Given T ≥ 1. Under the conditions and notations of LemmaEQUATIONand (66) hold, then the following inequalities hold,EQUATIONwhere J (t) is defined asEQUATIONandMt := C0 L (x) t d 1-β1/β2 .It's worth noting that J (t) is still random relying on the random variable L (x) t .Note that (40) in Appendix B.4 remains unchanged since it's independent from any smooth-related condition. In terms of A.1, the only difference is using H to replace G in (39) as we choose a different λ in (36) , leading toEQUATION)We also establish the following proposition which is a generalized smooth version of Proposition B.13. Proposition C.6. Given T ≥ 1. If f is (L 0 , L q )-smooth and (66) holds, thenEQUATIONwhere Σ max is as in Lemma B.1 and D 6 (s), D 7 (s) are defined as,5 D 6 (s) = L (y) s η 2 (1 + 4Σ 2 max ) 2(1 -β 1 ) 2 , D 7 (s) = 3L (y) s η 2 2(1 -β 1 ) 2 .Proof. The proof follows some same parts in proving Proposition B.14. We start from the descent lemma (68) in Lemma C.2 and sum over s ∈ [t] to obtain thatEQUATIONwhere A and B follow the same definitions in (32) . We also follow the decompositions in ( 33) and (34) . We could also rely on the same analysis for the smooth case in (46) but the smooth parameter is replaced byL (x)s . Hence, we obtain thatA.2 ≤ t s=1 L (x) s η 2 2(1 -β 1 ) 2 ms-1 b s-1 2 + t s=1 L (x) s η 2 2(1 -β 1 ) 2 g s b s 2 .(75)Similarly,EQUATIONNoting that C' differs from C with L replaced by Ls . Hence, relying on a similar analysis in (48), we obtain thatEQUATIONCombining ( 74) with (75), ( 76) and (77), and noting that L(x) s ≤ L (y)s from (64), we thereby obtain the desired result.Based on the unchanged parts in Appendix B.3 and Appendix B.4 and the new estimations in (72) and (73), we are now ready to provide the uniform gradients' bound in the following proposition.Proposition C.7. Under the same conditions in Theorem 4.1, for any given δ ∈ (0, 1/2), it holds that with probability at least 1 -2δ,EQUATIONandEQUATIONwhere H, H, L are given in (11) and Ĥ is given in (82).Proof. Based on the two inequalities ( 35) and (69), we could deduce the final results in (78) and (79). Since (35) and (69) hold with probability at least 1 -2δ, we thereby deduce the desired result holding with probability at least 1 -2δ. To start with, we shall verify that (66) always holds. Recalling η in (10) and F in Lemma C.1,ηF = C0 1 -β 2 F ≤ β 2 (1 -β 1 ) 2 (1 -β 2 )(1 -β 1 /β 2 ) 4L 2 q d • F ≤ 1 L q .Hence, we make sure that the distance requirement in (8) always holds according to Lemma C.1. Second, plugging (72) and ( 40) into the result in (73),EQUATION)We still rely on an induction argument to deduce the result. First, we provide the detail expressions of Ĥ, H as follows which is determined by hyper-parameters β 1 , β 2 and constants E 0 , d, T, δ, M T ,EQUATIONEQUATION)where E 0 > 0 is a constant and J (T ) is a polynomial of T given asEQUATIONand M := E 0 d 1-β1/β2 . The induction then begins by noting that from Lemma C.3 and H in (82),EQUATIONConsequently, recalling G T (s) in (19) , Ls , Ls in (64) and H, L in (11) ,G T (s) ≤ H, L (x) s ≤ L (y) s ≤ L, ∀s ∈ [t].(85) We thus apply (85) to (80),EQUATION)Further recalling the setting of C0 in (10) , with a simple calculation it holds that,EQUATION)Therefore, combining with (85), (87) and Mt in (71), we could use the deterministic polynomial J (t) to further control J (t) in (71),Mt ≤ C0 L d 1 -β 1 /β 2 ≤ E 0 d 1 -β 1 /β 2 = M , J (t) ≤ J (t) ≤ J (T ), log F i (t) β t 2 ≤ log J (t) β t 2 ≤ log J (T ) β T 2 , ∀t ≤ T, i ∈ [d].Then, we could use J (T ) to control the four summations in Lemma B.3 which emerge in (86). In addition, we rely on η = C0 √ 1 -β 2 and the induction assumptions of ( 84) and (85) to further upper bound the RHS of (86), leading toEQUATION)Then combining with (87) and the definition of Ĥ in (81), we obtain thatEQUATION)Then, further using Lemma C.2, Lemma C.3 and H in (82),∥ḡ t+1 ∥ ≤ L 0 /L q + ∥∇f (y t+1 )∥ q + ∥∇f (y t+1 )∥ ≤ L 0 /L q + (4L q ∆ t+1 ) q + (4L q ∆ t+1 ) q 2-q + (4L 0 ∆ t+1 ) q 2 + 4L q ∆ t+1 + (4L q ∆ t+1 ) 1 2-q + 4L 0 ∆ t+1 ≤ H.We then deduce that G t+1 = max{G t , ∥ḡ t+1 ∥} ≤ H. The induction is then complete and we obtain the desired result in (78). Finally, as an intermediate result of the proof, we obtain that (79) holds as well.Proof of Theorem 4.1. 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 (79), it holds that with probability at least 1 -2δ,EQUATION)Then in what follows, we would assume that (78) and (90) always hold. Relying on the two inequalities, we thereby deduce the final convergence result. Furthermore, since (78) and (90) hold with probability at least 1 -2δ, the final convergence result also holds with probability at least 1 -2δ. Using (78) and following the same analysis in (60),∥a s ∥ ∞ ≤ max i∈[d] (1 -β 2 )   s-1 j=1 β s-j 2 g 2 j,i + (G T (j)) 2   + ϵ s ≤ (H + ϵ) 1 -β s 2 , ∀s ∈ [T ].Combining with the parameter setting in (10) ,η s ∥a s ∥ ∞ ≥ η 1 -β s 2 (1 -β s 1 )∥a s ∥ ∞ ≥ C0 √ 1 -β 2 H + ϵ 0 √ 1 -β 2 .We then combine with (90) and H in (11) to obtain that with probability at least 1 -2δ,1 T T s=1 ∥ḡ s ∥ 2 ≤ 4 Ĥ T C0 2(σ 2 0 + σ 2 1 H p + H 2 ) √ 1 -β 2 + ϵ 0 log eT δ .Finally, following the same deduction in ( 62) and ( 63), we could derive that Ĥ ∼ O log η s b s-1,i η s-1 b s,i -1 = 1 - η s b s-1,i η s-1 b s,i < 1. When ηsbs-1,i ηs-1bs,i ≥ 1, let r = β s-1 2 . Since 0 < 1 -β s-1 1 < 1 -β s 1 , ∀s ≥ 2, then we have η s η s-1 = 1 -β s 2 1 -β s-1 2 • 1 -β s-1 1 1 -β s 1 ≤ 1 + β s-1 2 (1 -β 2 ) 1 -β s-1 2 = 1 + (1 -β 2 ) • r 1 -r .Since h(r) = r/(1 -r) is increasing as r grows and r takes the maximum value when s = 2. Hence, it holds thatEQUATION)Then, since ϵ s-1 ≤ ϵ s , we further haveEQUATION)Combining with ( 91) and ( 92), we haveη s b s-1,i η s-1 b s,i -1 = η s b s-1,i η s-1 b s,i -1 ≤ 1 + β 2 β 2 -1.Combining the two cases and noting that the bound holds for any i ∈ [d], we then obtain the desired result.s-1 j=1 β s-1-j 1 and applying (28) with M and α j replaced by M and g j,i respectively,EQUATIONHence, combining with the definition of b s,i in ( 16), we further have for any i ∈ [d] and s ≥ 2,m s-1,i b s-1,i ≤ m s-1,i √ v s-1,i = (1 -β 1 ) 2 s-1 j=1 β s-1-j 1 g j,i 2 (1 -β 2 ) s-1 j=1 β s-1-j 2 g 2 j,i ≤ 1 -β 1 √ 1 -β 2 M • s-1 j=1 β s-1-j 1 g 2 j,i s-1 j=1 β s-1-j 2 g 2 j,i ≤ 1 -β 1 √ 1 -β 2 M • s-1 j=1 β 1 β 2 s-1-j = 1 -β 1 √ 1 -β 2 1 -β s-1 1 1 -β 1 • 1 -(β 1 /β 2 ) s-1 1 -β 1 /β 2 ≤ (1 -β 1 )(1 -β s-1 1 ) (1 -β 2 )(1 -β 1 /β 2 ),where the last inequality applies β 1 < β 2 . We thus prove the first result. To prove the second result, from the smoothness of f ,EQUATION)Combining with (30) andEQUATION) Using ∥x s -x s-1 ∥ ≤ √ d∥x s -x s-1 ∥ ∞ and (94), ∥ḡ s ∥ ≤ ∥ḡ s-1 ∥ + LC 0 d 1 -β 1 /β 2 ≤ ∥ḡ 1 ∥ + LC 0 s d 1 -β 1 /β 2 .Proof of Lemma B.3. Recalling the updated rule and the definition of b s,i in ( 16), usingEQUATION)Proof for the first summation Using (96), for any i∈ [d], t s=1 g 2 s,i b 2 s,i ≤ 1 1 -β 2 t s=1 g 2 s,i ϵ 2 + s j=1 β s-j 2 g 2 j,i . Applying Lemma A.1 and recalling the definition of F i (t), t s=1 g 2 s,i b 2 s,i ≤ 1 1 -β 2 log 1 + 1 ϵ 2 t s=1 β t-s 2 g 2 s,i -t log β 2 ≤ 1 1 -β 2 log F i (t) β t 2 .Summing over i ∈ [d], we obtain the first desired result.Proof for the second summation Following from (96),t s=1 m 2 s,i b 2 s,i ≤ (1 -β 1 ) 2 1 -β 2 • t s=1 s j=1 β s-j 1 g j,i 2 ϵ 2 + s j=1 β s-j 2 g 2 j,i.Applying Lemma A.2 and β 2 ≤ 1, t s=1 m 2 s,i b 2 s,i ≤ (1 -β 1 ) 2 1 -β 2 • 1 (1 -β 1 )(1 -β 1 /β 2 ) log 1 + 1 ϵ 2 t s=1 β t-s 2 g 2 s,i -t log β 2 = 1 -β 1 (1 -β 2 )(1 -β 1 /β 2 ) log F i (t) β t 2 .Summing over i ∈ [d], we obtain the second desired result.Proof for the third summation Following from (96),t s=1 m 2 s,i b 2 s+1,i ≤ t s=1 (1 -β 1 ) s j=1 β s-j 1 g j,i 2 ϵ 2 (1 -β 2 ) + (1 -β 2 ) s+1 j=1 β s+1-j 2 g 2 j,i ≤ t s=1 (1 -β 1 ) 2 s j=1 β s-j 1 g j,i 2 ϵ 2 (1 -β 2 ) + (1 -β 2 )β 2 s j=1 β s-j 2 g 2 j,i.Applying Lemma A.2, and usingβ 2 ≤ 1, t s=1 m 2 s,i b 2 s+1,i ≤ (1 -β 1 ) 2 (1 -β 2 )β 2 • t s=1 s j=1 β s-j 1 g j,i 2 ϵ 2 β2 + s j=1 β s-j 2 g 2 j,i ≤ (1 -β 1 ) 2 (1 -β 2 )β 2 • 1 (1 -β 1 )(1 -β 1 /β 2 ) log 1 + β 2 ϵ 2 t s=1 β t-s 2 g 2 s,i -t log β 2 ≤ 1 -β 1 β 2 (1 -β 2 )(1 -β 1 /β 2 ) log F i (t) β t 2 .Summing over i ∈ [d], we obtain the third desired result.Proof for the fourth summation Following the definition of ms,i from ( 29), and combining with (96),t s=1 m2 s,i b 2 s,i ≤ (1 -β 1 ) 2 1 -β 2 • t s=1 1 1-β s 1 s j=1 β s-j 1 g j,i 2 ϵ 2 + s j=1 β s-j 2 g 2 j,i . Applying Lemma A.2 and using β 2 ≤ 1, t s=1 m2 s,i b 2 s,i ≤ (1 -β 1 ) 2 1 -β 2 • 1 (1 -β 1 ) 2 (1 -β 1 /β 2 ) log 1 + 1 ϵ 2 t s=1 β t-s 2 g 2 s,i -t log β 2 ≤ 1 (1 -β 2 )(1 -β 1 /β 2 ) log F i (t) β t 2 .Summing over i ∈ [d], we obtain the fourth desired result.Proof of Lemma B.4. Let x = x -1 L ∇f (x). Then using the descent lemma of smoothness,f ( x) ≤ f (x) + ⟨∇f (x), x -x⟩ + L 2 ∥ x -x∥ 2 ≤ f (x) - 1 2L ∥∇f (x)∥ 2 .Re-arranging the order, and noting that f( x) ≥ f * , ∥∇f (x)∥ 2 ≤ 2L(f (x) -f ( x)) ≤ 2L(f (x) -f * ).Proof of Lemma B.5. Applying the norm inequality and the smoothness of f ,∥∇f (x s )∥ ≤ ∥∇f (y s )∥ + ∥∇f (x s ) -∇f (y s )∥ ≤ ∥∇f (y s )∥ + L∥y s -x s ∥.Combining with the definition of y s in ( 17) and (95), and using β 1 ∈ [0, 1), we obtain the desired result that∥∇f (x s )∥ ≤ ∥∇f (y s )∥ + Lβ 1 1 -β 1 ∥x s -x s-1 ∥ ≤ ∥∇f (y s )∥ + LC 0 √ d (1 -β 1 ) 1 -β 1 /β 2 . D.2 Omitted proof in Appendix B.3 Proof of Lemma B.6. Let us denote γ s = ∥ξs∥ 2 σ 2 0 +σ 2 1 ∥ḡs∥ p , ∀s ∈ [T ].Then from Assumption (A3), we first have E zs [exp (γ s )] ≤ exp (1) . Taking full expectation, E [exp(γ s )] ≤ exp (1) . (1) , which leads to that with probability at least 1 -δ,A ∈ R, P max s∈[T ] γ s ≥ A = P exp max s∈[T ] γ s ≥ exp(A) ≤ exp(-A)E exp max s∈[T ] γ s ≤ exp(-A)E T s=1 exp (γ s ) ≤ exp(-A)T exp∥ξ s ∥ 2 ≤ log eT δ σ 2 0 + σ 2 1 ∥ḡ s ∥ p , ∀s ∈ [T ].Proof of Lemma B.7. Recalling the definitions of a s in (23) and ϵ s in Algorithm 1, we have for anyEQUATION)Then given any i ∈ [d], we setX s = -η s ḡs , ξ s a s , ω s = η s ḡs a s σ 2 0 + σ 2 1 ∥ḡ s ∥ p , ∀s ∈ [T ].Noting that ḡs , a s and η s are random variables dependent by z 1 , • • • , z s-1 and ξ s is only dependent on z s . We then verify that X s is a martingale difference sequence sinceE [X s | z 1 , • • • , z s-1 ] = E zs -η s ḡs , ξ s a s = -η s ḡs , E zs [ξ s ] a s = 0.Noting that ω s is a random variable only dependent by z 1 , • • • , z s-1 and applying Assumption (A3) and Cauchy-Schwarz inequality, we haveE exp X 2 s ω 2 s | z 1 , • • • , z s-1 ≤ E exp ξ 2 s σ 2 0 + σ 2 1 ∥ḡ s ∥ p | z 1 , • • • , z s-1 ≤ E zs exp ∥ξ s ∥ 2 σ 2 0 + σ 2 1 ∥ḡ s ∥ p ≤ exp(1), ∀s ∈ [T ].Applying Lemma A.3 and (97), we have that for any λ > 0, with probability at least 1 -δ,EQUATIONNote that for any t ∈ [T ], (98) holds with probability at least 1 -δ. Then for any fixed λ > 0, we could re-scale δ to obtain that with probability at least 1 -δ, for all t ∈ [T ], 19), together with (30), we have that with probability at least 1 -δ,t s=1 X s ≤ 3λ 4 √ 1 -β 2 t s=1 η 2 s ḡs √ a s 2 σ 2 0 + σ 2 1 ∥ḡ s ∥ p + 1 λ log T δ . Using σ 2 0 + σ 2 1 ∥ḡ s ∥ p ≤ G T (t), s ≤ t from (- t s=1 η s ḡs , ξ s a s ≤ 3ληG T (t) 4(1 -β 1 ) √ 1 -β 2 t s=1 η s ḡs √ a s 2 + 1 λ log T δ , ∀t ∈ [T ].Finally setting λ = (1 -β 1 ) √ 1 -β 2 / (3ηG T ), we then have the desired result in (37) .Proof of Lemma B.8. First directly applying (35) and G s in (19) , for any j ∈ [s],∥ξ j ∥ ≤ M T σ 2 0 + σ 2 1 ∥ḡ j ∥ p ≤ M T σ 2 0 + σ 2 1 G p j ≤ M T σ 2 0 + σ 2 1 G p s ≤ G T (s).Applying the basic inequality, ( 35) and M T ≥ 1, for any j ∈ [s],∥g j ∥ 2 ≤ 2∥ḡ j ∥ 2 + 2∥ξ j ∥ 2 ≤ 2M 2 T σ 2 0 + σ 2 1 ∥ḡ j ∥ p + ∥ḡ j ∥ 2 ≤ (G T (s)) 2. Finally, we would use an induction argument to prove the last result. Given any i ∈[d], noting that v 1,i = (1 -β 2 )g 2 1,i ≤ (G T (s)) 2 . Suppose that for some s ′ ∈ [s], v j,i ≤ (G T (s)) 2 , ∀j ∈ [s ′ ], v s ′ +1,i = β 2 v s ′ ,i + (1 -β 2 )g 2 s ′ ,i ≤ β 2 (G T (s)) 2 + (1 -β 2 )(G T (s)) 2 ≤ (G T (s)) 2 . We then obtain that v j,i ≤ (G T (s)) 2 , ∀j ∈ [s]. Noting that the above inequality holds for all i ∈ [d],we therefore obtain the desired result.Proof of Lemma B.9. Recalling the definition of b s,i in ( 16) and letting a s,i = ṽs,i + ϵ s in ( 23),1 a s,i - 1 b s,i = √ v s,i -ṽs,i a s,i b s,i = 1 -β 2 a s,i b s,i g 2 s,i -(G T (s)) 2 √ v s,i + ṽs,i ≤ 1 -β 2 a s,i b s,i • (G T (s)) 2 √ v s,i + β 2 v s-1,i + (1 -β 2 )(G T (s)) 2 ≤ G T (s) √ 1 -β 2 a s,i b s,i ,where we apply g 2 s,i ≤ ∥g s ∥ 2 ≤ (G T (s)) 2 from Lemma B.8 in the first inequality since (35) holds. The second result also follows from the same analysis. We first combine withEQUATIONwhere we apply√ a - √ b ≤ √ a -b, ∀0 ≤ b ≤ a.Applying the definition of b s-1,i and a s,i ,1 b s-1,i - 1 a s,i = ṽs,i - √ v s-1,i + (ϵ s -ϵ s-1 ) b s-1,i a s,i ≤ 1 b s-1,i a s,i (1 -β 2 ) (G T (s)) 2 -v s-1,i ṽs,i + √ v s-1,i + |ϵ s -ϵ s-1 | b s-1,i a s,i ≤ 1 b s-1,i a s,i • (1 -β 2 )(G T (s)) 2 ṽs,i + √ v s-1,i + ϵ √ 1 -β 2 b s-1,i a s,i ≤ (G T (s) + ϵ) √ 1 -β 2 b s-1,i a s,i .where the second inequality applies v s-1,i ≤ (G T (s)) 2 in Lemma B.8 and the last inequality comes from√ 1 -β 2 G T (s) ≤ ṽs,i .Proof of Lemma B.10. Applying the basic inequality and ( 35), for all tEQUATIONCombining with Lemma B.2, we havet s=1 ∥ḡ s ∥ p ≤ t s=1 ∥ḡ 1 ∥ + LC 0 √ ds 1 -β 1 /β 2 p ≤ t • ∥ḡ 1 ∥ + LC 0 √ dt 1 -β 1 /β 2 p t s=1 ∥ḡ s ∥ 2 ≤ t • ∥ḡ 1 ∥ + LC 0 √ dt 1 -β 1 /β 2 2 .Further applying the definition ofF i (t) in Lemma B.3, it leads to F i (t) ≤ F(t), ∀i ∈ [d].Finally, since F(t) is increasing with t, we obtain the desired result.Proof of Lemma B.11. First, we have the following decomposition,EQUATIONSince ( 35) holds, we could apply Cauchy-Schwarz inequality, Lemma B.9, and G T (s) ≤ G T (t), ∀s ≤ t from (19) to obtain that for all t ∈ [T ],EQUATION≤ 1 4 t s=1 η s ḡs √ a s 2 + ηG T (t) √ 1 -β 2 1 -β 1 t s=1 g s b s 2 .Finally, combining with (37) for estimating A.1.1, we deduce the desired result in (39) .Proof of Lemma B.12. Let us denote Σ := β1 1-β1 ⟨∆ s ⊙ (x s -x s-1 ), ḡs ⟩ where ∆ s is defined in (20) . We haveEQUATIONSince ( 35) holds, we could apply Lemma B.9 and Young's inequality and then use (97), (30) ,EQUATION)Using the similar analysis for Σ 1 , we also haveEQUATION)Then we move to bound the summation of Σ 3 over s ∈ {2, • • • , t} since m 0 = 0. Recalling s in (30), we have the following decomposition,EQUATION)Noting that ∥ḡ s ∥ ≤ G s ≤ G t , ∀s ≤ t. Then further applying Cauchy-Schwarz inequality and Lemma B.2,1 -β s 2 ḡs , m s-1 b s-1 ≤ 1 -β s 2 ∥ḡ s ∥ m s-1 b s-1 ≤ √ dG t (1 -β 1 )(1 -β s-1 1 ) (1 -β 2 )(1 -β 1 /β 2 ).Hence, summing Σ 3.1 up over s ∈ [t], applying β 1 ∈ (0, 1) and noting that Σ 3.1 vanishes when s = 1,EQUATIONSimilarly, using ∥ḡ s ∥ ≤ G s ≤ G t , ∀s ≤ t and 1 -β s-11 ≥ 1 -β 1 , 1 1 -β s-1 1 ḡs , m s-1 b s-1 ≤ 1 1 -β s-1 1 ∥ḡ s ∥ m s-1 b s-1 ≤ √ dG t 1 (1 -β 2 )(1 -β 1 /β 2 ).Hence, summing Σ 3.2 up over s ∈ [t] and still applying β 1 ∈ [0, 1),EQUATIONCombining with (105), ( 106) and (107), we obtain an upper bound for t s=1 Σ 3 . Summing (102), ( 103) and (104) up over s ∈ [t], and combining with the estimation for t s=1 Σ 3 , we obtain the desired inequality in (40) .Proof of Lemma C.1. Recalling in (95), we have already shown that∥x s+1 -x s ∥ ≤ √ d∥x s+1 -x s ∥ ∞ ≤ η d (1 -β 2 )(1 -β 1 /β 2 ), ∀s ≥ 1.(108)Applying the definition of y s in (17) , an intermediate result in (108) andEQUATIONRecalling the iteration of y s in (18) and then using Young's inequality∥y s+1 -y s ∥ 2 ≤ 2η 2 s g s b s 2 ( * ) + 2β 2 1 (1 -β 1 ) 2 η s b s-1 η s-1 b -1 2 ∞ ∥x s -x s-1 ∥ 2 ( * * ). 16), we then combine with (30) to haveNoting that g s,i /b s,i ≤ 1/ √ 1 -β 2 from (( * ) ≤ 2η 2 s • d 1 -β 2 ≤ 2η 2 d (1 -β 1 ) 2 (1 -β 2 ).Applying Lemma B.1 where Σ 2 max ≤ 1/β 2 and (108),( * * ) ≤ 2η 2 β 2 1 Σ 2 max d (1 -β 1 ) 2 (1 -β 2 )(1 -β 1 /β 2 ) ≤ 2η 2 d β 2 (1 -β 1 ) 2 (1 -β 2 )(1 -β 1 /β 2 ).Summing up two estimations and using 0 ≤ β 1 < β 2 < 1, we finally haveEQUATION)Combining with (108), ( 109) and (110), and using 0 ≤ β 1 < β 2 < 1, we then deduce a uniform bound for all the three gaps.Proof of Lemma C.2. Under the same conditions in Lemma C.1, we have∥y s -x s ∥ ≤ 1 L q , ∥y s+1 -y s ∥ ≤ 1 L q .Then, using the generalized smoothness in (8) , ∥∇f (y s )∥ ≤ ∥∇f (x s )∥ + ∥∇f (y s ) -∇f (x s )∥ ≤ ∥∇f (x s )∥ + (L 0 + L q ∥∇f (x s )∥ q )∥y s -x s ∥ ≤ ∥∇f (x s )∥ + ∥∇f (x s )∥ q + L 0 /L q .We could use a similar argument to deduce the bound for ∥∇f (x s )∥. Further, combining with L (x) s and Ls in (64), we could bound the generalized smooth parameters asEQUATIONWe could then deduce the first two inequalities in (67). Finally, (68) could be deduced by using the same argument in the proof of [49, Lemma A.3] .Proof of Lemma C.3. Given any x ∈ R d , we letτ = 1 L 0 + L q max{∥∇f (x)∥ q , ∥∇f (x)∥} , x = x -τ ∇f (x).From the definition of τ , we could easily verify that ∥ x -x∥ = τ ∥∇f (x)∥ ≤ 1/L q . Since f is (L 0 , L q )-smooth, we could thereby use the descent lemma in [49, Lemma A.3 ] such thatf ( x) ≤ f (x) + ⟨∇f (x), x -x⟩ + L 0 + L q ∥∇f (x)∥ q 2 ∥ x -x∥ 2 = f (x) -τ ∥∇f (x)∥ 2 + (L 0 + L q ∥∇f (x)∥ q )τ 2 2 ∥∇f (x)∥ 2 ≤ f (x) - τ 2 ∥∇f (x)∥ 2 .Since f ( x) ≥ f * , when ∥∇f (x)∥ = 0, the desired result is trivial. Let us suppose ∥∇f (x)∥ > 0.Case 1 ∥∇f (x)∥ q > ∥∇f (x)∥ τ 2 ∥∇f (x)∥ 2 = ∥∇f (x)∥ 2-q 2L 0 /∥∇f (x)∥ q + 2L q ≤ f (x) -f ( x) ≤ f (x) -f * .When ∥∇f (x)∥ q < L 0 /L , it leads to∥∇f (x)∥ 2 4L 0 = ∥∇f (x)∥ 2-q 4L 0 /∥∇f (x)∥ q ≤ ∥∇f (x)∥ 2-q 2L 0 /∥∇f (x)∥ q + 2L q ≤ f (x) -f * .When ∥∇f (x)∥ q ≥ L 0 /L q , it leads to∥∇f (x)∥ 2-q 4L q ≤ ∥∇f (x)∥ 2-q 2L 0 /∥∇f (x)∥ q + 2L q ≤ f (x) -f * .We then deduce thatEQUATION)Case 2 ∥∇f (x)∥ q ≤ ∥∇f (x)∥ We could rely on the similar analysis to obtain that7 EQUATIONCombining ( 112) and ( 113), we then deduce the desired result.Proof of Lemma C.5. Recalling (95), we then obtained that whenEQUATION)Noting that when (66) holds, we have∥ḡ s ∥ ≤ ∥ḡ s-1 ∥ + ∥ḡ s -ḡs-1 ∥ ≤ ∥ḡ s-1 ∥ + (L 0 + L q ∥ḡ s-1 ∥ q )∥x s -x s-1 ∥ ≤ ∥ḡ s-1 ∥ + C0 L (x) s-1 d 1 -β 1 /β 2 ≤ ∥ḡ 1 ∥ + C0 d 1 -β 1 /β 2 s-1 j=1 L (x) j . Using L (x) j ≤ L (x) t , ∀j ≤ t, we have t s=1 ∥ḡ s ∥ p ≤ t s=1 ∥ḡ 1 ∥ + C0 d 1 -β 1 /β 2 (s -1)L (x) t p ≤ t ∥ḡ 1 ∥ + t C0 L (x) t d 1 -β 1 /β 2 p .Similarly, we also havet s=1 ∥ḡ s ∥ 2 ≤ t ∥ḡ 1 ∥ + t C0 L (x) t d 1 -β 1 /β 2 2 .Further combining with F i (t) in Lemma B.3 and J (t) in (71),F i (t) ≤ 1 + 1 ϵ 2 t s=1 ∥g s ∥ 2 ≤ J (t), ∀t ∈ [T ], i ∈ [d].Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In 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 approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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 of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Note that we hide the constants β1, β2 inside O. The detailed expression of G 2 could be found in(52) from Appendix.The specific definition of Ĥ can be found in (82) from Appendix.We further deduce(7) in Theorem 3.1 based on(52).The notations are different from D6 and D7 defined in(42).The inequality still holds for s = 1 since x1 = y1.We refer readers to see[51, Lemma A.5] for a detailed proof under this case. 


Decision: All reviewers think the paper is interesting.  I recommend an acceptance.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

I will increase the score if this concern is addressed.
questions: 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?
2. Why in Table 1 you did not include [19] which you discussed in Section 5.1?
3. 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: limitations: See weaknesses and questions above
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: 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.
2. 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. 
3. 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].
4. 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).
5. In formula (58), line 557, where the last $\sqrt{\log}$ term comes from?
6. What's the meaning of formulas (59) and (60) since $G^2 \sim O(\text{polylog}T)$ has been claimed in formula (7)

[1] Balles, Lukas, Fabian Pedregosa, and Nicolas Le Roux. "The geometry of sign gradient descent." arXiv preprint arXiv:2002.08056 (2020).

[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: limitations: No limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. In line 118, the reference [10] is cited repeatedly.

3. 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. 

4. 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$.
questions: questions: 1. What is the symbol $\xi$ in Equation (1)? It should be explained in the main text.

2. What are the meanings of “right parameter” mentioned in line 4 (Abstract) and “problem parameter” in line 19?

3. 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?

4. 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: 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.

Comments: title: Discussions
Thank you for your positive feedback
comment: Dear reviewers, 

Thanks very much for your great efforts in the review process. Please read the authors' response and confirm it.  You are encouraged to discuss with all of us if you have any concerns.

Thanks,
AC
Thank you so much for your reply and generosity in raising the score. We thank a lot for the valuable suggestion from the reviewer and agree that considering the smaller $\beta_2$ setup would be a quite interesting topic for the future investigation. We shall add a brief remark related to this point after our main results.

Best regards,

Authors.
Thank you for the detailed explanations! 

I understand that $v_t$ is not a constant for $\beta_2=1-1/T$, but an exponential moving average of past gradient squared. Say $v_t=w_0 g_0^2+\cdots+w_{t} g_t^2$. One can show that $w_0=(1-1/T)^{t}\ge 1/e=O(1)$, which means $v_t$ never forgets the initial gradients. I feel this may simplify the analysis in some way. It should be more interesting to extend the result to a smaller $\beta_2$ like $1-1/\sqrt{T}$. That being said, I agree that the analysis is already non-trivial compared to SGDM, and would like to increase my score.
We thank Reviewer 4Xir very much for his positive comment and prompt reply.  We also thank Reviewer 4Xir for the constructive comments on investigating Adam with the $\ell_\infty$ norm and we agree that it is important.  We thank Reviewer 4Xir for the interesting references which we think are interesting and can better enhance the understanding of Adam.
Thanks to the authors for their clarifications. There might exist some minor concerns about novelty and experiment results, But as I claimed in my review, I think it's a good paper, and I'm happy to retain both scores of rating and confidence. Moreover, I would like to mention that analyzing the Adam from the $\ell_\infty$ norm might be interesting, since the geometry of Adam might align with the $\ell_\infty$ norm better as studied in [1, 2, 3]. 

[1] Kunstner, F., Chen, J., Lavington, J. W. and Schmidt, M. (2023). Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. ICLR.

[2] Xie, S. and Li, Z. (2024). Implicit bias of adamw: $\ell_\infty$ norm constrained optimization. ICML.

[3] Zhang, C., Zou, D. and Cao, Y. (2024). The Implicit Bias of Adam on Separable Data. arXiv: 2406.10650.
We thank a lot for the reviewer's quick feedback and generosity in raising the score. As far as we can understand, the reviewer still has two questions:

- whether there is an expectation form in $\nabla f(x)$;
- the result is not full high probability.

We then answer as follows:

- **The loss function $f$ is not necessarily the expected form in Eq. (1).** We indeed only require $f$ to be differentiable and smooth. We will clarify this in the revised version. In this sense, $\nabla f(x)$ also not necessarily includes the expectation.
- **$\\|\nabla f(x)\\|^2 \le \varepsilon$ implies that $x$ is near-stationary, which is a standard measure in non-convex smooth optimization.** Our high probability result shows that $\frac{1}{T}\sum_{t=1}^T \\|\nabla f(x_t)\\|^2\le \varepsilon$, indicating that there exists at least one near-stationary point $x_{\tau},\tau \in [T]$. 
- As far as we could understand, (please correct me if I was wrong), the fully high probability you mention is to derive a high probability bound for $\frac{1}{T}\sum_{t=1}^T \\|g(x_t,z_t)\\|^2$. We think that this could be meaningful. However, given the second point, the high probability bound related to $\frac{1}{T}\sum_{t=1}^T \\|\nabla f(x_t)\\|^2$ could implies a near-sationary point while the bound for $\frac{1}{T}\sum_{t=1}^T \\|g(x_t,z_t)\\|^2$ may not, which we will show through an example at the end.
- In addition, since $\frac{1}{T}\sum_{t=1}^T \\|\nabla f(x_t)\\|^2$ is an entirely random variable with respect to $z_1,\cdots,z_{T}$, **our result is fully high probability over random samples $z_1,\cdots,z_T$​.** However, when Assumption (A2) holds, we could choose any random sample $z_t'$ that is independent from $z_t$ and obtain that $\nabla f(x_t) = \mathbb{E}_{z_t'}[g(x_t,z_t')]$. Hence, due to the additional expectation on $z_t'$, we agree that the obtained result is not fully high probability without restricting on $z_1,\cdots,z_T$.

We also present a simple example to help better understand the difference of two types of measure. Suppose that the loss function is $f(x)=x^4$, which does not include expectation in its gradient. We now consider the following SGD algorithm (with differences to Adam in step-size):

- Input $x_1$ and step-size $\eta > 0$;
- For $t = 1\cdots T:$
  - Draw a random sample $z_t$ such that $\mathbb{E}[z_t \mid x_t]=0$ (e.g., a Gaussian white noise);
  - Generate the stochastic gradient $g(x_t,z_t) = 4x_t^3+z_t$ (which is an unbiased estimator);
  - Update the sequence as $x_{t+1} =x_{t} - \eta (4x_{t}^3 + z_t)$.

If we obtain that $\frac{1}{T}\sum_{t=1}^T (4x_{t}^3)^2 \le \varepsilon$ with high probability (as in our paper), which is fully high probability over $z_1,\cdots, z_{T}$, then we are able to deduce that at least one gradient $(4x_{\tau}^3)^2,\tau \in [T] $ is small enough and $x_{\tau}$ is near-stationary. However, if we obtain the fully high probability bound $\frac{1}{T}\sum_{t=1}^T (4x_{t}^3 + z_{t})^2 = \frac{1}{T}\sum_{t=1}^T [(4x_{t}^3)^2 + z_t^2  + 8x_t^3z_t]\le \varepsilon$, then we could not derive any stationary point from this inequality since the term $x_t^3 \cdot z_t$ may be non-zero. 

We hope that the above answer and example could address your questions. If you have any further inquiries, we are delighted to discuss them with you.



Best regards,

Authors.
Thanks for the detailed responses to my questions. I will raise my score to 6. However, I am still confused about the sentence "In general, $\nabla f(x)$ does not need to be of the expectation form, while for Eq. (1)". Why is Eq. (1) of the expectation form, but the author says there is no need for expected form? And due to the implicit expectation of $\nabla f(x)$, the results of this paper are not fullly high-probability. Is my understanding right?