Federated Learning with Client Subsampling, Data Heterogeneity, and Unbounded Smoothness: A New Algorithm and Lower Bounds
Authors: Michael Crawshaw
Yajie Bao
Mingrui Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: federated learning
client subsampling
nonconvex optimization
relaxed smoothness
data heterogeneity
lower bound

Abstract: We study the problem of Federated Learning (FL) under client subsampling and data heterogeneity with an objective function that has potentially unbounded smoothness. This problem is motivated by empirical evidence that the class of relaxed smooth functions, where the Lipschitz constant of the gradient scales linearly with the gradient norm, closely resembles the loss functions of certain neural networks such as recurrent neural networks (RNNs) with possibly exploding gradient. We introduce EPISODE++, the first algorithm to solve this problem. It maintains historical statistics for each client to construct control variates and decide clipping behavior for sampled clients in the current round. We prove that EPISODE++ achieves linear speedup in the number of participating clients, reduced communication rounds, and resilience to data heterogeneity. Our upper bound proof relies on novel techniques of recursively bounding the client updates under unbounded smoothness and client subsampling, together with a refined high probability analysis. In addition, we prove a lower bound showing that the convergence rate of a special case of clipped minibatch SGD (without randomness in the stochastic gradient and with randomness in client subsampling) suffers from an explicit dependence on the maximum gradient norm of the objective in a sublevel set, which may be large. This effectively demonstrates that applying gradient clipping to minibatch SGD in our setting does not eliminate the problem of exploding gradients.  Our lower bound is based on new constructions of hard instances tailored to client subsampling and a novel analysis of the trajectory of the algorithm in the presence of clipping. Lastly, we provide an experimental evaluation of EPISODE++ when training RNNs on federated text classification tasks, demonstrating that EPISODE++ outperforms strong baselines in FL. The code is available at https://github.com/MingruiLiu-ML-Lab/episode_plusplus.

