Taming Fat-Tailed (“Heavier-Tailed” with Potentially Infinite Variance) Noise in Federated Learning
Authors: Haibo Yang
Peiwen Qiu
Jia Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
optimization
heavy-tail
stochastic gradient descent
clipping

Abstract: In recent years, federated learning (FL) has emerged as an important distributed machine learning paradigm to collaboratively learn a global model with multiple clients, while keeping data local and private. However, a key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochastic first-order information has a finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many fat-tailed noise distributions (i.e., ``heavier-tailed'' with potentially infinite variance) that have been empirically observed in the FL literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us to fill this gap in this paper by proposing an algorithmic framework called $\mathsf{FAT}$-$\mathsf{Clipping}~$ (\ul{f}ederated \ul{a}veraging with \ul{t}wo-sided learning rates and \ul{clipping}), which contains two variants: $\mathsf{FAT}$-$\mathsf{Clipping}~$ per-round ($\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PR}$) and $\mathsf{FAT}$-$\mathsf{Clipping}~$ per-iteration ($\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PI}$). Specifically, for the largest $\alpha \in (1,2]$ such that the fat-tailed noise in FL still has a bounded $\alpha$-moment, we show that both variants achieve $\mathcal{O}((mT)^{\frac{2-\alpha}{\alpha}})$ and $\mathcal{O}((mT)^{\frac{1-\alpha}{3\alpha-2}})$ convergence rates in the strongly-convex and general non-convex settings, respectively, where $m$ and $T$ are the numbers of clients and communication rounds. Moreover, at the expense of more clipping operations compared to $\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PR}$, $\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PI}~$ further enjoys a linear speedup effect with respect to the number of local updates at each client and being lower-bound-matching (i.e., order-optimal). Collectively, our results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.

