Tight High-Probability Bounds for Nonconvex Heavy-Tailed Scenario under Weaker Assumptions
Authors: Weixin An
Yuanyuan Liu
Fanhua Shang
Han Yu
Junkang Liu
Hongying Liu
Venue: NeurIPS 2025 poster ()
Keywords: weaker assumptions
heavy-tailed noise
(L_0
L_1)-smoothness
optimization
generalization
Primary area: optimization

Abstract: Gradient clipping is increasingly important in centralized learning (CL) and federated learning (FL). Many works focus on its optimization properties under strong assumptions involving Gaussian noise and standard smoothness. However, practical machine learning tasks often only satisfy weaker conditions, such as heavy-tailed noise and $(L_0, L_1)$-smoothness. To bridge this gap, we propose a high-probability analysis for clipped Stochastic Gradient Descent (SGD) under these weaker assumptions. Our findings show a better convergence rate than existing ones can be achieved, and our high-probability analysis does not rely on the bounded gradient assumption. Moreover, we extend our analysis to FL, where a gap remains between expected and high-probability convergence, which the naive clipped SGD cannot bridge. Thus, we design a new \underline{Fed}erated \underline{C}lipped \underline{B}atched \underline{G}radient (FedCBG) algorithm, and prove the convergence and generalization bounds with high probability for the first time. Our analysis reveals the trade-offs between the optimization and generalization performance. Extensive experiments demonstrate that \methodname{} can generalize better to unseen client distributions than state-of-the-art baselines.

Tight High-Probability Bounds for Nonconvex Heavy-Tailed Scenario under Weaker Assumptions
Weixin An', Yuanyuan Fanhua Shang?; Han Yu Junkang Liu?, Hongying Liu4.5+
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, School of Artificial Intelligence, Xidian University, China
School of Computer Science and Technology, Tianjin University, China
SCollege of Computing and Data Science, Nanyang Technological University, Singapore Medicaal School, Tianjin University, China
PPng Cheng Lab, Shenzhen, China
reixinanut@163. 63. com, pyliu@xidian edu. aduu.n cn, fhshang@t ju.barng@jj..ed....o edu. cn yuentu. edu. sq, junkangliukke@mal com, hyliu20098t ju. eu.edu. en
Abstract
Gradient clipping increasingly important in centralized learning (CL) and feder- ated learning (FL). Many works focus its optimization properties under strong assumptions involving Gaussian noise and standard smoothness. However, practical machine learning tasks often only satisfy weaker conditions, such as -taved noise and (Lo, L1 -smoothessss To bridge this gap, we propose a high-probable probbbbbbbbiitty analysis for clipped Stochastic Gradient Descent (SGD) under these weaker as- sumptions. Our findings show better convergence rate than existing ones can be achieved, and assumption. Moreover, we extend our analysis to FL, where a gap remains between expected and tigh-probability convergence, which the naive clipped SGD can not bridge. Thus, we design a new Federated Clipped Batched Gradient (F (FedCBG) algorithm, and prove the convergence and generalization bounds with high proba- bility for the first time. Our analysis reveals the trade-off's between the optimization and generalization performance. Extensive experiments demonstrate that FedCBG can generalize better to unseen client distributions than state-of-the-art baselines.
high-probability analysis does not rely the bounded gradient
Introduction
Gradient clipping has proven effective in training vision and language models 53 56)
Many studies
demonstrated an optimal convergence rate of O(T under finite-variance assumption, where T is the number of iterations or communication rounds. However, recent studies [54] 14 pointed out
that assuming finite-variance noise is overly optimistic for modern machine learning tasks. Instead, is more appropriate assume that the noise has bounded p-th moment, stated in Assumption below (the first weaker assumption), which called heavy-tailed regime. This assumption brings significant challenges for theoretical analysis. Attempts to establish the convergence rate under this assumption have been made. For example, Zhang et al. (54) showed that clipped SGD achieves the state-of- the-art convergence rate in expectation. In practice, models
usually trained only once due to the long training process. Thus, Cutkosky and Mchta [7], Nguyen et al. [35]. Puchkin et al. [37 studied high-probability convergence, offering stronger guarantee for each individual run.
However, the above high-proe cecbbbrbbbbblity results are achievable only under standard smoothness. Works have demonstrated that some language and vision models [53 46 can not satisfy the standard
"Correpooding authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

epoch
0.15
0.06
250
200
Smoothness
0.04
Density
150
0.02
0.05
50
1
3
4
5
1.5
2.5
Gradient norm
Noise norm
Figure 1: Gradient norm vs estimated Lipschitz smoothness (left) and gradient noise distribution (right) during training for AWD-LSTM (34) on the PTB dataset. Local smoothness positively correlates with gradient norm instead exhibits heavy-tailed behavior and its norm can be as large as 2.5. Similar phenomena also appeared in the Shakespeare dataset, as shown in Fig.
constant, which satisfies Assumption] 2 The gradient noise
smoothness assumption. Instead, Assumption 2 (the second weaker assumption) applies. Zhang et al. [53] first analyzed the convergence properties clipped SGD under the (Lo, L1) -mmoohhnssss assumption, which covers many large language models 66 [8]
The two types of works focus on the single weaker condition, but both conditions can appear in the same model, which can be verified in Fig. [ Thus, there is an urgent need for analysis under both weaker conditions. Besides, these methods mentioned above focus on optimization, not including the generalization properties. Li and Liu [24] first analyzed the generalization of clipped SGD, but both depend on the bounded gradient assumption, which is stronger than Assumption 3 and can not hold even when is quadratic.
heavy-tailed noise also exists. The works [45 44 47 focuses on this issue. The most related work to our paper is [47]. Their analysis is in expectation, which offers a weak guarantee for each single run. Besides, their analysis depends on the restrictive assumption that local gradients are bounded, which may not hold even for the quadratic function and the independent Gaussian random variables. addition, they focus on the optimization performance under the standard smoothness assumption. In summary, there is a lack of studies jointly considering the optimization and generalization properties under weaker conditions the FL setting.
As for federated learning (FL) TO 40
The above analysis naturally raises the following questions:
Q1: Can analyze the clipped methods under only weaker conditions such as heavy-tailed noise and (Lo, L1) -mmoothtssssss assumptions in high probability?
Q2: Can the analysis in CL inspire to design an FL algorithu to achieve the convergence rate matching the lower bound under weaker conditions?
Q3: Can we analyze the high-probability generalization properties under weaker assumptions for both CL and FL?
1.1 Contributions
To answer these questions, we summarize our contributions as follows:
By induction, we prove a faster convergence rate of the clipped SGD under the weaker condi-
tions. By carefully choosing clipping parameter, we obtain a convergence rate O with a probability of at least 1 - 5, 5 E (0, 1), which improves existing high-probability bound 2g (T 3p-2 log" 2 }) (p E (1.2).. Interestingly, our analysis does not rely on the bounded gradient assumption used in 24 25). Besides, provide the generalization analysis for the first time.
2-2g logāp 2p-2
We design a new Federated Clipped Batched Gradient (FedCBG) algorithm for FL under weaker assumptions. We creatively prove the bounded variance of batch gradients, which opens the door to analyzing batch gradients under the heavy-tailed scenario. Then, we prove that FedCBG can 2-2p
T), where m and K is the number achieve the advanced convergence rate of ((mKT) 3p-2 log

---

of clients and local iterations, respectively. Finally, we provide a generalization upper bound for the federated setting for the first time. Our analysis reveals the trade-off between optimization and generalization. A summary of our theoretical contributions can be found in Tables 1 and below.
2
Related Work
2.1 Existing analysis under weaker conditions
Many works such as [54 47] have shown that there exists heavy- noise in many applications. An- alyzing convergence under this scenario is more challenging than for light-tailed noise (e.g.. Gaussian noise) due to the unbounded variance, which makes most existing proof techniques inapplicable. The first type of analysis addressed this issue by assuming the bounded gradient IE, [IV [ { S GP [54 [4 25]. However, this assumption is strong and cannot hold even when the loss is quadratic. As comparison, our inductive analysis only needs the weakened Assumption 3 which also used in works [35] 30]. Besides, the loss functions of many language and vision models can not satisfy the standard smoothness but rather a weaker (Lo, L -smoothness [53 23] (Lo, L1 J-moothness assumption is applied by the works [33] 11 6
18 23 under the light-tailed noise. As for the heavy-
tailed noise, the existing works [54 29 only analyzed the expected rather than probabbbbbyylt convergence rates as shown in Table 4 in the Appendix. In contrast, we propose tight high-pro high-probability analysis under both weaker conditions, offering a stronger guarantee for each individual training.
2.2 Optimization properties for clipped methods
In centralized learning settings, existing studies [54 29 focused on clipping for the heavy-tailed scenario and analyzed the convergence bounds in expectation. Besides, works such as 24 25 35 30) provide high- bigh-probability analysis, which matches the lower bound in expectation. However, the order 2p-2 of log & is at least 2 as shown Table We reduce this order to 2p-1 as shown the same table.
In FL, to the best of our knowledge, there is only one work 47] analyzing convergence rates under the heavy-tailed noise. However, they focus expected rather than high-probability analysis, and optimization properties rather than generalization aspects.
2.3 Generalization for nonconvex problems
Existing generalization analysis contains three types: 1) in expectation [ 9 15
21
22
36
43
50)
2) high probability [22 32 13 20 16). and 3) information theory [ 52 For example, Hardt et al. [1] pioncered generalization analysis in expectation based on stability. However, their analysis requires a very small step size, which leads to an exponential number of iterations. As comparison, the figh-probability analysis allows the constant step size, which controls the generalization error and makes the optimization error decay faster. Besides, can provide stronger guarantee for each single run and is tighter criterion for bounded losses [1] As for the information-theoretic analysis, they are usually Segrrthm--nddeeencee [] In this paper, we provide the high- nigh-probability upper bounds for optimization and generalization and focus on their joint perspective.
3 Preliminaries
Problem setting: In this paper, we focus on the clipped methods for solving the problems in both CL and FL settings. For the CL setting, the population loss is defined as:
F(x) = Eg~P (x;
(I)
where the loss function f is nonconvex w.r.t. x, is network weights, and one sample & is sampled from the distribution P:. Normally, the population risk F(x) is used for generalization but is compu- tationally invisible and it can only be estimated using the empirical risk (s(x)) = : Σ f'x;; &s).
FL (3I) allows multiple participants to share model training results but not data, reducing the risk of data leakage. FL usually addresses the following problem:
F(x) = (F
Eg,r, (x; Eg)],
(2)
where (z; Eg) is the loss at sample E, is sampled from the local distribution P., each client i is sam- pled from meta- distrriittibbtion P. We define the client empirical risk by f((z) 2, 1 f((x;E)
3

---

and the empirical risk on the participating training client data is defined by Fs(z) := E E fx()), where n; is the number of samples of the i-th client and m the number of participating clients. Generalization research in FL. includes the performance gap on unseen client data and unseen client distributions. For the former, the CL. can provide help. In this paper, we focus on the latter. For example, Problem (2) is common in the cross-device FL setting, where is generally large and it reasonable to sample from a meta-distribution to model local distributions of clients [49]. which makes it clear the generalization to non-participating clients.
Notation: We use lower-case letters to denote vectors. For differentiable function f. Vf(x) is the gradient of f at z. We let Fe be the natural filtration for the algorithms. E, is used to denote E1-1 for brevity.
Assumption (Bounded Function). F admits a finite lower bound, i.e., F = inf, F(x) -00. 1 satisfying | - vll I LT' VVs (x) - F>s(())l $ (To + [=([VFs(=)]lll= - -yll holding with smoothness parameter & = Lo + L1 &.lVE [F)())]
Assumption 2 ((Tn, Ln -Smootheess). The smoothness of the function Fs means that for Var, y
For the federated setting, the local (Lo, L,) Lip-sihsh continuous gradient for each client means < V (x))))(=== When L, = O. they become standard smoothness. Assumption 3 (Heavy-tailed Noise). For the centralized setting, the stochastic gradient estimator unbiased, i.e., B [{; (f) Besides, the gradient noise satisfies the heavy-tailed condition Eg] (s))) E))l S op, (1,
-
For the federated setting, the local gradient estimator unbiased, i.e, f.; {)] = Vf())). Besides, the local stochastic gradient noise in the i-th client follows the heavy-tailed distribution, i.., Egg [e][V[((() - fi(:; E) Sop ppp.p. E (1,2).
Many works such as image classification 42 training the large language models [54] and FL [47 have shown that stochastic gradient noise usually follows the heavy-tailed distribution, which is also corroborated by Fig. []] Some works 7 25 have made this assumption concrete to that the stochastic gradients are bounded in p-th moment, i.e., E2 || [ 5I < Go (or E,ll V fa(2,, I| GP in
FL), for some G > 0. However, it does not hold even when f is quadratic and Vf(x; Fz) (or [x; { V (z) in FL) is an independent centered Gaussian random variable. In contrast, Assumption is weaker. In this paper, we focus on the analysis under Assumptions 33
Tighter High-probability Bounds in the Centralized Setting
To answer Q1, we first consider the optimization properties of clipped SGD in Subsection 4.1 Besides, we prove its generalization bound Subsection 4.2
4.1 Tighter high-probability convergence under weaker conditions
The pseudocode of clipped SGD is shown in Algorithm In each iteration, clipped SGD performs gradient descent along the clipped gradient V (xy; Ex.)
A Algorithm Clipped SGD
Initialize: To. step size 1) and clipping parameter X. 1: for t = 0. 1......, T
do
2: Draw i.i.d. Es. stochastic sample;
We extend the analysis in 135 to the (Lo, L1) )-smoothness assumption, which can cover more applications. In Theorem I. we propose better parameter choices and prove a faster convergence rate than existing analyses such as [35 30.
3: Vf(az; E,, = minf1, [((eee))) /V (Zrii)))
4: It-1 = It ,/ fmm;
5: end for
6: Randomly draw from 21,..,, or at uniform; Output: 4.
7 Theorem 1. We assume that Assumptions
and 3 hold. If we choose X and qj satisfying X where R Lo + 2(L1 + 1)R, the constant F+, p max(log - 1}, the clipped SGD Σt [| (T 2 (log F) 3
O (log {)) 2222) ") O(T " (log
T 2x
R > 41 Ly 4v ATT. Lo A (2)
(Algorithm 1) can achieve the convergence rate of 1
T
with the probability at least 1 - ô for any d E (0, 1).

---

Theorem Doffers new probbabibyyility optimization bound for clipped SGD. According to Jensen's s inequality, the bound implies that -
+ Σ [x))( O t J //T which matches the lower bound $) in [54] up to logarithmic factor. Compared with existing results, our bound has the following advantages.
Table I: Comparison of existing high-probabbinn (HP) analysis in centralized learning (CL). We use 1 E [[V )1 and + - [+ as the criterion in high probability. Abbreviation: Standard smoothness (SS), (Zo, L1j smmoothhssss ((Lo, Li)). Heavy-tailed (HT), Theorem (Th.). Here, G is a constant, E (0, and E (1, It can be seen that our Theorems and 2 achhiee better optimization convergence and the state-of-the toto-of-the-arr art generalization bound under weaker assumptions.
Assumptions
Bounds
Methods
Additional Assumptions
Smooth
Noise
Optimization
Generalization
24
SS
HT
( SG
0
To Ti7z log" !)
2pm2 )((+) 3p-2 log
322
25
SS
HT (MI G
OTT 5- log !)
((
log (v 524
135
SS
HT
O log h ))
30
SS
HT
O log /)
Th.
(Lo, L1)
HT
O(T 3p-3 log .p- T T)((( 5p-2 log
Addressed the challenges under the weaker assumption. In analysis, the clipped SGD can deal with the ( (Ta, In -smoothness rather than only standard smoothness. The generalized smoothness increased analysis difficulty due to extra V Fa():l ]I in the upper bound ((To, I, smmosmmosssss makes the gradient upper bound implicit in an inequality, which complicates the analysis). Specifically, can lead to high-order term containing || [>)]]= The previous works like [51] keep it till the end
and use the boundedness of clipped gradients to choose step size Instead, Zhang et al. [53] chooses carefully clipped step size min TVPs(=]]] } to achieve convergence. But they focus on noise with
nd
bounded variance need additional assumption [=; Fss S which are not practical even when the loss is quadratic. However, the noise variance can not be easily bounded under the heavy-tailed scenario, and the boundedness of clipped gradients and clipped step sizes can be used for high-order terms. Thus, this paper still faces the challenge of high-order terms.
Inspired by the analysis in 23 for bounded variance, we prove Theorem ! by induction. In Appendix L. we show how to use induction arguments to handle (Lo, L1) -s)ossmmoonnssss and remove the bounded gradient assumption, and here give a proof sketch.
The key in the convergence rate analysis is to show that || Fs()))) < 3- By induction hypothesis at / < l), creatively solve a quadratic inequality w.r.t. [[V]s(1)) so that the gradient F(x)]l can be controlled under the (Lo, I1 Lsmosmothsnssss when À is greater than a constant. Based these, we construct new martingale difference sequence Σ
Proof sketch. sketch.
()) (VFsss (x:)), ), 8.) produced by (Lo, L1) J-smoothness, which does not appear in standard analysis like in 35 where 0f = f {,.) - E,IV f(x;; Ez)).. Next, by carefully choosing À and 17, we can obtain the following induction AT+1
E [v:))( 2A, with the probability least
1- 8, thereby achieving the desired convergence rate.
Tighter convergence bound. We amalyzed the parameter selection in 35 and found that O is already tight but the order of log can be reduced. By analyzing the inequalities that À satisfies
in our induction, set À sp- (log T) F)r-<r) ) and 7 O[ (log F) - ) which yields
tighter convergence rate on the logarithmic factor compared with 30]. as shown in Table [
4.2 Generalization bound under weaker assumptions
In addition to optimization, we analyze the generalization bound of clipped SGD answer Q3. We use the term |VF((x))) to estimate this bound. Similar criteria can be found in 25 20).
5

---

Theorem 2.
We assume that Assumptions
and 3 hold. We set the same step size and clipping
parameter as Theorem we choose T
T E [V(x))] S (( log then with probability at least Algorithm
can uchieve 1
Theorem
shows that clipped SGD can guarantee the generalization bound of the order O( log22-i 2==7 3 (
3) under weaker assumptions, such as heavy-tailed noise and (Lo, L1)- smoothness. Besides, Theorem is the first high-probability generalization analysis without bounded gradient assumption. For clarification, we provide proof sketch.
Proof sketch. We estimate the term || F as follows |VF(2))) < 2 F
F(x,) (x,(1) The first term is optimization error and we can bound it by Theorem I The second term is generalization error due to approximating the true gradient with its em- pirical counterpart and we bound it by generalized uniform convergence as shown in Lemma In Lemma 5, the value of R needs to be quantified. We prove that the generalization error in- creases as training progresses and we can choose R maxi<<<т || Next, we decompose | into A1, A2, Ag by Triangle Inequality and combine them with our inductive Lemma to get | = O(T 3
log 4) Along this line of thought, we successfully bounded || (xx)
Advantages compared with existing analysis
We offer generalized uniform convergence for (Lo, L1) -mmoohh objective as shown in Lemma which generalizes the results in 20 25
induction Lemma 6, which can guarantee that [[V < with the probability at least 1 8. This analysis removes the bounded gradient assumption in i.e., [R [ S G and achieves the first generalization upper bound.
Remove the bounded gradient assumption. We
The Proposed FedCBG Algorithm for the Federated Setting
As we discussed above, heavy-tailed noise also exists in FL.. answer Q2, we extend Theorems a FI., which inspires us to design an FedCBG algorithm to match the optimization lower bound Besides, we provide the high- probabbbbabiltty generalization bound for the first time.
5.1 Federated clipped batch gradient algorithm
To handle the heavy-tailed noise, we design a Federated Clipped Batch Gradient (FedCBC) algorithm shown in Algorithm / which mainly contains two parts:
In the client, use clipped batch
gradient (a cl,,) to perform gra- dient descent, where Vf (h.)
Algorithm FedCBG Algorithm
Initialize: Initial point To, local step size 17, global learn-
min TVJ.(Z, (TD MhI f +1,)
ing rate y and clipping parameter X.
and ch. = {(eh.); D which is different from the existing methods such as [47). where they use single sample
1: for ( = 0. 1...., T (communication round) do
for each client E [m] parallel do
3:
Update local model: x!
in each local update. This difference one of the key reasons why we obtain a convergence rate matching the lower bound under the more difficult criterion, ie., in high probability.
4:
for = o.... K - (local update step) do
5:
Draw i.i.d. stochastic samples e.;
6:
k+1 24, fi <h,);
7:
end for
8: Send A Σk= V <t.) to the server.
9: end for
In the server, we design a "sum- aggregation" paradigm Iz+1 xt y Em A. which the other reason why our FedCBG can achieve the con- vergence rate high probability match- ing the lower bound.
10: Global sum-aggregation server:
11: Server update: Ø141 2, - Σm Ag
12: Broadcasting I++1 to clients.
13: end for
Output: aT.

---

5.2 Convergence rate of our FedCBG algorithm
To prove the convergence rate of FedCBG, we need to bound the variance of the batch gradient under the heavy-tailed noise assumption. Compared to the Gaussian noise (light-tailed) assumption, such analysis more difficult. Fortunately, by Hölder Inequality and Markov's 's Inequality, we have proved an upper bound on this variance for the first time in Lemma I
Lemma 1 (Batch gradient variance bound). If Assumptions holds and f( S 2. vi [m]. for batch gradient V fi (o Et,) &ob Let, est. bound
eet.
Vfc( itt. have the batch gradient variance
E. [ Silaf, St,11 P
Remark 1. In Lemmal 7 we provide the first upper bound for batched gradient variance under the heavy-tailed noise. In our high-probability analysis, b > 1 provides one parameter of freedom for choosing the clipping parameter X, thereby achieving the convergence rate matching the lower bound in expectation. Specifically, we set = ((mKKT) (((nkTT)s(pp1))) 2n xisp->7), ) which allows us to choose A = O(mKT) 233--23), ), thereby achieving the desired convergence rate.
Inspired by the definitions of of and 0% (0) = [ En: Fs(t))) in the centralized setting, construct three errors in the federated setting: stochastic batch error e,, the clipped batch gradient deviation Ei and the bias ef between the expected clipped batch gradient and full gradient, where of =
mk Ee kk=1 (V fo (x <i,) - V fx ft, (1, & = MK E Ek= E.IV fa ct,) (31), and C & + C.. Based on Lemmal 1 we analyze their upper bounds in Lemma
2
Lemma 2. For Algorithm 2 Vt E [T]. we have ||< || S 2X. Besides, if (x)x) S 2 there is
||c||| 12="x--P and [| =
100=">2-> mkk
Lemma shows that the clipped batch gradient can add parameter of freedom b compared with 35 37 which relaxes the conditions for choosing hyperparameters. Now, we begin to prove the
convergence rate of our FedCBG algorithm. The key to our derivation lies in Lemma 3
T + 1, let E'y be the event that for all = 1, ,N, Lemma 3. For 1 S N <
A + ymk 1-1
(FFs(;;)1 A + mm
[11 + L VFs( 111
2
+ L.IVFS((DDIl VFs(2)) (VF 2 K2
VFs(=:))
(4)
1-1 + +ymK) Σ E
< 2
Then E'y happens with probability at least 1 1ا for each N [T')
Lemma 3 exxlains why our Algorithm 2 can achieve a convergence rate matching the lower bound.
Specifically, in our inductive analysis, we focus on constructing the martingale difference sequences 11 - E [ and {(t, VFs(x)))) and bound them in high probability by Freedman's 's inequality. Besides, by induction hypothesis at / (1 S 1), we also creatively solve a quadratic a inequality w.r.t. (x)]l and [++r)]] so that they can be controlled under the (Lo, Li )-mooothness when is greater than constant. Then, we leverage Lemma 2 and choose appropriate y,, 7, b and À to balance all the terms to achieve the desired convergence rate. Based on Lemma 3 we prove the convergence rate of Algorithm 2
as shown in Theorem 3
Theorem We assume that Assumptions
1
and 3
hold. If we choose b = (((K()) BiDD 27 )₂ A
((MKT) 21 /
21 (mI) 233p-2 ), where R' + 1)H² R¹ Z 41 + 4 A + Lo p maxflog AI 13. A/
/pb ),7 ((mKT))
1j O1
log T
1 2( L Lp Fs Fx( F*, and 3 min{
32Rg 3 3Lg
}. Algorithm 2 can achieve the convergence rate
Lo
8L
7

---

of T Σ [VFs(=))] ((IKTT) 2 log = ))) with the probability at least 8 for any E (0
Table 2: Comparison of the existing analysis in FL. "AA" indicates whether the additional gradient G are required, and refers to the lower bound.
boundedness assumption E, [z Ete [P]]
Assumptions
Bounds
Methods
Criteria
AA
Smooth. Noise
Optimization O((mlT) 5p-2 K
Generalization
47
SS
HT
Exp
47
SS
HT
Exp
v
O((mKT) 33-2
LB
SS
HT
Exp
x
Q(mKTT) Sp
Th.
4
(Lo, L1)
HT
HP
x
O(mMKT) 3p-7 log 1) ( log 1 (
Theorem shows that our FedCBG algorithm can achieve the desired convergence rate for the heavy-tailed noise setting. The size of b is consistent with our intuition that the smaller p is, the more sensitive the algorithm to noise, the gradient differences between different samples may be large,
By thus a small b can achieve ideal convergence rate. This convergence rate ((mKTT) 3p-2 log matches the lower bound proposed in [47] up to a logarithmic factor as shown in Table 2 Thus, FedCBG effectively reduces the number of communication rounds. Besides,
clipping parameter
is smaller than that of [47]. Small is typically used and often leads to good performance [34, 55), as stated in [17). The specific parameter choices and the inequalities they need to satisfy can be found in Appendix C.1. Compared with the state-of of-the-art methods in (4), our analysis has the following advantages. 1) Our analysis is in high probability and provides stronger guarantee for single run. 2) Our analysis use the weaker Assumption
(3] rather than the bounded gradient assumption, i.e. [ [a Ej. ]lP] S GP, 3) Our analysis use the weaker Assumption 2 rather than standard smoothness. Thus, our analysis can apply to a wider range of applications than existing methods.
5.2.1 Challenges and techniques for our analysis
In our analysis, we attempt to extend our Theorem to to the federated setting, but we find it is very difficult even impossible match the lower bound. The reasons are the following: faster convergence rate requires larger step size, but the inductive property requires a smaller step size. Thus, a contradiction arises. We balance the contradiction by addressing the following challenges.
Construct high-probabiility criteria. Starting from the smoothness of the function Fs(r), we use
proposed ssum-aggregation" paradigm and - (a, b) ll a bll2 |///1/ [|6|] handle the tricky inner product term (VF'(xzz), ( - xz). It helps to produce the term am Fs (x; #++1
and construct martingale difference sequences in Lemma 9, which constructs the high--probbbilityy criteria and relaxes the restrictions on parameter selection in the induction.
Difficulty of the analysis in high probability. Many upper bounds in expectation are usually tighter and more concise than those of high probability. For example, there the bound E, 1 10o"x2-> 2-> but only the bound ||0] | < 4 in the centralized setting, where À is usually of the order O(T*), ) a O. similar phenomenon also appears in federated learning, which makes the analysis difficult. Fortunately, we prove that our clipped batch gradient can provide one extra parameter of freedom to handle these rough upper bounds in Lemma
Weaker assumptions. In FL, the difficulties caused by heavy-tailed noise and (Lo, L1) smoothhesss were addressed by induction and our martingale difference sequence, just like in CL.
5.3 Generalization bound for our FedCBG algorithm
In FL, there is work jointly considering the optimization and generalization. To answer Q3, analyze the generalization upper bound for our FedCBG in Theorem 4
Theorem 4. We assume that Assumptions
2 and
3
hold. We choose the same parameter setting
as in Theorem If we choose T ==({{ 27p-6
7p-6
Gp-
and K ((()) 266--1)) then with
3p-2
8

---

probability at least 1 - 6, Algorithm can achieve the generalization bound El= VF(xx)) ((()) + log( ( (3) 207 x07
3p-2
To best of our knowledge, this generalization bound first upper bound for FL with heavy- tailed noise. If we set small global learning rate to obtain better generalization, the convergence speed will be slower, which reflects the trade-off between optimization and generalization.
Experiments
In this section, evaluate FedCBG algorithm against only FL algorithms FAT-clipping- (PR) and FAT-clipping- PI (PI) [47] that can theoretically handle heavy-tailed noise. We also compare the well-known Avd algorithm [T]. We test these methods on the CIFAR- 10, CIFAR-100 [19] and Shakespeare [41] datasets. By the way, our goal is to compare the relative performance of FedCBG and baselines and larger models achieve better performance these datasets. All the experiments were performed on the GeForce RTX 2080Ti platform with the PyTorch framework.
Training an LSTM only satisfying the weaker 2 and 3 Firstly, to verify that the federated scenarios may only meet weaker assumptions (i.e., Assumptions 2 and we evaluate smoothness and gradient noise distribution of stacked LSTM as in (26) training the Shakespeare dataset. We show smoothness and the histograms of gradient noise probability density for two randomly selected clients in Fig. 2 More results shown in the Appendix. It can be that
local smoothness [[ of a constant, which satisfies weaker Assumption 2 Besides, the gradient noise meets heavy-tailed
positively correlates with gradient norm | (aze) instead
||z] 10
distribution, i.e., Assumption rather than light-tailed Gaussian distribution.
0.08
500
0.06
400
0.06
Smoothness
Smoothnass
300
opoch
epoch
0.04
0.04
200
200
0.02
0.02
100
2
4
6
6
Gradient Norm
Gradient Norm
Frequency Distribution Gradient Noise Norms
Frequency Distribution of Gradient Noise Norms
Prequency
Frequency
30
40
2.0
10
1.10
1.15
1.20
1.25
1.30
1.35
1.45
2.5
3.0
4.5
Figure 2: Gradient norm vs estimated Lipschitz smoothness (left) and distributions of the gradient noises (right) during training a stacked LSTM (26 on the Shakespeare dataset.
Hyperparameter selection. conducted ablation experiments on hyperparameters 7, X, b and K as shown in Fig. and Fig. 6 in the Appendix. When global learning rate 0.2 or 0.3 and 3.0, our FedC3G algorithm performs better than other choices. The performance of 100 and K 10 n4/b exceeds that of other values.

---

37.5
35
35.0
Test Accuracy
30
FedCBG GL=0005
je5t Accuracy
32.5
25
FedCBG GL_0011
BedcBG_GL-00
30.0
FedCBG_Coa C-0.2
BedCB6_C=0.5
FedCBG_Gr =0,
27.5
FedCBG_C-11 C-1.0
20
FedCBG GL.0.4
FedCBG FedCBG_C-1.5
FedCBG GL GL-
25.0
PedCBG
15
FedCBG C=2.5
FedCBG_Cs C=3.0
20.0
FedCBG C-4.0
20
40
100
Communication Rounds
Communication Rounds
Test accuracy with different global learning (GL) rate (left) and clipping (C) parameter (right) on the Shakespeare dataset.
Figure 3:
Table 3: Comparison of the training loss (TLoss.), testing classification accuracy (TAce.) and the number of communication rounds (Round) to reach target test accuracy (84.5% for CIFAR-10. 10, 45.0% for CIFAR-100 and 35.5% for Shakespeare datasets) in FL with heavy-tailed noise various datasets.
Datasets
Evaluation
CIFAR-10
CIFAR-100
Shakespeare
TLoss
0.16
3.25
3.17
PR
TAcc. (%) Round
83.1
42.2
34.8
282 (3.1x)
412 (1.9x)
219 (2.2x)
TLoss
0.10
3.16
3.18
PI
TAcc. (%)
84.0
42.8
35.2
Round
189 (2.1x)
346 (1.6x)
178 (1.8x)
TLoss
0.12
3.20
3.52
FedAvg
ТΑсc. (%)
83.8
42.0
32.0
Round
201 (2.3x)
409 (1.9x)
268(2.7
TLoss
0.07
3.00
3.04
FedCBG
TAcc. (%)
85.6
44.2
36.5
Round
89
221
98
Experimental details. Firstly, we choose v = 3.0, = 0.3, nn/b and 100 to train all the methods. Device distributions non-llI. We use 100 randomly selected clients to train the model and the remaining 39 clients to test the model performance, which can quantify the performance gap unseen client distributions, We report the average experimental results of 10 random initializations in Table Secondly, we also conducted an experimental comparison based on the well-chosen hyperparameters and F FedCBG can achieve 1.6-3.1 times gains over the competitors on all the tasks including vision and text models, which verifies the validity of our analysis: FedCBG converges faster and performs better generalization ability than baselines on unseen client distributions.
results shown in the Appendix. Table shows that
7 Conclusions and Future Work
In this paper, we study clipped SGD for heavy-tailed noise. We prove a tighter optimization upper bound and the advanced generalization bound in high probability under weaker conditions. We extend our analysis to the federated setting based on our batch gradient variance bound and propose FedCBG algorithm, which first achieves the high- high-probability convergence rate matching the lower bound and the first high-probability generalization bound. In future work, we will explore the role of recursive momentum g and minimax optimization [27] 28 2 in heavy-tailed scenarios.
10

---

8 Acknowledgements
We want thank the anonymous reviewers for their valuable suggestions and comments. This work was supported by the National Key Research and Development Program of China (No. 2023YFF0906204), National Natural Science Foundation China (No. 02276182), Peng Cheng Lab Program (No. PCL2023A08), and the Ministry of Education, Singapore, under its Academic Research Fund Tier (RG101/24).
References
[1] Ibrahim Alabdulmohsin. An information- route from generalization in expectation to generalization in probability. Artificial intelligence and statistics, pages 92-100. PMLR, 2017.
[2] Weixin An, Yuanyuan Liu, Fanhua Shang. and Hongying Liu. Robust and faster geroth-orde minimax optimization: Complexity and applications. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[3] Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, and Daniel M Roy. Information complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. In ICML, 2024.
[4] Leighton Pate Barns,, Alex Dytso, and Harold Vincent Poor. Improved iiformatioo-theorettee generalization bounds for distributed, federated, and iterative learning. Entropy, 24(9):1178, 2022.
[5] Aurélien Bellet, Marc Tommasi, Kevin Scaman, Giovanni Neglia, et al. Improved stability and generalization guarantees of the decentralized sgd algorithm. In ICML, 2024.
[6] 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-
2022.
[7] Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances Neural Information Processing Systems, 34:4883 34:4883-4895. 2021.
[8] Ashok Cutkosky and Francesco Orabona. Momentua--bssed variance reduction in non-convex SGD. 2019.
[9] Xiaoge Deng, Tao Sun, Shengwei Li, and Dongsheng Li. Stability- based generalization analysis of the asynchronous decentralized sgd. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7340-7348, 2023.
[10] Tao Fan, Hanlin Gu, al. Ten challenging problems in federated foundation models. IEEE Transactions on Knowledge and Data Engineering. 2025.
[11] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference on Learning Theory, pages 89-160. PMLR, 2023.
[12] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware mini- mization for efficiently improving generalization. In ICLR, 2021.
[13] Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. Advances in neural information processing systems, 31, 2018.
[14] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon sgd. In International Conference Machine Learning, pages 3964 3975. PMLR, 2021.
[15] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pages 1225-1234. PMLR, 2016.
11

---

[16] Xiaolin Hu, Shaojie Li, and Yong Liu, Generalization bounds for federated learning: Fast rates, unparticipating clients and unbounded losses. In The Eleventh International Conference on Learning Representations, 2023.
[17] Florian Hübler, llyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. The 28th International Conference on Artificial Intelligence and Statistics.
[18] Florian Hübler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. In International Conference Artificial Intelligence and Statistics, pages 4861-4869 PMLR, 2024.
[19] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[20] Yunwen Lei and Ke Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(1):44505- 4511, 2021.
[21] Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient- dominated objective functions. In International Conference on Learning Representations, 2021.
[22] Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference Machine Learning, pages 6175-6186. PMLR, 2021.
[23] Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non- convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024.
[24) Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In International Conference on Machine Learning, pages 129313 PMLR, 2022.
[25] Shaojie Li and Yong Liu. High probability analysis for non-convex stochastic optimization with clipping. In ECAI 2023, pages 1406-141.. IOS Press, 2023.
[26] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429 2:429-450. 2020.
[27] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concan minimax problems. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th Inter- national Conference on Machine Learning, volume I 119 of Proceedings of Muchine Learning Research, pages 6083-6093. PMLR, 13-18 Jul 2020.
[28] Yuanyuan Liu, Fanhua Shang, Weixin An, Junhao Liu, Hongying Liu, and Zhouchen Lin. A single-loop accelerated extra- -traiegradeen difference algorithm with improved complexity bounds for constrained minimax optimization. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023. URL
maae/fforumt id 1mx 4bHrC
[29] Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. arXiv preprint arXiv:2412.19522 2024.
[30] 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 The Thirty Sixth Annual Conference on Learning Theory, pages 2266-2290. PMLR, 2023.
[31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-effee -efficienn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[32] Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 4666A):2747-2774 2018.
12

---

[33] Lei Meng, Zhuang Qi, Lei Wu, Xiaoyu Du, Zhaochuan Li, Lizhen Cui, and Xiangxu Meng. Improving global generalization and local personalization for federated learning, IEEE Trans- actions on Neural Networks and Learning Systems, 36, 2024.
[34] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. In International Conference Learning Representations, 2018.
[35] 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.
[36] Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What is good metric to study generalization of minimax learners? Advances in Neural Information Processing Systems, 35:38 11:38190-3822 38203, 2022.
[37] Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In International Conference Artificial Intelligence and Statistics, pages 856-864. PMLR, 2024.
[38] Zhuang Qi, Lei Meng. Zitan Chen, Han Hu, Hui Lin, and Xiangxu Meng. Cross-silo proto- typical calibration for federated learning with non-iid data. In Proceedings of the 31st ACM International Conference Multimedia, pages 3099-3100 2023.
[39] Zhuang Qi, Lei Meng, Zhaochuan Li, Han Hu, and Xiangxu Meng. Cross-silo feature space alignment for federated learning clients with imbalanced data. In The 39th Annual AAAI Conference on Artificial Intelligence (AAAI-25), pages 19986-19944 2025.
[40] Chao Ren, Han Yu, et al. Advances and open challenges in federated foundation models. IEEE Communications Surveys and Tutorials, 2025.
[41] William Shakespeare. The complete works of William Shakespeare. Wordsworth Editions, 2007.
[42] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning. pages 5827-5837. PMLR, 2019.
[43] Zhenyu Sun, Xiaochun Niu, and Ermin Wei. Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and Statistics, pages 676-684. PMLR, 2024.
[44] Youming Tao, Sijia Cui, Wenlu Xu, Haofei Yin, Dongxiao Yu, Weifa Liang, and Xiuzhen Cheng. Byzantine-resilient federated learning at edge. IEEE Transactions on Computers, 72(9): 2600-2614 2023.
[45] Chenhao Wang, Zihan Chen, Nikolaos Pappas, Howard H. Yang, Tony Q. S. Quek, and H. Vincent Poor. Adaptive federated learning over the air. IEEE Transactions on Signal Processing. 73:3187-3202, 2025.
[46] Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 16049-16057, 2024.
[47] Haibo Yang. Peiwen Qiu, and Jia Liu. Taming fat-tailed ("heavier-tailed' with potentially infinite variance) noise in federated learning. Advances in Neural Information Processing Systems, 35:17017-17029, 2022.
[48] Qiang Yang, Lixin Fan, and Han Yu. Federated Learning: Privacy and Incentive. Springer, Cham, 2020.
[49] Honglin Yuan, Warren Richard Morningstar, Lin Ning, and Karan Singhal. What do we mean by generalization in federated learning? In International Conference on Learning Representations, 2022. URL htttttt:/ net dame///rrrmriiddddo-ed-
13

---

[50] Dun Zeng, Zheshun Wu. Shiyu Liu, Yu Pan, Xiaoying Tang, and Zenglin Xu. Understanding generalization of federated learning: the trade-off between model stability and optimization. arXiv preprini arXiv:241 I. 16303, 2024.
[51] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511-
15521, 2020.
[52] Hao Zhang, Chenglin Li, Nuowen Kan, Ziyang Zheng, Wenrui Dai, Junni Zou, and Hongkai Xiong. Improving generalization in federated learning with model-data mutual information regularization: A posterior inference approach. In NeurIPS, 2024.
[53] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.
[54] Jingzhao Zhang, Sai Praneeth 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, 33:15383-15393, 2020.
[55] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068 2022.
[56] Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. In ICML, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. Please see the sections Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
The paper discuss the limitations of the work. Please see Section Conclusions and Future Work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: The paper provides the full set of assumptions and complete (and correct) proof in Sections 3, 4 and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please see Section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Please see the section Experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
pub gui / ss oooooooolleooo cy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht
/Coee Submi s issionn iisPoliccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://www....aae.e....aaaaaaaaa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is of a theoretical nature. The main contribution is weaken the conditions. There are no positive and negative societal impacts from this work, and as result we did discuss
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used public datasets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We propose a new analytical method.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ht /ttp:///eerpppp/pee /tt.errrppp.ccc/ooeeeeeee//////e 2025/ LLM) for what should or should not be described.
21


Reviews:
[{"review_id": "aBWEGWrgS7", "reviewer": "Reviewer_iqqA", "summary": "This paper presents a comprehensive high-probability analysis of clipped stochastic gradient methods under weaker assumptions: (L_0, L_1)-smoothness and heavy-tailed gradient noise. The authors claim that they prove tighter high-probability convergence rates than existing work. Moreover, they design FedCBG, and establish its optimization and generalization bounds in high probability, a first in the FL literature under such weak assumptions. Experiments on CIFAR and Shakespeare datasets empirically validate both convergence and generalization improvements over baselines.", "questions": "1. The main theoretical results of this work rely heavily on [29], which even considers momentum. However, the distinctions between this work and [29] are not sufficiently discussed in the main text. To improve the clarity and originality of the contribution, it is recommended that the authors: (1) Provide a detailed comparison between the theoretical results of this work and those in [1], including both the differences and the respective advantages and limitations; (2) Clearly explain the specific challenges involved in extending or adapting the theoretical framework of [1] to the current setting; (3) Explicitly identify which theoretical results in this paper are novel contributions and which are direct extensions or applications of existing results from [1].\n\n[1]\tLiu Z, Zhang J, Zhou Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 2266-2290.\n\n2. It is recommended that the authors carefully review recent advances in related work. For instance, in lines 39-40, the author claims that \"only one work focuses on the heavy-tail noise problem in federated learning\", but in fact, there are other works that also focus on this. For example, the work of Tao et al. [2] focuses on Byzantine-resilient federated learning in the presence of heavy-tail noise. This suggests that the related work section may not be sufficiently comprehensive and should be revised to reflect the current state of research more accurately.\n\n[2] Tao Y, Cui S, Xu W, et al. Byzantine-resilient federated learning at edge[J]. IEEE Transactions on Computers, 2023, 72(9): 2600-2614.\n\n3. This paper omits some important details and contains notational and typographical issues that may affect readability. For example, key symbols such as $\\Delta_t$ are used in the main theorems without formal definitions. Additionally, there are problems with notational rigor, bracket mismatches, and unclear references to mathematical inequalities. It is recommended that the authors complete missing definitions, standardize the notation, and thoroughly proofread the manuscript to improve clarity, precision, and overall rigor.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper makes solid theoretical advances in stochastic optimization under realistic conditions. Rigorous theoretical development with carefully designed proofs removing strong assumptions (e.g., bounded gradients), supported by martingale and inductive analyses.\n2. Despite the complex technical content, the structure is well-organized, and the derivations and algorithm descriptions are clear.\n\nWeaknesses:\n1. This paper omits some key details, leading to potential ambiguity. For example, the definition of $\\Delta_t$ is not formally given, but the main theoretical results, such as Theorem 1, rely on it. Therefore, it is recommended that the authors complete the key notation description that may be omitted.\n2. This paper has typos or inappropriate descriptions. For example, in line 158, please confirm whether the bound is obtained based on the Jensen's inequality or should be the Cauchy-Schwarz inequality. In line 8 of Algorithm 2, $\\tilde{\\Delta}_t$ should have a subscript about $i$. There is a bracket error in the value of T in Theorem 4 on line 294. And so on.\n3. The main theoretical results of this work rely heavily on [29] which even considers momentum optimization, but the difference between the two is not fully discussed in the main text. It is recommended that (1) the differences and advantages and disadvantages of the two theoretical results be compared in detail; (2) the difficulties in deriving the theoretical results based on [1] be explained, and specifically which results are innovative and which follow existing work.\n\n[1]Liu Z, Zhang J, Zhou Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 2266-2290.", "was_revised": true, "final_justification": "My concerns have almost been addressed, and I raise my score accordingly.", "rebuttal": "### **Detailed comparison with work [29]**\n\n#### **1. New challenges for adapting the theoretical framework of [29] to the $(L_0, L_1)$-smoothness**\n\n$(L_0, L_1)$-smoothness leads to the following challenges: Firstly, obtaining an upper bound on the gradient $\\|\\nabla F_S(x_t)\\|$ is difficult because it is hidden in an inequality. Secondly, we need to construct a new martingale difference sequence to handle the term $L_1\\|\\nabla F_S(x)\\|$ in $(L_0, L_1)$-smoothness. These two factors also complicate the selection of hyper-parameters such as the clipping parameter $\\lambda$ and step size $\\eta$.\n\n#### **2. Novel contributions and direct extensions from [29]** \n\n$\\bullet$ **Novel contributions.** By induction, we deduce that the gradient $\\|\\nabla F_S(x_t)\\|$ needs to satisfy the quadratic inequality, $\\|\\nabla F_S(x_t)\\| \\leq \\sqrt{4(L_0 + L_1\\|\\nabla F_S(x_t)\\|)\\Delta_1}$, so that the gradient $\\|\\nabla F_S(x_t)\\|$ can be controlled when $\\lambda$ is greater than a constant. In addition, we construct a new martingale difference sequence, $\\sum_{t=0}^{l-1}(2\\eta - L_0\\eta^2 - L_1\\eta^2\\|\\nabla F_S(x_t)\\|)\\langle X_t, \\theta_t^a\\rangle$, where $X_t = \\left\\\\{\\begin{matrix}-\\nabla F_S(x) & \\text{if } \\Delta_t \\leq 2\\Delta_1 \\newline 0 &\\text{otherwise} \\end{matrix}\\right.$, and bound it by the Freedman’s inequality. Finally, by solving the inequality about the clipping parameter $\\lambda$, we obtain a better parameter setting about step size $\\eta$, thereby achieving a better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^\\frac{2p-2}{2p-1}\\frac{T}{\\delta})$, compared with $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^2\\frac{T}{\\delta})$ in work [29].\n\n$\\bullet$ **Direct extensions from [29].** Eq. (15) is a direct extension from [29]. Eq. (15) is a basic tool for handling heavy-tail noise. Many works [1, 2, 3] also depend on such results. Although our analysis depends on Eq. (15), there are many differences compared with [29]. The comprehensive comparisons are provided as following.\n\n[1] Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS.\n\n[2] Li. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023.\n\n[3] Cutkosky. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.\n\n#### **3. Comparisons of theoretical results between our paper and [29].**\n\n(1) Different technologies. Under standard smoothness, [29] uses induction and constructs a martingale difference sequence \n\n$$U_s^t = \\left\\\\{\\begin{matrix} 0 & s = 0\\newline \\text{sgn} \\left(\\sum_{i=1}^{s-1} U_i^t\\right) \\frac{\\langle \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a, \\beta^{t-s}\\theta_s^a\\rangle}{\\|\\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a\\|} & s\\neq 0 \\text{ and } \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a \\neq 0\\newline 0 & s\\neq 0 \\text{ and }  \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a = 0\\end{matrix}\\right.$$\n\nto handle the heavy-tailed noise, where $s \\in \\{0\\} \\cup [t]$ and $\\beta = 1 - T^{-\\frac{p}{3p-2}}$, while we construct a new martingale difference sequence $\\sum_{t=0}^{l-1}(2\\eta - L_0\\eta^2 - L_1\\eta^2\\|\\nabla F_S(x_t)\\|)\\langle X_t, \\theta_t^a\\rangle$, and solve a quadratic inequality about gradient $\\|\\nabla F_S(x_t )\\|$ to handle the heavy-tailed noise.\n\n(2) Different intermediate results. As we propose new technologies mentioned above to deal with $(L_0, L_1)$-smoothness, our inductive Lemma 6 is very different from Lemma 8 in [29], which plays a key role in proving convergence rate. Specifically, due to different martingale difference sequences, each term in our Lemma 6 needs to be rebounded rather than simply extending the results in Lemma 8 in [29].\n\n(3) Respective advantages for convergence rates. Our goal is to achieve faster convergence rates under weaker assumptions. Our analysis achieves better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^{\\frac{2p-2}{2p-1}}\\frac{T}{\\delta})$ under the weaker $(L_0, L_1)$-smoothness as shown in Table 1. But [29] did not discuss this weaker assumption. On the contrary, under the stronger smoothness assumption, i.e., smoothness of individual stochastic function $f(x;\\xi)$, [29] achieves a convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{2p-1}}\\log^2\\frac{T}{\\delta})$, which breaks the lower bound. But we did not discuss this stronger assumption.\n\n(4) Generalization. We prove the generalization bound but the work [29] did not discuss this issue. To the best of our knowledge, our paper is the first work that provides the generalization bound under the heavy-tailed noise and $(L_0, L_1)$-smooth setting.\n\n(5) Federated setting. We propose the novel FedCBG algorithm for heavy-tailed federated setting. More importantly, we propose novel error estimations as shown in Lemmas 1 and 2 to obtain the nearly optimal convergence rate and the first generalization bound. But [29] did not consider the federated case. \n\nTo address your concerns, we will add a detailed discussion in our revised version.\n\n### **About related works.**\n\nThanks for your comments about related work. To address your concerns, we will add the following descriptions. \n\nAs for federated learning, heavy-tailed noise also exists. The works [4, 5, 6] focus on this issue. [4] proposed a Adaptive Over-the-air Federated Learning (ADOTA-FL) algorithm for over-the-air model training. But it require both bounded gradient and bounded $p$-th moment for stochastic noise, which are stronger than our assumptions. [5] studied Byzantine resilience, communication efficiency and the optimal statistical error rates for edge federated learning under the heavy-tailed noise setting. For the non-convex analysis, in addition to requiring the boundedness of the gradient, it also requires the smoothness and second-order information of the stochastic gradient. The most related work to our paper is [6]. \n\n[4] Wang C, Chen Z, Pappas N, et al. Adaptive federated learning over the air[J]. IEEE Transactions on Signal Processing, 2025.\n\n[5] Tao Y, Cui S, Xu W, et al. Byzantine-resilient federated learning at edge[J]. IEEE Transactions on Computers, 2023, 72(9): 2600-2614.\n\n[6] Yang H, Qiu P, Liu J. Taming fat-tailed (“heavier-tailed” with potentially infinite variance) noise in federated learning[J]. Advances in Neural Information Processing Systems, 2022, 35: 17017-17029.\n\n### **For readability and some typos** \n\n$\\bullet$  $\\Delta_t = F_S(x_t) - F^*$. Thank you for pointing out the typos, we will revise them in our final paper.\n\n$\\bullet$ We confirm that the bound in line 158 can be obtained by the Jensen's inequality or the Cauchy-Schwarz inequality. For the Jensen's inequality, $f\\left(\\frac{\\sum_{t=1}^T a_t}{T}\\right) \\leq \\frac{\\sum_{t=1}^T f(a_t)}{T}$, we let $f(a) = a^2$ and $a_t = \\|\\nabla F_S(x_t)\\|$, thus $\\frac{1}{T}\\sum_{t=1}^T\\|\\nabla F_S(x_t)\\| = ((\\frac{1}{T}\\sum_{t=1}^T\\|\\nabla F_S(x_t)\\|)^2)^{1/2} \\leq (\\frac{1}{T}\\sum_{t=1}^T\\|\\nabla F_S(x_t)\\|^2)^{1/2} \\leq \\mathcal{O}(\\log^{\\frac{p-1}{2p-1}}\\frac{T}{\\delta}/ T^{\\frac{p-1}{3p-2}})$. For the Cauchy-Schwarz inequality, $\\left(\\sum_{t=1}^T a_t b_t\\right)^2 \\leq \\left(\\sum_{t=1}^T a_t^2\\right)\\left(\\sum_{t=1}^T b_t^2\\right)$, we let $a_t = \\frac{1}{T}$ and $b_t = \\|\\nabla F_S(x_t)\\|$ and can obtain the same result. Thus, both Jensen's inequality and Cauchy-Schwarz inequality can derive the result.\n\n$\\bullet$ $\\widetilde{\\Delta}_t$ should be $\\widetilde{\\Delta}_t^i$. We modify the bracket error in line 294. Thank you very much for your detailed review.\n\nIn summary, we will complete missing definitions, standardize the notation, and thoroughly proofread the manuscript in our revised version."}, {"review_id": "SEtBNROBNz", "reviewer": "Reviewer_AasK", "summary": "This paper analyzes the Clipped SGD method under more relaxed assumptions of $(L_0,L_1)$-smoothness and heavy-tailed noise for nonconvex functions. Current literature tackles only one of the cases but two simultaneously. The authors extend the results to a Federated setting, providing the FedCBG method with similar convergence guarantees. On top of the convergence results, the authors provide generalization bounds for the Clipped SGD and FedCBG methods. Importantly, the convergence results are optimal in the number of iterations $T$.", "questions": "- I suggest moving assumptions 2 and 3 to the introduction, as they are used a lot before formally providing them. This would improve the clarity of the presentation.\n\n- There is a concurrent work [Chezhegov, Savelii, et al. \"Convergence of Clipped-SGD for Convex $(L_0, L_1) $-Smooth Optimization with Heavy-Tailed Noise.\" arXiv preprint arXiv:2505.20817 (2025)]. They consider the same setting assumptions but in the convex regime. It would be worth mentioning the paper and comparing the results, though it is not necessary. Interestingly, they obtain the optimal rate only after $\\mathcal{O}(1/\\delta)$ iterations. There is no such restriction in this work. Can the authors provide an intuition why it is so if possible?\n\n- There is no gradient-similarity-type assumption in the theory of the FedCBG method, while vanilla FedAvg's rate does depend on such a quantity. How is it avoided here? Is it hidden somewhere?\n\n- Is the power of $\\log$ terms in the rates optimal, or can they be improved further?\n\n- What is the difference between tables 1 and 4?\n\n- How is the power of $\\log$ terms improved? Does it only come from a more careful choice of the hyperparameters, like stepsize?\n\n- How are problem parameters like $L_0, L_1, \\Delta_1$ present in the rates? Can the authors provide explicit rates? Right now, I suspect that the rates are worse than what I expect in the nonconvex regime (see, e.g., [Hübler et al. \"Parameter-agnostic optimization under relaxed smoothness.\" AISTATS, 2024].\n\n- What is the value of $p$ in the experiments? Can the authors estimate it to ensure that the noise is indeed heavy-tailed with $p\\in(1,2]$?\n\n- Table 3 contains the results on CIFAR10, which is not heavy-tailed as far as I know. Therefore, the caption of Table 3 should be clarified.\n\n- What algorithm is used to obtain Figure 2? \n\n- What does \"recursive momentum\" mean?\n\n- What is the difference between the settings of the two left and two right plots in Figure 2?", "limitations": "The authors provided some discussion in section 7, though it is very limited. In particular, it is not clear what \"recursive momentum\" means and which part of the complexity results they aim to reduce. I suggest also including \n\n- Generalization to symmetric $(L_0, L_1)$-smoothness.\n\n- Dependency on the problem parameters $L_0,L_1$.\n\nin the limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "***Strengths:***\n\n- Strong theoretical guarantees for the Clipped SGD algorithm with an optimal dependency on the number of iterations $T$, only with a logarithmic factor depending on the failure probability $\\delta$.\n\n- I went through the proofs, and they look correct to me. The idea is to inductively bound the martingale differences.\n\n- The analysis does not depend on the gradient bound, which is an improvement over some earlier works. \n\n- Extension to the federated setting and an algorithm FedCBG, which also converges under relaxed smoothness and heavy-tailed noise with a competitive performance in practice.\n\n***Weaknesses:***\n\n- The results seem to be suboptimal in $L_0$ and $L_1$. It looks like we would get the same rates when using SGD with a fixed stepsize. In other words, there is no advantage to using the Clipped SGD.\n\n- The related works section can be improved further. Several important works that also study heavy-tailed noise assumption are not discussed, e.g., [Sadiev et al. \"High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance.\" ICML, 2023.], [Gorbunov et al. \"High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise.\" ICML 2024], one of them studies the federated setting as well. \n\n- The current theoretical results in the main paper are hard to parse. The dependency on other problem parameters, e.g., $L_0, L_1$ is missing. Several quantities that are used in the theorems, e.g., $\\Delta_1$ are not defined, or it is not clear how they affect the rate, e.g., $R$ or $\\mathcal{R}$. Similar claims are applied to the results presented in the table, to the proof sketches (what are the constants $A_{1,2,3}$ ?), and to the rate of FedCBG.\n\n- The convergence is given for a local version of $(L_0, L_1)$-smoothness, i.e. the smoothness holds when $\\|x-y\\|\\le 1/L_1$ (assymetric $(L_0,L_1)$-smoothness). It would be interesting to see the convergence results when a more general class of symmetric $(L_0,L_1)$-smooth functions is considered, i.e., for all $x,y\\in\\mathbb{R}^d$ we have $\\\\|\\nabla f(x)-\\nabla f(y)\\\\| \\le (L_0+L\\_1\\max\\_{u\\in[x,y]}\\\\|\\nabla f(u)\\\\|)\\cdot \\\\|x-y\\\\|$.", "was_revised": true, "final_justification": "The authors provided clarifications and addressed all my concerns by providing very detailed answers. I believe that this work is a significant contribution to the field of optimization, in particular, the convergence of gradient-based algorithms with heavy-tailed noise. The authors tackle a challenging case of non-convex $(L_0,L_1)$-smooth functions. The obtained results are optimal w.r.t. several quantities in the rate, demonstrating the tightness of the analysis. Therefore, I increase my score to 5, and support acceptance of this work.", "rebuttal": "#### **About weaknesses**\n\n$\\bullet$ Under the bounded variance assumption, SGD can achieve convergence rate $\\mathcal{O}(T^{-1/4})$, which is consistent with our results when $p = 2$. However, under the heavy-tailed noise assumption, clipped SGD performs better than SGD. Clipped SGD converges under heavy-tailed noise, while standard SGD may diverge [1].\n\n$\\bullet$ Thanks for your comments. The work [2] proposed a high-probability analysis for clipped SGD and achieved the convergence rate of $\\mathcal{O}(T^{\\frac{1-\\alpha}{\\alpha}})$. Although it eliminates the bounded gradient assumption, its convergence rate is worse than advanced one in [3]. The work [4] considers the distributed setting but under the convexity assumption, which limits its scope of application. To address your concerns, we will discuss the two works in our revised version.\n\n$\\bullet$ Thanks for your comments. $\\Delta_t = F_S(x_t) - F^*$ and $R$ and $\\mathcal{R}$ are constants. They do not affect the convergence rate results.  $A_1$ $A_2$ $A_3$ are defined in Eq. (88). For readability and space limitations, we put some detailed parameter dependencies in the Appendix. For example, $\\lambda = \\max\\{\\big(\\frac{64}{\\mathcal{R}\\rho}\\big)^{\\frac{1}{2p-1}}\\sigma^{\\frac{2p}{2p-1}}T^{\\frac{1}{3p-2}}, \\frac{(2\\Delta_1)^{\\frac{1}{p}}\\sigma T^{\\frac{1}{3p-2}}}{(\\mathcal{R}\\rho^2)^{\\frac{1}{p}}}, 40^{\\frac{1}{p}}{T^{\\frac{1}{3p-2}}}\\rho^{-\\frac{2}{p}}\\sigma (1+\\frac{L_1\\Delta_1}{32\\mathcal{R}})^\\frac{2}{p}, 4R\\}$ as shown in Eq. (31) in Line 603, where $\\mathcal{R} = L_0 + 2(L_1 + 1)R$, $R = \\frac{1}{2}(L_0 + (4L_1+1)\\Delta_1)$ and $\\rho = \\max\\{\\log\\frac{4T}{\\delta}, 1\\}$. To address your concerns, we will add them to our main paper.\n\n$\\bullet$ Thanks for your comments. We will consider to study the convergence properties and generalization bounds under symmetric $(L_0, L_1)$-smoothness assumption in future work.\n\n[1] Marshall N, Xiao K L, Agarwala A, et al. To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions[C]//The Thirteenth International Conference on Learning Representations.\n\n[2] Sadiev A, Danilova M, Gorbunov E, et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance[C]//International Conference on Machine Learning. PMLR, 2023: 29563-29648.\n\n[3] Liu Z, Zhang J, Zhou Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise[C]//The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023: 2266-2290.\n\n[4] Gorbunov E, Sadiev A, Danilova M, et al. High-probability convergence for composite and distributed stochastic minimization and variational inequalities with heavy-tailed noise[J]. arXiv preprint arXiv:2310.01860, 2023.\n\n#### **About Questions**\n\n$\\bullet$ Thanks for your comments. We will reposition Assumptions 2 and 3 in our revised version.\n\n$\\bullet$ Extending the results in the convex case to the non-convex case remains a significant challenge. Although the convex case can achieve the optimality, the non-convex problem is very difficult due to the existence of multiple local optimal points. The convergence rate we have proved is state-of-the-art so far and whether it can be achieved optimally is still an open question.\n\n$\\bullet$ This is due to the novelty of our proof technique. We decompose the quadratic term into errors $\\epsilon_t^a$ and $\\epsilon_t^b$ in the inductive Lemma 3. Then, we construct new martingale difference sequences and use the Freedman’s inequality, which removes the gradient-similarity-type assumption. \n\n$\\bullet$ There is no lower bound for high-probability analysis, it is unknown whether the power of $\\log$ terms can be improved.\n\n$\\bullet$ Table 4 is more detailed. Table 4 contains more related work and compares several results based on the criteria in expectation. Due to space limitations, we put the main compared methods in the main paper.\n\n$\\bullet$ The improvement come from our new martingale difference sequences and a more careful choice of hyper-parameters. We construct a new martingale difference sequence, $\\sum_{t=0}^{l-1}(2\\eta - L_0\\eta^2 - L_1\\eta^2\\|\\nabla F_S(x_t)\\|)\\langle X_t, \\theta_t^a\\rangle$, where $X_t = \\left\\\\{\\begin{matrix}-\\nabla F_S(x) & \\text{if } \\Delta_t \\leq 2\\Delta_1 \\newline 0 &\\text{otherwise} \\end{matrix}\\right.$. The new sequence requires us to solve new inequalities about the clipping parameter $\\lambda$. Then, we can obtain a better parameter setting about step size $\\eta$, thereby achieving a better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^\\frac{2p-2}{2p-1}\\frac{T}{\\delta})$.\n\n$\\bullet$ Under the bounded variance assumption, the work [5] can achieve convergence rate $\\mathcal{O}(T^{-1/4})$, which is consistent with our results when $p = 2$. The work [5] needs the bounded variance assumption but our results are based on heavy-tailed noise assumption. The explicit rate for CL is $\\mathcal{O}(\\max\\\\{\\frac{\\sigma^{\\frac{2p}{2p-1}}{\\mathcal{R}}^{p}}{T^{\\frac{2-2p}{3p-2}}}, \\frac{\\sigma(2\\Delta_1)^{\\frac{1}{p}}}{\\mathcal{R}^{\\frac{1}{p}}T^{\\frac{2p-2}{3p-2}}}, \\frac{\\sigma(1+\\frac{L_1\\Delta_1}{\\mathcal{R}})^\\frac{2}{p}}{T^\\frac{2p-2}{3p-2}}\\\\}\\log^{\\frac{2p-2}{2p-1}}\\frac{T}{\\delta})$. Similarly, we can also get the results under FL. To address your concerns, we will move them in our revised version.   \n\n$\\bullet$ The heavy-tailed phenomenon can be verified by the two right plots on the right side of Figure 2. To address your concerns, we will estimate the value of $p$ in our revised version.\n\n$\\bullet$ In the federated learning, CIFAR-10 occasionally performs heavy-tailed phenomenon. Similar experiments can be found in [6]. To address your concerns, we will delete \"heavy-tailed noise\" in the caption of Table 3.\n\n$\\bullet$ We use the FedAvg algorithm to obtain Figure 2.\n\n$\\bullet$ \"recursive momentum\" was proposed by the work [7], which is a technique that can achieve variance reduction using only a single stochastic sample.\n\n$\\bullet$ There is no difference between the settings of the two left and two right plots in Figure 2.\n\n[5] Hübler et al. \"Parameter-agnostic optimization under relaxed smoothness.\" AISTATS, 2024\n\n[6] Yang H, Qiu P, Liu J. Taming fat-tailed (“heavier-tailed” with potentially infinite variance) noise in federated learning[J]. Advances in Neural Information Processing Systems, 2022, 35: 17017-17029.\n\n[7] Cutkosky A, Orabona F. Momentum-based variance reduction in non-convex sgd[J]. Advances in neural information processing systems, 2019, 32."}, {"review_id": "x8Qa6yDdS6", "reviewer": "Reviewer_6QjF", "summary": "This paper provides the convergence bounds and the generalization error bounds for clipped-SGD, considering the $(L_0,L_1)$-smoothness and the heavy-tailed noise assumption. The authors also extend the clipped-SGD to federated learning and provide both the convergence bounds and the experimental results to illustrate the effectiveness.", "questions": "Is it possible to obtain a convergence bound with $\\log(T/\\delta)$ order, as the one in [1]? Or is it possible to drop the logarithm factor and match the lower bound?\n\n[1] Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883–4895, 2021.", "limitations": "No", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\na. The theoretical results are new and interesting, which are beneficial for the optimization community. There are no convergence bounds and generalization error bounds for the $(L_0,L_1)$-smoothness and the heavy-tailed noise assumption. Also, the improvement of logarithm order in the convergence bound is interesting.\n\nb. The proof looks sound. Although the proof borrows some techniques from the convergence analysis of heavy-tailed noise and $(L_0,L_1)$-smoothness, it's OK. Also, there are some new proof techniques.\n\nc. It's also interesting to study the federated learning scenario, which is rarely considered in the classical optimization field.\n\n**Weaknesses**:\n\na. Although the results are new, the contribution is a bit incremental. It's well known that the convergence results for clipped-SGD have been derived under standard $L$-smoothness and the heavy-tailed noise assumption. When relaxing to $(L_0,L_1)$-smoothness, the additional gradient inside the smooth parameter can be cancelled by a proper selection of the step-size. One of the central proof techniques still relies on the classical results for the heavy-tailed noise, such as the result in [29] to bound the two types of noise variance, as indicated in Eq. (15) on Page 16. \n\nb. If there are some new estimation techniques due to the $(L_0,L_1)$-smoothness, it would be better to elaborate more in the proof sketch. The proof sketch lacks details.\n\nc. The results for FL seem not very novel in comparison with the ones for CL. I will regard the theoretical results for CL as the major contribution in this paper, while the ones for FL as extension results. If there are some essential differences in the results or the proof techniques, it may be better to present them clearly. Otherwise, the part for FL can be compressed or moved to the appendix while adding more proof details for the results of CL in the main body of the paper.\n\nd. Although there is an improvement on the logarithm order in the convergence bound, the improvement can be considered a bit weak since the dominated order is the polynomial dependency on $T$ instead of the logarithm order.", "was_revised": true, "final_justification": "This paper provides novel convergence results for clipped SGD under $(L_0,L_1)$-smoothness and the heavy-tailed noise. I think it's a borderline paper. The strength is that the result is new. The weakness comes from that the main proof techniques still rely on the existing proof techniques of clipped SGD under heavy-tailed noise (usually on $L$-smoothness). Also, there are some minor issues regarding the presentation, including a lack of detailed proof sketches and a detailed comparison to existing works.\n\nOverall, I think it's a borderline paper.", "rebuttal": "### **Our analysis is non-trivial.**\n\n$\\bullet$ **Based on the bounded gradient assumption and the criterion in expectation, it is trivial to extend to $(L_0, L_1)$-smoothness by choosing the step size.** There are works [4, 5] to extend the standard smoothness to the $(L_0, L_1)$-smoothness in the heavy-tailed noise. They are all based on criterion in expectation and even rely on bounded stochastic gradients. The criterion in expectation helps to tighten the upper bound of the error. For example, there is $\\mathbb{E}_t\\|\\theta_t^a\\|^2 \\leq 10\\sigma^p\\lambda^{2-p}$ but only $\\|\\theta_t^a\\|^2 \\leq 4\\lambda^2$ without expectation operation, where $\\lambda = \\mathcal{O}(T^{\\frac{1}{3p-2}})$. The bounded stochastic gradient can be used to handle unbounded variance by decomposing it into $p$-th moment and gradient norm. However, **based on the high-probability analysis, it is non-trivial to extend the standard smoothness to the $(L_0, L_1)$-smoothness.**  On the one hand, some error terms in high-probability criterion are larger than those in expectation criterion. For example, there is $\\mathbb{E}_t\\|\\theta_t^a\\|^2 \\leq 10\\sigma^p\\lambda^{2-p}$ in expectation but only $\\|\\theta_t^a\\|^2 \\leq 4\\lambda^2$ in high-probability. On the other hand, we remove the bounded gradient assumption. Thus, it is difficult to handle $(L_0, L_1)$-smoothness only by choosing step sizes. Nevertheless, we provide an improved high-probability analysis only under $(L_0, L_1)$-smoothness and heavy-tailed noise assumptions.\n\n$\\bullet$ Eq. (15) is a basic tool for handling heavy-tail noise. Many works [1, 2, 3] also depend on such results. Although our analysis depends on Eq. (15), there are many differences compared with [29]. \n\n**New challenges**\n\n$(L_0, L_1)$-smoothness leads to the following challenges: Firstly, obtaining an upper bound on the gradient $\\|\\nabla F_S(x_t)\\|$ is difficult because it is hidden in an inequality. Secondly, we need to construct a new martingale difference sequence to handle the term $L_1\\|\\nabla F_S(x)\\|$ in $(L_0, L_1)$-smoothness. The two factors complicate choosing hyper-parameters $\\lambda$ and $\\eta$.\n\n**Novel contributions**\n\nBy induction, we deduce that the gradient $\\|\\nabla F_S(x_t)\\|$ needs to satisfy the quadratic inequality,  $\\|\\nabla F_S(x_t)\\| \\leq \\sqrt{4(L_0 + L_1\\|\\nabla F_S(x_t)\\|)\\Delta_1}$, so that the gradient $\\|\\nabla F_S(x_t)\\|$ can be controlled under the $(L_0, L_1)$-smoothness when $\\lambda$ is greater than a constant. In addition, we construct a new martingale difference sequence, $\\sum_{t=0}^{l-1}(2\\eta - L_0\\eta^2 - L_1\\eta^2\\|\\nabla F_S(x_t)\\|)\\langle X_t, \\theta_t^a\\rangle$, where $X_t = \\left\\\\{\\begin{matrix}-\\nabla F_S(x) & \\text{if } \\Delta_t \\leq 2\\Delta_1 \\newline 0 &\\text{otherwise} \\end{matrix}\\right.$, and bound it by the Freedman’s inequality. Finally, by solving the inequality w.r.t. the clipping parameter $\\lambda$, we obtain a better parameter setting for step size $\\eta$, thereby achieving a better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^\\frac{2p-2}{2p-1}\\frac{T}{\\delta})$, compared with$\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^2\\frac{T}{\\delta})$ in work [29].\n\n**Detailed comparisons between our paper and [29].**\n\n(1) Different technologies. Under standard smoothness, [29] uses induction and construct a martingale difference sequence \n\n$$U_s^t = \\left\\\\{\\begin{matrix} 0 & s = 0\\newline \\text{sgn} \\left(\\sum_{i=1}^{s-1} U_i^t\\right) \\frac{\\langle \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a, \\beta^{t-s}\\theta_s^a\\rangle}{\\|\\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a\\|} & s\\neq 0 \\text{ and } \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a \\neq 0\\newline 0 & s\\neq 0 \\text{ and }  \\sum_{i=1}^{s-1}\\beta^{t-i}\\theta_i^a = 0\\end{matrix}\\right.$$\n\nto bound errors, where $s \\in \\{0\\} \\cup [t]$ and $\\beta = 1 - T^{-\\frac{p}{3p-2}}$, while we construct a new martingale difference sequence $\\sum_{t=0}^{l-1}(2\\eta - L_0\\eta^2 - L_1\\eta^2\\|\\nabla F_S(x_t)\\|)\\langle X_t, \\theta_t^a\\rangle$ and solve a quadratic inequality about gradient $\\|\\nabla F_S(x_t )\\|$ to bound errors.\n\n(2) Different intermediate results. As we propose new technologies above to deal with $(L_0, L_1)$-smoothness, our inductive Lemma 6 is very different from Lemma 8 in [29], which plays a key role in proving convergence rate. Due to different martingale difference sequences, each term in our Lemma 6 needs to be rebounded rather than simply extending the results in Lemma 8 in [29].\n\n(3) Better convergence rates under weaker assumptions. [29] achieves the convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^2\\frac{T}{\\delta})$ but depends on standard smoothness of $F_S(x)$. Our analysis is based on the general $(L_0, L_1)$-smoothness and achieves better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^{\\frac{2p-2}{2p-1}}\\frac{T}{\\delta})$ as shown in Table 1. \n\n(4) Generalization. We prove the generalization bounds for CL and FL but the work [29] did not discuss this issue. To the best of our knowledge, our paper is the first work that provides the generalization bound under the heavy-tailed noise and $(L_0, L_1)$-smooth setting.\n\n(5) Federated case. We propose the novel FedCBG algorithm for heavy-tailed federated setting. More importantly, we propose novel error estimations as shown in Lemmas 1 and 2 to obtain the nearly optimal convergence rate. Thus, it is non-trivial to extend our technology to the federated setting. But [29] did not consider the federated case. \n\n[1] Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS.\n\n[2] Li. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023.\n\n[3] Cutkosky. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.\n\n[4] Liu. Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping. ICLR.\n\n[5] Zhang. Why are adaptive methods good for attention models? NeurIPS, 2020.\n\n### **Estimation techniques for $(L_0, L_1)$-smoothness.**\n\n**Challenges**\n\n$(L_0, L_1)$-smoothness leads to the following challenges: \n\n1. Obtaining an upper bound on the gradient $\\|\\nabla F_S(x_t)\\|$ is difficult because it is hidden in an inequality. \n2. We need to construct a new martingale difference sequence to handle the term $L_1\\|\\nabla F_S(x)\\|$ in $(L_0, L_1)$-smoothness. \n\nThese two factors complicate the selection of hyper-parameters $\\lambda$ and $\\eta$.\n\n**Novel estimation techniques**\n\n1. By induction, we deduce that the gradient $\\|\\nabla F_S(x_t)\\|$ needs to satisfy the quadratic inequality $\\|\\nabla F_S(x_t)\\| \\leq \\sqrt{4(L_0 + L_1\\|\\nabla F_S(x_t)\\|)\\Delta_1}$ so that the gradient $\\|\\nabla F_S(x_t)\\|$ can be controlled when $\\lambda$ is greater than a constant. \n2. We construct a new martingale difference sequence $\\sum_{t=0}^{l-1}(L_1\\eta^2\\|\\nabla F_S(x_t)\\| - \\eta)\\langle \\nabla F_S(x_t), \\theta_t^a\\rangle$ and bound it by the Freedman’s inequality.\n3. By solving the inequality w.r.t. $\\lambda$, we obtain a better parameter setting about $\\eta$, thereby achieving a better convergence rate $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}}\\log^\\frac{2p-2}{2p-1}\\frac{T}{\\delta})$. \n\nWe will add these details to the revised version.\n\n**The first generalization result under $(L_0, L_1)$-smoothness**\n\nTo the best of our knowledge, there is no work to analyze the generalization bound under $(L_0, L_1)$-smoothness. We propose a new analytical method base on uniform convergence to quantify generalization ability only under weaker assumptions (i.e., $(L_0, L_1)$-smoothness and heavy-tailed noise), which is shown in Section 4.2.\n\n### **It is non-trivial to extend the analysis in CL to FL.**\n\nExtending CL to FL will cause the error term $A \\leq \\mathcal{O}((mKT)^\\alpha), \\alpha > 0$ in Eq. (66), which restricts $\\gamma \\leq \\mathcal{O}((mKT)^{\\frac{-p-1}{3p-2}})$. A nearly optimal convergence rate requires $\\gamma \\geq \\mathcal{O}((mKT)^{\\frac{-p}{3p-2}})$, resulting in a contradiction. **Firstly**, we proposed the clipped mini-batch gradient and analyzed the batch gradient variance under heavy-tailed setting in Lemma 1, which open the door to analyze the mini-batch methods in the heavy-tailed noise. **Secondly**, different from Eq. (15) in the CL, we prove the upper bound for errors $\\epsilon_t^a$ and $\\epsilon_t^b$ as shown in Lemma 2. They are the new results under the federation setting. **Thirdly**, we propose a \"sum-aggregation\" as shown in Algorithm 2 to facilitate our proof. **Finally**, $(L_0, L_1)$-smoothness makes the gradient implicit in Ineq. (61) and we handle it by solving a quadratic inequality. Thus, such expansion is non-trivial. To address your concerns, we will add a discussion in our revised version.\n\n### **About the logarithm factor $\\log(\\frac{T}{\\delta})$.**\n\nIt is possible to obtain a convergence bound with $\\log(T/\\delta)$ order as in [1]. In fact, the work [29] achieves this result. Note that they are all based on the criteria $\\frac{1}{T}\\sum_{t=1}^T\\|\\nabla F_S(x_t)\\|$. According to Jensen's inequality, our convergence rate is $\\mathcal{O}(T^\\frac{1-p}{3p-2}\\log^\\frac{p-1}{2p-1}\\frac{T}{\\delta})$ based on this criteria, which is better than [6] [29] w.r.t. $\\log(T/\\delta)$ order due to $\\frac{p-1}{2p-1} \\in (0, \\frac{1}{3}]$. Although this improvement is not significant, it is achieved under the weaker $(L_0, L_1)$-smoothness assumption.\n\nIn the heavy-tailed noise, the lower bound in expectation is $\\mathcal{O}(T^{\\frac{2-2p}{3p-2}})$ [2] and it proves that global clip (GClip) algorithm can achieves this lower bound. But in high-probability analysis, the lower bound is unknown, and it is not clear whether the logarithm factor can be completely removed. This is also one of our future research directions. \n\n[6] Ashok. High-probability bounds for non-convex stochastic optimization with heavy tails. NeurIPS, 2021.\n\n[7] Zhang. Why are adaptive methods good for attention models?. NeurIPS, 2020."}]

Author rebuttal:

Meta-review: The paper provides tight high probability convergence bounds for clipped SGD for non-convex optimization with heavy-tailed noise. The results hold for functions that are (L0, L1)-smooth, which is a generalization of the classical smoothness assumption. Previous works were either only in expectation, for a less general class of functions or smaller noise. The paper also has new bounds for the federated setting and especially generalization bounds, which are not common in the literature.

The reviewers generally agree that while many proof techniques are from previous works, combining them requires addressing several technical challenges. They all put the paper above the bar.
Decision: Accept (poster)