Federated Learning with Client Subsampling, Data Heterogeneity, and Unbounded Smoothness: A New Algorithm and Lower Bounds
Michael Crawshaw
Yajie Bao" School Mathematical Sciences
Department of Computer Science
George Mason University Fairfax, VA 22030, USA
Shanghai Jiao Tong University
Shanghai, China
mcrawsha@gmu.com edu
baoyajio2019stateee edu. cn
Mingrui Liu
Department of Computer Science
George Mason University Fairfax, VA 22030, USA mingrui @gmu.. edu
Abstract
We study the problem of Federated Learning (FL.) under client subsampling and data heterogeneity with an objective function that has potentially unbounded smooth- ness. This problem motivated by empirical evidence that the class of relaxed smooth functions, where the Lipschitz constant of the gradient scales linearly with the gradient norm, closely resembles the loss functions certain neural networks such recurrent neural networks (RNNs) with possibly exploding gradient. We introduce EPISODE++, the first algorithm to solve this problem. It maintains historical statisties for each client to construct control variates and decide clipping behavior for sampled clients in the current round. We prove that EPISODE++ achieves linear speedup in the number of participating clients, reduced communi- cation rounds, and resilience to data heterogeneity. Our upper bound proof relies novel techniques of recursively bounding the client updates under unbounded smoothness and client subsampling, together with a refined high probability anal- ysis. addition, we prove lower bound showing that the convergence rate of a special case of clipped minibatch SGD (without randomness in the stochastic gradient and with randomness in client subsampling) suffers from an explicit dependence on the maximum gradient norm of the objective in a sublevel set, which may be large. This effectively demonstrates that applying gradient clipping to minibatch SGD in our setting does not eliminate the problem of exploding gradients. Our lower bound based on new constructions of hard instances tai- lored to client subsampling and a novel analysis of the trajectory of the algorithm in the presence of clipping. Lastly, we provide an experimental evaluation of EPISODE++ when training RNNs on federated text classification tasks, demon- strating that EPISODE+ outperforms strong baselines in FL. The code is available at httttt:///// httt:::://githbbb www.ttttt...oottteeeeeeeeeeeeeee Coom/Mingruiiiing http:///nnniiiiii---aaaaa//aeaee httpl/aa//ppispepppppppppp
"Equal Contribution.
1 "ooresponning Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Best complexity to find an e-stationary point for various methods and settings. The setting column describes the features of the setting in which the algorithm can solve the problem: (Re) denotes relaxed smoothness, (H) heterogeneous data, and (S) client subsampling. a: stochastic gradient noise, k: client heterogeneity, A: objective gap at the initial solution, J: local steps, R: communication rounds, subsampled clients. denotes a high probability guarantee. Ō() and ((-) omit logarithmic terms.
RT: iteration complexity, N: number of clients, S: number of
Best Iteration Complexity
Largest / to guarantee
Method
Communication Complexity (R)
Setting
lincar speedup
Local SGD
o o( Nr-
AIaNNT
ALN
o
(H)
SCAFFOLD
Ala"
Sict
A/)
ALa 0
0
N2
(H), (S)
CELGC 32
Adan? Nict
0
0 K>>
(Re)
Net
EPISODE
Alkuttylete))
(1 (+)))
(Re). (H)
(Theorem 1
EPISODE+
Alko da (mmp bn
Tap
Alae
(Re), (H), (S)
Clipped Minihatch SGD (Theorem
(Re), (H) (S)
Introduction
is distributed learning paradigm in which many clients collabora- tively train a machine learning model while communicating over a network, which preserves privacy and leverages parallelism across many clients. Minimizing communication cost, accounting for data heterogeneity across clients, and allowing for partial client participation are core principles of FL.. Interest in FL has grown in recent years, especially with user-facing applications such as next word prediction on smartphones [19].
Federated Learning (FL) 333 23
Optimization is central part of FL algorithms, and most work on non-convex optimization assumes a smooth objective in both the single machine setting [15 16 and the FL setting 41
48 24
26
However, recent work [52
g
has shown empirical evidence that certain neural networks (LSTMs
21, and Transformers
42 do not satisfy this assumption, but do satisfy a weaker condition known
as relaxed smoothness
22 Under relaxed smoothness, techniques such as gradient clipping (37
essential for avoiding exploding gradients. To avoid the negative effects of exploding gradients, GD without gradient clipping requires step size inversely proportional to the maximum gradient norm of the objective in sublevel set (denoted as M), resulting in very slow convergence. The usefulness of gradient clipping under relaxed smoothness matches observations of training these neural networks in practice, for example on natural language tasks, which are common in FL 23].
However, little work yet exists for FL in the relaxed smoothness setting. Liu et al. 32 introduced a communication-efficca gradient clipping algorithm for FL under relaxed smoothness, with the additional assumption of homogeneous client data and distributional assumption stochastic gradients. The EPISODE algorithm 9 was subsequently introduced to handle hetero- geneous client data in this setting, but requires full client participation, that is, that every client participates in every communication round. This significantly decreases the practical applicability of EPISODE, since full client participation is rarely achievable with large-scale FL in practice 23
the noise of
In this work, we introduce EPISODE++, the first algorithm for FL under relaxed smoothness, client heterogeneity, and client subsampling. EPISODE++ maintains statistics of the history of gradients for each client, and uses these statistics to (1) correct each local update step to approximate an update on the global loss and (2) determine at which steps the clipping operation should be performed. We prove that EPISODE++ achieves linear speedup in the number of participating clients, has reduced communication cost, and enjoys convergence rate independent of client heterogeneity.
previous line of work in the non-convex smooth stochastic setting algorithms against classical baseline: minibatch SGD [40]. Despite the impressive results of newer
45 47 27
compares FL.

---

algorithms in practice only few works have proven that some FL algorithms have a theoretical advantage over minibatch SGD [7 is therefore natural to ask what the analogue of minibatch SGD in the relaxed smooth setting, and whether it is possible to improve upon this analogue. In this work we consider clipped minibatch SGD, which obtained by applying gradient clipping to each update of minibatch SGD. We demonstrate a surprising negative result for clipped minibatch SGD: under client subsampling, relaxed smoothness, and client heterogeneity, the convergence rate of clipped minibatch SGD still depends on M. This implies that gradient clipping does not help minibatch SGD in this setting.
Our contributions can be summarized as follows:
We introduce EPISODE+,, the first algorithm for FL under relaxed smoothness, client heterogeneity, and client subsampling. We prove that EPISODE++ achieves linear speedup in the number of participating clients, reduced communication cost, and has convergence rate independent of client heterogeneity. Table shows a detailed comparison of the complexity of various algorithms. To achieve this result, we introduce novel techniques of recursively bounding the client updates in the presence of unbounded smoothness and client data heterogeneity, together with a refined high probability analysis.
We demonstrate lower bound for clipped minibatch SGD in which the convergence rate depends on M (the maximum gradient norm of the objective function in a sublevel set). This shows that, in our setting, clipped minibatch SGD is susceptible to exploding gradients, and avoiding them requires very small learning rate, which slows down convergence. Our lower bound is based on new constructions of hard instances tailored to client subsampling and a novel analysis of the trajectory of the algorithm in the presence of clipping.
We empirically evaluate EPISODE+ against strong baselines when training RNNs on fed- erated text classification tasks. The results show that EPISODE++ consistently outperforms baselines across various client participation ratios and resilient to heterogeneous client data, which is consistent with our theory.
2 Related Work
Federated Learning FL was proposed by 33 where the authors designed the FedAvg algorithm,
which is also referred to as local SGD in the literature [1 48) The local SGD algorithm has been
analyzed in various settings, including convex smooth setting 41 28
24
45
47
26
49
17 25
convex composite setting [50, 2, 35 J. and nonconvex smooth setting 22
43
B1
18 48 28 24
38
53
26
There is line of work which specially considered client partial participation in
44 7 under convex or nonconvex smooth settings. Recently, Liu et al. 32 and 9 considered FL with nonconvex and relaxed smooth functions for homogeneous and heterogeneous data respectively. However, they assume full client participation and neither of them are applicable to the case of client subsampling.
FL
6
1
24
Crawshaw et al.
Relaxed Smoothness Relaxed smoothness was proposed by 52 relaxation of the standard smoothness condition, which is used to model the exploding gradient problem in training deep neural networks such as recurrent neural networks 36 37 and long-short term memory networks (52), lan- guage models 14 34 and transformers [8. Zhang et al. (52) proved that gradient clipping converges faster than any fixed step size gradient descent for relaxed smooth functions. The complexity bound in (52) was further improved by [5T]. Recently, there is a line of work which considered different algorithms and various analyses under relaxed smoothness [8 39 12]. However, all of them focused on single machine setting and may not be applicable to FL setting.
Lower bounds in Federated Learning There are several lower bound results for FL algorithms.
Woodworth et al. 45 47 compared minibatch SGD and local SGD in the regime of federated stochastic convex optimization setting for homogeneous and heterogeneous data and established
lower bounds for local SGD. Woodworth et al. [66] proved min-max complexity of distributed stochastic convex optimization for any intermittent communication algorithm. Glasgow et al. [17 established improved lower bounds of local SGD in convex optimization setting for both homogeneous and heterogeneous data. However, all of these lower bounds are not applicable to our setting where the problem instance is relaxed smooth with heterogeneous data and client subsampling.
3

---

3 Problem Setup
We consider federated learning with heterogeneous and stochastic objectives, where the goal is to minimize the average loss function across N clients. For E [N], let fa(x) EE (a: {)] be the objective of the i-th client, where D; is the underlying data distribution of the i-th client. Then the global objective is
min wER
f(x)=
f(x) = N Σ F
(I)
Since each fi is not necessarily convex, we consider the problem of finding an e-stationary point, that is, a point x E Rdd such that [[>]( S.
Most works on non-convex optmization 15 16
consider the case where each fü is L-smooth,
so that V f() < for every æ R. However, several works [52 g have shown empirical evidence that objective functions corresponding to some types of neural networks (such as LSTMs 21 and Transformers (2) do not satisfy this condition, but do satisfy strictly weaker condition known as (Lo, L1) -smoothness, or relaxed smoothness. A second-order differentiable function I2d - R is called (Lo, L1) -smooth if [VVg((x)) < Lo + Lil [z)))) for all a E Rd. Notice that any L-smooth function is (L, -s-mmohh.
In this work we consider the problem described in T under the following assumptions.
Assumption 1. (i) Denoting by ao the initial iterate, there exists some A > O Ouchh that f [( min [ax A. (ii Each fa and is (Lo, Ia)-smooth. (iii) There exist K. 2 0, p 2 1 such that (x)) < K + pll V f=x)]] for all E Rd, (iv) There exists a 2 O such that E EgWD, [V,D, [V, f((z) and (F;((; ff(())] S a almost surely for & ~ Di.
Assumption (i) is standard non-convex optimization 15 16). Assumption (ii) is typically used in the literature [32 91. Assumption (Mix) is used in heterogeneous federated learning 24 and describes the heterogeneity between client objectives: if K = and p = 1, then all client objectives fi are equal. Assumption (iv) is common in the relaxed smoothness setting 152 51
32
8 9
In addition, we consider the case of partial client participation in federated learning, also known as client subsampling. With partial participation, only S out of N clients will participate in each communication round, which exacerbates the issue of client heterogeneity.
4 Algorithm and Convergence Analysis
4.1 Main Challenges and Algorithm Design
We first illustrate why existing algorithms such as SCAFFOLD (24] and EPISODE 9 are not able to handle heterogeneous data, relaxed smoothness and client subsampling simultaneously. The analysis of SCAFFOLD crucially requires the function to be L-smooth to recursively bound (1) the lag error from client subsampling and (2) client drift from local updates, but this argument is not applicable for relaxed smooth functions whose gradient information changes quickly. EPISODE has convergence guarantees for relaxed smooth functions and heterogeneous data, but only with full client participation. A naive variant of EPISODE in the client subsampling case does not work: the indicator of gradient clipping is based only on information from clients participating in the current round and ignores information from unsampled clients, which introduces non-negligible bias from client heterogeneity.
To address these challenges, we design a new algorithm named EPISODE++. which is presented in Algorithm[] [] Similar to EPISODE [9], our algorithm utilizes episodic gradient clipping, which determines whether a clipping operation will be performed depending on the size of the average control variate G,, This means that during each round, either (1) all clients perform a normalized update for all steps, or (2) all clients will perform an unnormalized update for all steps. However, different from EPISODE, our algorithm corrects local updates with control variates G;; computed as the averaged stochastic gradient over the previous round which client i participated, as in SCAFFOLD. As we will show in our proof, the episodic gradient clipping together with the update correction strategy allows the algorithm to progress in stable manner: and will sufficiently decrease the objective value and also avoid the negative effect of possibly exploding gradients.

---

Algorithm E
1: Initialize To. Go <- (a,, E)). Go + Nv Σ G
2: forr= 0, o..,....
do
3: Sample S, C [N] uniformly at random such that [S,] = S
4: for E S, do
5: #7.0 + Cr
6:
for k ..... do
7:
Sample FFi kr,k), where fr,k ~ D;
8:
9 FF kr,k) G² GG
27, t o - n |Grlls//n - - gh
9:
Noo 1G-1////1
10:
end for
11:
G 7 k=0
12:
AG; + G GG
13:
end for
14: Update I,+1 + 1
3. Eiss, _
15: Update G,+1 t G, + Eies, AG;
Denote G2,+1 G₁P for all i S
17:
end for
4.2 Convergence Result
The following result proves that EPISODE+ converges to an e-stationary point with high probability.
Theorem 1. Let ALo 16BLip
and E (0, 1). Denote K
log( RN/6) log(N/(N-))
ALo + BLIR+
4BL1p (2xr + ?) and 122 64 k 5p 2o + 2 2)) { }). If
Sea
A
7 S min
(74 + 90(K + I 321'
Aln. Blae
216AL log log
I
12o²
T2I
and
72o + BLiP)
ALa.
t then Algorithm satisfies / IDD [V
R-1
<
35c with probubility at
least 1 158, long as R
8A "
The above result holds for wide range of n and 7, and for any noise level a. The corollary below summarizes the best possible iteration complexity and communication complexity implied by Theorem 1 The full proofs of Theorem and Corollary can be found in Appendix A.5 A.6
Corollary Suppose > O. If. under the setting of Theorem we additionally choose ALo 16 74 BLJe)
I8AALO 32AT, (T4++ BLT
Ale
min
Alg 16BLip
{ n as large as possible under
45(K+1]
Fg log 3
and
27 A Iog
then Algorithm
has iteration complexity RT RT= ( Se
(Alggo log
If
4cT; ((70 + Biar
Ala
additionally 1 θ
Loo² log
then Algorithml / has communication complexity
tn Lip)
La [(lo+ta(N+to)) 2Tp
R = O
AAthhough it appears that this operation must be performed by unsampled clients, this is just an artifact of the notation: unsampled clients do not have execute any operations.

---

4.3 Proof Sketch
In this section we provide sketch for the proof of Theorem We wish to establish the descent inequality for the global objective function in each round by applying Lemma A.3 in (51]:
(0+ S f(tr) (V -x,) + ALo + BL, [V)
Erl.?
(3)
where = 1 c- and C O is an absolute constant. However, using this descent inequality requires |,, E. S C/ Achieving a universal bound on the distance over two consecutive rounds is nontrivial in the presence of client subsampling, data heterogeneity and relaxed smoothness, which requires a new analysis.
Compared with SCAFFOLD [24] and EPISODE [9]. the main difficulty of analyzing EPISODE++ lies in controlling the distance between local weights of and the synchronization point &, under relaxed smoothness and client subsampling. In EPISODE, the magnitude of g can be bounded in terms of ( (z,)) |I and ||G, since G is evaluated at the synchronization point É,- Then the distance be bounded recursively when clipping does not happen (i.e., | S //n). However, EPISODE+ utilizes historical gradients to construct the indicator G,, which means the increment also depends the lag error G f(,,))l Il. Due relaxed smoothness, we cannot bound the lag error as in SCAFFOLD where G.; is evaluated. In the extreme that client has never been sampled before round have G VF; &s), the lag error be unbounded when is large.
24 because we do not know the distance between T, and
To address the issue mentioned above, we analyze the convergence of EPISODE++ in a high- probability framework. Let yr,, denote the local model of client i at step k during the most recent round in which client à participated (before round r), and df denote the index of this round. Since client subsampling independent across rounds, P( 2 K) (1 S/N)*. Therefore, we introduce the event E := [maxogr<R-
- q.- < K. where K is logarithmic factor such that TE())= 2 Under E, we obtain the following lemma to bound the distance of local updates.
Lemma 1. Suppose that holds. Then for any 2 0 we have
1g max kE[l]
| x,|1 s 21 + +7, for any i Sr,
(4)
1 max k
Er < 2(K + 1)/ (2om) 7), for any i E [N].
(5)
The proof of Lemma is deferred Appendix A.3 which relies jump start analysis. If |G,|| 7/1, then (4) trivially holds due to the clipping operation. When |G,, S s/nn, a recursive argument shows that the discrepancy | =, depends on the magnitude of the increment the starting point, that is the lag error G (f.(z,)) and |G,|| after removing noise. According to the construction of G we know E
Σ Vf(((())= = Vf( Therefore, under the event E, the lag error at the r-th round can be bounded by the discrepancies of previous K + rounds at most, which is the bound (5). In summary, the discrepancy at any round can be controlled recursively if the discrepancy the initial round is small. This insight motivates the initialization G Fi &1) in Algorithm which enjoys zero initial lag error.
Finally, Lemma Sshows shows that the condition of 33) can be satisfied by choosing 7) 7, which establishes descent of the global objective from &, to Tr+ Summing from = O.... R and applying
concentration bounds over martingale difference sequences to yield high probability bounds for error terms coming from stochastic gradient noise and client subsampling yields
R-1 Σ
1
f(WR) f(āo)
(120² +I2I) 17 log
(6)
where Ar = G <7/1} denotes the clipping indicator, and (xx), V(x) are defined in the proof of Theorem According to the choice of 7, 7, the dominant term of U (a.,) ) is / (f ), and that of V (ā is [ Plugging into (6) and rearranging proves Theorem

---

5 Lower Bound for Clipped Minibatch SGD
to the relaxed smooth setting (see pseudocode in Algorithm 2 Appendix B Clipped minibatch SGD is nearly identical to minibatch SGD: with the addition of gradient clipping to each round's update. In the similar spirit of [45], we are interested in this algorithm because it has the same computation and communication structure as EPISODE++ and it is important to understand whether EPISODE+ has any advantage over clipped minibatch SGD, In fact, we will show that clipped minibatch SGD is significantly hindered by the combination of relaxed smoothness, client heterogeneity, and client subsampling.
Clipped minibatch SGD is natural extension of minibatch SGD 40 45
Assumption 2. There exists M 0 such that V f(x)l S
M for all x with f(x) S f(zo)
A line of work on relaxed smoothness in the single- machine setting [52 g has shown that the number of iterations required to find an e-stationary point by gradient descent (GD) under relaxed smoothness is Ω (لمدا while that of GD with gradient clipping is O سيي ). In this way, gradient clipping can remove the dependence on M, which can be large, and significantly speed up optimization.
Theorem 2 shows surprising result: under some conditions on the participation ratio, number of clients, and heterogeneity parameter p. clipped minibatch SGD requires Ω ( (اايا)) rounds, showing that applying gradient clipping to minibatch SGD does not eliminate dependence on M.
Theorem 2. eixe > 0, 0 < 8 < 1, Lo > 0, T, > 0, K 0, 2+log(2 6), M> max( to c). N 1ug(2-5)
(0+D)(1-oo(22-B) 8))
(og22))=(--))- Define Q = (+((-11MM x++++))M
Let Lo. L1, M, M, P. N) denote the set of problem
instances { satisfying Assumptions 7 (iv- and 2 with a = 0. For any fixed choice of parame-
ters 7, 17 based on the knowledge of above constants, there exists { E =F(Lo, Ln, M, R. p, P)
1og(2-5)(Q+H) will satisfy such that clipped minibatch SGD initialized at æo with 1 S S N U-Q+log(2-8)
((x)] <, 6. forr some 0 S r S R 1) 8 only if
L (f(zo) - f
1
167.0
R RZ
2e
1 + log
Li
Lo
The proof is included Appendix B This result shows that clipped minibatch SGD in our setting suffers the same problem as GD in the single-machine setting: divergence can only be avoided with very small step size, leading to slow convergence. In contrast, the convergence rate of EPISODE+ in the same setting is independent of M.
The proof of Theorem analyzes clipped minibatch SGD for three different problem instances. The first contains linear local objectives with high heterogeneity: if the clipping threshold is sufficiently small ( < .M), then clipped minibatch SGD will never converge with probability 8. The second instance contains homogeneous, exponential local objectives: the learning rate must be sufficiently
to avoid divergence due to the exponentially increasing gradient magnitude. However, with a large clipping threshold and small learning rate, the convergence of clipped minibatch SGD will depend on M for the third problem instance, which has homogeneous linear objectives. Note that our lower bound is different from previous lower bounds in [52] which are in the settings of single machine (52) or almost sure bounded noise (5]), since our lower bound is considering noise from client subsampling and client data heterogeneity which is not almost surely bounded.
small 17 O
T.
6 Experiments
To validate our theory, we evaluate EPISODE+ and baselines in the training of RNNs for two text classification tasks. We compare EPISODE+ to CELGC (32) clipped minibatch SGD, and NaiveParallelClip [32], which is naive parallel implementation of SGD with gradient clipping that requires communication at every iteration. As an ablation study, we also evaluate two algorithms closely related to EPISODE++. The first is a naive extension EPISODE O for client subsampling, where each participating client's control variate G is resampled at the beginning of each round, and G, = z Eies, G The second is an algorithm which we refer to as SCAFFOLDC (}) which applies gradient clipping to each local step of SCAFFOLD 24
We evaluate these six
7

---

SNU
0.7-
0.7
Test Accuracy
Test Accuracy
Trann Loss
0.6
0.80
Train LoSS
0.6
0.80
0.5
0.5
0.3
0.70
0.3
0.70
50%
30%
50%
30%
Participating Clients
Partidipatnng Clients
Data similarity
Data similarity
+
CELGC
NaiveParalleiCip
Clipped Minibatch SGD
SCAFFOLDCIIp
EPISODE
Training loss and testing accuracy for SNLI dataset.
Sentiment140
0.6
0.6
test Accuracy
Test Accuracy
Train Loss
0.5
Train Loss
0.5
0.4
0.4
0.3
0.74
0.3
0.74
2
4
6
20%
10%
0%
20%
10% similarity
0%
Participating
Participating
Data similarity
EPISODE++
CELGC
NaiveParalleiCiip
Clipped Miribatch SGD
SCAFFOLDCIp
- EPISDDE
(b) Training loss and testing accuracy for Sentiment 140 dataset.
Figure 1: Final training loss and testing accuracy for all algorithms, as participation ratio and data similarity varies. (a) and (b) show results for SNLI and Sentiment140, respectively.
algorithms on natural language inference with the SNLI dataset 4 and sentiment classification with the Sentiment 40 dataset [5]. More experimental results can be found in Appendix C
6.1
Setup
All experiments use uniform client sampling, batch size of 64 (on each client) and the multi-class hinge loss. See Appendix C.T for full details on hyperparameters. All experiments were implemented in PyTorch and ran on eight NVIDIA V100 GPUs.
a 3-way text classification task, in which the logical relationship of a pair of sentences must be classified as either entailment, neutral, or contradictory. The dataset contains 570k centralized dataset, we follow the heterogeneity protocol in [24 to divide the dataset into clients according to a similarity parameter between 0% and 100%. According this protocol, 5% of each client's local dataset is allocated from randomly shuffled set of examples, while the remaining (100- 3% is allocated from a set of examples which is sorted by label. this way, the similarity the label distributions of client datasets grows with s. The network consists of one-layer bidirectional RNN encoder followed by a three-layer fully connected classifier. train for 5375 communication rounds with 4 for all algorithms except NaiveParalleIClip. which uses R 21500 and I 1, so that every algorithm runs the same number of training steps.
SNLI SNLI
pairs of sentences. Because SNLI
Sentiment140 Sentiment 140 (5] is a sentiment prediction task designed for FL. The dataset is comprised of tweets, each labeled as either positive or negative. We follow the data processing steps of 28 to discard users with small datasets and split into training and testing sets. order to control the data heterogeneity between clients, we follow similar protocol described for SNLI to form client datasets by combining the datasets of original users in the Sentiment 40 dataset. The process is nearly identical to that of SNLI, but here we allocate users to each local dataset instead of examples. %% each client's ss local dataset allocated from a randomly shuffled set of users, while the remaining (100- % is allocated from set of users sorted by the proportion of positive samples. We train for 2000 communication rounds with / for all algorithms except NaiveParallelClip. which uses R = 8000 and I 1. We use the same network architecture as SNLL

---

SNLI
Sentiment140
0.8
1.0
Test Accuraty
Test Accuracy
0.75
Train Loes
0.8
Train Loss
0.6
0.6
0.70
0.6-
0.5
0.4
0.4
0.4
0.65
2000 4000
2000
4000
1000
2000
1000
2000
Rounds
Rounds
Rounds
Rounds
EPISODE++
CELGC
NalvoParalleiCiip
Clipped Minibatch
SCAFFOLDCIIp
EPISODE
Figure 2: Learning curves for SNLI and Sentiment 140 under the setting S = 4, 30% (SNLD and $ = 4, 10% (Sentiment140) 40). For NaiveParalleiClip. show the first 5375 (SNLI) and 2000
(Sentiment14)) rounds to compare all algorithms with a fixed number communication rounds.
SNLI
Sent140
Method
Train Loss
Test Accuracy
Train Loss
Test Accuracy
EPISODE+
0.317 = 0.001
83.89 + 0.07
0.258 + 0.004
77.97 = 0.16
CELGC
0.529 = 0.005
77.45 0.37
0.493 = 0.005
76.36 + 0.18
NaiveParallelCIip
0.377 + 0.001
81.74 + 0.09
0.365 0.004
77.73 + 0.07
Clipped MinibatchSGD
0.642 + 0.008
72.74 + 0.20
0.549 + 0.004
75.10 + 0.27
SCAFFOLDCIip
0.424 + 0.002
81.11 + 0.06
0.431 + 0.001
77.38 + 0.16
EPISODE
0.455 = 0.005
80.24 = 0.13
0.466 + 0.003
76.89 + 0.17
Table 2: Average results for three trials under S = 4, 30% (SNLI) S = 4, 10% (Sent140). The error is the distance from the average to the max/min across three runs.
We study the effect of client subsampling and data heterogeneity by varying each of these values in controlled way. We first fix the heterogeneity number participating clients = and vary s (10% 30%,50% It should noted that the experiments with varying S, we always train for fixed number of iterations R/. This means that separate training runs with different will have the same per-client computation cost (number of gradient computations), but the total computation cost of training run scales with S. For this setting, we use = 8 clients.
30% and vary S (2, 4, 6,8). then we fix the
To simulate large-scale federated learning, we also include results with larger number of clients N 128. For this setting, we use 16 participating clients in each round, and data heterogeneity of 30% (SNLI) and = 10% (Sentiment140).
6.2 Results
Figure T contains the final training loss and testing accuracy for the variety of settings of client participation and data heterogeneity. For a single setting of participation and heterogeneity. Figure and Table 2 show learning curves and average results over three trials, respectively. More learning curves are given in Appendix C.2 Learning curves for large-scale experiments are shown in Figure 3 EPISODE++ achieves the minimum training loss and maximum testing accuracy of all algorithms in nearly every setting. Only with full participation S = 8 does MaiveParallelClip achieve lower training loss than EPISODE++, but EPISODE+ maintains a higher testing accuracy. Also, NaiveParallelClip requires much larger communication cost than EPISODE+ to perform the same number of training iterations: when the number communication rounds is fixed, EPISODE++ significantly outperforms NaiveParallelClip.
Effect of Subsampling The first two plots of Figures [[a) and [b) show the performance each algorithm as the number of participating clients S varies over (2, 4, 6, 8} with fixed data similarity 30%. Clipped minibatch SGD, NaiveParallelCCipp and EPISODE all exhibit degraded performance as S decreases, whereas EPISODE++, SCAFFOLDClip. and CELGC maintain relatively constant performance as decreases. Despite the constant performance of CELGC and SCAFFOLDClip under client sampling, both algorithms are significantly outperformed by EPISODE++

---

SNU
Sentiment140
0.8-
1.0
Test Accuraty
Test Accuracy
0.75
Train Loss
0.8
0.7-
Train Loss
0.6
0.6
0.6-
0.70
0.5
0.4
0.2-
0.65
0.4
0.0
2000
4000
2000
4000
1000
2000
1000
2000
Rounds
Rounds
Rounds
Rounds
EPISODE
CELGC
NalveFaralleeCiIp
Clipped Minibatch
SCAFFOLDCIip
EPISODE
Figure 3: Learning curves for large-scale training with N = 128, S 16, and s = 30% (SNLI) or 10% (Sentiment1400). We compare all algorithms with fixed number of communication rounds.
Effect of Heterogencity The last two plots of each row in Figure I show each algorithm's per- formance as the data similarity a varies over (50%, 30%, 10%} for SNLI and (20%, 10%, 0%) for Sentiment 40, with fixed S = 4. For both datasets, decreasing data similarity negatively impacts the performance of clipped minibatch SGD, CELGC. and NaiveParallelClip. EPISODE++, SCAF- FOLDClip, and EPISODE are able to maintain performance data similarity decreases, though EPISODE+ maintains a significantly better performance than SCAFFOLDClip and EPISODE.
Large-Scale Experiments With larger number of clients (N 128, S 16), the relative performance of each algorithm is similar to the N = 8 setting, as shown in Figure Here, the proportion of participating clients S/N 1/8 is smaller than that of the N 8 experiments, where S/N 2 1/4. This suggests that the effect of partial client participation may be stronger in the large-scale experiments. EPISODE+ still outperforms all other algorithms in the large-scale setting, while maintaining about the same test accuracy as the N = 8 setting, demonstrating the effectiveness of EPISODE++ large-scale federated learning.
Comparison with Ablations By comparing EPISODE++ against the closely related EPISODE and SCAFFOLDDCip,. we can see that the use of information from previous rounds and episodic gradient clipping are both critical for the superior performance of EPISODE++ EPISODE only utilizes information from the currently participating clients, ignoring information from clients that participated in previous rounds. As result, the performance of EPISODE degrades S decreases. On the other hand, SCAFFOLDClip determines whether to perform clipping individually for each local step, as opposed to the episodic gradient clipping of EPISODE++ and EPISODE. Although SCAFFOLDClip maintains performance under changes in the participation ratio and data similarity, the level it maintains is significantly lower than that of EPISODE++
Communication Cost NaiveParallelClip suffers large communication cost for the same number of training iterations compared with other algorithms, due the cost of synchronizing clients every iteration. As shown in Figure and Figure 3 EPISODE++ outperforms all other algorithms by wide margin when the number of communication rounds is fixed. Also, EPISODE requires twice the number of communication operations per training round, which doubles the time required for communication per round compared all other algorithms.
Conclusion
We have presented EPISODE++. the first algorithm for FL with heterogeneous data and client subsampling under relaxed smoothness. We proved that EPISODE+ finds an e-stationary point with high probability, and its convergence rate satisfies linear speedup and resilience heterogeneity while enjoying reduced communication. We also presented a lower bound showing that the convergence rate of a special case of clipped minibatch SGD our setting suffers a dependence on A (the maximum gradient norm of the objective in sublevel set), implying that applying gradient clipping to minibatch SGD does not alleviate the problem exploding gradients. Our experimental results for RNN training on text classification tasks demonstrate the superior performance of EPISODE++ compared baselines. One limitation our current work that our lower bound assumes a and we plan to get better lower bound in the future for a >> 0.
10

---

Acknowledgments and Disclosure of Funding
We would like thank the anonymous reviewers for their helpful comments. Michael Crawshaw supported by the Institute for Digital Innovation fellowship from George Mason University. Michael Crawshaw and Mingrui Liu are both supported by grant from George Mason University, Computations were run on ARGO, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https://ore.mmu.ddd)) The work of Yajie Bao was done when he was virtually visiting Mingrui Liu's research group in the Department of Computer Science at George Mason University.
References
[1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1-2):165-214, 2023.
[2] Yajie Bao, Michael Crawshaw, Shan Luo, and Mingrui Liu. Fast composite optimization and statistical recovery in federated learning. In International Conference on Machine Learning, pages 1508- 1536. PMLR, 2022.
[3] Rémi Bardenet and Ambrric-Ambrym Maillard. Concentration inequalities for sampling without replacement. Bernoulli, 21(3):1361 1385, 2015. doi: 10.3150/14- URL https 7/doi.org/ 3t1p://..11/////// 14- BEJ605
[4] Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Con- ference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 2015.
[5] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1812.01097, 2018
[6] Wenlin Chen, Samuel Horvath, and Peter Richtarik, Optimal client sampling for federated learning. arXiv preprint arXiv:2010.1372. 2020.
[7] Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the convergence of federated averaging with cyclic client participation. arXiv preprint 20X::2230..03109, 2023.
[8] Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 2022.
[9] Michael Crawshaw, Yajie Bao, and Mingrui Liu. Episode: Episodic gradient clipping with periodic resampled corrections for federated learning with heterogeneous data. The Eleventh International Conference on Learning Representations, 2023.
[10] Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34:4883 4895, 2021.
[11] Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 12:13601-13612, 2019.
[12] Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: stopped analysis of adaptive sgd. arXiv preprint arXiv:2302.065500 2023.
[13] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning. In International Conference Machine Learning, pages 3407-3416. PMLR, 2021.
11

---

[14] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International Conference on Machine Learning, pages 1243- 1252. PMLR, 2017.
[15] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[16] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Progrumming, 156(1-2):59-99, 2016.
[17] Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. International Conference on Artificial Intelligence and Statistics, pages 9050-9090 PMLR, 2022.
[18] 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, pages 11080- 1109,, 2019.
[19] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: 1811 1.03604, 2018.
[20] Elad Hazan, Kfir Y. Levy, and Shai Shalev-Shwarte Beyond convexity: Stochastic quasi-convex optimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPSS' 15, page 1594-1602, Cambridge, MA, USA, 2015. MIT Press.
[21] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
[22] Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, pages 2525-2536, 2018
[23] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning, Foundations and Trends in Machine Learning, 14(1-2): (1112))122 2021.
[24] 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 on Machine Learning, pages 5132-510 1132-114. PMLR, 2020.
[25] 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, pages 4519-4529, PMLR, 2020.
[26] 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 Machine Learning, pages 5381-5393. PMLR, 2020.
[27] Kfir Levy. Slowcal-sgd: Slow query points improve local-sgd for stochastic convex optimiza- tion. arXiv preprint arXiv:2304.04169, 2023.
[28] 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, 2020.
[29] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint A90iv: 189, 2019.
[30] Xiaoyu Li and Francesco Orabona. high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007.14294, 2020.
12

---

[31] Tao Lin, Sebastian U Stich, Kumar Kshitjj Patel, and Martin Jaggi. Don't Itn't use large bani-batches, use local sgd. arXiv preprint arXiv:1808.072117 2018.
[32] Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-effiiieenn distributed gradient clipping algorithm for training deep neural networks. Advances in Neural Information Processing Systems, 35:26204-26217, 2022.
[33] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efficienf learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[34] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference Learning Representutions, 2018.
[35] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In International Conference on Machine Learning, pages 15718-15744 PMLR, 2022.
[36] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. corr abs/1211.5063 (2012). arXiv preprint arXiv:/211.5065 2012.
[37] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty training recurrent neural networks. In International conference machine learning, pages 1310-1318. Pmlr, 2013.
[38] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
[39] Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. arXiv preprint arXiv:2303 00883, 2023.
[40] Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 850-857, 2014.
doi: 10. 10.100//ALERTTON22144...7 27028444...
[41] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv:/805.09767, 2018.
arXiv preprint
[42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[43] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication--ffficeenn sgd algorithms. arXiv preprint
2018.
[44] Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation. In Annual Conference on Neural Information Processing Systems, 2022.
[45] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai. Brian Bullins. Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[46] Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. arXiv preprint arXiv:2102.01583, 2021.
[47] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 2020.
[48] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint arXiv: 1wrXiv1190... 1905.098177 2019.
13

---

[49] Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344: 2020.
[50] Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference Machine Learning, pages 12253-12266. PMLR, 2021.
[51] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511- 15521, 2020.
[52] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
[53] Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A feder- ated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. /418, 2020.
14

---

A Deferred Proofs of the Upper Bound
A.1 Notation and Preliminaries
Let % = O, yo. = To, and define
i S otherwise
00- =
(7)
d--1
and
x - 1
E
y =
(8)
otherwise
The intermediate variable g.. is the most recent round before (not including) round in which client i participated. Similarly, Vi. is the local model at step during the most recent round before (not including) round in which client i participated. Then know that yo x zg Therefore
G - V (q..)) Also, will initialize G v (a (t)
for all clients.
Denote by A, = G/ < }) Our analysis simplified by taking the following conditions throughout the proof:
(K 1)ml ALo BLik 4BL 20 + ++2) =
1
60
C
2(K + 1)1 (2on + 7)
Li
where C> a constant, and are defined in terms C (see Lemma D) and K defined in
Lemma 8 Usage of these conditions will be explicitly stated when used.
Through out this section, we denote the filtration
J, = ((ESNEtN) (E), 9 r, (M)))))
We = FF] and (P,(.) to denote the conditional expectation and probability given the filtration F,. Notice that, given Fr, the global weight ā, is fixed but the subsampling set S, still random and is independent of F,,
A.2 Auxiliary Lemmas
Lemma 2 (Corollary A.4 in (TI). Let f Ed be (Lu, L1)- and C > O. For any x, y E Rd with ||0 yll T
[V f(())) S (ALo + BL, BLIl()() - -yll.
where 1 E and B Eبع
Lemma (Lemma A.3 51). Let f Rdd be (Lo, Li)-smooth and C > For any æ, y Rd with [ yl1 S f.
f(y) < f(x) + (V/(z), + ALa BLI
x y11
2
where A= 1 c ل and B ب
Lemma 4 (Lemma B. in (1)) For any μ 2 0 and x,, y E Rd.
x
|
y
< - ا|||||
اiaاll + (1 + 11lyy - x1).
Lemma 5 (Lemma in 301.. Assume that Zn.... .., Zo is a martingale difference sequence with respect to the filtration F. and E, [e[epp( /2//2 oo?) I cxp(1) for all where di....,07 Or is a sequence of random variables such that o₁ E Ft. Then for any fixed x > 0 and 8 E (0, 1), with probability at least 1 - 8.
T
T
1 log
Z,
o +
1=1
15

---

Lemma 6 (Improved Serfling's inequality, Proposition 2.3 in B.. Let X' = (Z1...., IN) be finite population of N real numbers and X1, XI.....2 Xn, denote random sample without replacement from
X. Let p.x. N Li ii Li, 0 = N Di i= (xi - u)?, and fin 1 -i=1 X,. If maxxeI] |æa| S b,
N
then for any X > 0.
[2 n + n²
(1 (1- ))
Blexp(A((nn ux)iI S exp
Lemma 7 (Lemma 12 in (00). Suppose XI..... Xy is martingale difference sequence in Hilbert space such that || I b almost surely for some constant b. Further, assume Et-1 x,,1l1 s of with probability for some constants Jt. Then with probability at least - 36, for all k:
Σ
& X2
S 3b max (1,108 1
+ 3
Σ t=1
of max 1, 1, ;1)
t=1
A.3
Proof of Lemma
Define
E
a yr
E, is the average "lag" (over clients) of the correction G behind V ((xr) due to client sampling, since each G is set according to stochastic gradients at V
For any 8 E (0, 1), define
Ing
RX
S< N
K
log
N-3
==N
and
E OSPSR-LISISN
max
r S S K
(10)
The event occurs when every round in which a client is sampled occurs after no more than K rounds following the previous round in which that client was sampled. This means that under &, the correction G was computed within K rounds of round r. The next lemma shows that & occurs with probability 8.
Lemma 8. For any with 0 < 8 < 1, P(E) 2 1-
Proof. If S = N, then r of = 1, and we are done. Otherwise, since each round's participating clients are sampled uniformly without replacement and independently each round,
P(r Φf S k)
P(r gf =i)
Σm
k
Nv (1
1-1
k<r
otherwise
S
5
1
N
S
(1
$1 )*
N 1 -
(1
1
S
N
16

---

Also by the choice of K: K
log 4x4) log(
N we can show that
(1-N)*
S
5 RN.
So P(r 8/ 1
K) 2 1 RN Therefore
R-1 N ΣΣ
PP()) PP (r of S K,
2
- k)
r=0 ml
Lemma 9. Letr 2 0. @ y 1 s
C In
for i E [N] and k E I-...,,,-1,,, and BLi < 1,
then
[V(()))|| 5 G, + (ALo + BL
BBI1E,
Proof.
Due the assumption || yr S G. have
[V S IV)()))
G.1l+
N
VV((a,) - + |G,||
N
1-1
VV( VR Sy xll + |
NI
0=
N
[V(())) V1(C))) NT
V
||,,||
NT
N 1-1
(ALo + BL, Vf((E,
v + |
NI
Am
(1)
(ALo + BL + V((
Σ
| - +
0=
(ALo + (L +
|Grll.
where we used Lemma in (i) and Assumption iv) in (ii). Rearranging to isolate |[V((,,)] gives the result.
L
Lemma 10. Suppose that Equation 9 holds, then for any E [N] and k [T]
j Toll S 27 (2mm +7)
(11)
Proof.
Notice that, due to the clipping operation,
Ao T
To = key & 22(2on + 7)-
(12)
holds for any l: 5 T. Next we verify Equation the case = 1,
11 under the event Ag. To see this, first consider
Ao ||
Tool A. 7 (o.
G + Goll
< 1 (n V
+ G -
f. + Goll)
< 2on + 7,
where we used the initialization G (Zv;; and | < under the event Ag. This indicates that Equation holds with k = 1.
17

---

Now suppose that Equation 11 holds for some l with S A < I. Then we have
A 1| - Toll A A (VF 50,k) Go + Go) -Zoll
< Ao (11=0bx Boll 7) V (F,
Go Goll)
(6)
- 1.40 || -Boll + // k0
V ( + / Gú V()()))]
+ n1 V ff(( + 7| Goll
(9)
Ao (11zi Boll + V/ ( [i(
1 Ao (11=iox - Toll + + + BL, VV
- -
< Ao (1=0b. Boll + 2on + 7 + BL (x + I (a)a(a)))))lzz 2o
where (i) holds due to the initialization Go (Zo: (ii) follows from |ooll S 7. and (iii
follows from Lemma Note that the conditions of Lemma 2 are satisfied here by the inductive hypothesis together with Equation 9
Notice that En 0, so by Lemma we have
1 N
[x.lV $ ||oo Vf(ft))l + I S
VF((oo:)))
7 s ?
N
Therefore
ALD BLA + BLu (o+?) 2)) 1 Bul
A [|
Tbll < || Bull + 2an + 17
(4)
$ | -Boll + +220 + 7
| Toll
41
(1+
1
2on + 7 +
2k 2k(2 + 7)
41
k
2 kt +
+ 2
(2on + +
41
< 2(k + (2 + 7)
where (1) holds due to Equation 9 and (ii) holds because of the inductive hypothesis that Equa- tion holds for k. This completes the induction over k under the event Ag. This fact together with Equation 12 proves that Equation T1 holds for all k I....,I.
Lemma 11. Suppose that Equation 9 holds. If maxkel) 1 2zll S 2I + 7) holds for any
q S r 1, then we have
1. max
| 2r 21(2on + 7), for any Sr.
(13)
kEll
Ie max ke[l]
Il - æ. < 2(K + 1) (2an + +7,, for any E [N].
(14)
18

---

Proof. Under Ar, Equation 13 trivially holds due to clipping. Next we verify Equation 13 under A,. First consider the case k
1, || | - Er-l
1. MIl (a C,,
G
1-1
1 1 (a)( Σ
VR (
+ +nLA,11G,1
k=
S V (r, (.,
Vf((),)))
|
S 2on + 7 Σ
"
[V)(
-VA(E,
(15)
k=
Recall that V o from the definitions Equation 7 and Equation 8 so
j,, kl I |,,, - TGi1l 11 + [8a - Fzg. 5
| Titt Tigll + 1z
9=
(0) (r 4f)21 (20n + 7) + 2k(20n +
(6) 2(K + 1)7 (2on + +7)
(00)
(16)
T
where (i) holds due to inductive hypothesis for rounds E r0..; (ii) holds due to the event such that r of S K; and (iit) follows from Equation 9 The above bound on I| y verifies
Equation 14 and shows that the condition of Lemma 2 satisfied. Then applying Equation 15 yields
2, 1, $ 201 + + + BL, (,,
Σ o. h=
vi
7
$ k
+ 1), I(ALo + BL + BL v((e + 7) (1 + 2(K + ())/ BL1x A.
(2om + +7), (17)
where we used Equation 16 and Assumption D (iii) and (iv). Invoking Equation and Equation I6 gives
1
BLIE = BLIP
- - D s 2(K + 1)BL) + +2) S 2
NT
Am k=
Therefore the conditions of Lemma are satisfied, and we can bound [VV((,))| as follows:
1 + (ALo + BLiN)E,
[V <
1 BLIPEr
7 + (ATo + BLIx)E,)
22
77
2
σ
+
7
+ +2(K + +1)[(ALo + BLox)(2on + 7)
22
2x + ?
(1+2(K + 1)n + BL(k))
54
20 +
(18)
17
19

---

where we used Equation 9 Finally, plugging back into Equation 17 yields
( 22 + ++2)) 1)) (2om + +7)
||,) - A. <
1 2(K + 1)n/ [ALo + BLIk + 4BLi
s 2(2on + +),
where we used Equation 9 again. This proves Equation 13 for the base case k = 1.
Now suppose that Equation 13 holds for some with < I. Then
|,// T. = AA x r 7 (VF. (. G.) -rl
1 1 1e (1| ||, 2, ll + n/1 (( GG,l)
- 1 (11 - ærll + n/
v)(()))))))
1-1
+ 1r 1
1
Sp V fv(t)))
1=0
1-1
+ 1A, 1
7
[ - V + +
1=
S A. 1 -
+ 20m + + + [V -
1-1
+ LA I
11
[f.)) - v
(19)
1=
where we used ||, |l S I under the event A, and Assumption (iii.. We can individually bound
3) each of the two terms La, VV hypothesis over k together with Equation | æ,1l < 22 + 7) s L
V (ā Il and A, IV (z.) v fi(t..) Il- By the inductive
So we can apply
Lemma and obtain:
[V((()))))) VI(
3 LAL + BL, (V)
- x-
s LA (ALo + BLIK + BL V ff - Zrlll
s 1 AALo BLIx ABLIP
20 + 2 || ær-ll
< 4nj | - Erll.
(20)
where we used Assumption T (iii) and (iv), Equation 18 and Equation 9 Similarly, by the inductive hypothesis over
C
||,, vr S ||,,- - zz + [0 ااررب s 2(K + 1)T(2on++ + 7) $ L
So we can apply Lemma
[V/( -V/(,)))/(()))))) (ALo BLi [V)(( B, v''ill
< ATo + BL + 4BIap
<ATo
20 + 7 2)) ||., viull
4(K 1)ml |., v
(21)
where the last inequality follows from the assumption Equation
20

---

Finally, plugging Equation 20 and Equation 21 into Equation 19 gives
1.,. (4.1100,,+111 Fr-l < 20n + 7 + (1
1
T. + 4(K + 1)12 |
1
Σ
a. yisll
47)
j=0
1-1
1
< 20n + + 2h
1+
(2on +2) + 4(K 1)12
2(K + 1) +
41
j=0
k
2 +
4
(20T) +7)
41
2(k 1)(2nn + +),
where used the inductive hypothesis over lt and the inductive hypothesis This fact together with 1 A,, ||ar) ær|| S 2(k + (2mm + 7) (which trivially holds due to the clipping operator), we prove that Equation 13 holds for + 1, completing the induction over k. Therefore Equation I3 holds for all & [T]
Lemma restated. Suppose that Equation holds. Then for any 2 0 have
Ig max ||ac) kE(1]
æ.|| s 21(10)) + +)) for any i Sr,
(22)
Il max kE[1]
Trll s 2(K + 1)7 (2om +)); for any i [M].
(23)
Proof. We will use induction to prove Equation 22 by a induction over r. And Equation 23 holds
consequence of the inductive assumption due to Lemma [1 Invoking Lemma T0 can verify the base case of the induction over т. Now we assume maxxe[]]]ie[[[]
||=]) 7. T,, S
2(K + 1)I (2om + 7) holds for any S r 1. Then according to Lemma 11 we can prove Equation 22 and Equation 23 immediately. It also completes the induction of Equation
22 over
0
Corollary 2. Suppose that Equation holds. Then for any 2 0 and E [N].
7
1 < 2(K + 1)nT
(24)
LE (Vf < 20 2
(25)
1
I MEnA.IVSJ(E, G $ 2n + 30m
(26)
LEnA, IVf G, $ 20 +
(27)
301j
Proof. All proofs of this corollary are under the event E. Equation 24 follows directly from Equa-
tion 14 and the definition E, N Σ Ek= ll ær Equation 25 is exactly Equation 18
Due to Lemma
we can apply Lemma 2 such that
L
(f,(z,) VA(UAal
V - VF, ci (q)
< 1s
(ALo + (L I|) | wiuull + o
K=O
< (ALo BLik BL V )I} to.
21

---

So, using Equation 24 and Equation 25
20 20+?3 2)
(ALo+ BLN + 4BL,p (20 20 + 2)) +
1884, VV.((,) G - 2(K + 1mml
20 +
to a
30
7
2a +
30vj
where we used Equation
Equation 27 follows immediately from Equation 26 by
LEnA. V
1
18ns, (V,) G < 20 + 7
N
30m
A.4
Proof of descent inequality
Lemma 12. Suppose Equation holds. Then with probability 1 - 156, Algorithm 7 satisfies
f(xR)
f(0))
R-1 1
+ 216BL, 2 2 Ilog }
$ Σ 1A.
8 17 ([
22 + 1) 17
[[
r=0
20 + 2)²
2
108 2172 2 log
+ 16/
S
R 1
3 -76 (3
2BL BLysT [(
Ar
r=0
17
6o 2ALo71 - -/2 12 }BI1mor))
-7
1
20 + ;))
2
S )))
+ 1
120 + 64T
K (k+ 5p
log 8¹
where P1 = ALl + BLIK + 4BLip 20 +2) 2)
Proof. By Lemma P(E) 2 1 6. The remainder of the proof will suppose the event happens, and the results will hold with probability 8. By Lemmal and Equation 9 |
Er S L
Denote A, = G|| || < 7/n}. Therefore we may apply Lemma obtain
f(8,41) f(x))
ALo + BL
(V)(o)), 2r+1 Tr))
2
$-1Am1 vf(2,))
1
Σ +ΣΣN
gi.k
1
Vf(ā,), 1 Σ
gi +
iES. K=0
ieS, k=0
ALo + BL,
V fI
ALo + BL,
V (xx
1
|
-xrl1 + 1
[ - 1r11
2
2
22

---

Summing over r = o..... R 1 yields
R-1
[()n) ((xo) S -
Σ A.
V)()));
1
ΣΣ gik
5
r=0
rES, k=
Ai
R-1
I
1 AA.
(.(Tr):
S
g
iES, h=0
A2
ALo BL IV [V,,,,]
1.
1441 1.11
R
ALo + BL, IV (z,)
1
Tr41 12112
(28)
2
r=0
We proceed by bounding each of the four terms Equation 28
Bounding A1. Denote
C (F k.kk - Vf((zf())
1 Σ G. -Gr,
iES,
1 Σ
Vz( -Vf(a)).
FES,
Then we can write
1
Σ
g
1
Σ VF
1
Σ
G +G
S
5
S
EES
iES.
iES,
Σ
1
c (1)
3
5
iES.
iES.
5 Σ ((())))
+ [(Vi(( v)((E)) + Σ e (1)
1
1
5
3
iES.
iES.
ieS.
Vf(e,) { E + Σ
(VA((t))) -V((E))))))/(()))))))))))
+ S Σ E
S
iES,
23

---

It follows that
R-1
A = -
Σ
1A
Σ
Vf(z+);
Σ
giik
s
r=
k=
iES
= R-1
R-1
A (()
Σ 1
(/((.)):
Σ
Viilat,)))) V(((a))
5
VES,
11-
(((tr))
Σ
t
Σ
1A,
(Vf(ār). - -
3
iES.
r=0
R-1
[. - 1/ Σ 4
[
1
Σ
V(i(at+ v\((o,))
5
iES, k=0
1 Σ
)
|
|[1 Σ
IA (VI(E.),
(((t))
7
5
67,k)
k=
VES.
r=0
R-1
+ 7/
Σ
LA, (vf(tt).
(29)
Since ||a;;, - -,,ll S C/L, due to Equation 13 we can apply Lemma 2
such that
R-1
A (((,))
1
Σ
V [((()))) - V.(C.))
5
iES, A=
- /
LA. [(,
[)(())))))))) -
17
iES,
Σ Σ
[ - v(
S IES. K=
S 17
LA [V
3
Σ
Σ | - I+
0=
EES.
R-1
2 22
10 7)
?)
Σ
LA LT. + BL + BLa
17
-=
(1)
< 20 22 (ATo + Blak))
22 20+?
?
R-1
Σ
17
0=
1--
+
20 20022
2
Σ
1 [V
17
0=
(10)
R-1
1 R-1
< 2n7² (2AL + BLI
20 (20+2) 1
Σ
1 |V
)1 +
I (E,,,)
0
P=
24

---

where (i) holds due to Equation 13
ii)) follows from Assumption iv); and (iit) follows from
Equation Plugging into Equation
R A1 $ 7
R-1 Σ
14, VVf(2,) (ALo + BL1
20 + 7) r=u
14 Vf(2,))
r=
R-1
Σ E E
+
(ā(z));
1=
k=0
vES
B1
R-1
+ 7
Σ 1A, (Vf(Er).
R-1
+ 7l 1A. (V)(E,),
Σ
(30)
r=0
Bs
Denote each of the three last terms (those involving E er and Er respectively) as B1, B2, B3. B1 can be bounded using the martingale concentration bound Lemma Denoting Gr oFFr, Sr. (S i E Sr, s k))), we have
E AA
VI(x,); 5
Σ tre 1
XES.
so that { (IA. (v)(z)). 1 Eies, </r)) r,
is martingale difference sequence with respect to 9r,k-
Since 14, F, E Gr.k for any S I, we have
(f(a))) 1/2 Lies, stae)
1A
E
exp
1 V
grak-1
Eies, ||e Gra-1
< exp
o²
< exp(11,
where we used Cauchy-Schward Jensen's inequality, and |||| S a. Therefore we can apply Lemma to obtain
R-1 LA IV)
3 B S no IA
Σ r=0
" A1 g'
log
(31)
with probability - 8 for any \ > 0.
The concentration bounds for B2 and B3 will rely on the concentration bound for sampling without replacement in Lemma We start with By. Notice that
L (V) 1 (L. ( Σ 1 (V)(E,)
(32)
iES.
25

---

so we must upper bound 11.1(V/(a G to apply Lemma 6 Under Ar,
|| < [V
/V
G
< K + / |
G
(1)
-
2 + 2
S S 4p 20 +
11
+
")
20 + 2
S + (4p + 1)
68)
20 + 2)
5p
(33)
17
where (i) holds due to Equation 25 and Equation 26 and (éi) holds since p 2 Therefore
G < k + 5p 20 + 2 14,1 V
1A. IA.((V((e,),
and the condition of Lemma 6 is satisfied. Notice that A, E F, because G, is constructed by the history gradients before round Therefore, applying Lemma 6 to Equation 32 give
ee a, (V (V((z,) fxx,),c.)) c,,
20 + 2
=)
2 $11
(1- (1- N LA (V
S exp
k + 5p
2
11
52
2
2
[s - N 1A, 11 [
S exp
\
Ki k 5p
20 +
11
S
=: exp {}
(34)
Let
Σ 2o (V((a)) (()) - rell.)
Y, exp
9=0
y, exp
).e))...) (()) Ng.oa.
Then we know EY(Y) < - by Equation
34 which implies
E[ 1| = E[ER- (Y
E\ 2) S S E(Yo < 1.
Therefore for any A2 > 0, we have
R-1
R-1
1
1
P
Σ
Ia
(Vf(a))))))))
A2
M,
log
A2
T=0
R-1
R-1
1
P
A2
1 (V (1)
Σ
Mr + log
2 11
P
exp
A2 (1d - X2M,,) ->2M,)
1=
1
= P Yn-1 2 7
56
where the last line uses Markov's inequality. Repeating this argument for - -1,, (V((e)), we can obtain
R-1 P
R-
log 1
Σ
A
Σ
M,
2 1 1-26,
0=0
'Here E-[-] takes expectation over the randomness of subsampling, that is S..
26

---

which means that
B2 m/ + 5p 20 + )) (s N
2
N
Σ
1 Vf( + 7!
1
log
(35)
A2 8'
holds with probability - 26.
The same argument can be applied to B3. Notice that
N
AA (V.(()) S 14, (Vf(E.). V.((a))
Σ
Σ
LA (V. Vf(za))
N
iES,
so must upper bound we have
LA, (V.(((. (T.))) )) apply Lemma
Using Equation 25 in Corollary
AA V.( k p ( k 40 20 ;
20 + 2
S x 5p
This matches the corresponding upper bound in Equation 33 from the bound of B2. We may therefore apply an identical argument in the case of Bg and obtain
B3 S nl + 5p
20 + 2
1 S
Σ
LA
nI 2
log
(36)
A2 8"
17
r=0
with probability 25.
Combining Equation 31 Equation
35 and Equation 36 into Equation 30
yields that, with probability
1 55,
A1 S -n 7 3
2))²²
2
(
1)
Σ LA
0x01
x1
222 n kx 20
120+ + 17
(+
5
21j² (ALo + BL2K)
(20 20 (20+73 + 2)
R-1
Σ
1 [[ +11
+
27
log
1
17
A1
Ao )
8
3 R-1
1-1
S - n! Σ V
+ 2n 12 (ALo + BLTR)
20 (20
2
Σ
1 (f(+))]1+
4 0=
17
r=
5p 20 + ))
" 120² + 641
log
(37)
S N
8'
where we chose
\
12
A2-
32 k x 5p 20 + 2, )) 2
( - +
Bounding A2. From Lemma 4
L'M farr)
S <-MIVV[(E))1 (1 و)lاا + (1 + +)llg -Vlli.--V((..))
|
for any / 2 0. Also,
A. x = 1 VF ( - G.
2 1x,
(I|,,| -
2 1x
2 - -| 4i ( V/i(+,,,)|
- vA,,-)) -V V/ - GH1l
17
11.
[ (ALo +
||0 - = - V/.(..) - G
"
I I(ALO + BL + BLaP / G
2 1x
11
27

---

and
11 x.
11.1 -V)(a,) A. | G. G. V/(aa))
$ 11. (I/Fi -
+ +| - v)(ā))])
< A. (IV k7,
)| + [[[[(( V...a))
1 N
+ V).( G. +
Σ
G v.3
N
S A. a + (ATo + BL, V Si (., }|} | - -
N
+ / - G:ll + N Σ G - (F)(
I 1 A. 0 ( + BL V[
+ (f((a))) G:ll+ + 1 N
Σ
G vF)(E,)))
N
j=1
Therefore
gi.k
- -11 ([(
19
$11. (- 11-1)) 20 + 2o + 27T(A + BLix + (La.))
1
+2[V G. +
1 1+ 1
Σ
G. VV,(
N
and
-11 5 Σ
|1 11
iES,
< 1AA,
[ -(1-)) + +2 + 27L(A + BL + BLIP + +(3+-1+++))) u) 220 11
30m)
< Ax
((m (
9
+
31
7
(5 + m) 1- + +BIak))
10
30
where we used Equation 26
Finally
R-1
Le g gi
A2 -2
Σ
1,
V
1=0
SES, ビ=ル
R-1
9
31
72I
Σ
1
- -7I [BLi
+
30
+ + +5 + + BLIN)
10
1)
-=0
R-1
| (3 2BL1P11) [V -
(17
66 - 27I( + BIaR))]
1x.
8
where we used the choice μ -.$
28

---

Bounding Ag. To bound As, we begin by bounding 14, 1 -x,112
A. (..1aT+ TT+1
17
Ir,k
5
iES, k=0
LA,7
VF, ( A St. - G; + G,
iES, k=0
+
+ + G.) +G, Vf(x,)) + V
iES, K=
5 V V
SES, k=U
k=0
1
+ 14
Vf(( - G.
+ + 2 ||, vf(2,)11
S iES.
I 411 4, V (1,)
1A
11,
( vz.)
IES, K=0
1-1 [(((,)) (Si('r
+ R81
5T
iES, K=U
N --1
+ 1-872121
v((1 - v((Et)
N1
1=1 K=0
T-1
1-1
N 1-1
+ 8
1
ΣΣ
+
ΣΣΣ
+
11
ΣΣ
8 IES
N
k=
IES. k=0
k=
(38)
where we denoted e₁ = = Equation 38 can be bounded with similar arguments as those used previously:
VF
(f( -
The first three terms on the RHS of
A
iES, k=0
< A1 S iES, K=0
V((() (., ²
< 111A 5
Σ
(ALo + BL, (f
2 - =x,l1²
iES,
(1)
20 + 2)²
1AAo + BLIN+ + BL BL (()
20 (20+3) L
f 2) 1A.1\//(E+)11 1
+ BLIN)² 20
(20 fo++? 2)
(0) 1
)
S 32
11 IVF( 18,1722
20 + 17
29

---

where (i) holds due to Equation 13 and Assumption liv); and (it) follows from the condition on Equation 9 Due to Lemmal we can use the same argument to get
1 +
20 ? ))
1A.
f((,)) -
SI
11)
iES, km
and
I ΣE
20 2 2)²
AA,
V
+4
NI
79)
Plugging back into Equation 38
20 + 2)²
1A, 1 - a,11² < 5n/ 12 [Vf + 14, 1921
+ 8
ΣΣ
+ +1
1/2
1
ΣΣΣ C
iES, K=
iES, k=D
N 1-1
+ 8172
ΣΣ
En
(39)
N k=
We can bound the remaining terms using the concentration inequality from Lemma We write the index of S, as fei,...,s) (9} For lo = O,... I and for j E [S], let X = s/,, and Hes+s =
Fr, Sr. e JosesR-1,ES.. ( for le 2 1, where (Ese 2. For any
1 kS + j. it holds that
E [ H4-1) E (r Has+s-1| = 1 BB Fr, (5. de..))))) = =0,
where the second inequality holds due the independence between different clients given F,.. Then (Xihers is martingale difference sequence with respect to {Hahers. Also, ||xM|l| < almost surely for all t E [TS] and [II S o². Therefore, by Lemma 7 with probability at least
1 1-
1) 8 30 log +3/ STo² log
1 Σ LES, k=0
1
S
S
52
20 log
9T02 2og2log!
B
52
S
2 1log
1
log
+1
S
SI
28x² log"
S
Without loss of generality, we assume log(1/6) 2 1. the remaining noise terms:
We can apply the exact same argument to bound
1
1802 flg
E
S
VES. k=0
and
180 1l02llog
1
1 log
N
N
S
'In fact, we first verify that the bound holds with probability at least - given F, and S,. Since the upper bound does not depend on F, and Sr, we conclude the bound holds with the same unconditional probability.
30

---

each with probability - 36. Plugging back into Equation 39
20 2
17 7) 4320 2 log 8
1A. 0r+1 2r|1² - 1,, 5n)² 12 V[Il( 1921
with probability 95. Also, using Equation 25
ALo 4BL1 220 + 2 11))
AALO BL, BLIIV aA
s 1A.l'1
Finally,
A3
1A, + BL, [V -1,11
2 T=U
R-1
Σ 1
2
961 (20 220 + 2)
2216(ALo + +BL (BL.IV((E.))
021)²1 log
5
R-1
216BL1021 [f((a)]
<
1A,
8 [(
2)
216AL 22 log
+ 1
20 + 2 7
S
with probability - 95.
Bounding A4: Due normalization of the update gh under Ar, have
ALo BL BLIIV[((E))
g
A1 A= Σ 1r,
2
S
g
iES, K=0
R-1
ALo + BL, Vf(E,)]
$ 2
Σ
1A,
2
r=0
Combining the respective bounds for A1, A2, As, As into Equation 28
f()R) f(xo)
216BL 2 log [v.(
1A
12
20 20 20+21 11
+
8
S
2 216ALoo 272 log
+ 1,
220+ 2
1
S
+
R-1
Σ
-71 -BBL {LLn) |V.f(z,)] - -71
(17 (1
66 - 2AL BLimor))
r=0
12o + 64I (n+ 5p
2) 20 + 7 2)) (s
1 N -
2) log 1
+ +
which is the desired result. Note that the bound on A₁ holds with probability - 56 and the bound on Ag holds with probability 96, and we initially supposed the event E, which holds with probability
1 8. So the overall result holds with probability at least 156.
A.5 Proof of Theorem
Theorem restated. Let < T6BLIP
ALe and E (0. Denote K
log(RN
r =
log(N/(N SSJ
ALa + BLA 4BL,p 22 + ?) and 12 64 (x 5p (2o +
2
{ }
If
7
1 90(K + 1)T1 32T, (74 + BL,P)
Se
A
1
1 min
min 12 T2J
ALe.
216ALoo log
log
31

---

and 7 (720
ALe Bl1e/ n, then Algorithm
satisfies
Er=D [V - 35e with probability
at least 1 156, as long as R 7
Proof. First, under our choice of 1 and 7,
1
(K + 1n S
60'
and
7)}
20
1 7
22 3
1
S 1
2(K+1)n] 20 -
S
300
30 + BLI + 4BL1p 20 +7)
(20
120BLrP
120L,
where the last line follows from B, p 2 Therefore Equation holds under our choice of 1) and 7, so the condition of Lemma 12 is satisfied. Denoting
3 U(x) -1 (3 2BLLIpP BLITL)
17 81 [Vf(())] -
60 - -2ALOTI
BL BLINTL)
2
and
216BL log
V(x) / -(=)=-~n<\\((()) + 12 20 + ?
|[f(x)]++
S
,6 20 + (1
216AL 2)
+
S
Lemma
12 gives us
R-1
((xR) - f(0o) =
Σ
U + IA, L. V(+,)] 12no² log 5 + Tinl log 8
(40)
r=0
We will bound each of 11, U (Z,) and A,, V (a.) under our choices of y and 7)
To bound U notice
3
3 5
2BL + BL s
BLI
3
5
BLip- 2
nl
2
7)
3
5 IBL
ALa BLiP
+
720 +
2
5
(72BLipo + ALo)
3
45 In!
3 1
2
4'
and
17
+ 6o + 2ALo + BLI
17
+ 6a + 1
2ALo + BLIK
5
8
81
1
=2
1 17
2r 1nn
+ 60
8 87
7)
7 + 6o
30
n
1
ALo
720 +
+ 60
12
BLip
0.
32

---

So
U@.,) --,,)==>\\\\
_ / / (a,,))1
where the last inequality holds due to the fact notice
S
Alp 16BLiP
S 72o +
ALa.
2. To bound V(
BLIP "."
2T 12
20 + 7
S 11
T 1n,,
1
since 1) 5 321, 1 (74o+
32r 32,, (20++)))))) ;) and
Akc. BLTe)
216BL10² 1 3/4
BL1 216ALg0"n
S
ALo
BL1 en
ALo
1
2 enpl
16
where the last line uses
ALa 162L
Lastly,
16BLip
216ALoo2 212 1721 log
20 + 2)
96111 91
20+
20 20+ 7)
216.A log 1
S In!
961 96
+
S
8 2 +22
n/
So
V(2,) n -=
1 [[)] + +32n
en + 4c-
where the last line came from the inequality x² > 2ax + a² with r = [Vf(a,)] and = e.
Combining the bounds of U (z,) and V(.)).
(ax) < 1 -() + 4e2
-
Plugging this into Equation 40 yields
R-1
f(æR) - f(0o) S enn Σ
[f + 4 + 12no log 5 + Panl log 7
0=0
and by rearranging we have
vf(#))11 < 8(S(wo) - ((TR))
960 log
81, log eR
32c
enlil
eldl
< 8A
+ 32c +
960 log
7
8T log 1
emRl
eRl
el
960 2 log
8T, log
< 33e +
(41)
cRI
eR
33

---

where the last line comes from R 2 pnd
Finally, 17 S
min
1 12o2 T27
implies
log $
8A
960 log 1
R 2
en1l
221
and
8A
81 log
R Z
1n
2
so
966 log
8T log
6
+
8
2c.
eRl
eR
Plugging into Equation gives the result.
A.6 Proof of Corollary
Corollary
restated. If, under the setting of Theorem !
we additionally choose
Se
A
1
" min
min
ALe 90(K + 1)T2 32T,1 + +
216 log
log
12
T21
BL,P)
and
27ALoo² log
I 1 4eT (740 +
ALa BLip
with
16 740 BLiP
ALa.
I8AALo
32AT;
(740 +
ALo. BL1o)
< min
45(K- + 1)
S
P32 log
then with probability
148, Algorithm
will reach an e-stationary point with iteration complexity
ALooo log 1 8 Set
RI 0
Proof. From the condition on
16 (74
Abo.
BL10
6 S
45(K K + 1)
c
1
I
32T I
744
Abo Bl1e
90(K + 1)I
From the condition on I,
4cT S 740 +
Ala. BLIP
Sea
32r, / (74 +
ALe. BLip
744 32
ALa BLiP
27 log J
216ALoo² log
Also
Sea
S
18AAL9
A
216ATbo log
216A n log 8
S
12o2 log 3
and
Sea
S
32AI'
740 +
ALo. BlTe
27 A7 2ogo22oo2
21 log
21 log
T2 log 1
41' (740 + Ala.
BLiP
T,I log
34

---

Therefore 216ALgo2 log
Sr²
Choosing R = SA
8A
1296.AALoo log 0
|A log
RI = 1
Sed
Sed
B Deferred Proofs of the Lower Bound
Algorithm 2 Clipped Minibatch SGD
1: Initialize æo
2: for 0, 1..... R 1--1 do
3: Sample S, C [N] uniformly at random such that |S,| S
4: 9- ST Eies, Σk=o (x, 5%,k)
5: Update 2r+1 f H, min TT To-
6: end for
Our proof of Theorem 2 analyzes three separate functions satisfying Assumption| I and concludes that, in order for clipped minibatch SGD to avoid divergence on the first two functions, one must choose parameters ", 1) such that convergence on the third function is slow. These three functions separately analyzed in Lemmas 13 15| and 16 Each lemma assumes particular value of the initial point øy: this assumption can be made without loss of generality, since for the initialization zy we may always translate each function to simulate the assumed initialization.
Lemma 13. Let 8 E (0, 1) and denote Q
k+(p-1)M N k+(p+1]M
Suppose
2 + log(2 5)
(p + 1)(1 + log 8)) 2
log(2 - 5)(Q 11)
P
log(2 5) N N
1SS5
(42)
(p - 1) log
N + log(2 5)
and " S M. For any < E < M. there exists a problem instance (fim L1, M, k. p, N)
such that, with probability at least 8, clipped minibatch SGD with parameters Y S will generate
iterates {x,),- with || fxx,)l for all
The proof of Lemma 1 will require the following lemma.
Lemma 14 (Lemma 5.3 in 20). Let {X,] be a Markov chain over states {1) such that is an absorbing state, and the transition distribution elsewhere is follows:
X441((,- = i ++1 w.p. 1 1-p
w.p. p
Define the absorb probabilities = P(3t > 0: X, = 0 X, = i), then:
0x 1
, Vi Vi
Proof of Lemma 13 Define
Q
+ Φ
② N
b =
M,
Φ
and
3b
"
g(x)
8 x
4u x²
2T.¹
Also, define
M(x Mg(r)
x -v x x (-v,v)
(zx)
-g(())
M(x v) -Mg(v)
x x2
35

---

and
b(a o) + bg(u)
x x -
(x
bg(x)
xE (-2, x²
b(x v) bg(
Consider the problem instance defined by
(x)) 1sisQ f(x)) (2)
Q+1siSN
with global objective
MMx + 0) + Mg(v) -0 = Mg(x) M(x-v) Mggo))
f(0) -
+ o())=
(2)(()
x E ( (-U, v)
Note that 6 M. For this problem instance, we define the stochastic objective as Fj (a; = 1 (x). so that the true gradient of each local objective is returned by each gradient query of the algorithm.
By construction, each local objective fi and the global objective f is twice continuously differentiable, with gradient bounded by M. Also, each objective is (Lo, Lsm-ohh (in fact, they are smoothhh), since for |x]| S v,
3
3
lg"(x))
+
2r
2v
x²
1
2v
22
Lo
2v
5
and for |x| 2 u, (x) 0. Finally, the collection of objectives satisfies the heterogeneity condition.
For < Q
x
and for i 11
[1((0) = b [((x)]
1 1 Φ M
[x( M
[f(x)] M
S (ns PM)
S (x))
M
where we used
+ x+
1 1 ω
x+ x+(++1)Mr
2x + 2pM + (p + 1)M
K PM
kt(p- 1)
K 11+1)M
2M
M
x+ 10+ 1)M8
together with the fact Φ
1)M *+(++I)M
Therefore (A E F(Lo, M,,,,,,,,N)
Now, we analyze the behavior of clipped minibatch SGD on the instance ( with initialization
To = v ++++ 1. Let be the index of the first round (if one exists) in which 2p U. For each round
define the event B, = (S, C [Q]]. To compute P(B,), first notice
N-Q Q
log(2 2 - 8)
<
Q S-S+1
S
Therefore,
P(B,)
II (=0
Q (Q- 511
>
1
N N S +1
1
N N-Q
|
log(2-0)
2
8
0-S+1
where we used the inequality (1 -)=² c
36

---

Now define the auxiliary sequence {リr J as follows:
y0 - 40
yr + 7 if Br
y/+1
Ur 7 otherwise
We claim that yr I x, for all S ro. For any ro. if B, occurs then yr+1 - 1/, Ir+1 Ir. since in this case - M and x 2, = 7, due to the fact that 2 S M. If B, does not occur, then Fy+1 Ir y, due to the clipping operation, so that yr+1 Yr S 2r+1 Ty. Therefore for all r S ro.
Σ Mp+1 U1 S 20 +
//- yo
Tq+l
5g = Ir,
which proves our claim. Denoting D = (x,)x)) 2 M for all r 2 1}.
P(D) 2 P(x, 2 -1 for all r 2 1)
z Ply -1 for all 2 1)
(1) 1 - P(,)
1
P((.))
(6)
1 P(Br))
2
P(B,)
(I, -1
P(B,)
2
2-8 5 1 (2 (2-
8,
where (i) comes from applying Lemma 14 to the sequence y, and (ii uses I-P(B.) F(B.)
> and
< 6.
The following Lemma uses the same function as in the first half of the proof of Theorem 2 in 8.. However, the sequence of iterates computed by clipped minibatch SGD (our setting) evolves differently than that of GD (their setting).
2 (1 log log L For any 0 < M, there Lemma 15. Suppose 3 >> M, M > 4g.and vj 2 T.
exists problem instance {fiJ. F(Lo, L1, M, K. p. N) such that clipped minibatch SGD with parameters "I, T,, and uny S will generate iterales { IR with [xx))) > for all r.
Proof. Consider the following function,
Le exp (-L10- 1) I< - Ii I I I1
T
f(x)
La
2
21
Lg
exp (L1x 1)
x >> L
L.
and the problem instance f. f for all E [N], with the initialization xo = 1 (1+ log Lo We
define the stochastic objective for this problem instance as F,(x;;) = f(()),, so that the true gradient of each local objective is returned by each gradient query of the algorithm.
Note that f is bounded from below and (Lo, L -mooth. Also, since all clients have the same objective and gradients are computed deterninistically. this problem instance satisfies Assumption [ Also, our setting of zo is consistent with the definition of M, since
Lo
If (xo) exp (Liz0 1)
Li Lo MIa M.
L Lo
37

---

Lo ). By the condition 2 M, we know w zo. and by construction ('(w) "7' Since is increasing on [0, x)), and decreasing on (-xo, 0], know [f'ww)] 2 3 and only if |x| 2 w. This means that the clipping operation will be performed when |x]] 2 w, and will not be performed for |x] < w.
First, define == 1 1 + log 11
Li
Now analyze the behavior of clipped minibatch SGD on this problem instance. Suppose that [0o| I | S w for some r 2 Then
20
2L, Fry Lo exp 1 |r, 1)
r Lg exp I 1)
where the first inequality comes from the definition of zo and the condition 2 Mn (1+ log LM
2
Lo
2 and the second inequality comes from the fact that <xxx) Lo Loexp(11x-1) Therefore
is decreasing 00).
(0)
Lo nlf'(z,)) - (xp(L1|2x11
|2,| - 1) 2/2+||-
(43)
Since sign(f((x;)) * sign(x,), this implies [xr+1l = |,,- -f (x.)) 2 2/r,1| - -1,l1 |,,] This shows that the sequence iterates { non-decreasing absolute value until (if ever) the absolute value exceeds If |æ,1 w for all then we done, since in this case we have |æy| 2 | and therefore fV(2))] 2 Vf(x))] = M > c for all r.
Otherwise, let F be the first index r for which |,,| > w. Without loss of generality, assume 2y > 0 (for xy O, the same argument applies with signs reversed). Since 1 S w,
Ep Iz-1 (I S - 1 7 w.
So
F++1 = 27 - - (r - w) - -
Therefore [f((411) 2 [f((-w) = [w 3. and so 2F42 = I +y = 2p. We can then show
by induction that IF+2n and 2F+2n+1 = IT-1 for all n 2 0. Since (f+) > [f((w)) > [x(o) > e, we have |/ [x(x))] for all r.
The following lemma is nearly identical to the second half of the proof of Theorem 2 in g We include it here for the sake of completeness.
Lemma 16. Suppose > M and < Li,s (1+ log 12 For any O < < M, there ex- ists a problem instance ( E F(Lo, M,K,P,N such that clipped minibatch SGD with parameters 7/, H,, and any requires at least
2
Lo
L,M (f(zo) -
15c²
167.0
2e 1 log L
rounds in order to find an e-stationary point.
Proof. Consider the following function,
36
f(x)
1. 2ica
x
+ La
2 +
96²
3r
3c
T6L
20o
2Lo
3c
21.
and the problem instance fi = ff for all i [N], with the initialization stochastic objective for this problem instance F1 5) fa(x), that the true gradient of each local objective is returned by each gradient query of the algorithm.
3c d. We define the
2L
Note that f is bounded from below and (To. L, -moothh. Also, since all clients have the same objective and gradients are computed deterministically. this problem instance satisfies Assumption T Also, our setting of zo is consistent with the definition of M, since [zo) < M.
38

---

Now we analyze the behavior of clipped minibatch SGD on this problem instance. Since this problem
instance is homogeneous with deterministic gradients, we have 11 I E < M 2. so clipped
minibatch SGD will always perform unnormalized updates. Therefore, for 2
3x
2Lx"
2c
L,M
(1+ log Lo
Ty41 Zy 19r Ir > Ir LIM
Therefore
2cr (1 1+ log
L Lo
3e
2cr (1
L
Zr > 20
+ d
(1 log
L
2Lo
L
Lo
as long as
Per L
(1 (1+ log
4 Le
< d. or
dLiM
Notice that
2e
1+log
4
3x2
f(xo) =
+ de,
2L0
80
d 6
1
((xa)
3e²
((x0) -
15c2
2T.
16T.
Plugging into the above bound on tells that xy xi long r 2 La (200)-1-
10.2
The
2r 14log Lo
result follows from the fact that [x,)] for all xr- To.
We can now combine Lemmas
and to prove Theorem
Proof of Theorem 2 Let 7, 17 > 0 be given. We will prove the requirement on R for three cases of 7, n.. In the case π S M, then Lemma demonstrates that clipped minibatch SGD cannot guarantee to find an e-stationary point with probability greater than for any R. Second, if 2 > M and
[ + log M, ). then Lemma 15 demonstrates that clipped minibatch SGD can fail to find 7 T.M
L.M e-ttationary point for any R. In the remaining case, i.e. 2 > M and v < 1 (1+ (1+log log Lo
"
Lemma 16 demonstrates that for finding an e-stationary point, the number of iterations clipped minibatch SGD requires least
M (f(2o) -
15c² 16Lo
R 2
2x 1
Li log log Lo
C Additional Experimental Results
C.1 Hyperparameter Information
Learning Rate and Clipping Threshold For each dataset, we tune the hyperparameters fy and 7 with separate grid searches. Specifically, we first tune the clipping threshold 2 with grid search, then we tune the learning rate 7 with grid search. During the grid search for 7). 7 is chosen so that the clipping threshold 2 is equal to the tuned value from the search for 3. Due to computational constraints, we do not perform this search for every algorithm in every setting. Instead, we follow the tuning process of [9] we use the above procedure tune 17 and r for CELGC [32 separately for each 5 E {2, 4, 6, 8}, while fixing values of 7 and ry for all other algorithms and settings sharing the same dataset and Our theory suggests that the best learning rate 7 depends on the number of participating clients S, and we follow this guidance by tuning the parameters separately for each value of S. The search ranges and tuned values for each datasct are shown in Table 3
7
30% (SNLI) or 10% (Sent140). We then reuse the tuned
39

---

Table 3: Hyperparameter tuning information for each dataset.
Parameter
Search range
Tuned value
S 2: 1.0
S 4: 1.0
SNLI
2
{0.01, 0.03, 0.1, 0.3, 1.0,3.03
S 6: 1.0
S = 8: 1.0
S 2: 0.03
S = 4: 0.03
{0.003, 0.01, 0.03, 0.13
S 6: 0.03
S 8: 0.03
S 2: 0.3
S 4: 0.3
Sent140
{0.01, 0.03, 0.1, 0.3, 1.0,
S 6: 0.3
S 8: 0.3
S 2: 0.03
4: 0.03
r)
{0.003, 0.01, 0.03, 0.13
S 6: 0.03
S = 8: 0.03
Network Architecture For both datasets, the network is composed of a one-layer bidirectional RNN encoder followed by three-layer fully connected classifier. The encoder has hidden size 2048 and max pooling, and the decoder has hidden size 512 with tanh activations. Input sentences are encoded as sequences of GloVe vectors. For SNLI, where each input is pair of sentences, each sentence is passed through the encoder separately, and the resulting representations are concatenated and used as input for the encoder.
C.2 Learning Curves
Figures and contain learning curves (by communication rounds) of training loss and testing accuracy for all settings, for SNLI and Sentiment144 respectively. The experiments show that our proposed algorithm EPISODE+ significantly outperform all other baselines in various settings on these two datasets, including different client participation ratio and different heterogeneity level.
C.3 Training with Homogeneous Data
Here we include learning curves for an additional experiment that uses homogeneous data across clients, i.c. 0%. In this setting, use 8 and 4, and all other settings are the same as described in Section 6 We compare the six algorithms described in Section 6 Results are shown in Figure The results are consistent with the experiments that heterogeneous data: EPISODE+ outperforms all other algorithms in terms of training loss and testing accuracy.
40

---

SNLI (S=2, 3030%)
SNLI (5=4, 5=30%)
1.2
0.8
0,8
Train Loss
1.0-
Accuracy
0.7
0.8
Test Accuracy
0.7
0.8
Train
0.6-
0.5
0.4
0.4
0.4
0.4
2000
4000
2000
4000
2000
4000
2000
4000
Rounds
Rounds
Rounds
Rounds
SNLI (S=6, 5=30%)
5=30%)
Thain Loss
Accuracy
0.7-
Test Accuracy
0.6
0.6
0.6-
0.5
0.4
0.4
0.4
2000
4000
2000
4000
2000
4000
2000
4000
SNLI (S=4, s=50%)
SNLI (S=4, s=10%)
1.0
0.8
0.8
Train Loss
0.8-
Test Accuracy
0.7
0.6
Train
0.8
0.6
0.6-
0.5-
0.6
0.5
0.4
0.4
2000
4000
2000
4000
2000
4000
2000 Rounds
4000
Rounds
Rounds
Rounds
ERISODE++
CELGC
NaiveParalleCClip
Clipped Minibatch SGD
SCAFFOLDClip
EPISODE
Figure 4: Learning curves for SNLI under all settings. For NaiveParallelClip. we show the first 5375 rounds to compare all algorithms with a fixed number of communication rounds.
41

---

Sentiment140 (
Sentiment140 (5=4, 5=30%)
0.8
Test Accuracy
0.75
Test Accuracy
Thain Loss
Train Loss
0.6
0.6
0.70
0.70
0.4-
0.65
0.4
0.65
2000
2000
2000
2000
Rounds
Rounds
Rounds
Sentiment140 (S=6, 5=30%)
Sentiment140 (S=8, 5=30%)
0.8
0.8
Iest Accuracy
0.75
0.7
Test Accuracy
0.75
Train Loss
Train Loss
0.6
0.6
0.4
0.65
0.65
0.3
1000
2000
1000
2000
1000
2000
1000 Rounds
2000
Rounds
Rounds
Rounds
Sentiment140 (S=4, ($=4,s=20%) 5=20%)
Sentiment140 (S=4, 5=0%)
0.8
0.7
Test Accuracy
Test Accuracy
Train Lo8s
0.6
Train Loss
0.6
0.5
0.70
0.5
0.70
0.65
0.3
Rounds
Rounds
Rounds
Rounds
EPISODE++
NaiveParallelCiip
Clipped Minibatch
SCAFFOLDCIip
EPISODE
Figure 5: Learning curves for Sentiment 140 under all settings. For NaiveParallelClip. we show the first 2000 rounds to compare all algorithms with fixed number of communication rounds.
SNLI
Sentiment140
1.0
0.8
Test Accurary
Test Accuracy
0.75
Train Loss
0.8
Train Loss
0.70
0.4
0.4
0.4
0.65
2000
4000
2000
1000
1000 Rounds
2000
1000 Rounds
2000
Rounds
Rounds
++ISODE++
CELGC
NaiveParallelCipp
Clipped Minibatch SGD
SCAFFOLDClip
EPISODE
Figure 6: Learning curves for SNLI and Sentiment 140 with N 8, S
using homogeneous data, i.c. s = 100%. We compare all algorithms with a fixed number of communication rounds.
42


Reviews:
[{"review_id": "zqyoZK1BB1", "reviewer": "Reviewer_xXDR", "summary": "The paper investigates Federated Learning (FL) under client subsampling and data heterogeneity, focusing on functions with potentially unbounded smoothness, and introduces the proposed algorithm to address the problem, EPISODE++. EPISODE++ has demonstrated benefits including linear speedup with client numbers, reduced communication rounds, and resilience to data heterogeneity. The authors provide theoretical convergence analysis and experimental results validate the effectiveness of their method. ", "questions": "See weakness", "limitations": "The authors have mentioned limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n2. Provides novel techniques when proofing both upper and lower bounds.\n3. Theoretically demonstrates the benefit of proposed methods EPISODE++, and also shows the shortage of existing clipped minibatch SGD.\n4. The proposed algorithm achieves significant improvement over existing methods.\n", "weaknesses": "1. The experiments with N=8 may not fully reflect the actual performance with large-scale FL, for example, FedAvg uses 100 clients in their experiments, where more heterogeneity and client shift might result in different behavior. I would be happy to see if there's more benefit of EPOSIDE++\n2. Missing error bar and not indicates the number of repetition runs in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer xXDR (7): Thank you for taking the time to review our paper. Below we have addressed the concerns you raised during your review.\n\n**Q1: “The experiments with N=8 may not fully reflect the actual performance with large-scale FL”**\n\nWe agree that evaluating the proposed algorithm on large-scale experiments is important. In our 1 page rebuttal PDF, we have included results for large-scale experiments in two settings: (i) the SNLI dataset with $N = 128, S = 16, s = 30\\\\%$ and (ii) the Sent140 dataset with $N = 128, S = 16, s = 10\\\\%$, where $s$ stands for data similarity. Note that these experiments use the same dataset as those from the main text, and the dataset is split into a larger number of clients using the heterogeneity protocol described in the main text. We ran these experiments using 16 GPUs on a cluster of 4 nodes with 4 GPUs each. The results are shown in Figure 2 of the 1 page rebuttal PDF.\n\nIn both settings, the relative performance of each algorithm is similar to that of the main text experiments (i.e., those with $N = 8$). Note that the proportion of participating clients $S/N=1/8$ for the large-scale experiments and $S/N \\geq 1/4$ for the main text experiments, so that the effect of partial client participation may be stronger in the large-scale experiments. With $N=128$, EPISODE++ achieves a better training loss for both settings than in any experiment with $N = 8$, while the testing accuracy of EPISODE++ is about the same as the highest testing accuracy of the $N = 8$ experiments. Further, EPISODE++ outperforms all other algorithms in the $N = 128$ setting.\n\n**Q2: “Missing error bar and not indicates the number of repetition runs in experiments.”**\n\nAgain, we agree that multiple repetition runs is important to properly evaluate our proposed algorithm against baselines. To ensure that our results are representative of the performance of each algorithm, we have included results with a total of three repetitions for two experimental settings: (i) the SNLI dataset with $N = 8, S = 4, s = 30\\\\%$ and (ii) the Sent140 dataset with $N = 8, S = 4, s = 10\\\\%$. All other hyperparameters and configuration details remain the same as the results reported in the main text. The average results and error bars are shown in Table 1 of the 1 page rebuttal PDF. Note that the size of each error bar is the distance from the average over three trials to the min/max over three trials.\n\nAcross three trials, EPISODE++ remains the best performing algorithm in terms of training loss and testing error: the worst trial of EPISODE++ is better than the best trial of any other algorithm, across both metrics and both datasets. The ordering of the algorithms by performance in the trial-averaged results is the same as in the single-trial results of the main text, which is consistent with the experimental results of the main text.\n\nThank you for your time, and please let us know if you have additional comments.\n"}, {"review_id": "hoU5E1FRZ1", "reviewer": "Reviewer_PGRH", "summary": "The paper presents a novel algorithm for non-convex federated learning that addresses the challenges of relaxed smoothness, client heterogeneity, and client subsampling. The authors begin by discussing the limitations of existing algorithms such as SCAFFOLD and EPISODE in handling these challenges simultaneously. They then introduce their algorithm, EPISODE++, which is designed to overcome these limitations. The algorithm is initialized with a set of parameters and then iteratively updated through a series of communication rounds. In each round, a subset of clients is selected randomly, and each client performs local updates based on its own data. The algorithm also includes a gradient clipping step to control the magnitude of the gradient updates.\n\nThe authors provide a detailed theoretical analysis of the convergence properties of EPISODE++. They show that the algorithm can achieve a linear speedup over the standard federated averaging algorithm (FedAvg) under certain conditions. They also demonstrate that EPISODE++ can significantly outperform clipped minibatch SGD, another popular algorithm for non-convex optimization, in terms of the number of iterations required to find an epsilon-stationary point. The paper concludes with an extensive set of experiments that validate the theoretical findings. The authors show that EPISODE++ outperforms other state-of-the-art algorithms on a variety of benchmark datasets and neural network architectures, including LSTMs and Transformers.", "questions": "The paper could provide more information about the implementation details of the EPISODE++ algorithm. For instance, how are the parameters of the algorithm chosen in practice? Are there any specific strategies or heuristics for setting these parameters? Providing such information could help other researchers to replicate the results and apply the algorithm to their own problems.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The authors provide a detailed theoretical analysis of the convergence properties of EPISODE++. They show that under certain conditions, the algorithm can achieve a linear speedup over the standard federated averaging algorithm (FedAvg), and significantly outperform clipped minibatch SGD in terms of the number of iterations required to find an epsilon-stationary point. This rigorous analysis strengthens the credibility of the proposed algorithm.\n\n2. The paper includes an extensive set of experiments that validate the theoretical findings. The authors demonstrate that EPISODE++ outperforms other state-of-the-art algorithms on a variety of benchmark datasets and neural network architectures, including LSTMs and Transformers. There are many other FL papers that only conduct very toy experiments that are not convincing enough. This empirical evidence provides strong support for the effectiveness of the proposed algorithm.", "weaknesses": "While the paper presents a novel algorithm and provides a detailed theoretical analysis, the scope of the study appears to be limited to non-convex federated learning. It would be interesting to see how EPISODE++ performs in other contexts or problem domains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and give valuable feedback. See the list below, where we have individually responded to the questions and comments in your review.\n\n**Q1: “the scope of the study appears to be limited to non-convex federated learning.”**\n\nOur algorithm is indeed designed for the federated learning task, and the analysis focuses on the non-convex case, since it is more general (and includes) the convex case. Because of this, our theory provides a guarantee on the gradient norm $\\lVert \\nabla F(x_t) \\rVert$ along the trajectory with high probability. In the strongly convex case, this guarantee implies a guarantee on the objective gap $F(x_t) - F^*$ with high probability, where $F^*$ is the global minimum of the objective function $F$. Therefore, if we would like to restrict our attention from the general non-convex case to the special strongly convex case, our analysis immediately gives guarantees. Also, the problem of finding a point with small gradient is of independent interest [1, 2] outside of its implications for the “objective gap” even in the convex case.\n\n**Q2: “how are the parameters of the algorithm chosen in practice? Are there any specific strategies or heuristics for setting these parameters?”**\n\nThe parameters of EPISODE++ are the learning rate $\\eta$, the clipping parameter $\\gamma$, and the communication interval $I$, which are all parameters of previously existing algorithms such as FedAvg ($\\eta$ and $I$) and CELGC ($\\eta$, $\\gamma$, and $I$). These parameters may be chosen following standard conventions of federated learning and machine learning in general.\n\nTo choose hyperparameters in the experiments of the paper, we tuned the learning rate $\\eta$ and the clipping parameter $\\gamma$ according to a grid search that is described in Appendix C.1, which is referenced on Line 260 of the main text. After tuning the parameters for CELGC [3], we found that the tuned set of parameters worked well for the remaining algorithms, so we re-used these parameter values for all baselines.\n\nThank you for your time, and please let us know if we have addressed your concerns.\n\n[1] Yurii Nesterov. “How to make the gradients small.” Optima, 88:10–11, 2012.\n\n[2] Allen-Zhu, Zeyuan. \"How to make the gradients small stochastically: Even faster convex and nonconvex sgd.\" Advances in Neural Information Processing Systems 31 (2018).\n\n[3] Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-efficient\ndistributed gradient clipping algorithm for training deep neural networks. Advances in Neural Information Processing Systems, 35:26204–26217, 2022."}, {"review_id": "YaCs37FFf9", "reviewer": "Reviewer_sD3Q", "summary": "The authors propose a federated learning algorithm that can work under (L0,L1)-smooth function. Different from the previous work, the authors consider the partial-participant setting, modifying the previous algorithm, showing the convergence of the new algorithm, and giving a lower bound of the communication iterations under this setting. The experiments show that the proposed algorithm performs well.", "questions": "See weakness.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors propose a new algorithm that overcomes the bias introduced by client heterogeneity and client sampling.\n\n2. The authors prove the convergence of the proposed algorithm and a lower bound of communication iterations under this setting.\n\n3. The experimental results show the the proposed algorithm performs much better than previous work.", "weaknesses": "1. The key motivation is not clear to me. For me, it is hard to justify that with a uniform sampling strategy on clients, why the bias will occur? And it is hard to see how the proposed algorithm can fix the introduced bias. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and for providing helpful comments. Below we have addressed the concern you expressed in your review.\n\n**Q1: “The key motivation is not clear to me. For me, it is hard to justify that with a uniform sampling strategy on clients, why the bias will occur?”**\n\nTo discuss the bias from a theoretical perspective, we would like to clarify the meaning of bias in this context versus heterogeneity. They are different concepts in federated learning. Denoting the $i$-th client objective as $F_i$, consider the error $\\nabla F_i - \\nabla F$, where $i$ is sampled uniformly over $\\{1, \\ldots, n\\}$. The expectation over $i$ of this error (i.e., sampling bias) is zero, i.e., $\\mathbb{E} [ \\nabla F_i(x) - \\nabla F(x) ] = 0$ for all $x$. However, if we take the expectation of the squared norm of this error (i.e., sampling variance), we get a dependence on the heterogeneity $\\kappa$, i.e. $\\mathbb{E} \\left[ \\lVert \\nabla F_i(x) - \\nabla F(x) \\rVert^2 \\right\\] \\leq \\kappa^2$. The bias in the first case is zero because the sampling is uniform and the error from different clients cancel each other. The expected $\\ell_2$ error in the second case is non-zero because we consider the norm of the error and no canceling may occur: the expected norm depends on the heterogeneity $\\kappa$. If the algorithm only uses gradient information from sampled clients (such as FedAvg, CELGC, NaiveParallelClip), then the update direction is approximating $ \\frac{1}{S} \\sum_{i \\in \\mathcal{S}} \\nabla F_i(x)$, and the convergence will be slowed with a dependence on the heterogeneity $\\kappa$ due to sampling variance, i.e., $\\mathbb{E} \\left[ \\lVert \\frac{1}{S} \\sum_{i \\in \\mathcal{S}} \\nabla F_i(x) - \\nabla F(x) \\rVert \\right\\] \\leq \\kappa$. Therefore the heterogeneity is introduced even under uniform sampling.\n\nThe effect of client heterogeneity and client sampling can also be understood empirically. Several works have empirically demonstrated that the performance of FedAvg with uniform sampling and data heterogeneity decreases as the number of participating clients decreases (see Table 4 of [1] or Figure 1 of [2]), which demonstrates that this effect does occur even under uniform sampling.\n\nThe motivation of this paper is designing computation and communication-efficient algorithms in the relaxed smoothness setting and client subsampling. Our Theorem 1 shows that our computational complexity does not depend on heterogeneity level $\\kappa$.\n\nThank you for your time, and please let us know if we have addressed your concern.\n\n[1] Karimireddy, Sai Praneeth, et al. \"Scaffold: Stochastic controlled averaging for federated learning.\" International conference on machine learning. PMLR, 2020.\n\n[2] Li, Tian, et al. \"Federated optimization in heterogeneous networks.\" Proceedings of Machine learning and systems 2 (2020): 429-450."}, {"review_id": "d9Tx1mxmYh", "reviewer": "Reviewer_svY2", "summary": " This manuscript introduces a new federated learning algorithm, EPISODE++, to accelerate the convergence speed of federated learning and provides theoretical proofs for the upper bound of convergence speed.", "questions": "1. In Figure 1 (a) and (b), the left two figures show that NaiveParallelClip has lower training loss than other methods when the number of clients is 8, but its testing accuracy is lower than that of EPISODE++. How can this phenomenon be explained?\n\n2. How does the performance of the method change when there are more clients (resulting in larger variances for $G_{r+1}$ and $G_{r+1}^i$)? Does it outperform classical methods like fedprox?\n\n3. How were the hyperparameters (learning rate, training steps) chosen for each method?\n\n4. How does the proposed method perform when the client data are i.i.d.?\n", "limitations": "The method proposed in this manuscript only slightly modifies the EPISODE method, and the experimental section is not comprehensive.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The method proposed in this manuscript improves the EPISODE algorithm by addressing the issue of client heterogeneity while allowing partial client participation. The manuscript also provides theoretical proofs for the convergence speed.", "weaknesses": "The experimental section does not explain how the hyperparameters for each baseline method were selected, and it does not discuss how the performance of the method is affected when the number of clients reaches hundreds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your effort in providing valuable feedback. Below, we have individually addressed the questions in your review.\n\n**Q1: “In Figure 1 (a) and (b), the left two figures show that NaiveParallelClip has lower training loss than other methods when the number of clients is 8, but its testing accuracy is lower than that of EPISODE++. How can this phenomenon be explained?”**\n\nThis can be explained by the fact that NaiveParallelClip with $S=8$ is essentially simulating large-batch SGD, since it eliminates local steps and computes the update by averaging the gradient across ALL clients. It has been shown [1] that large-batch SGD can overfit in deep learning, and this may cause the overfitting in the case $S=8$. Notice that when $S<8$, NaiveParallelClip is not simulating large-batch SGD because it is still missing information from unsampled clients. Also, we would like to reiterate that NaiveParallelClip is not a practical algorithm due to the significant communication cost.\n\n**Q2: “How does the performance of the method change when there are more clients?”**\n\nIn our 1 page rebuttal PDF, we have included results for large-scale experiments in two settings: (i) SNLI with $N=128, S=16, s=30\\\\%$ and (ii) Sent140 with $N=128, S=16, s=10\\\\%$. All other configuration details are the same as in the main text. The results are shown in Figure 2 of the 1 page rebuttal PDF.\n\nIn both settings, the relative performance of each algorithm is similar to that of the main text experiments (i.e. those with $N=8$). The proportion of participating clients is $S/N=1/8$ for the large-scale experiments and $S/N \\geq 1/4$ for the main text experiments, so that the effect of client sampling may be stronger in the large-scale experiments. With $N=128$, EPISODE++ achieves a better training loss for both datasets than in any setting with $N=8$, while the testing accuracy of EPISODE++ is about the same as the highest testing accuracy of the $N=8$ settings. Further, EPISODE++ outperforms all other algorithms in the $N=128$ setting.\n\n**Q3: “Does it outperform classical methods like fedprox?”**\n\nWe have included additional results comparing EPISODE++ and FedProx in the 1 page rebuttal PDF. In this experiment, we used both algorithms for the SNLI setting as described in the main text, with $N=8, S=2, s=10\\\\%$. For FedProx, we tuned the additional parameter $\\mu$ over $\\{0.01, 0.03, 0.1, 0.3, 1.0\\}$, and the best tuned value according to test accuracy was $\\mu = 0.03$. The results are included in Table 2 of the 1 page rebuttal PDF. Due to time constraints, we were not able to evaluate other baselines in this setting.\n\nAs shown in Table 2, EPISODE++ achieves a lower training loss and higher training accuracy than FedProx. Similar to FedAvg, CELGC, and NaiveParallelClip, FedProx does not utilize gradient information from unsampled clients, which suggests that the performance of FedProx should degrade under data heterogeneity and client sampling. Since EPISODE++ utilizes information from ALL clients in the form of correction terms, EPISODE++ may be more resilient to data heterogeneity and client sampling, and indeed we observe this in Table 2.\n\n**Q4: “How were the hyperparameters (learning rate, training steps) chosen for each method?”**\n\nThe learning rate $\\eta$ and the clipping parameter $\\gamma$ were tuned according to a grid search described in Appendix C.1, which is referenced on line 260 of the main text. The number of training steps was chosen to be long enough that the test accuracy stopped increasing. \n\n**Q5: “How does the proposed method perform when the client data are i.i.d.?”**\n\nWe have included additional experimental results using i.i.d. data in the 1 page rebuttal PDF. We evaluated EPISODE++ and all baselines in two settings: (i) the SNLI dataset with $N=8, S=4, s=100\\\\%$ and (ii) the Sent140 dataset with $N=8, S=4, s=100\\\\%$. All other configuration details remain the same as the experiments from the main text. The results are shown in Figure 1 of the 1 page rebuttal PDF.\n\nFor both datasets, EPISODE++ remains the best performing method by both training loss and testing accuracy. All algorithms (besides CELGC) perform similarly with homogeneous data as in the counterpart settings with heterogeneous data.\n\n**Q6: “The method proposed in this manuscript only slightly modifies the EPISODE method”**\n\nThere are two important differences between EPISODE and EPISODE++, one practical and one theoretical. The first is that EPISODE++ does not perform double communication at each round, since the correction terms $\\mathbf{G}_r^i$ are computed using information from previous rounds. In EPISODE, these correction terms depend on the new averaged model $\\bar{\\mathbf{x}}_r$. Computing corrections requires one communication operation to broadcast $\\bar{\\mathbf{x}}_r$ and then another to share the newly computed corrections. Note that this is not just a doubling of the communicated bits: since $\\mathbf{G}_r^i$ must be computed after the end of the first communication operation and before the beginning of the second, the two communication operations cannot overlap, and there must be a doubling of the required communication time. The halving of the communication cost in EPISODE++ is a significant practical benefit over EPISODE.\n\nThe second important difference is that the introduction of client sampling brings new challenges for the convergence analysis which cannot be handled by the approach used to analyze EPISODE. To handle these new challenges we introduced a nested recursive analysis of the update size (Lemmas 1, 10, and 11) and provided a high probability guarantee of convergence (as opposed to the expectation guarantee of EPISODE).\n\nThank you for your time, and please let us know if we have addressed your concerns.\n\n[1] Keskar, Nitish Shirish, et al. \"On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima.\" International Conference on Learning Representations. 2016."}]

Author rebuttal:
We would like to thank all of the reviewers for taking time to review and critique our work. We have provided an individual response to each reviewer, and here we provide a general summary of our additional results included in the 1 page rebuttal PDF.

**Large scale experiments**

In the 1-page rebuttal PDF file, we have included large scale experimental results with a large number of clients $N = 128$. Results are shown in Figure 2 of the 1-page rebuttal PDF and are further described in the individual responses. The results with $N = 128$ are consistent with the experiments of the main text that use $N = 8$. EPISODE++ outperforms all other algorithms in terms of both training loss and testing accuracy, for the two datasets SNLI and Sentiment140.

**Multiple trials**

We have additionally included results for all algorithms averaged over three random seeds, in order to ensure that our experimental results are representative of the expected performance for each algorithm. In general, the results of the additional trials match that of the results reported in the main text: EPISODE++ outperforms all baselines, and the performance of each algorithm is stable across the three seeds. The results are shown in Table 1 of the 1-page rebuttal PDF file and are further described in the individual responses.

**Homogeneous data**

We also evaluated our algorithm and baselines in two settings with homogeneous data, and results are shown in Figure 1 of the 1-page rebuttal PDF. Every algorithm has similar or better performance compared with the heterogeneous setting, and EPISODE++ remains the best performing algorithm by a wide margin.

**Comparison with FedProx**

We compared EPISODE++ against the algorithm FedProx on the SNLI dataset. EPISODE++ achieves a lower training loss and a higher testing accuracy. This gap follows intuition, since FedProx does not use any explicit mechanism to combat client subsampling and data heterogeneity.

Meta-review: Given the scores, and also looking at the paper's writing and presentation as well as the discussions, I am recommending acceptance as a poster.
Decision: Accept (poster)