Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed
Authors: Savelii Chezhegov
Klyukin Yaroslav
Andrei Semenov
Aleksandr Beznosikov
Alexander Gasnikov
Samuel Horváth
Martin Takáč
Eduard Gorbunov
Venue: ICML 2025 poster (2025)
Keywords: stochastic optimization
heavy-tailed noise
adaptive methods
gradient clipping
high-probability convergence bounds
Primary area: optimization->stochastic
TL;DR: We prove that AdaGrad and Adam fail to achieve good high-probability convergence guarantees and show how gradient clipping fixes this issue under the heavy-tailed noise assumption.

Abstract: Methods with adaptive stepsizes, such as AdaGrad and Adam, are essential for training modern Deep Learning models, especially Large Language Models. Typically, the noise in the stochastic gradients is heavy-tailed for the later ones. Gradient clipping provably helps to achieve good high-probability convergence for such noises. However, despite the similarity between AdaGrad/Adam and Clip-SGD, the current understanding of the high-probability convergence of AdaGrad/Adam-type methods is limited in this case. In this work, we prove that AdaGrad/Adam (and their delayed version) can have provably bad high-probability convergence if the noise is heavy-tailed. We also show that gradient clipping fixes this issue, i.e., we derive new high-probability convergence bounds with polylogarithmic dependence on the confidence level for AdaGrad-Norm and Adam-Norm with clipping and with/without delay for smooth convex/non-convex stochastic optimization with heavy-tailed noise. We extend our results to the case of AdaGrad/Adam with delayed stepsizes. Our empirical evaluations highlight the superiority of clipped versions of AdaGrad/Adam in handling the heavy-tailed noise.

Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed
Savelii Chezhegov 123 Yaroslav Klyukin ! Andrei Semenov 4
Aleksandr Beznosikov 1256
Alexander Gasnikov-517 Samuel Horváth 8 Martin Takáč*
Eduard Gorbunoy
Abstract
1. Introduction
Stochastic first-order optimization methods such as Stochas- tic Gradient Descent (SGD) (Robbins & Monro, 1951) are the methods of choice in training modern Machine Learn- ing (ML) and Deep Learning (DL) models (Shalev-Shwartz & Ben--avid, 2014; Goodfellow et al., 2016). There multiple reasons for that, including but not limited to their simplicity, computation cost, memory usage, and gener- alization. However, standard SGD is rarely used due to its sensitivity to the choice of stepsize. Therefore, meth- ods such as AdaGrad (Streeter McMahan, 2010: Duchi et al., 201 and Adam (Kingma & Ba, 2014), which use adaptive' stepsizes, are much more popular in the DL com- munity (Vaswani et al., 2017; You et al., 2019; Nikishina et al., 2022: Li et al., 2022; Abdukhakimov et al., 2024; 2023; Li et al., 2024; Schaipp et al., 2023; Loizou et al., 2021; Moskvoretskii et al., 2024a;b; Shi et al., 2023). In particular, Adam-type methods are not just easier to tune but they also achieve better results in terms of the model performance than SGD in the training of Large Language Models (LLMs) (Devlin et al., 2019; Zhang et al., 2020).
Methods with adaptive stepsizes, such as Ada- Grad and Adam, are essential for training mod- ern Deep Learning models, especially Large Lan- guage Models. Typically, the noise in the stochas- tic gradients is heavy-tailed for the later ones. Gradient clipping provably helps to achieve good high-probability convergence for such noises. However, despite the similarity between Ada- Grad/Adam and Clip-SGD, the current under- standing of the higb-probabilltyy convergence of AdaGrad/Adam-yyee methods is limited in this case. In this work. prove that AdaGrad/Adam (and their delayed version) can have provably bad high-probability convergence if the noise is heavy-tailed. We also show that gradient clip- ping fixes this issue, i.e., we derive new high- probability convergence bounds with polyloga- rithmic dependence the confidence level for AdaGrad -Nrm and Adam-Norm with clipping and with/without delay for smooth convex/non- convex stochastic optimization with heavy-tailed noise. We extend our results to the case of Clip-ddaGrad/Cipp---
In the attempt to explain the later phenomenon, Zhang et al. (2020) consider the noise distribution in the stochastic gra- dients appearing in the pre-training of the BERT model (Devlin et al., 2019) and show that (i) the gradient noise is heavy-tailed in this case, (ii) Adam significantly out- performs SGD (with momentum). (iii) Clip-SGD (Pas- canu et al., 2013) also converges better than SGD for such problems, and (iv) Clip-SGD is provably convergent (in- expectation) when the noise has bounded a-th moment for some a E (1,2) while SGD can diverge for a < More- over, gradient clipping also plays a central role in the recent advances on the high-probabilityy convergence of stochastic methods under the heavy-tailed noise (Gorbunov et al., 2020; Cutkosky & Mehta, 2021; Sadiev et al., 2023; Nguyen et al., 2023). Taking into account the similarities between Adam
with delayed step- sizes. Our empirical evaluations highlight the su- periority of clipped versions of AdaGrad/Adam in handling the heavy-tailed noise.
Mooscow Institute of Physics and Technology. Russia Ivannikov Institute for System Programming RAS, Russia SSher AT Lab, Russia 'Machine Learning and Optimization Laboratory (MLO),, EPFL. Lausanne, Switzerland 'Innopolis University, Rus- sia "The Russian Presidential Academy of National Economy and Public Administration, Russia "Skolkovo Institute of Science and Technology. Russia 'Mohamed bin Zayed University of Artificial Intelligence, UAE Correspondence to: Eduard Gorbunov <ed- uord-gorbunov @mbzuai.ac.a.. ac.ac>.
'Throughout the paper, use the word "adaptivity" in its general meaning: stepsizes adaptive if they depend the (stochastic) gradients or function values. We emphasize that, in this sense, an adaptive method can still have parameters affecting its convergence.
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Clipping Improves Adam-Norm and AdaGrad-Norm
and Clip-SGD (the former one can be seen as Clip-SGD with momentum and iteration-dependent clipping level), one can conjecture that Adam enjoys good theoretical high- probability convergence when the gradient noise is heavy- tailed. If this was true, it would be perfectly aligned with the observations from (Zhang et al., 2020) about the connection between the noise in the gradients and Adam's performance. Moreover, some recent works show that AdaGrad/Adam have provable convergence under generalized smoothness assumptions (Faw et al., 2023; Wang et al., 2023; Li et al., 2023; Wang et al., 2024). Since Clip-SGD has similar convergence properties and since some authors explicitly mention that in this regard Adam and Clip-SGD are simi- lar", it is natural to conjecture that clipping is not needed in Adam/AdaGrad.
and their variants with delay by Li & Orabona (2020) do not have polylogarithmic dependence on the confidence level in the worst case when the noise is heavy-tailed. In particular, we design an example of a convex stochas- tic optimization problem such that the noise is heavy- tailed and the high-probability convergence complexity of Adam/AdaGrad has the inverse-power dependence on the target accuracy and confidence level.
Clipping fixes Adam-Norm and AdaGrad We prove that the above issue can be addressed via gradient clipping. That is, we derive sesh-probabilitt complexity results for Mlip-Adam-Norma and Clip-AdaGrad-- Norm (with and without momentum) in the case of smooth con- vex (for the methods with delay) and non-convex (for the methods with and without delay) optimization with the heavy-tailed noise having bounded a-th moment with a E (1,2). 2]. The obtained results have the desired polylog- arithmic dependence on the confidence level. Moreover, in the non-convex case, the derived complexities are opti- mal up to logarithmic factors, and match the complexity of Clip-SGD in the convex case up to logarithmic factors. We derive similar results for the modifications pf Clip- Adam and Clip-AdaGraa with delay in the non-convex case, showing that our analysis is applicable to the case of the methods with coordinate-wise stepsizes.
However, there are no theoretical results showing the high- probability convergence with polylogarithmic dependence on the confidence level of Adam under the heavy-tailed noise and even in the case of the bounded variance. Even for simpler "twin"3 33 such as AdaGrad there exists a similar gap in the literature. Moreover, Mosbach et al. (2020) apply gradient clipping even for Adam in the fine-tuning of BERT and ALBERT (Lan al., 2019) models. However, Mosbach et al. (2020) do not report the results that can be achieved by Adam without clipping. Therefore, it remains unclear whether and when the gradient clipping is needed for Ada- Grad/Adam and whether AdaGrad/Adam enjoy desirable high-probability convergence under the heavy-tailed noise.
Numerical experiments. We conducted numerical ex- periments for synthetic and real-world problems. More precisely, we illustrate the superiority of different versions of Adam/AdaGrad with clipping to the non- non-clipped ver- sions of Adam/AdaGrad on a simple quadratic problem with additive heavy-tailed noise in the gradients. Next, we also test Adam with and without clipping on the fine- tuning of ALBERT Base model (Lan et al., 2019) on CoLa and RTE datasets (Wang et al., 2018) and observe that Adam with clipping significantly outperforms Adam without clipping when the noise is heavy-tailed. We also obtain similar results for the fine-tuning of RoBERTa Large model (Liu et al., 2019).
In this work, we address this gap in the literature, i.e., we consider the following questions:
Does the high-probubiiityy complexity of Adam/AdaGrad without clipping have polylogarithmic dependence on the confidence level under the heavy-tailed noise?
Does clipping improve the convergence of AdaGrad/Adam under the heavy-tailed noise?
We provide a negative answer to the first question and a positive answer to the second one.
1.2. Preliminaries
1.1. Our Contributions
In this section, we formalize the setup. We focus on uncon- strained minimization problems
The main contributions of this work are summarized below.
Negative results for Adam and AdaGrad. We show that the bigh--robability complexities of Adam and AdaGrad
min f(x); #E
(1)
PPn & Li (2023) write in the abstract: "We conclude that the sharpness reduction effect of adaptive coordinate scaling is the reason for Adam's 's success in practice." In addition, Zhou al. (2020) mention in the discussion of the related work: "... adaptation in ADAM provides a clipping effect."
where the differentiable function f(x is accessible through the calls of stochastic first-order oracle returning an approx- imation Vfe( of fzx)). Here & is a random variable following some distribution D that may be dependent on æ and time. In the simplest case, fe (x) is a loss function on the data sample & and f(z) = E [ife (x)] is a population risk (Shalev- Shwwarz, & Ben-David, 2014).
'The existing convergence results for Adam often require the choice of parameters that make Adam very similar AdaGrad with momentum (Défossez. et al., 2022y; see also Section 1.3.
2

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Notation. The notation is quite standard in this work. We use [ to denote an expectation w.r.t. random vari- able c. All norms are standard Euclidean ones: ||a||| = (x,x).. The ball centered at x with a radius R is de- fined as Br(œ) == {v E TR lly - -x]l < R}. We also use x² to denote (any) solution of (1) and f. := inf J' f(r) Clipping operator with clipping level À >
this is not always the case; see (Sadiev et al., 2023, Ap- pendix B) for further details. Interestingly, when Q is compact set, function f can have non-Lipschitz gradients (e.g., polynomially growing with z) on R see also (Patel et al., 2022; Patel & Berahas, 2022).
In addition, for some of our results, we assume that the objective is convex.
defined as clip(æ, A) == min Y/al] for x + 0 and el clip(r, >) 0 for x = O.
Assumption 1.3 (Optional). There exists set Q C such that for all z, y E Q
Assumptions. We start with the assumption' on the noise.
((v) 2 (x) + (VI(x), x).
(4)
Assumption 1.1. There exists set Q S IRd and 2 a E (1,2) such that for all k 2 0 the oracle satisfies EIV fc. (x) x]] = vz(x) and
Finally, for the methods without the delay, we assume that function f is bounded.
E Sea (1) (())il| o0
Ya E Q.
Assumption 1.4 (Optional). There exists constant M 0 such that for all æ Rd
The sequence {&A J420 is the sequence of independent ran- dom variables.
J. M.
(5)
The above assumption used in many recent works (Zhang et al., 2020; Cutkosky & Mehta, 2021; Sadiev et al., 2023; Nguyen et al., 2023). When 2, it allows the stochastic gradients to have unbounded variance, e.g., Lévy a-stable noise. Such distributions are usually called heavy-tailed. When a = 2, it reduces to the standard bounded variance assumption (Nemirovski et al., 2009; Ghadimi & Lan, 2012; 2013; Takáč et al., 2013).
A stronger version of the above assumption (boundedness of the empirical risk) is used in (Li & Liu, 2023), which is the only existing work analyzing AdaGrad with clipping.
Why high probbbbbbbyllty convergence? The vast majority of the existing literature on stochastic optimization focuses the in-expectation convergence guarantees only. In partic- ular, for some metric P(z) quantifying the output's 's quality, e.g., P(x) = f(z) - ((=*). [Vf ||x =11 I|?, such guarantees provide upper bounds on the number of iter- ations/oracle calls required for a method to find x such that [[[(x)] S E. However, during recent years, high- probability convergence guarantees have been gaining a lot of attention as well. Such guarantees give upper bounds on the number of iterations/oracle calls required for a method to find x such that P(P(2)) S =} 2 8, where ó is usually called confidence level or failure probability. One can argue that using Markov's inequality, one can easily deduce high-probability guarantee from an in-expectation one: if [[(((x < sō, where X (x((5)) is an output of the method after K(εō) iterations/oracle calls, then ((P((T((E)) > 8} < H)P(zxceo)ll/ S 8. Unfortunately, for many methods such as SGD (Ghadimi & Lan, 2013) ((s) has inverse-power dependence on E implying that K(=ō) has inverse-power dependence on eô, leading to noticeable deterioration when 5 is small. Therefore, de- riving high-probability complexities with polylogarithmic dependence on requires a separate and thorough consider- ation and analysis. Moreover, such bounds more accurately reflect the methods' behavior (Gorbunov et al., 2020).
We also emphasize that the above assumption allows for the time-dependent noise, which actively use in our negative results from Section 2. Although not often explicitly stated, many existing results in stochastic optimization (Ghadimi & Lan, 2012: Harvey et al., 2019; Sadiev et al., 2023; Zhang et al., 2020; Cutkosky& & Mehta, 2021; Nguyen et al., 2023) hold in the case of the time-dependent noise as long as certain moment bounds (e.g.. (2)) hold.
Next, we make a standard assumption about the smoothness of the objective function.
Assumption 1.2. There exists set Q C IRd and L > 0 such that for all x, y E Q
[v)(() ff(=))1 < Lbyy ==|,
(3)
[z)) < (z) - f.).
We emphasize that the second part of (3) follows from the first part if Q = dRd However, in more general situations,
"Similarly to (Sadiev et al., 2023), for our results. it is sufficient make all the assumptions only some Q. This set is typically bounded and depends on some metric of sub-optimaliity of the starting point, c.g., the distance from the starting point to the optimum. We emphasize that our assumptions are strictly weaker than corresponding ones for Q = Rdd To achieve this kind of generality, we prove that the proposed method does not leave some set Q with high probability.
1.3. Related Work
Hiobb-brybabilityy convergence. The first results showing the high-probability convergence of SGD and its variants
3

---

Clipping Improves Adam-Norm and AdaGrad-Norm
are derived under the sub-Gaussian noise assumption for convex and strongly convex problems by Nemirovski al. (2009); Ghadimi & Lan (2012); Harvey et al. (2019) for non- convex problems by Li & Orabona (2020). Although the distribution of the noise is wear-sub--Gausian in some cases, like in the training of ResNer50 (He et al., 2016) on Ima- geNet (Russakovsky et al., 2015) as shown by Zhang et al. (2020). this assumption does not cover even the distributions with bounded variance. To relax the aub-Gaussian noise as- sumption, Nazin et al. (2019) consider a truncated version of Stochastic Mirror Descent, which is closely related to Clip-SGD, and prove its highh-robabilltyy complexity with polylogarithmic dependence on 5 under bounded variance assumption for convex smooth problems on the bounded domain. In the strongly convex case, Davis et al. (2021) propose general approach for obtaining high-probability convergence based on the robust distance estimation and show accelerated high-probability rates in the strongly con- vex case. Next, for the unconstrained problems, Gorbunov et al. (2020) prove the first srsbbprbbability convergence re- sults for SGD and the first accelerated high probbbbbbay rates in the convex case for a version of Clip-SGD with Nesterov's momentum (Nesterov, 1983). This result is gen- eralized to the problems with Hölder-comtinuous gradients by Gorbunov et al. (2021). Cutkosky& & Mehta (2021) derive the first -robbbbbbbbylity convergence results under Assump- tion 1.1 with a < 2 for a version of Clip-SGD with nor- malization and Polyak's 's momentum (Polyak, 1964) in the case of non-convex problems with bounded gradient. Sadiev et al. (2023) remove the bounded gradient assumption in the non-convex case and also prove the first high-probability convergence results under Assumption 1.1 for SGD and its accelerated version in the convex and strongly con- vex cases. Nguyen et al. (2023) provide improved results in the non-convex case under Assumption 1.1 and also im- proved the dependency on the logarithmic factors in the convergence bounds. The generalization to the composite and distributed optimization problems is developed by Gor- bunov et al. (2024). It is also worth mentioning (Jakovetić et al., 2023; Puchkin et al., 2024) who consider potentially heavier noise than in Assumption 1.1 through utilizing the additional structure of the noise such as (near-)su -symmmtry. This direction is further explored by Kornilov et al. (2024) and adjusted to the case of the zeroth-order stochastic oracle.
The method is analyzed in many works, in- cluding (Streeter & McMahan, 2010; Duchi et al., 2011; Zou et al., 2018; Chen et al., 2018; Ward et al., 2020; Défossez et al., 2022; Faw et al., 2022) to name few. However, the high-probability convergence of AdaGrad is studied under restrictive assumptions such as almost surely sub-Gaussian noise (Li & Orabona, 2020; Liu et al., 2023) or without such an assumption but with inverse- powser dependence on the confidence level ò (Wang et al., 2023) boundedness of the empirical risk and (non-central) a-th moment (Li & Liu, 2023), which in the worst case implies boundedness of the stochastic gradient (see the discussion after Theo- rem 3.3). In contrast, our results for Clip-Adam(D)/Clip- M-AdaGrad(D)
coordinate-wise.
hold under Assumption 1.1 (and under additional Assumption 1.4 for the methods without delay) and have polylogarithmic dependence on 6.
Adam (Kingma & Ba, 2014) can be seen as modification of AdaGrad with an exponential moving average bf of the squared stochastic gradients and with Polyak's 's momentum (Polyak, 1964):
2
Te+1 = It-
m,: b,
(Adam)
my = -mm--1 + -1- Ve.
b. v /8206 + (1-11)))1 fz.
(6)
where all operations (taking a square and taking a square root of a vector, division by a vector) are performed coordinate-wise. Although the original proof by Kingma & Ba (2014) has a flaw spotted by Reddi et al. (2019), one can still show the convergence of Adam when 3n goes to 1 (Défossez et al., 2022; Zhang et al., 2022; Wang et al., 2024). Moreover, for any fixed 33, and B2 such that 31 < / e.g., for the default values 31 0.9 and 32 = 0.999, Adam is not guaranteed to converge (Reddi et al., 2019, Theo- rem 3). Therefore, the standard choice of B3 in theory is 3e = - 1/K, where K is the total number of steps, and that is why, as noticed by Défossez et al. (2022), Ada- Grad and Adam are "twins". Indeed, taking 31 = 0 (no momentum) and B3 = 1 - 1/K in (6) we get that 12 (1 (111xx)+ +1 + K Eh 1/x))= (xx))² θ + (V (x)))))))) since 1/1= (1-1/22) <
(1-1/x)-* for < k < S K. Thus, up to the rescal- ing of and b21 the effective stepsize of Adam-CW is o(.) of the effective stepsize of AdaGrad-CN (though the points where the gradents are calculated can be quite different for these two methods). This aspect explains why AdaGrad and Adam have similar proofs and convergence guarantees. convergence of Adam is studied by Li et al. (2023) under bounded noise and sub-Gau Sab-Guussian noise assumptions, while our results for Clip-Adam(D) do not require such assumptions.
AdaGrad and Adam. AdaGrad (Streeter & McMahan, 2010; Duchi et al., 2011) has the following update-rule
F++1= = xt - ? V
bi
(AdaGrad)
where b.- = D2_ + (z))),
The
where all operations (taking a square and taking a square root of vector, division by vector) are performed
4

---