Taming Fat-Tailes ("Heavier-Tailed') with Potentially Infinite Variance) Noise in Federated Learning
Haibo Yang Dept. of ECE
Peiwen Qiu Dept. of ECE
Jia Liu Dept. of ECE The Ohio State University Columbus, OH 43210 liuβece. esu.edu
The Ohio State University Columbus, OH 43210 yang. 59520osu. edu
The Ohio State University Columbus, OH 43210 fiu.os. edu
Abstract
In recent years, federated learning (FL. has emerged as important distributed machine learning paradigm to collaboratively learn a global model with multiple clients, while keeping data local and private. However, key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochas- tic first-order information has finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), fails for many fat-tailed noise distributions (i.e., "heavier-tailed" with potentially infinite variance) that have been empirically observed in the FL. literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us fill this gap in this paper by proposing an algorithmic framework called FAT-Clipping (federated averaging with two-sided learning rates and clipping). which contains two variants: FAT CCT-Cpippi per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-Pl), Specifi- cally, for the largest tail-index a (1,2] such that the fat-tailed noise in FL still has a bounded o-moment, we show that both variants achieve ((mT) شي and
((mmZ) So-2 convergence rates in the stoogly-convve and general non-convex settings, respectively, where and I are the numbers of clients and communication rounds. Moreover, with more clipping operations compared to FAT-Clipping-PP FAT-Clipping-PP further enjoys linear speedup effect with respect the number of local updates at each client and being lower- nower-bound bound-matching (i.e., order-optimal). Collectively, results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.
1-a
Introduction
In recent years, federated learning (FL) has emerged as an important distributed machine learning paradigm, where, coordinated by a server, set of clients collaboratively leam global model, while keeping their training data local and private. With intensive research in recent years, researchers have developed many FL algorithms (e.g., FedAvg (1] and many follow-ups (2) that have been theoretically shown to achieve fast convergence rates in the presence of various types of randomness and heterogeneity resulted from training data, network environments, computing resources clients, etc. Moreover, many of these algorithms enjoy the so-called "linear speedup" effect, i.c., the convergence time to first-order stationary point is inversely proportional to the number of workers and local update steps.
However, despite the recent advances in FL algorithm design and theoretical understanding, "cloud that remains obscures the sky of FL" is a common assumption that can be found in almost all works
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

on performance analysis of FL algorithms, which states that the random noise in stochastic first-order oracles (e.g., stochastic gradients or associated estimators) has finite variance. Although this assumption is not too restrictive and can cover all light-tailed (i.e., sub-exponential) and some heavy- tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many "fat-tailed" distributions (i.e., "heavier-tailed"" with potentially infinite variance)). D. In fact, fat-tailed distributions have already been empirically observed under centralized learning settings [15) let alone in the more heterogeneous FL environments. Later in Section 3 we will also provide empirical evidence that shows that fat-tailed noise distributions can be easily induced by FL systems with non-i.i.. datasets and heterogeneous local updates across clients.
The presence of fat-tailed noise poses two major challenges FL algorithm design and analysis: i) Experimentally, it has been shown in [20) that many existing FL algorithms suffer severely from fat-tailed noise and frequently exhibit the so-called "catastrophic failure of model performance" (i.e., sudden and dramatic drops of learning accuracy during the training phase); ii) Theoretically, the infinite variance of the random noise the stochastic first-order oracles renders most of the proof techniques in existing FL algorithmic convergence analysis inapplicable, which necessitates new algorithmic ideas and proof strategies. light of these empirical and theoretical challenges, two foundational questions naturally emerge in FL algorithm design and analysis: 1) Can develop FL algorithms with convergence guarantee under far-eratttte far-tailed noise? 2) If the answer to 1) is "yes," could characterize their finit--ime convergence rates? In this paper, we provide affirmative answer to the above questions. Our major contributions in this paper are highlighted as follows:
To address the challenges of the fat-tailed noise in FL algorithm design, we propose algorithmic framework called FAT FAT-Clipping (federated averaging with two-sided learning rates and clipping), which leverages clipping technique to mitigate the impact of fat-tailed noise and uses two-sided learning rate mechanism to lower communication complexity. Our FAT-Clipping framework and FAT-Clipping per-iteration
contains two variants: FAT-Clipping per-round (FAT-Clipping- FFTT-Clipping-P1; We show that, for the largest tail-index a E (1,2) such that the fat-tailed noise in FL still has bounded a-moment, both FAT-Clipping variants achieve ((mTT) 2=0
and (mmT) )ー convergence rates in the strongly-convex and general non-convex settings, respectively, where and T are the numbers of clients and communication rounds.
Between the proposed FAT-Clipping variants, FAT-Clipping- only performs one clipping oper- ation in each communication round before client communicates the server, while FAT FAT-Clipping- PI performs clipping in each iteration of local model update. We show that, at the expense of more clipping operations compared to FAT- FAT-Clipping-PR, FAT-Clipping-PI further achieves a linear speedup effect with respect to the number local model updates at each client and is lower-bound matching in terms of convergence rate.
In addition to theoretical analysis, we also conduct extensive numerical experiments to study the fat- tailed phenomenon in FL systems and verify the efficacy of our proposed FAT-Clipping algorithms for FL systems with fat-tailed noise. We first provide concrete empirical evidence that fail-tailed noise distributions are not uncommon in FL systems with non-i.i.d. datasets and heterogencous local updates. We show that our FAT-Clipping algorithms render much smoother FL training process, which effectively prevents the "catastrophic failure" in various FL settings.
For quick reference and easy comparisons, we summarize all convergence rate results in Table The rest of the paper is organized as follows. In Section 2 we review the literature to put our work in comparative perspectives. In Section 3 we provide empirical fat-tailed evidence for FL to further motivate this work. Section 4 presents our FAT PCT-Clipping algorithms and their convergence analyses. Section [3 presents numerical results and Section (octioon]ccor cooclluess this paper. Due to space limitation, all proof details and some experiments are provided in the supplementary material.
'In the literature, terminologies "heavy-tailed" and "fat-tailed" are not universally defined and could be interchangeable sometimes. In this paper, we follow the convention of those authors who reserve the term "fat-tailed to mean the subclass of heavy-tailed distributions that exhibit power law decay behavior as well as infinite variance (see, e.g., [3 14). Thus, every fat-tailed distribution is heavy-tailed, but the reverse is not true.

---

Table 1: Convergence rate comparisons under fat-tailed noise distributions (shaded parts are our results; metries: fxx - f(x") S and [xx]] I for
convex and non non-convex functions, respectively): a and a E (1, 2) correspond to non-fat-tailed and fat-tailed noises, respectively. Here, R is the total number of iterations for centralized algorithms (SGD and GClip); K and T are local update steps and communication rounds in the FI. setting, respectively; m is the number of clients. N/A means no theoretical guarantee for convergence. Note that the total number of iterations R in FL can be computed as R = KT, which relates to that in the centralized setting.
Strongly Convex Objective Functions
Nonconvex Objective Functions
Methods
Fat. Tailed
Non. Fat Ranled-TTailed
Tailed
Non Non-Fat- Tai-Te
SGD 21
NIA 2-20 O
O(R-1)
N/A O 06
O t)
GClip 22
O(R-1)
O +)
FodAvg
NAA
((MKTT)-))
N/A O(mml) 36-2 K 5a-2) (((MTT) 3a=2)
((MKT) t)
FAT-Clipping-PR
((mi) 2- )²
(((KKT)-1)
((mKT) #)
FAT-Clipping-PI
(((mKT)
2-20
((MMKT)-)
((mKKT) b)
Lower Bound
2 Box D((KTT)
Q((mKT)-1)
1-8 0((MT))
A((MTT)
2
Related work
In this section, we will provide quick overview on three related topics in the literature: i) federated learning, ii) heavy-tailed noise in learning, and iii) the clipping techniques, thus putting our work into comparative perspective highlight our novelty and differences.
1) Federated I. Learning: As mentioned earlier, FL has recently emerged as an important distributed learning paradigm. The first and perhaps the most popular FL. method, the federated averaging (FedAvg) algorithm (T). was initially proposed as heuristic to improve communication efficiency and data privacy. Since then, FedAvg has sparked many follow-ups to further address the challenges of data/system heterogeneity and further reduce iteration and communication complexities. Notable approaches include adding regularization for the local loss function 22 556, using variance reduction techniques (3). taking adaptive learning rate strategy (8) adaptive communication strategy [23 24 and many momentum variants [4 10). Empirically, these algorithms are shown to be communication- efficient (I) and enjoy better generalization performance [25]. Moreover, many state-of-thh thethe--rt art algorithms enjoy the "linear speedup" effect in terms of the numbers of clients and local update steps in different FL settings 24 26). We note, however, that all these theoretical results built upon the finite variance assumption of stochastic gradient noise. Unfortunately, when the stochastic gradient noise is fat-tailed, the finite variance assumption longer holds, and hence the associated theoretical analysis is also invalid. This motivates us to fill this gap in this paper and conduct the first theoretical analysis for FL systems that experience fat-tailed noise.
2) Hlavy-TTiles Noise in Learning: Recently. heavy-tailed noise has been empirically observed in modern machine learning systems and theoretically analyzed [15] 16 18 22 27/30). Heavy-tailed noise significantly affects the learning dynamics and computational complexity, such as the first exit time escaping from saddle point (27) and iteration complexity (22). This is dramatically different from classic dynamic amalysis often based on sub- Gaussian noise assumption 32 and algorithmic convergence analysis with bounded variance assumption (3) However, for FL, there exist few investigations about hcavy-tailed behaviors. In this paper, first demonstrate through extensive experiments that fat-tailed (i.c., heavier-tailed noise in FL can be easily induced by data heterogeneity and local update steps. We then propose efficient algorithms to mitigate the impacts of fat-tails.
3) The Clipping Technique: Since our FAT-Clipping algorithms are based on the idea of clipping, here we provide an overview on this technique. As far as we know, dating back at least 1985 (34.. gradient clipping has been an effective technique to ensure convergence for optimization problems with fast-growing objective functions. In deep learning, clipping is a widely adopted technique to address the exploding gradient problem. Recently. gradient clipping was theoretically shown to be able to accelerate the training of centralized learning [17 35 37). Also, clipping is an effective approach to mitigate heavy-tailed noise [1 in centralized learning. In FL,, clipping has been used as the preconditioning step for preserving differential privacy (DP) (3). Unlike these works, in this paper, utilize clipping to address algorithmic divergence caused by fat-tailed noise in FL.
3

---

Algorithm 1 Generalized FedAvg Algorithm (GFedAvg).
1: Initialize X1.
2:
for -= (communication round) do
3: for each client & [ma] in parallel do
4: Update local model: x X
5: for k = =, K (local update step) do
6:
Compute an unbiased estimate V (x 5t,e) of fi(f)))
7:
Local update: g,5
,++1
= =x,,
TT V ck
8:
end for
9: Send A
= Vxi( tt,)) to the server.
end for
11: Global Aggregation At Server:
12:
Receive Ai, E [m].
13:
Server Update: X++1 = Xt- TEL Eielm A
14:
Broadcasting X to clients.
15:
end for
3 Fat-tailed noise phenomenon in federated learning
In this section, we first introduce the basic FL problem statement and the standard FedAvg algorithm for FL. Then, we provide some necessary background of fat-tailed distributions and provide empirical evidence to show that fat-tailed noise can be easily induced by heterogeneity of data and local updates in FL. which further motivates this work. Lastly, we demonstrate the algorithmic divergence and frequently catastrophic model failure under fat-tailed noise.
Problem Statement of Federated Learning and the FedAvg Algorithm: The goal of FL is to solve the following optimization problem:
min f(x) XERd
m Σ f((x),
1
where m is the number of clients and f+(x) A RE--D (xxxE) is the local loss function associated with local data distribution Dj. A key challenge in FL. stems from data heterogeneity, i.e., D, * Dj, vi * j. In FL. the standard and perhaps the most popular algorithm is the federated averaging (FedAvg) method. Here in Algorithm [ we illustrate more generalized version of the original FedAvg (GFedAvg) with separate learning rates on the client and server sides 73 8) Note that when " 1. GFedAvg reduces to the original FedAvg [1]. each communication round of GFedAvg, each client performs local update steps and returns the update difference A The server then aggregates these results and update the global model 2 and the updated model parameters will then be retrieved by the clients to start the next round of local updates.
With the basics of FL. and the FedAvg algorithm, we are now in a position to demonstrate the empirical evidence of the existence of fat-tailed noise in FL systems. As mentioned earlier, in most performance analyses of FL algorithms, a common assumption is the bounded variance assumption of the local stochastic gradients: / V < o², This assumption holds for all light-tailed noise distributions (i.e., the sub-exponential family) and some heavy-tailed distributions (e.g.. log-normal, Weibull, and some Pareto distributions).
2) Empirical Evidence of Fat-Tailed Noise Phenomenon in Federated Learning:
However, the finite-vriiacee assumption fails to hold for many fat-tailed noise distributions. For instance, for random variable X, if its density p(x) has power-law tail decreasing as 1/|z|-+1 with a E (0, 2), then only the a-moment of this noise exists with a < 2. To more precisely characterize fat-tailed distributions. in this paper, adopt the notion of tail-index [15) to parameterize fat-tailed and heavy-tailed distributions. More specifically, the density of a random variable X's distribution decays with a power law tail 1/ |+ where (0, 2]. then a: is called the tail-infex. This a-parameter determines the behavior of the distribution: the smaller the a-value, the heavier the tail
We assume all clients participate in the training each communication round, but the results can be extended that with (uniformly random sampled) subset of clients in each communication round 3

---

