EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Data
Authors: Michael Crawshaw
Yajie Bao
Mingrui Liu
Venue: ICLR 2023 poster (2023)
Keywords: Non-convex optimization
federated learning
heterogeneous data
gradient clipping
relaxed smoothness

Abstract:  Gradient clipping is an important technique for deep neural networks with exploding gradients, such as recurrent neural networks. Recent studies have shown that the loss functions of these networks do not satisfy the conventional smoothness condition, but instead satisfy a relaxed smoothness condition, i.e., the Lipschitz constant of the gradient scales linearly in terms of the gradient norm. Due to this observation, several gradient clipping algorithms have been developed for nonconvex and relaxed-smooth functions. However, the existing algorithms only apply to the single-machine or multiple-machine setting with homogeneous data across machines. It remains unclear how to design provably efficient gradient clipping algorithms in the general Federated Learning (FL) setting with heterogeneous data and limited communication rounds. In this paper, we design EPISODE, the very first algorithm to solve FL problems with heterogeneous data in the nonconvex and relaxed smoothness setting. The key ingredients of the algorithm are two new techniques called \textit{episodic gradient clipping} and \textit{periodic resampled corrections}. At the beginning of each round, EPISODE resamples stochastic gradients from each client and obtains the global averaged gradient, which is used to (1) determine whether to apply gradient clipping for the entire round and (2) construct local gradient corrections for each client. Notably, our algorithm and analysis provide a unified framework for both homogeneous and heterogeneous data under any noise level of the stochastic gradient, and it achieves state-of-the-art complexity results. In particular, we prove that EPISODE can achieve linear speedup in the number of machines, and it requires significantly fewer communication rounds. Experiments on several heterogeneous datasets, including text classification and image classification, show the superior performance of EPISODE over several strong baselines in FL. The code is available at https://github.com/MingruiLiu-ML-Lab/episode.

Published as a conference paper at ICLR 2023
EPISODIC GRADIENT CLIPPING WITH PE- RIODIC RESAMPLED CORRECTIONS FOR FEDERATED LEARNING WITH HETEROGENEOUS DATA
EPISODE:
Michael Crawshaw', Yajie Bao", Mingrui Liu
1 DDeaarmeent of Computer Science, George Mason University, Fairfax, VA 22030, USA 2 School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, China baoyajie201 9statêsjtu edu.en, en, mingrui 1 gmu. edu
mcrawsha@
ABSTRACT
Gradient clipping an important technique for deep neural networks with explod- ing gradients, such as recurrent neural networks. Recent studies have shown that the loss functions these networks do not satisfy the conventional smoothness condition, but instead satisfy relaxed smoothness condition, i.e., the Lipschitz constant of the gradient scales linearly in terms of the gradient norm. Due to this observation, several gradient clipping algorithms have been developed for noncon- vex and staxeedsmmooth functions. However, the existing algorithms only apply to the single-maching or caatipleemaching setting with homogeneous data across machines. remains unclear how to design provably efficient gradient clipping algorithms the general Federated Learning (FL) setting with heterogeneous data and limited communication rounds. In this paper, we design EPISODE, the very first algorithm to solve FL problems with heterogeneous data in the nonconvex and relaxed smoothness setting. The key ingredients of the algorithm are two new tech- niques called episodic gradient clipping and periodic resampled corrections. beginning of each round, EPISODE resamples stochastic gradients from each client and obtains the global averaged gradient, which is used to (1) determine whether to apply gradient clipping for the entire round and (2) construct local gradient corrections for each client. Notably, our algorithm and analysis provide a unified framework for both homogeneous and heterogeneous data under any noise level of the stochastic gradient. and it achieves state-of-ie oftt--o-thheart the-art complexity results. In partic- ular, we prove that EPISODE achieve linear speedup in the number of machines, and it requires significantly fewer communication rounds. Experiments on several heterogeneous datasets, including text classification and image classification, show the superior performance of EPISODE over several strong baselines in FL. The code is available //ttps:://gg thubb www.
the
wttp:/hhwww.coooiigggiiiiiiitiia ML- Labil-Labeeee ep isode
INTRODUCTION
Gradient clipping (Pascanu et al. 2012 2013) is well-known strategy to improve the training of deep
neural networks with the exploding gradient issue such as Recurrent Neural Networks (RNN) (Rumel:
hart et al. 1986; Elman 1990 Werbos 1988) and Long Short-Term Memory (LSTM) (Hochreiter & Schmidhuber 1997). Although it is a widely-used strategy, formally analyzing gradient clipping in
deep neural networks under the framework of nonconvex optimization only happened recently (Zhang
let al. 2019a 2020a Curkosky& & Mehta 202T] Liu et al., 2022). In particular, /Zhang et al. (2019a) showed empirically that the gradient Lipschitz constant scales linearly in terms of the gradient norm when training certain neural networks such as AWD-LSTM (Merity et al.) 2018), introduced the relaxed smoothness condition (i.e., (Lo, L1)-smoothnes, p. and proved that clipped gradient descent converges faster than any fixed step size gradient descent. Later on, Zhang et al. (2020a) provided
tighter complexity bounds of the gradient clipping algorithm.
Federated Learning (FL) (McMahan et al. 2017a) is an important distributed learning paradigm in which a single model trained collaboratively under the coordination of a central server without revealing client data FL has two critical features: heterogeneous data and limited communication.
"Corresoondig Author: Mingrui Liu (mi (mingrui @gmu. edu).
'The formal definition of (To, L1) smosshnossssss is illustrated in Definition 2 In this paper, we the terms "elient" and "machine" interchangeably.

---

Published as a conference paper at ICLR 2023
Table 1: Communication complexity (R) and largest number of skipped communication (mmax) to guarantee linear speedup for different methods to find an e-stationary point (defined in Definition D "Single" means single machine, N is the number of clients, is the number of skipped commu- nications, K is the quantity representing the heterogeneity. A f (xa) min f(x), and a² is the variance of stochastic gradients. Iteration complexity (7) is the product of communication complexity and the number of skipped communications (i.e.. T = R/) ). Best iteration complexity Tmin denotes the minimum value of T the algorithm can achieve through adjusting I. Linear speedup means the iteration complexity is divided by N compared with the single machine bascline: in our case it means
= O ALae" Ne
iteration complexity.
Method
Sctting
Communication Complexity (R)
Best lieration Complexity (Tata)
Largest guarantee lincar speedup (Jaas)
Local SGDD
Heterogeneous,
A6X)
et 2019c
I-smooth
Heterogeneoss,
O Atap'
Karrmireddyy ot al 2020
I--smroch
Clippel S0l
Singk, (Nay lu -smoohh
/hang el al. 20156
N/A
Clutin Flansowurk
Zlung 2020u
(1o, I-mmotth
Singk,
N/A
[Luuetal 3022
CELCC
(Lo, Li Hsmouth
Homogencous.
O
< (x+)
EPISODE
Heterogeneous
A (1+9)
O ((Aeer")
(this work)
(Ls. L.,,i)) Li)-shooth
Although there is a vast literature on FL (see (Kairouz et al. 2019) and references therein). the theoretical and algorithmic understanding of gradient clipping algorithms for training deep neural networks in the Fl. setting remains nascent. To the best of our knowledge, [iu et al. (2022) is the only work that has considered a communication--ffiiiee distributed gradient clipping algorithm under the nonconvex and relaxed smoothness conditions in the FL setting. In particular, Liu et al. (2022) proved that their algorithm achieves linear speedup in terms of the number of clietts and reduced communication rounds. Nevertheless, their algorithm and analysis are only applicable to the case of homogeneous data. In addition. the analyses of the stochastic gradient clipping algorithms
in both single machine (Zhang et al. (2200a) and multiple-machine setting (Liu et al., (022) require strong distributional assumptions on the stochastic gradient noise which may not hold in practice.
In this work, we introduce provably computation and communication efficient gradient clipping algorithm for nonconvex and relaxed-smoot functions in the general FL setting (i.e., heterogeneous the stochastic gradient noise. Compared with previous work on gradient clipping (Zhang et al. 2019a 2020a
data, limited communication) and without any distributional assumptions
Cutkosky & Mehtal 2020 Liu et al. 2022) and FL with heterogeneous data (Li et al. 2020a
Karimireddy et al.] 2020), our algorithm design relies on two novel techniques: episodic gradiens clipping and periodic resampled corrections. In nutshell, at the beginning of each communication round, the algorithm resamples each client's 's stochastic gradient; this information is used to decide whether to apply clipping in the current round (i.c., episodic gradient clipping). and perform local corrections to each client's update (i.c., periodic resampled corrections). These techniques are very different compared with previous work on gradient clipping. Specifically, (1) In traditional
gradient clipping (Pascanu et al. 2012: Zhang et al.) 2019a; 2020a| Liu et al. [2022), whether or not to apply the clipping operation is determined only by the norm of the client's current stochastic gradient. Instead, we use the norm of the global objective's 's stochastic gradient (resampled at the
beginning of the round) to determine whether or not clipping will be applied throughout the entire communication round. (2) Different from Karimireddy et al. (2020) which uses historical gradient information from the previous round to perform corrections, our algorithm utilizes the resampled gradient to correct each client's local update towards the global gradient, which mitigates the effect of data heterogeneity. Notice that, under the relaxed smoothness setting, the gradient may change quickly around point at which the gradient norm is large. Therefore, our algorithm treats a small gradient as more "reliable" and confidently applies the unclipped corrected local updates; on the contrary, the algorithm regards large gradient as less "reliable" and in this case clips the corrected local updates. Our major contributions are summarized as follows.
Zhang al. 2020a requires explicit lower hound for the stochastic gradient noise, and Liu et al. requires the distribution of the stochastic gradient noise unimodal and symmetric around its mean.
2022
2

---

Published as a conference paper at ICLR 2023
We introduce EPISODE, the very first algorithm for optimizing nonconvex and (Lo, L1)- smooth functions in the general FL setting with heterogeneous data and limited communica- tion. The algorithm design introduces novel techniques, including episodic gradient clipping and periodic resampled corrections. To the best of our knowledge, these techniques are first introduced by us and erucial for algorithm design.
Under the nonconvex and relaxed smoothness condition, we prove that the EPISODE algorithm can achieve linear speedup in the number of clients and reduced communication rounds in the heterogeneous data setting, without any distributional assumptions the stochastic gradient noise. In addition, we show that the degenerate case of EPISODE matches state-of-the- -ortte--tttt-ttteee complexity results under weaker assumptions + Detailed complexity results and a comparison with other relevant algorithms are shown in Table
We conduct experiments on several heterogeneous medium and large scale datasets with different deep neural network architectures, including a synthetic objective, text classifica- tion, and image classification. We show that the performance of the EPISODE algorithm is consistent with our theory, and it consistently outperforms several strong baselines in FL.
2 RELATED WORK
Gradient Clipping Gradient clipping is a standard technique in the optimization literature for
solving convex/quasiconvex problems (Ermoliev) [988] Nesterov 1984 Shor 2012: Hazan et al.
2015 Mai & Johansson 202T; Gorbunov et al.] (020). nonconvex smooth problems (Levy) 2016
Cutkosky & Mehta 2021), and nonconvex distributionally robust optimization (Jin al. 2021)
Menon et al. (2019) showed that gradient clipping can help mitigate label noise. Gradient c clipping is
well-known strategy to achieve differential privacy (Abadi et al. 2016 McMahan al. 2017b]
Andrew et al. Zhang et al. 202T). In the deep learning literature, gradient clipping is employed to avoid exploding gradient issue when training certain deep neural networks such as recurrent
neural networks or long-short term memory networks (Pascanu et al. [012] (013) and language
models (Gehring et al. 2017 Peters et al.) 2018: MMrrty et al.] | 2018). /hang et al. (2019a) initiated the study of gradient clipping for nonconvex and relaxed smooth functions. [Zhang et al. (2020a)
provided an improved analysis over Over/hhagg et al. (2099a). However, none of these works apply to the general FL setting with nonconvex and relaxed smooth functions.
Federated Learning FL was proposed by McMahan et al. (2017a), a. to enable large-scale distributed learning while keep client data decentralized to protect user privacy. McMahan et al. (2017a) designed
the FedAvg algorithm, which allows multiple steps of gradient updates before communication. This
algorithm is also known as local SGD (Stich) 2018 [in al.) [018 WWang & Joshi 2018 Yu et al.
2019c). The local SGD algorithm and their variants have been analyzed in the convex setting (Stich 2018 Stich et al. 2018 Dieuleveut & Patel 2019: Khaled et al. 2020) Li et al. 2020aa] Karimireddy
et al. 2020; Woodworth et al.) 22020a b Koloskova et al. 2020 Yuan et al.) (021) 1) and nonconvex
smooth setting (Jiang & Agrawal 2018
Wang & Joshi 2018 Lin et al., 2018 Basu et al. [2019]
Haddadpour et al. 2019: Yu et al. 2019c bt Li et al.) [020a] Karimireddy et al. 2020 Reddi et al.
|021| et al., 2020b; Koloskova et al. 2020). Recently, the stochastic convex optimization
setting, several works compared local SGD and minibatch SGD in the homogeneous (Woodworth cct al. 2020b) and heterogencous data setting [Woodworth et al./ (2020a), as well as the fundamental limit (Woodworth et al. 2021). For comprehensive survey, we refer the readers to Kairouz et al. (2019); Li et al. (2020a) and references therein. The most relevant work to ours is Liu et al. (2022), which introduced communication-effcienn distributed gradient clipping algorithm for nonconvex and relaxed smooth functions. However, their algorithm and analysis does not apply in the case of heterogeneous data as considered in this paper.
3 PROBLEM SETUP AND PRELIMINARIES
Notations In this paper, we use (:::) and || to denote the inner product and Euclidean norm in space Rdd. We use 1(-) to denote the indicator function. We let I, be the set of iterations the r-th
"We prove that the degenerate case of our analysis (e.g.. homogeneous data) achieves the same iteration and communication complexity, but without the requirement of unimodal and symmetric stochastic gradient noise as in [iu et al. (2022). Also, our analysis is unified over any noise level of stochastic gradient, which does not require explicit lower hound for the stochastic gradient noise as in the analysis of Zhang et al. (2020a).
3

---

Published as a conference paper at ICLR 2023
round, that is I, [f,,,... tr+1 - 1}. The filtration generated by the random variables before step f, is denoted by Fy. We also use [. to denote the conditional expectation E|- The number of clients is denoted by N and the length of the communication interval is denoted by I, ie.,, [I,| I for r = 0, ,..,, R. Let fix) == [F, {i) be the loss function in i-th client for E [N], where the local distribution D; is unknown and may be different across i [N]. In the FL. setting, we aim to minimize the following overall averaged loss function:
N
f(x) = Σ M()).
We focus on the case that each fi is non-convex, in which it is NP-hard to find the global minimum of f. Instead we consider finding an e-stationary point (Ghadimi Lan 2013: Zhang et al., 2020a).
Definition 1. For a function h : R - R. a point z E Rd called c-stationary if V[(x))) S
Most existing works in the non-convex FL literature Yu et al. 2019a Karimireddy et al. 2020)
assume each Si is L-smooth, i.e., [I (ty)l S L x y for any x; y E R. However is shown in Zhang et al. (2019a) that L-smoothness may not hold for certain neural networks such as
RNNs and LSTMs. (Lo, L1 -smoothness in Definition was proposed by Zhang et al. (2019b) and is strictly weaker than L-smoothness. Under this condition, the local smoothness of the objective can grow with the gradient scale. For AWD-LSTM (Merity et al. 2018), empirical evidence of (Lo, Immoooothss was observed in Zhang et al. (019b)).
Definition 2. A second order differentiable Lo + [=]]]( holds for any x E Rdd
h h R + IR is (Lo, smmoohh if V S
Suppose we only have access to the stochastic gradient (.; {) for & ~ D, in each client. Next make the following assumptions on objectives and stochastic gradients.
Assumption 1. Assume Ss for i [N] and defined in 7 satisfy:
(i) fo is second order differentiable and (Lo, smo-thh
(ii) Let x² be the global minimum of f and zu be the initial point. There exists some A 0 such that [(xr)) f(x"' S.
(iil) For all x E Rd. there exists some a 2 such that Eg,DD, (VL.D, (x; = fi(zz) and [V &t) - (z)))) < almost surely.
(iv) There exists some 2 0 and p 2 1 such that [V][(=)]] S K pl V for any RRd.
Remark: (i) and (ii) are standard in the non-convex optimization literature (Ghadimi & Lan 2013 3). and (iii) is a standard assumption in the (Lo, -mmoohhessss setting (Zhang al. 201 2020a Liu et al. 2022). (iv) is used to bound the difference between the gradient of each client's 's local loss and the gradient of the overall loss. which commonly assumed in the FL literature with heterogeneous data (Karimireddy et al. 2020). When & 0 and p = 1, (iv) corresponds to the homogeneous setting.
4
ALGORITHM AND ANALYSIS
4.1 MAIN CHALLENGES AND ALGORITHM DESIGN
Main Challenges We first illustrate why the prior local gradient clipping algorithm (Liu et al. 2022) would not work in the heterogeneous data setting. Liu al. (2022) proposed the first communication efficient local gradient clipping algorithm (CELGC) in a homogeneous setting for relaxed smooth functions, which can be interpreted as the clipping version of FedAvg. Let us consider a simple heterogeneous example with two clients in which CELGG fails. Denote fx) = 1_²² + aiæ and 1. We know that the optimal solution toz = -1. and both fi and f2 are (Lo, -smoohh with Lo = 1 and
fa(=) = 1222 + 02r with a1 -- 1, 02 = 7 + 2. and for f futf2 is x. = 2
L = O. Consider CELGC with communication interval / - 1 (i.e., communication happens at every iteration). starting point Zn = 0. 17- = 1/LLo = 1, clipping threshold y, and a = O. In this setting, after the first iteration, the model parameters on the two clients become 7 and -y respectively, averaged model parameter after communication returns to O. This means that the model parameter of CEL GC remains stuck at O indefinitely, demonstrating that CELGC cannot handle data heterogeneity.
that the
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Episodic Gradient Clipping with Periodic Resampled Corrections (EPISODE)
1: Initialize zij - Lo. To <
2o-
2: for r = 0. 1.... .... R do
3: for E [N] do
4: Sample (zrr where E.. D;, and update G (.(
5: end for
6: Update G, = E== G
7: for E [N] do
8: for by...., tr+1 do
9:
Sample (ii(
Et), where E D: and compute g VF((//)))) - G. + G..
10: si+1 + x ng! 1 (I) S 2/n) 7
zi Tist [[ 2 7/1).
11: end for
12:
end for
Update + # Ei=1 oi,
14:
end for
We then explain why the stochastic controlled averaging method (SCAFFOLD) (Karimireddy et al. 2020) for heterogeneous data does not work in the relaxed smoothness setting. SCAFFOLD utilizes the client gradients from the previous round to constructing correction terms which are added to each client's local update. Crucially, SCAFFOLD D requires that the gradient Lipschitz so that gradients from the previous round are good approximations of gradients in the current round with controllable errors. This technique is not applicable in the relaxed smoothness setting: the gradient may change dramatically, so historical gradients from the previous round are not good approximations of the current gradients anymore due to potential unbounded errors.
Algorithm Design To address the challenges brought by heterogeneity and relaxed smoothness, our idea to clip the local updates similarly as we would clip the global gradient (if we could access it). The detailed description of EPISODE is stated in Algorithm [ Specifically, we introduce two novel techniques: (1) Episodic gradient clipping. At the r-th round, EPISODE constructs a global indicator [I] S //m) to determine whether to perform clipping in every local update during the round for all clients (line 6). (2) Periodic resampled corrections. EPISODE resamples fresh gradients with constant batch size the beginning of each round (line 3-5). In particular, at the beginning of the r-th round, EPISODE samples stochastic gradients evaluated at the current averaged global weight E, in all clients construct the control variate G,,, which has two roles. The first is to construct the global clipping indicator according to ||Gr|| (line 10). The second one is to correct the bias between local gradient and global gradient through the variate o in local updates (line 10).
4.2 MAIN RESULTS
Theorem 1. Suppose Assumption holds. For any tolerance S
3ALa 5BLiP' choose the hyper
parameters as 17 I min 216T1: 180r1a: 16Algg } and (110+ ALo BL,p) T, where I = ALo +
Ne²
BLa + BTap (o 2)- Then EPISODE satisfies T++1 2r=0 [[V](( < 3e as long as the
number of communication rounds satisfies R Z
4A 2nd
Remark 1: The result in Theorem holds for arbitrary noise level, while the complexity bounds in the stochastic case of Zhang et al. (2020a); Liu et al. (2022) both require o > 1. In addition, this theorem automatically recover the complexity results in Liu et al. (2022). ) but does not require their symmetric and unimodal noise assumption. The improvement upon previous work comes from better algorithm design, well discrepancy in the non-clipped case (see Lemma a.d
careful analysis in the smoothness and individual
Remark 2: In Theorem when we choose " min 21617 1801T0' 16A
No² }. the total
communication complexity to find an e-stationary point no more than
O AlLuthy(nto) (1 2) + Aboa? NTct Next we present some implications of the communication
complexity.
5

---

Published as a conference paper at ICLR 2023
1. When I x (Loth)(tta)ne O( (A In this case, EPISODE enjoys a better communication complexity than the naive parallel version of the algorithm in Zhang al. (2000a), that is O( (Aae"") Moreover, the iteration complexity of EPISODE is T = RI O A Ne which achieves the linear
Lgo
and Z c, EPISODE has communication complexity
Ne
speedup w.r.t. the number of clients N. This matches the result Lf et al. (022)) in the homogeneous data setting.
2. When I 2 [Lo+Likto))N and 2 the communication complexity of EPISODE is
Log
O( (0A(To A This term does not appear in Theorem III of Karimireddy et al. 2020 but it appears here due to the difference in the construction of the control varrates. In fact, the communication complexity of EPISODE is still lower than the naive parallel version of Zhang et al. (2020a) if the number of clients satisfies N - (LotLi
Loo
3. When < a S e, EPISODE has communication complexity O( At this particular noise level, the algorithms in Zhang et al. (2020a); Liu et al. (2022) do not guarantee convergence because their analyses crucially rely on the fact that or 2 c.
Under
4. When = 0, EPISODE has communication complexity O ((A(lot))x)) This bound includes an additional constant L compared with the complexity results in the deter- ministic case (Zhang et al. 2020a), which comes from data heterogeneity and infrequent communication.
4.3 PROOF SKETCH OF THEOREM
Despite recent work on gradient clipping in the homogeneous setting (Liu et al., 2022). the analysis
of Theorem [ simultaneously. In addition, we do not require lower bound of a and allow for arbitrary 2 0.
is highly nontrivial since we need to cope with (Lo, L1) -smoothness and heterogeneity
The first step is establish the descent inequality of the global loss function. According to the (Lo, smooshhessssss condition, if ||ē,+1 E. s C/L1, then
E, 1f - f(ā,)] S E, ((1(4) + 1 (A,)) (V (x, 3,+1 mr)] + E, (1(44) ( (AA)) ALo + BL, VV (a,))
|8, 11-11-0p1 1.,113
(2)
where A. == [|| S 7/n). Ar. is the complement of A,, and A, B, C are constants defined in Lemma 5 To utilize the inequality ( we need to verify that the distance between 3r44 and &. is small almost surely. In the algorithm Liu et al. 2002), clipping is performed in each iteration based the magnitude of the current stochastic gradient, and hence the increment of each local weight is bounded by the clipping threshold y. For each client in EPISODE, whether to perform clipping is decided by the magnitude of G, at the beginning of each round. Therefore, the techniques in Liu et al. (2022) to bound the individual discrepancy cannot be applied to EPISODE. To address this issue, we introduce Lemma []] which guarantees that we can apply the properties of relaxed smoothness (Lemma and 6 to all iterations in one round, in either case of clipping or non-clipping.
and
Lemma 1. Suppose (AL + BL1K + BLip(o + +7/n)) S 1 and max (2mI(20 + y/n), 71} < C. Then for any i [N] and E I,, it almost surely holds that
(AA))ll= ã, < 2mp (2o + r/n) and 1(A,)lxx) 2, 7I.
2, Equipped with Lemmal the condition - 1
+ || t. - x, S C/L, can hold
almost surely with a proper choice of 17. Then it suffices to bound the terms from (2) in expectation under the events A, and A, respectively. To deal with the discrepancy term E[ 2, [I'] for 1-1 E I,, Liu et al. (2022) directly uses the almost sure bound for both cases of clipping and non-clipping. Here aim to obtain more delicate bound in expectation for the non-clipping case. The following lemma, which is critical to obtain the unified bound from Theorem [ under any noise level, gives an upper bound for the local smoothness of fi at x.
Lemma 2. Under the conditions of Lemmal 1 for all x E Rdd such that ||æ: - x. S 2np (2a + *//n), the following inequality almost surely holds:
2 Lo La (1S (p (2/n++2)))

---

Published as a conference paper at ICLR 2023
From we can see that all iterations in the r-th round satisfy the condition of Lemma 2 2 almost surely. Hence we are guaranteed that each local loss f: is L-smooth over the iterations in this round under the event A,, where L Lo + Li (N + (p + 1)(/// + 20)). In light of this, the following lemma gives a bound in expectation of the individual discrepancy. We denote pr = E, (..(((())) (Ar)).
Lemma 3. Under the conditions of Lemma [ for any i [M] and - 1 In. we have
[1-] < 36p, 12-1" (V/ )|2 121) E,, [1 -e,
(4)
Er, [1 3. 11 - 18p, 18p, VV (t,)) + 12, (70/ /1 + 50²2.
(5)
is worthwhile noting that the bound in (4) involves quadratic term of [ whereas is linear in (5) The role of the linear bound is to deal with [[A)))l] | 12, from the descent inequality (2). since directly substituting (4) would result in a cubic term which is hard to
analyze. With Lemma I and 3
we obtain the following descent inequality.
Lemma 4. Under the conditions of Lemma
ler r ALo + BIa (N + p(7/1) + a)). Then it holds
that for each O S r 1,
By ([(r++)) - [(x,) S B, (1(A, + [A,))U
(6)
where the definitions of (ā.r) and ( are given in Appendix
The detailed proof of Lemma is deferred in Appendix C.I With this Lemma, the descent inequality divided into (zz)) (objective value decrease during the non-clipping rounds) and (æ,) (objective value decrease during the clipping rounds). Plugging in the choices of 17 and y yields
1
max (U(E,, (( s [ En.
(7)
4
The conclusion of Theorem can then be obtained by substituting 7 into (6) and summing over r.
5 EXPERIMENTS
In this section, we present an empirical evaluation of EPISODE validate our theory. We present results in the heterogeneous FL setting on three diverse tasks: a synthetic optimization problem satisfying (Lo, L1 smoothhssssss natural language inference on the SNLI dataset (Bowman al. 2015). and ImageNet classification (Deng et al. (2009). We compare EPISODE against FedAvg (McMahan et al.) 70) SCAFFOLD (Karimireddy et al. 2020 CELGC (Liu al. 2022). and naive distributed algorithm which we refer to as Naive Parallel Clip 5 We include additional
experiments on the CIFAR- 10 dataset (Krizhevsky et al. 2009) in Appendix E.44 running time results in Appendix [ ablation study in Appendix G and new experiments on federated learning benchmark datasets in Appendix
5.1 SETUP
All non-synthetic experiments were implemented with PyTorc (Paszke et al. 2019) and run on a cluster with eight NVIDIA Tesla V100 GPUs Since SNLI, CIFAR-IO, 10, and ImageNet are centralized datasets, we follow the non-i.i.d. partitioning protocol in (Karimireddy et al. (2020) to split each dataset into heterogeneous client datasets with varying label distributions. Specifically, for a similarity parameter E [0. 100), each client's 's local dataset is composed of two parts. The first s% is comprised of i.i.d. samples from the complete dataset, and the remaining (100- s)% of data sorted by label.
Synthetic To demonstrate the behavior of EPISODE and basclines under (Lo, L1 smoothnssss we consider a simple minimization problem
single variable. Here we have N = 2 clients with:
fx( z - 3x + H +x, fa(x) zd - 3x 2H + x,
where the parameter H controls the heterogeneity between the two clients. Notice that fi and f2 satisfy (Lo, L1) smoothness but not traditional L-smoothness.
Proposition 1. For any E R and i = 1,2, 2, it holds that [[V](())] < 2|V + *(H), where <(H)= < 3o and is positive increasing function of H for H 2.
According to Proposition Assumption Tiv) will be satisfied with p = and k = (H), where x(H) is an increasing function of H. The proof of this proposition is deferred to Appendix E.
Naive Parallel Clip uses the globally averaged stochastic gradient obtained from synchronization every iteration to run SGD with gradient clipping the global objective.
7

---

Published as a conference paper at ICLR 2023
0.7
08
06-
Train loos
Thiin Joes
Tran kos
0.35
2500
044
0.3
0.3-
20
25
s000
todon
195m
24000
10
19
20
25
Epoch
Round
Epoch
0.94
0..6
Toa accuss))
0.50
Test accuracy
0.50
Text accnree
0.78-
8:78
CELoGs
0.76
0.76
Saaee Plp
10
15
20
25
5000
10000
15000
200000
25000
16
19
20
25
Epoch
Round
Epoch
(a) Effect (Epochs)
(b) Fffect (Rounds)
(c) Effect of (Epochs)
Figure 1: Training loss and testing accuracy SNLI. The style of each curve (solid, dashed, dotted) corresponds to the algorithm, while the color corresponds to either the communication interval / (for (a) and (b)) or the client data similarity (for (c)). (a), (b) Effect of varying I with 30%, plotted against (a) epochs and (b) communication rounds. (c) Effect of varying with 4.
SNLI Following Conneau al. (2017) we train BiRNN network for 25 epochs using the multi- class hinge loss and batch size of 64 on each worker. The network is composed of one layer BiRNN encoder with hidden size 2048 and max pooling, and a three-layer fully connected classifier with hidden size 512. The BiRNN encodes sentence (represented as sequence of GloVe vectors (Pennington et al. 2014)), and the classifier predicts the relationship two encoded sentences as either entailment, neutral, contradiction. For more hyperparameter information, Appendix E.3
To determine the effects of infrequent communication and data heterogeneity on the performance of each algorithm, vary I E {2, 4, 8, 16) and E {10%, 30%, 50%). We compare EPISODE. CELGC, and the Naive Parallel Clip. Note that the training process diverged when using SCAFFOLD, likely due gradient explosion issue, since SCAFFOLD does not gradient clipping.
ImageNet Following Goyal et al. (2017). we train a ResNet-50 (He et al. 2016) for 90 epochs using the cross-entropy loss, batch size of 32 for each worker, clipping parameter ? 1.0, momentum with coefficient 0.9, and weight decay with coefficient 5 x 10 We initially set the learning rate 7 0.1 and decay by a factor of 0.1 at epochs 30, 60, and 80. analyze the effect of data heterogeneity in this setting, we fix = 64 and vary 8 E (50%, 60%, 70%). Similarly, to analyze effect of infrequent communication, we fix s = 60% and vary I (64, 128). We compare the performance of FedAvg, CELGC, EPISODE, and SCAFFOLD.
5.2 RESULTS
Synthetic Figure 3 Appendix E.2 shows the objective value throughout training, where the heterogeneity parameter H varies over {1, 4, 4). CELGC exhibits very slow optimization due to the heterogeneity across clients: as H increases, the optimization progress becomes slower and slower. In contrast, EPISODE maintains fast convergence as H varies. We can also see that EPISODE converges to the minimum of global loss, while CELGC fails do so when larger.
SNLI Results for the SNLI dataset shown in Figure I To demonstrate the effect of infrequent communication. Figures [(a] and shbw results for EPISODE, CELGC, and Naive Parallel Clip the communication interval varies (with fixed 30%). After 25 epochs, the test accuracy
8

---

Published as a conference paper at ICLR 2023
Interval
Similarity
Algorithm
Train loss
Test acc.
64
70%
FedAvg
1,010
74.89%
1,00
CELGC
1.016
74.89%
Thin Loss
20-
0.95
SCAFFOLD
1.024
74.92%
0.90
EPISODE
0.964
75.20%
64
60%
FedAvg
0.990
74.73%
CELGC
0.979
74.51%
SCAFFOLD
0.983
74.68%
40
50
EPISODE
0.945
74.95%
Eiech
0.80
64
50%
FedAvg
0.955
74.53%
075
CELGC
0.951
74.12%
0.75
SCAFFOLD
0.959
74.19%
Accunay
0.5
0.74
EPISODE
0.916
74.81%
0.0
128
60%
FedAvg
1.071
74.15%
0.5
CELGC 1.034
74.24%
CELGC
SCAFFOLI
SCAFFOLD 1.071
74.03%
045
BPSSDDE
EPISODE 1.016
74.36%
040
40
Epoch
Figure 2: ImageNet results. Left: Training loss and testing accuracy the end of training for various settings of and 8. EPISODE consistently reaches better final metrics in all settings. Right: Training loss and testing accuracy during training for I 64 and
50%.
of EPISODE nearly matches that of Naive Parallel Clip for all I < 8, while CELGC lags 2-3% behind Naive Parallel Clip for all values of I. Also, EPISODE nearly matches the test accuracy of Naive Parallel Clip with little times fewer communication rounds. Lastly, EPISODE requires significantly less communication rounds to reach the same training loss as CELGC. For example, EPISODE with 7 4, 30% takes less than 5000 rounds to reach training loss of 0.4, while CELGC does not reach 0.4 during the entirety of training with any I.
To demonstrate the effect of client data heterogeneity, Figure [(e] shows results for varying values of 8 (with fixed / -= =4). 4). Here we can see that EPISODE resilient against data heterogeneity: even with client similarity as low as s = 10%. the performance of EPISODE the same Also, the testing accuracy of EPISODE with = 10% is nearly identical to that of the Naive Parallel Clip. On the other hand, the performance of CELGC drastically worsens with more heterogeneity: even with = 50%, the training loss of CELGC is significantly worse than EPISODE with s 10%.
50%.
ImageNet Figure shows the performance of each algorithm at the end of training for all settings (left) and during training for the setting I = 64 and s = 50% (right). Training curves for the rest of the settings are given in Appendix E.5 EPISODE outperforms all baselines in every experimental setting, especially in the case of high data heterogeneity. EPISODE particularly dominant over other methods in terms of the training loss during the whole training process, which is consistent with our theory. Also, EPISODE exhibits more resilience to data heterogeneity than CELGC and SCAFFOLD: the client data similarity deceases from 70% to 50%, the accuracies of CELGC and SCAFFOLD decrease by 0.8% and 0.7%, respectively, while the test accuracy of EPISODE decreases by 0.4%. Lastly, as communication becomes more infrequent (i.e., the communication interval I increases from 64 to 128), the performance of EPISODE remains superior to the basclines.
CONCLUSION
We have presented EPISODE, a new communication efficcii distributed gradient clipping algorithm for federated learning with heterogeneous data in the nonconvex and relaxed smoothness setting. have proved convergence results under any noise level of the stochastic gradient. In particular, we have established linear speedup results well reduced communication complexity. Further, our experiments on both synthetic and real-world data show demonstrate the superior performance of EPISODE compared to competitive baselines in FL. Our algorithm is suitable for the cross-silo federated learning setting such as in healthcare and financial domains (Kairouz et al. 2019), and we plan to consider cross-device setting in the future.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like to thank the anonymous reviewers for their helpful comments. Michael Crawshaw is supported by the Institute for Digital Innovation fellowship from George Mason University. Michael Crawshaw and Mingrui Liu are both supported by a grant from George Mason University. The work of Yajie Bao was done when he was virtually visiting Mingrui Liu's 's research group in the Department of Computer Science at George Mason University.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455- 17466, 2021.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pp.
2019.
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguisties. 2015.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf': benchmark for federated settings. arXiv preprint arXiv:1812.00000
2018.
A Conneau, D) Kiela, H Schwenk, I. Barrault, and A Bordes. Supervised learning of universal sentence representations from natural language inference data. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 670-680. Association for Computational Linguistics, 2017.
Ashok Cutkosky and Harsh Mchta. Momentum improves normalized sgd. In International Conference on Machine Learning. pp. 2260-2268. PMLR, 2020.
Ashok Cutkosky and Harsh Mehta. probabbbbybilityy bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Ieee, 2009.
Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-off's for local-sgd with large step size. Advances in Neural Information Processing Systems, 32:13601-13612, 2019.
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):19-221, 1990.
Yuri Ermoliev. Stochastic quasigradient methods. numerical techniques for stochastic optimization. Springer Series in Computational Mathematics, (10):141-185) 1988.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International Conference on Machine Learning, pp. 1243-1252. PMLR, 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (220)2331-22363 2013.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. arXiv preprint arXiv:2005. 10785, 2020.
10

---

Published as a conference paper at ICLR 2023
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv: 0eee1176.0000000 02677, 2017.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 10800-10922 2019.
Elad Hazan, Kfrr Y Levy, and Shai Shalev-Shwarde Beyond convexity: Stochastic quasi-convex optimization. arXiv preprint vrXiv:1507.020300 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1997.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. Advances in Neural Information Processing Systems, pp. 2525-2533 2018.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782 2021.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. arXiv preprint 1rXiv:1912.04990 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-51433 PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5399 PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Kfrr Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint 1rXiv:661.008.. 2016.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a.
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 450, 2020b.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv: FrrXiv1188..000 1808.072 2018.
Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication--ffiiienn distributed gradient clipping algorithm for training deep neural networks. arXiv preprint arXiv:2205.05044 2022.
Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. arXiv preprint arXiv: 102. 062.9648, 2021.
11

---

Published as a conference paper at ICLR 2023
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, al. Communication--cffcienn learning of deep networks from decentralized data. AISTATS, 2017a.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:/710.0000 06667, 2017b.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Can gradient clipping mitigate label noise? In International Conference on Learning Representations, 2019.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations, 2018.
Yurii Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29:519-531, 1984.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. corr abs/1211.5063 (2012). arXiv preprint arXivv 2012.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning. pp. 1310-1318. PMLR, 2013.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations, arXiv preprint arXiv: 1802.05355 2018.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by hack-propagating errors. nature, 323(6088):533-536, 1986.
Naum Zuselevich Shor. Minimization methods for non-differeniaallefuntiee volume 3. Springer Science & Business Media, 2012.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.0976) 2018.
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-efficieett sgd algorithms. arXiv preprint 1rXXiv/8088.00 2018.
Paul Werbos. Generalization of backpropagation with application to recurrent gas market model. Neural networks, 1(4):339-356, 1988.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning, arXiv preprint Stt::200000473333 2020a.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan. Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference Machine Learning, pp. 10334-10343. PMLR, 2020b.
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. arXiv preprint 102.0:20 2021.
12

---

Published as a conference paper at ICLR 2023
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint Mwxivv1905.03880 2019a.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, pp.
7184-7193, 2019b.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019c.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference Machine Learning, pp. 12253 12266. PMLR, 2021.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. arXiv preprint arXiv:2010.02519, 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. arXiv preprint arXiv: 1905. 1881, 2019a.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? arXiv preprint 191.033 194, 2019b.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data, arXiv preprint arXiv:2005.1144 1418,
2020b.
Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. arXiv preprint arXiv:2106.1300 13673, 2021.
13

---

Published as a conference paper at ICLR 2023
A PRELIMINARIES
We use Fr to denote the filtration generated by
[ : T,i = (
means that given Fr, the global solution क, is fixed, but the randomness of Ar, G¹, and G, still exists. In addition, for E I, use Hr to denote the filtration generated by
F & S S + (
Recall the definitions of G. and G..
1 G ( and G, N Σ G
Hence we have
G V/( S and V o
hold almost surely due to Assumption
iiil). Also, the local update rule of EPISODE is
2 2 - (A,) - gi where gi (.((f))))) G + G., Ar [I|r/l |l S 7/n) and A, (I|Gr|l > 7/n)-
(Ar) for t E
|لتو||
A.1 AUXILIARY LEMMAS
Lemma 5 (Lemma A.2 in Zhang et al. For any x, x' Id such that x I C7 L1, we have
2020a)). Let be (Lo, L1) smooth, and C' >> 0 be constant.
ALo + BL -
f(x)) [(x) (VI(x), x' w)
=01133
where A= 1=1+ - E and B E
Lemma (Lemma A.3 in Zhang et al. For any x, xx' IRd such that ar
).20aa). Let f be (Lo, In -smooth, and > 0 be a constant. I C/ TA, have
[Vf((') ff(x)) S (ALo + BL ff(x)))) x=1,
where A = 1- داع and B بسع
Here we choose C' 2 such that A 2 1 and B 2 1.
Lemma (Lemma B.1 Zhang et al. 2020a)). ). Let ps > 0 and u. v E R.d. Then
(u =M|lu|| (1 ||||| (1 p)]l u/l
||a||
B PROOF OF LEMMAS IN SECTION 4.3
B. PROOF LEMMA
Lemma restated.
Suppose AnLo + BL₁ + BLiplo + 7)) 5 1 and
max 2 + 7), 71 < E. where the relation between A, B and is stated in Lemma and
Then for any E [N] and I,, it almost surely holds that
[A.))a= æ, < 2nl 20 7)
and
11 (AA)))) # s STT.
(9)
14

---

Published as a conference paper at ICLR 2023
Proof of Lemmal 7
To show ( holds, it suffices to show that under the event Ar,
ærll S 2n(t t,) 20 + 2
|
holds for any t + 1 < t and E [.]] We will show by induction. In particular, show that this fact holds for t = t, + notice
|| - E, = n nlg.. || - ( - G + 7/ & 2no +y - 2n 0 7)
11
under Ar, and VV (F S |G; where used the fact that ||_||| s 2 1
(.,(),) I a hold almost surely. Now, denote A = 2 20 + 7)) and suppose that
|| ærl S An 4.).
(10)
Then have
| Er||
|| x. -l
Ani( (,) -
$ Anj( - (,) + +/)+ - - 2n +
(11)
Using our assumption nAI < C1L1 together with the inductive assumption (10). we can apply Lemma to obtain
|| (xx) - ((,,))
< (ALo + BL, -L 2z,1
< Any( (AL, + BL
(
S An(t t, (AL + (Lx
I Any(t tALO + mABLiptt t.) - I|+II
(ATo BL BLip BLip (+
S Anpt 4.)
( A(t - (x) A
S -
(12)
21
where (i) comes from the heterogeneity assumption [V][(()] < for all x and from the assumption 2n/ (ALo + BL1K + BLi((a + 7)) < 1. Substituting this into Equation
(
yields
A
||
x. s An(t (,) + 11
2no + 7
A
+ 20 ?
$ 1 A(t t,) +
- Am(t t, + 1). which completes the induction and the proof of Equation 8 Next, to show Equation
99.. notice that under the event A, we have
| x:l =
7
g
<
Σ
g:
= r(t
- (tr + 11) STT.
Lgl |l
B.2 PROOF OF LEMMA 2
Lemma
restated.
Suppose (ALo + BLI + BLip(o + 7)) S 1 and
max { / 20 + :). m1 < G. Then for all E Rd such that || Erll S 2nl 22 + 2)
we have the following inequality almost surely holds:
[AA)) & to + Ta [ (p+ (1(222))
15

---

Published as a conference paper at ICLR 2023
Proof of Lemma 2 Under the event A, {||..|| S r/n)- From the definition of (Lo, L1)-
smoothness we have
[xx)]l < Lo + L [
- Lo + 1, (IV - V/( (z))))
< Lo 11 (=) v/( p (x,)))
(4)
< Lo 11 [f)(z) V + x + 0 2 (++1)
(13)
where we used the heterogeneity assumption [+) - K ((,)) for all æ to obtain (i) and the fact |/ ( < [V G. + Gr
to obtain (ii). Now, for all a such that || - æ. < 2ny (2o + ) according to our assumptions, we have || -z, l S 2n + 5 +. Hence we can apply Lemma 6 to and T,, which yields
[v) (z,)) - (ALo BL, V fa(aa))lll ) 2,
s 1
2x 7
(ATo + BI. [VI
s 2
20 7
(ALo + BLa (
17
S 2
20 + 1)
2
(ALo + BL BLi [1 [2+o]
(
Y
+ - 20
"
where (1) comes from the assumption 27y + BL + BLip(o + ?)) S
Substituting this
result into Equation (13) yields
20 ? + p a 17 | [ax))l s Lo Lı
2
"
20 + 2
$ To + In
k (p+ + 1)
B.3 PROOF OF LEMMA 3
Lemma
restated.
Suppose
(ALo + BLN + BLiPlo + 3)) s 1 and
max [2 + 7), 7T S h. we have both
E, [1 2.,1? [13] < 36p, 12 / (1 + 126,, Pij00²
(14)
2 + 502 E, [1A)))] 11 < 18p, 12 12 1ml 18p
(15)
hold for any - 1 I.. Proof of Lemma
Under the event A,, the local update rule is given by
. 2 ngh, where g: VF(( G G,,.
Using the basic inequality (a (a++b b)² < (1 (1+1/Aja² (A + 1)62 for any À 0, we have
E, 1 (A,))a+t 2.,1
E, [(a))) 3r - 1 -
(
2 Ey (AAr)] - t.. -//V(((a
G. + G.) + T [1(4)) ( - v)((a)))1
(it)
+1 Er |I(A)))>> 211
+ (I 11 F, (1AA))1))))))) + || + 20
x
(16)
16

---

Published as a conference paper at ICLR 2023
The equality (i) and (ti) hold since J, S Hi for 2 t, such that
E, (1A) (a) Cr ((Vi(( - G. (F( [=x()
=E, - V vi(((())) [e]]
G.
=E. (1,,, (a) - Br - ()((((()))))) - G. G. V (x) - v(((a)) He])] = 0,
and
E, [(AAIIVV()))))) - =E, [V [1(=
I E, [A(,))]) p.o
Let I. - Lo + (1 + (p + (){ + 20)). Applying the upper bound for Hessian matrix in Lemma and the premise in Lemma we have
E, [1(A)) - - 1
= -E, (1A.) [[V]((((V)(()))) V)((E)) + (Vf((E)) -.) C.) G.
s 2E, [[AA) - v.((..)) + -V
- G + 2E, [IAA)]
s 4E, [T(A))V - VA(#,) |1 + 4p,o² + 2E, [1AA)]
4E 1(A.) / fiaat + (1-o8 a1-a),,) (z) - 3, )da
4p,o0² 2E, [1(A.)]
A,, [A a., .. || 4p,0² 2 [1 (AA, Gr
(17)
where the second inequality follows from |G (a,,))) S a almost surely. Plugging the final bound of (17) into (16) yields
7 +1+44117² E. [1A4)]] - =.]
E, 2 2.1
<
+ 2(I + 1),² [I(A+)]),,]] + 10p + +17200
(18)
By recursively invoking (8). we are guaranteed that
++1+4411 +114A1PP (1+ (1+1) [1(A))]],]]] + 10p,1)²02)
E, [0(A))laa411-
s=0
( + 1 + 4L1
(I+1) [1(4,)]] + 10p,)
1 4TTT7
3
(7 +1))'
(T (1+1) (2 (1(4)] 10p,)?002
(8)
< (212 E, [1(4.)] + 10p, 10p
< <3679 (E, [1( |. V/ >| [ + [() + 12,202
(60)
< 36p, 12 f(, + 12800
The inequality (1) comes from
1 2 12 (2T1L) < 7 21n Lo + LaK + (p - 1) + b))) s 7 7.
(
which is true because 21/ + BL,K + BLip(o + 7)) < and A, > 1. The inequality (ii) comes from (T+1) TT for any > 1. The inequality (iii) holds since || Vf( <
17

---

Published as a conference paper at ICLR 2023
almost surely. Therefore, we have proved (14). In addition, for 15
notice that
E, [1(A,)]]=]+1 =.11a] 18 [1(A,) [[, 90,,
17 B, [14 G, (I + o2
(iv)
I 18p, 1 aa + [V + 10p0000p000
18p, m V (+,))l 18p, 12 (2 50²
17
The inequality (ie) holds since |G,|| N 7/11 holds under the event A, and ||,, - -V/(,,(() Sa
almost surely.
C PROOF OF MAIN RESULTS
C.I PROOF OF LEMMA
Lemma
restated. Under the conditions of Lemma
let P(A, ALD BLI
O + +)). Then it holds that for each S r S R
By [f(#++1) - -(,,) & E, (I,,)) + E, [IA,,)U(EE))]
where
36. 9 BL 121 2 ((x)) (-2 nT
(50R+ [Vf(2,)
17
2AL
+ 901 2 1210000000
N
and
2 U(Ø,) = -1 BL + 1)
3721 |V/(
+ + + +BB[ak - 6o
2
5n
Proof.
We begin by applying Lemma obtain bound on f(ā,41) f(ūr), but first we must show that the conditions of Lemma 5]hold here. Note that
N
1
[0++1 - 2,1 =
x 4+
Er
N
N
N
11 (A
-x,11+
1
Σ
1
(A,))
Er
N
N
i=1
20 + 2 71
C
< max
2nl
,7
Ta
where the last step is due to the conditions of Lemmal This shows that apply Lemmat 5 to obtain
ALo + BL V
E, [f(#,+1) f(x))) E, (V)( B.)1 + E,
[ 2,
-ME,
((4.))
EET,
gi
E, N [(A.)(V((E))
|
i=1 IEI,
ALo E, [|| 5. [1
BL
+
V (6,
| [| =r.13]
2
(19)
18

---

Published as a conference paper at ICLR 2023
Let p. = -(),, then 1- Pr P(A, Notice that p, is function of क,. The last term in
Equation (19) can be bounded as follows:
[V, -
- =.1l²]]
[V [1 [++1 a, 1E
/V [1 2.11
[V/( (1,1 + (1-
18p,11"//lVf(., ( ( +0
7
+ + -11-,.)>??[1({(6
17
12
500² + 2 [[.() + (1-p (1- (20)
1
where (i) comes from application of Lemma with = 1, and (ii) comes from an application
of 15 in Lemma 3 Substituting (20) into 119
gives
E, [f f(#))]
1
1 N
gi (f.
S ~n
((
-yLE,
Σ
IEI
TET.
ALo
( [()
5502 + - | [
+ 2
E, [|(ēr+1 3t || + 9p, BL, 12,12
+
B2
+ (1 p.)
V+)))
(21)
2
We introduce three claims to bound the first three terms in 21
whose proofs are deferred to Section
D
Claim 1. Under the conditions of Lemma 4 have
1
gi (V
B,
N
Iiill
IEI,
((-301+ 21 - [V,((,,
3,21
$ (1 pr)
+ 2- + BL1x) + 6y
5n
Claim 2. Under the conditions of Lemma 7 have
1 ((A.)V/((E)).)))
E,,
N
LEZ.
$ Pr [
n!!
+ 3613,1112
[V 1262
1 E, 1(A,)
vf(=t)
i=
where I = ALo BLi (r (c+p(o+?)).
Claim 3. Under the conditions of Lemma 4 have
10, E, [| -x,1?] < 2(1 21
1 N
+ 2
1(A,)
+ΣX
V f(()))
N
N
(=1 IET.
19

---

Published as a conference paper at ICLR 2023
Combining Claims and 3 with 19 and
20
yields
E, [f(0,+1) - f(a))
$ pr ( 7 + 36T 19 + 492 B2
-p, BL, (50²
(50² +200 | [
+
2
17
2AL
12100
N
(-5
2
BLa (4p 1
3421
+ pr)
7T+
[V
13 + 2BL1n) + 6y10
2
5n)
1 N
+ 2ALo7*
21 E, 1(Ar)
vf(=a)
N
im I TET,
S Srr [(-7
79
+ 361 261113111 131 + -
BL
9BL, [[a,))) +
500 +2 [V
2
17
2ALo
900
N
1--5xx+
BLa + 12
3
+ (L
| f(æ))))
5nj 232Lo + +2BLIx) + 66,10
2
where the last inequality holds since //(21) 4n²² due to the assumption 4ALon < 1. Then can finish the proof of Lemma 4 by noticing that p, = E, [1 (Ar)) and pr = E, (AA)]- 1
C.2 PROOF OF THEOREM
1
Theorem restated.
3Alaa Suppose Assumption hold. For any es SBLip" we choose
Ne
and 7 (11 +
ALo
S min (856T' 180T 8ALgo2
n
(22)
BLap
where I = ALu + BLIN + BLiP (o + 7).
The output of EPISODE satisfies
(l, S 3c
R
as long as 2 pn
Proof. In order to apply Lemma 4 we must verify the conditions of Lemma Jnder our choice of hyperparameters.. From our choices n and y, we have
2T < < 1.
856
Also
2 17
(
20 +
(1i)
2n 20
+
Li'
856
ALL + BLI + BLip
n
where (i) comes from the condition 77 1/(8561'1) in 22 (ii) is true due the fact that B, C > 1
and 2 1. Lastly, also holds that
I < 4n/o + 2y1 27l1
20
2 17
S
c 4
Therefore the conditions of Lemma Mrre satisfied, and we can apply Lemma Denoting
U(x)= ( T [+ B4, + 12)
3121 5n
+
2 + 2BB (23)
2
20

---

Published as a conference paper at ICLR 2023
and
V(x) = --2 n1 16 1
[Vf + 92, 500² + +3z) |V
+ 1261 2
(24)
N
Lemma|4]ella us that
E (=) - [(x,)) S E. [AA)))((E,) [(A))
(25)
We will proceed by bounding each (ax) and ((x) by the same linear function V/()]]]
To bound (x), notice
2
BL (4p + 1)
571
2
2
2B 22 B
5
2
11
+2BLmpT + B
2
ALu +10 BLiP
+ 1 2
(11o
ALo BLip nn
1/
2BL1P
nl
BL1
+
5
0
77
+
(11BL) + +Lo)) nj
3
5
(1)
2 18
7/
<
10 T
856
(a))
3 ALo
(1v)
10 BL,p ml S enl
(26)
where (i) comes from 2 and (ii) comes from 856Th// < and (iii) holds since 7/1 =
11 + BLiP
ALo and (iv) comes from c S 5BLiP"
3ALo Also, we have
3
5m + 1 2 + +BBbk) Go <
2
3
+
T + 60 !
7
5
?
2
3
3
6o
+
+
856
1lo +
ALe.
BLip
3
3
+
I 0.
(27)
5
856
11
Plugging Equations (66 and 27 into Equation
23) yields
U(x)
en [
(28)
Now to bound V(x).. we have
n + 36 9 BL, 12, <
(4)
1 7
36
9(1BL1 + ALo/P) (p.
n
2
856
8561
-
7
(29)
where (i) comes from 7 S s66r and
BL,
ALo/P for p > 1. Using the assumption
7 < 1 it holds that
= 9BB, 1,p 1602 + ALpo
9BL, 1212
502 + 7/
BLip
16BL + ALo
(6) 1
< nle
<
4 Enl
(30)
20r
21

---

Published as a conference paper at ICLR 2023
where (di) comes from 16BL1 + ALo 5T. Lastly, we have
1 2ALgI120²
2ALono²
=1 P00
N
N
((x)
2ALgo² Ne
- n, 901
18
N
8ALoo
1 InI,
(31)
4
where (i) comes from S min
N₂²
Plugging Equations 29). (30, and (31 into (24)
18011' 8ALge
then yields
V(x) - [ + [ + 2nnT
We then use the inequality x² > 200 a² with [V](( and obtain
1
V(x) S - 2nI
(32)
2
Having bounded (x) and Vxx), we can return to 25
Using
28
we can see
(xx) S -
2 - S enl fx()) + 2 E
so the RHS of (32 is an upper bound of both Uxx and Vxx). Plugging this bound into (5 and
taking total expectation then gives
1
E [ [(x,)) S -
2 nT.
Finally, denoting A = f(00)) f", we unroll the above recurrence to obtain
R
[[ - [(xo)] S - enl
E
+
1 (R + 1)e?n/
r=0
R
4A
E /
< T (R + 1)
+ +
R
+
R
E[IVS(E
3e.
R+1
T=
where the last inequality comes from our choice R 2 1
D DEFERRED PROOFS OF SECTION C
D.1 PROOF OF CLAIM
Proof. Starting from Lemma with V and v gi. have
(V 9 ~=|[V[[(a)) - (1 - ا)llاf + (1 + p)lgg (*
(33)
Ig:il
Under A, G| > 7)) note that gi V=( G. G,, and we have
|| || 2 |G V (2 - G
2 VV ( - [z(())]] [+))( vf(a,)) - -VA((,)) G Vz
2 7
vf(E,)))
22

---

Published as a conference paper at ICLR 2023
and
l1 Vf( [VF +
+ +VV - G V/(aa)]
I 30 + [v) (z,)ll
Plugging these two inequalities into 33
yields
(V) gi)
S <-1|\V](a,) (1- p)) 2 (5 + p)o 2II Vf(a)))l.
g
"
Under A,, we know ||=] - - S 7I, and 7I - f by assumption. Therefore we can apply Lemma to obtain
[V[((z))- - VS((ū)) S (ALo - BL, V/ - x.1l S>((Aoo + BL, (I,))),
This implics that
(V <-
<= - (1-x1) -1- + (5 u1o + 2ALoy! + 2BLLn//[V((E.I1
Igill
Combining this with the choice == =2/5, we have the final bound:
gi
E,,,
(V)(.))
g
LEI
1 N
(-
2
3921
pr)
+,yla + +V
N
5n
|V.f((,)| (-331++BB1pprr"
3121
$ (1 p.)
2- 12
+ BL + 6
5n
where we used the heterogeneity assumption [f(,))] < + pl V
D.2 PROOF OF CLAIM
Proof. Recall the event A, Gr S 7/n}, we have
N
[AA,VV((E))..))
=R, ((AA)) IV)(
Σ
1 N Σot
1=1
IEI.
EEI.
V (i( (1) I
E
(Arr
(V)()
N
IEI,
N
V Vila)) }
(
E,
I(Ar)
IVf(E,))
N
IEI
==1
(is)
12
(( )1 + E I(A,)
Σ vf(=))
2
N
reT,
1 E 1(A,)
Σ
(((())) vf(x,)
(34)
FEI.
The equality (i) is obtained from the fact that N Σ> g = N ΣN VF(( G + G, = + E (F
C)). The equality (ii) holds due to the tower property such that for t >> br
E ((4)) +) E [1
(7()) H. |. EE [1(A))V(EE)
23

---

Published as a conference paper at ICLR 2023
fort
E (I(A))VF((E
VF [
-
which is true since G, = N Σ Va, 2 is independent of V ( given F, and (iii) holds because 2(a, = |||| + ||b|| - ||a - bll?.
Let I ALo + BLI ki + (o + ))) Notice that we can apply the relaxed smoothness in Lemma
6 obtain
E.
- V/
S E, +
- =r1131
< E, [1(A,) + ( =
2 T [1(A,)] - 1.
(00
1 18p, 17 (2) ([+)))
The inequality (1) holds since [V S Gr Gr S + +// almost surely
under the event A... The inequality (ti) follows from the bound (14) in Lemma 3 Therefore, we guaranteed that
N
E
I(A,)
Σ
v(((2)) - V)(E,))
N
LEI,
1(4.) [f((at) Vf(E,) [2]
B
TET.
iml
N
18p, 12 (2
+709)
IEI
2=1
s 18p, 1 " r 12
(35)
Multiplying both sides of 34 by In//I and substituting 35 then yields
1 N
((a.))
1=1 TE
P
( (.., [1 - 1 ME,,
I(A,)
1
Σ ff(x))
2
21
N
im
T
+
Pr
Ex
fi(tt) (V(())
21
N
i=1
SPr Pr ((
n!!
N
+ 3673 1,73,
|VS + 12663,,80222
E,
I(Ar)
ΣΣ (5(z))
2
21
N
lEI,
24

---

Published as a conference paper at ICLR 2023
D.3 PROOF OF CLAIM
Proof. From the definition of 1r+1, we have
E, ||, 1r11
s ((A,)
E,
1
gi
+ 2
1(A,)
ΣΣ IEz.
oi gi
N
FET,
(0)
21y E
1(A,)
Fa St
+ + 2r
i=1 EEI
1
S E,
((A))
V (1(
N
i=1 EE,
+ 4p, EE
((A,)
1
VF. (1)()))) - VAlat))
+ - (p
N
i=1 IEI,
(0)
N N
(AA) I E
fi(t))
i=1
EEI
N
+ 4m
Er
I(A,)
Σ IEI
- -
+ + (36)
where (i) is obtained by noticing that 1/ +i= g = 2 Σm fact that each client's 's stochastic gradients (. { are sampled independently from one another. Similarly, let E In with > L., we can see that
1= VF((ot and (ii) holds by the
E, ((4)) (F. Vf((E) VF(E) vf((aa)))
=E, [(A.) (VP((a): V)(( (i((a: V[i(z()))) H.
E, [(A)) vf(( E,
( H4 [(((x=)))
0.
Therefore, we have
N
E
((Ar)
Σ
VF((a)))) - -Vi((a)
N
IETT
N
E,
- -VA(a)))
N2
1ET,
E,
EET.
Pr
(37)
N
And the desired result obtained by plugging (7) into 36).
E ADDITIONAL EXPERIMENTAL RESULTS
25

---

Published as a conference paper at ICLR 2023
E.1 PROOF OF PROPOSITION
Proof. Recall the definition of f (z) and /2(2),
f1(x) = x² - -xz + Hr + +I, f2(x) = x² -3.x 2H +
which means
Vf(x) 4x3h 9x Hr 1.
and
V/i(2) Vf(=) = 3H. Vf2(2) - Vf(x) -3Hx.
follows that
<
33H + [V](()]]
$ 33H |42 - 9x - Hæ +
$ 4H -x² +
< 10/
| - + | [()]]
(38)
Let g(r) = 10H|ar] - |4.3 9z2 next we will characterize g(z) in different region.
(i) When E (-o0, 0), g(x) = 4x - - 10Hr. The root for the derivative of g(x) in this region
18
V182 + 480H
12x² 18x 10H
It follows that
g(x) S 4r
9x 10Hr
V182 + 480H - 18
< 10H
24
20H
25H2
< 10H
(39)
24
3
where the last inequality follows from < 0.
(ii) When x E (0, 2), (xx) 2x 9x 10/r.. The derivative of g(x) is greater than in this
case since 182 480H < for H 2 Then we have
45H
g(x) < 10H
(40)
2
(iii) When (4, +00). 9(x)
3r + 2x + 10Hz. The root for the derivative of g(x) is
18 + V882 + 480H
122 18x + 10H = 0 - x=
24
Then we have
9
9
45H
g(x)= < max
-4z 9x + 10HH2, -4
+9
4
2
9 2 45H
< 9x² + 10H + 9
(41)
2
Combining
40 and
we are guaranteed that
-18 + /18² + 480H
-18 + V18² + 480H
(x))
10H
24
24
2
+ 45H + 100
3
:= =(H))
26

---

Published as a conference paper at ICLR 2023
Substituting this bound into 38
get
[VA(()) 21l + +1
<
And x(H) < oo is an increasing function of H.
E.2 SYNTHETIC TASK
For two algorithms, we inject uniform noise over 1-1, 1] into the gradient at each step, and tune 7/n {5, 10, 15} and tune 7) {0.1, 0.01, 0.0013. We run each algorithm for 500 communication rounds and the length of each communication round I = The results are showed in Figure
E.3 SNLI
The learning y and the clipping parameter 7 are tuned with search in the following way: that the clipping threshold 7/n varies over {0.1, 0.333, 1.0, 3.333, 10.03. leading 15 pairs (n, 7). We decay both 1 and y by factor of 0.5 at epochs 15 and 20. We choose the best pair (7) 7) according to the performance
vary y E {0.01, 0.03, 0.1} and for each we vary
validation set, and the corresponding model is evaluated on held-out test set. Note that we not tune (7- 7) separately for each algorithm. Instead, due to computational constraints, we tune the hyperparameters for the baseline CELGC under the setting I = 4, 8 = 50% and re-use the tuned values for the rest of the settings.
E.4 CIFAR-10
E.4.1
SETUP
We train ResNet-50 (He et al. 2016) for 150 epochs using the cross-entropy loss and a batch size of 64 for each worker. Starting from an initial learning rate 17o 1.0 and clipping parameter yy 0.5, we decay the learning rate by factor of 0.5 epochs 80 and 120. In this setting, we decay the clipping parameter 7 with the learning rate rj, so that the clipping threshold 2 remains constant during training. We present results for / = 8 and s E (50%, 70%}. We include the same baselines as the experiments of the main text, comparing EPISODE FedAvg, SCAFFOLD, and CELGG.
E.4.2 RESULTS
Training loss and testing accuracy during training shown below in Figure 4 In both settings, EPISODE is superior in terms of testing accuracy and nearly the best in terms of training loss.
E.5
IMAGENET
The training curves (training and testing loss) for each ImageNet setting are shown below Figure
RUNNING TIME RESULTS
To demonstrate the utility of EPISODE for federated learning in practical settings, we also provide a comparison of the running time of each algorithm on the SNLI dataset. Our experiments were run on eight NVIDIA Tesla V100 GPUs distributed on two machines. The training loss and testing accuracy of each algorithm (under the settings described above) are plotted against running time below. Note that these are same results as shown in Figure plotted against time instead of epochs communication rounds.
On the SNLI dataset, EPISODE reaches a lower training loss and higher testing accuracy with respect to time, compared with CELGC and NaiveParallelClip. Table 2 shows that, when / < 8, EPISODE requires significantly less running time to reach high testing accuracy compared with both CELGC and NaiveParallelClip. When / 16, CELGC and NaiveParallelClip nearly match, indicating that I 16 may be close to the theoretical upper bound on for which fast convergence can be guaranteed. Also, the client data similarity decreases, the running time requirement of EPISODE
27

---

Published as a conference paper at ICLR 2023
100
EPISODF
80
CELGG
Objective value
Objectvve value
60
EXPISODDE
40
-20
10
20
30
Round
(a)
100
80
Objective value
Objesive value
60
40
-20
10
20
30
Round
(b) IT
150
100
-5
Offecive value
Objectrre valu
-9
-14
-100
10
20
Round
(c)
150
-10
100
Objective volue
-11
Oblecive vake
50
820
-100
-50
200
(d) H = 8
Figure 3: The loss trajectories and converged solutions of CELGC and EPISODE on synthetic task.
to reach high test accuracy stays nearly constant (e.g., when I 4), while the rumning time required by CELGC steadily increases. This demonstrates the resilience of EPISODE's convergence speed to heterogeneity. Training curves for the same experiment shown in Figure 6
28

---

Published as a conference paper at ICLR 2023
ReAA CB.CC
25
9.8
2.0
1215/004
Tann 1000
02
TTn
0.9
355
140
145
RodAng
140
145
CELOC
0.5-
140
120
140
Epocto
Epecte
(a)
8, 8
50%
2.5
CHLOG
2.0
EPI5ODE
0.90
9.6
140
0.4
FedAke
0.2
SCAFOLLD
EMISODE
1751
Uppdds
(b) 7 = 8, 8 70%
Figure Training curves for CIFAR-I0 experiments.
Interval
Similarity
Algorithm
70%
75%
80%
100%
NaiveParallelClip
37.30
59.69
118.45
2
30%
CELGC
33.57
63.98
N/A
EPISODE
27.20
38.07
70.60
4
30%
CELGC
23.84
42.51
N/A
EPISODE
18.34
25.73
55.15
8
30%
CELGC
20.37
34.06
N/A
EPISODE
13.98
22.43
53.43
16
30%
CELGC
16.57
27.00
N/A
EPISODE
21.26
28.39
N/A
4
50%
CELGC
18.52
31.86
N/A
EPISODE
18.37
25.71
47.76
4
10%
CELGC
39.75
N/A
N/A
EPISODE
18.46
29.71
55.92
Table 2:
Running time (in minutes) for each algorithm reach accuracy of 70%, 75%, and 80% on SNLI dataset. We use N/A to denote when an algorithm did not reach the corresponding level of accuracy over the course of training.
G ABLATION STUDY
In this section, we introduce an ablation study which disentangles the role of the two components of EPISODE's s algorithm design: periodic resampled corrections and episodic clipping. Using the SNLI dataset, have evaluated several variants of the EPISODE algorithm constructed by removing one algorithmic component at a time, and we compare the performance against EPISODE along with variants of the baselines mentioned in the paper. Our ablation study shows that both components of
29

---

Published as a conference paper at ICLR 2023
3.0
3.0
2.5
1.00
Train Loss
1.00
Trann Loss
0.95
2.0
0.95
866
89
0.90
86
89
1.5
1.5
1.0-
1.0
0
20
40
60
80
0
20
40
60
80
Epoch
Epoch
0.80
0.80
0.95
0.75
0.75
0.70
Test Accuracy
Test Accuracy
0.65
0.65
0.74
0.74
0.60
0.60
86
89
86
89
0.55
FedAvg
0.55
FedAvg
0.50
CELGC
0.50
CELGC
SCAFFOLD
SCAFFOLD
0.45
EPISODE
0.45
EPISODE
0.40
0.40
0
20
40
60
80
0
20
40
60
80
Epoch
Epoch
(a) 1 64, 70%
(b) 1 = 64, 8 60%
3.0
3.0
2.5
2.5
1.00
1.075
Tmin Loss
2.0
0.95
Train Loss
1.050
1.025
0.90
86
89
866
89
1.5
1.5
1.0
1.0
40
80
20
40
60
80
Epoch
Epoch
0.80
0.80
0.75
0.75
Accuracy
0.65
Test Accurcy
0.65
0.74
0.74
0.60
0.60
86
89
86
89
0.55
FedAvg
0.55
FedAvg
0.50
CELGC
0.50
CELGC
SCAFFOLD
SCAFFOLD
0.45
EPISODE
0.45
EPISODE
0.40
0.40
0
20
40
60
80
0
20
40
60
80
Epoch
Epoch
(c) I = 64, 50%
(d) = 128,
60%
Figure 5: Training curves for all ImageNet experiments.
30

---

Published as a conference paper at ICLR 2023
0.70
0.70
0.65
0.65
0.60
0.60
Train loss
0.55
Train loss
0.55
0.50
0.50
0.45
0.45
0.40
0.40
0.35
0.35
0.30
0.30
150
150
Minutes
Minutes
0.84
0.84
0.82
0.82
0.80
0.80
Test accuracy
Test accuracy
0.78
0.78
0.76
0.76
CBUGC 1-
0.74
CELOC.T<4 I-8
0.74
CELOC 1- 16
EMSODE.1-2
CBLOC, 10%
0.72
0.72
EPISODE, = 20%
EPIS0DE: 10%
0.70
Nair Puslii Cip
0.70
Pusiel Clip
50
100
150
0
50
100
150
Minutes
Minutes
(a) Effect I
Effect K
Figure 6: Training loss and testing accuracy on SNLI against running time. (a) Various values of communication intervals / E (2, 4, 8, 16) with fixed data similarity 30%. (b) Various values of data similarity (10%, 30%, 50%} with fixed = 4.
EPISODE's algorithm design (periodically resampled corrections and episodic clipping) contribute the improved performance previous work.
Our ablation experiments follow the same setting as the SNLI experiments the main text. The network architecture, hyperparameters, and dataset are all identical to the SNLI experiments described in the main text. In this ablation study, we additionally evaluate multiple variants of EPISODE and baselines, which described below:
SCAFFOLD (clipped): The SCAFFOLD algorithm (Karimireddy et al. 2020) with gradient clipping applied at each iteration. This algorithm, variant of CELGC, determines the gradient clipping operation based on the corrected gradient at every iteration on each machine.
EPISODE (unclipped): The EPISODE algorithm with clipping operation removed.
FedAvg:
The FedAvg algorithm (MMMaha al. 2017a). We include this show that clipping in some form is crucial for optimization in the relaxed smoothness setting.
SCAFFOLD: The SCAFFOLD algorithm (Karimireddy et al.) 2020). We include this to show that SCAFFOLD-style corrections are not sufficient for optimization in the relaxed smoothness setting.
We compare these four algorithm variations against the algorithms discussed in the main text, which include EPISODE, CELGC, and NaiveParallelClip.
31

---

Published as a conference paper at ICLR 2023
Interval
Similarity
Algorithm
Train Loss
Test Acc.
100%
NaiveParalleiClip
0.357
82.4%
2
30%
CELGC
0.579
75.9%
EPISODE
0.361
82.3%
SCAFFOLD (clipped)
0,445
80.5%
EPISODE (unclipped)
4.51
33.3%
FedAvg
1.56
32.8%
SCAFFOLD
1.23
34.1%
4
30%
CELGC
0.564
77.2%
EPISODE
0.399
81.7%
SCAFFOLD (clipped)
0..40
80.7%
EPISODE (unclipped)
9.82
33.0%
FedAvg
1.14
32.8%
SCAFFOLD
4.39
32.8%
8
30%
CELGC
0.539
78.0%
EPISODE
0,431
81.1% %
SCAFFOLD (clipped)
0.512
77.1%
EPISODE (unclipped)
8.02
34.3%
FedAvg
1.25
32.7%
SCAFFOLD
10.86
32.8%
16
30%
CELGC
0.525
78.3%
EPISODE
0.534
77.8%
SCAFFOLD (clipped)
0.597
75.7%
EPISODE (unclipped)
4.71
33.0%
FedAvg
3.45
32.7%
SCAFFOLD
4.87
32.7%
50%
CELGC
0.490
79.1 1
EPISODE
0.385
82.1 %
SCAFFOLD (clipped)
0.436
80.7%
EPISODE (unclipped)
9.08
34.3%
FedAvg
4.81
32.8%
SCAFFOLD
2.40
32.9%
10%
CELGC
0.667
73.3%
EPISODE
0.404
81.5%
SCAFFOLD (clipped)
0).438
80.7%
EPISODE (unclipped)
8.54
33.0%
FedAvg
1.89
34.3%
SCAFFOLD
5.61
34.3%
Table 3: Results for ablation study of EPISODE on SNLI dataset.
Following the protocol outlined in the main text, we train each one of these algorithms while varying communication interval / and the client data similarity parameter 8. Specifically, we evaluate six settings formed by first fixing 30% and varying E {2, 4, 8, 16). then fixing I - 4 and varying E {10%, 30%, 50%}. } Note that the results of NaiveParallelClipp are unaffected by I and s, since NaiveParallelClip communicates at every iteration. For each of these six settings, training loss and testing accuracy reached by each algorithm at the end of training. Final results for all settings given in Table 3 and training curves for the setting I = 4, 30% shown in Figure 7
provide the
conclude that both components of EPISODE (periodic resampled correc- tions and episodic clipping) contribute to EPISODE's improved performance.
From these results,
Replacing periodic resampled corrections with SCAFFOLD-styLe corrections yields the variant SCAFFOLD (clipped). In every setting, SCAFFOLDD (clipped) performs slightly
32

---

Published as a conference paper at ICLR 2023
NaveParalliiCip
0.8
0.9
CELOC
EPISODE
0.8
SCAFFOLD clipped
NalvePuraleeCIp
CELGC
axpemay
0.7
EPISODE
SCAFFOLD diippdd
EMSSODE undipppdd
0.5
FedAvg
0.5
SCAFPOLD
0.4
0.3
10
20
25
15
20
25
Epochs
Eppchs
Figure 7: Training curves SNLI ablation study under the setting / == 4 and s = 30%. Note that the training losses of EPISODE (unclipped), FedAvg, and SCAFFOLD are not visible, since they orders of magnitude larger than the other algorithms.
better than CELGC, but still worse than EPISODE. This corroborates the intuition that SCAFFOLD-style corrections use slightly outdated information compared that of EPISODE, and this information lag caused worse performance in this ablation study.
On the other hand, clipping is essential for EPISODE avoid divergence. By removing clipping from EPISODE, we obtain the variant EPISODE (unclipped), which fails to learn entirely. EPISODE (unclipped) never reached test aceuracy higher than 35%, which is barely higher than random guessing, since SNLI is 3-way classification problem. In summary, both periodic resampled corrections and episodic clipping contribute to the improved performance of EPISODE over baselines.
In addition, FedAvg and SCAFFOLD show similar divergence behavior as EPISODE (unclipped). None of these three algorithms employ any clipping normalization in updates, and consequently none of these algorithms are able to surpass random performance on SNLI Finally, although NaivePar- allelClip appears to be the best performing algorithm from this table, it requires than any other algorithms due to its frequent communication. For a comparison of the running time results, Table 2 in Appendix F
wall-clock time
H NEW EXPERIMENTS ON FEDERATED LEARNING BENCHMARK: SENTIMENT144 40 DATASET
To evaluate EPISODE on real-world federated dataset, we provide additional experiments on the centiment140 benchmark from the LEAF benchmark (Caldas et al. 2018). Sentiment140 is sentiment classification problem on a dataset of tweets, where each tweet is labeled as positive or negative. For this setting, follow the experimental setup of Li al. (020b): training 2-layer LSTM network with 256 hidden units on the cross-entropy classification loss. We also follow their data preprocessing steps eliminate and testing sets. We perform an additional step to simulate the cross-silo federated environment (Kairouz et al. 2019) by partitioning the original Sentiment 140 users into eight groups (i.e., eight machines). To simulate heterogeneity between silos, we partition the users based on non-i.i.d. sampling scheme similar to that of our SNLI experiments. Specifically, given a silo similarity parameter each silo is allocated s% of its users by uniform sampling, and (100 s)% of its users from a pool users which are sorted by the proportion of positive tweets in their local dataset. This way, when is small, different silos will have very different proportion of positive/negative samples in their respective datasets. We evaluate NaiveParallelClip CELGC, and EPISODE in this cross-silo environment with / = 4 and {0, 10, 20). We tuned the learning rate n, and the clipping parameter yy with grid search over the values 7 E {0.01, 0.03, 0.1, 0.3, 1.0) and E {0.01, 0.03, 0.1, 0.3, 1.0). Results plotted in Figures 8 and
with small number of data points and split into training
33

---

Published as a conference paper at ICLR 2023
0.75
035-
EPISODE
Natr Panilel Cip
Train lods
Train loas
0.50
Training Steps
Trainin Steps
Training Steps
0.78
0.18
0.18
0.76
0.76
0.76
0.74
0.74
0.36
Tex accuraty
0.00
0.10
0.70
0.8
0.68
Tol
0.68
0.52
2000
0.62
2030
0.62
a000
Tranning Steps
Tranning Steps
Training Steps
1 4, 8
20%
(h) /
10%
(c) 4, 0%
Figure 8: Training curves for all Sentiment]40 experiments over training steps.
0.75
CELOC
6.75
0.75
0.90
Naive Buallel Clip
0.30
0.70
Train 1086
0.65
0.65
0.65
0.50
8,60
0:60
100
200
300
500
100
230
300
400
5.0
100
200
300
400
Time
Time
Time
0.76
0.76
0.76
Toat B000ra
6:70
0.00
0.70
0.08
Teal
8.68
Teal
0:68
0.64
0.64
0.64
0.62
180
350
550
+50
650
0.62
100
25o
v00
450
s00
0,62
210
100
450
s50
Time
(a) / = 4, 20%
(b) 1 4,
10%
(c) / = 4, 5 = 0%
Figure 9: Training curves for all Sentiment 140 experiments over running time.
Overall, EPISODE is able to nearly match the training loss and testing accuracy of NaiveParalleeCllpp while requiring significantly less running time, and the performance of EPISODE does not degrade as the client data similarity decreases. Figure 8 shows that, with respect to the number of training steps, EPISODE remains competitive with Naive ParalePaallllCCipp and outperforms CELGC. In particular, the gap between EPISODE and CELGC grows the client data similarity decreases, showing that EPISODE can adapt to data heterogeneity. On the other hand, Figure showws that, with a fixed time budget, EPISODE is able to reach lower training loss and higher testing accuracy than both CELGC
34

---

Published as a conference paper at ICLR 2023
and NaiveParallelClip in all settings. This demonstrates the superior performance of EPISODE in practical scenarios.
35


Reviews:
[{"review_id": "oBuHVn2jsl1", "reviewer": "Reviewer_2GmL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper introduces a new optimization algorithm for the federated learning setting with heterogeneous data, limited communication, and a relaxed smoothness condition. The algorithm uses two new ideas: episodic gradient clipping and periodic resampled corrections. They prove that the algorithm has improved performance for heterogeneous data compared to prior methods, and matches prior results for homogeneous data. They demonstrate the effectiveness of the algorithm empirically, on both synthetic and realistic data.\n\n", "summary_of_the_review": "For the reasons discussed above, I recommend acceptance.\n\n----------------------------------------------------------\n\nPost rebuttal: I have read the other reviews and responses, and I will stick with my original score.", "strength_and_weaknesses": "The task studied in the paper is natural and relevant and has been studied in prior works. The paper significantly improves the state-of-the-art results, and thus the contribution is significant. The algorithm is based on novel ideas, and its theoretical analysis is non-trivial. Finally, the experiments demonstrate the effectiveness of the algorithm compared to prior approaches.  \n\nI cannot point to weaknesses, although I should mention that I am not familiar enough with the relevant literature, and hence this review has low confidence.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "nKWAmCbTmXC", "reviewer": "Reviewer_5vyJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper proposed the EPISODE method for clipping in federated learning. Each algorithmic round in EPISODE consistents two communication rounds: (1) a “global” gradient is estimated by sampling and averaging the gradient over all clients; (2) the estimated gradient is then used for two purposes, as control variable similar to SCAFFOLD, and as an indicator for gradient clipping; the indicator will determine whether the gradient (calibrated by control variable) for each local step will be clipped. Experiments on SNLI, ImageNet and CIAFR-10 show that EPISODE outperforms FedAvg, SCAFFOLD and CELGC. \n", "summary_of_the_review": "As the main contribution seems to be theoretical, I would see more discussion on the theory advantage and the connection between theory and practice. ", "strength_and_weaknesses": "I did not check the full details of the proof, but the results look reasonable to me. The proposed EPISODE method appears to be novel to me. Compared to CELGC (Liu et al. 2022), EPISODE studies heterogeneity in federated learning, and introduced control variates similar to SCAFFOLD (Karimireddy et al., 2020). Compared to SCAFFOLD, EPISODE studies the assumption of relaxed smoothness functions and applies gradient clipping. \n\nI did not see obvious flaws in the draft. However, I also want to see more discussion connecting theory and practice: in the relaxed smoothness setting, could the authors comment on the theoretical advantage of EPISODE over SCAFFOLD, and how does that connect to the empirical results? \n\nFedAvg is a strong baseline, but I am a little surprised to see that in Figure2, both CELGC and SCAFFOLD underperform FedAvg for accuracy, but EPISODE (the conceptual combination of CELGC and SCAFFOLD) outperforms FedAvg. \n\nI would encourage the authors to discuss application scenarios. Assuming all clients participate in training every round seems to suggest the algorithm is more applicable to cross-silo setting. See [A Field Guide to Federated Optimization https://arxiv.org/abs/2107.06917 Section 3.1]. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PyGHIPoK7d", "reviewer": "Reviewer_njR7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper proposes a new algorithm called EPISODE for Federated learning with clipping. The algorithm at every round first computes the full gradient from all the clients and after that either clips all of the local updates, or doesn't clip it based on the norm of this full gradient. \n\nAuthors prove the convergence under (L_0, L_1) smoothness assumption. Authors also provide an experimental comparison of their algorithm to the previous baselines. ", "summary_of_the_review": "The paper is well written, theoretical result is novel, but not well compared to the literature. Experimental evaluation is limited. ", "strength_and_weaknesses": "+ Paper provides the algorithm that can achieve theoretically faster convergence than previous algorithms under (L_0, L_1)-smoothness. \n\n- It is not compared in the paper how does proved convergence rate compare to FedAvg and to Scaffold convergence rates. \n\nExperimental evaluation is limited:\n\n- IMAGENET and SNLI datasets are not Federated Learning datasets. Would be more interesting to see comparison for some classical FL datasets, e.g. from LEAF benchmark. \n\n- in Imagenet experiments the learning rate was fixed to be the same value for all of the algorithms: this might be not a fair comparison of the algorithms, as optimal stepsizes might be different for different algorithms. \n\n- Paper did not provide experimental comparison to other clipping baselines, such as e.g. adaptive clipping [Andrew et al 2021]. \n\n- Every round of the proposed algorithm requires communicating gradients twice. Thus it can be considered that every round has effectively two rounds of communications. This was not taken into account during experimental comparison. \n\n- It is also unclear if the experimental speedup comes from clipping, or from better estimating correction terms G_r and G_r^i. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-WiXeucSBqi", "reviewer": "Reviewer_m9yX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper proposes a communication-efficient distributed gradient clipping algorithm for federated learning, which is called EPISODE. The algorithm works particularly well with the heterogenous data and under the nonconvex and relaxed smoothness setting. The novelty consists in two techniques: episodic gradient clipping and periodic resampled corrections. Another contribution of this paper is to provide a convergence proof for the proposed algorithm under several assumptions. Empirical studies show that EPISODE outperforms other federated learning algorithms on the both synthetic and real datasets, which include SNLI and ImageNet.", "summary_of_the_review": "The major contribution of this paper is to propose an algorithm to solve the distributed optimization with heterogenous data. Although the setting might not be realistic, the theoretical contribution should still be appreciated.", "strength_and_weaknesses": "Strength:\n\n1. This work seems to be the first to study the federated learning under heterogeneous data setting with relaxed smoothness assumption, and provide a provable algorithm to solve the problem.\n2. The paper is well motivated by giving examples why existing algorithms (CELGC and SCAFFOLD) do not work in the setting.\n3. The theoretical results come with well sounded implications, making the results convincing (theoretically).\n\nWeaknesses:\n\n1. I am not sure if the given setting is realistic. Like many other distributed optimization papers, this paper put quite a few constraints to the scenarios, such as heterogeneity of the data. But in reality, do we really need to solve such a problem?\n2.  While the paper proposes a distributed algorithm, which implies the problem scale is large enough. However, in the experiments, the data/model scale is not that big that a single machine can easily hold them. It is like motivating the paper by solving a very difficult problem but it turns out the problem is not that challenging.    ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster