Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance
Authors: Qi Zhang
Yi Zhou
Shaofeng Zou
Venue: Accepted by TMLR ()

Abstract: This paper provides the first tight convergence analyses for RMSProp and Adam for non-convex optimization under the most relaxed assumptions of coordinate-wise generalized smoothness and affine noise variance. 
RMSProp is firstly analyzed, which is a special case of Adam with adaptive learning rates but without first-order momentum. Specifically, to solve the challenges due to the dependence among adaptive update, unbounded gradient estimate and Lipschitz constant, we demonstrate that the first-order term in the descent lemma converges and its denominator is upper bounded by a function of gradient norm. Based on this result, we show that RMSProp with proper hyperparameters converges to an $\epsilon$-stationary point with an iteration complexity of $\mathcal O(\epsilon^{-4})$. We then generalize our analysis to Adam, where the additional challenge is due to a mismatch between the gradient and the first-order momentum. We develop a new upper bound on the first-order term in the descent lemma, which is also a function of the gradient norm. We show that Adam with proper hyperparameters converges to an $\epsilon$-stationary point with an iteration complexity of $\mathcal O(\epsilon^{-4})$. Our complexity results for both RMSProp and Adam match with the complexity lower bound established in Arjevani et al. (2023).

Published in Transactions on Machine Learning Research (02/2025)
Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance
Qi Zhang
qzhan261 @asu. edu
School of Electrical, Computer and Energy Engineering Arizona State University
Yi Zhou
yi. gi.chou@tamas edu
Deportment of Computer Science and Engineerin Texas A&M University
Shaofeng Zou
zou@asuu.co edu
School of Electrical, Computer and Energy Engineering Arizona State University
Reviewed on OpenReview: https: // openreviee.... net/ forum? id= IInd
Abstract
This paper provides the first tight convergence analyses for RMSProp and Adam for non- convex optimization under the most relaxed assumptions of coordinate-wise generalized smoothness and affine noise variance. RMSProp is firstly analyzed, which is special case of Adam with adaptive learning rates but without first-order momentum. Specifically, to solve the challenges due to the dependence among adaptive update, unbounded gradient estimate and Lipschitz constant, we demonstrate that the first-order term in the descont lemma converges and its denominator upper bounded by a function of gradient norm. Based on this result, we show that RMSProp with proper hyperparameters converges an e-stationary point with an iteration complexity of O(e-)). We then generalize our analysis to Adam, where the additional challenge is due to mismatch between the gradient and the first-order momentum. We develop new upper bound on the first-order term in the descent lemma, which is also a function of the gradient norm. We show that Adam with proper hyperparameters converges to an e-stationary point with an iteration complexity of O(e-t) Our complexity results for both RMSProp and Adam match with the complexity lower bound established Arjevani et al. (2023
1 Introduction
RMSProp (Hinton et al. 2012 and Adam Kingma & Ba. 2014] are among the most popular and powerful adaptive optimizers in training state-of-the-art machine learning models (Brock et. al. 2018 Brown et al. 2020 Cutkosky Mchtal 2020 Dosovitskiy al., (020). RMSProp and Adam only require first-order gradients with little memory requirement, and thus are efficient to in practice. RMSProp based the idea of adaptive learning rates for each individual parameter, and Adam combines the benefits of RMSprop (Hinton et al.] 2012) and AdaGrad (Duchi et al. 2011), which consists of two key components of adaptive learning rates and momentum. Despite their empirical success, theoretical understandings on the convergence and complexity, especially when optimizing non-convex loss functions, e.g., neural networks, still remain underdeveloped until very recently.
Recently, there have been series of works in examining the convergence and complexity of RMSProp and Adam for non-convex loss functions (see Table 1 for detailed review). However, these works do

---

Published in Transactions on Machine Learning Research (02/2025)
not completely explain the performance of RMSProp and Adam in training neural networks, they rely assumptions that may not necessarily hold. For example, Zhang et al. (2019) pointed out that neural networks are not L-smooth, and instead satisfy the generalized (Lo, L1 -mmoothessssss where the gradient Lipschitz constant increases linearly with the gradient norm. Furthermore, many of these works assumed that the stochastic gradient has a bounded norm/varionn /varianceeee which however does not even hold for linear regression (Wang et al.) 2023b), and instead a relaxed affine noise variance condition shall be used.
In this paper, we derive the convergence guarantee and iteration complexity for RMSProp and Adam with coordinate-wise generalized (Lo, L.m-mmotth loss function and affine noise variance. To the best of our knowledge, this is one of the most relaxed assumption sets in the convergence analyses of RMSProp and Adam that best describe the training of some neural networks. We prove that RMSProp and Adam with proper hyperparameters converge to an e-stationary point with a complexity of (ce which matches with the lower bound for first-order optimization in Arjevani et al. (2023).
1.1 Related work
1.1.1 Relaxed Assumptions
Affine Noise Variance: In most of the studies on stochastic optimization, access to an unbiased estimate of the gradient with uniformly bounded variance is assumed [Nemiovvskij & Yudin 1983 Ghadimi & Lan 2013
Bubeck et al. 2015 Foster et al. 2019h. Ghadimi & Lan (2013) first showed that for I-smooth objectives,
the SGD algorithm converges to a first-order e-stationary point with an iteration complexity of O(e=*) if
the stochastic gradient has uniformly bounded variance. Furthermore, [Arevani et al. (2023) proved that for any first-order algorithm with uniformly bounded gradient variance, the iteration complexity of O is optimal. For overparameterized neural networks, Vaswani et al. (2019) considered another gradient noise assumption: the strong growth condition, where the upper bound on the second-order moment of the norm of gradient estimate scales with the gradient square norm. Both the uniformly bounded variance and strong growth condition are special cases of the affine noise variance. It was demonstrated in Bottou et al. (2018) that for non-adaptive algorithms with affine noise variance, the optimal itcration complexity of O(c can be achieved. The exlension of afline noise variance assumption to adaptive algorit is not straight.orward
and was studied in Jin et al. (2021]; |; Chen et al. (2023); Wang et al. (2022 2023b); Shi et al. (2020): Faw
let al. (2022 )023); Hong & Lin (2023). In this paper, we study two adaptive optimizers: RMSProp and
Adam with affine noise variance.
Generalized Smoothness: In stochastic optimization, the L-smooth objectives widely assumed Ghadimi & Lan 2013 Ghadimi et al. 2016). However, it was demonstrated in Zhang et al. (019 that the L-smoothness does not hold for some neural networks and polynomial functions with degree larger than 2. Then, extensive experiments were conducted to verify that these functions satisfy the generalized (To, In)- smoothness condition, where the gradient Lipschitz constant increases linearly with the gradient norm. Com- pared with L-smoothness, (La. Li)-smoothness introduces extra socond-order error terms, thus making the optimization problem hard to solve. The clipping algorithms for generalized smooth function were studied in Zhang et al. 2019 2020). However, they require the gradient norm to be bounded. A relaxed assumption on bounded gradient variance was studied in Reisizadeh et al. (2023), where the SPIDER algorithm was applied. Furthermore, Chen et al. (2023) showed that for generalized smooth objectives with affine noise variance, the SPIDER algorithm still finds a stationary point. Under the same assumption, Jin et al. (202)) provided the convergence rate for a normalized momentum algorithm. With extensive experiments, Crawshaw et al. (2022) showed that in the training of Transformer, the (Lo, Ln J-mmothhness holds coordinate-wisely. This condition is widely used in coordinate-wise type optimizers like generalized SignSGD and Adam. Note that for the original Adam, proving the expectation of gradient norm converges with (Lo, Lm)-mmoothness remains unresolved issue. In this paper, consider functions that are coordinate-wie (Lo, Ly)-smooth.
1.1.2 Adaptive Optimizers
Adaptive optimizers are widely used in deep learning due to their ability to adapt to changing data and conditions. Adagrad (Duchi et al. (201]) is the first adaptive algorithm, which calculates the accumulated sum of the past gradient norms and uses the reciprocal of its square root to scale the current. gradient.
2

---

Published in Transactions on Machine Learning Research (02/2025)
Recently, Wang et al. (2023b); Faw et al. (2023 studied Adagrad under generalized smoothness and affine noise variance conditions. However, the training of the above Adagrad algorithm may stop in advance since the accumulated sum does not shrink, and thus the learning rate can be extremely close to 0. To overcome this problem, RMSProp (Hinton et al. 2012) was proposed, where a momentum method is employed to replace the accumulated sum. Thus, the adaplive learning rate can increase or decrease. There a rich literature on the convergence analyses of RMSProp (Zaheer et al.) 2018 De al. 2018 Shi et al. 2020). However, all of them focus on L-smooth objectives, and only (Shi et al. (2020) considered the alfine noise variance. RMSProp is special case of Adam, which only includes the second-order momentum, and is widely studied e.g.. Défossez et al. (2020): Zou et al. (2019); Chen et al. (2018); Zhang et al. (2022); Wang (et al. (022); Guo et al. (2021); Hong & Lin| (2023) | Li et al. (2023); Wang et al. (2023a). There are also two recent works (Hong& & Lin 2023 Wang et al. 2023a) that studied Adam for L-smooth objectives with affine noise variance. However, their methods can not be generalized to (Lo.L) L1) smooth objectives due to the additional terms invalidating the key incqualities or requirements of bounded Lipchitz constant in their key Lemma. In Li al. (2023), Adam for (Lo, Li )-smoothh objectives with sub-Gaussian norm was studied, where the gradient estimate bias follows sub-Gaussia distribution. Under this assumption, based on the gradient estimate, the real gradient belongs to bounded set with high probability, which converts the unbounded Lipschitz constant to bounded one. However, the bounded Lipschitz constant is quite large, which leads to small step sizes and slow practical convergence. Adam on (Lo, L )-smoothness with affine noise variance (for the special case of finite sum problems) were in Wang et al. (2022). However, they only showed that Adam converges to the neighborhood of stationary point with a constant learning rate, More details can be found in Table
Method
Smoothness
Algorithm
Convergence
Assumption
Batch size Complexity
De et al.
2018
(LS)
RMSProp
(BN)*
0(1)
O
Zaheer et 2018
(LS)
RMSProp
(BN)
0
O
Shi et al. 2020
(LS)
RMSProp
(TSAN)
Défossez et al. (020)
(LS)
Adam
(BN)
0(1)
Zou et al. 2019
(LS)
Adam
(BSM)
0(1)
Chen et
2018
(LS)
Adam
(BN)
Zhang et al.
2022
(LS)
Adam
X
(FSAN)
Wang et al.
2022
(FSGS)
Adam
(FSAN)
Guo et al.
2021
(LS)
Adam
(AN)s
0(1)
Hong & Lin
[2023
(LS)
Adam
(CAN)
0(1)
Wang al.
(2023a
(LS)
Adam
(CAN)
0(1)
Li et al.
2023
(GS)
Adam
(SGN)
0(1)
Wang al. (2024)
(GS) Scalar Adam
(AN)
0(1)
Our method
(CWGS)
Adam
(CAN)
0(1)
Table 1: Comparison for existing RMSProp and Adam analyses. For V ff(x) with its estimate g, the bounded norm assumption is ||g]| < G (almost surcly), where G is some positive constant. The bounded socond-order moment assumption is that Elllg| [2] < G². The bounded sub- Sab-Gasssian norm assumption is that lgg V f=)) follows a sub-Gaussion distribution, which weaker than the bounded norm assumption but stronger than the bounded variance assumption. The batch size refers the number of samples necessary to compute the gradient estimate g and complexity denotes the total computational effort required to achieve an e-stationary point. Explanation on the upper footmarks: 1 (I.S) indicates the standard T-smoothness, (GS) denotes the gencralized (Lo, L1)- smoothhesss (FSGS) denotes the finite sum (Lu, L.)-mmothhness and (CWGS) indicates the coordinate-wise (Lo, L1 )-smoothness. 2 X indicates the algorithm only converges to the neighborhood of a stationary point, whose radius can not be made small. 3 (BN) indicates Bounded Norm, (FSAN) indicates Finite Sum Affine Noiso, (BSM) indicates Bounded Second-order Moment, (AN) indicates Affine Noise, (CGN) indicates Sub-Gaussian Norm. 4 De al. (2018) also requires the signs of the gradients be the same across batches. 5 Guo et al. (2021) also requires the upper bound on the gradient norm. 6: A reduced method is also investigated in Li et al. (2023), and the complexity is O
3

---

Published in Transactions on Machine Learning Research (02/2025)
When preparing this work, we have observed concurrent work by Wang et al. (2024). which studies scalar-or
of Adam. In this paper, we study the per-coordinate version of Adam with the practical and challenging coordinate-wise L1.-ooommoohh objectives (see Algorithm for more details).
2 Preliminaries
Let f: I2 + IR be a differentiable non-convex loss function. For a positive integer d, let [d] denote the set [1, Let æ E Idd be an optimization variable. Our goal is to minimize the objective function f(x):
min (m²)
For a differentiable function f, point æ E Rd is called a first-order e-stationary point if [V S e. Denote by H, E Rd the optimization variable at the f-th iteration and we have access to an estimate gt of f(())) Define J. = o-.1.---991 9t-1) is the sigma field of the stochastic gradients up to - 1. We focus the Adam algorithm shown in Algorithm (. Ir,i, ma,; and ve are the i-th element of V (xxx), 9s, My and Ut, respectively.
[ where O denotes the Hadamard product. For any [d].
The Adam algorithm is provided in Algorithm in the adaptive stepsize from 7 vo to 7
I Compared with the original Adam, we make a minor change This minor change does not influence the adaptivity of Ve.+<" the algorithm but makes the analysis much casier.
"
2.1 Technical Assumptions
Throughout this paper, we make the following assumptions.
Assumption 1. fxx) is bounded from below such that inf f(x) > -00
Assumption 2 (Coordinate-wiss affine noise variance (Wang et al. 2023a Hong & Lin 2023) ). We have access to an unbiased gradient estimate 9t such that F.g. = (f())) and for any i E [d]. TE Egg [ s
+ + (.: where Do. D1 0 are some constants.
2
As discussed in Hong & Lin 2023), this assumption allows the magnitude of noise to scale with the cor- rosponding gradient coordinate. Many widely used noise assumptions special cases of this affine noise variance assumption. For example, when D1 = 0, it is the bounded second-order moment assumption in Zou et al. (219)) and when D2 1, it is equivalent to coordinate-we wirsi bounded gradient variance, However, as pointed out in Wang et al. (2023b), these two assumptions of bounded second-order moment and bounded gra- dient variance do not even hold for linear regression problems. For example, let f(w) = ELED (e, where z is a sample and D a standard Gaussian distribution over It can be shown that g = 2= is an unbiased estimate of fw()). However, both the variance and second-order moment of g is in the order of O(w2) which are unbounded when w + C0. When Do 0, it is called the "strong growth condition" (Vawwani et al. 2019). which is shown to be reasonable for overparameterized neural networks that can inter- polate all data points (Vaswani et al. 2019). Under Assumption 2 the norm of the gradient increases with the norm of the true gradient. This is important for model parameters that are multiplicatively perturbed by noise, e.g., multilayer network (Faw et al. 2022). In this paper, we study the coordinate-vn wise affine noise variance assumption, which was also used in Hong & Lin (2023): Wang al. (003aa).
w?
Though the L-smoothness assumption is widely used in optimization studies, recently it has been observed that in the training of neural networks, such as LSTMs (Zhang et al., 2019). ResNets (aanNntsZZhagg.. et al. 2019) and Transformers (Crawshaw et al. 2022), ; this assumption does not hold. Instead, it is numerically verified that the following generalized smoothness assumption better models the training of neural networks (Zhang -yll for some positive Lo and Ly_ This assumption is widely studied in the literature, e.g., Jin et al. (2021); Chen et al. (2023): Li et al. (2023); Wang et al.
let al. 2019): | (x=) - V V/(y)]| < (Lo + L, [xxx))
(2022 2023b); Faw et al. (2023). Compared with L-smooth functions, for the generalized smooth functions, the Lipschitz constant scales with the true gradient norm thus may not be bounded. For the training of Transformer models, Crawshaw al. (2022) finds the following coordinate-wise (Ta, Tm)-smoot which
4

---

Published in Transactions on Machine Learning Research (02/2025)
provides more accurate characterization of the objective. It is generalized from the coordinate-wis L- smoothness (Richtárik & Takáe 2014; Khaled & Richtárik 2020 Bernstein et al. 2018 In this paper, we
focus on coordinate-wiss (Lo, L1 -smooth functions as defined below:
Assumption 3 (Coordinate-wise (Lo, L1) smoothhee)) A function f is coordinate-wise (Lo, smoothh if for any E Rd and E [d],
Lo Vd L1 [1(0.((2))) || - yll-
(1)
The training of Adam enjoys adaptive learning rates for each parameter individually due to the coordinate- wise update process. Moreover, extensive experiments in Crawshaw et al. (2022) show that the Lo and L, for each coordinate vary a lot. Therefore, is more accurate to leverage the coordinate-wise (Lo: Li)- smoothness. this paper, for the sake of simplicity and coherence with the coordinate wise affine noise variance assumption, we assume the Lo and L1 to be identical for each coordinate. Our results can be casily adapted to the case with distinct Ln and Lı for different coordinates.
2.2 Challenges and Insights
Our theoretical analyses address several major challenges: (i) dependence between stepsize and gradient, (ii) potential unbounded gradients, (iii) mismatch between gradient and first-order momentum, and (iv) additional bias terms due affine variance and coordinato-wise (Lu, L1)-smoothness. Prior rescarch circum- vented most of these challenges by introducing extra assumptions, whereas provide several new insights and show that these assumptions may not be needed.
Algorithm Adam
Initialize parameters: 31, learning rates 1,, B1, 82, Ç, Iteration T Initialize first and second moment estimates: vo R m
Initialize time step: =
while & < T do
Generate stochastic gradient:
Update first-order momentum estimate: m, + mm + (1- -1)g:
Update second-order momentum estimate: 02 +- 02 + +11 -82)., о og.
Update parameters: I++1 + It 7 Veito @ m, ++1
end while
In this paper, we have an access to an unbiased estimate of Vf(x)) such that E[g|=]
V(x)). Consider the
Adam algorithm in Algorithm [ which reduces to RMSProp if 31 = 0. For coordinate-wise (Lo, L1) -smooh
objective functions, we have the following descent incquality (Lemma in Crawshaw al. (2022))
E [(V (xx), - 2 1F f(x.) ([
first-order
Lo
L (zx)
B 111 2211 [I,,
El Dell|ae+111 [F,,,
(2)
2
2
second-order
additional term
where the last term the additional term due to the (Tgg -smmmoothh assumption.
Challenge 1: dependence between stepsize and gradient. We the RMSProp optimizer explain our technical novelty. The challenge the same for Adam. For RMSProp the optimized parameter is updated: Ø1+1 H;
nge , where the adaptive stepsize 7h -o.tę depends on the current gradient
estimate gr, which makes it hard bound the conditional expectation of the first-order term in equation 2
To address this challenge, studies Adagrad (Ward al. 2020 Défossez et al. 2020 Faw et al. 2022
5

---

Published in Transactions on Machine Learning Research (02/2025)
and studies RMSProp Zaheer et al. 2018 propose surrogate in of vs which is independent of gt, and then the first-order term is divided into two parts: the first-order.a term E order.b term E ( faze)
19: and first- VB,+5/ Fi] The main challenge lies in the first-order.b b term (surrogate error). In Zaheer et al. (2018), this term is bounded based on the assumption of bounded gradient norm, which does not hold in this paper.
[ (V (
vo.ts/
[
-00 + Je,tc
79:
Insight 1: reduce surrogale error. We choose the same surrogate ür = f as the one in Zaheer el al. (2018), which requires that the gradient norm is bounded. To remove this assumption, we change the adaptive stepsize from /e.tc to " (details seen in Remark T.. For Adagrag (Wang et al. 2023b,, due -
Vel+c
to the non-increasing stepsize, in the 1-th iteration, the error term can be written as [[o(vr-1) 1) x [F where & is some function. Thus, these terms cancel out with each other by taking the sum from = 1 to T. However, this mothod does not work for Adam due to the employment of sccond-order momentum. With our modified adaptive stepsize, we can also show the sum of error terms is bounded (details can be found in Lemma D. We notice that a different surrogate is selected in [Wang et al. (2023a), which aims to bound the surrogate error for L-smooth objectives while our surrogate is tailored to the specific requirements of our generalized smooth objectives.
Challenge 2: unbounded gradient. Previous works, e.g., De et al. (2018) Défossez et al. 2020 Zaheer
et al. 2018)) assumed that the gradient norm is bounded, based on which, they proved the convergence. However, with affine gradient noise, the gradient may be infinite, and thus those approaches do not apply.
Insight 2: recursive bounding technique. For RMSProp, with bounded surrogate error in Lemma 1 first show that E + V +.
is of the order of O(e²). If the gradient norm is upper bounded, then 6 is bounded, and the convergence result directly follows. However, under affine gradient noise, the gradient norm may not be bounded. For generalized smooth objectives, we develop novel approach to bound E + Vll
[((.))
Dt=1 | [ instead of constant (see Lemma 3 for details). Applying Hölder's ' inequality (Hardy et al. 1952) we will obtain the convergence result. The complexity result matches with the lower bound in Arjevani et al. (2023). A similar method is applied in Wang et al. (023a)) which
using E
focuses on the L-smooth objectives and bound Eh [[+ by constant.
Challenge 3: mismatch between gradient and first-order momentum. Compared with RMSProp, Adam employs the first-order momentum m,, The momentum m, is dependent on the surrogate stepsize Voite' Moreover, the momentun m, is a biased estimate of the current true gradient. Both the above chal- lenges make it hard to theoretically characterize the convergence rale of Adam. These mismatch challenges also accur in the analysis for SGDM (Liu et al. 2020) and Adam (Wang et al.) 2023ah, where potential function of f(u)) with u, n - 1.-1///11// is studied. It can be shown that u u, is close function of B: Vo+tc' which is much easier to analyze compared with m. However, both of them are limited to Voltc
1/
L L-smooth objectives.
Insight 3: bounding first-order term using E
V [[=))]]. In this paper, we choose the same potential Using the descent lemma of f(u),, we show that the
T
t=
function but different surrogate in Wang et al. first-order term is also bounded by a ee-level constant plus a function of E
2023a
1 T ET [++( Compared to RMSProp, this additional function is introduced due to the bias of m.- Then via Hölder's inequality, we show Adam converges as fast as RMSProp.
Challenge 4: additional error terms due to affine variance and (Lo. -mmoohhhhssssss. Compared with L-smooth objectives, in the analysis for RMSProp with (Lo, L.)-moooth objectives, there is an addi- tional second-order error term: Σd_ 1.10,( xxll|= ær, which is hard to bound since
(x:()))) may be unbounded. Moreover, for RMSProp, since Bl a.. E vig.al and gr, /o.
is independent of o.,s given Fe, the affine noise variance assumption can be leveraged to bound the second-
6

---

Published in Transactions on Machine Learning Research (02/2025)
order error term directly. Nevertheless, for Adam due to the dependence between m4, and Ut,s, the above approach cannot. be applied directly.
Insight 4: bounding additional term by function of forst-order term. For RMSProp, we can show that (0.f(=))) According to the affinc noise assumption, 2r,
|| - æz1l 1 nva and (0)(()))]24111=0:
11-B2
we have that ([gh,,1F) is upper bounded by a linear function of (ax)( thus can bound the additional error term. However, we cannot directly apply this method to Adam since [[m] is hard to bound.
Instead, provide a new upper bound Σi= mi, Lemma
using the gradient norm (details can be found in
you
3 Convergence Analysis of RMSProp
To provide a fundamental understanding of Adam, in this section, we focus on RMSProp which consists of the design of adaptive learning rates for each individual parameter in Adam.
For RMSProp, the main challenges come from the dependence between stepsize and gradient, potential unbounded gradients due to the affine noise variance, and additional error terms due to (Lo. L.)ssoootheess
The analysis can be extended to general Adam, which requires additional efforts to handle the first-order momentum. Define c = VS + d + |[ll] We then present our results of RMSProp in the following theorem.
Theorem (Informal). Let Assumptions 1 and 3 hold. Let - B2 = O(e2) n O(62), and = O(--))
For such that s5dD vDi V/'
have that.
T
2dv35DoD + vo)c.
[[
(3)
T 1=1
44
To the best of our knowledge, this paper provides the first convergence analysis of RMSProp for (Lo, L1)- smooth functions with affine noise variances. Existing studies mostly assume bounded gradient norm or variance (De et al. 2018: Zaheer et al.) 2018) or only show the algorithm converges asymptotically (Shi et al. 2020). More importantly, our result matches the lower bound in Arjevani et al. (2023), and thus is optimal.
The formal version of the theorem and the detailed proof can be found in Appendix Below, we provide proof sketch to highlight our major technical novelties.
Proof sketch. Our proof be divided into three stages:
Stage 1: develop upper bound of
[[,))]] [|+c] Stage II: develop an upper bound on E[ + <]: and Stage III: show E [[[v)((
E
B2llo
converges using results from Stages II and Hölder's inequality.
Stage I: upper bound of E
As discussed in Section 1 for coordinato-wisc (Lu, L1) -mmoohh
functions, following the descent inequality (Lemma in Crawshaw et al. 2022 we can get 2 We first
obtain [V /3.llv-- I Ed r(ar((m)))²
V Therefore, the following we will bound Dd ((m,((m)))
/
Towards this goal, in Step 1.1, will show the LHS of equation 2 is lower bounded by a function of
Ed
and in Step 1.2 we will show the RHS of equation is upper bounded by a function of
Σd
Di=
/324:-1.45" Combining the two steps, will obtain upper bound on Σd Di=1 /B2mm11.t<
((a,((=)))²
Step 1.1: lower bound on the firs--orer term in equation g Since the adaptive stepsize and the gradient
estimate are dependent, design a surrogate 320,-1 decompose the first-order term in equation 2

---

Published in Transactions on Machine Learning Research (02/2025)
into two parts:
E
(V)(())) 2t
2t+1)
firstrorder
E
V (mx),
n9t
Fe +
(((x)
79:
1/9t
Ft
(4)
+
Vu,
Vo +
+
first-order.a
first-order.b
For the first-oreer.a a term in equation
we can show that
(V/(a))
n(0,f(x;))
E
FF
0z +
12
We then bound the first-order.b term in equation
Remark 1 (Importance of modified adaptive stepsize n). For the original RMSProp, Zaheer et al. (2018) chose the same surrogale 8t a function of Eim B2 1,+
32 as in this paper. Then the first-order.b b term was lower bounded by oi.
(1-92)0². F. Then they developed on upper bound (Vera /2uit
Fr
(1- B2)0"
on the second term WBB.it 1B assumption on the upper bound of Igu.el
Fe
S which is quite loose, thus they introduced on additional
Zaheer al. 2018).
In contrast, using adoptive stepsize
can show that the first-order.b b term can be lower bounded
by a function of Ed
E
F
x E
- Vao <) Fi which can be further bounded by
(1-92)8².
El E 9.. [F.
E
F
Applying the affine noise variance assumption in Assump-
vo,,
Lion we oblain a lower bound on the first-order.b b term the sollowing lemma.
Lemma 1 (Informal). Under Assumptions
and 3
we have that
V (axe) Vo,
19.
199
Fr
/ /B201-1+ +
((0,((x)))2
112
(0.f(x)))
+0
11200-1. +
VI
B2 v 1320-111 +
1=1
((0.f(z))))
Fi 1))
+ 0
EE
n7
Fi
+0
VBUUL-15+C +
0e, +
Vur. +
small error.
(5)
The formal version and detailed proof of Lemma can be found in the Appendix A which is based modified update process v. Hölder's incquality and Assumption 3
(0,((===)))²
(0.f(a.))²
In the RHS of equation consider the term E
Fr
Taking sum from = to T, the
Vitm 1stc 1.+C VoL.th
((:-(=))))) and (0.((=))))) shall be close each other as Ba - Similarly,
terms / (atm-1at
V
/ V
can also be bounded.
Step 1.2: upper bound on second-order and additional terms in equation 2 We first focus on the second-order
term. Based on the update process of v, and Assumption 2 we get that
d
Lo
Lon Do + (((0((zz))
E [ - x 211la24111 - Fe. <
Σ
(6)
2vd
2/C
Vi20-11;+6

---

Published in Transactions on Machine Learning Research (02/2025)
We then focus on the additional term in equation 2 and we provide a new upper bound using Σi=1 with some small errors: for any 022 > 0, we have that
(0.112)))
1 11100(((1)))
B1|121+1 - 2411 Tail
2
S 2/1
v2vd
LIVDi+
02 a2vI- 3
1
(0.f(x)))
17 12Vda223DD
- B2
V +
2/B200-1,1
Plugging Lemma
6
and
in 2 get the following lemma.
Lemma 2. Let Assumptions
and
hold.
With the same parameters in Theorem we have that
[
(8)
T
The details of the proof can be found in the Appendix The major idea in the proof of Lemma bound the first-orderb, the second-order term and the additional term using Σd
2 to
((m)))))
Sam, 1,
Stage II: upper bound of El Ballall--11=--
With the bounded gradient norm assumption, + E [=))\( OEe²) follows directly from Lemma However, under the affine gradient noise
assumption in this paper, the gradient norm may not be bounded. Here, we establish key observation that + +Σ [ 1-- can be bounded using Ii= (x))) By Hölder's inequality, we have
Σ ( s
Σ
T
E
32
Ur 11 +
+
x
1 T
| [V 32 W32llu--a11 +
1) 1+))
(9)
It is worth noting that in the RHS of 9 the second term is bound in Lemma If the first term is upper bounded using E B[IlV[( we then prove upper bound on T -1=1 B[Il [xx)ll and show the algorithm converges to stationary point. In the following lemma, we show novel bound on
T D
B2ll +c].
Lemma 3. Let Assumption hold. Then, we have
T E
2vdD, ΣT [f
B2 Ur +| c V(1- (1-)))
(10)
T
E=1
The detailed proof can be found in the Appendix C where we recursively apply Jensen's inequality (Jensen 1906). The proof only depends the affine noise variance and the update process uy. Thus, it works for both RMSProp and Adam with (Lo, L-)-mmothh objectives.
Stage III: upper bound of E [ (xx (a]. Now we show that the algorithm converges to a stationary point.
Define + ΣT [(xx)] By 9 Lemma and Lemma have that
2 c+
2 < 2
VI 32 e
(11)
Thus if < SodD.
we have
VD. Ve
2d 2dd/35DDa1
+ vc)
e
V
which indicates the algorithm converges to stationary point.

---

Combining the two steps, we will obtain an Published in Transactions on Machine Learning Research (02/2025)
4 Convergence Analysis of Adam
In this section, we extend our convergence analysis of RMSProp to Adam. Such result is attractive since empirical results on complicated tasks show Adam may perform better, e.g,, the mean reward is improved by 88% via RMSProp and 110% via Adam for Atari games (Agarwal et al. 2020
We present the convergence result for Adam as follows.
Theorem 2 (Informal). Let Assumptions] 1 2 aadd 3 hold. Let 1 -3) V32 < O(
and T = =({==)) For small such that e ViaoCaDi we have that
v2C²
4vdD1
Σ BIIVS()))
2 /2c VCg
E,
(12)
where Cg is a positive constant defined in Appendiz
To the best of our knowledge, Theorem 2 is the first convergence result. of Adam to a stationary point under some of the most relaxed assumptions of (Lo, -smooothtesssss and affine gradient noise. In Li et al. (2023); Wang al. (2023a), the authors show that the Adam converges to a stationary point with affine noise variance. However, their methods only work for L-smooth objectives, while in this paper we focus the (Lo, L-)-smooth functions. Morcover, show that for Adam, the overall computational complexity matches with the lower bound in Arjevani et al. (2023), while there is additional logarithmic term in Li et al. (2023). The normalized momentum algorithm (Jin et al. 2021] can also be viewed as special case of the Adam family, which applies the momentum on the first-order gradient. However, in their algorithm, a mini-batch of samples is required in each training iteration, while we do not require such a mini-batch. Thus, in the distributed setting with heterogeneous data, where the data distributions under each computat ional node are different, Algorithm can be used directly. However, the normalized momentum in Jin et al.) (2021) may require gradient information from many computational nodes, making the problem degrade to the centralized setting.
The formal version of the theorem and detailed proof can be found in Appendix H Below, we provide a proof sketch to underscore our key technical novelties.
Proof Sketch. Similar to the proof of RMSProp, we divided our proof into three stages. The key difference lies in Stage I, which is because of the dependence between m. and dr.
Stage I: upper bound of E
For the Adam optimizer, the first-order.a term Ft is challenging to bound due to the dependence between m. and o, Following the
E.
(a))) Vort<
recent analyses of SGDM
(Liu et al. 2020) and Adam Wang et al. 2023a we study a potential function
m
f(ux) with us
The benefit of analyzing u, is that we have E(Vf(x;;) u. u4+1) ( [Fa]
V
(1-9)) E (V)(z)) VP
Fo where the numerator and denominator in the last term are independent. Ve.tc
In Step 1.1, we will show that the LHS of the descent lemma for f(u:) (shown in equation 79 is lower v(a.((=))) and in Step 1.2 will show the RHS of the descent lemma bounded by function of Σd_ Viqmt-1-te'
of f(u)) is upper bounded by function of Ed n0, 7320e-1.45
upper bound on dd ((,,) VBzer-1,ts
Slep 1.1: lower bound of the first-order term (VVVS())) un 104--41333 1) We first divide the first-order term into two parts:
E((VS()) u (4+1)(FF) -B([))))))B((((()))))))))))))))) u4 u4 ((V((u)) - V)()), ut u41) [F]]-
10

---

Published in Transactions on Machine Learning Research (02/2025)
The first part mimics the first-order term in the proof of RMSProp and the second one is due to mismatch between ue and Zt. By bounding these two parts separately, we have lemma similar to Lemma D but with
m and
m
two additional terms: E
Fe
due to the employment of the first-order momentum
(see details in Lemma 91. For the additional terms, Wang et al. (2023a) showed that Σt= mis can be It is worth noting that due to the (Lu, -s)-smohhssssss our objective is harder to bound and only Lemma is not enough. Here, we bound the Σi mis term by Von,
ea,
bounded by a function of er, (shown in Lemma 7
function of 10.1 /02,i-V0.. 1-02
-E=IVOL-L, (the details can be found in Lemma
Step 1.2: upper bound on the second-order and additional terms. Based on the update process of us and æt, we bound the second-order and additional terms similarly to those in equation G and equation 7 but with gt replaced by m. (see details in equation 80 and equation 81h. Unlike in the proof of RMSProp, where
E
Fi can be bounded by VC
+
Dj (0: Ver,tt
Assumption does not hold for m, and this the
reason why two terms m
m
F
and
E
F
are kept the upper bound of the second-order
and additional terms. Then based on the descent lemma of f(u)), we can show E Σ
f(m)(()))) vB2e, L:tc can
be upper bounded by function of Σ m and Et= mi, which further can be bounded by function vmnt
m.s
of [[x)( We then get the following lemma
Lemma 4. Let Assumplions
7 and hold.
With the same parameters as in Theorem we have that
V
(+
E
S 2 T /(+))(
B2 0 +
The details of the proof can be found in the Appendix
Stage II is the same as the proof of RMSProp and thus is omitted here.
Stage III: upper bound of E [ (=x))). As mentioned before, Lemma 3 and equation g hold for Adam.
It is worth noting that in the RHS of (9) the first term is bounded in Lemma 4 which is more complicated
than Lemma 2 and has additional term. Let e = + ET f(l) By 9 Lemma and Lemma 3 we have that
2/dD, eE2 + cee + e² 2
e² 5 +
(13)
Voe
Thus, e ~ O(c), which shows the algorithm converges to a stationary point.
5 Comparison with Existing Works
We obscrve that there are two recent works (Li ct al. 2023 Wang et al. 2024 on Adam with (Lu, L1) smmohhh objectives. In this section, we provide detailed comparisons with them.
Li al. (2023) studies the original Adam where the adaptive learning rate is Jo and in this paper we study the modified one where the adaptive learning rate is - Fig. and Fig. demonstrates that this
modification has little influence to the model performance. Moreover, though computational complexities of the method in Li et al. (2023) and our method are dependent on (c.g. O(c-2) for our paper and O(c for Li el al. (2023)), in practice, the selection of Ç makes minor differences. The analysis of el al. (2023) is fundamentally different from this paper, which relies on a stopping time. Thus the authors in Li et al.
(2023) only show Adam converges with high probability. Their proof relics on the fact that there exists a large constant G such that (x))l S G for any before their stopping time, which requires stronger assumption gradient noise. Thus the generalized smooth problem is converted to standard T-smooth
11

---

Published in Transactions on Machine Learning Research (02/2025)
problem with large smoothness constant, leading to very small step sizes which make the convergence slow in practice. In this paper, we do not need this stopping time and we show that the expectation of gradient norm converges, which is stronger than the convergence with high probability.
Test Original and Modified Adam
90
A- le-0
(- 1e40
A- le-1
80
(- 1e-2
le-3
(= 1e
Test Emor (%)
1e.8
1e-12
50
1e
(= 1e-16
40
30
100
125
150
Epoch
Figure Test Error for Original Adam and Modified Adam. The stepsize the original Adam set Vee+X and our stepsize is set to Ve,+c" The parameters are the same CNN task in Fig. of Li et al.
2023 where 0.001, 3 0.9, 32 0.999 and we build a six layers CNN for CIFAR 10.
Validation Accuracy
0.5
0.4
A-1
1=le-2
0.3
1-1e-3
[=1
(-1e-2
0.2
(-10-
Epoch
Figure 2: Test accuracy for Original Adam and Modified Adam. The stepsize in the original Adam is set to VoetA and our stepsize is set to v We follow the setting in Yoshioka (2024) to build vision- transformers for CIFAR 10. The stepsize is set to 17 0.001, 31 0.9, B2 = 0.999.
Both this paper and Wang et. al. (2023a) extend the work of Wang el al. (2023b), which focused on the Adagrad algorithm. Our RMSProp analysis was developed concurrently with Wang et al. (2023a), but there are significant differences between their proofs and ours. Specifically, we consider the generalizod smoothness objectives while Wang al. (2023a) only considers the L-smooth objectives. Thus we choose different surrogate, modify the Adam and bound the first-order term and its denominator by different
12

---

Published in Transactions on Machine Learning Research (02/2025)
functions. When we extend our findings from RMSProp to Adam, study a potential function f(u)) with 21-92111 which was introduced by Liu al. (2020) and has been extensively employed in the analysis of momentum-basee based algorithms. The only thing inspired by Wang et al. 2023a in this paper to set this 3 0 Wang et al. (2024) extends the work of WWan et al. (2023a and is a concurrent work of this paper, which tocuses on the scalar version of Adam with (Zo. L1 -mooohh objectives. This paper focuses on the per-coordinate version of Adam and our proof is different from Wang et al. 2023a 2024
u, 1-3
V
6 Conclusion
In this paper, we provide tight convergence analyses for RMSProp and Adam for non-convex objectives under some of the most relaxed assumptions of generalized smoothness and affine gradient noise, The complexity to achieve an e-stationary point for both algorithms is shown to be O(c=*), which matches with the lower bound for first-order algorithms established in Arjevani al. (2023). In the future, we will explore the convergence of the original Adam with the challenging (Lo, L1 smoothness condition and affine gradient noise variance.
7 Acknowledgment
The work of Q. Zhang and S. Zou was partially supported by the National Science Foundation under Grants ECCS-2438392 and ECCS-250166 Y. Zhou's work supported by the National Science Foundation under grants DMS-2134223, ECCS-2237830.
References
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offiine rein- forcement learning. In International Conference Machine Learning, pp. 104 114. PMLR, 2020.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mothematical Programming, 199(1-2):165 224, 2023.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzaeneshelli, and Animashrre Anandkumar. signsgd: Com- pressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223 311, 2018.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. aiiiv preprint Xiv:11880 11096, 2018.
Tom Brown, Benjamin Mann, Nick Ryder, Mclanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877-1901, 2020.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, (33-4)2331335 2015.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. arXiv preprint arXiv:1808.02%, 2018.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalizee-smoothh nonconvex optimization is efficient smooth nonconvex optimization. arXiv preprint arXiv:2303.0285, 2023.
Michael Crawshaw, Mingrui Liu, Franccsco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35: 2022.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International Conference Machine Learning, pp. 2260-2268 PMLR, 2020.
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 arXi::8807006766, 2018.
Alexandre Défossez, Léon Botton, Francis Bach, and Nicolas Usunier. simple convergence proof of Adam and Adagrad. arei preprint arXiv:2003. 02395, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa. Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words:
Transformers for image recognition at scale. arXiv preprint arXie:2010. 11929, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic pptimization. Journal of Machine Learning Research, 12(7), 2011.
Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pp. 313 355. PMTR, 2022.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive SGD, arXiv preprint orXic:2302.06570) 2023.
Dylan J Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference Learning Theory, pp. 1319 1345. PMLR, 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. STAM Journal on Oplimization, 23(4):2341-2388) 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for
nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267-30) 305, 2016.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the Adam family and beyond. arXiv preprint 1xXx:2104.14840, 2021.
Godfrey Harold Hardy, John Edensor Littlewood, and George Pólya. Inequalities. Cambridge university press, 1952.
G Hinton, N Srivastava, and K Swersky. Lecture 6d-a separate, adaptive learning rate for each connection. Slides of Lecture Neural Networks for Machine Learning, 1:1-31, 2012.
Yusu Hong and Junhong Lin. High probability convergence of Adam under unbounded gradients and affine variance noise, arXiv preprint arXiv:2311.02000 2023.
J. L. W. V. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acto Mathematica, 30:175 - 193, 1906. doi: 21100//FF0248871.. URL
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34:2771 2782, 2021.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv:2022.0 03329, 2020.
arXiv preprint
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXio preprint ar1iv:1412. 6980, 2014.
Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence of Adam under relaxed assumptions. arXiv preprint ar Xiv:23004 13972, 2023.
14

---

Published in Transactions on Machine Learning Research (02/2025)
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Newral Information Processing Systems, 33:18261-182711 2020.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing lstm language models. arXiv preprint arXin:1 708.02182. 2017.
Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernocký, and Sanjeev Khudanpur. Recurrent neural network based language model. In Interspeech, volume 2, pp. 1045-1048. Makuhari, 2010.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Amirhossein Reisizadch, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-rcduced clipping for non- convex optimization. arXiv preprint arXiv:2303. 00883, 2023.
Peter Richtárik and Martin Takáč. Iteration complexity of randomized block-coordinate descent methods for minimizing composite function. Mathematical Programming, 144(1-2):1-38, 2014.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. RMSProp converges with proper hyper- prper-parameter. In International Conference on Learning Representations, 2020.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In International Conference on Artificial Intelligence and Alatistics, pp. 1195 1204. PMLR, 2019.
Bohan Wang, Yushum Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie-Yan Liu, and Wei Chen. Provable adaptivity in Adam. arXiv preprint Xrv: 09900, 2022.
Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and the lower bound of Adam's itcration complexity. arXiv preprint arXiw:2310. 17998, 2023a.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of Adagrad for non-convex objec- tives: Simple proofs and relaxed assumptions. In Conference on Learning Theory, pp. 161-190. PMLR, 2023b.
Bohan Wang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, and Wei Chen. On the conver- gence of adam under non- non-unifome uniform smoothness: Separability from sgdm and beyond. arXiv preprint arXiv:2403.1114 2024.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex land- scapes. The Journal of Machine Learning Reseurch, 21 (1):90047 9979007777776,- 2020.
Kentaro Yoshioka. vision-trannforrmes--ciaa11:: Training vision transformers (vit) and related models on www.ooontttrrssooooooooooom cifar10 2024.
cifar-10. https://github. http://aaa.aaaaaaaaaaaaaaaaaaaaa
Manzil Zaheor, Sashank Roddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optinization. Advances in Neural Information Processing Systems, 31, 2018.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non- convex optimization. Advances in Neural Information Processing Systems, 33:15511 15521, 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A thcoretical justification for adaptivity. arXiv preprint arXiv:1905. 11881, 2019.
Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quar Luo. Adam can converge without any modification on update rules. Advances in Neural Information Processing Systems, 35:28386 28399, 2022.
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/CVF Conference on computer vision and pattern recognition, pp. 11127-11135, 2019.
15

---

Published in Transactions on Machine Learning Research (02/2025)
A Formal Version of Lemma 1 and Its Proof
Lemma 5. Under Assumetiins
and 3 for any coo, 01
>
0,00 21 and >> 0, we have that
E
v f(()),
19t
n9t
Fr
Vu,- -
V B2
n(0,f(a;)))
naoDo E
Ft
20k0
1201-1, +
B2 +
Vo, +
i=1
110 D1
(0,f(x,-1))
(arf(a)))? Fr
E
2
12 +
Vor, +
d
(0:((x=))² a1Di
aidD,
2V dv (0,f(())))
+
(14)
2
8201-1 +
1 B2
v1 - 32
i=1
Proof. Since 12 + (1 - $2)g. @ It, for any i E [d], we have that
VoL.t +5 /2
V1,1 - 3200-111
Vo, 01, (V 1/320-111 ((v 10,00itt+ + 12
(1 32)gg,,
(15)
Ver, + 1200 + C( //v,, + + v 12
Thus, the first-order.b term can be bounded as
E
V
[(xr),
-1 + V3201-1 +
Vo: +5
d
E
Fr
VoL.t +5
/ B22 + 5
1=1
d
(1-32)98
E
F,
Vusi + ( B2 + +((1 V1.s + B201-111 +
m10,f(xx;)
VI- VI-32g²
E
F
(16)
v 1,20--15
+
( 11,5 + + / 1.200111 +
where the second equality is duc to equation 15 and the last incquality is because
I9..1l
For
V1-92
any a, TR, we have ab s +2? Thus for any ag > 0, the RHS of equation 16 can be further bounded as
m10:1(m:)1 JE
vI 1-
F
1
(Vor, D1,i +
/B20--1,+ +
((),((x))2
VI
B297.
#1)² 2
7000
E
(17)
200 / 120
2 2/320.1,1+6
VoL. + C / BB20e-1. +
For the last term of equation 17 due Hölder's inequality, we have that
vi
E
F.
2 B2
2/B20
Ve.5
+
1,200111 +
16

---

Published in Transactions on Machine Learning Research (02/2025)
82)n
gi, (Vor, + /B20r-11 5)2
FF....F.....
Fz
2/ B2ur 1,
(1 - 1-12)
$2 (Do+ (((0ff(2))))))
"
Fr
D1,i + 355321111 ((v M4,5 + 5 1200-11
" (D, + (z))) -
2/,s + 6- 1,+
Fr
U1, + 1 + C(V Vo,s +5+ v 12201-1.+
" (Do + (000)((2))))) 2
1
1
Fe $
(18)
1/
Ver +
where the sccond incquality is due Assumption 2 and the fact that Thus for any 2 1, combining equation 16
U1, + {+ 12 V
equation 17
and equation
18 we have that
(((i)),
-1 VVL + (x+))
+
0 Fe
- +
d
11000
(Do + Di (20)(
1
F,
(19)
200y 120 +
2
Ver, + VB200-10+6
For t > 1, equation
18 can be rewritten as
(1
B2)m
g
Blg
Fr
2/ 32
+
Vii + <
v 13 + 2)2
Do
+ 1D E
(0,((2)--)))
(2x1()
E
Fi
Ft
2
1B2U +
Voli +0
13201-1, +5
Ve,, +
(0.f(z))) - (0:f(x)-1)) D
(20)
2
1201-1,1 +.
For the last term in 20 by the fact that f is (Lo, smoohh and for any an 0, we have that
D1 (a.((x)))² - (0:
1200-115
D/ 2z (z()) - 0=ff(x=11)
v /B20r-1. +
10.f(z;)((Lo + 110:f((2))111
Voi-tts 3 9i-1
SnDr
v 1.20-185 +
1
Lon
2 9r-1
+ L, +110,((2;)11
2 g:-
/ /B201-1.
VoL-t
Vo--+ +
(0.((z)))3
d
(9-1,
2 (n
+ D1 1in?
Σ
+
2 +1
D1
i=1 -
VI-12 B2
nD
(0.((x)))²
LidD
2v dnLi (ax)()))) +
(21)
2//B201111+ +
D1
B2
vI B2
where the first inequality is due to the fact that for any a, b, we have d² - 62 < 2/al|a - b). the second
inequality is by the (To, smoothhesss and the third one is because that ab < 2 for any a, b and
a" 2'
17

---

Published in Transactions on Machine Learning Research (02/2025)
$
Based on (16), (17),
20 and (21
for t >> 1 can get that
V1-32
E
V (are)
19h
vigt
Ft
vv: +
32
+
d
1(0,f((0)))
d
noa Do
E
Fc
200 / 12
2
Vus, +
1a0 D1
(0
(xx)(
2
1B221-1, +5
Vn, +
1=1
11
(0.f(xx))2 a1Di
ajdD2L3n
2V (0.ff((0.f(x)))
(22)
2/ /2
82
v1 - 82
Since we set Zg 1 the RHS of equation 22 an upper bound on the RHS of equation
As a result,
equation 22 also holds for 1. We then complete the proof.
B Proof of Lemma 2
For (Lo. -smoohh objective functions, we have the following descent inequality (Lemma in Crawshaw
et al. (0222) ):
E
vf(z)).
gi
Fi
Vo, +
firstorder.aa
Lo El [ x111
<f(x:) - B[f(x++)] +
Fe,i
Fi]
2vd
second-orde:
L L(00,((x;)
Elll x111 x 0
FF
additional term
E
vf((x))
FFr
(23)
Vv + Vo
first-order.h
For the first-order.a a item, given Fe, we have gi independent of ū; and æ,. It then follows that
E (Vila))
Vo.+C + g: | Σ n(.S(())))
"
1,201-1, +
Based on Lemma 1 we provide lower bound on the first-order.b d term. Plugging Lemma equation we have the following inequality for any on, an and 1>
(0,
B201-1,1 +
Lo
<f(x:) (E (1)++))) +
B [
2z 1.1111141.5 2t,
2
second-order
18

---

Published in Transactions on Machine Learning Research (02/2025)
L1 0. (xx)
E1 2c+1 - xz 2011 - FFd
2
additional term
(x)))
naoDo
+
Fr
2000 / B22 +
2
VBUrr-Ii+
VoL. +
1=1
100 D1
(0:((
(0:f(z)))
E
Fi
Vors +
im
+
naoDi
(
(0.f(z:))2
agD1 +
an L3n 2v (0.f(((2)
(24)
2 2/B200-1,++
1- -B
V1- 32
Now we focus on the second-order term, which can be bounded as follows:
Lo
E3 ||
xe 1111/ - FFF
2vd
d
Top
| - Dell
Vd
E
(1+111 - x2.;)² Fe
2vd
2vd
2
Lo E
2 Li
Ft
2
11ii + (
Lo
Pi.
Ft
2
B2 + 5
Lon Do + D1 (8, ((x1))
2
1201-1,1 +
Ton? Do + Dj (1.0
(25)
2/C VBUU--1++
=1
where the fourth incquality is due to Assumption 2 term can be bounded as follows
Based Assumption 2 for any 02 0, the addition
L f
Ell
xx11|x1111 - F[F
2
VdL (xx)(()))
E
122
1820 +
Fr
2/1 B2
172 VdLd (.f((())(()))
V
E [T]]
2/1 - B2 / 1200-
1 /.T.naa.// ((),((())))))))))))) ) (VDo (TT(),
2/ - /2
2 (0. + 2(1 - 32 / 32 1,0 +
v22 LiDo
(26)
2/1 322 1, +
2 3/220-1144
Vān
where the first inequality is due to the fact that ||a2+1 - xz || v -
the second inequality is because that
E [g..
S
[ Fr]. and the third inequality is due to Assumption and the fact that for any a, 2 0,
we have Va + b b Va + Vo. Plug 25 and 226 into (24). and it follows that
d (0,f(z)))
12211-15 +
19

---

Published in Transactions on Machine Learning Research (02/2025)
d
Lon Do + (((0f((E))
<f(x)) ([((((++)))+))))))))))))))1(1)))
2V5
(B201-1,1 +
==1
dL V D2 (O,f((z))))
(
172 /2v/auy LiDO
2/1 32 1200-1. +
2(1 - B2) 120 +5
2 12 +
((0r5(
maoDo
E
Ft
2000
12 1221-111+
2
v V2
Vor, +
110D1
(8.f(xc-1)) 1)2
(xi))
+
E
Ft
2
V2200-11+5 +5
Vo, +
d
(O.f(zi))
ajdD Lin2
2 (0.
+
(27)
1200
+
Di
1- B2
VI-1a 12
1=1
which can be written as
d
17
700
Lon D1
L VaVdD
12vd
n /ddann
(2x)())))
11
200
2011
2V
2V1
B2
2(1
32)002
VI-B2
1220 +
i=1
+ dLom> Do
agaid of
D2
1
rJ
rrand Lo
<f(x))
Bls [[5(x (1
26
2(1
32)
VC
2/5
Do
1
1
E
Fr
2
120-11146
Vul, +
11 E
(0,f(x1-1))2
(z.f(x)))2
Ft
(28)
2
V200-111 +
Vul, +
It is worth noting that the sum of the last two terms in equation 28 from t t= to T can be further bounded. Specifically, for any E [d], taking the expectation with respect to F,, and the sum from L = 1 to T, we have that
T
1
E
18201-14
+
Vuri+
1
1
E
E
-E
B200,5 +
V +
Vuri +
VUT,
UT,
+
+
Σ
I
1
VB2
VC
V Bo0l. +
/B20e,i +
V32
+
I3
VC
V. +
1=1
/B2
+
(29)
VC
VC
Similarly, for the last term in equation
28
the sum from L t= to T can be bounded as follows
(0.((x,)1))
(x,()
E
1. +
(zoo)
(0)(()1))2
T
(0.(
(0.((x)))2
E
Σ E
B200, +
VoL +
12 +
V +
(0.(())))2
T-1
(z)
(0.((x)))2
(0.f(x)))2
E
+
Σ
E
- .E
B2200 +C
+
VoL, +
Vor.+ +
20

---

Published in Transactions on Machine Learning Research (02/2025)
(0.f(z1))2
T-1
( [
1
V
(0.s(2;))2
S
E
VS
Brvr, +
v
//2 +
[=1
(0.f(x1))2
T-1
(0,f(x)))
(1 3B2)TE
VC
VB202 +
(of((a1))
1- VB2 E
(ar((x))))
VS
VB2
Ve,s +
(.f(x)))2
(0.f(z)))²
(1 32)
(30)
VS
/20 +
t=1
since To 21, 90 and the last incquality due to the fact that
S 1 VB2. By taking expectations
and sums of 28 from t = to T, based on 29 and
30 we have that
Σ>
T
7)
110
Lon D1
LDVVD v2
17
vdddagl
(0:f(2::))
200
201
2V5
2/1-12
2(1 B2)22
v1-
13U +
[=1 i=1
+ 1000 Dj D
goodDo
dLou Do
Agand d² LBn DP
<f(+1) - B(f(xT+1)
+
2/5
2/5
2c
2(1 -12)
VC
+ 17" a.dd..55 1oppd.55'7 Do T gaodDo(1 VB2).
7o0 D1 - (22
d
T
10::((x))11
+
E
(31)
2VC
2/5
1200-11i
i=1
t=1
Define A = f(x1)) - f(xx))
(((x))+++ + DondDg
where f(x")
inf f(x). If we set = 1, =
2/5
2/4
vce
and 02 = 1, obviously we can find some
83 = min
( and
7D.
35dD,
VC
3
1- 82
ÇE²
e 1-
33L2d D = 0(2)
Vce²
7 S min
DL
max (14,
7L, VdD)
7vd
35LndDo
7D, Lod55
such that
E
(O.S(x)))
+ A
T
11
+T
11
T 11
2
T
7
(32)
14
70
70
70
70
Set >> 702 ne²
((E-)))) and we have that
T
f(x())1
d
T
(0.f(x:))
Σ
E
E
5.
(33)
T
121
1B201-1,5 +6
t=1
This completes the proof.
C Proof of Lemma 3
For any a, 2 0, we have that Va Va+bs vo + Vb. It then follows that
d
E 2/2l + 5) > E B2U1-15 + VC.
(34)
For the first term E[ 12 and t > we have that
El B1B0 = E E
32 12 F.
Fe
E
V
R3,-2s + 82 -8))0n
(35)
21

---

Published in Transactions on Machine Learning Research (02/2025)
Given Fi-1, V2-2 is deterministic. By Jensen's 's incquality, we have that
E
E V 1Bur-2, + B2(1 + - 12) 941- Fi-1
<B
18 [8g00-2, B2 -1
<B
130022 + =2(11 - -D) D1
<B
8301-2, + B2(1 Du)
+ -1 (m)-..))
(36)
where the second inequality is according to Assumption 2
By recursively applying (36) we have that
EI
v 13 32(1- 32))
<
B80-3s + +B2 (B)+ (1) D2)
+B + 83(1 -2)D)1000(00=22]
(37)
Specifically, we can get that
E
32 1,1
<E
Rv0- 32(1 - Do
+ V 32 - (0)
<B
+ + (32+ - -1)
+ E VVB3L 3.)D
+ E
V3a(1 - 3.000,/0000
<
(B2 + 182 + 13 +... + +1 - Do + vo.i
E
V -3(1--300 (88(11 3.)
==1
1-1
SvDo | || +
> E
[V [[BBBc (1 -0)01(00
(38)
j=1
As a result, we have that
Σ E B2 B22 1=1
T
V + dv Do + |ool||
E VB[(1- ( =0)0))00
T
d T-1
=c+
Σ
sc+)
Σ
10 (ax:))
V(1 - D1
Σ
T
v 32
T
1=1
2/D7
Ei= E((a)((0:1]]
Sct
(1 (2)
i=1
<ct
/dDi
21=
[(
(39)
V(1 - -32)
T
22

---

Published in Transactions on Machine Learning Research (02/2025)
where the last incqulity is due to El [[.f(a)]| S va]]f())ll- We then complete the proof.
D Formal Version of Theorem 1 and Its Proof
Recall that cV dv Do + 1ool A f(x1) - f(x*) + gaodDo
+
200 D2 ([
Define A1
2/5
2/5
VC and A3 TD: Lodv5
V/c
max (144, vdd. 7.D vaD.)' A2 = min
35 35r4ai.0D))
vie
Theorem 3. Let Assumplions
1 and
3 hold. Let 1 82 = =min
0(2), S
FDi 35dDo
V PLybi AA,,AAII--
min
B2,
1-82
A
A B2) O(e2), and T >
704
O0e For small such
7vd
njc
that e e
VodDo we have that VDi V/'
T
(2d/3DDoDi
+ vo)a
Ell
f(x+)ll
(40)
T
4C
Proof. According Lemma
wc have that
1
[
56
(41)
T
12110:1111
According to Lemma 3
we have that
T
E[ / B3 0//10u=111++0 +C]
1=1
Sct 2vdDi ΣT [f(x)]
(42)
v(1 (2)
T
Define
$ It
[[ By Hölder's inequality, we have that
1
T
2 < T
V (
))
(
T
E [
B
(43)
T
32 2 +
By Lemma 3 and Lemma this can be written as
2vdD1
2 5 2
c+
(44)
v1 B2
Thus we have that
T [(IV)()))Il = = 2dD 1
(2VdD(e2
2
VI - Bg //
+ 4cx2
vI B2
Since 1 f2 min
Vie 7D, 35dD,
= 0(22,, if
JodDo VD.V''
we have
2
S
/35dDa 4/s
c. It. demonstrates that
V1-
T
2dl35DDoDi
+ vc) Vc)s,
V ||| -
(45)
T
JC
which completes the proof.
23

---

Published in Transactions on Machine Learning Research (02/2025)
E Lemmas for Theorem 2
Here are some lemmas we need for the proof of Theorem
2 Lemma
G
and Lemma 7 are from Wang et al.
(023a)) We include their proof for completeness.
Lemma 6. (Lemma 6 in Wang et al.
(2233a)) For any {or
and at 32ac-1 + (1 32) and
b, B1b1-1 + (1 3, ff< 31 B2
1, have that
bt
31
(46)
Vu +
vI 32
87
32
Proof. We can show that
be
be
Σ Ei (1 -11)89c-1
2
va
+
Va
Σ 1=0 (1 (22)8522 + ag
1 - 31 V 1= 3307
32
1 1 31
<
(47)
V1 32
i= 3
VI - 32 /2 1
where the third inequality is due to the Cauchy-Schwarz Schwarz inequality.
Lemma 7. (Lemma 5 in Wang et al.
2023al) For any {aliz= 2 0 and at B2ar-1 + (1 - B2)c and
b. Bib--1 + (1 Di) if 0
8 < and ag > O, we have that
T
12
(1 (1-B1 B1)²
In
aT ag
- -TI((22)
(48)
at
(1
8n ) - (32)
3/
Proof. Due to the monotonicity of the 1 function and Lemma 5.2 in Défossez et al. (020), we have that
à
(1 32
11-0-(1-182) da = In
4 (1 - 3e)cc = In at
at
ln(32).
(49)
Cc-1
By telescoping, we have
2i=1 a.
<
In 2z
T' lo(8,) (1-82)
Moreover, for by we can show that
1-p2
b S (1 B1)
0 C4
s (1-3))
Σ
t.
4-1
c
(50)
va
at
B32
Vai
Further applying the Cauchy-Schward inequality, we get that
62 5(1 1511-,99 22)2
Σ
at
B2
aa
<(1 - 81)2
Σ
31
b-1
B1
c
VB2
v32
4
(1 31)2
B
t-ع
(51)
1 B1
132
VBa B2
This further implies that
62
(1 - 81)2
In
aT
T
Tlin(22)
(52)
0t
(1
8, (2 32)
ag
3
24

---

Published in Transactions on Machine Learning Research (02/2025)
(1 (1-B2)c} Lemma 8. For any {cr 2 0 and ae + and O, we have that
and b, + 3i)a, 80< BJ <
32 <1
T
(1
31)²
2
T + 2 2
(VT
v [an
at-1
(53)
1 82
Proof. Due to the monotonicity of the
1
function, we can show that
Va
(1 - 82)
-2 va da 2/0r - 22/0 - 111---11100 11-1((11)))) -B2)c
1
-a-a-(11Baac)
22/0 2/ B201-1 - 2 + + Vae-
(54)
Taking sum up from t= 1 to T, we obtain the following:
Σ
T
32)
S <2V0T 20 + +211 - B2) Σ
T
Va-1
(55)
Va.
t=1
t=1
We then derive the following bound:
b
S (1-
-1)
B1)
Σ
8t c2
S (1 31)
Σ
B
(56)
Va,
Va
4/2
V/
i=1
1=1
It then follows that
63
5(1 B1)2
Σ
31
t-j
C
2
V 0/t
12
Va:
Σ
)-1
B
1-
<(1 81)²
3/2
a
(1
3,)3
3
t-i
(57)
91
D2
P2
Taking the sum from / == to T, we can derive that
(1 - B
(58)
(1
81
0t
Plug equation 55 in equation 58 and we complete the proof.
F Lemma 9 and Its Proof
Define Ci = 81 C2 = V
of Fe
we have the following lemma:
Lemma 9. For any ag a1, az3, a4 > 0, B2 > 0.5, and 0 < 88 < 32, we have that
E((V((u), u, [F
1(1 31) (1-B1)
an
LI 31)
C1
C2C₂
200
2m
VI-B3b
1L1(1 - -2)²
nL1(1 (1)
d
(0.f(x:))²
x Σ
2ay
Ca,07
Ca
/ /2
25

---

Published in Transactions on Machine Learning Research (02/2025)
d
711 -
(1)
agDo
Σ
E
Ueii + Fi [r)
CiO₂
{2
1/ +
1=1
D
(O.f(xx-1))*
(0=
E
Ft
2
V,201-1,1+
Vol. +
0001
Di - -1) 037d31 (1
31) -2) B2)
2(1
32)0,
2C1C2
(11 -22
+.5 +2)2+
Ci))vdLo
m
0) - C2)
m 2
1,
Ft
C7
11-18 +
C7
Vt. C
d (1 (1) dL
m
d
aun (1 (1-1,11-000 (1) -1)dL
m
Fc
(59)
2(1- (11-32) C2
U1-1
2(1-B2) B72
V1,5 +
By #1-1
Proof.
Since
Ue
v82
U1
we then have that
7/2
11+1
31
11
21
U+++1
VB2
B.
v 30
3
11 3
Vertc
31
17
V
31
V/2
B1
Via
V //2
-17
-1
Ve,tc
+ 17
v
-
B1
81
VB
B1 m
Bi m
-11
12
12
+.1aa
12t
A1
B1
17 ④
(1-9i)e
)ar
7)
④
m
+ 17 ④
m.
1)
8
-7)()
9,m.-1
1
/ui+c
Viam ItC
i+80
1
+
(00)
31
Viaa
V/a
//2
where the last equality is due to m. 8-m--1 + (1 - -B1)g:- For (To, I -smooth objectives, from Lemma in Crawshaw et al. (2022) we can get that
Lo Ell uilluu-1. [..i
B(Vf(u)) 4 u 1F & f(u)) - E[f(u++1))F:)+
first-order
scrond-order
L (ux))
E [111 uA / (.F......
(61)
additional torm
We then focus on the first-order term. Based on equation 60 we divide our first-order term into four parts:
B((Vf(u)) 2 (44)) E[(ff(()))
un u.-i)ii + +E[Vf(u) - vf(xi), u ux11) [Fl
n n (1-81)0
E
Vf(x)),
F
first-order main
26

---

Published in Transactions on Machine Learning Research (02/2025)
-1
m,
+ 1) O V 1
m.
Ve+t
V V((r))
Fr
31
10
12 11 17
8im--1
8,m4-1
12
Vf(x)).
VB2
emrrr 2
BkV((u)) - vf(z)), u++1 uz Fi.
(62)
The first-order main term is easy to bound. Since given Ft: 9: is independent of 0z-1 and we have that
② (1-8))0
v 1
n11 31)
(0.f(x,))2
E
v f(x)),
Ft
(63)
120
V BB
1=1
B2
first-order main
We then focus the error term. Since U. = -20 (1 82)gr ② gr, we have equation 15 and it follows that
17 Ve++C 77
O v 1
(M)t)
Ft.
92
d
(1 B2 9 mm.a
7
(0.f(x)))
F
(64)
(Ver, ()( v B20 + () Ve,s + + v (200-111
1=1
According Lemma 6
we have
1-
which demonstrates that
ve.tt
VI- /
error 1
1
15
d
7
31
(x,f(xx))
VI - B2gi.
F
(65)
B1
82
1, +
Dz,5 + + B2U +
2m1
V02
32
Similar to the proof in Appendix
we can show that for any on > 0 and i E [d],
0xf((x;1
V 329
E
F
1200-111 +
V1, + + v 12
(x:)(x;))²
VI
B29?.
Fr )
E
(66)
2010 1200-18+
2 1/
( Ve,i
5
B2 2 1.
For the last term, using Hölder's incquality, we have that
VI F2gi.
09
E
Ft
2 120 +
(Ve + ( / /22 + ()
(1
32)00
gi.
F
2 1/20 +
11,i + S
3200 + {)2
(1
32)
06
(Do. E
Fr
Vv,i B/ ((Ver, 00, + S /3201-11+
27

---

Published in Transactions on Machine Learning Research (02/2025)
00 Do + (8)
1
Ft
(Bour-ia+e
Voc. +
(67)
Similar to equation 20 we then show the sum of equation 67 from -= 1 to T can be bounded. For & >> we have that
000
Do
(1(()
Ft
2
12 +
Voli + +5
on
aoDoE
1
D
(0.f(x)-1))?
(a.f(xx)))
E
Ft
+
Ft
2
V +6
Vo, +
1B20L-11
+c
Uz,i +
an
D1
(a.f(x)))²
(drf(x)-1))
JE
(68)
2
V3200-11+
Note for the last term on RHS of equation 68 due the different update of æt; there is a little difference from equation 21
For the last term and any aj 0 and i [d], we have that
a
-0,,))
Ft
2
/BUL-1.++ +
2axx(((r))] (0.(()))) (c2((02)))
(pp
Ft
2
/ +5
(0.f(=))((Lo + 1110,((20))11
2 m
D1
BB0 +
a0D1
(0.f(x,))2
2
+ aj Dj 1.21?
m
2 B0, 1/ +
D,Di
P--1t5
2 m 1) 4--1
D1
(a.f(z))) a1Di
d(1 B21)
Vd(1 -31)
D1 Lin
f + (0,f1()((=:))
(69)
2 13 +
(1-
v1 32
1
B7
B3
where the first inequality is due to the fact that for any a, we have a² - b² < 2/a||a - b/. the second inequality is by the (Lo, L1) smoohhesssss assumption and update process of Ft, and the last inequality is due to Lemma 6 As result, for oo, on > 0, if 1, it be shown that
7
1
B1
(0.f(x;))²
Dr
error 1 1
+
E
F
8
200 3201-1,5 +
2
+
/ Ue.s +
V
B2
Og D
(i: (ar(())))
(0.S(
Fr 5.))
E
(70)
2
B201-14 +5
Vu, +
and if
we have that
77
1
-
B
(0if(x)))
an E
1
1
error
8
/
/7
2200 1200 +
/320m
Ver,i +
Fg
12
82
0n D
(0,f(x+11))
(0,f(x:))2
E
Fr Vor, +(
2
12201111 +
28

---

Published in Transactions on Machine Learning Research (02/2025)
anD1
(0.f(zi)))
D1 + D1 1gn d(1 B1)² (1 (1-3)) 32)
+ 2 10,-1, +
732
Vi(11 - 31)
(1)))
(71)
v1 32 V
Since define mg = 0, and 3p 21, therefore this inequality holds for 1. Note many terms in the RHS of equation 7] can be reduced by telescoping, which will be demonstrated later. Now move to the
error term. For any 03 > 0,0 < o7 B2 and $2 > 0.5, we have that
Jim-1
Dr m
D22
Bati-itS
fa())
31
V/2
error
n181
(1-
(a(a)));
3 -
P1
(V + (V (25) O (V /201-1+ + 12 32C)
m1
10,f(z+))
(VB201-1,1 + +00--,+++((
(DVBB12V100 1211-1,1 + B25) 12 +5+ v /2 B25
1=1
(1-
1- 31
10.f(x))
31
B201-1,1 + SIVS vI - 32 / 1 o9
VB2
f2
n (1 - BivV
(x,(())))2
+ 0, (1 - (32)
(72)
3
203 203/ 120011 + 2 +
8
where the second inequality is due to Lemma 6 and 2,3 > 1. For error 3, it can be bounded as follows
(V)())) Vx(x)),, ur u(+1)
d
(0.((u:) a, 0.f(x:))lu;; we11.
LL + -10.f(2)))) x.ll/ur; u.41. Σ i=1
$
Σ (Lo + L(0.((x)) 1=1
d
V82
xt-1||
It+1.1
D1,
81
Dt,i
21-14
(73)
1
8
B1
VB2
91
V
8
where the second incquality due to Assumption 3 it is easy to get that
According to the update process of æ; and Lemma
L
11-1
1t+1.i
B1
Bt.i
Et
1,
8,
v
12
B
1=1
32
/ 12
V02
8
9,
d
12
Ln
(1|23, xc
|1++1, Zr,il) +
(1
2z-1 1|,,
Zz- 22.1,))) 1,5l)
8
8
9
1=1
9
V
V
d
V
D2
2
Vol
x0,,x12 =00,1
L
8
g
2dd
29

---

Published in Transactions on Machine Learning Research (02/2025)
81
x1-1
21
Vdlaa,, 11 ?
+
+
91
2
V A2
< Lon
2
d
2/Dr
B1
D2
vd
Vd
1
m
2/332
D vd
m
(74)
i=1
B1
11-1,
+
(1
81
2
22,i + C
VD2
V32
However, it hard to bound the remaining (z))(l) - Iz- l|/ - u441al term by directly applying
Lemma 6 which will induce a 0(00,(( term and with our affine noise variance, we can only bound
the ((.)( term. It is worth noting that this challenging additional term is due to the (Lo, Ln) VD2 -1 1.tC
smoothness, and methods in Wang et al. (2023a); Li al. (2023) do not generalize to our case. To solve this challenge, we first bound the additional terms follows:
10tf(x;))1) x1-11l/<r1 - x1-1
1/1m-1.5l
10=f(xx))
(x,))()))(;; -x
V +
n(0,f(xx,))
a47mm 2
1,2
xc - x1-1|2
204 V 11-1,i +
2 1/- +
m(O.((z)))
2 m
d(1- -
(75)
204 12 +6
21-111
( 11)
for any 04 0, where the last incquality is due to Lemma and m where the latter can be bounded by Lemma 8 Similarly, we have that
The motivation is to bound using (0. ((x.))
v /3
2 2/0011065'
1 -0-11122411, Be,1l
a.f(
n(Ors(arr))
asmmi
[0, :1-1 2
201Ven 21,1 +5
2i,
d
110,5 ((x))
d
aun
?
d(1 - -1)
(76)
204 3201-1,1 +C
2 U1.i
Ç (1 32)
8
32
Combine equation 62 equation 63 equation equation 76 and we then have that
71
equation
72
equation
73
equation
74
equation and
75
E V fu:), u++1 FF.
11 - Bi) (x,f(x;))
V22011111 +
1=1
Viz
Σ
1- B1
(0.f(xx))²
Do
1
+ 2
81
v1
of
2000 1200-1.4 +
1.201-1,1+ +
Vur, +
B2
Okg D
(0,f )
(0.f(x;))
Ft
2
13201-11 +6
Vor,t +
30

---

Published in Transactions on Machine Learning Research (02/2025)
D
(0.f(zz))
d(1 31)²
+ 2 Bo0 10 -5
an + an Diign (1- B2)
fi 352
vd(1= - -11)
+ 20111(0
VI- //
19
n311 BI)V
(xx))
03 (2)
+
81
1V1
2003 12
2/ B2
VD2
82
B1
Vd
8 Vd
B Vd
2 D2
8/2
m 2
1,2
2/
2
+ Lo7
+
2
11-16 +
1 (1-9)
Utii +
8/
8/2
88
L1
32
(0,f(xz))
0447 m 04 2
1,8
d(1 - B1)²
d(1
2011 120 +
11 + (1 31)
187 82
1
91
V
81
/ 2/2
n(0,f(2;))²
a d(1- - B,)2
+ L1
E
(77)
2
201 B20 +
2 01, + +5 32) 1
1
VB2
Since C1 = 1 - 81 and C2 =
equation
77
can be further bounded as follows
V32¹
f(i), u1+1 [Fl
n11 10--80 -1)
Ci + 17(1 - B1)
1
a
nao (1 -1-111111 31)
+
+
CiO2
200a
2011
B2-2
20 C2
1L - -c1²
204Ci + 1L1(1 - -11
d
(0.f(x))2
/B201 1,8 +C
1=1
n11 -1))
Do
1
E
Fr
C12
VB200-1.+G +
Ve. +
D
(0:f(1x-1))2
(0:5(
appon D&T.312d221
B1)3
a3dd33 31)(1 -22)
E
Ft
2
(B2ut-1,1+ +
Vus +
2(1 - 1--3)
2C1C₂
d
17 122 2 +0.5(1
Ci)lvdLo
m
d 17 20
Ci)VLo
m
F
C7
11-1, +
C7
Vt.i + C
(1-7"(1-1110) - d.)
m
(1-1)
Ci)dL 2(1 2(1-B))C74 C2C
m
E
F5
(78)
2(1- 3,)0
VU--i
Vv,5 Ve.s +
This completes the proof.
G Proof of Lemma 4
For (Lo, L, smooth objective functions, we have the following descent inequality (Lemma in Crawshaw et al. (2022))
Lo
(w:), ui Ur 11+1) S f(ue) - Elf(u++ 1)]
+
Elll uulluue-1. [F
2
first-order
second-order
31

---

Published in Transactions on Machine Learning Research (02/2025)
L1 | ((,))(()) ||
Mx+1 wel U1+1,1 -b,,il
(79)
2
additional term
The first-order term is bounded by Lemma g second-order term, based on the definition of un and update process of æt, we have that
we then only need to bound the remaining two terms. For the
Lo Bl1 U1+1
We ||
2vd
Lo
E
11+1
81
Et D(-1
+
Vd
11+1i
Lt.i
B1 Lt
1t-1,
|FF
2
2vd
B1
V 3/2
D1
B1
v 132
1
B1
V
V02
V02
v 02
8
Lo E
2vd
2v
11+1,1
-x,,i 22 +
32
22,i
21 1,
2vd
(1
(1
3
VB2
Σ
Lo
2
E
m
Ft
2vd(1 - C1) 1/2 7pm 11
(80)
2vd
C7
11.5
+
C2 11-1,
Now we focus on the additional term. According to the definition of us and update process of æt. for 0k4 > we have that
0
Li ((x)( Blllu-1 -
2
(10,f(x;:) + (Lo + 1.10. - = U2+1
ue
u.lluu441.
FeF
8
81
L1
|a.[(ar))1 To
V02
||,0,
xt-1|l Lu ((x))
v32
at 2z 1||
2
8,
B1
3
3g
x
||||
U1+1 - uzll 4111/4+1,1 - [F,
d
1
1 C nvd 1 1 31
+ L1
2
C1
-T F2222
1=1
va 2 - C1 v/(1 31)
n m/
1 1-C C1
1 7//m,1,a1
X
C1 12-3,02
10:5 (0:s(zi)
Ci
E
VVo. + C
F
+
C1
v /
Li C-C1
1 1- 31
2vd
1)² ?/²m?? 2
2vd(1 C1)² m2
E
Fr
2
C
VI-
C7
U4.s + C
C
2/-1,1
1=1
d
C-
1/ 1 1 1-31
++ 11
2
C
VI-
2d
(0,f(z)))2
1201111 +5 + a117 )
m
17.
x
F
C2
204
/
2(1 - C2
Vvr, +
2vd(2
G)2
7 (0,f(x)))2
-B1)2
m 1,
C7
20x4 1,41111 +
2(1 - -B
V +
d
LiLo 1 -C1
Vivā 1-3
2vd
2vd(1
C1 1/2
E
Fi
+
(81)
2
C
1T-300
C7
Ve,i +
C2
V1-1. +
32

---

Published in Transactions on Machine Learning Research (02/2025)
where the first incquality is due to the (Lo, smosshhhssssssss assumption, the third incquality is due to
Lemma G and equation 80 and the last inequality is due to equation 75 and equation 76 Combine Lemma
equation 79
equation 80 and equation 81 together, and we have that
7(1 111 31)
711 {1)
1 ao
noov dD, L1 311)
n - 3:lvS nL1(1- -1)
C1
C1O₂
200
201
VI- B₂
203C1C2
204
n11 -C1 VdLı
(1 11+L1
1 1- C1
nvV 1- 1- )-,,)s
(
17
112 -2-011))
(0:f(z:))
27
C1
vI - 32C22
aa09
1201-117 +
7(1 31)
Sf(u;) - -B(((u++)(Fi)
C₁C₂
Do
1
Dn
(0.f(z)-1))
(0.f(2x))) F1
x
E
Ft
+
E
2
V2204-15+
Vv,, V1,i + 5
2
v V3201-1;+
Vor,i +5
(100k)
Bi)
03/d331 (1
31)(1 - 332
2(1- (1-3))
20102
(2((1-)) -1) + -
- Ci) dL - C1
1 B1
2(1 -
2
m
+
Cf
C1
1)
-I-3202
Cf
17²
01-1+
1f(05(11 Gi) 1)vaLo
dL
1-
1- B1
2
m
+
1p
E
Ft
Cf
2
C1
VI-
11-320p
C2
C7
Vtii + C
(1 - (1 - -i)
Σ
+
2(1 - C22
L
1+ L1 1- 11 nV 1- 11
2vd(2- - C1)² (1 31)²
m
+
x
2
C1 v1- B3C22
C7
2(1 32
VoL-1.5 +
(117/(11 - -1:)((1 - c2ddl
4
11(1
1- 1-
vVa 1-
2vd (1
+
+
1 Tn
2(1 C2)
2
C1
-2222
CJ
-2
1=1
m
x E
Fr
(82)
Ut
+
It is worth noting that 29 for any E [d] we have that
and (30 still hold for Adam since the update of dt does not change. Specifically,
+T V
E
S
(83)
v 1201-117 +
Vors +
VC
VC
t=1
Furthermore, since abp = æ1, we have that
(a.f(zo))²
(0.f(x1))2
T
(0.f(x:-1))2
E
+
+ E 1=2
v B220,11 +
Vo1, +
1201-11
01,5 + (
(ar
T-1
(ar((z))))
Σ E=1
(1 B2)
(84)
VC
1/200-115 +C
Taking expectations and telescoping we can show that
82 for to T, and based on 83 84h Lemma
and Lemma
n(1 - 31) C
7/1 (1--))
1
ag
700 (1 (1-1))1-111) 31)
n11 (1 - 3DV
+
C₂C₂
200
201
VI- VI-300, 3₂O₂
2a,
204
33

---

Published in Transactions on Machine Learning Research (02/2025)
7L1(1 C1)
vdLı
1 1 11 1 C vvd 1
v1 - B1-B,C, )
+ 1/2 C12 -1)-
))
20
2
C1
a4C1
anCp
T
(0.f(xr))2
x
12 +
711 31)
<f(ui) - ([s(ur+)) []F + Σ
C₁
1=1
D0D0 1 1
+T- 11--/B VB2
D0
(O,f(z1))
T-1
( 1))
+
Σ (1 82)
VS
V2
VS
20a1 a L
31)3
a3nd3 (1 B1)(1- -B2)
+
2(1 C2)CIC3VS
20,C2
17 21 2)2
12(22
+ dla
C1 1-3
2(1 2)) +2
+
7??
C2
C7
2
C1
VT-
B2C
Ci
x
d
E
(1
(1 - -1)3
81 //,)) )²(1 - 32)
In
UT.
Vo.i
- T Im(132)
1=1
V
dI) +1)++ (1
+
2(1 82)0902
VdL1
1 1- C1
Vd 1- 31
2 2-2(2 -c1²
ann -1-
2
C1
VI-B2Cg
Of
2(1 B2)
(1- 31)
2
T
].
x E
(Ver, vva.))
Σ
2
(85)
1=1 (1
81
)2
1 32
2/
1=1
Moreover, for any a > 0 we have that In(a) S 5a-1 1. We then have that
B(n(vrs)) = _ Blln( /er,)l 1 VVral
T
T
2 Do + V0,5
2
T
E
B5(L1
12)
T
T
1=0
2/ Do + V0.3
2
T-1
Σ
((1- 1,)
(86)
T
where the second inequality is due to equation
38
addition, for any Bg 2 0.5, we have that
1
- In( = In
15 < 2(1 - 22)
(87)
32
3
Combining
equation
39
equation
85
equation
86
and equation
87
we then can show
ELEE
2
upper bounded by a function of Σ E [ Specifically, we can
get
ΣΣ 1=1
T
E
(z.((
x
1111 111 B1)
1 +
on
700 Li, B1)
1.20-111 +
C1
C2C₂
200
201
v1 -1-38a 32C
n1
B:)vC 7L1 - 2
C1)
C,3
C7
Ca
34

---

Published in Transactions on Machine Learning Research (02/2025)
VdL1 (1
1 I1 C
C1 v1 B2C /1-BBC,)
nVd 1 1-
1/2 -2-C1)2
771 ((1-A0 -11 ag B2)
a.C2
C1C2
2
sf(wi) - B[f((u++))]F] + 1o0dd 31)
1000
2C1C2V5
2C2C2V5
+ T nddaDDol -3) - 32)
+T +T a0aa Li dd
B1)3
+ +T 03nd81 (1 Bi) - 32)
22,C2v5
2(1 - (1--8)) C2C2
201C²
2 - 11111-()Vaa VaLo +
(2(2--1) CiVooo dLaLo 1-
1-
2(1 10--0 -12 +2 17?
+
Cf
Ci
2
Ci
VII
C7
(1 B1)²
T
X
Σ
2V Do + Voti
+
Σ
(1-
(111)))) + 2T - 32) -In(vo.))
(1
B
)²(1 - B22) i=1
8/2
1=1
047 (1 -B1) B1)2dL,((1 (1) (1-
+
2(1 - C333
VdL1
1 L1 1- C1
Vvd 1- B1
2+2(2- C1)² an1 (1 - 31)2
+
Ci
V1-B2C0
Ci
2(1 - 32)
(1 (1-
2
x
Do + v0,5 +
R (1
(1 B1 )2
1 32
(=1
8/2²
4vD1
T
+ 2T / Do + Vo.1 +
(88)
VI B2
If
we
have
ag
202 01
21
210g 202 03
78 78. v
20 a4
14T, 1412-2(2--1) for 17
C(-
min
C² 12
1-82
1 B2 S
20g 20p,), ), then it can be shown that D,
(1)((1-1)(11)))
7111 - 31) (1 (11-31) 31)
2000 + 2g
+ 1000 V (D, 11 31))
73111 - -1-1--IVV
C1 CiC₂
201
V1-B200
2013
nT - -2 1T - -C1) 17(1 - (1) 00
11 - -32)
Ca
C7
C1C2
2
Vdlı
1+ (1+ T-1
1- C-C
1/ v 1- 1 )
"
712 -22-))²²)
11(1 -1)
(89)
C1
v1 32C2
1a.c7
7Ci
Let A' = f(u1)= - inf f(x) + 3andDa(1-91) 20/02/C
+ D Cs = (211-Cu (2(1-c,)VVLo + Cf
(2-O,)
+
2010
C9
VdLo (1-9)++1)
C2 = (os(1-8)) (all-))aan((L-0))(--))) + vdL, 2+2(2-C,) ( we then have that of
20703
711 -1)
T
(0,f(x))))
Σ +D
7C1
1B2U1-1,t +
i=1 t=1
<A' + T ndoo Do
B1)(1 - B2)
+ 20a1 a00aDi
2(1-3)CC133 + +T (1 - B2)
dd d2
31)3
20/C2VC
2C1C2
17 C d
Σ
2 DD + Vo,s +
Σ
E - (1)
(82) - -I((vo))
CP(1- 32) 1=1
t=1
7CO (1- 2
Σ
d
2
VDo + Vo. +
Elv (1 32)0 [1I(1-B3)0000011
(1 82)
(1
8 2
I 82
1/2
35

---

Published in Transactions on Machine Learning Research (02/2025)
AvD1
T
+ 2T 2T Do + 20 +
Σ
El a. (x;)))
(90)
v1
B2
By rearranging the items equation 90 further follows that
Vf(x2))1
T
1211e.-111
5
(Oif(z=))2
Σ
Σ
E
T
V /B200-111 +
1=1
A
+ 7n -()) (2dv Do |
14n C1,(1111111111 VDo
Σ
In (()o))))) +
Do
10
T
711 (1)
Ci(1 - -12)
(1 - B2) 1/133²
==1
TandDD(11 (2) 7aga T Lin dd d
81)²
To (1 32)d
14ndCs 31)
2C2VS
2(1 - 32)
202
C1
1, -31)d Do + Vool $1 )2
(1-32)(1-
$/8
- -4nC3(1-$IIVDD
T dE
| V (
(91)
-ivI-12
(1 - 1.).211.
Bg
)2
V/2²
For 1J S Cb(1 - 82); (where C3
and
will be introduced in Appendix )a
Cs
min
Cove
C3
C2
1/82
2landDo
21ago D2 1.1.(1 P.PC
21o3d81 84CsCsd( BA))
84C, Jay
784030g(1 8,)=dD1
V
1 1- <
Coe2, and T max
126C, A 011
1260&Ca(1-81) (2d Do + |00|
ES ln(
Do voole-2
equation 91 can be further written
T
[
T
vV BB 11-1l +
1=1
14 3iDvdDi
C ( VaD 6,
D E
< 2+
(92)
CivI-
(1 12)
//,)) )2
T
Since we have that 7) S Cs(1 - B2) and - .3 < Coc? thus have that
1
V [fxx))
ΣT LE [
5 +e
(93)
T
B2 0 +
This completes the proof.
H Formal Version of Theorem 2 and Its Proof
7/
For Ogg 2
21
2
21am 202
a' 2
04 >
C1, C2 defined in Appendix F
define
20, ,
Ci(1-91)
A' = f((1)) inf f(x) + nond 31)
nanDi(1-
20,O2V5
2C1C2V5
36

---

Published in Transactions on Machine Learning Research (02/2025)
(2 (2LCo 2(1 - VaLo
(1 (1- +1
C3
+ vala
C
Ci
Ci
(14(1 - (L) (11 (1) + - c1)
2 2(2 C2) 04(11 - 3:)2
203 )
C
+ vdLi
20102
C
C
1/22
C5 = min
112CB(1 31)dD1 168DiCiCa(1 B1)d
C2v2
CVV
C2
Co = min
2laodDo 2laga; Dg B1) & 2lazd81
(1-
$1
)2
C1
Vi
Cf
84C3C3d(1 B1)' ( B1)dy
Do + vool
784C309(1 - C
C2
C/C₂
A4 min
21 al, (1 31) VaI, Ci)(1 B1)
126CaCa(1 - (1) (2d Do + |ool
As
In(vo.i))
C1
2=1
A6 252CgCiCu(1 - 3i)d
V Do + |
A )2
V32
We then have the following theorem:
Theorem 4. Let Assumptions 4 and 3 hold. Let 1 1- B2 min
FooD; , = = < < 1,
20,
< min (AiVI --2 Cs(1 (221-)2) OE))), and T 2 max
7(1-1:)<2 Age -2 Age A2) O(E-a). For small
1260
such that < ViagCoDi we have that
/2C₂
AvdD; VCo
[(]V)( 2e 220+
(94)
Proof. The proof follows similarly the one in Appendix D According to equation we have that
92 in the proof of
Corollary 4
[+
B2 10 -1 +
14 31) dDi
B (xx)))l
2
(95)
CIVI- B2
(1 (,)
B1
T
According to Lemma
3 we have that
T
E(v 32l 1111111 +51
T
2ddD1 ΣT. [fxx))
cct
(96)
V(1 32)
Define == +T (()))(( By Hölder's inequality, we can show that
T 2 1 ト/ Σ
V Vf( 12
))
T
Bl| )
<
3r 2 1
-
Σ
El
B2
(97)
+
1=1
37

---

Published in Transactions on Machine Learning Research (02/2025)
By Lemma g and Corollary
equation 97
can be further written
- - Vi) dD,
- dDi
0 (ct
2vdD,
e² S +
CIVI- 82
(1 (1-8))1(1-0
V/2 2 )2
-I-
2/aDi
6²
S 06 + CBE +
e62 +
(98)
VCBE
2
where the sccond incquality is due to the fact that LInCs(1-OL)VDD) CiVI-82
+ (21
S and
(1-92)² 1/1 (1-111110 =1)
V
12r"C,,C(1--1))) (1 (1-82) 1(1-
2v
S Co(- 1- 82 = min
2C T
Coe2)
CGe2
Ci CivI-Aa
B )2
v VI-B
3/22
and Cg = min
T12Ca(1 - jabi
168 18 Ci Ci
Thus, we have that
T
4vdDi 22c (2c+V2c+ V2c+
[() =es
T
VCg
which completes the proof.
Experiments
In this section, we provide numerical experiments to verily the coordinate-wise generalized smoothness and affine noise variance conditions. We follow the same setting of the LSTM language model (Zhang et al. 2019) for the Penn Treebank (PTB) (Mikolov al. 2010) dataset. The model is a 3-layer LSTM language model with hidden size of 1150 and embedding size of 400. The training details follow Merity et al. (0177
Given and #t+1, we estimate the wordiinate-ise smoothness by
10,5(x; + x - -x,) - fx;(
L
max 7E(61,02.....
(99)
21 I++11ll
where (ō1, d2..... 5N} denotes for the sample locations. We then show the training results for coordinate-wise smoothness vs. absolute gradient value in Fig. 3 In Fig. 4 we plot the foordinate-wise gradient standard deviation vs. absolute gradient value.
38

---

Published in Transactions on Machine Learning Research (02/2025)
5,0010
0.0010
103
0,0008
0.0006
Smoshiee
5.0036
60
0.0004
0.0004
-60
-40
5.0002
-20
0.0002
0,0000
0. 0042
0.001
5,0056
0,00ns Grudlent
0.6310
0.0022
6600
50000 a 000005 n 0.00552 5 60075 a 0.00100
00122 6.00150
6.00775 0.00000
Gradient
100
100
0.035
Itraatin
0.023
-00
-10
0.013
0.905
2.000
0.002
0.201
0.006
0.000
0.034
0.00
0.02
0.05
0.00
5.10
0.12
0.34
Grodient
Gradient
Figure 3: Coordinate-wise smoothness vs. absolute gradient value on LSTM language model for the PTB datatset. Each figure presents one randomly selected coordinate.
39

---

Published in Transactions on Machine Learning Research (02/2025)
10-
-80
-40
Teeetto
-00
Aa 20
10-4
20
20
10-1h
10-
10
10-4
10-4
oglGrasiient
logiSrodient
-100
-100
10-4
fieertee Destiionn
-60
Tresitin
-60
20-4
40
40
10
oggGrasslent
Ing]rradient Mear)
Figure 4: woordinate-wise gradient standard deviation vs. absolute gradient value on LSTM language model for the PTB datatset. Each figure presents one randomly selected coordinate.
40


Reviews:
[{"review_id": "suv74llRVY", "reviewer": "Reviewer_McMB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n**Technical Depth**: The authors develop intricate proofs to overcome significant technical challenges, such as handling unbounded gradient estimates and mismatched terms in the descent lemma.\n\n**Comprehensive Coverage**: Both RMSProp (without momentum) and Adam (with momentum) are analyzed, and their coordinate-wise version is analyzed, which is more detailed comparing to existing work.\n\n**Clear Structure and Proof**: The manuscript is well-structured, and the proof is presented in a manner that is easy to understand, which facilitates the reader's comprehension of the convergence analysis.\n\nWeaknesses\n\n**Inaccurate Claim**\n\nThe paper's claim that the result matches the lower bound in Arjevani et al. (2023) is inaccurate because this paper is developed under the assumptions of relaxed smoothness of the objective while Arjevani et al. (2023) derives the lower bound under the assumptions of  global L-smooth condition of the objective. \n\nThe paper claims that it improves logarithmic factors in iteration complexity than Wang et al. 2023a. It is not an accurate claim as the logarithmic factors are addressed in  Section 5 Theorem 2 of  Wang et al., 2023a.\n\nMoreover, the paper's techniques are not much of innovations. Given the result of Li et al., 2023, the contribution of this paper is the expansion of the noise assumption to coordinate-wise affine noise. This extension is not technically hard given existing works have already considered affine noise assumptions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the convergence properties of RMSProp and Adam in non-convex optimization settings. RMSProp and Adam are analyzed under relaxed assumptions: coordinate-wise generalized smoothness and affine noise variance. The paper addresses challenges like the dependence of adaptive updates, unbounded gradient estimates, and Lipschitz constants, and establishes a convergence to an $\\epsilon$-stationary point with an iteration complexity of $O(\\epsilon^{-4})$, which matches existing analysis under similar assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please correct or restate the claims in an more accurate way, which are mentioned in the weakness part.", "broader_impact_concerns": "The paper studies the theoretical convergence of widely used optimizers. It will give us more theoretical understanding of adaptive optimizers and will not lead to other impact concerns as far as I see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7k9MW7FXZR", "reviewer": "Reviewer_p2PR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Major theorems and lemmas are generally correct and the paper is technically sound.\n2. The paper demonstrates the limitation of the previous works in the literature showing that most convergence theorems are based on the assumptions that are not hold for widely used neural networks.\n3. The paper shows the minor change to the algorithm does not drastically affect the performance of the convolutional neural network trained on CIFAR10 dataset.\n4. The paper explains the main challenges of using coordinate-wise $(L_0, L_1)$ smoothness instead of bounding gradient and $(L_0, L_1)$ smoothness.\n\nWeaknesses (the suggestions for them is listed in the next section)\n1) There is an error in the presentation of Lemma 1 (and its extended version Lemma 5). Also, the explanation of its usage in the beginning of Page 8 is not clear (and needs to be revised).\n\n2) It is not clear how Lemma 1 is applied in the proof of Lemma 2. \n\n3) The change in the Adam algorithm has no motivation except the convenience in the proof. It is expected to discuss how it changes the behavior of the algorithm. While it is numerically shown that it does not change the performance drastically, it can be further explored for other neural network architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes the convergence behavior of RMSProp and Adam as two well-known primary optimizers for different variations of neural networks (Convolutional Neural Networks, LSTM, Transformers) under more realistic assumptions of coordinate-wise Lipschitz continuity (smoothness) and coordinate-wise affine noise variance of the gradient. While there are several recent papers showing the convergence of these optimizers under each one of these two assumptions combined with stronger assumptions, this is the first paper that have both of these more general assumptions compared to the previous works. The main challenge of showing the convergence of these algorithms under these conditions is that due to the dependence of the step-size to the gradient size, bounding the first-order surrogate error is not straightforward. To address this issue, the authors slightly change the update rule for the step-size of Adam. They numerically show that by applying this change, the performance of the optimizer in the test phase is not drastically affected. By changing the update rule, they bounded the first-order surrogate error, and therefore, given the rich theory for proving the convergence of Adam and RMSProp, the remaining steps are straightforward.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Suggestions:\n\n1. There are several issues in proving theorems. \n    \n- Lemma 1 should be used as an upper-bound. I am not sure why we seek to lower-bound the first-order.b term in Lemma 1. Therefore, the inequality must be flipped in Lemma 1 and its formal version (Lemma 5). The explanation in the beginning of Page 8 must be revised accordingly. By following the proof of Lemma 5, we can observe that the term is upper-bounded but the Lemma statement is written as a lower-bound. Also, the authors use Lemma 1 in the proof of Lemma 2 correctly (as an upper-bound). I also suggest to explain more in Lemma 2’s proof how you use Lemma 1. \n    \n- In the proof of Lemma 2, the authors just mentioned “Based on Lemma 1, we can bound the first-order.b term. We then have that.” Please explain how Lemma 1 can be applied and what will be the result. The current version is confusing and needs efforts for the readers to understand the proof\n\n2. The change in the Adam algorithm is for the proof convenience. To justify it, either there should be an intuitive explanation (why does the original version have that form? And, how this change conceptually change the algorithm). Also, it will be nice to validate the test error for another type of neural networks such as transformers. Because, the CIFAR10 dataset is not a very challenging one.\n\n3. The paper does suggest the limitation of the bounded gradient and $(L_0, L_1)$ smoothness even for the linear regression and mentions the coordinate-wise version is more general. Is it possible to validate it for a simple multi-layer neural network or a small convolutional neural network to motivate the assumption (as the main contribution of the paper) for practitioners?", "broader_impact_concerns": "No Concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4G3haUHjgV", "reviewer": "Reviewer_fhNs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths :** The paper shows a tight bound for convergence analysis to an $\\epsilon$-stationary point for RMSProp and Adam under relaxed assumptions with respect of what is done in the literature, which the authors effectively situate within the literature. The technical content is robust; the proofs appear correct, to the best of my knowledge. Understanding of the main results through the well-presented key ideas in the main text (with detailed evidence available in the appendix) is particularly appreciated.\n\n**Weaknesses :** The assumption that $f$ is differentiable is common in convergence analyses for neural network training, but is rarely the case in practice. In particular, it is said the chosen assumptions \"best describe the training of some neural networks\". A clarification on neural networks that fall within the framework of coordinated generalized smoothness $(L_0,L_1)$ and affine noise variance condition could be added; along with a note on the neural networks (or the type of functions) that verify these assumptions (the more relaxed one), but not those otherwise considered in the literature.\n\nPlease note that my expertise lies outside the direct focus of this paper, therefore I am not familiar with the literature around RMSProp and Adam, so I may be missing references and insights.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors establish the convergence of both RMSProp and Adam to a $\\epsilon$-stationary point with iteration complexity of $\\mathcal{O}(\\epsilon^{-4})$ for functions verifying coordinate-wise generalized $(L_0,L_1)$-smoothness assumption and under affine noise variance condition. Their approach focuses specifically on neural network training.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My only request is that the authors highlight examples where the combination of the two assumptions is particularly relevant, in order to reinforce the interest of this particular framework. That said, I think the proposed article is of sufficient interest to the community to be published in TMLR.\n\nMinor comments :\n- Page 12 : In Figure 1, you could specify what the parameter $\\lambda$ corresponds to.\n- Page 12 : \"The only thing inspired by Wang et al. (2023a) in this paper to set this $\\beta = \\frac{\\beta_1}{\\sqrt{\\beta_2}}$.\" -> The verb is missing.\n- Page 16 : \"RKS\" should be RHS.\n- Page 17 : $\\frac{\\vert g_{t,i}\\vert}{\\sqrt{v_{t,i}}+\\zeta}$ should be $\\frac{\\vert g_{t,i}\\vert}{\\sqrt{v_{t,i}+\\zeta}}$\n- Page 19 : In equation (27), I may be wrong, but shouldn't we have a factor $\\frac{1}{4}$ instead of $\\frac{1}{2}$ for the last two terms in the last inequality?\n- Page 22 : \"Give\" -> Given.\n- Page 27 : \"haveequation\" -> have equation.\n- Page 29 : Last line : \"$2\\beta_2\\geq 1$\" -> $2\\beta_2> 1$.", "broader_impact_concerns": "I have no ethical concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are positive enough and any of their concerns were addressed in the rebuttal.  The only outstanding issue is, to quote from a reviewer's final decision, 

"If the authors can suggest several practical scenarios in which the assumptions work beyond the established literature, the paper can gain significantly more attention."

I agree with that. I know the paper already talks about the assumptions, but being even more clear or with more examples can only help. So if the authors wish to add more discussion/examples/citations here, they may do so in the final camera-ready version (but it's not a strict requirement, so up to their judgment).
Decision: Accept (poster)