Clipping Improves Adam-Norm and AdaGrad-Norm
2. Failure of Adam/AdamD and AdaGrad/AdaGradD with Momentum
Adam(D)M-AdaGraa(D) do not achieve desired high- In this section, we present the negative result on the conver- gence of Adam, AdaGrad with Momentum (M-AdaGrady) and their delayed versions - AdamD/M-AdaGradD (Li & Orabona, 2020).
probability convergence rates and motivates us to apply clipping to Adam(D)M--AdaGrad(0)
Time-dependent noise. We also emphasize that the noise structure is time-dependent in the provided example, which is used to simplify the proof. Moreover, as discussed in Section 1.2, many existing upper bounds hold for time- dependent noise as well.
Theorem 2.1. For any a > 0 and sufficiently small e, E (0, 1), there exist problems (1) such that Assumptions 1.1, 1.2, 1.3, hold with with I. = 1, at = 2, and the iterates produced by (aaam(DM-AdaGraaa
with zo such that 1/r for Adam(D) satisfy: P (f(TT) f(x') 2 8) S 6, then
Initial condition. The provided negative examples rely on the assumption that |zo| is sufficiently large, i.e. the method is initialized not too close to the optimum. In particular, for M-AdaGrad, we require To > v2 + 3y. Since typically E < 1, the condition is relatively mild. Moreover, this assumption simplifies the proof. Although we do not pro- vide negative results for arbitrary choice of zo and % we conjecture that similar negative results can be obtained in the case of more general choice of %
|aa x1' > I and with B2
T T= Ω (poly(=-Ve, //,88/// V-)))
iee, the complexity of Adam(D)M-AAdaGradl) has inverse-power dependence on d.
Sketch of the proof. To construct our example, we consider the Huber loss function (Huber, 1992)
Generalization under Assumption 1.4. The provided ex- ample does not satisfy Assumption 1.4 that is used in the next section in the analysis of methods without delay (Theo- rem 3.3). To address this issue, one can replace function (8) with the following one:
J0² (xx) = V (|x] -2),
if |2| Su, otherwise,
(8)
and design two specific sequences of noises (one for Adam/M-AdaGrad and the second one for AdamD/M- AdaGradD). For Adam/M-AdaGrad, we consider a dis- crete additive noise for the first step such that Markov's inequality holds as equality, and for the remaining steps, noise equals zero. Then, with high probability, b, becomes large after the first step, which slowdowns the method. As for AdamD/M-AdaGradD similarly to Sadiev et al. (2023), we add the noise only to the last step: since by is constructed using the norm of the previous stochastic gradient, the noise independent of the stepsize and can spoil the last iterate. See the complete proof' and details in Appendix B.
2 2000
if | if | < D,
f(x) = v (1x) 5²),
(9)
v (D 2))
if |x| > D,
where D is such that D > |zo||- Then, the modified function satisfies Assumption 1.4 and the proofs remain the same.
3. New Upper Bounds
To address the issue indicated in Theorem 2.1, we consider Clip-Adam(D)/Cipp. -atp//Ciii-MAaGra((()).a)-----// Ad) (see Algorithm 2). In contrast to the existing practice (Pan & Li, 2023), we use clipping of the stochastic gradient not only in the update rule for momentum buffer m, (Line 3 in Algorithm 2), but also in the computation of the scaling factor b, (Lines 5 and 7 in Algorithm 2). The role of clipping in m, is similar to the role of clipping in Clip-SGD-type methods: it prevents the method from too large steps that may occur due to the presence of the heavy-tailed noise in the gradients. In this regard, is important to select clipping level in such a way that bias and variance of the estimator are balanced. However, the role of clipping in by is different: clipping prevents b, from growing too quickly since such growth can lead to poor high-probability guarantees (see the proof's sketch of Theorem 1). We note that clipping is also used in Clip-AdaGrad-Noon -orm (without momentum, i.e., with 31 = 0) for both my and b, computation by Li
Methods.
Interestingly, in the above example, it is sufficient con- sider the noise with bounded variance show that the high- probability convergence rates of (aam(D)/M-AdaGrad()) depend polynomially on s-1 and 8-//2 Moreover, fol- lowing a similar argument to (Zhang et al.. 2020, Re- mark 1), one can show the non-convergence of AdamD/M- AdaGradD when a < 2. We also conjecture that for 2 one can show even worse dependence on E and 6 for Adam/AdaGrad (or even non-convergence) since b, will grow with high probability even faster in this case. Moreover, we also emphasize that the negative re- sult for Adam(D) is established only for 82 = =1 1/T, which is a standard assumption to ensure convergence of Adam-type methods. Nevertheless, the negative re- sult of Theorem 2.1 provides necessary evidence that
5

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Algorithm Addm-torm/AAdmmD-torm and N.AkaaCrnccrommmt--kCGaa000000
Input: Stepsize > 0, starting point 20 E IR initial constant b-1 > 0 (for Adam-norm and M-AdaGrad-norm) or
by > 0 (for AdamD-norm and M-AdaGradD-norm) momentum parameters B1, B2 E [0
1: Set m- 1.... do 2: for t
3: my - + (1 8 (x+)
4: if no delay then
B2b3
B2)1l B2).IV Ve. (x:)]l
for Adam-norm for M-AdaGrad-norm
5: be
12 (x.)ll
6: else
v
VBgh Bybl
+ (1 B2)1l Se, fe. (x))l²
for AdamD-norm for M-AdaGradD-norm
7: bi+1
v b3 + (v)e
8: end if
9: 2(+11
Zt
b. m+
10: end for
Algorithm Clll--aam--ommmoiii--ddddDDDDD
and Cll-M/AAAacaacccammmmiiiiiAAAAAa
Input: Stepsize > 0, starting point Rd, initial constant b_1 > 0 (for Clip-Adam-norm and Clip-M- ClipM--AdGrrad
norm) or bo > (for -lip-AdamD-norm and Clip-M-AdaGGraD--orrm) momentum parameters 31, 32 E [0, 1]. level
of clipping À > 0
1: Set m- = 0
2: for = 0, 1, ..... do
my 8mm-1 + (1 81)clip (
4: if no delay then
B2b] (1 (1- (2)). A)1
for Clip-Adam-Norm
5: b
1/ +
(x:),
for Clip-M-AdaGrad-Norm
6: else
/32b + +1 12][cclipp (V.e, (2x), A)1
for Clip-AdamD-Norm for Clip-M-AdaGradD-Noom
7: bi+1
bf + ||elip (V. A2))
8:
end if
9: Tt+1
Ze b. m.
10:
end for
Liu (2023) but the authors do not comment about the role of clipping in b, and use restrictive assumptions as we explain later in this section.
è ( (vT-AbboR)
where A In
((K+1) 8
Then, to guar-
antee [((K) ) [(x²) S E with probability at least
for EK = KtI En Ft Clip-AdamDDCiip-MMAAaed
Norm requires:
Convergence results. We derive new high-probability convergence bounds for the generalized method formalized as Algorithm in the convex and non-convex cases. The fol- lowing theorem gives the main result for Clip-AdamD/Clip- AdaGradD-Nome
LR
oR
δ max
(10)
(1- BE
(1- (1
iterations/oracle calls. Moreover, with probability at least 1- ô, all iterates { stay in Q.
the convex case.
Theorem 3.1 (Convex Case). Let K > O and 8 e (0. 1] and Assumptions 1.I, 1.2, and 1.3 hold for Q = B2R(x") for some R 2 | - -x*l|- Assume that
Next, we present main results for Clip-AdamD/Clip- M-AdaGradD-Nont and ClppAAdam/Clip-MAAtaGnaa Norm in the non-convex case.
31 E 1), B2 =
K+1 (for Clip-AdamD-Norm)
= θ min (1-9) 9 166
Rby Réu
8-1 1) and X
Theorem 3.2 (Non- Convex Case: Methods with Delay), Let
LA
a(K+)]&A
> 0 and 8 (0, 1] and Assumptions I.I and 1.2 hold for
6

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Q = f E Rº1 By E (2A): || - vll S /A } with
the confidence level 8. Up the differences in loga- rithmic factors, these complexities coincide with the best- known ones for Clip-SGD (Sadiev et al., 2023; Nguyen et al., 2023). Moreover, the leading terms in (11) and (12) are optimal up to logarithmic factors (Zhang et al., 2020), though the first terms in (II) and (12) can be improved (Ar- jevani et al., 2023). In the convex case, the first term in (10) is not optimal (Nemirovskij & Yudin, 1983) and can be improved (Gorbunov et al., 2020; Sadiev al., 2023). The optimality of the second term in (10) is still an open question.
20vL J
(2 = tu E Rn11 f(v) S f. + 2 for some A 2
f(xo) - f-- Assume that B1 E 10, $2= - K+T (for
K
Clip-AdamD-Nomm and
(1-31)bb
VI B
y = θ min
L(K + 1) e
1u 3A VLa (K +1) A
(1 31) b -
2a
+ 1) 30-2
where A = In 4(K+1))
It is also worth mentioning that the existing high-probabilltyy complexities for Adam/AdaGrad-Iypt (without clipping) methods either have inverse power dependence on 8 (Wang et al., 2023) or have polylogarithmic dependence 8 but rely the assumption that the noise is sub- Gaussian/bounded (Li & Orabona, 2020; Liu et al., 2023; Li et al., 2023), which is stronger than bounded variance assumption. Under the additional assumption that the em- prical risk is bounded and the (non-central) a-th moment of the stochastic gradient are bounded and the empirical risk is smooth, which are stronger than Assumptions 1.4, 1.1 and 1.2 respectively. Li & Liu (2023) derive similar bound to (12) for Clip- Soep--dGGrrdNooooo We emphasize that boundedness and smoothness of the empirical risk imply the boundedness and smoothness of all Se (x) in the worst case (c.g., when the distribution D is discrete). Therefore, in the worst case, these assumptions imply the boundedness of fe(x) (in view of the second part of (3) for function fe), meaning that the noise is bounded and, thus, sub-Gaussian. In this case, clipping is not needed for AdaGrad to achieve good high-probability convergence guarantees as shown by Li & Orabona (2020); Liu et al. (2023). Our Theo- rem 3.3 extends this result to the momentum version of Clip- Hitp-AdGrrad-Nort under less restrictive assumptions (not implying ubb-Gausianiity of the noise) and gives the first boobbbbrbbbbltty convergence bounds for Clip-Adam with polylogarithmic dependence on 8.
A = -
(L
Then, to guarantee K+1 t0 [ S & with proba- bility at least 1-6 & Suli---daD//Cii-------- M-AddGradD-Nooooo Norm requires the following number of iterations/oracle calls:
E
LA
20-1
oVLA LA
20-2
δ max
3E)
(1 B1)
(LA)
20-9
(II)
(1 - 31)
Ja-2
2a-18
Moreover, with probability at least 1-8, all iterates {or }
stay in Q
Theorem 3.3 (Non-Convex Case: Methods without Delay). Let K > 0 and ā E (0, 1] and Assumptions 1.1, 1.2, 1.4
hold for Q = Rd. Assume that 31 E [0, 1). 32 = 1 K
(for Clip- Heip-Adam-Norme and
b-1
b-I M
θ min
L(K + 1) Sur I A VLo(K + - A
b_ 20'1
2n T 20
L 20
(K + 1) 3 A
20-2 21
==
where A In (t). Then, to VTxA(K+1I) 1) 3m
b-1 VT AT
Moreover, to the best of our knowledge, Theorems 3.1 and 3.2 are the first results showing high-probability con- vergence of Adam/AdaGrad--ypp methods with polyloga- rithmic dependence on the confidence level in the case of the heavy-tailed noise without extra assumptions such as Assumption 1.4. We also show that the iterates of Clip- do not leave set Q with high probability, where Q = BBn(x*) in the convex case and VA Q = f E Rd By E (2(2 : ||. all < 20VL with y = (v E T (() s f. + 24} in the non-convex case. Further details and proofs are deferred to Appendix C.
[=x))] < & with probability at least - ô Clip-AdamCClip-M -araaaClp AdaGrad- Norm requires the following number of iterations/oracle calls:
guarantee R4I Σ
LM
Zu
av LM
2a-2
max
(1 B1)
E
0
2n Ia
(LM)
(12)
Discussion of the results. Theorems 3.2, and 3.3 pro- vide high-probabilitg complexities for Clip-Ad M-AdaGrad(D)-Nomm with polylogarithmic dependence
Assumption 1.4 in Theorem 3.3. As we explain above, Assumption 1.4 is weaker than the one used in Li & Liu
7

---

Clipping Improves Adam-Norm and AdaGrad-Norm
(2023). It is worth mentioning that Assumption 1.4 is rela- tively restrictive. Nevertheless, we need this assumption in our proof to overcome the difficulty of analyzing stochas- tic methods with correlated stepsizes, i.e., to handle the fact that 9t and by are dependent. The existing approaches typically use boundedness of the variance and the norm of
ing the necessity of gradient clipping in AdaGrad/Adam for high-probability convergence.
4. Numerical Experiments
In this section, we illustrate numerically that clipping indeed helps AdaGrad and Adam to achieve better high-probabilityy convergence. Our code available on- line: https://gi com/ comm/yarostt warrrollakkikkkkni cLipped-AdaGrad-anee Adam.
the gradient (see Lemma 5.1 in Défossez et al. (2022)) or assume that the noise is sub- Gaussansiinn (Li & Liu, 2023) to tackle this issue. In the heavy-tailed noise regime, these as- sumptions do not hold. Therefore, we use Assumption 1.4. More precisely, to decouple by and 9: in the analysis, we multiply inequality (68) by by However, it eventually leads to the non-trivial weighted sum of function values EL be be-1) P Pt (f(x)) - f-) in inequality (72). To es- timate this sum, we apply Assumption 1.4. We are not aware of the alternative ways of analyzing versions of Ada- Grad/Adam or closely related methods in the heavy-tailed noise regime.
Quadratic problem. In the first experiment, test the performance of different versions of AdaGrad with and without clipping on the 1-dimensional quadratic objective
with additive heavy-tailed noise: f(x) = = =²/2, fe())) = x + 5. where the noise & has probability density function
p(t) = + In this case, Assumption 1.1 is satisfied with any a E (1, and the a-th moment is unbounded for a 2 1.5. Moreover, the function is strongly convex and L-smooth with L = 1. We choose 2g = 2. bo = 3 (for the versions of AdaGrad with delay). b-1 = 3 (for other cases), À = 1/2 for the methods with clipping, and choose y from (1, 1/1e, 1/128). Each method was run 100 times with different seeds.
3
Analysis of coordinate-wise methods. In Appendix C.5, derive new results for Clip-AdamD and Clip-M- AdaGradD in the non-convex case, i.e., for the methods with coordinate-wise scaling. The analysis and the derived bounds are similar to the ones from Theorem 3.2. The new bounds explicitly depend on the dimension of the prob- lem, which is standard for the methods with coordinate- wise scaling. In particular, under the coordinate-wi wise ver- sion of Assumption 1.1 (see Assumption C.I.), we show that there exists a proper choice of y and À ensuring that K+I Ex= |l V (+xx)) I" < with probability at least 1 - 5 after the following number of iterations/oracle calls of Clip- AdamD/CCip-M-AAaGrradD.
The results are given in Figure 1, where for each method, we show its trajectory in terms of the squared distance to the solution for y = 1 and y = 1/16 (the results for y = 1/128 are given in Appendix D.I). Solid lines correspond to the median value of the squared distances, and the error bands cover the areas from the 10-th 90-th percentiles of (I, "tt==="² ) These results show that clipped versions of Ada- Grad (with and without delay) achieve better convergence with higher probability than their non-clipped counterparts. Moreover, versions with clipping exhibit similar behavior to each other. That is, the error bands for Clip-AdaGraddD) are lower than for AdaGrad(D) (note that the vertical axis is shown in the logarithmic scale making the error bands for Clip-AdaGrad(D) look wider than for (D)Grad()), while they are not). In general, the observed results for Ada- Grad-type methods are perfectly aligned with the theory developed in this paper. We provide the results for Adam with and without clipping/delay in Appendix D.I.
VaLA
max
3
30-2
VLA
Ei 0
2-
(1 - B1) Vd
1o-2
1
Ei=1 ofa
d
(TA))
(1 - {1) T
ALBERT Base v2 fine-tuning. In the second part of our experiments, we consider fine-tuning the pre-trained AL- BERT Base v2 model (Lan et al., 2019) on CoLa and RTE datasets (Wang et al., 2018). Since Adam-based algorithms are the methods of choice for NLP tasks, in the main part of the paper, we focus on Adam and its clipped versions Clip-Adam and Clip-AdamD - and provide additional ex- periments with AdaGrad -ased methods in Appendix D.2. We took a pre-trained model from the Hugging Face library. Then, the model was fine-tuned following the methodology
Discussion of Kunstner al. (2023). Kunstner et al. (2023) show that Adam outperforms SGD even in full-batch settings, hinting that the success of Adam is not only related to its better interaction with the heavy-tailed noise. Our fo- cus is on high-probability convergence of AdaGrad/Adam- based methods, showing that without clipping, they have poor high- probbbbibby complexities, similar to SGD. Thus, our results complement Kunstner et al. (2023) by highlight-
8

---

Clipping Improves Adam-Norm and AdaGrad-Norn
6099 us Cip Sladmd
AdaG as Clpes5a6nd)
6do6 us Slp-tiGdd
AdaiestD vs dip ddaGraDD
Adtiend Sccesse
Number of Eltraabone
Mumber of Etarationn
Namber of llaraation
Mamber of betallams
Figure 1: Performance of different versions of AdaGrad (with and without clipping/delay) with stepsizes 7 = (two left plots) and y = 1/18 (two right plots) on the quadratic problem.
Cola, Adam vs Cllp-Adam
RTE. Adam Clip-Adam
0475
Als-Adam
Adam
0.73
ClioAdam
Adam
0100
0,355
Vel 1055
0.500
8.500
0.115
0.0
0.00
200
200
300
400
300
10
200
330
200
250
300
Number of shops
Number of stops
Figure 2: Validation loss for ALBERT Base v2 fine-tuning task on the CoLa and RTE datasets.
suggested by Moshach et al. (2020). For the methods with clipping, we used the same batchsize and stepsize as for Adam and tuned the clipping level for the two types of clip- ping In the main text, we show the results with layer-wise clipping. Further details and additional results are deferred to Appendix D.2.
computed for the standard normal distribution (PMRN and PeRV) and show Pmu Pmxx/pmax and Pet PCR/PERX on the plots. The histograms are provided in Figure 6 (see Appendix D.2). They show that the noise distribution has much heavier tails for CoLa than for RTE.
Then, similarly to the experiments with the quadratic prob- lem, we ran the methods 100 times, and for each step, we computed the median value of the validation loss and its 5-th and 95-th percentiles. The results presented in Fig- ure 2, where the solid lines correspond to the medians and the error bands cover the areas between 5-th and 95-th per- centiles. As expected, Adam exhibits poor high- shgb-probabblityy convergence on the CoLa datasets where the noise is sig- nificantly heavy-tailed, and Clip-Adam shows much better performance: the area between 5-th and 95-th percentiles is relatively narrow for Clip-Adam. In contrast, for the RTE dataset, Clip-Adam performs similarly to Adam. This is also expected since the noise is much less heavy for RTE, as Figure 6 shows. Taking into account the negative results from Section 2, and the upper bounds from Scction 3, we conclude that these numerical results are well-aligned with the theory developed in the paper.
Before comparing the methods, we ran Adam and checked how heavy-tailed the noise in the stochastic gradients is along the trajectory. In particular, for both tasks, we se- lected 4 iterates corresponding to the starting point, points generated after se 1/3 and z 2/3 of all steps, and the last iterate. Then, for each of these points, we sampled size-16 (for CoLa) and size-8 (for RTE) mini-batched es- timator (x(( of the gradient 1000 times, saved the re- sulting norms of the differences ||V (x)) - [x())), and plotted their histogram, i.c., we plotted the histograms of the noise norm. Moreover, we also measure the heavy- tailedness of the noise following the approach from (Gor- bunov et al., 2022): we compute two metrics PmR = fe (z) - V (=)])), which quantifies "mild" heavy tails, and PeR by Jordanova & Petkova (2017), which quantifies "ex- treme" heavy tails, where fe
(((())((()) - (=))l)) introduced
In Appendix D.3, we also provide additional experiments with the fine-tuning the 355M parameter RoBERTa Large model (Liu et al., 2019) on the two GLUE (Wang et al., 2018) datasets: QNLI (1 (116k question-answer pairs) and CoLa (10.7k linguistic acceptability examples). Similarly to the previous results, the elipped variants consistently out- perform their unclipped counterparts for the larger model.
(e) - v((x)] > Q3 + a{Q3= - Q1) and Q2 is the i-th quartile of [[V Vf(=)) To illustrate the heavy-tailedness clearly, we divide these metrics to the ones
'We did not consider the global/norm clipping (the considered in theory), since typically coordinate-wise or layer-wise clipping work better anc-ttning, see (Lv et al., 2024).
9

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Acknowledgements
Computational Linguisties: Human Language Technolo- gies, Volume I (Long and Short Papers), pp. 4171-4186, 2019.
The work of Savelii Chezhegov and Aleksandr Beznosikov on the final version of this paper was supported by the Min- istry Economic Development of the Russian Federation (agreement with MIPT No. 139- 15-2052000-,,,, dated June 20, 2025, IGK 100000C313925P4BB000
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Dzhaparidze, K. and Van Zanten, J. On bernstein-type inequalities for martingales. Stochastic processes and their applications, 93(1):009-177, 2001.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Faw, M., Tziotis, I., Caramanis, C.,, Mokhtari, A., Shakkot- tai, S., and Ward, R. The power of adaptivity in sgd: Self- tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pp. 313- 355. PMLR, 2022.
References
Abdukhakimov, F., Xiang, C., Kamzolov, D., Gower, R., and Takáč, M. Sania: Polyak-type optimization frame- work leads to scale invariant stochastic algorithms. arXiv preprint arXiv:2312. 17369, 2023.
Faw, M., Rout, L.,, Caramanis, C., and Shakkottai, S. Be- yond uniform smoothness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference on Learning Theory, pp. 89-160. P-LLR..0.MM......M 2023.
Abdukhakimov, F., Xiang, C., Kamzolov. D., and Takáč, M. Stochastic gradient descent with preconditioned polyak step-size. Computational Mathematics and Mathematical Physics, 64(4):621-634 2024.
Freedman, D. A. al. On tail probabilities for martingales. the Annals of Probability, 3(1):100-118, 1975.
Ghadimi, S. and Lan, G. Optimal stochastic approximation algorithms for strongly convex stochastic composite op- timization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4): (4(4):1469-142, 2012.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth- methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-233 2013.
Bennett, G. Probability inequalities for the sum of indepen- dent random variables. Journal of the American Statisti- cal Association, 57(297):33 45, 1962.
Goodfellow, I., Bengio, Y., and Courville, A. Deep learning. MIT press, 2016.
Chen, X.,
Liu, S., Sun, R., and Hong, M. On the conver- gence of class of adam-type algorithms for non-convex optimization. arXiv preprint arXiv: 17X.v:880.00294/ 2018.
Gorbunov, E., Danilova, M., and Gasnikov, A. Stochas- tic optimization with rtilld noise via accelerated gradient clipping. Advances in Neural Information Pro-
Cutkosky, A. and Mehta, H. High-probability bounds for non-convex stochastic optimization with heavy tails. Ad- vances in Neural Information Processing Systems, 34: 4883 4895,489,2222 2021.
cessing Systems, 33:15042-1550 2020.
Gorbunov, E., Danilova, M., Shibaev, I., Dvurechensky, P., and Gasnikov, A. Near-optimal high probability complex- ity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.0540 2021.
Davis, D., Drusvyatskiy, D., Xiao, L., and Zhang. J. From low probability to high confidence in stochastic convex optimization. The Journal of Machine Learning Research, 22(1):2237-2274, 2021.
Gorbunov, E.,, Danilova, M., Dobre, D., Dvurechenskii, P., Gasnikov, A., and Gidel, G. Clipped stochastic meth- ods for variational inequalities with heavy-tailed noise. Advances in Neural Information Processing Systems, 35: 2022.
Défossez, A., Bottou, L., Bach, F., and Usunier, N. A simple convergence proof of adam and adagrad. Transactions on Machine Learning Research, 2022.
Devlin, J., Chang, M.-W., Lec, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for
Gorbunov, E., Sadiev, A., Danilova, M., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. High-probability convergence for composite and
10

---

Clipping Improves Adam-Norm and AdaGrad-Norm
distributed stochastic minimization and variational in- equalities with heavy-tailed noise. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scar- lett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learn- ing, volume 235 of Proceedings of Machine Learn- ing Research, pp. 15951-16070. PMLR, 21-27 Jul 2024. :ttp:tt:: pttp///eereeeeeccceeeeeepcec.cse mwr. wali.ppees press/ 2235/gorbunov240 hhmml..
Li, and Liu, Y. High probability analysis for non-convex stochastic optimization with clipping. In ECA/ 2023, pp- 1406-1413. IOS Press, 2023.
Li, S., Swartworth, W. Takáč, M., Needell, D., and Gower, R. M. Sp2: A second order stochastic polyak method. ICLR 2023, 2022.
Li, X. and Orabona, F. sis of adaptive sgd with momentum. arXiv preprint vrXiv2200.114244 2020.
high probability analy-
Harvey, N. J., Liaw; C., and Randhawa, S. Simple and opti- mal high-probabilityy bounds for strongly-convex stochas- tic gradient descent. arXiv preprint 1rXiv:1909000844 2019.
Li, Y., Yuan, R., Fan, C.,, Schmidt, M., Horváth, S., Gower, R. M., and Takáč, M. Enhancing policy gra- dient with the polyak step-size adaption. arXiv preprint arXiv: 2404.445440555 2024.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pultern recognition, pp. 770-778, 2016.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyrr, L.., and Stoyanov, V. Roberta: A robustly optimized bert pretraining approach, 2019, URL https: / arxiv. org/ aaaaab///a 1tt.//97.111111
Huber, J. Robust estimation of location parameter. In Breakthroughs in statistics: Methodology and distribu- fion, pp. 492-518. Springer, 1992.
Liu, Z., Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. High probability convergence of stochastic gradient methods. In International Conference on Machine Learn- ing, pp. 21884-21914, PMLR, 2023.
Jakovetić, D., Bajović, D., Sahu, A. K., Kar, S., Milošević, N., and Stamenković, D. Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise, SIAM Journal on Opti- mization, 33(2):394 42..3944443..00 2023.
Loizou, N., Vaswani, S., Laradji, I. H., and Lacoste-Julien, S. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pp. 1306-1314. PMLR, 2021.
Jordanova, P. K. and Petkova, M. P. Measuring heavy- tailedness of distributions. In AIP Conference Proceed- ings, volume 1910. AIP Publishing, 2017.
Lv, K., Yang, Y., Liu, T., Gao, Q., Guo, Q. and Qiu, X. Full parameter fine-tum tie-ttnnng for large language models with limited resources, 2024. URL https: //tp:///aaiivvia abs/ 206.. 09782.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6998 2014.
Kornilov, N., Dorn, Y., Lobanov, A., Kutuzov, N., Shibaev, I., Gorbunov, E., Gasnikov, A., and Nazin, A. Zeroth- order median clipping for non-smooth convex optimiza- tion problems with heavy-tailed symmetric noise. arXiv preprint ar arXiv:2402.024611 2024.
Mosbach, M., Andriushchenko, M., and Klakow, D. On the stability of fine-tuning bert: Misconceptions, explanations, and strong baselines. arXiv preprint MXXiv:2006.048844 2020.
Moskvoretskii, V., Panchenko, A., and Nikishina, I. Are large language models good at lexical semantics? a case of taxonomy learning. Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pp. 1498-1510, 2024a.
Kunstner, F., Chen, J., Lavington, J. W. and Schmidt, M. Noise is not the main factor behind the gap between sgd and adam transformers, but sign descent might be. In The Eleventh International Conference on Learning Representations, 2023.
Lan, Z., Chen, M., Goodman, S., Gimpel, K., Sharma, P., and Soricut, R. Albert: A lite bert for self-supervised learning of language representations. arXiv preprint arXiv: 1909v 11942, 2019.
Moskvoretskii, V., Tupitsa, N., Biemann, C., Horváth, S., Gorbunov, E., and Nikishina, I. Low-resource machine translation through the lens of personalized federated learning. In Al-Onaizan, Y., Bansal, M., and Chen, Y.-N. (eds.), Findings of the Association for Computational Lin- guistics: EMNLP 2024, pp. 1806-8825, Miami, Florida, USA, November 2024b. Association for Computational Linguistics. doi: 10.18653/v 1/11655/11/2024 htt.2//.innnnnnseeeeee findings-emmllp
Li, H., Rakhlin, A., and Jadbabaie, A. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2023.

---

Clipping Improves Adam-Norm and AdaGrad-Norm
514. URL https://accllaaaaee httts//lly.aaaoooooooooooooooo.. wwwphhollooo..r/22222... Eindings-emnip.55
Reddi, S. J., Kale, S., and Kumar, S. On the convergence of adam and beyond. arXiv preprint arXiv:/904.0999 1904.09237, 2019.
Nazin, A. V., Nemirovsky, A. S., Tsybakov, A. B., and Judit- sky, A. B. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607-1627, 2019.
Robbins, H. and Monro, S. A stochastic approximation method. The annals of mathematical statistics, pp. 400- 407, 1951.
Nemirovski, A. S., Juditsky, A. B., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4): 1574-1609, 2009.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z.., Karpathy, A., Khosla, A., Bern- stein, M., al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115: 211-252, 2015.
Nemirovskij. A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983.
Sadiev, A., Danilova, M., Gorbunov, E., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 29563-29648. PMLR, 23-29 Jul 2023.
Nesterov, Y. E. A method of solving a convex program- ming problem with convergence rate O(1/k²). In Dok- lady Akademii Nauk, volume 269, pp. Academy of Sciences, 1983.
Russian
Nguyen, T. D., Ene, A., and Nguyen, H. L. Improved con- vergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXiv:2304.011 2023.
Schaipp. F., Ohana, R., Eickenberg, M., Defazio, A., and Gower, R. M. Momo: Momentum models for adaptive learning rates. arXiv preprint arXiv:2305.00588 2023.
Nikishina, I., Vakhitova, A., Tutubalina, E., and Panchenko, A. Cross-modal contextualized hidden state projection method for expanding of taxonomic graphs. In Proceed- ings of Tex:Graphs- 16: Graph-band baseed Methods for Natural Language Processing, pp. 11-24, 2022.
Shalev-Shwartz, S. and Ben-David, S. Understanding mu- chine learning: From theory to algorithms. Cambridge university press, 2014.
Pan, Y. and Li, Y. Toward understanding why adam con- verges faster than sgd for transformers. arXiv preprint 2XXi:23306.00204 2023.
Shi, Z.,, Sadiev, A., Loizou, N., Richtárik, P., and Takáč, M. Ai-sarah: Adaptive and implicit stochastic recursive gradient methods. Trunsactions on Machine Learning Research, 2023.
Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1311 Pmlr, 2013.
Streeter, M. and McMahan, H. B. Less regret via online conditioning. arXiv preprint /002: 4862, 2010.
Patel, V. and Berahas, A. S. Gradient descent in the absence of global lipschitz continuity of the gradients. arXiv preprint arXiv:2210.02411 2022.
Takáč, M., Bijral, A., Richtárik, P., and Srebro, N. Mini- batch primal and dual methods for svms. In In 30th International Conference on Machine Learning, ICML 2013, 2013.
Patel, V., Zhang, S., and Tian, B. Global convergence and stability of stochastic gradient descent. Advances in Neural Information Processing Systems, 35:36014- 36025, 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.., Gomez, A. N., Kaiser, L.,, and Polosukhin, At- tention is all you need, Advances neural information processing systems, 30, 2017.
Polyak, B. Some methods of speeding up the convergence of iteration methods. USSR Computational Mahhmatics and Mathematical Physics, 4(5):1-17, 1964.
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, R. Glue: A multi-task benchmark and anal- ysis platform for natural language understanding. arXiv preprint arXiv: 100.:::880047444 2018.
Puchkin, N., Gorbunov, E., Kutuzov, N., and Gasnikov, A. Breaking the haave-tailed noise barrier in stochastic optimization problems. In International Conference on Artificial Intelligence and Statistics, pp. 856-8666 864, PMLR, 2024.
Wang, B., Zhang. H., Ma, Z., and Chen, W. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. The Thirty Sixth Annual
12

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Conference on Learning Theory, pp. 161-190. PMLR, 2023.
Wang, B., Zhang. Y. Zhang, H., Meng, Q., Sun, R., Ma, Z.-M., Liu, T.-Y., Luo, Z. and Chen, W. Provable adaptivity of adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2960-2969, 2024.
Ward, R., Wu, X., and Bottou, L. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Ma- chine Learning Research, 21(219):1-30, 2020.
Yang, C. and Ma, X. Improving stability of fine-tuning pretrained language models via component-wise gradient norm clipping, 2022. URL https://arxiie org/ abs/22100 10325.
You, Y., Li, J., Reddi, S., Hseu, J., Kumar, S., Bhojanapalli,, S., Song, X., Demmel, J., Keutzer, K., and Hsieh, C.-J. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: /904iv9904.0000 1et..090422022 2019.
Zhang, J. Karimireddy, P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15399 153933, 2020.
Zhang. Y., Chen, C., Shi, N., Sun, R., and Luo, Z.-Q. Adam can converge without any modification on update rules. Advances in neural information processing systems, 35: 28386-28399, 2022.
Zhou, P., Feng, J., Ma, C., Xiong, C., Hoi. S. C. H., et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems, 33:21 18:21285-22 185-212296 2020.
Zou, F., Shen, L., Jie, Z., Sun, J., and Liu, W. Weighted adagrad with unified momentum. arXiv preprint arXiv: 03408, 2, 2018.
13

---

Clipping Improves Adam-Norm and AdaGrad-Norm
A. Technical Details and Auxiliary Results
Additional notation.
For the ease of exposition, we introduce the following notation for the proofs:
9t clip (Vie. (z))
0, 9t vf(z)).
0r = Jt Eg, Lee]
6 Eg, [g Vf(xe))
R. 22 x= 11
A, f(())) fa.
Auxiliary results. We also use the following standard results. Proposition A.1 (Young's inequality.). For any 2, y E æ2 and p >> the following inequality holds:
> + v/1 v (1 + p) 1| + 1 11v12
In particular, for p
| y/1 s 2|||=11 + 22
Lemma A.2 (Lemma B.2 from (Défossez et al., 2022)). Let 0 S a S b be some non-negative integers and 0 S < 1. Then,
q v (1 q)2
q
k=a
Lemma A.3 (Lemma from (Streeter & McMahan, 2010)), Let { and e be non-negative reals. Then,
0
2
c+
a
k
Di=1
The following lemma by Sadiev et al. (2023) helps estimate bias and variance of the clipped stochastic gradient satisfying Assumption 1.1.
Lemma A.4 (Lemma 5.1 from (Sadiev et al., 2023)). Let X be a random vector from Rdd and X = (elip(X,\), Then,
x I 2X. Moreover, if for some a 2 0 and a E (1,2) we have E [X] = x E Rd E [|| - x 2010 S σ", and
|z>|| < 2. then
x
Aa-I
2)
E
x
< 1812 2-a 000
x E
[
x 181 8
Finally, in the analysis of Clip-RAdaGradD, we face the sums cautiinaae-diiffreee sequences. One of the tools that we handle them Bernstein's 's inequality (Bennett, 1962; Dzhaparidze & Van Zanten, 2001; Freedman et al., 1975).
Lemma A.5 (Bernstein's 's inequality). Let the sequence of random variables {Xi)izı form martingale difference sequence, i.e. [Xx, X,-I,..., X1] = for all 2 1. Assume that conditional variances of = E [X? Xi-1I..., X1] exist and are bounded and also assume that there exists deterministic constant >
O such that X,| I c almost surely for all 2 L.
Then for all b 0, and n > 1
oo < G ) 1=1
6²
P
X1
> b and
2exp
2G +
20
3
14

---

Clipping Improves Adam-Norm and AdaGrad-Norm
B. Missing Proofs from Section 2
this section, we provide further details regarding Theorem 2.1 giving a negative result about high-probability convergence of Adam/M-AdaGrad and AdamD/M-AdaGrado For all methods, we use the 1-dimensional Huber loss function:
f(x) = 2
if | S V,
-1))
otherwise.
This function is convex and T-smooth with == 1. However, the construction of noises and proofs are different for Adam, M-AdaGrad, AdamD, and M-AdaGradD. Therefore, we provide the negative results for these methods separately in the following subsections. We emphasize that the constructed examples are 1-dimensional, meaning that they hold for coordinate-wee and norm-versions of the considered methods.
B.1. Failure of M-AdaGrad
We start with the following lemma giving a closed-form expression for the iterates of deterministic M-AdaGrad applied to (8).
Lemma B.1. Suppose that the starting point To is such that To > 0. If after T iterations of deterministic M-AdaGrad with initial momentum m- 2 0 we have |xa| > and xa > 0 for all t = 1.T I, then
T-1
3 + +8
2r = 2o
TV
12 + (1 1)v2
Proof. Since |xa| > y and 2; is positive, the gradient at 2, is equal to v. Hence, by substituting the gradient into the algorithm, we get the final result.
The above lemma relies on condition that [x, e and n, > for = 1,T 1. For any 7, 7,b-1 and T this condition can be achieved if choose sufficiently small v.
Next, estimate the interval where or lies.
Lemma B.2. Let the conditions of Lemma B.l hold. Then, we have
+ +2 + - 2/00 + 1 1.
2 3o 7 v1 a0
v(1 B1)
S x0 (1 - B1) 22 (2V00 + - +1)
62
where ag G
Proof. From Lemma B.1 we have:
T-1
1 g + P1
214 m
FT To
V au + (t 1)
where ag
F Next, we bound the second term in the following way:
1I+1) 21
31)
dx (1 B1) (2 a. +T 2/ au + 1),
(13)
VI+
00
Go
"By default, m- = hut result this lemma holds non-zero m_1 2 as well. m-1 S 0, then one can select 2o <
15

---

Clipping Improves Adam-Norm and AdaGrad-Norm
T-1 +1
g
T-1
g++1
a0 + (t (t+1)
40 + (t +++1 1)
ag + (t+1)
1=0
1=0
1=0
Bo+T-1
T-1 dr Σ
g m1
vI + 4g
v1 + I
(m0
m-1
+ +2 00
2/00
(14)
vI ap
4 - 31)
Combining (13) and (14), we get the final result.
Corollary B.3. x0 -
18
and
x(1-B,)
To 1/
7m0 181 x1-
+ 4y
Io -
7m
v11
181
Voo +
T
+ +1,
472
then 2T > V for deterministic M-AdaGrad. Alternatively, |TT| S v implies that
2
20
2 31)
3m-1
+ 47
I0 - V -
2m
31)
Vuo +
T
+
422
Proof. First, let us show that
z0 - (1+2Vao ag T -2 +1
1-131
(15)
v(1 - (1)
equivalent to
F0 7
18 v(1
2
+ +47 40 1/ -
v(1-81)
7m 19
vag +I
T
+ 1.
4²2
Rewriting the (15), one can obtain
-1 u(1 - 31)
2YV 0g + < 00 V -
22yaa + +1.
Squaring both parts of the inequality above and expressing T, we get the alternative equivalent formula. Noticing that 1 VT and applying Lemma B.2, we get the final result. The second part of the corollary just a negation of the implication stated the first part of the corollary.
Theorem B.4. For any e, (0, 1), o > 0 such that 8/Ve6 2 8, there exists convex L-smooth minimization problem (8) and stochastic gradient oracle such that Assumption 1.1 holds with 2 and the iterates produced by M-AdaGrad after
K steps with stepsize y and starting point zg such that R 2o /2z 3y 2 3y3, + / 87 2 3, satisfy the following implication:
b Ven
oR
P (f(()) (x=))
K=n
(16)
7Ve8
i.e., the high-probabbllity complexity of M-AdaGrad has inverse-power dependence on 6.
Proof. Before we delve into the technical details, we provide an intuition behind the proof. We want to use the lower bound from Corollary B.3 and estimate the bound for the number of iterations required to achieve the desired optimization error with probability least 1 5. Moreover, we need set v depending on the accuracy & (v analytically clarified later).
16

---

for O, Clipping Improves Adam-Norm and AdaGrad-Norm
We denote the output of deterministic M-AdaGrad after / iterations as dt. Then, we introduce the noise in the stochastic gradient in the following way
where
E
with probability
2/7
(17)
0,
with probability 1 - A=
otherwise,
A,
with probability
+
2A7
where the formula for A is given later. The noise construction (17) implies that stochasticity appears only at the first iteration of M-AdaGrad, and then it only affects the stepsizes. Therefore.
T0
mu.
bo
where bo- = -022, + (v- - and mo = = (1- -1-381 -1)(v- - Moreover, 2 can be bounded in the following way
Tu + > > HD 7.
Also, let us define Ko as the number of iterations required to achieve at least e-accuracy. According to the stochasticity construction, we get that for &u * A the momentum my is non-negative:
(1 B1)(v +AA,, if -
mg
(1 Bi)u,
if Eo =
2
Therefore, choosing To in such way that zo - 27 - v be chosen
7m0 v11-3,)
2 0. we can apply Corollary B.3 and obtain that Ko can
mm 2 B.)
I1
a1
Ko
&2 be and S Let specify that this estimate depends the stochasticity the first iteration, i.e., the bound on the number of iterations is random. Consequently, if M-AdaGrad achieves e-solution after K steps, we should have K 2 Kg. Therefore, P(K' 2 Ko} 2 P(f(xx) f(x") I E) and we want to estimate K such that
with d1
P(Ko < K} 2 1 6.
Bounding the left-hand side,
P(K, < K} = P(Ka < Kl50 = A)P(E0 = A} + PPKKo & KlE0 + A)P(Eo + A}
21 1/
3, (1-
Vai
P
K Eo # A Pito + A} PPEo A}
20
2
w(1
3
31)
< P
S K
Eo +
PfEo # A) + A).
7
17

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Denoting R x0 derive
2 and assuming that for to A we have R
2rma8 v(1
which implies R
2m088 m11-81)
2 2
I0
2
7m0 m(1 81
Vai
P(Ko - K} <
I K
Eo F A
PiEo * A} + = AA
?
R
< P
27 va S K
50 +
P(Eo + AA} P(5o- = A}
P
b2 + (v -060)² <
422
50 + A 2 P(5o * A} + P(5o = A}
R²
<P (v oEo)² <
E0 + A)
Pl50
A} + PfED A}.
R22
where in the third row, we substitute the analytical form of a1, and in the fourth row, we used K 2 1 get
Therefore, we
4py
2k vy R
P(K, < < P lo5u -11
Eo A
PiEo A) + P(Eo A}
2KvY R
S
1oll -
+
Eo # A
Pien * A} P = A}.
As a result, P(Ko < K} 21 1 - 8 implies
P f a [ol s
2KrY
+ + # A Pieo # A] + P(E- = A} 2 1 1- 6.
R
2K 2v satisfies the condition on random variable. Hence, we have
Consequently, choosing A
the first probability in the inequality above is equal to T². since the only Eo- 0
1
24 21-8. 8.
Consequently,
0
S 25.
A
2K 1
+ 2u
Therefore,
R 6
Ro
K
1
2
20
28
8%
Veo
since o/VE8 and 2s. remains to find the conditions on zg and y ensuring that R > sufficient to choose in the following way:
2ymo x(1-1.)
for Eo + A. It
27(2 + + =2y 3+ R
2K>
B1.
V
R
Solving the quadratic inequality in R, we get 2 3y31 + 29 + inequality is satisfied, we conclude the proof.
Choosing zg such that the previous
B.2. Failure of M-AdaGradD
Similarly to the case of M-AdaGrad, we start by obtaining the analytic form of iterations of the deterministic M D-AdGGradD in the following lemma.
18

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Lemma B.5. Suppose that starling point wo such that xg O. If Jafter T iterations of deterministic M-AdaGradD have [re] > and Tt for all 1,7 with, then
T-1
2T TO
TV
L0
Proof. The proof is similar to the proof of Lemma B.1. Since Fı > the gradient point 2y is equal to Substituting that into the iteration of M-AdaGradD for each I, we finish the proof.
Now, let estimate the interval where IT lies. Lemma B.6. Let the conditions of Lemma B.5 hold. Then, we have
-0-7 7 (11 Vau +2200 40 + 1 2/00
S rT S 3o 7(1 -Bi (2v + +7- - -2Van)
b2
where dg
Proof. Let start with Lemma B.5:
T-1 87+1
FT 20
ag +t
12 Next, we bound the second term in the following way:
where ag 2.
To
(1
31)
-1-
+ +T -
(18)
0g
T-1
g1+1
1
T-1
1
Σ t=0
dx
+ 22 00 +T - 2 as.
(19)
0g
00
V
V0
Combining (18) and (19), have the final result.
Corollary B.7. xo 0, du 2 and
(wo -V + 4 V) 2,
4g2
then >> V for deterministic M-AdaGradD. Conversely, the case (xT| < implies that
(ro V ---7² + 47(20 v - -70ao + 2.
T
412
Proof. The proof is the same as for Corollary B.3.
Theorem B.S. For any E, ó E (0,1), o > O, there exists convex L-smooth minimization problem (8) and stochastic gradient
oracle such that Assumption I.I holds with a = 2 and the iterates produced by M-AdaGradD after K steps with stepsize
and starting point xo such that = To - /28 - 7 > 0, bo > and (1-6, (2-B.)oR//v R/e/88 2 16t2 satisfy the following implication
RR
(( - f(x)) 25 = k=
(20)
EVo
ie., the high-probability complexity of M-AdaGradD has inverse-power dependence on
19

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Proof. The overall idea of the proof resembles the for Theorem B.4 combine the lower bound for the number of iterations from Corollary B.7 with the specific choice of stochasticity. Nevertheless, prove this theorem, construct the adversarial noise in another way. More precisely, we consider the following stochastic gradient
V[((x) - -ak
where
0,
if < - |0 >
Age
with probability 244 with probability 1 - A4
Ex- =
(21)
O,
otherwise,
AE
with probability 24g
where d is the result of deterministic M-AdaGradD after K iterations and A max { 1, 2uhy (2-8))10 S. What is more,
E [Ex] 0 and EE [<]] by the construction. Therefore, the stochastic gradient satisfies the Assumption 1,1 with a
We want to prove that ((f(xx) f(²") > <} < 8. For d < 1, this implies that |&xl S with the contrary, the noise is equal to for each iteration by the construction, meaning that
-² Indeed, assuming 2
P ((((=k) f(x²)( > c) (f((k) f(x") =(=))
{ > v} = =1> 5.
As result, | S v and, applying Corollary B.7, we obtain
(ro - 7 47 ~ + 2. K
472
What is more, zς can be written as
mK-1 ãx + (1- Bi)Tok-11
KK = fK-1
bk-1
bk-1
Hence,
(ff(#k) - f(x'((()))))))))))) 2) = [1 2 v) 1/= =P{ 0K + (1- -B1)yoo
2
bk-1
BI)
B1)Tok-1
2 2 iK
PP
2 220
bk-
bk-
2vbx-1
1K-1| 2 (1 -1 31 }
If max {1, ( (1-10000
2vbx-1
1, then
22bxx
8
16- (1 -1 (1-32)m0 =1, 1,
which leads us to the contradiction. Therefore max
(1,
2vbx-1 }
2ubxc1 and (1-B1170'
[1-B1170 /
2vbK-1
2222 112b23
82 82P -((
f(x') 2 [K-11
(1 -1- 1-110
A K-1
where we used that Ax-1 max {1, bk-1 can be bounded as
20xx-1 } and the noise structure. Consequently, 5 (1-B1a9) f
22bx-113 V8 (1-B1)0
What is more,
bx / B3 Kv²
20

---

Clipping Improves Adam-Norm and AdaGrad-Norm
since the gradient of is uniformly bounded by v. Hence, we obtain
(0g V 7)
4(wo- v 7) Von
(20
7)2
K
472
47
4-2
2 (1 (x) 70
(b) + Kr2)6
Multiplying both sides by 16 Kv²), we get
(bg + Kv2)² 2 12 kK\) (1 - (5) 7))00
165
implying that
K 2 (1 - 3oR
(1 -1- 1
(1 - B-
b/
b/ 2
4v2 V8
8
16EV8
which finishes the proof.
B.3. Failure of Adam
Similarly to the of M-AdaGrad, we start by obtaining the analytical form of iterations of the deterministic Adam in the following lemma.
Lemma B.9. Suppose that the starting point ng is such that Fo > 0. If after T iterations of deterministic Adam with initial momentum m-1 2 0 we have |xe] and xı > foror all t 1,T 1, then
f m_ + (1-1
Σ
FT = 30
12 + (1- 32+1) u2
Proof. Since [aca| > v and 24 is positive, the gradient at d4 equal to v. Hence, by substituting the gradient into the algorithm, we get the final result.
The above lemma relies on the condition that |a, > v and xa > 0 for all = 1,T - 1. For any 7, b,b and T this condition can be achieved if we choose sufficiently small v.
Next, we estimate the interval where ør lies. Lemma B.10. Let the conditions of Lemma B.9 hold. Then, if B2 = 1 1/8, where K the total number of iterations of deterministic Adam, we have
(1
2.3m-1
+ 2Tv
< ET S (1 - -/1/TT
20 7
(1
b-1
60_, v22
Proof. From Lemma B.9 we have:
3 m_ + (1-
2T
+ 3 62, + (1 82+1) 222
Next, we bound the second term in the inequality above in the following way:
3 m- + (1-
8 m_
2Tv
23
2Tv
+
<
(22)
g b2, + (1 1)+))))² v2
62 + (1 02+1) 22
b_1
(1 - B1)b_1
b_1
t=0
P2
"By default, m- = hut the result this lemma holds for non-zero m_1 2 as well. m- S 0, then one can select 20 < 0.
21

---

Clipping Improves Adam-Norm and AdaGrad-Norm
3++ +
(1 --1v1
(23)
82 62 82 + (1 522 1/
602 v²
T=0
where the fact that with K 2 2 next inequalities hold
(1 -1- 2
1/x) k 2/41
05 3/ - 3/4 1
Combining (22) and (23), get the final result.
Corollary B.11. ro (1-81)6-1
2-8,m-11
0 and
ID
24,8 m- (I-B1]6. 11-B116-11
b-1
271
then 2T v for deterministic Adam with 32 1/K. Alternatively, | S v implies that
xo
(1-31 31-11
27.8 m
b-1
2
27v
Proof. Let note that
(
231m
2Iv
20 -7
(11- B1)b-1 (1-11)b-1
+
b-1
is equivalent to
TD V
(1-3,)6-1
2-
b-1
T
2yv
The second part of the corollary is just negation of the implication stated in the first part of the corollary.
Theorem B.12. For any E, 8 E (0, 1), > 0, there exists convex L-smooth minimization problem (8) and stochastic gradient oracle such that Assumption 1.1 holds with a = and the iterates produced by Adam after K steps with 32 = = 1-11/x and
stepsize y and starting point an such that R = Ho v 2 2- + 3:)VK satisfy the following implication:
( Vey
(1)
R
3/8
f(xx))
K=Ω
(24)
(VE
i.e., the high-probability complexity of Adam has inverse-power dependence 6.
Proof. The main idea is quite similar the proof of Theorem B.4. We introduce the noise in the stochastic gradient the following way
gk Vf(xx) a
where
0.
for l O,
A,
with probability 2,77
E
(25)
0,
with probability 1
otherwise,
Aa
A
with probability
22

---

Clipping Improves Adam-Norm and AdaGrad-Norm
where the formula for A is given later. The noise construction (25) implies that stochasticity appears only at the first iteration of Adam, and then it only affects the stepsizes. Therefore,
7 ma.
31 3o
bo
where bp- = V 32121 + (1 - (v) - x and mn (1 - 3:)(U - oQ). Denoting Ko as the number of iterations
required to achieve at least e-accuracy, choosing zo in such way that 20
2mm
[1 31-3,,b0 Jb0 > 0 and considering the
27,6 mo.
bo
case Eo j A to guarantee me 2 0, we apply Corollary B.11 and get that the algorithm needs to make at least
27,8 ma bo (ibo
31
Kg= =
24yv
iterations to reach e-aceuracy, where E o8r Let us specify that this estimate depends on the stochasticity at the first iteration, i.e., the bound on the number of iterations is random. Consequently, if Adam achieves e-solution after K steps, we should have K 2 Ko. Therefore, P(K 2 Ko} 2 ([f( f(=") S }} and we want to estimate K such that
P(Ko S K} 2 1 6.
Bounding the left-hand side,
P(Ko S K} = P(Ko S K|60 = AJP(Eo A} P(Ko S KIS0 + A)P(Co # A}
S P
11
(1 Bi /60
2y
bu
S Ko Eo + A
PfEo + A} PPfo- = A}
242
Fu - 7
mg bo
2ry9 mo (1- Jbo
bu
P
< K K|50 # A A
P(so + A} + P(G- = A}.
24V
Similar to the proof of Theorem B.4, denoting R= Fg v and assuming that for Eo F A we have R
1ymo bo (1
2ymo
bo
which implies R
2yma 6o 81)
1m28 b0
2yma
+
7mo by
we derive
bo
1 B1)
20
mn b0
V-
24 ma (1 91
bo
P(Ko S KJSP
SP
S 5o # A J P(5o # A} + PP(E- = A}
27yv
Rbo
< K| + A PfSo + A} + P150- = A}
< P
4yp
V B2b2, + (1 - (B22( - -o6o))) - 4yvK
R Eo # A Pf5o 1 # A} + PPE. = A}
P
V1 B2 10- -oEal S 4yuK
< P
5o 5o x A A PPEo + A)+ + PP = A}
R
4yK
< PP/
a 1ul - RV B2
+ + E0 # A PPEu * + +P) A],
where in the fourth row we used K > b R
Therefore, P(Ko- S K} > 1 - 5 implies
4y0
P folkol < RVI- 32
4rkK
+ v 6o + A plso + A} + = A} 2 1-8.
Aypk +2v Consequently, if we choose A = R-
then the only realization of the random variable &o for which the inequality in the first probability is satisfied is Eo = 0. Hence, we have
1
1
2 1
8.
242
23

---

Clipping Improves Adam-Norm and AdaGrad-Norm
As result, get
1
a
S 28.
A
4ypK
+2
Rv1-32
Therefore,
R
Ro
Ro
k/VI- = K 2 27
K2
22v/20
16
16>VE0
where we use 1 - 1= =1/K, o/VER 2 8 and v = 22. It remains to find the conditions on To and ?y ensuring that for Eo # A
R 41
2yma
2ymo
(_28) 2
+11 +1)
bo (1 B1)
60
bo
1 1- B1
Therefore, the above is equivalent to
29 1 31 +
Bi)u
(1- Bi) aA)
R 27
max
B222 + (1 - B2)u² V
B2b2 + (1 - B2) a)
To simplify the condition R, we derive upper bound for the maximum in the right-hand side:
11-31)D
31)x()
(1- (1-B1)y
(1 B1)(1 (v/ + toA
max
max
32b2 + +(1 B2)N²² V22b2 + (1 32) + to
(1(1 - V2)= V(1 - B2)(U oA)²
1 31
= =(1-
v1 Bg
Therefore, is sufficient to choose R satisfying
28
R 2 -1)
+1) = 27 +
1- 31
This concludes the proof.
B.4. Failure of AdamD
We follow the idea for previous proofs and start by obtaining the analytical form of iterations of the deterministic AdamD in the following lemma.
Lemma B.13. Suppose that the starting point zo is such that > O. If after T iterations of deterministic AdamD we have
[xa] > and Iz > 0 for all I. = 1,T 1, then
T-1
1 g
FT
To
TV
B56 (1 Bb) 22
Proof. Since |ate| and v, is positive, the gradient v, equal to Hence, by substituting the gradient into the algorithm, get the final result.
The above lemma relies on the condition that |ax| > and x, > 0 for all t -I For any bo and T this condition can be achieved if we choose sufficiently small v.
Next, we estimate the interval where ær lies. Lemma B.14. Let the conditions of Lemma B.13 hold. Then, if 32 = 1/K, where is the total number of iterations of deterministic AdamD, we have
2yT
7V (1 B.)
F0
< xT
S x0
bo
v D/ 222
24

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Proof. From Lemma B.13 have:
85+1
2T= 50
TV
12
(2)
v2
2
Next, we bound the second term in the inequality above in the following way:
T-1
8
2T
(26)
12 + (1 85) v2
b0
t=
1 B/+1
-1- B1)T
Σ
(27)
V B85 + (1- (1-1 v2
vbj bJ + v2
1=
where we use the fact that with K 2 2 next incqualities hold
2 8 = (1 1/x)* $ 2 (1 - 1/x)* 2 2/4,
0 < 3/4 2//4 1
Combining (26) and (27), get the final result.
Corollary B.15. If and
(To 1)66
T <
27vv
then PT > V for deterministic AdamD. Alternatively, |TT| S v implies that
T (0o 1)60
2
Proof. The proof is the same as for Corollary B.
Theorem B.16. For any e E (0, 1). a > O, there exists convex L-smooth minimization problem (8) and stochastic gradient oracle such that Assumption I.I holds with a = 2 and the iterates produced by AdamD after K steps with stepsize yy and starting point Ta such that ::= Zo v > 0, by > and BB/eSB 2 16b2 satisfy the following implication
RR 5V5
P(f(zk) 25
K K=
(28)
ie., the high-probabillty complexity AdamD has inverse-power dependence on 8.
Proof. The overall idea of the proof resembles the one for Theorem B.12 combine the lower bound for the number of iterations from Corollary 1. with the specific choice of stochasticity, Nevertheless, to prove this theorem, construct the adversarial noise in another way. More precisely, we consider the following stochastic gradient
Vf(xx) - oC
where
0,
if - |xxl v.
- Ak:
with probability
247 with probability 1 xy with probability
Ex-
(29)
0,
otherwise,
A
247
25

---

Clipping Improves Adam-Norm and AdaGrad-Norm
where ž is the result of deterministic AdamD after K iterations and A₁ = max {1,
(1-9:)70 What is more, E [&x] = 0
2ecb
and E [2]] I by the construction. Therefore, the stochastic gradient satisfies the Assumption 1.1 with = 2.
We want to prove that P(f(<k) - f(=*)= > 2} I 6. For 1, this implies that |&x| S v with e the contrary, the noise is equal for each iteration by the construction, meaning that
1 2.
Indeed, assuming
P (((K))) - [(x) > 2) = (f(x)) [(x)) > of [ > o) =1>1 6.
As result, |xx| < y and, applying Corollary B.15, we obtain
(T v/)b
K
27y
What is more, zx be written
7
mK-1 ãx + (1- B1)TokK11
KK = fK-1
bx-1
bx-
Hence,
0K + (1- - B1)
P(f(EK) - f(x")= 2 E) = = p|[k 20 IP
2
0k-1
2P {
(1 - 31)T0EK-1
P
2
22 2V
bk-1
{ 16x-11 2 (1 B11a0
2vbx-1
If max {1,
2vbg [1-B1h0 f then
2vbb --
5 12P( 28) 2 [K 16x-112
=
(1
31
which leads us to the contradiction. Therefore max {1, 2
2vbk-1 and (1-31170"
70
2vbx-1 8 82 (f(xk) f(x') 2 KK-1122 (1 31)11
}
(1 - 31)22002
A
42263
where used that Ax-1 max {I, bx- can be bounded as
200g (1-
1 and the noise structure. Consequently, 5
200g 1v8 (1-Bi)0
What is more,
bK- S V + v2
since the gradient of f is uniformly bounded by v. Hence, we obtain with bo 2 v
(1 (z) v)obo
(1 3I)(E0 v)o
(1 B₁ Ro
K
2
27v
4 4v D3 + 22288
8u2
168 18
which finishes the proof.
26

---

Clipping Improves Adam-Norm and AdaGrad-Norm
C. Missing Proofs from Section 3
In this section, we provide missing proofs for Algorithm 2 in the convex and non-convex cases. For each case, the proof consists of two parts descent lemma and main theorem. Moreover, for convenience of the proofs, we consider a reweighted version of Algorithm 2 summarized Algorithm 3, which has an additional parameter 1j > 0 appearing in the update rule for be. However, Algorithms and are equivalent: if divide by and y in Algorithm by v the method reduces to Algorithm but produces exactly the same points as before (given the same initialization and source of stochasticity, i.e., seed), since 7/6, remains unchanged.
Algorithm 3 Reweighted Alip-AddaCCii--AdaamD-- and Cilp:M//aaaGaaa//iiiMMAAAAAAaAa-
Input: Stepsize > 0, starting point 2o R initial constant b-1 > (for Adam and M-AdaGrad) or bu 0 (for AdamD and M-AdaGradD), momentum parameters $1, E [0. IJ. level of clipping À >> 0, reweighting parameter
1)> 0
1: Set m_ = 0
2: for = 0, 1... do
3: my mmm-1 + (1 (
4: if delay then
32b2 + (11 -2)l (V
for Clip-Adam-NNrm
5: b
nllclip (V.f,, (V
for Clip-M-AdaGrad-Nom
6: else
V B2b2 + 11 32)l (V A)I
for Clip-AdamD--Nrm
7: be+1
for Cip-MM-AGaGradD-ooom
end if
9: 1 Ht Eo m,
10:
end for
C.1. Technical Lemmas
Here we introduce technical lemmas for the future proofs.
Lemma C.1. Let the sequence {bi) is generated by Algorithm 3 in K iterations. Then, for every t, r: 22 we get
b, 2 Cmbry
where the constant on depends on the update rule for by. To be more precise, Cy for the Clip-M-AdaGGra/Clip--M AdaGradD-Norm, and C. for Clin-AAlam/Ciii-AcaDD-oor
Proof. The case For the Alip-Adaa/Clip--caaD---o we obtain that
is obvious since the sequence (br)t=0 is non-decreasing.
K
62 2 $
K
K
P3
where we, without loss of generality, assume that K 2 and apply the analytical form of B2 with fact that g(K)
(1 1 is increasing function. Taking the square root from both parts, we conclude the proof.
K)
Lemma C.2. Let the sequence {me is generated by Algorithm in K iterations. Then, for every St5 holds that
Σ
8 -Bi) Bi)gg.
m.
k=0
27

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Moreover, ||me]l? can be bounded in the following way:
|m, 2 (1-
(1-B)lll
Proof. The first part of the lemma is the direct consequence of update rule of momentum my. For the second part we need apply the Jensen's inequality as follows:
- (1 31)
8 8t-k(1 31)
Σ k=0
11
31+1
1
B
k=0
where we use the convexity of I|.11* and Σ x1 - 31) = 1 - 8++1 Multiplying both sides by (1 - (1-19t1)² we get the
k=0
final result.
C.2. Non-Convex Case: Methods with Delay
Lemma C.3 (Descent lemma). Let Assumption 1.2 hold
x: E Rd By Rd: f(v) S. 2A and | yll
VA 20vL Jr where (20) -J- Ao A. Then, after T iterations of Cllp-M-AaGrraDDDcii-aaaaa----o-a with bn
27 ) 1e E Q = 0,T, we have
T
C
T-1 Σ 1=
T-1
T-1 2.4 |0,011
[f(xx)]
A - AT
(nc 2A,) (Vf(z)) 0,) + Σ
+ Σ
2
t=
E=
t=
where C
T-1
Σ
1
g A
() cm ho
(k- - + 1)88-t and Cm is taken from Lemma C.I.
by
Proof.
We start with the L-smoothness of f:
L^²
((set)--(e - S (ZI()),, 24) + + - -- (V)())) mx)
||
(30)
b.
26
Using the update rule of Algorithm 3, obtain
(Vx()), m²) 31
B1) (V
31 (Vf(z;) - Vf 31 (V)(I=-)),
(1 81) (V)()))
S -31 (1)( + 31 Vf(zz) (f [m=1l
(1 - B1) (V (V)()))).))
S -31 (V]((x-1), m4-1 L | - 2x ||
(1 31) (V (z))..))
7B1L
-31 (V [x)-1),,
||
b
(1 B1) (V)(2).)))
where we use the Cauchy-Sch Schwarz inequality and L-smoothness of Applying the same idea for the 1, .,... and noting that m-1 = 0, get
g k
-11- (V.())) mc) 5 -(1 - Bi)
Σ 3
(1())...))) Ly
mm 112
(31)
k=0
k=U
28

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Therefore, substituting (31) into (30), have
((2441)-(aax) < (1 (1-31))
Ln
1-1
3(-k
In2
(Vf(I))
+
|m
1|2
mm
br
bt
bk
2b}
k=00
(1 B1)
L
t
k
B 81
(V gk)
+
m
122
bt
be
by
k=0
k=
Applying Lemma C.2 with 1 -1 1, can rewrite the inequality above follows:
(1 8117
L
8 k
f(z(+1) - f(x))= 5
(V)())),
gk)
+
bt
be
bk
k=0
j=0
(1 - B1)7 8 (x*)))) +
In²
(1-
(32)
b
bk
where we change the limits of summation. Now let us bound the second term. Applying Lemma C.I, we obtain that by 2 by (the constant Cm is taken from Lemma C.I). Consequently.
L
89-k by
2 11)11,11 s Ly²(1 - 311)
-31)
ΣΣ
89 11,,1
by
beb
j=0 Amm
j=0 kmj
L7 -1)
(t (t- j + 1)
(33)
bibibo
j=0
Thus, substituting (33) into (32), we get
(1 B-)
L B1)
f(4+1) -(441)- f After summing over 1. 1 O,...T
5
8 - (VI(=x)) +
Σ
8 k 1)
bt
Cn bebo
T 313
17 B1)
S
8 (V)(ss).9)) +
Σ
at - 1) 12)
bmb
k=
The main idea is to estimate the coefficients corresponding to (VI(zr) gr) and || These multiplicative factors be estimated as
1 711 31) g'-
(34)
be
for the scalar product and
31) (t - r 1)
(35)
b,b
for the squared norm, respectively, For (35) we can apply Lemma C.1 in the following way:
L Bi) (t r r 1)89
L Bi) (t r 1)8
L7 31) T-1
E (t-r+1))
byb
bb
27 b,bbo
T-1
Applying Lemma A.2, and using that
Σ
81- <
1- we get
1
T-1
LT2(1 B1)
LA2
A,
- r 1)s
(36)
Cy b,
2 b2,bbbb - B1)
29

---

Clipping Improves Adam-Norm and AdaGrad-Norm
for each & o,....r. r. Moreover, let us denote the factor corresponding the scalar product (34) as -7 C, can be bounded as follows:
31) -1-
31)
(1 (1- B1)
1
89-
by
by
Cmdu
Cmbo
where we apply Lemma C.I. Therefore, the descent lemma can be formulated as
T-1
((xT) f(xo) S
Σ
Acllgal?
Substituting the analytical form of gt. we have
f(xT) - f(xo) S
c. (V
Σ A Al 2
cc (VVI(o))) 0,) | (1x)))
At (110.11 12 + 2 (V (ax)), + +[{
+
Σ (,C,- - A.) A.) Σ (nc, Enc, 2A,) (VI(s,).
+ A.110.12.
Choosing 7 S (1-9119662. bo we get that yC, 2A, 2 0 since the boundary C. 2 1-4 21.
and (36) hold with A t. Therefore,
b,
using that 0, = 8.: + 8%. one can obtain
T-1
T-1
T A 10.12
f(zT) - f(zo) S Σ
(0c, A)IV
Σ (nC, 2A, (Vf((,))
T-1
Σ
(7C, - -0)1))(((
Σ (nC, - 2Ad (V.((x)).
1=0
T-1
24 (10))12 + -108811
+
- -A1) 1VS(E2)1
Σ
CC
- -A1) |0?!1
2
2
1=
1=
Σ 7 [(((2)) - Σ (7C 2A,) (Z:)),, 07) + Σ 2A,
|0
(7c 2
+ A1) |10911-
1=
t=
Using that 2C2 2 A,, and rearranging terms with A, fxx) Sn, we get the final result.
Remark C.4. is important to note that Q can be any non-empty subset of IRd as long as the iterates belong it. In this sense, the form of Q is not that important for the proof (a similar observation holds for Lemma C.6 in the convex case). Nevertheless, Q plays key role in the next part of the proof.
Theorem C.5. Let Assumptions 1.1 and 1.2 hold on Q = {ar eRd
VI Rd By E Rdd f(y) S. + 24 and || vll S 20VT. J
with f(x0) fx Ao S A. Then, after K + iterations of CiipMMAAGGCCaDDDCCiAAaaaaDDDaaoa with
(1 P2) m (K + +1) 3
Cm emvI I 3,35 b
7 < min
80 +1++1]
4 20 K + 1) 3o
4(K+1)
Cm (1 1 31)
bn
LT - -1)
11
(37)
20 3:
(K + 1)
26-1 4(K+1)
A
30

---

Clipping Improves Adam-Norm and AdaGrad-Norm
and
Bibbv + 2a- (1(++1)
A
(38)
10vl711 In
the bound
CC [f(x))] 22
k=0
holds with probability at least 1 - 6. In particular, when y equals the minimum from (37), the iterates produced by Hilp----AGGradDDDcii--ddDDDD---- satisfy
+ [+
LA In K+1
VLAg In K+1
20
(LA)
2a
In
2a
K+1
=0 max (1 (1-3))) +1) (1 B1) [K + 1) du
(1 81
3er
KK
+ 1)
22
with probability at least 1 1 5.
Proof. Our proof is induction-basee (similarly to the one for Clip-SGD by Sadiev et al. (2023)). We introduce probability event Eg as follows: inequalities
1-1
I(aa 2Ai) (VI(m)), Σ callo 1=0
Σ 1=0
2A
SA,
A. 22
hold simultancously Vi = 0, ,,..,.,.k.
kg k. We want to show that [x 21 K+I
Vk = 0, 1,... K+1. The case when k: = 0
is obvious. Now let us make an induction step: let the statement hold for some A: = - < K: PT 2 1- (T-1)6
K+1 It
remains prove that TP (ET) 2 1 and
T5 The event F implies that J. E {v E Rd f(v) < f VI = 0, 0.. R+I-
1r xr =
7 by
|
VA
V
C. bo
20 In 4(++))
20VL'
Hence, event ET implies {a=)T-o Q and we can apply Lemma C.3:
C [f(x))] < A. 2A) +
Σ
Σ
2A 10:91
1=0
t=0
1=0
1=0
VI = I,...., T and 11 = I.... T- - it implies that
[-]
t-1 +
[+)(2)))
Au A.
(1g 2A,) (Vf(zz),
24 18:11 22..
2
Taking into account that
Σ
C 2
2 for all t, we get that Er-1 implies
1=0
T-1
T-1
AT
5
Ao
Σ
(nC, 2Ad (Vf(z.))
2 1|
+ Σ
2A, |0/11
1=
Ao
Σ
(7C, 22,) (Vf(Iz),
>C 1cc110811 ?
T-1
+ T-1
2A, (1198112
Eç, 11000"1))
Σ EA 110211
1=
31

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Next, for vectors
[f((=)) 2VLLA
0,
otherwise
for all / = 0,1,.... T 1, we have that that with probability
|mrel - LVL
(39)
- -1 What is more, for all / = ......
-r-1 implies
À
[V S 2IL & IA
2
Thus, ET-1 implies fzz)) for t = 0, I..., - and
T-1 (nC, 2A,) (m,, 071)
T-1
T-1
AT < Do
Σ
Σ
Σ
2A, (108)12
Es 110/
24, Bg 111811
(40)
remains bound each term in (40) separately with high probability. Before we move on, also note that event ET-1 implies [x)]l s -- Therefore, one apply Lemma A.4 and get
10 S 2X,
(41)
0
|0:1 < Xa-I
(42)
Eg. |10)11 I 18) 2-2 0
(43)
Bound for @. The definition of 0N implies
Ee, (-C -2A,) (m, 077 0.
What is more, since C.
6m by get
(39)(41)
4YVLLA
A
-24)) (me, 07'1 S 7C, [| ||r|||
S
C.
bm
5
1(K+1)
Let us define oî EE, (nC) - -2Ar)² (n,, 021) Hence,
(39)
4-2
of s (nC, - 2A,)² 4LAB,, 110M11 <
Ee, 110011
(44)
22 by
Therefore, we can apply Bernstein's 's inequality (Lemma A.5) with G=
7 480
2(*+1)
P -
T-1
Σ (rC, 2A,) (Vf(2)). 07)
A
and
T-1
Σ
o
G
<
2exp
A
8
4
16 (2G + 40)
2(K + 1)
Thus, get
T-1
P either Σ
(nC, (4A) (Vf(x.),
A
or
Σ
o
> G
2
8
4
2(K + +1)
32

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Moreover, event Ey -1 implies
Σ
(43) 7272
x2 00 LAT (38) 72c -1)=-220000 20000 -VA5 (K + 1)
22-32
3n-2
LAT
m % oi
c
202 a vov/ VL 2-0 -2 2 4(K+1)
10
7
48 4(K+1) 8
Bound for @. For the second term, we get that Er-1 implies
(42) 4 o 2/TT
Σ
110.112
cm
Gm x 2 200
t=
20 2 2 La-aly2a
2a 2(K + +1
11(2 2)
In 22222 (4(K+1)
(38) 40h 200 K + 1)
2a-1
211 B1
a-
bn
pa-2
2 Aa-1
Cm
40. 202a-2 2 0 20 1 aa-1 (K + 1)
1o-1(K
20-2
In 2a-2
4(K+1)
b
2a-1
2a
(1 B1)a (1j)-1111 1000
Aa-1
Cm
(37) A
4
where in the last step, we apply the third condition on y from (37).
Bound for @. Similarly to ①, we have unbiased and bounded terms in the sum:
Eg, 2A. (1102)1 Eg, 11,111 [²]] o
and, since (36) from Lemma C.3 hold with k: = 0,
2A, (107)12 Reg 1001100113)
(41)
16LA2a2
A
154
2 bb(1
(1))
2n
4[++1]
47 In 4K+1j
=
(45)
4A4 (11011 2 Ec, -E,, 109:11))11)3) 27
Next, we define 67- = Egg,
For the introduced quantities, we have
(45) of
S clEs, [2AA (100 (10: Eg, 100))
2T
Eg. 10:11
(46)
c (1 - 31)
Therefore, we can apply Bernstein's 's inequality (Lemma A.5) with G
7
1n SKTTI
P Σ r
24. (10::122 - Be, 102111))
>
A
and
T-1
Σ 0
0
G
<
2exp
2
8
4
16 (2G +
2(K + +1)
6
Thus, we get
P either
Σ 1=0
2A, (10m112- Rgg -Fg 11x
S or Σ
T-1
07 > G
2 1- 5
2(K +1)
1=0
Moreover, event ET | implies
(46),41) 72L 22
- (38)
720, 63 2-a
(K "
2-a
+1) 3a
2 3a+t
0 LT
02
bB( B1)
20 202-a c (1 81) 8 VT.² -
1/
In 2 2-a 4 +1)
0=0
(37)
7Ac
7
480
1504 In 4(K+1)*
33

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Bound for @ For the last term, have that Er-1 implies
T-1
T-1
2
gg 10:1
Bgg 10:11
2 (/(
31)
367
- VA a
(K +
30-2 0 LT
Cr 10(1
(1)
202-a
31) VL
18 2-a 4(++1)
74
A
960 In
4(K+1)
4
Thus, taking into account the bounds above, the probability event Er-1 Ej n Eg implies that
A
AT S A
2A.
4
where
T-1
Ly²
T-1
7A2
F1
either
Σ
(VS(s)), 0N)
S
0
1= be
by
480 In
4[K+1]
1=0
T Σ
L7"
(10:11² - Ee, 100711)))
T-1
7A2
E2 = either
or
0
4(K+1)
1504
0=0
0
8
Therefore,
T8
P(Er)2P(E1-11) - P1--P(EE-UU
UE 21- (P -
=
K + 1
Hence, for all O,..., K we get P(Ex)
2 1
As revision result, event Ex+1 implies that K+1
kg
[f(x))]
24
(47)
2
k=
holds with probability at least --6. 6.
Therefore, we get that with probability at least
K [V)(2z)1
44
max kE
C
and, since C₁
1-81 bx
obtain
K [v((x))] <
4A
max b
(48)
>(1 B1)
kelo,
k=
Moreover,
K
60 17
3[ +3100111 + +3)0011++(((0011))
(49)
Amm
for the Clip-AdaGradD of by and
<
1J
3 [/(())
+ =3110%11 2
(50)
+
34

---

Clipping Improves Adam-Norm and AdaGrad-Norm
for the Clip-AdamD, respectively. Next, use that the event Ek+1 implies
0211==
A
2 c 1 (1)
10
A
bn
2
k=0
because we could replace b, - by into C₁ and Ae, and all steps in @, @ and @ will be the same. Therefore, with applying Lemma C.I, next bounds
4A
3nbbo
37pb(1 - 31)
DG +
3n
[f(x2)1 +
7(1
B1)
47
4hy2
4A
31
3ndo
3rdb - -11
[++x)) S
Σ
[
7(1 31)
K ++1
My(K+)
1 + +1)
hold with probability at least 1 - 6, where we substitute different cm from Lemma C.I and (49), (50) for Clip-M-AdaGradD- Norm and Clip-AdamD-Norm, respectively. Next, solving quadratic inequalities above with respect to obtain
K
Σ [V we
k=0
K
(1
48
+
9449
(1)
+
111-01)²
16A2
17
(10g(1-8114 1L72
+ +b
<
2
24
576 A1
3rpbn A3
+ 31p22,
41gA2
+
+
+ 7/(1 - B1)2
71 -31)3
741 - (111-1)]**
73(1 - -1)3
Ly4 (3))
A 72
24AAA
5767)222
33pbo
4b872
=
(1 B1)2
1 (1 B1)4 +
(1 - B1)2
+ L(1 -B1 + (1 -,
for Clip-M-AdaGradD-Noom and
K
A4n
fIxx2) - 7, - 31) 2(K +1)
9 9.4% 43
442
3
31pb(11 - B1)A
bg
111 ( K- +
1)2 (2 B1)²
(y(K+1)
16I (K +1]
24
21 (.)(K(1))))) +1)
576m2 A
3nb A3
3763 41 - BI) +1 1711-117
45/44
711 (1) + 1)2
(1
A
24nA
22
(1 31)2(K +
576m2 A
3rbbo A 2(1 - 31) (K +1
3r1fA AL(1-B:)(k +1) (1 31-B1)²
41632
(K + 1)
for the Clip-AdamD-Norm. Substituting 1) = L1) and applying Vaz + 12 cd + d S -a+b+ct negatiee
A
35

---

Clipping Improves Adam-Norm and AdaGrad-Norm
numbers, one can obtain the bound for ClipMM-AdGGradD-Norm.
K
48T,² + V3 + 3/ - -31) + 2700
f((x)))
KL k=
(K + 1)y²
A
27.00
49L + 3/2 B1)
(1) + 1
(K + 1)12
2ydu
4 2 + 3760 + 1
(K + 1)7
2A
5y:b
max 49L -1- 31
(K + 1)72
98T.A
10
max
(51)
K +
7(
+1 B1)
and for Clip-AdamD-Norm:
A
48I,²
3b
3y21 B1)
27b0
K Σ [ff(21)1
(K + 1)12
K K+11
V 2(K +1)
+
4(K +
1 - 31
A
48T,7
Ly
+ +obo + 2700
+ 2
(K + 1)?
K+1
(K +1)
31
A
499
4760
+ 1- B1
(K 1)
K +1
2A
{ 199 47y0
(K + 1)}2
K
$1
98LA
8Aho
max
(52)
(K + 1)2²
7(K 1)(1 3z)
where use that ab a b. Consequently, after substitution of (37) into (51), (52), we get final bounds for CllpM.AdaGraDDCipp-dddb------
K
1
V f(xx))2
K +1
k=0
LA In K+1
VLAg In
K+1
2g 20-
(LA)
n-1 20-2
In
K+1
= max
(1 (1
(1 B1) (K + 3u
81)
+ 1) 35
holds with probability at least 6.
C.3. Convex Case: Methods with Delay
Lemma C.6 (Descent lemma). Let Assumptions 1.2 and 1.3 hold on Q = B2 where ||ll - x=1| S R. Assume that 8nL
It E Q Vt = O.T. Then, after T iterations of Clnp-MAAAdCcraDDDMo///cilAAAlad Adwa:/Diii--AaD----aaaaaa have
with by 2 [1-81)ee5
we
T-1 Σ
T-1
T-1 C₂ (x, - 0,) + Σ
R² - Σ
2A, || 0.112
1=
1=0
t=0
T-1 1- 2 gi-l and A,
I- 2+(1)))) (/-()) - 1).
where C =
Σ
Σ b,
1st
36

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Proof. According the update rule of Algorithm have
27 by
72
F++1 - x²11 10 x01
(ar x² .m +
lmmll
by
To bound the scalar product, we substitute the update rule for m.:
(ore x², .m&)
-1 (It x², mmmm1) (1 -1) (2) x².90
-1 (It 21-1, -1--1, B1 (1x-11 x², mm-1)
(1 B1) (xt x9+)))
I -B1 (r1-1 x², m-m)) - (1 (1 (1) (xze - xx, ,9)
+ B1 || - 22-1ll |11
31 (Ii-1 - xx,, m=+ - (1 - B1) (xte - x², ,9)
7 ||m--1122
b-11
Applying the same idea for t 1,t ...... O and using that m_1 0, can obtain
1
9:99
(Iee - xxxxx,,) mi) S
E(1 31) (xx x². x'
||m 11?
Therefore, we get
0141 - 1²11² $ ||00
x²11
27
Σ
31)
(xk x², x²
+
27
Σ
1| 11
b
be
bk
k=0
Substituting the bound for ||m from Lemma C.2 with 1- Bltt1_ < we have
[0++1 - x²1 1 1|:0-
x1
2
Σ (1 - 31)5 (ox x²,9x) +
272
Σ
k
(1-)(l11)
-
be
b
k=0
k=U
j=0
2
27
t
k
3
1|,,,
x=" 11
B1) (xx x=, ,9u) +
(1 B1)1l9;11
b,
b,
k=0
k=U
Applying the same technique as in Lemma C.3 (see (33)), one can obtain
2y(1
31)
(0x xx) + 20 -11)
31) Σ
[1411 - 2²112 s || 1²1
3 - + 1)
b,
bybb
km0
jm
After summing over l:
T-1 27(1 -3,)
1 8 (ox xx.9k)
|| - 2011= < 11:0 x0112
bi
k=
21 - 31)
0
gt- (t j+ 111
(53)
bebo
1=0
Therefore, multiplicative factors for (xs, x=, (r) and ||g,11 are equal to
2y - B1) 8' and
2T Bi) g r+1),
b;
bmb,b
37

---

Clipping Improves Adam-Norm and AdaGrad-Norm
respectively. Let us denote them as -2yC, and A,. Using the same idea as in Lemma C.3, get
(1 - 31)
1
I Cr
S
br
CmDp
and
27²
A, S
cn b bo - 11))
for all p p= O,...r because of Lemma C.I. Rewriting (53) in terms of Cr:
T 1
T-1
| - x²11² < 120 x²11 - Σ
2+C (xz x90 + Σ
A 119 11
0=
0
Consequently,
T-1
T-1
aT x²112- - -1120 x²11² S
Σ
27C, (Tt x², .9)
Σ
Agl19.1 1
T-1
T-1
2yCr (ate - x,, vf(xx) + 0,) +
A f + +
1=0
T-1
2yCr (Ie - x", vf(xz)) - Σ
27Cr (x)- - xx)
1=
1=
2A ff + Σ
2A, 1
1=0
1=0
Using Assumptions 1.2 and 1.3, one can obtain
T-1
Σ -AC.-4AAM (F4))))))))))) f.) S Σ
12 (2-- x², Vf(x))) ( 2A.11((a)11)))
t=
T-1
T-1
S 1:0 - 1²122 || - x² x²11
Σ
2yC, (1x 0,) +
Σ t=0
2A, 1
(1-91)2 SL
If we choose 7 < finishes the proof.
then 2yC, - 4LA, 2 7Cr because of lower bound on C, and upper bound for Ar. This
Theorem C.7. Let Assumptions 1.1, 1.2, and 1.3 hold on Q = B2a(x*) with I|ll - x01 S R, Then, after K + iterations of CClpMM--eeccaoD-oommmiiillelmaaa with
(1 (1- (1=),)²c2, bo
-I-Bicm Rbo
22(1- -81)2
7 S min
17
(54)
160L In
((K+1)
40 o (K 1) In
1(K+1)
R2
8
and
A VI- bo
(55)
407 In [((+1)
the bound
K
Σ
7Ch (f(x)) - f.) < 212
38

---

Clipping Improves Adam-Norm and AdaGrad-Norm
holds with probability least 1 8. In particular, when Y equals the minimum from (54), the iterates produced by Hwwi--aaaGrraD-NoooC---------- satisfy
f(x=)) = max (1 (1-BB)(K- (1- })
LR In K+1
RRIn - K+1
with probability at least 1 5, where IK- K+I Σ IK=O
Proof. Our proof is induction- based (similarly to the one for SlD by Sadiev et al. (2023)). We introduce probability event Fg as follows: inequalities
[-1
Σ 10
27C (2) 2²) +
Σ
2A||0:1 S RR,
1=0
R4 S V2R
kg hold simultancously Vt = 0, o.......6 k. We want to show that P{Ex) 1-
K+I Vk = ..ll....,+... The case when k: = 0
is obvious. Now let us make an induction step: let the statement hold for some k = T - 1 K: (( 2 1 (T-1)8 remains to prove that P(ET] 2
K+1
The event ET- implies T, B (22r(²*) Vt .,..., T 1. Hence, ÆT K+T
Ts
also implies
PT x²11 S | x²11+ +
7
| || S V2R+ 7t
S
/2R +
7 2
br-1
by-1
by
Therefore, ET implies (ma)i=o S B2x(x*)) and we can apply Lemma C.6:
t-1
(-1
GG ([(a)) - (.) s R R²
Σ
C7Cr (u1 - 00)
Σ |A:1
1=
1=0
1=0
Vt 1..... T and Vt= = 1....T T - 1 implies that
cc (f(x)) - (.) < R3 Σ 27C4 (m - .0) +
2A1 < 2R².
1=0
1=0
Taking into account that Σ
71 f.) 2 0, we get that Er-1 implies
T-1
R x R
Σ t=0
C7 (ar x", x²,0,)
Σ t=
2A, 10.113
(56)
Next, for vectors
xt
x=,
121 - 10 S V2R
171
0,
otherwise
for all L 0,1,..., T - 1, we have that with probability 1
|allll < 22..
(57)
Then, ET-1 implies that n - -xx x= for all t = =..... T - 1. What is more, for all f -....T ...TT-
- T
Er-1 implies
(55) A [+)(2)]] L1x = s V2LR
< 2
39

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Hence, using the notation from Appendix A, have that Er-1 implies
T-1
R RD-
CyC (It x², 2²,0%)
Σ
CgC
(2t - x²,0%)
-0",
Σ
4A, (1181112 -Eg, 11000
8
4A 10 2
4A 0
(58)
Next, bound each term separately with high probability. Before we move on, we also note that event Er-1 implies [V S - Therefore, one can apply Lemma A.4 and get
|0 S 2A,
(59)
2a
|00]] < Xa-I
(60)
Eg. |100 || s 1812-000
(61)
Bound for @ The definition of 0f implies
Eg, [-2yCt (me, 0,)] 0.
Moreover, applying the bound on Ct: C. S Cy by
from Lemma C.6,
(57) GyAR (55)
3R²
1-2 (n,, 07 s 2 [Inil
Cm bo
20
[((+1)
For of = Es, (4,20 (n, 0 we also derive
8 R2
of s 5 C |00
11
Eg
1|
(62)
ct bg
Hence, we can apply Bernstein's 's incquality (Lemma A.5) with c defined above and
n 100
T
27
R²
T-1
Rd
P
(xz - x,, ,²,0")
>
and
o
<
$ 2cxp
by
5
25 (2G +
2n
1=0
t=
15
8
2(K + +1
Therefore,
T-1
27 x²
R²
T-1
8
p
either
(xz
07)
or
Σ
2
G
2 1
b,
2(K +1)
1=0
t=0
In addition, event E implies that (due to (62) and (61))
14472)2-a RCT (55) 144(1
31) --)2-" 44 1 ataRt-aT
2 b
4 ci by In 2-a [(K
(44
144(1 - RT
RN
9. (K + 1) In A(K+1)
100 In 4(K+1)
40

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Bound for @. For the second term, one can obtain from (54), (55) and a S 2 that Er-1 implies
27
(57) 2/2. 200""TR
Σ 1=0
C7 (3e x², 0²)
|1
|1
|
Cm bo
0mb0da-1
t=0
4 4.2040%00 TR
(54) 4 29 BI)
(55)
40(1 - B1) - cm b0 In
1-a 4[K+1)
360 (K + +
0
2/2
R22
45
5
Bound for @. For the third part, we have
4A1 (108)12- - Bgg 10, ]
E
= 0.
What is more,
AA1 (1007) [10811=-&3,11003 =0.110011)) s 4AA (1081)] R.g 1108 (59)
64>2X2
(55)
R2
6b - -3)
25 2
4(K+1)
3/2
(63)
20 In
1(K+1)
We also define
16A2 (1089))-
Re, 110% 1) 27
07 = Egg
Hence,
(63) 6, 5
3R²
Egg | (10%91- Bg, 1100 I1²)
20 In
((K+1)
5
12y² 2 R
Eg, 10:1111.
5c (g(1111 - B1) In 4(K+1))
Therefore, we can apply Bernstein's 's inequality (Lemma A.5) with e defined above and G
R
100 In
P
4AA (10r Eg, Eg, 1101111))
R²
and Σ 07 < G
< 2cxp
Rd
5
25 (2G +
2c
t=0
15
5
2(K +1)
Consequently,
T-1
R2
T-1
P either Σ 4Ac (10:112 - Ee, 1109112))
<
or
Σ
G
2 1
5
2(K + 1)
t=0
-=0
Moreover, event Er-1 1 implies that
T
T-1
12
EE, 11 (61)
18 1 0 PPT
<
2 (1 31) In 4(K+1)
5 63((1
B1) In 4(K+1)
1=
t=0
18 12 4000000000 Rl-aT
18 12R*T
(55)
5 202c ca (1 31) 3 bg In 3-a
4(K+1)
9- 402 + 1) (4(K+))
8
R2
100 In
1)K++)

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Bound for @ For the fourth part, we get that Er-1 implies
T-1
8
(61)
14472X2-00"
Σ
A
E
1
C (1 - 31) Eg, 10
S
2 (1 31) 81)
1=0
1=
(44)
140 182 12-00000 TTT
(54)
144Rº
40 m bg
31) ; In a-a 4(K+1]
9 402 + 1)
4(K+1)
R
R²
100
Bound for G. For the last term, Er- implies
T
Σ
4A
1A.1
S
T-1
Σ
872
00/1/ (60)
8 2T
2
11 - B1)
C 51 - 31 )2((a-1)
4 4020 0 20 201 111 2(a-1)
[(K+1)
20 (1
R2(a-1)
(54)
8 RT
8R
R²
3602 + 1)²
45
5
Thus, taking into account the bounds above, the probability event Er n E1 n Eg implies that
R²
R +5
2R
5
where
27
R
T-1
Rd
E1
either
x² 0,) 1
Or
0
2
by
100 In
4(K+1))
E2
either
T- 1
422
(1197) 12
Eg |10,11 2
R²
or
T-1 1
07
R²
by
5
100 In
4(K+1)
0=
t=0
Therefore,
78
P ( 2 (Ey E
= -1 (P
E1 SUUEEE E2} 2 21-P (E.)) P
EE2)
21
K + 1'
Hence, for all 1 O,..., K ++ we get P [( 2 K+I. As the result, event Ex+1 implies that
K
Σ
7C (f(x)) f.) s 2R
(64)
with probability at least 1- 8. Next, from (64) get that with probability at least 8
K
2R max kE|U,K] Ck
1
(f(xx) - f.)
0=
Moreover, ल.
I can be bounded in the following way (from Lemma C.6):
1 by
5 (1 - 31)
Cx
42

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Hence, get
K
2R 7(1 -31) ke (0
(f(z)) ( f.)
(65)
Also we can bound by for
using that gh f(xx) + O2 and Assumption 1.2:
by S th +
(L (.) + 2110x11²)
k=0
and for Clip-AdamD-Nome respectively
bg s by
7
Σ
K
Therefore, due the fact that the event Æ implies (see the bounds for @ 4 and ())
472
3/2²2
10
31)
we get
3n R2
09 s b0
4L ((f(z))- Σ
10y2
for Clip-M-AdaGrraD-NNom scheme and
- 40,2 +)
Σ AL (U((z)) -f))
K
k=
for Clip-AdamD where we substitute the constant cm from Lemma C.I. Consequently, substituting bounds above in (65), we get
Σ (f(xx) ((())))1))
11)
5
4R
10 + Σ
f.)) 3n(1 - 12
22 - -31)2
10y2
for Clip-M-AtaGGraD--Nom and
K E(((n))
2 - -()))))()))
4R
3n(1 -
10 +
11
Σ
(4L(
72 - (1-
K+1
40-2 +
O=
for Clip-AdamD-Norm, respectively. Solving these quadratic inequalities, we have that Ex+1 implies
K
2R
AImRR
16T.2 R²
222
R2
Σ (f(x)) fa)
+ +
72
- (1)
(1 (1-31) -1)4
(1
31)2
10(1 - 31)
< x2
6R
max
((1 - 32) 1 B1
8L
bb
R
V
1 1 8
71
and
K
2R²
4L
Σ (f(xz) - (()
7²
(1 B,J2(K +1)
16L212 R
72
3nR²
+ 1 (1 Bi) + +1)2
+ 69
+
(1 31
40(1
Bi)(K +1)
6R2
8LnR2
bo
11
max
by R
22
(11 (K
31
(1-B:)(K +1)
43

---

Clipping Improves Adam-Norm and AdaGrad-Norm
with probability at least Choosing 1j = - we obtain the bound for Cijp-M-AdaaGradDrCCii---oo AwwaiCiiii--aa------aaaaA for the convex case:
y equal to the minimum from (54) and using that 2/ab - a aa+a b,
R²
LR In Kil K (f(xa) fa) = = max (1- +1) (1 31) ( +1)
1
oRIn K+1
with probability at least
6. To get the final result, remains to apply Jensen's 's inequality.
C.4. Non-Convex Case: Methods without Delay
Lemma C.8 (Descent lemma). Let Assumptions 1.2 and 1.4 hold. Then, after T iterations of (lipp-AAddGrradClpl--ddaaa we have
T-1 1
C [V <
n1(1 - 113) )
2L72
T-1
T-1
T-1 (V
G |10.11
2M +
\ 100 +
Σ
,.,
T-1
for Clip-M-AdaGrad- where Ct = Σ (1 31)88- and
k=t
C
[[(x)) 3M
16KL
1.2
T |
2
T Σ
(V[(),)))
T-1 2 0
Σ
711 - -11))
for Clip-Adam-Norm, where C. C,= (1-B107 "\vaa>)/aa>>>
Proof. The first part of the proof similar to the Lemma C.3. We start with the L-smoothness of f:
((++1) f(xx))= < (ax)), R+f1 - x²) + L |1-11 - xell? =-
x=ll==-2 (VS(()) mz) +
L2²
m
(66)
2
b.
2b
Using the update rule of Algorithm 3, we obtain
fZ))), m²) = - 31 (f(m)) (1 B1) (1)(()))
31 (Vf(z,) - (() 31 (I m--1)
(1 (1) (z))))).)))
S -91 (V/( + B1 Vz( vf(++-))
(1 - B1) (V)(2))))))
$ -31 m)-1 + 1 10 - xz-1 ||,-1|
(1 - B1) (V fZ))))))))
7BIL L
-31 (V / (xt-1), m-
|m |
b
(1 B1) (V)()))...)
where we use the Seuuchy-Schward inequality and L-smoothness of f. Applying the same idea for the t - 1, ., and noting that m_ = 0, we get
g k
V (V:))) m²) < -(1 B1)
Σ
3 (VS(*)) gk)
by
mm
1|2
(67)
k=0
k=0
Therefore, substituting (67) into (66), we have
[(x+1)) ((x)) < (1 - Bi)y
L7
g k
In²
3 (VI(I)), gk) +
||
1 +
[|m]]]
1mx
bt
by
20
k=
k=
(1 Bi)r
L
3 k
3 V
f (Ix). .gh)
+
7 12
bz
b%
k=
44

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Applying Lemma C.2 with - -/
rewrite the inequality above follows:
f(1+11) f(x))) _ (1 8177
In²
1 k
Bi (V)(zz),
+
(1-
ah-
bt
bk
k=
k=0
j=0
81)
L
8 V f2x))))
gk) + be
B
(1-
B1) 11
(68)
bt
by
==
where we change the limits of summation. Multiplying both sides of the inequality above by & where
1,
for Clip-M-AdaGrad-Noom
Pt
(69)
(V32)' for Clip-Adam-Norm
and using that by Cmby (see Lemma C.1), one obtain
by (f(x0+1) - f(x))) 1
(1 (1-3:)y
Lg t 8
Σ 81-* (Vf(xx) gh) + Σ
(1- B1)(t - it + 1)1,,,11
Pt
Pt
Cmby
k=0
j=0
After summing over 1,
T-1
8 (V((x)))))) + +
T-1 ΣΣ
3-
(f(ae+1) - [(x))) < -(1 B1)7
31)(1 - j + 1)
Cmb
1=0 k=0
t=0 3=0
Next, applying the same idea as in Lemma C.3, we get that multiplicative factors are equal to
T-1 7(1
31)88-
-
Σ
(70)
Pt
1=r
for the scalar product (Vf(zr),,.) and
T-1 (1 31) Cmb,p
A, =
(t r 1)89
(71)
for the squared norm [|g, respectively. Moreover, it can be shown that Ps 2 Gn, for corresponding update rule b Hence, for (71) we apply Lemma A.2 to obtain the next bound:
L
A, <
2 (y B1)
Therefore, rewriting the descent lemma in terms of (70) and (71), we have
by (((oo-1-f((1))) <
T-1
Ly²
T-1
9t ||
Σ
c. (Vf())))))
Pt
22 (1 - 31)
b;
45

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Using that 9t (1r) + Oc. we get
T-1
bt (f(zt) - f(x(-1)) Σ
T-1
Ln
T-1
19h 11
f
7c (Vf(az), +
Pt
on
(1 - B1) -B1)
bc
1=
t=
be (f(z)) -fa - -
T-1
Σ
7c (Vf(zs))
1= Pt
t=
LA2
T-1
119.11
2. (1 - B1)
be
bu (f(x0) - f+) +
T-1
by
b
T-1
(f(2)) - fc) - Σ
cc (Vf(2).
(72)
Po
Pt-1
I^2
T-1
2/
31)
b
t=
Since P. = for Clip-M-AdaGrrddNorrs we can use that by 2 b,-1, and for Clip-Adam-Norm we get by 2 BBbr.11. with pt = (vB2)*. Therefore, applying Assumption 1.4, we obtain
what is equal to b b-11 P
M 1
|| 2
C(V
cc (V + (1 31)
Po
PT-1
t=
Now we construct descent lemmas for each considering update separately. For Clip-M-AdaGGrad-Nomm we directly apply Lemma A.3 to bound the last term:
T-1
+ LT²
Σ ([ $
22M6T-1- - Σ
7c (V)(2)))))
1/(1 -B1) b-
1=0
2M 2L7²
b bT Σ
10, (V (V)())
17(1 - B1)
21g²
T-1
2M + 11(1 - B1)
6T-11
7c, (V.(z))))
1=0
T-1 1 10
T-1
CC
|10213
+
(73)
2
2
1=
where we use that Cm 1 and P. 1 for Clip- Clip-M-AdaGrad-Norm. For the Alim-Adam-Norm, we get
1g.
2
n|1gel 11
bt
5 12 +(1 B2)n Ei 32 $1.9x| ll
K
2 2 |100112
62 1 + N/2 Ei=o 1
T-1
4K
62 +
7 K
Σ
119. 12,
17
where we use that B8 2 f/4 all k o..... K. Consequently, with upper bound on by and cm = 1/2, for Clip-Adam-Norm
46

---

Clipping Improves Adam-Norm and AdaGrad-Norm
one can obtain
I
7-1
16
Σ <GIV S 6b, +
y0 (Vf 0,) +
62 + K R=0
|9 ||
(v32)TT11
771 - (()
1=
18
3M +
16
12 +
"
T-1
119111
70, (v))))))
711 81)
K
1=
3M +
16K
62 + 7
T-1 Σ
|19.11
P-1
Σ
7C,
(V.(()))
711 31)
K
T-1
CC [V)
C
10:11
+
t=
t=0
After substitution of the analytical form of by-1 in (73) and different options of pt. we claim the final result.
Theorem C.9. Let Assumptions 1.1, 1.2 and 1.4 hold. Then, after K iterations Ail.-//A/AAAAAAAA-///i--------- Norm with
b K 3a
b VM
y S min
48L In (1)
4 12 [K 1) 30-2
b MT- T
I
1)
(74)
4
12
0
(K 1)
20
M(1 - 31)
and
A b- M(K + 1)
(75)
12vIn In (3)
the bound
K- Σ [vfxx)) K=O
=0
LM In (1)
VLMo (4) g 2a-1
(LM)
20 1
2m
(1- max
K
8
K
30-2
2u
K
2a
K
2a
holds with probability at least 1. 8.
Proof. The main idea of the proof is similar to the proof of Theorem C.5, but we do not need to introduce any probabilistic events since according Assumption 1.4 the norm of gradient is always bounded:
[>)()) 2TL - f.) V2LM <
Therefore, one can apply Lemma A.4 and get
10 S 2X,
(76)
|0:1 < a
(77)
A--T:
Eg. ||0| 2| < 18A 2-0 2-22 0
(78)
According to the Lemma C.8, we get
Σ C
2TA²
T-1
T
T-1
10
<
2M + 7(1 - 815)
62 +
7 (V)x:))))))
Σ
10001
2
\\
2
1=
1=0
1=
1=0
47

---

Clipping Improves Adam-Norm and AdaGrad-Norm
T-1
with C. Σ (1 - -1) for Clip-M-AdaGrad-Norm and k=t
T-1
C ff(+)))l - 3M + 1,
T-1 | ?
T-1
T-1
2
Σ
6-_ + K
Σ
7c (Vf(2.)))
87) +
Σ 0
2
711 - (1)-
2
1=
with C. Σ
(1-81)8t*// /VVD5)* for Clip-Adam-Norm, Let us bound C, regardless of the method. In be shown that
1 1 31 C(CCloo-MAAACCCrraNNoo)) - Σ - -1) =
k=0 0
and
n0 2 B1) k=0
1 B1 S C(CClip-Adam-Norm) -
since (VB2)T-12 2 1/2. Therefore, descent lemmas for Clip-M-AdaGrrd-NNom and Clip-Adam-Norm can rewritten in the following way:
71 81)
2L7²
|V (xx))l < 2M
11(1 311)
\
62_
+ 11
Σ
119. 1l
ΣΣ
T-1
7. (V)s))))))
+
7
112111
(79)
1=
for Clip-M-AdaGrad-Nonn and
711
B1) T-1
V [((aa)| <
3M +
16K
12 +
71 K
T
11 11
2
17(1 B1))
T-1 7. (V)(1))
T-1 Σ
>
0|
(80)
for Clip-Adam-Norm. Moreover,
ll can be bounded as follows:
9 <
(IVS(=>)1 + -
Be, 10011111) + Ee, 10:11 + =100911)
(81)
t=o
The main idea to give upper bounds for the next terms for all S K:
[10% 1|2 Ee. 10:11
ES 110
Σ
C. (VS()))))
In cases of D, and @ we multiply sums from (81) to the factors to move to the corresponding type of sums from Theorem C.5.
Bound for ① We have bounded and unbiased terms in the sum:
Ly²
E
110:11
Eg. 11011111))
82
48

---

Clipping Improves Adam-Norm and AdaGrad-Norm
and
In? (10811²
Eg, [11
8 (76)
24M C.
b
b2
19 0
Next, we define o?- = =Bg,
L2nn b9
(1104112 Be. Bg.110x11
For the introduced quantities, we have
of
claz - Rs,
|10;11 - Eg, 1100 11] 5 b-,
2eIr²
Eg 110.111
Therefore, apply Bernstein's 's inequality (Lemma A.5) with G =
3M2
38 Iu ())
Σ b2,
I
(10r
Es, Es, 11091111)
M and Σ
T-1
o. S G
exx
M
6
2G +
2cM
2
3
Thus, we get
P either
Σ
2
Ee, 10.110817) )
$ M or
Σ
T-1
>
G
2
b2 0=
2
t=0
Moreover,
T
36cT LocT'L?222000
(75) L, "V"LL"
VMM 2-a (1-912--)
K
S0-2
(74)
3M²
82
122-a VI
- 2-a 2-a
38 In (1)
0=0
Bound for @ For the second term, we get
T-1 L2 ΣE Ee, 18;1
18T
(75) 18T L VM 2
(1 ax2-
3a
M
< M.
6²1
22 VL
In 2-a
32
t=
Bound for @ For the third sum, we obtain
T-1
oo 2 (77) 20 (75) 4d 2020 220 1 TT
In 2a (2) (74)
Σ
S b 22a-2
S M,
b 2a Ma K
11 12 2)
where we choose the third option for ?.
Bound for @ Similarly to @1 we have unbiased and bounded terms in sum:
Eg.
=0
b
and
rC, | (Vf(x:), 0.))
2Y [VV( b_1
(76) 47AV2LM
3M
b-1
<
b_1
4 In
(
4
= C.
ct (Vf(zz). 0/13
Let us define of Bg,
Hence,
62,
8 62,
Eg, 1
Therefore, apply Bernstein's 's inequality (Lemma A.5) with G _1²2
[lm(z)²
cC (Vf(x)).0)
T-1
M
8
M and
Σ
of < G G
2eexp
b-
2G +
2cM
2
3
49

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Thus, get
C (Vf(z)),
T-1 S or 07)
2 21 8
P
either
Σ o > G
b-1
2
1=0
1=0
Moreover,
T-1
(78)
144
144/M K LMMM> (75)
(1-aX2-00
9 LMTO (74) M
v
122-0b2.v VL 2 2-a
In 2-
4 In (1)
t=0
Consequently, next inequality holds with probability at least - for all T TSS K:
T-1 Σ 1=
6M6 In2
3Mb
Σ
loell 3
IVS(+))
Let us specify yy for each method. This parameter can be chosen as follows:
L-
for Clip-M-AdaGGra-NNom
M 8
7
KL M1)1-81)
for Clip-Adam-Non
Therefore, (79) and (80) can be rewritten in an unified form with and ① 2, and @:
7(1 (1-330 31)
3L7²
662
3L 2M
[((x)) 19M,
12
(2xx))
M(1
31)
1- 31 B1
holds with probability at least 1 - for both algorithms. Denoting above, we get
[f(x))]1 as SK and squaring the inequality k=0
2
2 21
31)2
3L
612
3L76-1
5k S
19M
12,
SK +
+ 1- B1
+ 2M
4
M(1 B1)
1-3
3Ld²
602
+ 3Lyb-1
S 762M
6_ + M(1 B1)
SK +
+ 8.M26211
1 B1
1 - B1
where we use the fact that (a b)² < 2a² + +6b Rearranging the terms, we have
6 3- LM
2 2-382 M
812
66_ 1
3Lyb
S
SK
62
5 0.
(1 (1-3))3
72(1 101--10 31)2
762
31
B1
Solving the quadratic inequality and using that va² + < a + b. one can obtain
6 6.382 LM
38
812
662, 1
3Lyb-1
Sk - (1- (1-3,)3
7(1 - 31) V
12 +
762
1- 31
- 31
6 3.382LM
38V2M
(21b_1
3b_1
(1 - (1-3))3
7(1 (1)
19
V1- 31
because Ly T8 Therefore, after division of both sides by K and substitution of y from (74), we get the final bound for AaA.aaGGrra--om//iiipiaaaaaaa
K
(0a0))0000000 == (1 (1- 3
LM (1)
VLMo In a-1
(1)
o -
20
(LM) 20-1
In 2-- (1)
max
K k=
K 30-2
20-2 K
30-2
K
3n-2
2o-2
with probability at least -. 8.
50

---

Clipping Improves Adam-Norm and AdaGrad-Norm
C.5. Non-Convex Case: Coordinate-wise Methods with Delay
Similarly the methods with scalar stepsizes, for convenience, we consider an reweighted forms of the coordinate-wise methods, which equivalent to non-reweighted ones.
Algorithm 4 AlimpCAAam/ClippAAAamm and Cilp-MAAAaCrrad//iiiMMAAACCCCaa
Input: Stepsize y >> 0, starting point zi R&, initial constant b-1 > (for Adam and M-AdaGrad) 0 (for A and M-AdaGradD), momentum parameters 31, 32 [0. 1]. level of clipping X > 0 for each coordinate, reweighting parameter
0
1: Set m- = 0
2: for = 0, 1,. do
3: my, = -1 + (1 - 31)olip (V
4: if delay then
820% + 1(1 32) [ ( (2r))li, Aa)
for Clip-Adam for Clip-M-AdaGrad
5: bi.:
6: else
V Babi, + (1 B2) [c) ([V (z)),
for Clip-AdamD for Clip-M-AdaGradD
7: but1, =
13. i
8:
end if
9:
21+111 21,
b2.
2 m4,5
10:
end for
To improve the readability of the proof of coordinate-wise case, introduce the following notation for this subsection:
Ve,
It.s [grlis
01 = Dt, Ve,r
84 I1, (g...
8,, = Eg., - Vi.
Lemma C.10 (Descent lemma). Let Assumption 1.2 hold
x E Rdd Fl Rd f(v) S. 2A and || y/1 S
20vL S where (Z0) f. Ao A. Then, after T iterations of Cfli-AAAAAAGGrraDD/llloAaaaa with 2 7L/cms if
VA )
Ie E Q Vt = 0, T, we have
T-1
Σ
Cli Vi, I (f(zo) - f*) (f(xt) - -f)
Σ (r,, 2At.)) O
T-1 d
T-1
+
Σ Σ
2A,
A0, (0 + Σ Σ
Gr, (0%,)²
where Ca, = (1- (1)
T-1
Σ
a+
and Ar,
172 8
T k
bu,
Gyp
kitt
k=t
p=t
51

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Proof. Starting with L-smoothness, derive
f(0+1)- - f(x)) S (VI(s)), F141 - -x1)+ + I.
In²
d
|1:41 - =xell = -?
b
2 y=1
1,5
d Σ
L^ m
+
(82)
b
2 19
1=1
Similarly to the proof of Lemma C.3, we get
Vv,,mu = 31 V2,, V.ig...
= -V., V1-1,)mm - - -1 (1-B:) V < 31 VV. - Vi-1,il M4-1.1 - 31 V 1- 1. (1 (1- (V31VVV... 1,,
Using that m-1,; = with the above recursive inequality, we get
t-1
Vi S (11 - 31)
s k Vv
+
8
V - V mxxal
k=
k=0
Dividing both sides by b and summing over i, we have
Ve,ma < -1 81)
V
t-1
Va+L
Va,il mm
3
(83)
A=
k=
Then, we apply
inequality to the last term in the right-hand side:
VK+1.
Vasel Ima,i
m
Σ
Σ 0
Σ
V Vetl. - VVELL--VaN' Vx.e)
Σ
b
br,
k=
k=0
t-1
m2
Σ 8 [[ - V[(aa)ll
Σ
DZ
i=1
m
0
k L ||
æxll
Σ
by
k=
i=1
1-1
d
m
m
L
DZ
D2
1-1
m
k
Cm
where in the second inequality we apply T-smoothness, and in the last inequality we apply Lemma C.I. Therefore, substituting the inequality above into (83) and combining it with (82), we derive
L
2 mKii
L
d
m
((set)) -(a)))
-(1-BB)
+
k=0
be
Cm
R=0
k,
2
Vkiikk.
m
< < - 31)7
3
k
be,b
Cm
0=0
1=1
km0
1=1
Applying Lemma C.2 to the last term, we get
Tn2(1 - 31)
-(z11)_(zz) S -11-A0 - (1-1))
k
g
b
Cm
k=0
1=1
k=0
1=1
3=
52

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Summing over I, obtain
Vkilkk.
((oT)- - - -11 31)7
b
(=0 k=0
1 - 31)
T
+
ok
(84)
Cm
t=0 R=0
1=
The rest of the proof follows Lemma C.3. Let us denote -7Cr, and Ar as the coefficients in front of Vraire and L in (84), respectively. These coefficients equal to
1
- = B1)7
(85)
1=
L2 - B1)
A,
(86)
Cm
Following the same steps as in the proof of Lemma C.3, get useful bounds (will be used later)
(1 31) S Cr S
L o br - -1))
Ar S
(87)
brg
Cya
due to Lemma A.2 and Lemma C.1. Rewriting (84) with (85) and (86), we have
T-1 d
T-1
-() - S ΣΣ
- -
Vi,iht
ΣΣ
A
t=o
Following the same steps as the proof Lemma C.3, we get
T-1
T-1 d
(f(xr) - 5-) (f(o)) - -
Σ
Ca, V..gt. +
Σ
A
==
1=0
T-1
T-1 1 ΣΣ (nC,, Ac,)
(nCr, - 2A.,) v,,O0
1= sl
A..
53

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Using the notation of tf and 0g with 7 -
(1-9.)2
which implies yC,, - 2A,,, 2 0 due to (87),
2L
T-1
T-1
Σ
E
(n - 2A,,)) Σ
Σ (7C A.,) V2.
T-1 d
Ar,50f,
(1,,,
Σ
Cr Av,
1=
(0,,) + +00,)))
T-1
Σ
CCii Ae.s) (02,)2
1=
-A1,
Vi.
2
T-1
yo Vi.
T-1
ΣΣ
(n.,,
VA,,,,,,,,f
2
10
T-1
2A
(0
)²+
ΣΣ CC,(00)))
where we use the fact that CC., 2 2 Ar.i. Rearranging the terms, we conclude the proof.
Next, to reflect tighter dependencies on the variance of different coordinates of the stochastic gradient, we make the following assumption.
Assumption C.11. There exists set Q S Rd and ø 2 0, a E (1, such that the oracle satisfies E fg(r)) fxx) and
E [| V (z( V Vi E [d] and Vo E Q.
(88)
Moreover, assume that {V are independent.
Theorem C.12. Let Assumptions C.1l and 1.2 hold on Q - {x Rd By E Rd: f(y) S f.+2A and || - yll s with f(xo) f. Ao < A. Then, after K + iterations Ciip-M--AdaGrraDD/CippAaaaaa (1 - 32 1--31)2
v
200L
with
35 Cm 1 -3ib0 Avd 2-o
bo (K + +1) +
< min
40Lv In 41K+1)
432 20 Σ of=108)
(K+ + 1) 1- In 4(K+1)
Cm (1 31)
Fa bn I
L (1)
11
0+1 4 1 20
29-2
1i=1
0220
20-1
2
26-1
(K + 1) 1 In 2- (4(K+1))
A
(89)
and
A =ン= 4m
I SI
3,00 V A(K + 11) -
(90)
20VdvIn In (A(K+1)
the bound
TChi V2 24
i= 2
54

---

Clipping Improves Adam-Norm and AdaGrad-Norm
holds with probability least 1 8. In particular, when Y equals the minimum from (89), the iterates produced by CippMM-AddGradD/Ciip-Adddam sarisfy
VV fx(x))
K
0=
VdLA In K-1
VIA
Σ d
In
i=
= 0 max
(1 - 3-)33)(KKK +
Ia-I
3a-2
(1 (1- 31)
2-a
(K +
>i iml 0720)
(LA)
In
2a
(1 B1} 2
(K 1)
33
with probability at least 1 -
Proof. We construct the proof in similar way as the proof of Theorem C.5, The probability event Eg is defined as follows: inequalities
t-1 d
(4C1, - 2A V1,88, 2A,,())))) + (0,,(0,,))
AA
A S 2A.
hold simultaneously 1/ 0, k. The main idea is to show that [P 2
Kd Ak 0, K + 1. The case k: = 0 obvious.
K+1
According an induction step, assume that this statement holds for some T < K P(E 1) 21 (T-1))
We
K+1
need to prove that PrEr] 2 and
78 The event Er- implies that Ty E (y E R f(v) - f + 24 A T,..., T
K+I
mii
m
X VA i=1
7
| xT-1 7
Cmbg
bg
C.
20
Hence, event E implies (T) C Q and according to Lemma C.10,
1-1 d
Cr. Vi, s Ao A.
(7CLs - 2A1s) V1, 20,,) + (0,,)
VI = 1,7 and V1 1, T it implies that
CC, S Ao A.
(rC1, 2A1,)) Vi, + (O,,) + +0,,000),))
1=0
1=0 t=
2A.
Taking into account that left-hand side is greater than zero (since every term is nonnegative), ET implies
AT < Ao +
(7Cr, 2A..)) Vi, + (0,,) + (0,,))
I=0
Next, let us denote
Vin
$
Mt.1
(91)
0,
otherwise
55

---

Clipping Improves Adam-Norm and AdaGrad-Norm
14 .,...., T 1. Therefore, the event Er-1 implies T/t,s t,i since
(90) X
1. [f = SVVLA
2
Thus, we obtain that ET-1 implies
A s 0 + ΣΣ
- (701, - 2A(,)) n..
t= 1=1
d
2A (0(2)
ΣΣ> Σ
h ho..10
(0 -ss. [(0 "]]
(nC2, - -2A,,) mt
2A1s
2
T-1
2A E (0
(0
(92)
It remains to give upper bounds for each term in (92). Moreover, due to (90) we get VV, $ A. Therefore, we can apply
Lemma A.4 and get
10%,1 $ 2
(93)
10 S 20 Aa-I : Ex. [00 < o
(94)
(95)
Bound for @. The definition of 0f, implies
Es.
Σ
(1Cri 2A nr
=0.
What is more, we have
d
d
(11,00)
I 4VdAALLA
-Wres - -2Aes) 0i,0
(0),))
M
Cm bo
c,
5 In 4(K+1)
where
we use that (7Cr, -A..)
due to the choice of 7. Therefore, using (87),
Also let us define of
(7Cr, 24t,i) ne.oo''s ))
Eg,
by
M
Σ Eee, (0%))²]
@1)
c2
E
(0r,)
(96)
1=1
Hence, one can apply Bernstein's 's inequality (Lemma A.5) with G
7
4n
SCKFIT 5
T d
A
T-1
A
P
(rCr, - 2A..) n.
and
Σ
á
< G
< 2 exp
4
16 (2G Ac)
t=
8
2(K +1)
56

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Thus, get
IP either
P-1
ΣΣ 1= =
(yCr, - 2Aca)) n.,0r
A
or
Σ
T-1
o
G
2 1
8 2(K 1)
4
==
Moreover, event -1 implies
T-1
Σ o
47 LA
d
E
27
(95) 72. LAT d
22 bi
2,2
c bg
t=0
1=0
i=1
iml
(90)
(2
31) 1-
22-0
V
(K
LAT
(89)
7
of
20
VL 2
2
Vd
2
In 2-a 4(+1)
480 In
4(K+1)
Bound for @ Here also apply Bernstein's 's inequality. One check that terms into @ are unbiased and bounded:
d 2A,
(07:;) -Bg. [(0r,)) []
Ex,
= 0
because of the definition of O2 and
4dT,222
A
154
2A, [(0),) Ee, (O )
C.
c (1 - 31)
100 In
4(++1) 8
47 In
4(K+1)
24 [(0r,)) IE (0r, ) 1)²
What is more, let us define o, = BEE
Σ
Hence, we get
o, S cB&r
Σ
2A [[(0)))) Eg, (0%,) ]
4L72c
Σ Es. (0%))) 2
B1)
Therefore, one can apply Bernstein's 's inequality (see Lemma A.5) with G
7
1504 In( 11++11
2A, (07,)) - -Re, [(0%,)"' 21 $1
and
T-1
Σ
o7 G
I <2exp
A
16 (2G + Ag)
t=
t=0
8
2(K + 1)
Thus, we get
P either
Σ
Σ
2
[00))) -Ee,
Ec, [(0g)) 27
Σ o G
2
8
2(K 1)
h= im1
t=0
Moreover, event - implies
(95) 22 aq
(9m)
7207 ạ A
(K +11
23-30+2
3n-2 LT
d
Σ t=0
0
<
m
2 (1
B1)
a0
31) ca b8 /
2 a
In
2 a
4 K+11)
(89) 7Ac
2
480
1504
4)K+1)
57

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Bound for @. For the third term, we have that the event Er-1 implies
T-1
(95) 36 TT
2A, (0,,)) (0W,))
16 - 31) o
3617
2
(K + +1
3a-2 T
20 202-a((1 31)
3 cm 66
VL
In a-a [(K+1)
(89)
A
4
Bound for @ Similarly the previous bound, ET-1 implies
Σ Σ p
(94)
477T
Σ
o
Cm 220
i=1
(90) 40 7 (K + 1)
d
20 vola- 2--2 2 2a-2 200- 2 "In" 2a-2 (4(K+1)
VL
0,
20
Cm bo
(1 B1 aa11 210 2 V/ 2a 2 (K' +1)
(1 (1-n)aa 27
1=1
36-2
20 Vd
2 2 VL
20 2 In 2a- 2 [(K{+))
40 (K + 1)
2a
20
bg
(1- 31)
20- 22 2 V
2n 2 (K + 1)
a1120-21
(89) A
Therefore, the event Ey-1 0 E1 0 Eg implies
AT = 2A.
where
A or
7
E
either
Σ Σ
(,Cr, 2Ac,)) m.
5
Σ
o
480 In 1(K+1)
t=
E2- either
ΣΣ
241
(0%,)2- -99- EEC [0r,)]]
2
A
7A2
4(K+1)
1504
8
Similarly Theorem C.5, one can obtain
k8
P[Fx} 2 K +1
for all k= = O,..., K +1 1. Consequentl,, EK+1 implies
K
d
ΣΣ
Vh. 2A
2
K=
with probability at least
8. Hence, with (87) we get
k
K
4A max b
[f(x)))
< 7(1 - B1)
(97)
keb,K
k=
What is more
K
d
d
max LeO,K,eiL..
b 5g + 7m
Σ
3
22
+ 3
Σ ( (00%,)2 - -Ec. [(022.]] )²)
k=U
1=1
1=1
d
+
Bg. [0%%,)]]
+3 Σ
(0%
58

---

Clipping Improves Adam-Norm and AdaGrad-Norm
where Tm 1y for Clip-M-AdaGradD and 7mm " K+I for Clip-AdamD. Also the event Ex+1 implies
A m (1 31)
(0% - Eg, [0E..)] + Bgg [0RR.)])
4
R==
K
Am bo 4y
(0h
(0,)) )
k=0
due to the bounds @ and @ (exchanging b to Cm in these terms allows to obtain the same bounds for them). Therefore,
K
31
"m 31 2 1g1 - (11)
max KEO, IET
b2 - by
31mm
[f(xx)]|
+
(98)
4y
4L2²
k=
Denoting the left-hand side of (97) as Sk, squaring both sides and substituting (98) gives the quadratic inequality on Sk. Solving it, we have
24A² 2
2 ATH
1669 A
3mm
37m C. 63,43
SK S
+
+
+ 16
B1)3
(1
B1)4
21
31)2
473(1 =11
4T B1)
48A 7m
2m
4
1m Cm
Tm c 1ig
< max
7(1 31)" $1
72(11
31
73(1 32)2
LA 32)
16A max
1227m
bu
mm A
1 B1
7(1 - 31)22
L - 31)
After substitution of 7m and division by K + 1, similar to the Theorem C.S, we conclude the final result:
K
[V
K +
K=
1 In
VdLA In K-1
VIA
Σd 1i= 0.0
K+1 (K +1+
o
O max
(1)
Ta
(1- B1)
d i== o
(LA)
In 20 K+1
(1 - 31) a-1
(K + 1) 8
with probability at least 1-6. 5.
59

---

Clipping Improves Adam-Norm and AdaGrad-Norm
AdaGrad Clip-AdaGrad
AdaGradD vs Clip-AdaGradD
AdaGrad
AdaGradD
Clip- AdaGrad
Clip-AdeGradD
21100
10
10a
10a
4000
8000
2000
6000 Number of iterations
10000
Number Iterations
Figure 3: Performance of different versions of AdaGrad (with and without clipping/delay) with stepsize 1/128 on the quadratic problem.
AdaGrad vs Clip-AdaGrade tuned stepsizes, scaled noise
Adam vs Clip-Adam, tuned stepsizes, scaled noise
109
AdaGrad, y=1 1= Alarad, y= 1.A 0.005
10
10-2
10
10"
10
10-6
10
1014
Adam, y= 1/64
10-10
10 10
Clip-Adam, 0.01, 0.005
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Number of iterations
Number of Iterations
Figure 4: Performance of different versions of AdaGrad and Adam (with and without clipping) on the quadratic problem with scaled noise.
D. Numerical Experiments: Additional Details and Results
D.I. Quadratic Problem
In addition to the results provided in the main text, we compare the performance of different versions of AdaGrad with y = =1/128. The results are given in Figure 3. One notice that methods with clipping consistently outperform the methods without clipping for this stepsize well.
Moreover, we provide the results of similar experiments for Adam with and without clipping/delay in Figure 5 (for 3 = 0.9 and B2 = 0.999). In general, the observed results for Adam-based based methods are very similar to the ones obtained for AdaGrad: clipped versions Adam show better high-probability convergence than non-clipped ones.
We also run AdaGrad and Adam and their clipped analogs for the same problem with scaled noise, that is, instead of & defined in Section 4, use 5/100. The clipping level is chosen 100 times smaller well, i.e., À 0.005. Stepsizes tried 1, 16 62 for Adam, we tried 16 20 64: 100 for Clip-Adam, we tried 7 16 20 64 100 The results are reported in Figure 4. As in the original experiments, the methods with clipping achieve a better optimization error with high probability.
tuned for each method: for AdaGrad, we tried y 1, 16 20 ga poo for Clip-AdaGran I.
1
1
D.2. ALBERT Base v2 Fine-tuning
Further details. In our experiments with finetuning of the ALBERT Base v2 model on Col.a la and RTE datasets, we follow standard practice of usage Adam, we apply bias correction to Adam and Clip-Adam. For the delayed version Clip-AdamD we do not apply bias correction and tune by instead.
We used linear warmup with warmup ratio being 0.1, and hyperparameters were 31 0.9, 82 0.999, b c1, where
60

---

Clipping Improves Adam-Norm and AdaGrad-Norm
Adam Clip-Adam
AdamD Clip-AdamD
AdamD Clip-Adamb
108
10
10"4
10
10"
Adam
10.-
Clip-Adam
4000
8000
10000
4000 Number of Iterations
6000
20000
Number of Iterations
Adam vs Clip-Adam
AdamD Clip-AdamD
Adam
AdamD
1.0
10"
Clip Adam
Clip AdamD
10--
10
10
10
2000
4000
5000
10000
2000
4000
6000
10000
Number of Iterations
Number of Iterations
Adam vs Clip-Adam
AdamD vs Clip-AdamD
Adam
109
AdamD
Clip-Adam
Clip-AdamD
10-4
10
1005
10'7
10"4
2000
4000
6000
8000
30000
2000
4000
6000
B000
10000
Number of Iterations
Number of Iterations
Figure 5: Performance of different versions of Adam (with and without clipping/delay) under the standard setting (B1 0.9, 32 0.999) with stepsizes y 1 (first row) and 1/16 (second row) on the quadratic problem.
1 (1, 1I E IRd. We tuned batchsize and stepsize for Adam and selected best values from {4, 8, 16, 32} for the batchsize and from {10-6, 3- 33-10-5 10-6, 1005,00.0 3.3 10-5 10-5,10-4) for 7. For the CoLa dataset, the best batchsize was 16 and = 10-5, and for the RTE dataset, the best batchsize was 8 and 7 10-5 We tested noordinate-wise clipping with A E f0.001, 0.002, 0.005,000 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1} and layer-wise clipping with E (0.1, 0.2, 0.5, 2, 5, 10). For the CoLa dataset, the best results were achieved with À for layer-wise clipping and 0.02 for coordinate-wil wise clipping, and for the RTE dataset, the best results were achieved with À for layer-wise clipping and A 0.005 for coordinate-wise clipping.
Noise histograms. The histograms are provided in Figure where we additionally estimate the mean and standard deviation and plot the density of the normal distribution with these parameters (black curve). For the CoLa dataset, the noise distribution changes significantly after the start of the training, and its mean drifts to the right. However, the standard deviation does not change significantly, and, more importantly. metrics Pmn and Pen remain quite large, showing that the distribution is significantly heavy-tailed. In contrast, for the RTE dataset, the noise distribution does not drift significantly, and, interestingly, PeR decreases towards the end of training and becomes zero, while PmR stays in the interval [5, 10). Therefore, the noise distribution has much heavier tails for CoLa than for RTE.
Additional results. In the main part of our work, we present the results for Clip-Adam with layer-wise wise clipping. In Figure 7, we provide the results in the case of coordinate- wise clipping. general, they are quite similar to the ones given
61

---

Clipping Improves Adam-Norm and AdaGrad-Norm
CoLa stepa
Cota, ches
Cola. 356
Calo, 534 cheps
26.03 2.0
22.34
23.03
13
Ac- 10000
3.05
Pir 13002
Au- 6167
642
049
Nolie ccm
Nodio com
RTE
C/e 5.54
3CB
C-m 0.33
o 3.00
Ohi 19707
do 10000
(hi 3333
0.45
0.43
942
041
65 nom
Sostew m.mm
Holse ncm
Notoe 12m
Figure 6: Gradient noise evolution for Adam on CoLa (the first row) and RTE (the second row) datasets. Histograms were evaluated after 0 steps, after x 1/3 and x 2/3 of all steps, and in the end.
CoLa, Adam Cllp-Adam
RTE, Adam vs Clip-Adam
Cip-Adan
Alp-Adam
0.075
Adam
0.70
Adam
0.68
9375
0.66
va loss
0.552
0.64
0:23
0.500
8:75
0450
0.5
300
200
300
400
200
90
200
100
Number of steps
Number of sleps
Figure 7: Validation loss for ALBERT Base v2 fine-tuning task on the CoLa and RTE datasets. Clip-Adam is used with coordinate-wise clipping (A = 0.02 for CoLa and A = 0.005 for RTE).
in Figure 2, indicating that both clipping strategies can be useful in practice and improve the high-probability convergence of Adam.
We also conducted experiments with Alim-A and compared its performance with Clip-Adam. We tuned parameter e defining b as = e1, where 1 = (1, 1,......, 1)T E Rd. Tuning was performed in two phases: during the first phase, we selected the best values of c from (10-s, 10-7, 10-5,10-3 10-5, 10-4, 10-3, 10-3,1100 10-2), and then for every selected we tried e E {0.2E, 0.52, 0.82, 26, 5é, 8E). In the case of CoLa dataset, the best e was 10 6, and in the case of RTE dataset, the best E was 2- 10 6.
The results are p in Figure 8 and show that Clip-AdamD performs worse than Clip-Adam, especially on CoLa dataset. However, it is worth mentioning that the clipping level was selected the same for both Clip-Adam and Clip-AdamD, Moreover, we have not tried to use bias correction for Alim-AdamD that could also improve its performance. Finally, the tuning of e parameter over multiple runs can also improve the result of Clip-AdamD.
Finally, we also conducted similar experiments with BaaGGrad-based methods with and without clipping/delay. Parameter yy and batchsize were tuned across the same values as in the case of Adam. Moreover, similarly to the experiments with Adam, we used standard layer-wise clipping for AdaGrad-based methods since it gave better results. The final parameters are (i)
'In the plots, we use the name Clim-RAdamD, which is equivalent to Clip-AdamD as explained at the beginning of Appendix C.
62

---

Clipping Improves Adam-Norm and AdaGrad-Norm
CoLa, Clip-Adam P-RAdamD
RTE. Clip-Adam vs Clip-RAdamD
0.72
C- MAdamD, 1D
Oip-RAcamD, n=1
0.825
ClipAAaam
0.70
Cip Adam
0.600
0.88
0273
0.66
va 1055
0.550
Va
0.04
0.000
3475
0450
300
202
300
100
500
50
100
350
300
250
300
Number of steps
Number of sleps
Figure 8: Validation loss for ALBERT Base v2 fine-tuning task on the CoLa and RTE datasets.
7 = 10-4, batchsize 4, À = 5 for (Clip-)AdaGrad on CoLa dataset, (ii) = 10-4, batchsize 16, À = for (Clip-)AdaGrad
on RTE dataset, (iii) y = 10 4 batchsize 4, À = 5 for (Clip-)AdaGradd on CoLa dataset, and (iv) y = 10 10-4, batchsize 16, 0.1 for (Clia-)AdaGradD on RTE dataset. The results are presented in Figure 9. For this particular case, there no big difference between versions of AdaGrad with and without clipping, and only for CoLa dataset we see that Clip-AdaGrad has much smaller error band than AdaGrad.
D.3. Scaling Up:
Fine-Tuning of 355M Model
Setup. We replicate the setup from Appendix D.2 for fine-tuning the 355M parameter RoBERTa Large model (Liu et al., 2019) the two GLUE (Wang et al., 2018) datasets: QNLI (116k question question-answer answer pairs) and CoLa (10.7k linguistic acceptability examples). Keeping identical hyperparameters, including the learning rate scheduler, warmup ratio, and optimizer parameters (31, B2). we employ a moderate batch size of 16 for both datasets to ensure comparability with the previous finding. Through extensive testing of layer-wise clipping with À E 0.1, 0.2, 0.5, 1, 5, 10, we identified X = 1 as the best value for both tasks, aligning with prior work specialized in fine-tuning of large language models (Yang & Ma, 2022). The best values that we have selected this part are used to build noise histograms and compare algorithms with and without clipping.
Noise Histograms. We also build the noise histograms (see Figure 10) for the RoBERTa Large model. In the histogram, we quantitatively present the measure the beilyesailedness of the noise following the recipe from (Gorbunov et al., 2022). After fine-tuning the model with checkpointing the full dataset (QNLI or CoLa), we compute the true gradient V f(x:) through many gradient accumulation steps. From identical initial checkpoints, we sample 1000 mini-batched gradient estimators for CoLa and 100 for QNLI (all of them are with the batch size of 16), calculating the norm differences V (z) V (x)) for histogram construction. As in Section and Appendix D.2, we assess the heavy-tailedness of the noise using the metrics PmR and Pen- Both metrics remain consistently large throughout training, indicating that the noise exhibits significant heavy-tailed behavior. Furthermore, the histogram profiles closely resemble the Lévy o-stable distribution, as shown in Figure 10.
Comparison of Methods With and Without Clipping. We replicate earlier setup with key modification: the number of random seeds is reduced from 100 to 5, due to computational constraints when scaling to model-partieular,, given QNLI's substantially larger size compared to CoLa or RTE. At each step, we compute the median validation loss, along with the 5-th and 95-th percentiles.
The comparison between Adam and Clip-Adam shown in Figure 11, while the comparison between AdaGrad and Clip-AdaGrad presented in Figure 12. Notably, for the new model and across both datasets, the clipped variants consistently outperform their unclipped counterparts.
63

---

Clipping Improves Adam-Norm and AdaGrad-Norm
CoLa, Clip-AdaGrad vs AdaGrad
RTE, Clip-AdaGrad AdaGrad
Clip AdaGrad
0.74
CipvAdeGrad
AdsGred
0.72
MaGGrad
0.00
0.68
loss
0.55
0.08
0.50
2.52
0.50
0.45
0:30
230
750
1000
1230
1500
11.30
2000
200
120
160
Number steps
Number of steps
CoLa, Cilp-Adaaraac-eelayedd Clip-AdaGrad
RTE, Clip-Ad&Grad- Dalaaydd vs Clip-AdaGrad
Clip AdaGrad Delayed ClipAAaarrad
0.14
Clp-AcaGrad-Delaaee
0.45
0.77
Cip-AcaGrad
0.50
loss
Val loss
0.66
0.55
0.64
0.62
0.58
250
1000
125h
1900
13%0
100
Number silepss
Number steps
Figure 9: Validation loss for ALBERT Base v2 fine-tuning task on the CoLa and RTE datasets.
steps
ONL, 1400 stops
4:255
0.2
25 714
4:300
53 BA4 20300
7:33
15,
20.025
0.35
Cendity
630
0.5
6.85
Notee norm
Nais nam
Notus nom
Nobrenam
Cola,, steps
Cola, 333 steps
Cul... 567 stapa
Esli: 1030 shope
050
630
D- 5:13
9.71
23-32
Per 10002
6.58
A1- 10303
Pa- 9657
Deneiy:
1.34
652
6:33
Raice Froms
20
A/6
Notto nomm
120
Figure 10: Gradient noise evolution for Adam on QNLI (the first row) and CoLa (the second row) datasets during RoBERTa Large fine-tuning. Histograms were evaluated after 0 steps, after 1/3 and x 2/3 of all steps, and in the end.
64

---

Clipping Improves Adam-Norm and AdaGrad-Norm
QNU, Adam Clip-Adam
CoLa, Adam vs Clip-Adam
0.7
cip-bdam
val loss
0.55
0.55
0.2
1000
2000
3006
a032
5000
230
420
1506
Number of steps
Number of steps
Figure 11: Validation loss for RoBERTa Large fine-tuning task on the QNLI and CoLa datasets. Clip-Adam is used with layer-wise clipping.
QNLI, AdaGrad vs Clip-AdaGrad
CoLa, AdaGrad vs Clip-AdaGrad
Clip-AdaGrad AdaGrad
Clp-AdaGrad
0.7
AdaGrad
0.65
val 1os
0.60
0.4
0.55
0.2
0.50
1000
2000
3000
4003
5000
600D
1000
8000
MBD
1003
1500
2000
2500
Number of steps
Number of steps
Figure 12: Validation loss for RoBERTa Large fine-tuning task on the QNLI and CoLa datasets. Clip-AdaGrad is used with layer-wise clipping.
65


Reviews:
[{"review_id": "BDnT3E2D4v", "reviewer": "Reviewer_H5h1", "summary": "This paper suggests that clipping enables high-probability convergence (with polylogarithmic dependence on the confidence level δ) for Adam-norm/AdaGrad-norm under heavy-tailed noise. In contrast, without clipping, Adam/AdaGrad has inverse-power dependence.\nThe authors provide some numerical results to support this result.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and positive feedback. We also thank you for your useful comments, which we have addressed below.\n\n>1:**It’s not the specific settings but rather the scale that I’m concerned with. I believe the experiments can be much more comprehensive to claim a solid support of the theory results.**\n\nA: We agree that the scale of our experiments can be further improved, and we can provide additional numerical results for larger models and datasets. However, the main contribution of our paper is primarily theoretical. Therefore, we see our experimental results as complementary contributions extending theoretical findings.\n\n>2: **The obvious weakness of this work is that the versions of Adam/AdaGrad are actually normed…**\n\nA: We point out that we also analyze coordinate-wise versions of AdaGrad and Adam (with $\\beta_1 = 0$) in Appendix C.4, as explained in the very end of Section 3. Moreover, we generalized our proof to the case of $\\beta_1 > 0$ (please, see our response to Reviewer GE8p).  Unfortunately, due to the page limitations of the main part, we had to defer these results to the Appendix. If the paper gets accepted, we will use an additional page in the main part to discuss the results on coordinate-wise versions of AdaGrad and Adam with clipping in more detail.  We also kindly ask you to check our response to Reviewer RQzs (comments 2 and 10).\n\n>3: **I kind of received an impression that various versions of algorithms are analyzed not because they are all important but because they can be proved. It would be nice to see how the choice of conditions under which methods are analyzed is made, or why analyzing all of these would be worthwhile.**\n\nA: Thank you for mentioning this point of view. The main goal of this paper is to provide a comprehensive answer to the questions formulated on the second page, right before Section 1.1.  In general, the answer could potentially depend on the choice of the convexity and the stepsizes. Therefore, we analyze both non-convex and convex problems and derive the results for the scalar (a.k.a. “-norm”) and coordinate-wise versions of AdaGrad and Adam with and without delayed stepsizes. We believe that the provided analysis is quite comprehensive and covers many different cases (though not all possible ones for the sake of having the paper of a reasonable length; see also our response to Reviewer RQzs, comment 10). That is, we believe that the main research questions formulated in the paper are adequately addressed, i.e., we show that standard AdaGrad and Adam (with and without delayed stepsizes) do not enjoy logarithmic dependence on $1/\\delta$ in their high-probability complexities and clipping provably improves their high-probability convergence.\n\n>4:**Numerical results for CLIP-Adam do not seem strong or much differentiated.**\n\nA: We believe that the main theoretical findings of this paper are properly illustrated and complemented by our numerical results. We kindly ask the reviewer to clarify the concern.", "claims_and_evidence": "The claim of this work is mainly supported by providing the theoretical results and comparing it to the settings / results in previous works.\nOverall the paper is written clearly to deliver the ideas.", "methods_and_evaluation_criteria": "The authors attempt to validate the idea on both synthetic and realistic problems in numerical experiments.", "theoretical_claims": "I’ve skimmed through proofs of failure cases in Appendix B. I’ve not seen the proofs for the clipping results.", "experimental_designs_or_analyses": "It’s not the specific settings but rather the scale that I’m concerned with. I believe the experiments can be much more comprehensive to claim a solid support of the theory results.", "relation_to_broader_scientific_literature": "This work renders a theoretical contribution to the optimization for machine learning community in particular for adaptive methods and more broadly stochastic methods. The authors present a balanced review over prior works in the Related Work section and the New Upperbound section, where one can find how this work compares to previous works.", "essential_references_not_discussed": "As far as I’m concerned, the paper seems to address previous / concurrent related works well enough.", "other_strengths_and_weaknesses": "* The obvious weakness of this work is that the versions of Adam/AdaGrad are actually normed ones, i.e., Adam-norm/AdaGrad-norm, rather than the original form. This is a concern on both theory and practice sides. I think this should be discussed more clearly / up front in the paper rather than at the end of the theory result.\n* I kind of received an impression that various versions of algorithms are analyzed not because they are all important but because they can be proved. It would be nice to see how the choice of conditions under which methods are analyzed is made, or why analyzing all of these would be worthwhile.\n* Numerical results for CLIP-Adam do not seem strong or much differentiated.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V1lmaIlMML", "reviewer": "Reviewer_9uKJ", "summary": "This work examines adaptive optimization methods, specifically variants of Adam and AdaGrad, in settings with heavy-tailed noise. The authors establish that for Adam and AdaGrad with momentum, achieving a polylogarithmic dependence on the confidence level is impossible. In contrast, they show that the clipped versions of Adam-Norm and AdaGrad-Norm provide high-probability convergence guarantees, with additional results for the clipped versions of Adam and AdaGrad without momentum. Numerical experiments further confirm the improved performance of the clipped variants.\n\n## update after rebuttal\n\nI thank the authors for their response and I updated my score.\n\nI recommend the authors to better reflect the paper is mainly focused on the norm versions instead of the element-wise versions per the comments of the other reviewers regarding Algorithm 1.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback that helped to improve our paper.\n\n>1:**Time-dependent noise.** \n\nA: Thank you for spotting this. We will rewrite Assumption 1.1 to explicitly highlight that we allow time-dependent noise. Such assumptions are relatively standard for stochastic optimization with streaming oracle [1-3]. Moreover, many existing convergence upper bounds hold for time-varying noise as long as the corresponding moment bound is satisfied for each step [4-6]. We will add these clarifications to the final version of our paper. \n\n>2:**Coordinate-wise methods & momentum.**\n\nA: In the abstract, we claim that we show that clipping fixes AdaGrad-Norm and Adam-Norm. In Section 1.1, we made a typo in line 65: it should be “without momentum” instead of “with momentum”. We also explicitly mention that Clip-AdaGradD and Clip-AdamD are analyzed without momentum. **To address this limitation of our paper, we generalized our proofs for the methods with coordinate-wise stepsizes to the case of $\\beta_1 > 0$ – please see our response to Reviewer GE8p.** We promise to add the complete proof to the final version of our paper.\n\n>3:**Lower bound & Assumption 1.4.**\n\nA: Our lower bounds can be extended to support Assumption 1.4, if we modify $f$ as follows: \n\n$$f(x) = \\begin{cases}\\frac{1}{2}x^2,& \\text{if } |x| < \\nu,\\\\\\\\ \\nu\\left(|x| - \\frac{1}{2}\\nu\\right),& \\text{if } \\nu \\leq  |x| \\leq D,\\\\ \\nu\\left(D - \\frac{1}{2}\\nu\\right),& \\text{if } |x| > D, \\end{cases}$$\n\nwhere $D > |x_0| > \\nu$. Then, the proofs remain the same, and the problem satisfies Assumption 1.4.\n\n>4:**Lower bound & time-independent noise.**\n\nA: If we assume that the noise is i.i.d. for each step, e.g., the same as for $k = 0$ in formula (16), then for the provided example of function and oracle M-AdaGrad/Adam should also have inverse-power dependence on $\\delta$ in their high-probability complextites – this is our conjecture. However, deriving the lower bounds for this case is technically more difficult because the explicit form of the iterates becomes more involved than in Lemma B.1 (due to the summation of the squared norms of stochastic gradients in the stepsize). We will discuss this more explicitly in the final version of the paper.\n\n>5: **Why Assumption 1.4?** \n\nA: The main difficulty comes from the dependence of $b_t$ and $g_t$ in the methods without delayed stepsizes. The existing approaches typically use boundedness of the variance and the norm of the gradient (see Lemma 5.1 in [7]) or assume that the noise is sub-Gaussian [8] to tackle this issue. In the heavy-tailed noise regime, these assumptions do not hold. Therefore, we use Assumption 1.4, which is a relaxation of the assumption used in [9] (see also our discussion of Theorem 3.3 on page 7). More precisely, to decouple $b_t$ and $g_t$ in the analysis, we multiply the inequality above (67) by $b_t$. However, it eventually leads to the non-trivial weighted sum of function values: the first sum in the RHS of the first row on page 44. After small rearrangements, we get the term $\\sum_{t=1}^T \\left( \\frac{b_t}{p_t} - \\frac{b_{t-1}}{p_{t-1}} \\right)(f(x_t) - f_\\ast)$ that we estimate using Assumption 1.4. We are not aware of the alternative ways of analyzing versions of AdaGrad/Adam or closely related methods in the heavy-tailed noise regime.  \n\n>6:**On the hyper-parameters**\n\nA: For AdaGrad-Norm *without clipping*, similar results cannot be obtained with logarithmic dependence on $1/\\delta$ due to Theorem 2.1. However, it is an interesting open question whether it is possible to show convergence for Clip-AdaGrad-Norm with a choice of hyper-parameters agnostic to $L,\\sigma, \\alpha$, and $R$, in the heavy-tailed noise regime. We leave this question for future work. \n\n---\n\nReferences:\n\n[1] S. Ghadimi & G. Lan. Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms. SIOPT 2012\n\n[2] N. J. A. Harvey et al. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv:1909.00843\n\n[3] A. Sadiev et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023\n\n[4] J. Zhang et al. Why are Adaptive Methods Good for Attention Models? NeurIPS 2020\n\n[5] A. Cutcosky & H. Mehta. High-probability bounds for Non-Convex Stochastic Optimization with Heavy Tails. NeurIPS 2021\n\n[6] T. D. Ngyen et al. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS 2023\n\n[7] A. Défossez et al. A Simple Convergence Proof of Adam and Adagrad. TMLR 2022\n\n[8] Z. Liu et al. High Probability Convergence of Stochastic Gradient Methods. ICML 2023\n\n[9] S. Li & Y. Liu. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023", "claims_and_evidence": "The paper provides an analysis of several variants of Adam and AdaGrad to support the claim that clipping improves performance in the presence of heavy-tailed noise. However, some aspects of the evidence could be more comprehensive.  \n\nFirst, the noise model deviates from the standard gradient oracle model, as the noise may depend on time. This is only briefly mentioned (in line 90 of the second column) and is not explicitly detailed in Assumption 1.1, despite being a crucial component for establishing the lower bound (see the noise distribution in line 928).  \n\nAdditionally, while AdaGrad and Adam perform poorly without clipping, the results for clipped coordinate-wise methods remain incomplete, as momentum is not incorporated. So, claiming in the abstract that clipping fixes Adam is not fully proven.\n\nFinally, Theorem 3.3 is established using Assumption 1.4, whereas the lower bound does not support this assumption.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The paper contains many technical details, most of which are provided in the appendix. The reviewer focused on the lower bound of M-AdaGrad and the upper bound of Clip-M-AdaGradD/Clip-AdamD-Norm presented there.  \n\nAside from the non-standard noise model, which the reviewer noted is used in the appendix, the examined parts appear to be correct.", "experimental_designs_or_analyses": "The experiments align with the authors' claims. Notably, Adam appears to fail completely with a reasonable probability in the CoLa experiment (Figure 2), which is somewhat surprising. The reviewer would expect that, with properly tuned parameters, Adam would still be able to learn, even if the clipped version performs better.", "relation_to_broader_scientific_literature": "The paper aims to extend observations from Clip-SGD to adaptive methods, which is a valuable direction for advancing our understanding of optimization with heavy-tailed noise.", "essential_references_not_discussed": "Essential references are discussed.", "other_strengths_and_weaknesses": "**Strengths**\n- The analysis of widely used optimization methods under heavy-tailed noise is an important topic.\n- This paper establishes results for a broad range of adaptive variants.\n  \n**Weaknesses**\n- As mentioned earlier, the connection between scalar and coordinate-wise versions is limited.\n- The large number of details, different variants, and assumptions make it challenging for readers to compare the positive and negative results presented in the work.", "other_comments_or_suggestions": "No further comments.", "questions_for_authors": "- Can the lower bounds be modified to accommodate stochastic gradients that does not depend on the time? What modifications are required and how difficult is the task?\n- Can an improved lower bound support assumption 1.4?\n- What is the difficulty in removing assumption 1.4 from Theorem 3.3?\n- What is the main difficulty in accommodating both coordinate-wise algorithms and momentum when discussing heavy-tailed noise?\n- With light-tailed noise, AdaGrad-Norm converge even without accurate specification of the hyper-parameters (the bound itself degrades according to the hyper-parameters, but the algorithm still converge). Can such results be obtained with heavy-tailed noise?\n\nOverall, the paper provides new insights and results, but the connection between claims and results can be improved.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RfqtVN8fvb", "reviewer": "Reviewer_RQzs", "summary": "This paper provides a loss function that AdaGrad and Adam have bad high probability convergence when the noise is heavy-tailed. Then they show a desirable convergence rate for AdaGrad-Norm and Adam-Norm with clipping gradient to fix the heavy-tailed noise issue. They conduct experiments to show that clipping can help Adam optimize faster.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback that helped improve our paper. The requested numerical experiments can be found here: https://anonymous.4open.science/r/Clip-Adam-Norm-and-Clip-AdaGrad-Norm-1E8A/ (folder \"rebuttal\").\n\n>1: **Algorithm 1.**\n\nA: We will add \"-norm\" to method names in Algorithm 1. Section 1.3 provides coordinate-wise versions of AdaGrad/Adam.\n\n>2:**Gap between experiments and theory.**\n\nA: We include coordinate-wise methods with $\\beta_1 = 0$ in Appendix C.5 (end of Section 3). **Our proofs now cover coordinate-wise stepsizes—see our response to Reviewer GE8p**. In Section 2, our results hold in 1D, where coordinate-wise and norm/scalar versions coincide. Hence, the theory aligns well with quadratic problem experiments. The Clip-Adam experiment without delay, though not analyzed theoretically, complements our theory.\n\n>3:**Why ALBERT?**\n\nA: Mosbach et al. (2020) motivate our choice. RoBERTa wasn't used with gradient clipping in their experiments. Due to computational constraints and the need for 100 runs per method for high-probability convergence, we used a smaller model (ALBERT) instead of BERT.\n\n>4:**Small datasets.**\n\nA: We use two of three datasets from Mosbach et al. (2020). We can add results on larger datasets if the paper gets accepted.\n\n>5: **Training loss.**\n\nA: New plots are available in the anonymized repository.\n\n>6: **On Theorem 2.1.**\n\nA: Let us address your concerns on the example of AdaGrad with momentum (Theorem B.4). The same reasoning holds for other methods as well.\n\n1. We focus on worst-case guarantees [1], estimating complexity for the worst possible problem given the method’s parameters. This allows a resisting oracle [2], where the problem depends on $\\varepsilon$ and $\\delta$. This is a classical approach.\n\n2. We require $x_0 > \\sqrt{2\\varepsilon} + 3\\gamma$. Since typically $\\varepsilon, \\gamma \\ll 1$, this assumption is mild. The stepsizes in Theorems 3.1-3.3 do not contradict Theorem 2.1: the results are derived for *different methods*. For $R, \\sigma, M, L, b_{-1} = O(1)$ and large $K$ in Theorem 3.3, Theorem B.4 applies.\n\n3. The fact that AdaGrad/Adam lack logarithmic dependence on $1/\\delta$ even for $\\alpha = 2$ strengthens our results. Some works [3] label $\\alpha = 2$ case as heavy-tailed. Our setting, where noise is zero except in the first iteration, reinforces our findings: a large first stochastic gradient drastically reduces stepsize.\n\n4. The stochastic gradient noise is $\\sigma \\xi_k$, with $\\mathbb{E}[\\xi_0^2] = 1 \\Longrightarrow \\mathbb{E}[\\sigma^2\\xi_0^2] = \\sigma^2$.\n\n>7: **The noise in the quadratic experiment seems too large.**\n\nA: Figures 1, 3, and 4 show results for different $\\gamma$. Methods with clipping consistently outperform those without. Additional experiments with lower noise (scaled by 100) and tuned stepsizes are in the anonymized repository.\n\n>8: **Fine-tuning experiment?**\n\nA: Randomness stems from the seed that determines mini-batch sampling order.\n\n>9: **Results from Kunstner et al. (2023)**\n\nA: We will discuss this paper in the final version. Their work shows Adam outperforming SGD even in full-batch settings -- this observation is unrelated to stochasticity. Our focus is on high-probability convergence of AdaGrad/Adam-based methods, showing that without clipping, they have poor high-probability complexities, similar to SGD. Thus, our results complement Kunstner et al. (2023) by highlighting the necessity of gradient clipping for high-probability convergence.\n\n>10:**Scalar or coordinate-wise methods?**\n\nA: We analyze both scalar (norm) and coordinate-wise versions of AdaGrad/Adam, studying both in experiments.\n\n>11:**Introduction.**\n\nA: We will rewrite the introduction for clarity on considered methods.\n\n>12:**Definition of heavy-tailed noise.**\n\nA: The noise is heavy-tailed if it satisfies Assumption 1.1.\n\n>13:**Discussion of Theorem 2.1.**\n\nA: We will expand the discussion, incorporating the points above.\n\n>14: **Dependence of $K$ on $\\varepsilon$ and $\\delta$ in Theorems 3.1-3.3.**\n\nA: The complexity results are presented in a standard way for the optimization literature (e.g., see Theorem 2.4 from [4]). The hyperparameters also depend on $\\varepsilon$ and $\\delta$: even standard SGD with constant stepsize converges only to the neighborhood of the solution for strongly convex smooth problems, i.e., one has to choose the stepsize to be dependent on the target error. We also provide the rates in Appendix C (see Theorems C.5, C.7, C.9, C.12).\n\n---\n\nReferences:\n\n[1] A. Nemirovsky & D. Yudin. Problem complexity and model efficiency in optimization. J. Wiley @ Sons, New York (1983)\n\n[2] Y. Nesterov. Lectures on convex optimization. Springer (2018)\n\n[3] E. Gorbunov et al. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. NeurIPS (2020)\n\n[4] S. Ghadimi & G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization (2013)", "claims_and_evidence": "1. Theorem 2.1 can’t be viewed as an example of bad dependence on $\\delta$. See detailed comments in theoretical claims. \n2. Algorithm 1 is not a proper definition for Adam/AdaGrad. Instead, it should be Adam-Norm/AdaGrad-Norm because $b_t$ is the weighted average/sum of the square of gradient norm rather than entry-wise square of gradient. \n3. There is a gap between the experiments and the theory. All the theoretical results are for Adam-Norm/AdaGrad-Norm but the experiments are done with Adam/AdaGrad.", "methods_and_evaluation_criteria": "High-probability convergence is preferable to in-expectation convergence, and heavy-tailed noise is a real issue in practice, as confirmed by this paper and prior work. While the fine-tuning experiment is reasonable, I am curious why the authors chose ALBERT over BERT and RoBERTa. Additionally, CoLA and RTE are relatively small datasets, though I don’t doubt that clipping would also be beneficial for larger datasets, given its common use in practice. However, it would be more informative to compare training loss rather than validation loss, as the focus is on optimization rather than generalization.", "theoretical_claims": "I checked the proof of theorem 2.1 and found the statement and loss example problematic. I have listed the specific problems below but in short I find this theorem completely useless. We can easily get similar result even for deterministic Adam because the key idea in the loss example is to make $x_0$ far enough from $x^*$ so that it can not enter the region with small loss because its moving distance is restricted when $T$ and stepsize $\\gamma$ are not large enough. \n1. This **cannot** be viewed a polynomial dependence on $\\delta^{-1/2}$ and $\\epsilon^{-1/2}$ because both the function and noise depends fixed $\\epsilon$ and $\\delta$. They are defined by the specific $\\epsilon$ and $\\delta$ and then the authors show that $T$ needs to be larger than $\\frac{R}{\\gamma} (\\frac{\\sigma}{\\nu \\sqrt{2 \\delta}}-1)$. For each fixed function, you instead need to show the convergence rate as a function of $\\epsilon$ and $\\delta$. \n2. It is inapproriate to choose initial $x_0$ depending on stepsize $\\gamma$. Specifically, clip-Adam will get the same negative result under the same setting so theorem 2.1 isn't a valid example for failure of Adam without clipping. In comparison, stepsize is decided based on the lipschitzness of loss function and initial distance $R=||x_0-x^*||$ in the positive result theorem 3.1-3.3. \n3. The noise distribution is not heavy-tailed at all since there is only noise at the first update and the noise even has bounded variance. It is very different from the heavy-tailed noise people find in practice. \n4. The provided example doesn’t satisfy assumption 1.1 as claimed in the theorem statement. The variance of noise is always $1$ rather than any choice of $\\sigma$.", "experimental_designs_or_analyses": "1. The noise in the quadratic experiment seems too large. I feel the failure of Adam comes from the large magnitude of noise rather than heavy tail. If large gradients are accumulated in $b_t$ without clipping, the effective stepsize of AdaGrad will be much smaller than the effective stepsize of Clip-AdaGrad, which may be the real reason of AdaGrad’s failure. I’d like to see how the result will change if you use 100 times smaller noise. The distribution is still heavy-tailed. Or a fair comparison between AdaGrad and Clip-AdaGrad is to thoroughly tune the learning rate in a large range for each one. Comparing them under the same learning rate rather than the optimal learning rate is not appropriate. \n2. What is the randomness in the fine-tuning experiment? Is it just the seed that determines the batch order in training set? It is hard to believe that some seeds will lead to no improvement to val loss.", "relation_to_broader_scientific_literature": "It can help understand the relationship between vanilla optimization algorithms and the tricks like clipping that people use in practice.", "essential_references_not_discussed": "[1] conducted experiments to show that heavy-tailed noise is not the major factor for the gap between Adam and SGD. They point out that Adam should be more similar to sign descent when handling heavy-tailed noise. I think the authors should discuss more whether their results on Adam-Norm can really suggest anything for Adam when dealing with heavy-tailed noise because Adam-Norm makes Adam completely different from sign descent. \n\nReferences\n\n[1] Kunstner, F., Chen, J., Lavington, J. W., and Schmidt, M. Noise is not the main factor behind the gap between SGD and Adam on Transformers, but sign descent might be. arXiv preprint arXiv:2304.13960.", "other_strengths_and_weaknesses": "Weaknesses:\n1. It is hard to understand whether the authors really want to analyze clipping for Adam or Adam-Norm. The title and the theoretical results are all about Adam-Norm. But the motivation for analyzing Adam-Norm under heavy-tailed noise is missing because the relevant literature mentioned in introduction focuses on Adam under heavy-tailed noise. If the goal is to analyze Adam through the middle step of Adam-Norm, then it is doubted how much insight can be provided by the theoretical results because Adam and Adam-Norm are completely different algorithms as shown in [2]. \n2. There is no clear definition of heavy-tailed noise. The failure example provided in theorem 2.1 is not heavy-tailed noise in my opinion. \n\nReference\n\n[2] Xie, S., Mohamadi, M. A., and Li, Z. Adam exploits $\\ell_\\infty$-geometry of loss landscape via coordinate-wise adaptivity. arXiv preprint arXiv:2410.08198.", "other_comments_or_suggestions": "The introduction should be carefully rewritten since the authors often confuse Adam with Adam-Norm. It seems that the authors initially focus on Adam but only get rigorous theoretical results for Adam-Norm so they need to make the current title. But the introduction and the paper should be revised to keep consistency.", "questions_for_authors": "1. I’d like to see some discussion on Theorem 2.1 to check if I misunderstand anything. See details in theoretical claims.  \n2. Why can we view Theorems 3.1–3.3 as a positive result? Even if the number of iterations doesn’t depend on $\\delta$, its dependence on $\\epsilon$ is even worse than Theorem 2.1 if Theorem 2.1 is valid.  \n3. I don’t understand why the hyperparameters need to depend on $\\delta$ in Theorems 3.1–3.3. If we want very high probability $1-\\delta$, then $A$ needs to be very large, and $\\gamma$ and $\\lambda$ will be very small. Does this suggest that the clipping effect needs to be very strong to achieve a good convergence result?  \n4. Can you conduct more experiments as suggested in the experimental design?  \n    a. Decrease the magnitude of noise in the quadratic problem and carefully tune learning rate.\n    b. Report the training loss of the fine-tuning experiment.  \n    c. Repeat the fine-tuning experiments with Clip-Adam-Norm.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6TCaqDyKRh", "reviewer": "Reviewer_GE8p", "summary": "This paper studies high probability convergence rate of clip-AdamNorm and clip-AdaGradNorm under heavy-tailed noise. The authors show that Adam/AdaGrad fails to get convergence rate with $log(1/\\delta)$ dependence if the noise is heavy-tailed. Then the authors show that gradient-clipping can fix this issue for AdamNorm and AdaGradNorm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive evaluation of our paper and constructive feedback.\n\n>1:**Analysis of Clip-Adam with $\\beta_1 > 0$**\n\nA: We revisited our proof and generalized it to the case of $\\beta_1 > 0$. The sketch of the proof with the key derivation is provided below. We promise to include the complete proof in the final version. \n\nThe main idea remains the same: we prove the descent lemma for the coordinate-wise approach as for the nonconvex case in scalar-wise form (Lemma C.3) and the rest of the proof follows the induction-based arguments (similarly to Theorem C.5). Applying smoothness and rewriting everything in the coordinate-wise form, we get an analog of formula (29) for Clip-AdaGradD and Clip-AdamD:\n\n$$f(x_{t+1}) - f(x_t) \\leq \\sum\\limits_{i=1}^d\\left[-\\gamma \\frac{\\nabla_{t, i} m_{t,i}}{b_{t,i}} + \\frac{L\\gamma^2}{2}\\frac{m_{t,i}^2}{b_{t,i}^2}\\right].$$\n\nThe next step is to derive an analog of formula (30) from page 26. We have:\n\n\\begin{align}\n\t-\\nabla_{t,i} m_{t,i} &= -\\beta_1 \\nabla_{t,i} m_{t - 1,i} - (1 - \\beta_1)\\nabla_{t,i} g_{t,i} \\\\\\\\\n&= -\\beta_1 (\\nabla_{t,i} - \\nabla_{t-1,i}) m_{t - 1,i} -\\beta_1 \\nabla_{t-1,i} m_{t - 1,i} - (1 - \\beta_1)\\nabla_{t,i} g_{t,i} \\\\\\\\\n&\\leq \\beta_1 |\\nabla_{t,i} - \\nabla_{t-1,i}| \\cdot |m_{t - 1,i}| -\\beta_1 \\nabla_{t-1,i} m_{t - 1,i} - (1 - \\beta_1)\\nabla_{t,i}g_{t,i}.\n\\end{align}\n\nUnrolling the recurrence and summing over $i$, we get\n\n$$ -\\sum\\limits_{i=1}^d \\frac{-\\nabla_{t,i} m_{t,i}}{b_{t,i}} \\leq -(1 - \\beta_1)\\sum\\limits_{k=0}^t \\beta_1^{t-k}\\sum\\limits_{i=1}^d\\frac{\\nabla_{k,i}g_{k,i}}{b_{t,i}} + \\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\sum\\limits_{i=1}^d\\frac{ |\\nabla_{k+1,i} - \\nabla_{k,i}| \\cdot |m_{k,i}|}{b_{t,i}}. $$\n\nApplying Cauchy-Schwarz inequality to the last term in the right-hand side and then using $L$-smoothness, we obtain\n\n\\begin{align}\n\\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\sum\\limits_{i=1}^d\\frac{|\\nabla_{k+1,i} - \\nabla_{k,i}| \\cdot |m_{k,i}|}{b_{t,i}} &\\leq \\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\left(\\sqrt{\\sum\\limits_{i=1}^d (\\nabla_{k+1,i} - \\nabla_{k,i})^2}\\right)\\left(\\sqrt{\\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{t,i}^2}}\\right)\n    \\\\\\\\\n&=\\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\|\\| \\nabla f(x_{k+1}) - \\nabla f(x_k)\\|\\|\\left(\\sqrt{\\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{t,i}^2}}\\right) \n    \\\\\\\\\n&\\leq \\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} L \\|\\| x_{k+1} - x_k\\|\\| \\left(\\sqrt{\\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{t,i}^2}}\\right) \\\\\\\\\n&=  L\\gamma\\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\left(\\sqrt{\\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{k,i}^2}}\\right)\\left(\\sqrt{\\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{t,i}^2}}\\right) \\\\\\\\\n&\\leq \\frac{L\\gamma}{c_m}\\sum\\limits_{k=0}^{t-1} \\beta_1^{t-k} \\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{k,i}^2}.\n\\end{align}\n\nThen, we plug this bound into the previous ones and get:\n\n$$f(x_{t+1}) - f(x_t) \\leq -(1 - \\beta_1)\\gamma\\sum\\limits_{k=0}^t \\beta_1^{t-k}\\sum\\limits_{i=1}^d\\frac{\\nabla_{k,i}g_{k,i}}{b_{t,i}} + \\frac{L\\gamma^2}{c_m}\\sum\\limits_{k=0}^{t} \\beta_1^{t-k} \\sum\\limits_{i=1}^d\\frac{m_{k,i}^2}{b_{k,i}^2}.$$\n\nApplying Lemma C.2 and summing over $t$, we derive the following bound:\n\n\\begin{align}\n\t(f(x_T) - f^\\ast) - (f(x_0) - f^\\ast) &\\leq -(1 - \\beta_1)\\gamma\\sum\\limits_{t=0}^{T-1}\\sum\\limits_{k=0}^t \\beta_1^{t-k}\\sum\\limits_{i=1}^d\\frac{\\nabla_{k,i}g_{k,i}}{b_{t,i}} \\\\\\\\\n&+ \\frac{L\\gamma^2(1-\\beta_1)}{c_m}\\sum\\limits_{t=0}^{T-1}\\sum\\limits_{k=0}^{t} \\beta_1^{t-k} \\sum\\limits_{i=1}^d\\sum\\limits_{j=0}^k\\beta_1^{k-j}\\frac{g_{j,i}^2}{b_{k,i}^2}.\n\\end{align}\n\nThen, similarly to the proof of Lemma C.3, we denote the coefficients in front of $\\nabla_{r,i} g_{r,i}$ and $g_{r,i}^2$ as $-\\gamma C_{r,i}$ and $A_{r,i}$ respectively. They have the following explicit formulas\n\n\\begin{align}\n    -\\gamma C_{r,i} &= -(1 - \\beta_1)\\gamma\\sum\\limits_{t=r}^{T-1}\\frac{\\beta_1^{t-r}}{b_{t,i}},\\\\\n    A_{r,i} &= \\frac{L\\gamma^2(1-\\beta_1)}{c_m}\\sum\\limits_{t=r}^{T-1}\\sum\\limits_{k=r}^t\\frac{\\beta_1^{t - r}}{b_{k,i}^2}\n\\end{align}\n\nAfter that, we follow exactly the same steps as in the proof of Theorem C.5 and get that for $\\gamma \\leq \\frac{(1 - \\beta_1)^2c_m^3 b_0}{2L}$ the following inequality holds:\n\n\\begin{align}\n\t\\sum\\limits_{t=0}^{T-1}\\sum\\limits_{i=1}^d \\frac{\\gamma C_{t,i}}{2}\\nabla_{t,i}^2 &\\leq (f(x_0) - f^\\ast) - (f(x_T) - f^\\ast) - \\sum\\limits_{t=0}^{T-1}\\sum\\limits_{i=1}^d (\\gamma C_{t,i} - 2A_{t,i})\\nabla_{t,i}\\theta^u_{t,i} \\\\\\\\\n&+ \\sum\\limits_{t=0}^{T-1} \\sum\\limits_{i=1}^d 2A_{t,i}(\\theta^u_{t,i})^2 + \\sum\\limits_{t=0}^{T-1} \\sum\\limits_{i=1}^d \\gamma C_{t,i}(\\theta^b_{t,i})^2.\n\\end{align}\n\nThe rest of the proof follows very similar steps to the current proofs of Theorems C.5 and C.12 – from Theorem C.5 the same dependence on $1 - \\beta_1$ follows, and from Theorem C.12 the dependence on $d$ is preserved.\n\n>2:**In Theorem 3.3, $M \\to \\Delta$**\n\nA: Thank you for spotting the typo: should be $M$ in the upper bound.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "Yes, in Section 4", "relation_to_broader_scientific_literature": "It is generally related to theoretical understanding of popular optimization algorithm in machine learning.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "This is a clearly theoreitical-solid paper, providing a complete proof of high probability convergence of Adam-type algorithms with clipping. The only concern is that the analysis heavily depends on the global adaptive stepsize instead of coordinate-wise scaling as in original Adam. Although the authors provide results for clip-Adam, it still dependends on $\\beta_1=0$. This is not aligned with practice. The only paper I know that analyzes clip-Adam without sub-gaussian noise assumption is [1], which has similar assumptions with this paper but in distributed setting. This might be helpful for the authors to do future research.\n\n[1] Cheng, Ziheng, and Margalit Glasgow. \"Convergence of Distributed Adaptive Optimization with Local Updates.\" arXiv preprint arXiv:2409.13155 (2024).", "other_comments_or_suggestions": "In Theorem 3.3, $M\\rightarrow\\Delta$", "questions_for_authors": "see strength and weakness part", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the convergence under heavy tail noise of adaptive methods such as the single step size versions of Adagrad and Adam and other variants of these methods. The paper gives an example of an instance where the iteration complexity of these methods is polynomially large in $1/\delta$, where $\delta$ is the failure probability. The paper then shows that clipping improves the convergence, and establishes convergence guarantees with a logarithmic dependence on $1/\delta$ for the methods with clipping.

Adaptive methods such as AdaGrad and Adam are some of the widely used optimization methods, and understanding their performance in challenging stochastic settings is an impactful direction. The paper makes a valuable contribution in this direction and further underscores the importance of clipping in settings where the stochastic noise is heavy-tailed. Most of the reviewers appreciated the main contribution of this work and supported accepting the paper. One of the reviewers was concerned that Thm 2.1 does not provide a lower bound but rather only an example of an instance, and that the experimental evaluation has limitations. Although Thm 2.1 does not provide an actual lower bound, it provides an informative example. We encourage the authors to strengthen the experimental evaluation based on the reviewers' feedback. Overall, the paper makes a valuable theoretical contribution that is sufficiently supported by the experimental evaluation.
Decision: Accept (poster)