2: 2:020-
0.25
1..4. case
1:15
Single 560
Test Accu.
0.6-
g 0015-
loal F
00:0
Epechiu?
5 0.05
Epcchw
8.
0.00
0.25
0.1
0.6 08
non-..d.
10
122
166
1.06
Grad Norm
60
200
400 600 800 100012001400
24 2-000
5 10:00-
0.15
%
① 0.055-
0.00
0.4
0.5
0.6
1.C
0.58
200 400 600 B00 10001200 1400
Noise
Non-II Index (o)
Communication Round
Figure 1: Distributions of the norms of the pseudo-gradient noises computed with CNN on CIFAR- 10 dataset in i.i.d. case (top) and non-i.i.d case (bot- tom). m = 100 clients partic- ipate in the training.
Figure 2: Estimation of a for CIFAR-I0 dataset. The non-IlI) index p represents the data het- erogeneity level, and p 10 is the IID case. The smaller the p.
Figure 3: Catastrophic training failures happen when applying GFedAvg on CIFAR-10 dataset, where the test accuracy expe- riences a sudden and dramatic drop and the pseudo pseudo-gradient norm increases substantially.
the more heterogeneous the data across clients.
of the distribution. Also, the a-parameter also determines the moments: E[[X["] < oo if and only if r < a, which implies that X has infinite variance when a < 2, i.e., being fat-tailed.
Next, we investigate the tail property of model updates returned by clients in the GFedAvg algorithm. Due to multiple local steps in the GFedAvg algorithm, we view the whole update vector A returned by each client, which we called "pseudo-gradient"" " as a random vector and then analyze its statistical properties. Note that in the special case with the number of local update K 1, A coincides with a single stochastic gradient of a random sample, (i.e., A fx( (:))
We study the mismatch between the "non-fat-tailed" condition (a = 2) and the empirical behavior of the stochastic psudo-gradient noise. In Fig. 0 we illustrate the distributions of the norms of the stochastic pseudo-gradient noises computed with convolutional neural network (CNN) on the CIFAR-10 10 dataset in both i.i.d and non-i.i.d. client dataset settings. We can clearly observe that the non-i..dd. case exhibits a rather fat-tailed behavior, where the pseudo-gradient norm could be as large as 1.6. Although the i.idd case appears to have much lighter tail, our detailed analysis shows that we estimate a-value for the CIFAR-10
it still exhibits a fat-tailed behavior. To see this, in Fig. 2 dataset in different scenarios: 1) different local update steps, and 2) different data heterogeneity. We use a parameter p to characterize the data heterogeneity level, with p = 10 corresponding to the i.i.d. case. The smaller the p. the more heterogeneous the data among clients. Fig. sisows that the a-vulue smaller than 1.15 all scenarios, and a increases as the non-i.i.d. index p increases (i.e., closer to the i.i.d. case). This implies that the stochastic pseudo-gradient noise is fat-tailed and the "fatness" increases as the clients' data become more heterogeneous.
3) The Impacts of Fat-Tailed Noise on Federated Learning: Next, we show that the fat-tailed noise could lead a "catastrophic model failure" (i.e., a sudden and dramatic drop of learning accuracy), consistent with previous observations in the FL literature [20). To demonstrate this, we apply GFedAvg on the CIFAR-16 10 dataset and randomly sample five clients among m = 10 clients in each communication round. In Fig. 3 we illustrate a trial where catastrophic training failure occurred. Correspondingly, we can observe in Fig. 3 spike in the norm of the pseudo-gradies gradient. This exceedingly large pseudo-gradient norm motivates gradient updates. is also worth noting that even if the squared norm of stochastic gradient may not be infinitely large in practice (i.e., having bounded support empirically). it could still be too large and cause catastrophic model failures. In fact, under fat-tailed noise, the FedAvg algorithm could diverge, which follows from the fact that there exists one function that SGD diverges under heavy-tailed noise (see Remark in (21). As a result, the returned value by one client might be exceedingly large, leading to divergence of the FedAvg-type algorithms.
to apply the clipping technique to curtail the
It is worth pointing out that, although we have empirically shown heavy/fat-tail tailed noise in FL for the first time in this paper, we are by no means the only one to have observed heavy-tailed or failda noise phenomenon property in learning. Previous works have also found heavy/fat-tailed noise phenomenon in centralized training with SGD-type algorithms. For example, the work in [15) showed the heavy-tailed noise phenomenon while (centralized) training the Alex on CIFAR-10 10. Here, we adopt a procedure similar to that in [5] to evaluate the tail index of the noise norm distribution in
5

---

Algorithm 2 The FAT-Clipping-PR Algorithm.
1: Initialize X1.
2:
for 1, (communication round) do
3: for each client E [m] in parallel do
4: Update local model: x X
5: for k = =, .,... K (local update step) do
6:
Compute an unbiased estimate V (x), St,i) of (x.t)).
7:
Local update: x k++1 = =x,,
(x St,1)
ck
8:
end for
9:
Let A; EkE(K] Vf((x,, st,))
10:
Clipping: Á min {1, |اح } where A EkE(K] St,,)
Send Â the server.
12:
end for
13:
Global Aggregation At Server:
14:
Receive Â [m]-
Server Update: X++1 X VH
Exe(m) D
m
Broadcasting X clients.
17:
end for
FL. As indicated above, we also observe that the (oseudo-)stochasse gradient noise is heavy/fat-tailed rather than Gaussian.
is also worth noting that it remains controversial whether the heavy/fat-tailed noise phenomenon exists in all models and datasets. For example, the work in (19) showed that the stochastic gradient noise is Gaussian at least in the early phases of training, while [41] showed that the stationary distribution of stochastic gradient noise heavy-tailed and state-dependent. Also, the evaluation methodologies of could be different in different works with different statistical errors, thus leading different observations [9 22). We believe that the phenomenon of heavy/fat-taile noise training with SGD-type methods is an under-explored area that deserves more efforts from the community.
To conclude this section, would also like leave caveat regarding catastrophic training failures. In this section, we have shown that, under heavy/fat-tailed noises, catastrophic training failures happen in FL training, which is consistent with the observations in large-cohort FL training (20). However, this does not necessarily mean that all FL trainings will suffer from catastrophic failures. Sometimes, such catastrophic failures may not happen at all (see the appendix for such empirical evidence). Here, we hypothesize that the heavy/fat-tailee noise phenomenon in FL is highly correlated with catastrophic failures in FL. This is based on our subsequent observations that such catastrophic failures in FL can be effectively mitigated by employing clipping methods. However, whether or not the heavy/fat-tailed noise phenomenon is truly the culprit for catastrophic failures still needs further investigations. Nonetheless, the mere existence of such a correlation between heavy/fat- taatt/tattllledd noise and catastrophic failures in FL warrants our study on mitigating heavy/fat-taais tailed noise in this paper.
The FAT-Clipping algorithmic framework for fat-tailed federated learning
Given the evidence of fat-tailed noise in FL and its potential catastrophic training failure as shown in ( there a compelling need to design an efficient FL algorithm with provable convergence guarantee under fat-tailed noise in FL. Interestingly, the observation of an exceedingly large pscudo- gradient norm in Fig. BJugggests a natural idea to mitigate fat-tailed noise: clipping. Toward this end, in Section 4.1 we first propose clipping-based algorithmic framework called FAT-Clipping, which contains two variants: FAT FAT-Clipping per-round (FAT- TFAT-CCipping-PP5 and FAT-Clipping per-iteration WPAT-Clipping-. Then in Section 4.2
analyze their convergence rate performances.
4.1 The FAT-Clipping-PR and FAT-Clipping-P11 algorithms
We illustrate the FAT-Clipping-PPE and FAT-Clipping- PI algorithms Algorithms 2 and 3 respec- tively. It can be seen that both FAT-Clipping-PPP PR and FAT-Clipping- PI share similar algorithmic

---

Algorithm 3 The FAT-Clipping-Pl Algorithm.
1: Initialize X1.
2: for =, (communication round) do
3: for each client E [m] in parallel do
4: Update local model: x X
5: for k = 1, ... K (local update step) do
6:
Compute an unbiased estimate ( St, of (x(.)))
7:
Clipping: V fx(f ST.:) = min f1, V V St. (x))
8:
x 7Ι (x S. Local update: X,, k+1
9:
end for
10:
Send A = E (x $f,)) to the server.
11: end for
Global Aggregation At Server:
Receive Σ E [m]]
14:
Server Update: X++1 = X
WEL
Eie(m) Di.
m
15:
end for Broadcasting X1+1 to clients.
16:
structure with GFedAvg. with the key differences lying in the additional clipping operations. In FAT-Clipping-PRR each client performs clipping in each communication round on the returned A
A A min {1. "A!I
and then sends á instead of A to the server (Line Algorithm 2. Pl, each client clips the stochastic gradient before each local update step (Line 7 in Algorithm
By contrast, in FCT-Ciipping-
fx a:
st,)) = min
f st,))
(3)
IV &tD
k+1 XLi
x
( ct.))
(4)
Then, Á
ΣkE[K]
(x
ck is sent to the server for aggregation (Line 10 in Algorithm 1,11
4.2
Convergence analysis of the FAT-Clipping algorithms
Before conducting the convergence analysis for the FAT-Clipping algorithms, we first state two standard assumptions that are commonly used in the literature of first-order stochastic methods.
Assumption 1 (L-Lipschitz Continuous Gradient). There exists constant L > 0, such that [VV[(x)) - V)e(y) < L||x - yll, Vx, E Rd and E [m].
Assumption (Unbiased Local Gradient Estimator). The local gradient estimator is unbiased, i.e., E[VA((x < V (xx),, Vi E [m], where & is random local data sample at the i-th worker.
Next, we state the key bounded a-moment assumption for fat-tailed the stochastic first-order oracle, which leverages the notion of tail-index introduced in Section 3
Assumption (Bounded a-Moment). There exists a real number E (1, and constant G 2 0, such that f. [ < Ga, Vi E [m], E Rd.
1) Convergence Rates of the FAT MAT-Clipping-PR Algorithm: We first state the convergence rates of FAT-Clipping-PRR PR for μ-strongly convex and non-convex objective functions.
Theorem 1. (Convergence Rate of FAT-Clipping-PRR in the Strongly Convex Case) Suppose that ʃ(+) is p-stronggy convex function. Under Assumptions [ J'mM.K 2_ then the oulput Xr
of FAFT-COT Clipping- PR being chosen such a way that Xy X2 with probability Eje wy²
we
where
w. = (1 kumm K)) 1-, satisfies:
K)'-1,
S(XT) f(x") exp (-1 (-2um.KK)
MMLK Go 2012-0 22 2- 20 x3
7

---

where x" denotes the global optimal solution. Further, let 1771,, K
2e IufP)
mKT where 2 1 is
constant satisfying 2=2a
K g 2-20 2 1, and let 1 S (mKT) 1-
It then follows that
f(TT) - f(x'((xx=x)))))>r)) - ((ml)) 2-20 K&)
Theorem 2. (Convergence Rate of FAT-Clipping-PRR in the Nonconvex Case) Suppose that f(-) is if m/. K.I. S 1, then the sequence of outpuls {xx)
nonconvex function. Under Assumptions generated by FAT- AAT-Clipping-PP satisfies:
2 (f(x)) - -((T))
min E V (1 (E
( -K2 2(a-1) LLL G
MLKT
LaME (KG
m
Further, choosing learning rates and clipping parameter in such way that m771 d-tn
m T 30-2 ,,,,, M S (m'T) 30-2 K 30-2, and X = (mK*T)3 we have
min ((x) (((mm) 2 EE[T]
We note that the above convergence rates for FAT- FAT-Clipping-PP does not generalize the results of FedAvg when a = 2 (non-fat-tailed noise). Specifically, FedAvg is able to achieve (mmKT)))) and ((mKT)) 4) convergence rates for strongly convex (f (x) f(x*) S é) and
Remark 1.
non-convex function (IV [x)) S e). respectively (3 42). In contrast, FAT AAT-CCipping--PP PR achieves ((mT))- K") and ((mm)) - for strongly-convex and non-convex functions, respectively. These two rates are consistent with those of FedAvg in terms of m and T, but not in terms of K.
Interestingly, with separate proof for non-fat-tailed noise (a = 2), we can show that clipping does not affect the dependence on K in the convergence rates. Thus, FAT-Clipping- convergence rates as those of FedAvg. Due to space limitation, we state an informal version of these theorems here. The full versions of Theorem 6 and their proofs are formally stated in Appendix.
has the same
Theorem 6 & 7 (informal) (Convergence Rates of FAT- CAT-ClipPing-PR for Non-Fat-Tailed Noise):
For 2, CPR-FedAvg achieves convergence rale ((mKT)-+) for strongly-convex and ((mKT)- for non-convex functions, respectively.
2) Convergence Rate of the FAT-Clipping-Pl Algorithm: Next, we provide the convergence rates of FAT-Clipping-PI for y-strongly convex and non-convex objective functions.
Theorem 3. (Convergence Rate of FAT FAT-Clipping-P) in the Strongly Convex Case) Suppose that f()) is p-strongly convex function. Under Assumptions [
if fmnk a.. then the output &e
of FAT FAT-Clippi being chosen in such way that XT X₁ with probability Eyem wej
where
W = (1 - k) scatisfie:
f(xT) f(x') - 1 exp (-5mm. KT
MiK
Ga x-x
2
122 2(a-1) X 212 xm
where x" denotes the global optimal solution. Further, let MM K 1, and let X (mKT)) and n (mIT - ).
2c In(T)
a mKT where 2 is
constant satisfying (mK) 2-2n get
2-20
then follows that
[(xT) - s(x'x(xxx))))))) = ((mKT) 2-20
Theorem 4. (Convergence Rate of FAT- PI in the Nonconvex Case) Suppose that f() is non-convex function. Under Assumptions generated by FAT-Clippings satisfies:
3 if KL & 1, then the sequence of outputs {xx]
2 (x(1)) - f((T)) + (20 + +2L2 K2 G2 x-a2-a)) km
min E V (xx 2 T
mmrKT
LMML
(G" (-0))
8

---

2.
Fedivn FAT Clsping PI
FAT-Ckrpingg11 P1
20 6
Sucees
888888
non U.d. case
FAT-cliping-11
100/607)
1.5
800
FudAeg
FAT-Cip-PR FAT-Cii-Pl
ap 300000000
ob8883 g
0.5
31h00-1 0
of
Communication
Communication
100
160
200
250
800
Fackhn FAT-CII-PR FAT-CIp-
Figure 4: Convergence compar- isons of FedAvg, FAT -Ciippnnn- PI, and FAT-Clipping-PP for solving strongly convex mod- els: synthetic data with & having Cauchy tails (fat).
Figure 5: Convergence compar-
Figure 6: Percentage of suc- cessful training over 5 trials when applying FedAvg, FAT- Clipping- -Pp and FAT-Clipping- PI CIFAR-10 dataset in non- i..dd case and i.i.d. case.
isons of FAT FAT-Clipping-Pl and FAT-Clipping-PR for solving strongly convex models: syn- thetic data with & having differ- ent fat tails represented by a.
Further, choosing learning rates and clipping parameter in such way that TpI 20
m (KT) Su 2 2, I (mKT) oa and X = (mKT) Ba we have
min [ (((KT)))5- $ E
In comparison to FAT-Clipping-PRR convergence rates of FAT FAT-Clipping-Pl generalize the results of FedAvg for the non-fat-tailed noise case (i.e., a = 2). Specifically, when a = FAT-Clipping-P) achieves ((mKK))) and ((mKT) ) convergence rates for strongly convex and nonconvex objective functions, respectively. These two convergence rates consistent with those of FedAvg in terms of m, K and T (ignoring logarithmic factors in the strongly-convex case).
Remark 2.
Next, show that the convergence rates for FAT-Clipping-PP is order-optimal for a (1,2) by proving the following lower bounds.
Corollary 1 (Convergence Rate Lower Bound), Given any o (1, 2). for any potentially randomized algorithm, there exists stochastic strongly-conve function satisfying Assumption 3 with G < 1, such that the output of XT after T communication rounds has an expected error lower bounded by
[[f(x,] - -f(xx))))((xx) = (((KKT)
Also, there exists a non-convex function communication rounds has expected error lower bounded by
connttttuuunnioinn satisfying Assumption 3 such that the output of Xy after T
[
= ((()))====((((XX 3a-2).
With T' communication rounds, the total number of stochastic gradients is m.T. Thus, the lower bounds above can be obtained from the centralized SGD with fat-tailed noise [22 Theorems and 6)). Clearly, the above lower bounds imply the optimality of the convergence rates of FAT FAT-Clipping-PI.
5 Numerical results
In this section, we conduct numerical experiments to verify the theoretical findings in Section 4 Musing 1) synthetic function, 2) convolutional neural network (CNN) with two convolutional layers on CIFAR- dataset [43), and 3) RNN on Shakespeare dataset. Due to space limitation, we relegate experiment details and extra experimental results to the supplementary material.
Strongly Convex Model with Synthetic Data: We consider a strongly convex model for Prob- lem as follows: fa (z) Eg [f (x. {)] and f {x. 1 ||-|| (),x), where
random vector. We compare FedAvg. FAT-Clipping Pl, and FAT-Clipping- PR, where the noise ş is Cauchy distributed (fat-tailed). Also, we compare FAT FAT-Clipping-PP and FAT-Clipping-PP with E having different tail-indexes (a = 0.5, 1.0, and 1.5). For each distribution, we use the same experimental setup, and m 5 clients participate in the training. We show the trajectories of FedAvg, FAT- Clipping-Pi Pl. and FAT-Clipping- PR for solving Problem ( with having Cauchy tails in Fig. 4 and
2

---

with & having different a-values in Fig. [ We can clearly observe from Fig. that FAT -li-ppip PI and FAT- FAT-Clipping-PP converge rapidly in the Cauchy case, and FAT- AAT-Clipping-- Pl converges faster than FAT-Clipping-PR as our theoretical results predict. In contrast, FedAvg is not convergent in the Cauchy case. In Fig. 5 we can see that the convergence processes of FAT-Clipping-Pe and FAT-Clipping-PP PI become slower as the o-value increases as our theoretical results predict, but the differences in FAT-Clipping-PP are much less obvious compared to those of FAT-Clipping-PRR
2) CNN (Non-convex Model) on the CIFAR-10: This setting has m = 10 clients in total, and five clients are randomly selected to participate in each round of the training. We compare FAT- Clipping algorithms with FedAvg under different data heterogeneity. To simulate data heterogeneity across clients, we distribute the data to each client in a label-based partition following the same procedure as in existing works (e.g.. 7 44)) D: we use a parameter to represent the number of labeled classes in each client, with p = corresponding to the i.i.d. case and the rest corresponding to non-i.i.d. cases. The smaller the p-value, the more heterogeneous the data across clients. In Fig. 6 we present the percentage of successful training over 5 trials when applying FedAvg, FAT- Clipping-PR and FAT-Clipping-PP on CIFAR-IO in non-i.idd. case (p = 2) and i.i.d. case (p- 10). FAT-Clipping-P) has 100% successful rates (i.e., no catastrophic model failures) in both non-i.i.d. and i.idd cases, and FAT-Clipping respectively. However, FedAvg fails in all 5 trials. Thus, compared to FedAvg, FAT-Clipping methods (FAT-Clipping-PP Pl in particular) significantly reduce catastrophic training failures.
has 60% and 20% successful rates in non-i..dd and i.i.d. cases,
6 Conclusions and future work
In this paper, we investigated the problem of designing efficient federated learning algorithms with convergence performance guarantee in the presence of fat-tailed noise in the stochastic first- order oracles. We first showed empirical evidence that fat-tailed noise in federated learning can be induced by data heterogeneity and local update steps. To address the fat-tailed noise challenge in FL algorithm design, we proposed a clipping- -based algorithmic framework called FAT- -lippinp The FAT ACT-Cinp framework contains two variants FAT- PAT-Clipping-PR and FAT-Clipping-PLL which perform clipping operations in each communication round and in each local update step. respectively. Then, we derived the convergence rate bounds of FAT-Clipping- PR and FAT-Clipping-PP PP for strongly convex and non-convex loss functions under fat-tailed noise. Not only does our work shed light on theoretical understanding of FL under fat-tailed noise, it also opens the doors many new interesting questions in FL systems that experience fat-tailed noise.
Acknowledgements
This work has been supported in part by NSF grants CAREER CNS-2110259, CNS-2112471, ECCS-21402777, and 102-21
References
[1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, "Communication-efficine learning of deep networks from decentralized data," " in Artificial intelligence and statistics. PMLR, 2017, pp. 1273-1282.
[2] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, "Federated optimization in heterogeneous networks." in Proceedings of Machine Learning and Systems, I. Dhillon, D. Papailiopoulos, and V. Sze, Eds., vol. 2, 2020, pp. 429-450.
[3] P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. Suresh, "SCAFFOLD: Stochastic controlled averaging for federated learning," in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13-18 Jul 2020, pp. 5132-5143.
[4] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, "Tackling the objective inconsistency problem in heterogeneous federated optimization." Advances in Neural Information Processing Systems, vol. 33, 2020.
[5] X. Zhang, M. Hong, S. Dhople, W. Yin, and Y. Liu, "Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data," arXiv preprint 2rXiv:2005.114:1 2020.
10

---

[6] D. A. E. Acar, Y. Zhao, R. M. Navarro, M. Mattina, P. N. Whatmough, and V. Saligrama. "Federated learning based on dynamic regularization." " in International Conference on Learning Representations, 2021.
[7] H. Yang, M. Fang, and J. Liu, "Achieving linear speedup with partial worker participation in non-III federated learning." in International Conference on Learning Representations, 2021.
[8] S. J. Reddi, Z. Charles, M. Zaheer. Z. Garrett, K. Rush, J. Konecný, S. Kumar, and H. B. McMahan, "Adaptive federated optimization," " in International Conference on Learning Repre-
sentations, 2021.
[9] P. Khanduri, P. SHARMA, H. Yang, M. Hong, J. Liu, K. Rajawat, and P. Varshney, "STEM:
A stochastic two-sided momentum algorithm achieving near-optimal sample and communica- tion complexities for federated learning," in Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[10] X. Gu, K. Huang. J. Zhang, and I.. Huang, "Fast federated learning in the presence of arbitrary device unavailability," in Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[11] M. Luo, F. Chen, D. Hu, Y. Zhang, J. Liang, and J. Feng. "No fear of heterogeneity: Classifier calibration for federated learning with non-IID data," in Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[12] S. P. Karimireddy, M. Jaggi, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh, "Breaking the centralized barrier for cross-device federated learning," in Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[13] Nair, A. Wierman, and Zwart, The Fundamentals of Heavy Tails. Cambridge University Press, 2022, vol. 53.
[14] J. E. Taylor. Heavy-tailed distributions. [Online]. Available: https///math.la.as..cduu Seaching/Spring2016//TPP.. htccs////////ccuuusssabbbbpppppp
[15] U. Simsekli, L. Sagun, and M. Gurbuzbalaban, "A tail-index analysis of stochastic gradient noise in deep neural networks," " in International Conference on Machine Learning. PMLR. 2019, pp. 5827-5837.
[16] M. Gurbuzbalaban, U. Simsekli, and L. Zhu, "The heavy-tail phenomenon in sgd," in Interna- tional Conference on Machine Learning. PMLR, 2021, pp. 3964-3975.
[17] J. Zhang, T. He, S. Sra, and A. Jadbabaie, "Why gradient clipping accelerates training: theoretical justification for adaptivity," in International Conference on Learning Representations, 2020. [Online]. Available:
Yww)
[18] E. Gorbunov, M. Danilova, and A. Gasnikov, "Stochastic optimization with heavy-tailed noise via accelerated gradient clipping." Advances in Neural Information Processing Systems, vol. 33, pp. 052-115 053, 2020.
[19] A. Panigrahi, R. Somani, N. Goyal, and P. Netrapalli, -oon-gaussianity of stochastic gradient noise," arXiv preprint arXiv: 1900.0966. 2019.
[20] Z. Charles, Z. Garrett, Z. Huo, S. Shmulyian, and V. Smith, "On large-cohort training for federated learning." Advances in Neural Information Processing Systems, vol. 34, 2021.
[21] S. Ghadimi and G. Lan, "Stochastic first-and zeroth-order methods for nonconvex stochastic programming." " SIAM Journal on Optimization, vol. 23, no. 4, pp. 2341-2368, 2013.
[22] J. Zhang. S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra, "Why are adaptive methods good for attention models?" Advances in Neural Information Processing Systems, 33, pp. 15 383-15 393, 2020.
[23] J. Wang and G. Joshi, "Adaptive communication strategies to achieve the best error-runtime trade-off in local-update sgd," in Proceedings of Machine Learning and Systems, A. Talwalkar, V. Smith, and M. Zaharia, Eds., vol. 1, 2019, pp. 212-229, [Online]. Available: https: /proceedings.mil mwwss.sssssssssoss www.mmmssssossppeerree wttp://appe////////cctttttttaaaa
52d381112223 Paperri
[24] H. Yang. X. Zhang, P. Khanduri, and J. Liu, "Anarchic federated learning." in International Conference on Machine Learning. PMLR, 2022, pp. 25 331-25 363.
[25] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi, "Don't 't use large mini-batches, use local sgd," arXiv preprint arXiv: 1808.00100..7.,,,, 2018.
11

---

[26] X. Zhang, M. Fang, Z. Liu, H. Yang, J. Liu, and Z. Zhu, "Net-fleet: achieving linear convergence speedup for fully decentralized federated learning with heterogeneous data," Proceedings of the Twenty-Thire International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2022.
[27] T. H. Nguyen, U. Simsekli, M. Gurbuzbalaban, and G. Richard, "First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise," Advances in neural information processing systems, vol. 32, 2019.
[28] U. Simsekli, L. Zhu, Y. W. Teh, and M. Gurbuzbalaban, "Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise," in International Conference Machine Leurning. PMLR, 2020, pp. 8970-8980.
[29] L. Hodgkinson and M. Mahoney, "Multiplicative noise and heavy tails in stochastic optimiza- tion," in International Conference on Machine Learning. PMLR, 2021, pp. 4262-4274.
[30] H. Wang, M. Gurbuzbalaban. L. Zhu, U. Simsekli, and M. A. Erdogdu, "Convergence rates of stochastic gradient descent under infinite noise variance," Advances in Neural Information Processing Systems, vol. 34, 2021.
[31] S. Yaida, dnluctuatiiondissipaatit relations for stochastic gradient descent," arXiv preprint arXiv: 1810000040 2018.
[32] W. Hu, C. J. Li, L. Li, and J.-G. Liu, "On the diffusion approximation of nonconvex stochastic gradient descent," Annals of Mathematical Sciences and Applications, vol. 4, no. 1, 2019.
[33] L. Bottou, F. E. Curtis, and J. Nocedal, "Optimization methods for large-scale machine learning." " Siam Review, vol. 60, no. 2, pp. 223- 1, 2018.
[34] N. Z. Shor, "Minimization methods for non-differentiable functions," in Springer Series in Computational Mathematics, 1985.
[35] B. Zhang, J. Jin, C. Fang, and L. Wang, "Improved analysis of clipping algorithms for non- convex optimization," Advances in Neural Information Processing Systems, vol. 33, pp. 511- 15 521, 2020.
[36] X. Chen, S. Z. Wu, and M. Hong, "Understanding gradient clipping in private sgd: A geometric perspective," Advances in Neural Information Processing Systems, vol. 33, pp. 13 13 782, 2020.
[37] Qian, Y. Wu, B. Zhuang, S. Wang, and J. Xiao, "Understanding gradient clipping in incre- mental gradient methods," in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 1504-1512.
[38] X. Zhang, X. Chen, M.-F. Hong, Z. S. Wu, and J. Yi, "Understanding clipping for federated learning: Convergence and client-level differential privacy," ArXiv, vol. abs/2106.1366l 2021.
[39] R. Das, A. Hashemi, S. Sanghavi, and S. Dhillon, "Privacy-preserving federated learning via normalized (instead of clipped) updates," arXiv preprint arXiv:2 2021.
[40] G. Andrew, O. Thakkar, B. McMahan, and S. Ramaswamy, "Differentially private learning with adaptive clipping," " Advances in Neural Information Processing Systems, vol. 34, 2021.
[41] Q. Meng, S. Gong, W. Chen, Z.-M. Ma, and T.-Y. Liu, "Dynamic of stochastic gradient descent with state-dependent noise," arXiv preprint arXiv:2006. 1 19, 2020.
[42] Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth, "Lower bounds for non-convex stochastic optimization," arXiv preprint arXiv: 19/2. 2019.
[43] A. Krizhevsky, G. Hinton et al., "Learning multiple layers of features from tiny images," " 2009.
[44] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, "On the convergence of fedavg on non-iid data," in International Conference on Learning Representations, 2020.
[45] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, "Federated optimization in heterogeneous networks," " Proceedings of Machine Learning and Systems, vol. 2, pp. 429-450, 2020.
[46] Y. LeCun, Bottou, Bengio, and P. Haffner, "Gradient- learning applied to document recognition," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324 1998.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] As
theoretical paper towards further understanding federated optimization, do not see a direct path to any negative applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Section 4.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No] The dataset used in this paper is widely-used public datasets and we have provided detailed instruction for the partition about datasets.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section Jandi and Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We run the experiments multiple times and report the failure rates instead.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zotkS6iGiAd", "reviewer": "Reviewer_cdKo", "summary": "This paper considers federated learning with stochastic gradient-based algorithms being run on each local machine, where the gradients may be potentially heavy-tailed in the strong sense that only a bounded $\\alpha \\in (1, 2]$ moment assumption is placed on the random gradient norms. Since traditional analysis of SGD makes use of bounded second moments, the authors consider the general technique of norm-clipped gradients, with two variants, namely clipping at each local iteration (per-iteration, PI variant), and clipping just before integrating the parameters from all local machines to the central server (per-round, PR variant).\n\nThe main contributions are theoretical. Their main results are in the form of excess error bounds in the strongly convex case, and approximate stationarity guarantees in the non-convex case, for both the PR and PI variants. As it turns out, clipping at each local iteration turns out to be the \"better\" strategy in terms of overall dependence on the number of samples used, an intuitive result, since without controlling the gradients at each iteration in the local processes (even with finite variance), we can say very little about what we'll get from the $K$ non-clipped local updates, and thus given the resolution of the standard analytical tools, such updates are essentially wasted. The authors share some lower bounds which give some perspective on these results, and complement their theory with some empirical tests that highlight the impact of the gradient noise on the convergence rate of each procedure. The overall story has \"FedAvg\" as the standard algorithm against which performance guarantees are compared, and the final message is that the PI variant is the natural robustification of FedAvg, since it recovers the rates achieved by FedAvg in the $\\alpha = 2$ case.", "questions": "Please consider the points I raised in the previous field; if I have misconstrued the scenario considered in this paper, or misread any results, please let me know.\n\n**Update:** the authors have clarified some concerns I had, and I have revised my score.", "limitations": "Overall, the authors are clear about what they intend to prove, what they do prove, and how the learning procedures tend to be have in practice.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is well-written, the main assumptions, learning algorithm details, and key results are stated clearly, and given a concise but transparent discussion. The empirical test results, while basic, do provide a very clear example highlighting how the degree of noise makes a big difference in the PR case, whereas the PI variant is less sensitive.\n\nOn the other hand, I had some concerns about how this work compares with some of the past literature on robust stochastic gradient methods. For example:\n\n> High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails, Ashok Cutkosky and Harsh Mehta, NeurIPS 2021\n\nIn this previous work, the setting is \"centralized\" (i.e., just one machine, rather than $m >1$ clients), but the authors obtain results for the non-convex, smooth objective case with $1 < \\alpha \\leq 2$ moment bounds on the stochastic gradients. These results hold with high probability, and can be shown to hold for the last iterate. The algorithm used takes advantage of clipping, normalizing, and momentum. As such, the state of the art for the centralized, smooth, non-convex, fat-tailed gradient learning problem has high-probability guarantees without random stopping. In comparison, the current work has results in expectation with random stopping (or the unknown best candidate). There seems to be a gap here, and I wonder if it is an unnecessary gap?\n\nFor example, set $K=1$, run the C and M (2021) sub-routine to process the noisy gradients from each local machine, and then average over these $m$ robust gradient estimators and update the central server parameters as in the current FAT-Clipping-* procedures. Or, alternatively, average over the non-clipped local gradients and then run the C and M robustification procedure before updating the central parameters. This latter case seems like it is just the C and M procedure with a mini-batch, and one would expect this to yield high-probability guarantees (I have not checked this carefully).\n\nOf course, I know that in the federated learning setting we want the local machines to do the bulk of the work for us, and thus we'd like to take both $m > 1$ and $K > 1$ large; can we not modify the above robust procedure with $K=1$ to deal with the $K>1$ setting? If not, why not? The interplay between algorithmic decisions and the guarantees we can obtain are precisely the point of interest when moving from centralized to federated learning, and yet I feel these questions are sort of swept under the rug in the current analysis.\n\nBy the way, it is unclear to the reader if the error bounds in the convex case (e.g. Thm 1) are in expectation or are high-probability. \n\nTo summarize, it seems like the current paper is somewhat narrow-sighted in terms of the aggregation procedures (and the local procedures, for that matter) being considered, and state-of-the-art guarantees in the one-machine setting, which makes it somewhat difficult to evaluate the significance of this current work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "m39glngmgtx", "reviewer": "Reviewer_4F3m", "summary": "It has previously been shown that cross-device federated learning (FL) can exhibit unstable convergence and experiences a sudden catastrophic failure. The current work posits that this instability is due to fat-tailed nature of the client updates. They provide some empirical evidence for this hypothesis, and proceed to show how to combine clipping with FedAvg to derive a new algorithm which converges under such fat tailed noise.", "questions": "Since this is an emergency review for which the authors may not be able to respond in time, I will only use this space to summarize my review.\n\nOverall, this work proposes a new hypothesis of why non-iid-ness is challenging in cross-device federated learning - they claim it is due to fat tailed noise. While there is some preliminary evidence for this, the results are far from conclusive. Some of the authors' own experiments contradict this and further fat-tailed-ness does not explain other empirical phenomenon observed. Finally, there are places where both the experiments and the theory can be improved. \n\nDespite such shortcomings, the paper provides a valuable new perspective on FL and advances the conversation. I feel that these shortcomings are worth investigating by the community in future work. However, I **strongly recommend** that the authors to replicate their experiments on a few other datasets / models in the final version of their paper. I recommend acceptance trusting the authors to follow through on this.", "limitations": "No societal limitations.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. The problem of unstable convergence is an important aspect, and the hypothesis that this may be a result of fat tailed noise is mathematically sound. Such noise would indeed explain the catastrophic failure seen in federated learning.\n\n2. I very much appreciate the experiments in Section 3 (Figs. 1, 2, and 3) to establish the presence of fat tailed noise in FL. The setup is carefully thought through and indeed shows that fat tailed noise increasingly becomes a problem as heterogeneity increases. This explains why we see unstable training in non-iid setting, but not in an iid setup.\n\n3. The algorithms derived to deal with fat tailed noise FAT-CPR (where the client pseudo gradient is clipped), and FAT-CPI (where each local update is clipped) are both intuitive and shown to have strong convergence guarantees as well.\n\n4. The theory shows that FAT-CPI has a faster convergence rate than FAT-CPR. This is exactly reflected in practice as well where the former seems to perform better. Overall, FAT-CPI is a simple, intuitive algorithm which is provably more stable under fat tailed noise.\n\n## Weakness\n\nThe paper does still leave a lot of questions unanswered however.\n\n1. The estimated alpha in Fig. 2 seems to indicate that increasing the number of local steps makes the distribution less fat tailed. However, we know from experience that more local steps makes the convergence more brittle. In fact, Fig 2 seems to indicate that standard single-SGD is very fat tailed, but empirically converges without any issues. This is not discussed in the text.\n\n2. Previous work on large cohort training [Z. Charles et al. 2021] shows that the updates seem to become orthogonal as we increase number of local steps. How does that explanation fit in with the current fat-tailed explanation? More generally, there is no investigation of why such fat tailed distributions seem to arise in federated learning.\n\n3. Assumption 3 makes no distinction between the local variance within a client vs. variance across the clients due to heterogeneity. Thus, the theory is not useful to shed light on the effects on non-iid ness. Further, unlike previous work of [J. Zhang et al. 2020], the current work does not investigate adaptivity.\n\n4. Finally, the experimental results are very limited - only CIFAR 10 with a CNN is tried. It is unclear how this observation and algorithm would generalize to other settings.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h5K2sns2dcY", "reviewer": "Reviewer_ZT6s", "summary": "The authors observe that federated learning setting creates gradients that are fat-tailed and that these schemes are often marred by divergence of the training. They propose two gradient clipping schemes that aim to mitigate this, the difference being where the gradient clipping is applied. The authors present convergence results for the two algorithms. The authors compare their results with an existing algorithm on synthetic and CIFAR-10 data. ", "questions": "I presented my questions within my assessment of the paper above.", "limitations": "The authors present very little discussion of the weaknesses of their approach, which I think is not appropriate given the discussion presented above.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Distributed learning schemes present crucial avenues of development for machine learning, especially with respect to topics such as privacy and scalability. Recent research on deep learning theory demonstrated the pervasive involvement of heavy-tailed distributed parameters and/or gradient noises in determining of various aspects of deep learning models such as convergence and generalization. Extension of these results to such crucial areas is an important endeavour. The most important contribution of the paper seems to the convergence rate results they present when their algorithms are used.\n\nHowever I feel that the paper is insufficient in terms of both justifying the grounds for their methodology, as well as their effectiveness. This is also exacarbated by problems in the presentation which I will present below. The first problem is that the authors present insufficient evidence imprecisely when making a case for the existence of heavy tailed gradients in federated learning, and that these heavy-tailed gradient noise actually leads to divergence. The following questions remain unanswered or unclear in the text, which is problematic given the centrality of these matters for the article:\n\n- How is pseudo-gradient noise calculated? How is the expected value for the pseudo-gradient computed during experiments?\n- How does p relate to data heterogeneity exactly? How do we know it is a authoritative measure of data heterogeneity?\n- Does Single SGD case refer to a normal training scheme in Fig. 2? If so, in what specific ways does a federated learning scheme differ from the known results of heavy-tailed noise in the literature?\n- The authors use the divergence events as a motivation for gradient clipping. Is there a theoretical or empirical evidence to assume that the fat-tailed pseudogradient noise necessarily cause or even is statistically associated with divergence? The results on heavy-tailed parameter / gradient statistics in deep learning show that not only that this is not the case, but that heavy-tailed parameter / gradient statistics lead to better generalization.\n- The authors analyze the pseudogradient noise and find it to be heavy-tailed. Do we know the tail index statistics of the expected-pseudogradient? (which can itself be heavy-tailed.)\nSo much so that it is not clear in the text distribution of which variable they are addressing. , the authors do not explicitly specify how they compute the pseudo-gradient noise (e.g. how do they compute the expected pseudo-gradient). The experiments in Fig. 1 and 2 seem \n\nIn addition to problems in the justification of the method, the authors do not demonstrate enough empirical evidence to show that their method is superior. The experiments are very small scale - the largest experiment setting only includes 5 trials for each setting. Given the weak evidence regarding the existence and/or the effects of heavy tailed gradient noise in federated learning, extensive empirical evidence can be expected to verify that the authors' methods are viable and advantageous. Especially important is the following question:\n\n- Given the benevolent effects of heavy-tailed parameter statistics in deep learning, how do we know that the claimed advantages of the presented clipping schemes do not come with a negative effect on generalization performance?\n- Given the importance of training hyperparameters in presence or absence of heavy-tailed parameter/gradient noise, how do the authors results change with respect to hyperparameters such as learning rate or batch size?\n\nI would recommend a much more involved discussion of at least some of the questions presented above and as well as more extensive introduction to authors' terminology (e.g. the authors never explicitly state that x are their parameter vector.) The authors relegate some content to supplamentary material for lack of space: I believe a lot of space can be gained by not repeating Algorithms 2 and 3, and instead just describing the clipping operation in the text, referring to the original algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VKeEvslHVL", "reviewer": "Reviewer_Kx2k", "summary": "In this paper, the authors discussed the problems of the presence of fat-tailed noise in the stochastic gradient noise in the federated learning algorithm. The authors provided the empirical results that fat-tailed gradient noise can be induced by data heterogeneity and local update steps in the federated learning algorithm. And the fat-tailed gradient noise will lead to catastrophic training failures when applying GFedAvg algorithm. In order to fix that problem, the authors developed a clipping-based algorithmic framework called GAT-Clipping and provided the convergence rate bound of the algorithm.", "questions": "1) In the assumption the \\alpha is defined between 1 and 2. But in the experiments of Figure 5, \\alpha=0.5, which violates the assumption.\n2) In both FAT-Clipping-PR and PI, there is an extra hyperparameter \\lambda, and in the experiment part the value of \\lambda is not mentioned. How to choose a proper \\lambda value, is it related to the value of \\alpha? If so, when we start the training, \\alpha is not known, then how to choose \\lambda.\n3) The current experiments are not enough to validate the claim in the paper. Maybe providing extra experiments result can help the validation of the paper.", "limitations": "Yes, the authors adequately addressed the limitations and potential negative sociteal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper is well-written and easy to follow the idea of the paper.\n2) Related works have been fully discussed.\n3) The idea is interesting and the proof of the theorem is solid.\n\nWeakness:\n1) The experiments are not enough to verify the claim.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Rfbod8KGjYn", "reviewer": "Reviewer_tQun", "summary": "The paper considers tackling fat-tailed noise in in federated learning, where the local gradients may not even have finite covariance. It is shown that in both theory and experiments, prior approaches can fail in this setting. The paper provides a simple solution to this problem by clipping the local updates. On the theory side, they show that the algorithms achieve near optimal convergence. The paper also provides numerical experiments to validate their results.", "questions": "It seems that the algorithms require knowledge of $\\alpha$? (I noticed that $\\lambda$ and $\\eta$ settings in Theorem 1,2 both require $\\alpha$) Is that an assumption that we can get rid of? Alternatively, what would be a good heuristic to set $\\alpha$ in practice?", "limitations": "I do not see where the author(s) addressed the limitations of their work. \n\nFederated learning itself may have potential negative societal impact, but I do not consider this work particularly risky in that regard. It's mostly theoretical. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----\nThe paper is generally well-written. \n\nThe main approach of the paper is simple and can be easily implemented in practice. \n\nI have not checked the proofs in appendix, but the main theorem claims are strong, in the sense that they are optimal in $T,m$.\n\nWeaknesses\n---\nIt may be argued that the main algorithmic technique of this paper is not novel. It is mostly applying a known idea (clipping) to this problem. \n\nComparing the upper bound Theorem 1,2 and lower bound Theorem 5, the paper does not achieve optimal rate in terms of $K$, though the dependence on the more important factors of $T$ and $m$ is tight. \n\nMinor \n---\nLine 252: constructing the lower fundamental bounds -> proving the following lower bounds\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R2vooXfZ_E", "reviewer": "Reviewer_Eovh", "summary": "(I have been added as a reviewer only very late in the review process. Even though I am adding a few questions below I am fully aware that the authors cannot respond appropriately. Nevertheless, I believe these remarks might still be useful for the internal discussion an AC).\n\nThis paper studies stochastic gradient descent in a distributed/federated learning setting under the assumption that the $\\alpha$-th moment ($\\alpha \\in (1,2]$) is bounded. This generalizes standard analyzes, that typically assume bounded variance (second moment).\n\nEarlier work [22] studied SGD in a centralized setting ($m=1$ worker) under the same bounded moment assumptions. This work showed that gradient clipping allows SGD to converge, and this earlier work also showed that this approach is optimal by proving matching lower and upper bound.\n\nThe paper under review generalizes the results from [22] to a distributed setting. The main results are:\n\n(i) an asymptotic convergence analysis for two version of clipping (per-iteration or per-epoch) with local steps under the assumption that the functions on the $m$ workers are identical (homogenenous), for the strongly convex and non-convex settings. The convergence guarantee of one of the presented algorithms matches the lower bound presented in [22] and is thus optimal.\n\n(ii) the paper makes the conjecture -- which I find very interesting -- that clipping can also be used to overcome non-iid-ness when the functions on the $m$ workers are different (without resorting to variance reduction techniques such as SCAFFOLD or similar). However, this claim is only verified in one numerical experiment and the presented results are thus not yet conclusive enough to prove this claim.\n", "questions": "- it is not so evident that $c$ is constant. (The expression that $c$ must satisfy depends on parameters like $T,K$, etc.). Please show here that $c$ is indeed constant.\n\n- why does the paper introduce two algorithms (PR, PI), when apparently one is dominated by the other (at least in theory). Please make it more clear what would be the advantages of using the suboptimal algorithm in practice (or why it is included in the paper).\n\n- to get the correct dependency on $K$ for the case $\\alpha = 2$ a separate proof is needed (Theorems 6&7). One could expect to recover the result by letting $\\alpha \\to 2$, which is not the case. Is this an artefact of the proof, or is there a deeper reason that the case $\\alpha < 2$ is behaving differently?\n\n- how is the parameter $\\alpha$ estimated in Figure 2? Please explain the method.", "limitations": "Already mentioned above that limitations of theoretical results, and practical guidelines for choosing PR vs. PI could have been emphasized better.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow. In terms of originality, it seems the paper combines the clipping technique from [22] with other known analyzes for local SGD/fedAvg. It would have been nice if the paper could have pointed out the technical difficulties a bit more to explain to the reader the significance of the contribution regarding these aspects. \n\nAs mentioned above, I particular liked the discussion of the general heterogeneous setting as this seems to cover some novel aspects. Unfortunately, the evaluation fell a bit short.\n\nThe convergence results are presented from an asymptotic point of view and only hold for sufficiently large iteration counter $T$. I tried to estimate a lower bound on $T$: by the first two conditions stated in Theorem 1 on the term $\\eta \\eta_L K$, it must hold $\\frac{c \\ln T}{mK} \\geq 1$, i.e. $T \\geq e^{mK}$ when ignoring $c$. An exponential dependence on $m$ and $K$ seems very strong here, as the asymptotic regime might never be reached in practical settings where $m$ and $K$ are typically large. I was missing a discussion these limitations of the theoretical result. This strong dependence makes me doubt the practical relevance of the current theory (and might also hint that these results could probably be improved).\n\nCalling Theorem 5 a theorem seems a bit overclaimed, as the result is a direct corollary of [22]. \n\nA theoretical analysis of the heterogeneous setting would strengthen the paper considerably and would allow the contribution to be clearly distinguished from previous work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept