Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
Authors: Zijian Liu
Zhengyuan Zhou
Venue: ICLR 2025 Poster (2025)
Keywords: Stochastic Optimization
Heavy-Tailed Noises
Primary area: optimization

Abstract: Recently, the study of heavy-tailed noises in first-order nonconvex stochastic optimization has gotten a lot of attention since it was recognized as a more realistic condition as suggested by many empirical observations. Specifically, the stochastic noise (the difference between the stochastic and true gradient) is considered to have only a finite $\mathfrak{p}$-th moment where $\mathfrak{p}\in\left(1,2\right]$ instead of assuming it always satisfies the classical finite variance assumption. To deal with this more challenging setting, people have proposed different algorithms and proved them to converge at an optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate for smooth objectives after $T$ iterations. Notably, all these new-designed algorithms are based on the same technique – gradient clipping. Naturally, one may want to know whether the clipping method is a necessary ingredient and the only way to guarantee convergence under heavy-tailed noises. In this work, by revisiting the existing Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm, we provide the first convergence result under heavy-tailed noises but without gradient clipping. Concretely, we prove that Batched NSGDM can achieve the optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate even under the relaxed smooth condition. More interestingly, we also establish the first $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{2\mathfrak{p}}})$ convergence rate in the case where the tail index $\mathfrak{p}$ is unknown in advance, which is arguably the common scenario in practice.

Published as a conference paper at ICLR 2025
NONCONVEX STOCHASTIC OPTIMIZATION UNDER HEAVY-TAILE) NOISES: OPTIMAL CONVERGENCE WITHOUT GRADIENT CLIPPING
Zijian Liu' Zhengyuan Zhou
Stern School of Business, New York University (213067, zzhou)
ABSTRACT
Recently, the study of heavy-tailed noises in first-order nonconvex stochastic op- timization has gotten lot of attention since it was recognized more realistic condition as suggested by many empirical observations. Specifically, the stochas- tic noise (the difference between the stochastic and true gradient) considered have only a finite p-th moment where E (1,2) 2] instead of assuming it always sat- isfies the classical finite variance assumption. To deal with this more challenging setting, people have proposed different algorithms and proved them to converge
at an optimal (T rate for smooth objectives after T iterations. Notably, based the same technique gradient
all these new-designed algorithms clipping. Naturally, one may want to know whether the clipping method is a nee- essary ingredient and the only way to guarantee convergence under heavy-tailed noises. In this work, by revisiting the existing Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm, we provide the first convergence result under heavy-tailed noises but without gradient clipping. Concretely, we prove that Batched NSGDM can achieve the optimal ( 5p-a) rate even under the relaxed smooth condition. More interestingly, we also es- tablish the first (T convergence rate in the case where the tail index p unknown in advance, which is arguably the common scenario in practice.
INTRODUCTION
This paper studies the optimization problem min F(x) where F Rd - R is differentiable and could be nonconvex. When F is smooth (i.e., the gradient of F is Lipschitz), the classical first- order method, Gradient Descent (GD), is known converge the optimal rate ((T- to find stationary point (i.c., to minimize (VF(())) (Nesterov et al. 2018). However, main drawback of GD in the modern view is that it requires true gradients, which could be computationally burdensome (e.g., large-scale tasks) or even infeasible to obtain (e.g.. streaming data). As such, a famous variant of GD, Stochastic Gradient Descent (SGD) (Robbins & Monro 195T), has become the gold standard and been widely implemented nowadays due to its lightweight yet efficient computational procedure. Under the standard finite variance noise condition, i.e., the second moment
difference between the stochastic gradient and the true gradient is bounded, SGD has been proved to converge in the rate of (TT )) (Ghadimi & Lan 2013). 3) which is unimprovable if without further assumptions as indicated by the lower bound (Arjevani et al. 2023)
Although the finite variance assumption has been widely adopted in theoretical study (see, e.g., Lan (2020)), it has been recently recognized as too optimistic in modern machine learning tasks pointed out by empirical observations (Simsekli al., 2019 [Simçekli al. 2019 [Zhang al.) 2020c), which reveal a more realistic setting: the heavy-tailed regime, i.c., the stochastic noise only has finite p-th moment where p E (1, 2). Such new assumption brings new challenges in both algorithmic design and theoretical analysis since SGD unfortunately fails to work and the prior theory of SGD becomes invalid when p (Zhang et al. 2020c).
"Corresponding author.

---

Published as a conference paper at ICLR 2025
To resolve the failure of SGD under heavy-tailed noises, Clipped SGD (or its further variants) has been proposed and shown to converge in both expectation (Zhang et al. (020c) and high proba-
bility (Cutkosky & Mchta 2021 Liu et al., 2023b; Nguyen al. 2023 Liu et al. 2024) at a rate
5 )) which is indeed optimal (Zhang et al. 2020c). As suggested by the name, the central tool lying in all these existing algorithms gradient clipping, which seems to be necessary ingredient against heavy-tailed noises so far. Therefore, we are naturally led to the following question:
Is gradient clipping the only way to guarantee convergence under heavy-tailed noises? If not, can we find an algorithm that converges at the optimal rate 3r 1- 22) without clipping?
Another important but often omitted issue in previous studies is that the tail index P of heavy-tailed noises is always implicitly assumed to be known and then used to choose the clipping magnitude and the stepsize (or the momentum parameter) (Zhang et al., 2020c Cutkosky & Mehta 2021 Liu et al. [023b] Nguyen et al. [023]] Liu et al. (024). However, knowing p exactly or even estimating its approximate value is non non-trivial task lots of cases, e.g., the online setting. Consequently, the existing convergence theory for Clipped SGD immediately becomes vacuous when no prior information on p guaranteed, which however arguably the common scenario in practice. The above discussion thereby leads to another rescarch question:
Does there exist an algorithm that provably converges under heavy-tailed noises even the tail index p is unknown?
This work provides affirmative answers to both of the above questions by revisiting a well-know technique in optimization: gradient normalization, which is surprisingly effective even under heavy- tailed noises as demonstrated by our refined theoretical analysis.
1.1 OUR CONTRIBUTIONS
We study the Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm (Cutkosky & Mehta 2020) under heavy-tailed noises and establish several new results:
We prove that Batched NSGDM converges in expectation the optimal rate O $) when noises only have a finite p-th moment where E (1, 2). which is the first convergence result under heavy-tailed noises not requiring gradient clipping
We establish refined lower complexity result having more precise order on problem- dependent parameters (e.g., the noise level op). which perfectly matches our new conver- gence theory for Batched NSGDM further showing the optimality of our analysis.
We initiate the study of optimization under heavy-tailed noises with an unknown tail index P and provide the first provable rate O(T 22 also achieved by the same Batched NSGDM method indicating the robustness of gradient normalization against heavy-tailed noises?)
Our analysis goes beyond the classical smoothness condition and heavy-tailed noises as- sumption studied in previous works and is the first to hold under their generalized counter- parts (see Assumptions 2.2 and 2.4).
Our proof is based on a novel expected incquality for the vector-valued martingale differ- ence sequence, which might be of independent interest.
1.2 RELATED WORK
We focus on the literature on nonconvex problems under heavy-tailed noises. For recent progress on convex optimization, the reader can refer to /hang & Cutkosky (2022); Sadiev et al.) (2023); ; Liu &
Zhou ) Kornilov et al. (2023): y Puchkin et al. (2024); Gorbunov et al. (2024) for details.
Upper bound under heave-tailed noises. For smooth objectives, different works have established the optimal rate ( 1-2 2) (up to extra logarithmic factors) for Clipped SGD or its further variants
In preparing the camera-ready version the paper, it was brought to our attention that two independent and concurrent works established similar results (Hübler ct al. 2024 Sun et al. 2024).
Hübler al. 2024) also gave matched lower hound for Batched NSGD, L.C. in Algorithm
2

---

Published as a conference paper at ICLR 2025
Zhang et al.) 2020c Cutkosky & Mehta 2021: Liu et al. 2023b guyen et al. 2023 Liu al. 2024]. among which. Zhang et al. (2020c) and Nguyen et al. (2023) respectively provide the best expected and tigh-probbbility bounds for Clipped SGD as their results do not contain any extra (log I') factor. Notably, Zhang et al. 22000c can recover the standard O b) rate in the noiseless case. In contrast, the rates by by[Cukksky & Mehta (222 Liu et al. (2023b); Nguyen et al. (2023); ); Liu al. (2024) are not adaptive to the noise level. In addition, we note that the results from Cutkosky & Mehta (2021) also depend on an extra vulnerable assumption, i.e., the stochastic gradient itself has finite p-th moment, which can be easily violated. However, all these works require a known tail index p to establish convergence theory, which may not be realistic in practice.
Lower bound under heavy-tailed noises. As far as we know, Zhang et al. (2020c) is the first and only work that provides the Q((T5= lower bound for nonconvex optimization under the classical smooth assumption and the finite p-th moment condition on noises, where the proof is based on the tool named probability zero-chain developed by AArevaai et al. (2023). However, we should remind the reader that the lower bound by Zhang et al. (2020c) is actually proved based on assuming a finite p-th moment the stochastic gradient instead of the noise and hence may fail to provide a correct dependence on
parameters like the noise level du-
In addition, we provide a quick review of the gradient normalization technique.
Gradient normalization. The normalized gradient method has a long history and could date back to the pioneering work of Nesterov (1984), which is the first paper to suggest considering normalization in (quasi- )covvex) optimization problems and provides a theoretical convergence rate. Many later works (e.g., Kiwiel (200T); Hazan et al. (2015): Levy (2016); Nacson al. (2019)) further explore the potential of gradient normalization. In deep learning, gradient normalization (or its variant) has also gained more and more attention since it can tackle the gradient explosion/vanist issue and has been observed to accelerate the training (You et al. [017] (019). However, provable theory still lacks for general nonconvex problems until (Cutkosky Mehtal 2020), who established the first meaningful bound by adding momentum to the normalized gradient method.
2 PRELIMINARIES
Notation. N denotes the set of natural numbers (excluding 0). [T] & (1,2. ,T} for any T E N. ()-) is the Euclidean inner product on IRd and ||-I1 A v(, is the Eg norm. Given a sequence E R. Vt E [T', we use the notation Ne:t - IT' re for any 1 S s t T and rea $ if t.
We consider the optimization problem min F(x) in this work, where F: Rd + RR is differen- tiable and potentially nonconvex. A computationally tractable goal is to minimize [[F(()]] which is the focus hereinafter. Our analysis relies on the following assumptions.
Assumption 2.1. Finite Lower Bound. F. A wn F(x) > -0.
Assumption 2.2. Generalized Smoothness. There exist Lo 2 O and L1 2 such that [VF(()) FF))) < (To In [)=))()))]) ||æ for anr
any x. y TRd satisfying || yl 2
The original definition of generalized smoothness was proposed by Zhang et al. (2020b) but required the objective be twice differentiable. Here, instead adopt weaker version introduced later by Zhang et al. (2020a). which only needs F' to be differentiable. As one can see, Assumption 2.2 degenerates to the standard Lo Lo-smoothness when L1 and hence is more general. We note that there exist other versions of generalized smoothness proposed recently and refer to Chen et al.
2023 al. (2023a b) for details.
Assumption 2.3. Unbiased Estimator. At the t-th iteration, we can access a batch of unbiased gradient estimator G, e {g).... ..)......)).... i.e. E [gi [F-i]] = FF(::), Vi E [B], where B is the batch size and F, - oG..... G.) denotes the natural filtration. Moreover, we assume that gi. Vi E [B] are mutually independent for any fixed t.
Assumption 2.4. Generalized Heavy- Tailed Noises. There exist E (1,2), ag 2 0 and 01 2 Ouch ||:l [Fr- < og + of Fx(x))) Vi E [B] almost surely where gl A gf V F(..)
that
We remark that Assumption 2.4 is a relaxation of the traditional heavy-tailed noises assumption (i.e., set σ1 0) and is new far we know. The reason for proposing this generalized version
3

---

Published as a conference paper at ICLR 2025
is that the finite p-th moment requirement used in prior works be violated in certain situations where the new assumption instead holds. We refer the reader to Example[A. provided in Appendix for details. In addition, such form of Assumption 2.4 may reminisce about the affine variance condition studied the existing literature (Bottou et al. 2018). Indeed, this new assumption is inspired by it and can also be viewed as its extension.
However, to make our work more reader-friendly we will stick to the case 01 = (i.e., the classical heavy-tailed noises assumption used in prior works) in the main text to focus conveying our high- level idea and avoid further complicating the analysis. The full version of our new result considering an arbitrary pair (or, (1) Assumption 2.4 deferred Appendix D
To finish this section, we introduce the following smoothness incquality under Assumption 2.2
whose proof is omitted and can be found in, for example, ZZhang et al. (2020a).
Lemma 2.5. Under Assumption 2.2 for any a. y E TR satisfying || yll
LT there is
F(y) S F(x)) (VF(x). y x) Lo + L1 VVF
1 yl
2
3 CONVERGENCE WITHOUT GRADIENT CLIPPING
Algorithm 1 Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDMM
Input: initial point 11 Rd, batch size B E N, momentum parameter 3, E [0, 1]. stepsize ne >> 0 for t = to do
9: >E= g
m, 3,m,-1 (1 3:)g
where mg - 91
1t++ = 3t- 17t mm
m.
D where [
end for
Remark 3.1. Instead of the norm normalization in Algorithm D we can consider an elementwise
mifil Vi E [d]. which is known Batched Sign normalization rule, i.e. 2++1 [ x. 1/s, [
Stochastic Gradient Descent with Momentum (Batched SSGDM). By applying the idea introduced in Section 4 one can also establish the convergence of Batched SSGDM under heavy-tailed noises.
The method we are interested in, Batched NSGDM (Cutkosky & Mehta 2020). is provided above in Algorithm Compared the widely used Batched SGDM algorithm, the only difference the extra normalization step. which we will show has crucial effect when dealing with heavy-tailed noises. Since many prior works (ou et al. Cutkosky & Mehta (2020): Jin et al.) (202T) have explained how and why Batched NSGDM works (in the finite/affine variance case), we hence do not repeat the discussion here again. The reader seeking the intuition behind the algorithm could refer to, for example, Cutkosky & Mehta (2020) for details.
Now we are ready to present our new result for this classical algorithm under heavy-tailed noises.
3.1 CONVERGENCE WITH KNOWN TAIL INDEX p
In this subsection, we provide the convergence rate of Batched NSGDM under ideal situation, ie., when every problem-dependent parameter is known, which is commonly assumed implicitly in the optimization literature.
Theorem 3.2. Under Assumptions for any T E N, by taking
2.1
2.2
2.3 and 2.4 (with ai = 0), let A A F(x1) F., then
A1L1 + 0o
L
3P-7
B: 3 min
1. max
ooT
a
(1 B)
1- 8
?e 1 min
B B=1,
LoT
8L1
4

---

Published as a conference paper at ICLR 2025
Algorithm guarantees
1
A1L1 T
A Lo T + (A1L1)
20-1 1p-1
00
+
+ (A1 00-200
30-2
=
+ V
T
T
T T'p-2
Theorem 3 2
states the convergence rate of Algorithm [ Junder heavy-tailed noises. The full version,
Theorem D. that works for any σi 2 0 is deferred Appendix D As a quick sanity check, (T) when p = 2 (i.c., the finite variance case), which is known to be tight not only in T but also in A1, Lo and (Arjevani et al.) 2023).
Theorem reduces to the rate
We would like discuss this theorem here further. First and most importantly, as far as we know, this is the first and only convergence result for nonconvex stochastic optimization under heavy- tailed noises but without employing the gradient clipping technique, which the central tool for all previous algorithms under the same setting, not to mention the rate O(T 3) is also optimal in T 5
since it matches the lower bound (2 (T proved in Zhang et al. (020c). In fact, the lower-order term I((A -
T in our rate is also tight in A1, Lo and below, where we present a refined lower bound by extending the prior result (Zhang et al. (020c).
indicated by Theorem 3.3
To the best of our knowledge, we are also the first to obtain tight dependence on these parameters
compared to the previous best-known bounds for Clipped SGD that are only optimal T ZZang
et al. 2020c Nguyen et al. (223)). The proof of Theorem 3.3 is given in Appendix D and mostly follows the same way established in Carmon et al. (2020 : Arjevani et al. (2023): Zhang et al. (202cc) but with simple alteration to ensure that the noise magnitude du shows up the conrect order.
Theorem 3.3. For any given E (1, Lu, ou > O, and small enough e > 0, there ex- ist function F (depending on the previous parameters) satisfying Assumptions
2.7 2.2 (with
L, 0) and F(0) F. I A and a stochastic oracle satisfying Assumptions 2.3 (with
1)
and 2.4 (with 01 0) such that any zero-respecting algorithm startinig from æ1 0 requires
A(A, Togo - --²)
iterations to find an e-stationary point, i.e., E. [[[VF(==)]] S E.
Remark 3.4. The careful reader may find that Theorem 3.3 is established under the classical smooth assumption instead of the relaxed (Lo, L1) )smooth condition. However, noticing that the function class satisfying the traditional smooth condition is subclass of the function set fulfilling generalized smoothness. this lower bound can thus be directly applied to the setting considered in Theorem 3.2 Remark 3.5. We also note that, when p 2. Theorem 3.3 perfectly matches the existing lower bound Q A1 Looge=4) in the finite variance case (Arjevani et al. 2023).
Morcover, we would like to mention that Theorem 3.2 holds under generalized smoothness (and generalized heavy-tailed noises), which greatly extends the implication of our result compared the previous works (Zhang et al. 2020c] Nguyen et al. 2023) that can be only applied to the classical setting. In addition, the reader may want to ask why we need batch size B given it is set to 1. The reason for considering B is that it plays important role when σi > O. To be precise, B could possibly be larger than to guarantee the convergence when σ > O. For details about how the batch size B works, please refer to Theorem D.I and its proof. Lastly, 3.2 perfectly recovers the fastest rate in the noiseless case. In other words, when dp = O, the rate degenerates to I / / Lo/ /T), which is the best result for deterministic (Lo, -mmoohh nonconvex optimization far
want to point out that Theorem
are aware (Liu et al. 2023a).
Given the above discussion, we believe that our work provides a new insight on how to deal with heavy-tailed noises, i.e., using normalization, in stochastic nonconvex optimization problems.
3.2 CONVERGENCE WITHOUT A KNOWN TAIL INDEX
As pointed out at the beginning of Subsection 3.1 the convergence result shown in Theorem 3.2 can only hold under full information because the choices of 3 and y) heavily rely on problem-dependent parameters, which are, however, hard to estimate in practice. Especially, assuming prior information on p not realistic. As such, we will try to reduce the dependence on these parameters in this subsection.
A first-order algorithm is called zero-respecting if it satisfies a, E Uusessupportgg)) Vt E N. The reader could refer to Definition 1 in Arjevani al. (202) for details.
5

---

Published as a conference paper at ICLR 2025
Theorem 3.6. Under Assumptions for any E N, by taking
2.1
2.2
2.3 and
2.4 (with 01 =0), ler A1 - F(x1) )
F.. then
3 = B
T
"1 = ==
min
T
81,72 2
B=1,
Algorithm 7 guarantees
A VT
A
Lo
T
T T
shows the first provable convergence upper bound OT 1-p
when the tail index is unknown and, at the same time, tries to relax the dependence on other parameters. As one can see, the only parameter that we require now is L1. It is noteworthy that, once the time horizon T is large enough to satisfy T = ((()) (or cquivalently. L1 is small enough to satisfy T = = D), we can get rid of L1 7) and thus do not need any information on the problem. remarkable implication is that, in the same classical smooth case (i.e., when 11- 0) studied in previous works (Zhang et al.)
Theorem 3.6
2020c Nguyen et al. 2023). Batched NSGDM can converge in the rate O(T 1 without knowing any of p, 21, Lo. do. In contrast, the choices of the clipping magnitude and the stepsize in Clipped SGD provided by Zhang et al. (2020c); Nguyen et al. (2023) heavily depend on these parameters.
In addition, there are several points we would like to clarify. First, one may want to ask whether the requirement of knowing L1 can be totally lifted, which we incline to a positive answer. But to prevent deviating from the main topic of paper heavy-tailed noises, we defer the detailed discussion about L1 to Appendix
B in which we will explain the reason and talk about a possible way to achieve this goal. Another question that we view important but currently have no answer is
whether the (T 5) rate is still achievable when is unknown, which we leave as an interesting direction to be explored in the future. Moreover, the reader may find that the rate Theorem 3.6 loses the adaptivity on og since can only guarantee the OTT convergence instead of the optimal OTT 1) rate in the noiseless case. We remark that this is a common phenomenon for optimization algorithms when oblivious to the level of noise. For example, it is well-known that SGD suffers the same issue even under the finite variance assumption but when do is unknown. The last thing have to mention is that, unfortunately, the good property of not needing the tail index p may fail when considering d > O in the generalized heavy-tailed assumption. Precisely speaking, we can only prove that there exists a constant threshold of > such that B can always be set if σ1 < of and B has to be chosen based on when 01 of The details can be found in Theorem D.2 in the appendix.
In summary, we exhibit the first convergence result under heavy-tailed noises when only partial information about the problem is available. Particularly, under the classical heavy-tailed noises, we show how to guarantee convergence even if the tail index is unknown.
4 HOW GRADIENT NORMALIZATION WORKS
In this section, we will explain how gradient normalization works under heavy-tailed noises by both intuitive discussion and theoretical analysis. Moreover, to keep the analysis simple and better compare the difference between Batched NSGDM and Clipped SGD studied previously, we will focus on the classical smoshh case (i.e., take L1 0 in Assumption (.2) under finite p-th moment noises (i.e., take 01 = O in Assumption (.4) to align with prior works. Due to limited space, the missing proofs of presented lemmas (and their full version) deferred in the appendix.
4.1 WHAT DOES GRADIENT CLIPPING DO?
Before analyzing Algorithm let us first recap the update rule of Clipped SGD:
1, Te
0++1 3; - vi 9,
Dr-
(1)
where 9, is the clipped gradient and T. > 0 is known as the clipping magnitude playing a critical role in the convergence. Especially, (1) can recover SGD by setting 7, +00.

---

Published as a conference paper at ICLR 2025
We provide simple analysis here to illustrate how gradient clipping helps Clipped SGD to converge in expectation. First, by the well-known smoothness inequality, ie., Lemma 2.5 with L1 = 0, we know
To
F(x++1) S F(a.) (VF( E++1
-xt) +
| - xel1
2
L1 Lo
F(a:)) t/ (VF((:)))))))))))))))))))))))( 9..)
11
m Lo
Lo c
=a(+))
|VF(())) 12 (n: - Lo) (VF())),
where E - 9. VF(z:). Following the existing literature (c.g.. Cutkosky & Mehta 2021 Liu
et al. 2023b ) we next decompose 4, into G o + c. where o - 9. E 9. Fi and
9t Fi-1] V (xx)) By noticing E [[(VF( + = E ((t e = 0. we thus have
Lo E |[F(()))
B [[F(x++)) < [F(x)]]
2
n² LoLo E || + +||2/11
(n nH [
(VF(2))
if 1m E[F(x))]
Th |VF 2 ||| + Lo
E
[|-1|]] 2
+ 2 T ||
(3)
2
2
where the last step is by E [VVF(=)) et B B[IVF(20)11
"| ++ [|=+]]]]] and 7/+ u/ Lo 2 0.
Now let us check what will happen for SGD without clipping, i.e., taking T. = +00 In this case, recovers the classical one-step inequality for SGD by observing e7 E. -
9:
V F
( and et = 0 now, which also reveals why SGD may fail to converge because
E
| = E | could be too under Assumption 2.4
In contrast, loosely speaking, setting + would ensure that both E [|(]|]]]] and
E ||= finite, whose upper bounds could be further controlled by picking To prop-
erly. Finally, Clipped SGD would converge under carefully designed r)e and ne
From the above comparison (which though is not strictly rigorous), one can intuitively think that the key thing done by gradient clipping is making the second moment of the error term [|| be bounded even when the noise &, only has finite p-th moment.
2
4.2 WHAT DOES GRADIENT NORMALIZATION DO?
By the discussion in the previous subsection, we can see that gradient clipping is used to control the second moment of the error term. A natural thought could be that we may avoid gradient clipping the error term ||=]|] in ( is in a lower order, for example, say ||=/|| which can be bounded in expectation directly without clipping. However, because is not necessarily known, we could aim decrease the order of ||<,]| from 2 to 1, i.e., the extreme case.
The above thought experiment may immediately help the reader who is familiar with the optimiza- tion literature recall the gradient normalization technique, in the analysis of which first-order terms always show up. As such, it is reasonable to expect that Batched NSGDM can converge under heavy-tailed noises even without knowing p due to gradient normalization.
From now start analyzing Algorithm riigorussly and formally showing how gradient nor- malization overcomes heavy-tailed noises.
Lemma 4.1. Under Assumptions 2.1 and 2.2 (with L1 =0), let A & F(x1) F., then Algorithm guarantees
T
Lo Et=
m
T
E [V < A
2m E [||=|]],
(4)
2
7

---

Published as a conference paper at ICLR 2025
where E my (F())), Vt [T].
Lemma 4.1 provides a basic inequality used in the amalysis of Batched NSGDM. We remark that this inequality not new and has been proved many times before, when Lı (e.g., see Cutkosky & Mehta (2020): Jin et al. (2021)) But for completeness, the proof is provided in Appendix D
As mentioned earlier, the first moment EE [|] is exactly what want, which hope could be finite even under Assumption 2.4 To bound this term, we first recall the following widely used decomposition when studying gradient normalization (Cutkosky & Mehta 2020 2021
Jin al.
2021
Liu et al., 2023b).
Lemma 4.2. Algorithm guarantees
= B1IEE0 +
Beat D. Σ (1- 3,)3. 1. VI e [2],
(S)
s=1
8=1
where
D, A -
2
60 -1-v((()))
&, - 9. VF(x))
0
1=1
Proof. By the definition of when t 2 2,
6 m, F((.))) 3mm;-1 (1 3.)g, VF())) 3e - V (x (.( - Vf(x;)) + (1 B)) VF(x)))
+
-.)
One can verify that the above equation also holds when = under our notations (recall my = 91 in Algorithm I). Unrolling the equation recursively, can finally obtain the desired result.
After plugging 5 into as one can imagine, our remaining task is to upper bound E [||eo Il] E 3x.: D. and E
E - B.)8st1nE, ||] For simplicity, we consider the batch size
B 1 in the following.
First, note that E D. - P Dill and ||D can be bounded by Lo- smoothness easily (even under (Io, Li)-smoothness) hence we skip the calculation here. Next, when B = 1, one can use Hölder's inequality to bound E [[|eo]]] < (E [[]=ol[]]] < on where the [ E (1 B,, 8.)8++12..11
last step is by Assumption 2.4 when 0 = 0. For the left term E
When p = 2, prior works like Cutkosky Mehta 2020) invoke Hölder's inequality to have
Σ
B.) In
S
E
Σ
B.)
Σ ((1 8.)8
where the last step is due to E KS.., [.)l = 0 for every cross term and E ||S. - o/
Naturally, when noises only have finite p-th moments, one may want to apply Hölder's inequality in the following form,
[]
$
EE Ea 3.) 3.)8.
Σ (1
B.)3. 1
However. a critical issue here is that I|- cannot be expanded like ||- to make the cross term (E., E,) show up, which fails the analysis.
8

---

Published as a conference paper at ICLR 2025
As such, how to establish meaningful bound on E proofs, which essentially differs from the existing analysis when p = 2.
E (1 Be) the novel part of
Fix t [T], to ease the notation, denote by v, (1 - 1. Vs [t]. Hence, our goal can be summarized as bounding the norm of E Us. where is vector-valued martingale difference sequence (MDS). To do so, we introduce the following inequality, which is the core of our analysis.
Lemma 4.3. Given a sequence of integrable random vectors Vt E R
N such that the natural filtration, then for any p [1,2],
E [0 Fi-1] = 0 where Fi - a (V1, ,,, ;,1) there is
T
E
Σ
vt
2V2E
Σ
VV.
(6)
At first glance, (6) seems wrong because provides E
EE 1=1
will
2222E
by |1 hold. So
V V |0ll?
taking p 2. However, may only expect E
Σ 84
V
Σラ=
E
why is 66) true? Intuitively, this is because (6) is only stated for the MDS in contrast to Hölder's
inequality being able apply to any sequence.
To Iet the reader believe Lemma 4.3 is correct, we first consider the case of d and recall the famous Brrkholder-DDvii-Guiee
(BDG) inequality.
Lemma 4.4. (Burkholder-Davic Davis-Gundy Inequality (Burkholder] 1966 Burkholder & Gundy 1970
Davis 1970 simplified version) Given a discrete martingale X, E IR with Xo 0, then there exists
constant C2 such that
E
max 1E
X
S
C3E
Σ Xx
Xo-1)²
VT E.
under d = 1 and 2 (up to Let X, E.= Us BDG inequality immediately implies 6 constant) due
U
< E
max X, [E(T]]
- CEE
Σ
- - X._1)² = C.E
Σ
2
1=1
1=1
One more step, by noticing
||-||
< I1-1lp for E [1. Lemma 4.3
thereby holds when d = by
T Σ
T S
E
Σ
CE
|r 1=1
CE
Σ
Though we have applied BDG inequality to prove Lemma 4.3 for d = 1, extending the above analysis to the high- high-dimensional case obvious and could be non-trivial.
Here, inspired by Rakhlin & Sridharan (017)). we will provide simple proof of Lemma 4.3 via
the regret analysis from online learning. Specifically, we will prove the regret bound of the famous
AdaGrad algorithm (McMahan & Streeter 2010 Duchi et al., (011) implies Lemma 4.3 which is
kindly surprising (at least our opinion) and shows the impressive power of online learning. Due to space limitations, the proof of Lemma 4.3 is deferred to Appendix
Before moving on, we make two comments on Lemma 4.3 First, as one can see, Lemma 4.3 holds
for any E [1, 2] meaning that this analysis is automatically adaptive to the tail index Next, one may wonder why we keep the expectation outside on the R.H.S. of ( instead of putting it inside by Hölder's i inequality. This is because under the full version of Assumption 2.4 (i.e., di 0), making expectations inside may fail the analysis. For details, we refer the reader to the proof of Lemma D.5 in the appendix.

---

Published as a conference paper at ICLR 2025
Now, we can apply Lemma 4.3 to bound E
- Be)B.+1nE. under Assumption 2.4 with
01 0 and then obtain the following ieqqualtyy for E [|] by combining the previous bounds on
[|| and E
1 D.
S..:
Lemma 4.5. Under Assumptions 2.2
(with L1 = 0), 2.3 (with B = 1) and 2.4 (with or = 0), then
Algorithm guarantees
E I|lll11 s 2 BI100 +
B [T].
8=2
The full version of the above result, Lemma D.5 that works for any L1, o, can found in Appendix which requires extra effort as mentioned earlier.
we are able to prove the convergence of Batched NS- GDM under the classical smooth condition and heavy-tailed noises by plugging in the stepsize and momentum parameter introduced in Theorems 3.2 and 3.6 respectively.
Finally, equipped with Lemmas 4. and 4.5
Before ending this section, we briefly talk about the intuition behind the rate O(T '=0 achieved when the tail index p is unknown, i... Thcorem 3.6 Actually, we take a quite simple strategy: setting the stepsize and the momentum parameter while pretending the tail index to be 2. Amazingly, this straightforward policy is already enough to guarantee convergence even there is no prior information on p.
5 CONCLUSION AND FUTURE WORK
In this work, we present the first optimal expected convergence result under heavy-tailed noises but without gradient clipping, which is instead achieved by gradient normalization. More specifically, we study the existing Batched NSGDM algorithm and prove it converges in expectation at an optimal parameters in our upper bound also
OTT rate. Additionally, the order of the first to be tight as indicated by a newly matched lower bound improved from the prior work. One step further, we initiate the study of convergence under heavy-tailed noises but without knowing the tail index p and then obtain the first provable O 2p rate. Thus, work suggests gradient normalization a powerful tool for dealing with heavy-tailed noises, which we believe will bring new insights into the optimization community and open potential ways for future algorithm design.
However, there still remain some directions worth exploring, and we list three specific topics here:
Minimax rate for unknown tail index p. As previously discussed, to achieve the minimax ((T rate under heavy-tailed noises, all optimal algorithms so far require knowing the tail index Thus, it would be interesting to consider the optimal upper/lower bound of the convergence rate when is unknown. We provide two concrete problems here and hope them being addressed in the future: 1. When lacking any prior information on p. is it possible to find algorithm that can
improve our new OF upper bound to the best-known (T rate? 2. If the answer to the former question is negative, what is the corresponding lower bound when p is unknown?
Adaptive gradient methods. Though we have established the first convergence result under heavy- tailed noises without gradient clipping, the Batched NSGDM algorithm studied is not commonly used in practice. In comparison, the family of adaptive gradient methods (e.g.. AdaGrad (McMahan Streeter 2010 Duchi et al. 2011). RMSprop (Tieleman al. 2012). Adam (Kingma Baj 2014) and their variants) is more popular and has been widely implemented nowadays, especially when training neural networks. Surprisingly, their performances are still good even though the stochastic noises are empirically observed to be heavy-tailed. However, far we know, rigorous theoretical justification has been established to show that adaptive gradient methods can converge under heavy-taibe noises. Hence, is worth studying and trying close this important gap between theory and practice.
Time-varying choices. Another potential extension is to study the time- varying stepsize and mo- mentum parameter to make the algorithm more practical, which we believe is possible given our general lemmas.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work is supported by the NSF grant ECCS-2419564. We also thank the anonymous reviewers for their valuable comments.
REFERENCES
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2): 165-214, 2023.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223311, 2018.
Donald L. Burkholder and Richard F Gundy. Extrapolation and interpolation of quasi-linear opera- tors on martingales. 1970.
Donald Lyman Burkholder. Martingale transforms. The Annals of Mathematical Statistics, 37(6): 1594-1504, 1966.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):11-120, 2020.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. mization is efficient smooth nonconvex optimization. In Andreas Krause, Emma Brun- skill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Pmo- ceedings of the 40th International Conference on Machine Learning, volume 202 of Proceed- ings of Machine Learning Research, pp. 5396-5427. PMLR, 23-29 Jul 2023. URL https:
Generalized nonconvex opti-
//proceedings . ml www.s/vveee....... http://22/cennae html
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35:9955-9996 2022.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In Hal DaumA@ III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 2260-2268. PMLR, 13-18 Jul 2020. URL http:///ppppedooo.o...eeeeeeeeep
html
Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 11:4883-4895 2021.
Burgess Davis. On the intergrability of the martingale square function. Israel Journal of Mathemat- ics, 8: 8:1-71990 1970.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. In Gergely Neu and Lorenzo Rosasco (eds.), Pro- ceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 169160. PMLR, 12-15 Jul 2023. URL https: / http://e///pooceeing..o.o
mlr. hll.ppesssvv995/E5 v
html
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-2) -23688, 2013.
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probabilie convergence for composite and distributed stochastic minimization and variational inequalities with heavy- tailed noise. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International

---

Published as a conference paper at ICLR 2025
Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 15951-16070. PMLR, 21-27 Jul 2024. URL https:://pxoceedigggg.uu press/ v235/ 2235//orbbnoo24a.ttm
Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex opti- mization. Advances in neural information processing systems, 28, 2015.
Yusu Hong and Junhong Lin. Revisiting convergence of adagrad with relaxed assumptions. arXiv preprint arXiv:2402.137999 2024.
Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. arXiv preprint arXiv:2410. 13849, 2024.
Florian Hübler, Junchi Yang. Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238 of Proceedings
of Machine Learning Research, pp. 4869. PMLR, 02-04 May 2024. URL https://
proceeding ngs mo..mrr... www.srrsss....... huw eerlerr24a.. html
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Krzysztof C Kiwiel. Convergence and efficiency of subgradient methods for quasiconvex minimiza- tion. Mathematical programming, 90:1-25, 2001.
Nikita Kornilov, Ohad Shamir, Aleksandr Lobanov, Darina Dvinskikh, Alexander Gasnikov, In- nokentiy Shibaev, Eduard Gorbunov, and Samuel Horváth. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. In A. Oh, T. Naumann, A. Globerson, K. Saenko. M. Hardt, and S. Levine (eds.). Advances in Neu- ral Information Processing Systems. volume 36, pp. 64083-64102. Curran Associates, Inc., 2023. URL. |tttps:// ngs neurips cttpppccccccpeeee.. htt.ge/eee..er.s.../ppp/epee/a/a wttp///////saa///2//3/3//3/ pddf
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint arXiv: 10l.:6611.43111 2016.
Haochuan Li. Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36. pp. 40238-40277 Curran Associates, Inc., 2023a. URL httpttts///rcceeddinosss/ ngs wwwrine.uusccee cctpssscccpppppeepeeeeeeeee http:e/eeeeeeeeeeeeeeeeeecceeeee
http://pwrr_.lleeeeeeeree/a File/ 11l.:///6eaaaaaocaee222200022000
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assump- tions. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems. volume 36, pp. 52166-52196. Curran Associates, Inc., 2023b. htt.::::/pppoceedddo.eeeeee.s..o E
Langgi Liu, Yibo Wang, and Lijun Zhang. High-probabilityy bound for non-smooth non-convex stochastic optimization with heavy tails. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceed- ings of the 41st International Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pp. 32122 32138. PMLR, 21-27 Jul 2024. URL https: //proceed igs. ml www.mmp...............m.mmmmm wrw.srassppom www.ppraasss333 v235///223/11 11w5//1uu4b.... html
12

---

Published as a conference paper at ICLR 2025
Zijian Liu and Zhengyuan Zhou, Stochastic nonsmooth convex optimization with heavy-tailes noises. arXiv preprint arXiv:2303.12277, 2023.
Zijian Liu, Srikanth Jagabathula, and Zhengyuan Zhou. Near-optimal non-convex stochastic opti- mization under generalized smoothness. arXiv preprint arXiv:2302.06033 00022200.0000... 2023a.
Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Gergely Neu and Lorenzo Rosasco (eds.). Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 2266 2290. PMLR, 12-15 Jul 2023b. URL
press/ 95/1iu23c. html
H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In Conference on Learning Theory (COLT), pp. 244 256. Omnipress, 2010.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420-3428. PMLR, 2019.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Yurii E Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 2993)31 1984.
Ta Duy Nguyen, Thien H Nguyen, Alina Ene, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances in Neural Information Processing Systems, 36:24191-24222, 2023.
Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy- tailed noise barrier in stochastic optimization problems. In International Conference on Artificial Intelligence and Statistics, pp. 856-864. PMLR, 2024.
Alexander Rakhlin and Karthik Sridharan. On equivalence of martingale tail bounds and deter- ministic regret inequalities. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. PMLR, 07-10 Jul 2017. URL https: http:ss//poocceeiiie ml r.prsss/v6/ m....rr...s//.../
rakhlinin htmm
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. Andreas Krause, Emma Brunskill. Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (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. URL www.innss........mmmmmmm.......m wtwp./ig............... / v202 sadiev23a htmml
Umut Şimşekli, Mert Gürbüizbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint /912:09912.000 2019.
Umut Simsckli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pp. op2558875837. PMLR, 2019.
Tao Sun, Xinwang Liu, and Kun Yuan. Gradient normalization provably benefits nonconvex sgd under heavy-tailed noise. arXiv preprint arXiv:2410. 1656/, 2024.
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-mmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2))26-31, 2012.
13

---

Published as a conference paper at ICLR 2025
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non- convex objectives: Simple proofs and relaxed assumptions. In Gergely Neu and Lorenzo Rosasco Learning Theory, volume 195 of Proceed- ings of Machine Learning Research, pp. 161-190. PMLR, 12-15 Jul 2023. URL https: //proceedings ml wreas wwt.:/praass.///weee 33. ht.ml
(eds.), Proceedings of Thirty Sixth Conference
Bohan Wang, Huishuai Zhang. Meng, Ruoyu Sun, Zhi- Zhi-Ming Ma, and Wei Chen. On the con- vergence of adam under non-uniform smoothness: Separability from sgdm and beyond. arXiv preprint arXiv:2403. 1 15146, 2024.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint ar xrx: 1708.1700.0000 118:01708.03888, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint 1rXiv 2019.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non non-convex optimization. Advances in Neural Information Processing Systems, 33:1551 1-15211,
2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelcrates training: A theoretical justification for adaptivity. In International Conference Learning Rep- resentations, 2020b. ULL.Bttts::/ooeereeeiie
net wewt/forormidd...... Bat.rrummniidd..ggXeWeeeWa.
Jingzhao Zhang, Sai Pranceth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 13:15383-1539,, 2020c.
Jiujia Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. Ad- vances Neural Information Processing Systems, 35:8000-801 1010000-11,,-00 2022.
14

---

Published as a conference paper at ICLR 2025
A AN EXAMPLE FAILS THE EXISTING HEAVY-TAILED NOISES ASSUMPTION
In this section, we provide a simple one-dimensional case that violates the previously used finite p- th moment assumption but satisfies new generalized heavy-tailed noises condition, Assumption 2.4 Extending the example to high dimensions is straightforward, which is left to the reader.
Example A.1. Let F()) _ 2 L.a. [(ax - b)²] where æ E IR a & Bernoulli(q) (g) for some q E (0, 1),
and b az, + w where I. E IR is fixed and w is centered random variable being independent of and only has a finite p-th moment (i.e., E. [| [P] S oP for some a 2 0). For the stochastic gradient
ax, b) - a ab and the true gradient (F)) A Eu [aa] I Eu,b [ab], we let the the noise be E(x)) g b) V F (z:), then
Assumption 2.4 is failed for any pair (oo, 0) where 0o 2 0 can be arbitrary;
Assumption 2.4 is satisfied for a certain pair (oo, (1) where di > 0.
Proof. Note that g a, b) and (x)) can be simplified into
g a. b) a² d2 x.) - aw, VF(x) g(x x..)
Thus, we know
{(x) (a² q)(x xx)) aw
3 Ea,b [I{( Bul |1a² (a () xr.) aw p]
= (1 9)9º x x. 1 glEus [|(1 ()(x xx) -w -1
On the one side, we have
F., [p 2 (1 - 9)4² x - x.1 2000 400,
Therefore, B., [I{()))1] s of cannot hold for any do 2 0.
On the other side, we observe
En [[(1 (xx - x.)) - wll] s E, [[[1 9) | - x.1 + |w||
< 2P- - q) | x. 1 + 2p
(1
En |||||
2 (1 q) |æ x. P + 2 PP.
Hence,
Ea,b [1{())
2 q008 + [[1 q)g²² + 28 20-1p-19 ((1 - q)'l x x.
2 -2p-1900 q0p + [1 - q + 2 P1 9)9 VF (x)
So Assumption 2.4 is satisfied for of & 2p 100 2 and of - 11 19' P(1 q)P.
B FURTHER DISCUSSION ON L, IN THEOREM 3.6
One may think knowing La is necessary under the present version of (Io, In )-smoothness (i.e., Assumption 2.2 It is because the current form of (To, Ts)-smoothness can be only invoked under the hard constraint || y/| S +. As such, regardless of whichever two points F, and 2, we want apply to the descent inequality in Lemma (which serves as the cornerstone in the whole proof), they have to satisfy ||ær, æel < J.-. In other words, one has to know L1 to set the stepsize to ensure Lemma can can be used. Moreover, even if when = 2 or under a weaker condition on noises (e.g., almost surely bounded noises), prior works under exactly the same form of Assumption r.qureq the value of L1 (c.g., see JJi et al. (202T): Crawshaw et al. (2022)). ) even for the famous
adaptive method AdaGrad (Faw et al. 2023 Wang al.) 2023 Hong Lin 2024) and Adam (Wang et al. 2024).
However, this turns out to be too pessimistic. To see why, we first claim that Assumption 2.2 essentially equivalent to the following condition (up to redefining the pair (Lo, L1))
[[VF(()) V F(y)l (To + Ln F[)
|| yll exp (In || -yl)), Var, y Rdd.
15

---

Published as a conference paper at ICLR 2025
Remark B.1. (7) is also known to be equivalent to the Lsym(1) function class. See Definition 3 and Proposition 1. 1.2mn in Chen et al. (2023) for details.
This means that for any 2, y E R. we can still bound the difference between their gradients even if the distance between them larger than Σ, but incurring extra multiplicative term as penalty. As such, it is possible to combine the dynamic stepsize and time-varying momentum, i.e., taking ?) = .yl and Be 31 for some 1,, a. b > 0, to get rid of knowing I- since we can control the size of gradient norm during the warm-up period (i.e., the time before 7/: ('L and then follow similar proof in our paper when т " to obtain the desired result. Whereas,
trade-off, one has to incur an exponential dependence on L1 in the final convergence rate as pointed by Hübler al. (2024).
Lastly, let us prove this important equivalence.
This is the easy case. Suppose 7 holds, then for any æ, y E satisfying ||æ yl there is
implics Assumption 2.2
F V F(yill s (eTo + eL, [[) || yll,
which implies F is (eLo, eLi smohhhh in the sense of Assumption 2.2
Assumption 2.2 implies 7 This direction is not obvious, whose proof in the following
is inspired by Chen et al. (2023). Given z, y E Rd, we define the linear interpolation
(t) & tx + (1 t)y, Vt E [0, 1]. Note that for any n E N satisfying n 2 L1 x yl and i [n]. there is
| y
kn,yy// En.y( (i-1/11))))) 1/-)||
T1
Therefore, we can use Assumption 2.2 to control V (1a)) VF(2zy((-1/o) and obtain the following bound whenever 2 L1 | yll.
VF(x)) FF(')l
VF (F (Vx)) VF (1
VF F F (2,,) VF ( (1-1/n))
1=1
0 yl
| yl
Lo + L (F (11//))]
h( h(-1//),
(8)
where h(1) A Lo + L1 (= (1)] 11 E [0,
1]. We notice that h is continuous because
for any given E (0, 1) and 8 > 0, for s [0, 1] satisfying Is S L,b(t) = there is
min(h(t)..c)
(M(s) n(t)) Ln |I Z (s)) IVF (t)) s L1 VV (z (s)) VF(za,
(4) < LI(() [ (8) - Zn (1)l = (()) | yll Is -| S E,
(b)
where (a) is due to 1 (8) zx,((1) || yl - || S + and Assumption 2.2 and (b) holds by Is Lnh(e] x wll
Thus, is integrable [0, 1). which implies
h((-1/m) = | y S. A(()de
[VF(x) V (()) | yl lim Σ
(9)
1=1
By Lemma 2 and Proposition 1.2 in Chen et al. 2023).
is equivalent to 77.
C PROOF OF THE CORE LEMMA 4.3 AND SOME DISCUSSIONS
we need the following technique tool, which based on the regret analysis of the AdaGrad algorithm as mentioned in Subsection 4.2
Before proving Lemma 4.3
We especially thank the anonymous Reviewer tQr8 for suggesting this direction during the discussion.
16

---

Published as a conference paper at ICLR 2025
Lemma C.I. (Based Lemma in Rakhlin & Sridharan (2017)) Given sequence of vectors v; E R Vt E N, then there exists a sequence of vectors wi R such that I|w I 1 and every we only depends U1 V satisfying
T
Σ
U
<
Ue wi) VT E.
Proof. W.l.o.g. we assume ||e 0. Otherwise, we let T argmin {t E N: ||ol|| 0}, set w 0 F. Vt [T 1]. and start the following proof at time T.
Let w1 and recursively define w1+1 - II (we - 7101) where Im denotes the Euclidean projection operator onto the unit ball Bd in Rd and & V E.,,lo Clearly, || || S 1 and
only depends on U1 to Ut-1 by construction. Next, observe that
W++1 1l (w, 7v argmin |/w0 wt + vevell
which by the optimality condition implies for any E [Bd
(W++1 - we + yo,, W++1 - u) 1
(w, W (+11 W1+1
u.)
(wi, We+1 - u) s
%
u wi
W 11
|
W
27/2
uu we|| 1|2
|u
Wi+1
11? -I(we wi+1ll
(v,, We u)
(we, we w(+1)
2%/2
| well 1|u
W 11?
||1e|l
Yt
27z
2
where (a) is by the Arithmetic dean-Geemetticc Mean inequality. Hence, for any E Bd and T N,
T
T
Iu
wel 11
u w.+1
Y/
1|1,,11
Ue, wi u) 1
27:
2
1=1
||u
wi
1|2
1u - WT+1 11
T
u
will
T
Yt
||
+
2/11
2
2
7
9t-1
1=2
1=1
(6) 2
1
1
T
74
|
2
|
2
(10)
71 1=2
7
--1
2
PT
t=1
t=1
where (b) is due to
0, Vt 2 by the definition of ys
and
|u
well
2
7e-1
V
|0
since u and we are both Tdd In addition, let
A 0, we notice that
7' | 2
T
1
1
2
7t
2
1-1
2
76-1
7/1
(11)
Combining (10 and 11 and using 7r
2
we have
Σ
Ut,
22
2
|
11
(v, wT) Yu E 18, N.
t=1
Finally, we use max
u1 1
21=
Dz,
1
to obtain
12
2
2 Σ
D ||
Σ t=1
(e we) VT E E.
17

---

Published as a conference paper at ICLR 2025
Now we are ready to prove Lemma 4.3
Proof of Lemma 4.3 We E Fi-1 satisfying
By Lemma
C.1
there exists a sequence random vectors w, R2 such that
T Vt, wT) VT E N.
Σ
S
1=1
We take expectations on both sides to get
E
Σ
S 2TE 2TE
well
[0 w.)l
By noticing that
E (vv. w = E
E ((ve we)
Fi-1ll = E (IE
Fi-1], w.y1 0,
we find
E
Σ v
s 2E
Σ |
Finally, by observing v ΣT= ||,,1'
<
vp E [1, 2]. the proof is hence complete.
Lastly, we briefly talk about the difference between Lemma 4.3 and Lemma 4 in Kornilov al.
D t= 2 ||
2023), the latter of which essentially states an inequality E
< 2T under the same
Vt E [T]. Though it is possible to employ their mequality to prove convergence under the traditional heavy-tailed noises assumption (i.e., 01 0 in Assumption 2.4). whether is applicable under remains unclear since dealing with the new term in the generalized heavy-tailed noises assumption requires finer conditional expectation argument shown in the proof of Lemma D.5 Hence, believe that our new Lemma 4.3 is more general.
setting in Lemma 4.3 and an additional condition E || ||
Assumption 2.4
D FULL THEOREMS AND OTHER MISSING PROOFS
D.1 UPPER BOUNDS
Theorem D.I. (Full version of Theorem 3.2
Under Assumptions
2.1
2.2
2.3
and
2.4
let A
F(x1) - Fr, then for any E 14, by taking
{
A
+ + VF(x1)]]
26v 1)
3p-2
8. B = -min
1, max
T
of
(1 A)
1- 3
{ [16V .
11 min
B = max
LoT
8L1
Algorithm
guaraattes
1
T
A + (0o + to VF
"
p-1
A A
B[]VF(>)II =0
T
T
T
1
(A,L, + (av + o1 VF
00
2p-1
(A
p-1
30 30
(BT) #-
(BT)ap-2 -
18

---

Published as a conference paper at ICLR 2025
Proof. Because 7/ 17 8L, (7) to obtain
1-8 1,, vt [T). we can safely invoke Lemma D.4 with n 17, Vt
LOT
T
T 1
[
2n
Σ
(12)
2
Next, by Lemma
D.5 with 1/: = 31 3, E [T]. have for any E [T].
2 E || <
8t (oo 01 [ + (11- B)
Σ go(t-s)
p=l
00
2v2
8 g--0+1 11
(1
3,
2_1
2
1 1-
BnLo
8 (00 01 VF +
1
BP)
00
1-
2
Σ
8 L VF(2,-1)]]
3)
o E VF(x))
2/2
B
3d (00 +
2-1 3) " 00
B
1-
2/2 _
g gt-s+1 /L
Σ (1
3)3²
σ E VF(x.)]]
2=2
==1
where we use SP < B when p 2 1 and B < 1 in the last step. As such, we know
T
2
T
T
2,3 Lo
Σ
En
||| <
8t (au + 01
+1 #)
+
+ Σ
B
1-3
t=1
4v2n
23
L E
(
V
Σ
o
B"
1=1
4
(Do + a1
VF x. II)
+ (1 -
(1- -
Too
+ 1-3
2,302
B
1-3
2,812 L
4
Σ
(13)
1-
where the last step we use non-negative for i E (1,2).
Σ Σi= = Σt=
Dt I
when the summands
19

---

Published as a conference paper at ICLR 2025
Now plugging 13 into 12
to get
E
(1
4v2n
3 + 01 [VF(())])
AA1
+11 (11-3) B)
2(1-3)
BF
1-
T
(1+33)n2L L1
4
+
Σ
2(1
(8)
B
1=1
(0)
LoT
4v2n
[oo + 01 |F((1)]l
1
(1 (1-8) B) = Too
1-3
B" 1
1 1-8 B
T
21 2
4v
+
Σ
[
1- 3
B
1=1
(8)
2T
LOT
4v2n
do + 01 VF x1 ||
T
1
+ (1- 3) Too Too
+ Too
1-
B ,
1-8 B
2
(14)
where we use 3 < 1 in (a) and n
1-8 81,1
B (16v in (b). We observe that
(14
implies
T
E
(I
2A
AnLoT
+
8/2
00 +
01
|V
+11 -
(11-3) -) 2 Too
TTo
(15)
"
1 1 B
B
--1
1-8 3
9 0
A1 + (00 + t [ I1)/B" -
ALoT
+ (1- 3) 007 T
1-3 3
1- B
B
(4)
0
A1L + (o0 t VF (1F(==)))/BB+ P=1 + VALTT
LA + (ou 01 VF (z)
[I) (
(o) 30
30
300
3--7
T
2p
B Bap-2
(16)
where plug in n min
(1-MAA) 1-9 LoT
in (c) and use the following estimation in (d):
8L1
Let U & A F
to /(())))
and A
Lo
3p-2
we know B
ofl
T
min (1, max {U,V})
VJ).
Then there is
C +
C2
+Cs(1 =²
1-
8
1-B
<Ci
|+ max {U,V})
+ 102 1+ max [U
(1(
Ca (max (U V3) '
<C1 1+ 1 + v C3
[+ (
+ +C3 (U" + )
G π
+ - + +C (1 + v(t)
C22
where
11//""" C2 2 ALOT, C2 C To p-1
G + (00 to VF x 11/
20

---

Published as a conference paper at ICLR 2025
Finally, divide both sides of (66) by T obtain the desired result.
Theorem D.2. (Full version of Theorem 3.6 Under Assumptions 2.1
2.2
2.3
and
2.4
let
A
F - F., then for any T E N, by taking
5: ===3-1 T
min The 17 mmin
S B max
7
SLTT
Algorithm
guarantees
( (oo t [V
A + Lo
EIIVF(=))I
VT
T
(BT)
In parficular, if
always set B get rid of the tail index p.
16
Remark D.3. We note that is possible improve the threshold 16v to slightly bigger constant, but this still cannot help us to remove the requirement of needing p when on becomes larger. Thus, we do not put further effort into optimizing this constant but keep it as it is.
Proof.
Note that (1)) still holds under current parameter choices since = min
T 8L,T
min
1-8
Hence, we have
T
8Lg
T
E [1
A
NooT
do + to [VllVV((
50
+
1 1-8 +
+(1 -1 Too
1 1-8
A (00 + 0 VF(( II) 1
T
(1-
To
(A1 + Looy
1-3 3
1-3
B'
[ (oo + a [VF
ToT
VT + (AI Lo)T
B" 7-1
where we use 7) min
min
1-8 1-8 {v - 82,
in (a) and 1 B
in (b).
We
SL,T
T2
divide both sides by T' to obtain the desired result.
D.2 LOWER BOUND
In this subsection, we will prove the lower bound, Theorem 3.3 The proof is simple variation of Zhang et al. 2020c), which itself is based on Carmon et al. 2020): Arjevani et al. (2023)
Proof of Theorem 3.3 For any æ E Rd and a E [0, 1]. we denote by prog, (z) the highest index
whose entry is c-far from i.e.,
prog, (x)) A max (i [d] [<+]||]
a} where max 0 - 0.
Now given d N, we introduce the following underlying function originally proposed by Carmon et al. 2020).
fa(x:) A (=1)((<11))
Σ
1 x-=x 1))0(--200))) (-(11) (a=li (eefi-1))0(/1ppp) (x(1),
where
(1) A 0
t t
+(1) 2 Ve J exp(- 72/2)
eep (2f 1) -2
t>
1
By Lemma in Arjevani al. (2023). la admits the following properties:
21

---

and Published as a conference paper at ICLR 2025
1. fa(0) fa,x I ód, where fa, inf fa(æ) and ò 12.
2. fa 6-smooth, where é 152.
3. For all R. [[ S 7 where 7 23.
4. For all x E RR, progo V Vf(())) & prog (m)) + 1.
5. For x E R² and prog (z). Vfa(æ) Vfa((<144) and [Va(())ls
[fa( where youbil _ y S i].
6. For all æ R4, if progi (a) < then
[[a())]] 1.
Now consider the following stochastic oracle introduced by Arjevani al. (202))
ha(a, [] fa(x)]] [ [L+1 1 i
prog: (z)
( ( )) vi [d],
where z Bernoullig)) and q E [0, 1] will be specified later. As can check, Ez [ha( 2)] [[a())), Vx E Rd. Moreover, by Lemma in Arjevani et al. (2023), we know ha is a probability-g zero-chain (see Definition Arjevani al. (2023) for what is) and satisfies almost surely
(1)( fa(=)) s
g 1x
Ve E R².
(17)
Next, given p E (1,2), A1, Lo, > 0, and small enough e, we define d a
48862
Lod2 fa 5 where À A
21s Lo
Fa(x)
Moreover, we let
92(x, 2) a Lod ha
x : and q
[478)
do
q S 1 can true since we assume that E is small enough.
Note that Fa is lower bounded since fa is lower bounded and thus satisfies Assumption 2.1 In addition, we have VFa(æ)) Lad V fa (+) which implies Fa is Lo-shooth because fa is e-smooth. So Fa also satisfies Assumption 2.2 with L1 O. Moreover, we can find
(O - inf Fx(x) = Lod2
x fa
Sa.-) x Lod2
Lo>2
AjLo A
8d -
8
zERa
486=2
Now let us verify
Eg (g, 2]] Ex Lod
Lod fa
hdd
x.2
VF((x).
Hence, ga( 2) satisfies Assumption 2.3
Lastly, we know
E, [x)))(0r - = Lod [Fa(=)]1]]=
F
E=
hdd
x 2 - V (7)
Lod7
4
E
2
1
P7
8
4
Lndy> )
(1 (1- -p)
gp-1
(1
p-
1 q +
(2>E) q)
qp
gP-1
(4yE)p qP-1
of-
Thus, ga(2,2) 2) satisfies Assumption 2.4 with 0.
Finally, by Lemma 1 in Arjevani et al. (002)) for any zero-respecting algorithm starting from
æ0 with probability at least 1. progo (x:e)
d, VI. & d-1 By noticing that prog, (*x) <
2q
22

---

Published as a conference paper at ICLR 2025
progo (x) (xt) d. then have with probability at least 2/2 d-1, which implies
1,
2q
V = Lod E
dit
Lod 2
d-1
= E, vt
2g
Thus, to output an e-stationary point, the algorithm need at least the following number of iterations
d-1
A 29 2 4
(
-1)
0o
A= 32
=
145
D.3 HELPFUL LEMMAS
We first recall the notations as follows
6 2 my vF(x;) 1 [T]
(18)
mo VF((1) ==
D, A 1,2 (V VF(x;)) e [T],
(19)
< A g. VF(x;), Vi E B W [T),
(20)
B
1
& _ VF(x;) = B
E vt E [T).
(21)
21
Now we are ready to start the proof.
Lemma D.4. (Full version of Lemma 4.1 Under Assumptions i < 1 Vt E [T]. then Algorithm 1 guarantees
2.1 and 2.2
let A & F(x1)) - Fx,
T Lo + L, V
Σ The V
< A +
Σ
2m || +
1/2
2
t=1
t=
Proof. Note that | ærll
W/ [m
S m S L
now, we then invoke Lemma 2.5 to obtain
for any t E [T].
F(x++1)= S Fxx) (VF(x;), 0++1 xt) + Lo + L1 [FF()))
10+11 - xel1
2
= =((x)) тh. (VF( my/mm.ll) Lo Ln 11V F(x:)))]
T/
2
18
F(x..) - 7/t ||m + 7/ (E,, me/1mm,l) + La Li
|
2
Lo Li 1I [[F)(()))
F(x:)) t/t ||m]]] ||ee||
mE
(6)
Lo + L1 [[VF((x))]
2 F(x:) - Th VF(x;)] + 21/ ||, +
(22)
2
where (a) is by (e,, m./1 m//mmmml)) < ||e||| |////|mm ||eell and (b) is due to mm
[v;) + ell Z |[ || up from t = 1 to T. we have
Taking expectations on both sides of (2 and summing
I
T Lo L
(2x)
< E F(()))
Σ BIIV
+
Σ
2m |||e +
Σ
nh.
2
1
Finally, we rearrange the terms, apply E [F(T++1) 2 F. due to Assumption F(m) F. get the desired result.
2.1 and use A
23

---

Published as a conference paper at ICLR 2025
Lemma D.5. (Full version of Lemma 4.5 then Algorithm 7 guarantees
Under Assumptions
2.2
2.3 and
2.4
if
I 1 A4
[T].
$
2v2 E
t Σ
p- ||| |||
B1 o1 +
(1 (.))((311s)))
(B=+2=)P
B²
Beit (Lo + ([
2=2
2 2
t
Σ (1 - - e [
P=1
Proof. Based on Lemma 4.2 we know for any t E [2].
| S S1. ||ol|| +
Σ Bast D.
+
Σ (1
Ba) (.)8++1555
+ [[| B...B [[eool] E
Σ
Do D
+ Σ (1 B.) 3.)8
(23)
First, by the definition of EO
m10
VF(x1) = 91 VF(z1)
B Disl Ei. we have
B
(a)
2
E
colll
E
E
Σ ||
B
(b)
2v2
Σ
[|(|||
Assumption 2.4
2v2 B
(of
of [[
(c) 2
(00 + VF(x)))).
(24)
B
where (a) is by applying Lemma 4.3 with v, A si Vi E [B], (b) is due to Hölder's inequality, and (c) is because of (x y) S xr + y when p 2
Next, we know
Σ Bos D2
But D.l
Bad VF(xx-11) - VF(x,)]] 1,22
Assumption
Bos (Lo La |VF(( ||c, x,-1 || 1 1,22
Bad (Lo + L1 VF(x.-1)1)) 7--11
Bes (Lo + b1 (FF 1-11
where (d) is by ||x5, F xz-1 || Therefore, we have
170 T
m m
7--1 from the update rule of Algorithm
E
Σ Bast D.
<
Bun (Lo + ([V
(25)
2
24

---

Published as a conference paper at ICLR 2025
Moreover, let (1)-1)8++ - (1-
8,)8 then there i8
Vi [B] E [t] and note that this sequence satisfies
the requirement of Lemma 4.3
E
Σ
1
B.)B
E
(1 3,) 1.
B E
Σ> Σ
B
$1
2v2
Σ
B
2v2
IE
(1 (3)+( ||
(26)
B
#=1 1=1
Observe that
B
E
Σ
Σ
(1 -1
(Bo4 [kE_1l))
F
8=
1=1
(c)
E
Σ (1- (B) |2:1 ||:11
F
B
t-1 B Σ s=1
E
- (B)+(1) || Fe
+
-
||=:1|
Assumption
B(1 - /
Σ ΣΣ (1 B.) (Bo+(a1) ||%:11"
1=1
A- B
B(1 (.))(3e+1.))Pd)
ΣΣ (1- (.) 1.) |1es
B (1 31 [F:))]]]
(27)
where (c) is by Hölder's inequality. Taking expectations on both sides of 27 get
$
Σ 10 (1 3.)P |E?)|"
E
$7
1-1 B (1 (.) [|E.]l))
<
B(1 (1))))((B++1.)P80
ΣΣ
Bb (1-
B
Recursively applying the above argument from F Fo. we can finally obtain
B 11
E
1.)) ||%
1=1
<
Σ
P (B.+1:)))
oo + B
D (1
(28)
25

---

Published as a conference paper at ICLR 2025
which gives us
E
Σ
(1
Be)
26
2
Σ (B ||=:||
x B
E
B
:
28
2
Σ 3.) (3)+111))
oo +
2v2
Σ (1
(29)
B BFF
B B=
Combining
23
24
25
and
29
we finally obtain for any t E [T].
2v2
E [|]
<
Bi +1 +
E 21-BB)1 (8++1a))))))) a
B -
+
Σ
Bost (Lo + V
8=2
2v2
(1 - 1.) (|
B ?
8=1
26


Reviews:
[{"review_id": "3f5FHiNobF", "reviewer": "Reviewer_R9Yi", "summary": "This paper addresses two questions:\n- Is gradient clipping the only way to guarantee convergence under heavy-tailed noises? Can an alternate algorithm achieve the optimal convergence?\n- Does there exist an algorithm that provably converges under heavy-tailed noises even if the tail index p is unknown?", "questions": "- In line 336, how is $\\mathbb E \\langle \\epsilon_t^b, \\epsilon_t^u \\rangle = 0$?\n- In both Theorem 3.2 and 3.6, batch size $B=1$. Is there any case where a larger batch-size is needed for convergence?\n- lines 300-304 - can you explain this point about needing $p$ when $\\sigma_1 > 0$ a bit more?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written. The results are well-explained.", "weaknesses": "- The paper is well-written, but, given the proof-heavy nature of the paper, it is difficult to follow a few things without looking at the Appendix. This is not necessarily a criticism of the paper, but a limitation of the format.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yIlteecx0Y", "reviewer": "Reviewer_tQr8", "summary": "The paper addresses a problem of (generalized) smooth non-convex optimization with heavy-tailed noise in the stochastic gradients and provides new convergence guarantees for the Normalized SGD with Momentum (NSGDM). In particular, the authors assume $(L_0,L_1)$-smoothness, which is strictly more general than standard smoothness, of the objective function, its lower boundedness (classical assumption), and boundedness of the $p$-th moment of the gradient noise for some $p \\in (1,2]$, i.e., $\\mathbb{E}\\|\\| g(x) - \\nabla F(x) \\|\\|^p \\leq \\sigma_0^p + \\sigma_1^p \\|\\| \\nabla F(x)\\|\\|^p$ for all $x \\in \\mathbb{R}^d$, where $F$ is the objective function. Then, the authors provide new results for (mini-batched) NSGDM - a method proposed by Cutcosky & Mehta (2020) - under these assumptions.\n\nThe first result establishes $O(T^{-\\frac{p-1}{3p-2}})$ convergence rate for $\\frac{1}{T}\\sum_{t=1}^T\\mathbb{E}\\|\\| \\nabla F(x_t) \\|\\|$ in the case when $L_0, L_1, \\sigma_0, \\sigma_1, \\Delta_1$, and, more importantly for the paper, $p$ are known. This result matches the known lower bound (when $L_1 = 0$ and $\\sigma_1 = 0$) and the best-known rates for Clipped SGD. Moreover, the result extends the known ones to the case of $L_1 > 0$ and $\\sigma_1 > 0$.\n\nThe second result establishes $O(T^{-\\frac{p-1}{2p}})$ convergence rate but without any prior knowledge about all parameters except of $L_1$. This rate is worse than optimal but still matches it when $p = 2$ (since it is obtained for the parameters with the dependency on $T$ as in the case of $p=2$). This result demonstrates a noticeable robustness of NSGDM.\n\nThe authors also provide a refined formulation of the lower bound from Zhang et al. (2020), though the worst-case example and the proof are largely dependent on the previous results, i.e., on the proofs from Arjevani et al. (2023).", "questions": "**Questions.**\n\nQ1. Is it possible to prove a version of Theorem D.1 when only some upper bounds on problem-related parameters are known, i.e., upper bounds on $L_0, L_1, \\sigma_0, \\sigma_1, \\Delta_1, \\|\\| \\nabla F(x_1) \\|\\|$?\n\nQ2. Is it possible to generalize the results of the paper to the case of $B=1$ even when $\\sigma_1 > 0$? If no, could the authors provide a counter-example or an experiment illustrating that $B$ has to be larger than $1$ in this case?\n\nQ3. Is the result for NSGDM without the prior knowledge of $p$ tight?\n\nQ4. What is the difference between Theorem 3.3 and the result from [1]? As far as I see, the proofs are almost identical to the one from [2] (up to the difference in the choice of $q$).\n\nQ5. Is it possible to generalize the results of this paper to the case when parameters are horizon-independent, i.e., independent of the total number of steps $T$, like in [3]?\n\nQ6. Could the authors comment on the differences between Lemma 4.3 and Lemma 7 from [4] and add this discussion to the paper?\n\nQ7. Line 809: why is the assumption with $\\|\\| x - y\\|\\|| \\leq c/L_1$ is stronger than the one for $\\|\\| x-y \\|\\| \\leq 1/L_1$? Aren't they both equivalent (up to the redefinition of $L_0$ and $L_1$) to the so-called symmetric $(L_0,L_1)$-smoothness from [5]?\n\n\n\n**Comments.**\n\nC1. I recommend adding the statements of the main results in the full generality to the main text, i.e., with $\\sigma_1 > 0$. In my opinion, they are quite understandable for the broad audience, so they can be placed in the main text.\n\nC2. Lines 104-106: the rate from Nguen et al. (2023) in the noiseless regime is $O(T^{-\\frac{2p-1}{3p-2}})$ (for the average of the expected squared norms of the gradients), which is worse than $O(T^{-\\frac{1}{2}})$.\n\nC3. I believe that the discussion of the related work on $(L_0,L_1)$-smoothness should be extended. In particular, the authors should discuss how their results can be compared to the known results for NSGDM from [3].\n\nC4. Line 334, \"following the existing literature\": the authors should provide the reference to the paper.\n\nC5. Sketch of the proof of Lemma 4.2 on page 8: $m_0$ is undefined. I assume that $m_0 = g_1$.\n\nC6. I suggest adding in (10) more details about the last step (that the authors used $\\sum_{t}a_t b_t \\leq (\\sum_t a_t)(\\sum_t b_t)$ for non-negative sequences).\n\nC7. The last step in (13) is a bit technical and requires the reader to do a lot of calculations on their own. I suggest adding more details on how you estimate each term.\n\nC8. Regarding the proof of Theorem 3.3: essentially, the proof is almost identical to the one from [2] up to the replacement of $\\sigma$ with $\\frac{\\sigma_0^{\\frac{p}{2(p-1)}}}{4\\gamma \\varepsilon^{\\frac{p}{2(p-1)}-1}}$ because for the considered example all moments exist (though they are different). I also encourage the authors to mention explicitly that the construction in the lower bound depends on the target accuracy $\\varepsilon$.\n\n\n\n\n**Minor comments.**\n\nM1. Line 16: noise, that --> noise, which\n\nM2. Line 48: Simsekli et al. 2019  -- the same reference appear twice\n\nM3. Line 108: should be \"the results from Cutkosky & Mehta (2021); Liu et al. (2024) also depend\"\n\nM4. Line 256: Theorem 3.2 is not perfectly adaptive to $\\sigma_0$ since it requires its knowledge. I suggest to rewrite this sentence.\n\nM5. Line 324: help --> helps\n\nM6. Line 325: smooth --> smoothness\n\nM7. Title of Appendix C: 4.4 --> 4.3\n\nM8. Line 855: AM-GM - better to replace abbreviation with a full version.\n\n---\nReferences\n\n[1] Zhang et al. Why are Adaptive Methods Good for Attention Models? NeurIPS 2020.\n\n[2] Arjevani et al. Lower bounds for non-convex stochastic optimization. Mathematical Programming 2023.\n\n[3] Hübler et al. Parameter-agnostic optimization under relaxed smoothness. AISTATS 2024\n\n[4] Kornilov et al. Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. NeurIPS 2023\n\n[5] Chen et al. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. ICML 2023", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The paper addresses an important question and makes an important contribution to the literature on stochastic optimization with heavy-tailed noise. In particular, I would like to highlight Theorem 3.6, which gives the first convergence result in the considered setting without the knowledge of $p$, and Lemma 4.3, which generalizes Lemma 7 from [1] and gives an alternative and quite simple proof to a similar result.\n\nS2. The generality of the results is also noticeable. While most of the existing works on the stochastic optimization with the heavy-tailed noise focus on smooth problems, this paper considers $(L_0,L_1)$-smooth setup, which is known to better reflect the properties of the minimization problems arising in the training of neural networks. Moreover, bound on the $p$-th moment of the noise contains an additive term proportional to $\\|\\| \\nabla F(x)\\|\\|^p$, while the previous works assume uniform boundedness of the $p$-th moment of the noise.\n\nS3. The paper is, in general, well-written and easy to follow. I also did not find any mistakes in the proofs (though some parts could be further improved). Moreover, the authors provide intuitive explanations in the main text and the sketch of the proof, allowing to understand the key steps of the proof and also to see what the main technical novelty of the paper (which I believe is Lemma 4.3; other parts of the proof are very similar to the previous works such as [2, 3]; nevertheless, it does not undermine the contribution of the paper, in my opinion). \n\n\n\n---\nReferences\n\n[1] Kornilov et al. Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. NeurIPS 2023\n\n[2] Cutckosky & Mehta. Momentum Improves Normalized SGD. ICML 2020\n\n[3] Hübler et al. Parameter-agnostic optimization under relaxed smoothness. AISTATS 2024", "weaknesses": "W1. When $\\sigma_1 > 0$, the result of Theorem D.1 requires the knowledge of $\\|\\| \\nabla F(x_1) \\|\\|$. Moreover, the theorem is formulated in such a way that all problem-related parameters are required to be known precisely.\n\nW2. When $\\sigma_1 > 0$, the results hold only for $B > 1$.\n\nW3. The paper lacks numerical experiments. In particular, it would be very interesting to see in some (even toy) experiments how NSGDM depends on the choice of $\\beta$ and whether the rate $O(T^{-\\frac{p-1}{2p}})$ is indeed tight *for NSGDM* when $p$ is unknown.\n\nNevertheless, I believe that the strengths outweigh the weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q3UX2kjsOl", "reviewer": "Reviewer_jQHz", "summary": "By revisiting the existing Normalized Stochastic Gradient Descent with Momentum (NSGDM) algorithm authors provide the first convergence result under heavy-tailed noises but without gradient clipping. They also establish the first optimal convergence rate in the case where the tail index p is unknown in advance, which is arguably the common scenario in practice. The results are quite good from mathematical point of view (up to a further generalization for rates in terms of probability of large deviations), but in my opinion are mainly interesting from theoretical point of view, not practical (e.g. I can not find experiments). Moreover, when the tail index p is unknown in advance it seems the result not necessarily to be optimal. \nBTW It seems that these papers https://arxiv.org/pdf/2409.14989, https://arxiv.org/pdf/2410.13849 could be added in to the literature survey.", "questions": "Is it possible to generalize the result for convex problems? I can make rating significantly higher if you can add this case, but it seems to be more difficult one in my opinion (hope that you can dissuade me).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I guess the paper is good from mathematical point of view. The results is accurate, original, well presented.", "weaknesses": "1) This is not the honest normalization procedure that is of independent interest. The motivation to replace clipping by something else is not very attractive for me. For example, under different symmetrical assumptions on noise you can think of different medians procedure rather that clipping, or sign SGD type procedures...\n2) Many modern paper on heavy-tails SGD methods include analysis with high-probability deviations bounds, rather than in considered paper\n3) Lack of numerical experiments. Weak motivation to consider convergence in terms of the norm of the gradient for real non-convex applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wiVUOU0fUd", "reviewer": "Reviewer_3wrr", "summary": "This paper studies the batched normalized stochastic gradient descent with momentum (Batched NSGDM)\nand proves that convergence under heavy-tailed noise, when only $p$-th moment is finite where $p$ is between $1$ and $2$.\nConvergence analysis is also obtained when the tail-index $p$ is unknown. The assumptions are relatively mild. \nOne ingredient in the proof is a novel expected inequality for the vector-valued martingale difference sequence,\nwhich might be of independent interest.", "questions": "(1) In the abstract, it seems the word batched is never mentioned although you focus on batched NSGDM in the rest of the paper.\n\n(2) It might be better to define $T$ in the abstract.\n\n(3) In Section 1.1., \"We initial the study'' should be ''We initiate the study''.\n\n(4) It is nice that you provided examples in the appendix regarding your Assumption 2.4. I think it would be nicer if you can provide some references and comparisons to the literature since you mentioned \"Assumption 2.4. is a relaxation of the traditional heavy-tailed noises assumption''\n\n(5) In Algorithm 1, how do you define it when $m_{t}=0$?\n\n(6) In Lemma 4.1., Lemma 4.2., it seems that you are working with general $\\beta_{t}$, $\\eta_{t}$,  does that mean you can extend your Theorem 3.2, Theorem 3.6. to allow momentum parameter and learning rate to be time-dependent as well?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Traditionally, under heavy-tailed noise, convergence analysis is carried out under clipping. This paper no longer requires clipping, but rather works with normalized gradient, and brings a new angle and contribution to this field.\n\n(2) The paper is well written and the intuition behind the results and proofs is well explained.\n\n(3) Some novel inequality is derived (Lemma 4.3.) as a by-product of the proof, which might be useful in other contexts.", "weaknesses": "(1) As the paper mentions in the conclusion and future work section, it would be interesting to investigate the adaptive gradient methods in the future because batched NSGDM is not commonly used in practice. \n\n(2) The paper should make it more clear whether batched NSGDM is proposed as a novel algorithm in this paper, or it already exists in the literature (if that's the case, some references should be provided).  If batched NSGDM is not commonly used or is first proposed in this paper, even though this paper is a theory paper, numerical experiments will significantly strengthen this paper because it can show that batched NSGDM works well under heavy-tailed noise.\n\n(3) Taking batch-size $B=1$ is quite restrictive. If the paper can relax this assumption, it would make the theory stronger. If not, at least, it should be made more clear whether this restriction is due to the limitations from the proof technique, or the limitations of the algorithm itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)