Convergence Analysis of Sequential Federated Learning on Heterogeneous Data
Authors: Yipeng Li
Xinchen Lyu
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
Convergence analysis
TL;DR: This paper aims to derive the convergence guarantee of Sequential Federated Learning and compare it with Parallel Federated Learning (FedAvg) theoretically.

Abstract: There are two categories of methods in Federated Learning (FL) for joint training across multiple clients: i) parallel FL (PFL), where clients train models in a parallel manner; and ii) sequential FL (SFL), where clients train models in a sequential manner. In contrast to that of PFL, the convergence theory of SFL on heterogeneous data is still lacking. In this paper, we establish the convergence guarantees of SFL for strongly/general/non-convex objectives on heterogeneous data. The convergence guarantees of SFL are better than that of PFL on heterogeneous data with both full and partial client participation. Experimental results validate the counterintuitive analysis result that SFL outperforms PFL on extremely heterogeneous data in cross-device settings.

Convergence Analysis of Sequential Federated Learning on Heterogeneous Data
Yipeng Li and Xinchen Lyu
National Engineering Research Center for Mobile Network Technologies
Beijing University Posts and Telecommunications
Beijing, 100876, China
fliyipeng, lvxinchen
wewrchhennbubppeeeec Sbtpt. edu.
Abstract
There categories of methods in Federated Learning (FL) for joint training across multiple clients: i) parallel FL (PFL), where clients train models in a paral- lel manner; and ii) sequential FL (SFL), where clients train models in sequential manner. In contrast to that of PFL, the convergence theory of SFL on heteroge- neous data is still lacking. In this paper, establish the convergence guarantees of SFL for boongly/genera/noon-oooee convergence guarantees of SFL are better than that of PFL heterogeneous data with both full and partial client participation. Experimental results validate the counterintuitive analysis result that SFL outperforms PFL on extremely heteroge- neous data in cross dessce settings.
objectives on heterogeneous data. The
Introduction
Federated Learning (FL) (McMahan al., 2017) is popular distributed machine learning paradigm, where multiple clients collaborate to train global model. To preserve data privacy and security, data must be kept in clients locally cannot be shared with others, causing one severe and persistent issue, namely "data heterogeneity". In cross-device FL, where data is generated and kept in massively dis- tributed resource-constranee devices (c.g., IoT devices), the negative impact of data heterogeneity would be further exacerbated (Jhunjhunwala et al., 2023).
There are two categories of methods in FL to enable distributed training across multiple clients (Qu et al., 2022): i) parallel FL (PFL), where models are trained in a parallel manner across clients with synchronization at intervals, e.g., Federated Averaging (FedAvg) (McMahan et al., 2017); and ii) sequential FL (SFL), where models are trained in sequential manner across clients, e.g., Cyclic Weight Transfer (CWT) (Chang et al., 2018). However, both categories of methods suffer from the "client drift" (Karimireddy et al., 2020), i.e., the local updates on heterogeneous clients would drift away from the right direction, resulting in performance degradation.
Motivation. Recently, SFL (more generally, the sequential training manner, see Algorithm 1) has attracted much attention the FL community (Lee al., 2020). Specifically, SFL demonstrates advantages on training speed (in terms of training rounds) (Zaccone et al., 2022) and small datasets (Kamp al., 2023), and both are crucial for cross-device FL. Furthermore, the sequential manner has played great role in Split learning (SL. (Gupta and Raskar, 2018; Thapa et al., 2022), an emerging distributed learning technology at the edge side (Zhou et al., 2019), where the full model is split into client-side and server-side portions to alleviate the excessive computation overhead for resource-constrainge devices. Appendix A will show that the convergence theory in this work also applicable to SL.
Xinchen Lyu is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Convergence theory is critical for analyzing the learning performance of algorithms on heteroge- neous data FL. So far, there are numerous works analyze the convergence of PFL (Li al., 2019; Khaled et al., 2020; Koloskova et al., 2020) on heterogeneous data. However, the convergence theory of SFL. on heterogeneous data, given the complexity of sequential training manner, has not been well investigated in the literature, with only limited preliminary empirical studies Gao et al. (2020, 2021). This paper aims establish the convergence guarantces for SFL and compare the convergence results of PFL and SFL.
Setup. In the following, provide some preliminaries about SFL and PFL. Problem formulation. The basic FL problem minimize global objective function:
1 M
(F = EE-D. lm E)] } m=1
M Σ
min
F(x)
where Fms fm and Dm denote the local objective function, the loss function and the local dataset of client m (m E [M], respectively. In particular, when Dm has finite data samples fEm. [[Dmi]), the local objective function also be written Fm (x) P... E.r fm(x: Sin).
Update rule of SFL At the beginning of each training round, the indices ..,..... TM are sampled without replacement from {1, 2.... M) randomly as the clients' training order. Within round, each client i) initializes its model with the latest parameters from its previous client; ii) performs K steps of local updates over its local dataset; and iii) passes the updated parameters to the next client. This process continues until all clients finish their local training. Let x denote the local parameters of the mith client (i.e., client mm) after & local steps the r-th round, and x(r) denote the global parameter in the r-th round. With SGD (Stochastic Gradient Descent) as the local solver, the update rule of SFL is as follows:
x(()
Local update x,, Xm,k
(r)
initializing as xm.0
m
m-1K
m
Global model: (r+1) (r) M.K
where B ViTn. (x) ki E) denotes the stochastic gradient of Fr... regarding parameters x x and 1) denotes the learning rate. See Algorithm 1. Notations are summarized in Appendix C.I.
(n))
(r)
Update rule of PFL. Within a round, each client i) initializes its model with the global parameters; ii) performs K steps of local updates; and iii) sends the updated parameters to the central server. The server will aggregate the local parameters to generate
global parameters. See Algorithm
In this work, unless otherwise stated, we use SFL and PFL to represent the classes of algorithms that share the same update rule Algorithm 1 and Algorithm 2, respectively.
Algorithm 1: Sequential FL
Algorithm 2: Parallel FL
Output: (R); weighted average on x (r) for training round 0, 1,..., Sample permutation T1, T2: TM
Output: x( weighted average on x())
do
for training round
1,..., R do
2
2
for m =0 1,,,, 1,2,..., M parallel do (r) ("))
.....,,.
of (1.2...., MM}
xm
for m 1,
M in sequence do
for local step k 0. ...,, K do
(r)
(r)
m
m,k+1 = x (r)
(r)
x
kn 11mm,
x
m
m >
for local step 0, ..... K do
Global model: (1+1))
Σ K
6
m, 1
x mik
11
M
Global model: x (r+1) (r)
XM.KK

---

2
Contributions
Brief literature review. The most relevant work the convergence PFL and Random Reshuf- fling (SGD-RR). There are a wealth of works that have analyzed the convergence of PFL on data heterogeneity (Li al., 2019; Khaled et al., 2020; Karimireddy et al., 2020; Koloskova al., 2020; Woodworth et al., 2020b), system heterogeneity (Wang et al., 2020), partial client participation (Li al., 2019; Yang al., 2021; Wang and Ji, 2022) and other variants (Karimireddy al., 2020; Reddi et al., 2021). In this work, we compare the convergence bounds between PFL and SFL (see Subsection 3.3) on heterogeneous data.
SGD-RR (where data samples are sampled without replacement) deemed to be more practical than SGD (where data samples sample with replacement), and thus attracts more attention recently. Gürbüzbalaban et al. (2021); Haochen and Sra (2019); Nagaraj et al. (2019); Ahn et al. (2020); Mishchenko et (2020) have proved the upper bounds and Safran and Shamir (2020, 2021); Rajput et al. (2020); Cha et al. (2023) have proved the lower bounds of SGD-RR. In particular, the lower bounds in Cha al. (2023) are shown to match the upper bounds in Mishchenko al. (2020). In this work, we use the bounds of SGD-RR to exam the tightness of that of SFL (see Subsection 3.2).
Recently, the shuffling- based method has been applied to FL (Mishchenko et al., 2022; Yun al., 2022; Cho et al., 2023; Malinovsky et al., 2023). The most relevant works are FI. with cyclic client participation (Cho et al., 2023) and FL with shuffling client participation (Malinovsky al., 2023). The detailed comparisons are given in Appendix B.
Challenges. The theory of SGD is applicable to SFL homogeneous data, where SFL can be reduced to SGD. However, the theory of SGD can be no longer applicable to SFL on heterogeneous data. This is because for any pair of indices m and (except stochastic gradient is not an (conditionally) unbiased estimator of the global objective:
1 and le 0) within round, the
E V Sm (Xm,ki E) x] + V F (x,mk.))
In general, the challenges of establishing convergence guarantees of SFL mainly arise from (i) the sequential training manner across clients and (ii) multiple local steps of SGD at each client.
Sequential training manner across clients (vs. PFL). In PFL, local model parameters updated in parallel within each round and synchronized at the end of the round. In this case, the local updates across clients are mutually independent when conditional on all the randomness prior to the round. However, in SFL, client's local updates additionally depend on the randomness of all previous clients. This makes bounding the client drift of SFL more complex than that of PFI..
Multiple local steps of SGD at each client (vs. SGD-RR). SGD-RR samples data samples without replacement and then performs step of gradient descent (GD) each data sample. Similarly, SFL samples clients without replacement and then performs multiple steps of SGD on each local objective (i.e., at each client). In fact, SGD-RR be regarded as special case of SFL. Thus, the derivation convergence guarantees of SFL is also more complex than that SGD-RR.
Contributions.
The main contributions are as follows:
We derive convergence guarantees of SFL for strongly convex, general convex and non-convex objectives on heterogeneous data with the standard assumptions in FL in Subsection 3.2.
We compare the convergence guarantees of PFL and SFL, and find a counterintuitivv compari- son result that the guarantee of SFL is better than that of PFL (with both full participation and partial participation) in terms of training rounds on heterogeneous data in Subsection 3.3.
We validate our comparison result with simulations on quadratic functions (Subsection 4.1) and experiments on real datasets (Subsection 4.2). The experimental results exhibit that SFL. outperforms PFL on extremely heterogeneous data in cross-device settings.
3 Convergence theory
We consider three typical cases for convergence theory, i.e., the strongly convex case, the general convex case and the non-convex case, where all local objectives Fi, F2,..., FMr are j-sttrongly con- vex, general convex (μ 0) and non-convex.
3

---

3.1 Assumptions
We assume that (i) F is lower bounded by F for all cases and there exists minimizer x' such that F(x") = F for strongly and general convex cases; (ii) each local objective function L-smooth (Assumption 1). Furthermore, we need to make assumptions on the diversities: (iii) the assumptions on the stochasticity bounding the diversity of (: client (Assumption 2); (iv) the assumptions on the heterogeneity bounding the diversity of local objectives {Fm m E [M]] with respect to m across clients (Assumptions 3a, 3b).
E [[mm]]] with respect to inside each
Assumption 1 (I-Smoothnesss) Each local objective function F... is I-smooth, E (1, M), i.e. there exists constant L > 0 such that V (x) (y)m(y)) s L ||x yll for all x,y IRd.
Assumptions on the stochasticity, Since both Algorithms and use SGD (data samples are chosen with replacement) as the local solver, the stochastic gradient at each client is (conditionally) unbiased estimate of the gradient the local objective function: EgwD.. [fm (x; E) x = VI,, (x). Then Assumption 2 bound the stochasticity, where measures the level of stochasticity. Assumption 2. The variance of the stochastic gradient at each client is bounded:
Be I Fmm,(())) x S oo²; Vm (1, M}
Assumptions on the heterogeneity, Now we make assumptions on the diversity of the local objective functions in Assumption 3a and Assumption 3b, also known as the heterogeneity in FL. Assump- tion 3a is made for non-convex cases, where the constants 33 and Ç measure the heterogeneity of the local objective functions, and they equal zero when all the local objective functions identical to each other. Further, the local objective functions are strongly and general convex, we use one weaker assumption 3b Koloskova et al. (2020), which bounds the diversity only the optima. Assumption 3a. There exist constants B and 5² such that
M
IIV VF(x)]] < 8 VF(())] +C²
(2)
Assumption 3b. There exists one constant C such that
1 D I
V Fm (x+)x
where x* E arg minl F(x) is one global minimizer.
3.2 Convergence analysis of SFL
Theorem 1. For SFL (Algorithm 1), there exist a constant effectivv learning rate fj == MKn and weights We, such that the weighted average of the global parameters x(R) = WR Ex= W (r)
R
(WR = En_ wy) satisfies the following upper bounds:
1 Strongly convex: Under Assumptions 1, 2, 3b, there exist a constant effective learning rate îj S 1 and weights wr = (1 -(r+1),,, such that holds that
S
uR
E (()(1)) F(x*)] s 2 JuDe exp (- WRR R
12ñ0
18L1P
18L7
+
(4)
2
MK
MK
M
General convex: Under Assumptions 1, 2, 3b, there exist a constant effective learning rate î S and weights W. 1, such that it holds that
GL
3D² nR
12ñ02
18L
18L7P
E F(x
(1)) (() - F(()) <
+
+
MK +
(5)
MK
M
Non-convex: Under Assumptions 1, 2, 3a, there exist a constant effective learning rate S 6L(3+1) and weights W, = 1, such that it holds that
min E |IVF o
3.A
+
LL
27L27R002
27L2
(6)
MK
8MK
8M
where D: == x=1 for the convex cases and A = F(x(()) F for the non-convex case.

---

The effective learning rate fj == My is used in the upper bounds as Karimireddy et al. (2020); Wang et al. (2020) did. All these upper bounds consist of two parts: the optimization part (the first term and the error part (the last three terms). Setting ij larger can make the optimization part vanishes at a higher rate, yet cause the error part to be larger. This implies that we need to choose an appropriate fj to achieve balance between these two parts, which is actually done in Corollary 1. Here we choose the best learning rate with prior knowledge of the total training rounds R, as done in the previous works (Karimireddy et al., 2020; Reddi et al., 2021).
Corollary 1. Applying the results of Theorem By choosing appropriate learning rate (see the proof of Theorem 1 in Appendix D), we can obtain the convergence bounds for SFL as follows:
Strongly convex: Under Assumptions 1, 2, 3b, there exist constant effective learning rate PR S
1j S 5T. and weights Wp- = (1 41) - such that it holds that
E F(x - - F(X*) = =Ō (UMKR" H2MKR
(HMKRR
o²
Lo² +
LCa 12M
DDD
HRR
exp
12L
General convex: Under Assumptions 1, 2, 3b, there exist a constant effective learning rate î S GT. and weights W, 1, such that it holds that
E - =
(VARR
oD VMKKR
(LO2D4) 1/3
(LG3
LD R
(MK)USTer + M1/3 +
Non-convex: Under Assumptions 1, 2, 3a, there exist a constant effective learning rate 6L(3+1) and weights Wi = 1, such that it holds that
1/2 [|F( = (L ( A)
(L302A3)1/5
(L2ç2
L3A
min OSTSR
VMKR +
+
(9)
(MK)U3Ra/S M1/3
R
where omits absolute constants, Ô omits absolute constants and polylogarithmic factors, D = |x(00) xI [|r the convex cases and A = F(x(0)-- FF* for the non-convex case.
Convergence rate. By Corollary 1, for sufficiently large R, the convergence rate is determined by the first term for all cases, resulting in convergence rates of ((1MM for strongly convex cases, OLLVMMK for general convex cases and OLL/VMKR) for non-convex cases.
SGD-RR vs. SFL. Recall that SGD-RR can be seen as one special case of SFL, where one step of GD is performed on each local objective F., (i.e. K 1 and T.2 n MR + DD2 exp
0). The bound of SFL turns to
when K = 1 and = for the strongly convex case. Then let us borrow the upper bound from Mishchenko et al. (2020)'s s Corollary 1,
pR) L
LÇ? - [ = M
[UMRR L.
(Strongly convex)
E [
DD exp
As we can see, the bound of SGD-RR only has an advantage on the second term (marked in red), which can be omitted for sufficiently large R. The difference on the constant μ is because their bound is for E [[|x( x [[2] (see Stich (2019b)). Furthermore, our bound also matches the lower LC?
bound R2 of SGD-RR suggested by Cha et al. (2023)'s Theorem 3.1 for sufficiently large R. For the general convex and non-convex cases, the bounds of SFL (when K 1 and = 0) also match that of SGD-RR (see Mishchenko et al. (2020)'s Theorems 3, 4). These all suggest our bounds are tight. Yet specialized lower bound for SFL is still required.
Effect of local steps. Two comments are included: i) It can be seen that local updates can help the convergence with proper learning rate choices (small enough) by Corollary 1. Yet this increases the total steps (iterations), leading to higher computation cost. ii) Excessive local updates do not benefit the dominant term of the convergence rate. Take the strongly convex case as an example. 2
LC?
When JMKR S M= the latter turns dominant, which is unaffected by K. In other words, when the value of K exceed á (o2/<3 H/L. R), increasing local updates will no longer benefit the dominant term of the convergence rate, Note that the maximum value of K is affected by a² /²/C2. // L and R. This analysis follows Reddi et al. (2021); Khaled et al. (2020).
5

---

3.3 PFL vs. SFL on heterogeneous data
Table 1:
Upper bounds in the strongly convex case with absolute constants and polylogarithmic factors omitte. All results are for heterogeneous settings.
Method
Bound (D ||x(0) -x"
SGD (Stich, 2019b)
μMKR + LDd exp
(-%.
uitt
(1)
PFL
(Karimireddy et al., 2020)
#MKR +
R
La²
+
ICa R2
+ DD2 exp
(-7,)
(- kRt
(2)
(Koloskova et al., 2020)
La?
LC2
+ LKD2 exp
(- (3)
(MKR
Theorem 2
aMKR
d²
La²
LC?
+ DD2
exp
(-1)
MR
SFL
Theorem 1
à aMKR
L JAMKR
12 DDD exp (-
M
SGD with a large mini-batch size. We get the bound in the table by replacing o² in the Stich (2019b)'s
2² result with MX See Woodworth et al. (2020b) for more details about Minibatch SGD.
Karimireddy et al. (2020) use 1. Σ pm=1 Fm [x)]] < B² || F to bound the heterogencity, which is equivalent Assumption 3a. The global learning rate is considered this work.
Koloskova et al. (2020) use o² ΣM Mr ity, which is weaker than Assumption 3b.
fm. x E) V... Fx.(("")) (x*) to bound stochastic-
Unless otherwise stated, our comparison is in terms of training rounds, which is also adopted in Gao et al. (2020, 2021). This comparison (running for the same total training rounds It) fair considering the same total computation cost for both methods.
Convergence results of PFL. We summarize the existing convergence results of PFL for the strongly convex case in Table 1. Here we slightly improve the convergence result for strongly convex cases by combining the works Karimireddy et al. (2020); Koloskova et (2020). Besides, we note that to derive unified theory of Decentralized SGD, the proofs of Koloskova et al. (2020) are different from other works focusing on PFL. So we reproduce the bounds for general convex and non-convex cases based on Karimireddy et al. (2020). All our results of PFL are in Theorem 2 (see Appendix E).
The convergence guarantee of SFL is better than PFL on heterogeneous data. Take the strongly convex case PFL, with an advantage 1/M on the second and third terms (marked in red). This benefits from its sequential and shuffling-basee based training manner. Besides, we can also note that the upper bounds of both PFL and SFL are worse than that of Minibatch SGD.
example. According to Table 1, the upper bound of SFL is better than that of
Partial client participation. In the more challenging cross-device settings, only a small fraction of clients participate in each round. Following the works (Li et al., 2019; Yang et al., 2021), we provide the upper bounds of PFL and SFL with partial client participation as follows:
0²
C M 5
Lo²
LC2
ul
PFL:
+
+
+
DD exp
(10)
USKR
RR S(M 1)
H²KR²
4²
L
2 (M S).
Lo²
LS2
uR
SFL:
+
DPSR2 + +uD2 exp
(11)
4SKR
JRS 11) IRSKRE
L
where clients are selected randomly without replacement. There are additional terms (marked in blue) for both PFI. and SFL, which is due to partial client participation and random sampling (Yang al., 2021). It can seen that the advantage of 1 /S (marked in red) of SFL also exists, similar to the full client participation setup.

---

4 Experiments
We run experiments on quadratic functions (Subsection 4.1) and real datasets (Subsection 4.2) to validate our theory. The main findings are i) in extremely heterogeneous settings, SFL performs better than PFL. ii) while in moderately heterogeneous settings, this may not be the case.
4.1 Experiments on quadratic functions
According to Table 1, SFL outperforms PFL on heterogeneous settings (in the worst case). Here we show that the counterintuitive result (in contrast to Gao et al. (2020, 2021)) can appear even for simple one-dimensional quadratic functions (Karimireddy et al., 2020).
Results of simulated experiments. As shown Table 2, we use four groups of experiments with various degrees of heterogeneity. To further catch the heterogeneity, in addition to Assumption 3b, we also use bounded Hessian heterogeneity Karimireddy et al. (2020):
max Fm) - F²F(X)| 5
Choosing larger values of S. and 8 means higher heterogeneity. The experimental results of Table shown in Figure 1. When Ç. 0 and 6 0, SFL outperforms PFL (Group 1). When S, and 5 = 0, the heterogeneity has no bad effect on the performance of PFL while hurts that of SFL. significantly (Group 2). When the heterogeneity continues to increase to 5 >> 0, SFL outperforms PFL with a faster rate and better result (Groups 3 and 4). This in fact tells us that the comparison between PFL and SFL can be associated with the data heterogeneity, and SFL outperforms PFL when meeting high data heterogeneity, which coincides with our theoretical conclusion.
Limitation and intuitive explanation. The bounds (see Table 1) above suggest that SFL outperforms PFL regardless of heterogeneity (the value of (x), while the simulated results show that it only holds in extremely heterogeneous settings. This inconsistency is because existing theoretical works (Karimireddy et al., 2020; Koloskova et al., 2020) with Assumptions 3a, 3b may underestimate the capacity of PFL., where the function of global aggregation is omitted. In particular, Wang et al. (2022) have provided rigorous analyses showing that PFL performs much better than the bounds suggest in moderately heterogeneous settings. Hence, the comparison turns vacuous under this condition. Intuitively, PFL updates the global model less frequently with more accurate gradients (with the global aggregation). In contrast, SFL updates the global model more frequently with less accurate gradients. In homogeneous (gradients of both are accurate) and extremely heterogeneous settings (gradients of both inaccurate), the benefits of frequent updates become dominant, and thus SFL outperforms PFL. In moderately heterogeneous settings, it's the opposite.
Table 2: Settings of simulated experiments. Each group has two local objectives (i.e., M = 2) and shares the same global objective. The heterogeneity increases from Group to Group 4.
Group 1
Group
Group 3
Group 4
(x))) 1w²
[x)))) 1/22 +
Fi(e)= n=2 + x F2(z)= = f -
(x) = x² +
Settings
F2(x)) 2
F2(x)) 3 x.
F2(z)) = -I
Co == 0,8
Co = 1,8 =0 0
C. = 1,0
Go 6= 6,118- =
to thw.hho.ooo spaium
K=2
Didance the restmum
Distinoo the astinum
Diggnoo 5o the octmumm
PEL, K=10
SFL K-10
22
120
Training rounds
Tahning Ruind
Traning Founds
Palring
rounds
Figure 1: Simulations quadratic functions. It displays the experimental results from Group 1 to Group 4 in Table 2 from left to right. Shaded areas show the min-max values.
7

---

4.2 Experiments on real datasets
Extended Dirichlet strategy. This is to generate arbitrarily heterogeneous data across clients by extending the popular Dirichlet-based data partition strategy (Yurochkin et al., 2019; Hsu et al., 2019). The difference is to add a step of allocating classes (labels) to determine the number of classes per client (denoted by C') before allocating samples via Dirichlet distribution (with concen- trate parameter a). Thus, the extended strategy can be denoted by ExDir(C, a)). The implementation is as follows (with more details deferred to Appendix G.I):
Allocating classes: We randomly allocate C' different classes to each client. After assigning the classes, we can obtain the prior distribution q. for each class c.
Allocating samples: For each class e, we draw P. ~ Dir(aq.) and then allocate a Po.m propor- tion of the samples of class to client For example, Q.
..... means that the
samples of class c are only allocated to the first 2 clients.
Experiments in cross-device settings. We next validate the theory in cross-device settings (Kairouz et al., 2021) with partial client participation on real datasets.
Setup. We consider the common CV tasks training VGGs (Simonyan and Zisserman, 2014) and ResNets (He et al., 2016) on CIFAR-10 (Krizhevsky et al., 2009) and CINIC-10 (Darlow et al., 2018). Specifically, we use the models VGG-9 (Lin al., 2020) and ResNet-18 (Acar et al,, 2021). We partition the training sets of CIFAR-10 into 500 clients / CINIC-10 into 1000 clients by ExDir(1, 10.0) and E2 10.0); and spare the test sets for computing test accuracy. As both partitions share the same parameter a = 10.0, we use C = (where each client owns samples from one class) and C = 2 (where each client owns samples from two classes) to represent them, respec- tively. Note that these two partitions are not rare in FL (Li et al., 2022). They are called extremely heterogeneous data and moderately heterogeneous data respectively in this paper. We fix the number of participating clients to 10 and the mini-batch size to 20. The local solver is SGD with learning rate being constant, momentem being O and weight decay being le-4. We apply gradient clipping to both algorithms (Appendix G.2) and tune the learning rate by grid search (Appendix G.3).
The best learning rate of SFL is smaller than that of PFL.
We have the following observations from Figure 2: i) the best learning rates of SFL smaller than that of PFL (by comparing PFL and SFL), and ii) the best learning rate of SFL becomes smaller as data heterogeneity increases (by comparing the top row and bottom row). These observa- tions are critical for hyperparameter selection.
C-1
C=1,
C-1KK=50
PRI
60-
2526151065
2520151225
252515
C=2.K=5
C=2,K=20
2-2
co-
Effect of local steps. Figure 3 is aimed to study the effects of local steps. In both plots, it can be seen that the perfor- mance of SFL improves as K increases from I to 5. This validates the theoretical conclusion that local steps can help the convergence of SFL even on heterogeneous data, Then, the performance of SFL deteriorates as K increases from 5 to 10, whereas the upper bound of SFL always di- minishes as long as K increases. This is because when K exceeds one threshold, the dominant term of the up- per bound will be immune to its change as stated in Sub-
2526151066
25201522355
3523-55065
Figure 2: Test accuracies after training VGG-9 on CIFAR-10 for 1000 training rounds with different learning rates.
1IAA VGG-9. 9
CIFAR 10. VGG.9, 2
Text Too sccurccy
section 3.2. Then, considering "catastrophic forgetting" (Kirkpatrick et al., 2017; Sheller et al., 2019) problems in SFL, it can be expected to see such phenomenon.
5FL
511 E-30
SFL outperforms PFL on extremely heterogeneous data. The test accuracy results for various tasks are collected in Table 3. When = 1 (extremely heterogeneous), the performance of SFL is better than that of PFL across all tried settings. When = 2 (moderately heterogeneous), PFL can achieve the close or even slightly better performance than SFL in some cases (e.g., CIFAR-1O/C with our observation and analysis in Subsection 4.1. Notably, on the more complicated dataset CINIC- 10, SFL shows better for all settings, which may be due to higher heterogeneity.
160
2000
3000
5050 2800 1806
Figure 3: Effect of local steps.
2/K 50). This is consistent
8

---

Table 3: Test accuracy results in cross-device settings. We run PFL and SFL for 4000 training rounds on CIFAR-10 and CINIC-10. Results are computed across three random seeds and the last 100 training rounds. The better results (with larger than 2% test accuracy gain) between PFL and SFL in each setring are marked in bold.
Setup
==1
C = 2
Dataset
Model
Method K
K 20
K 50
K K=
K 20
K 50
PFL
67.61
14.0
62.00
15.77=5.91 72.61
78.42 78.88 82.56 82.18
78.01 +1.50 +1.51
VGG-9
SFL
78.43 1246
68.86
79.67+2.30
CIFAR-10
ResNet-18
PFL
52.12 66009
44.58
14479
34.29 ::499
80.27 +.52
82.27
#1.55
79.88 1:2118
SFL
83.44
76.971148
68.91
=4229
87.16
84.90
79.38=4.4
VGG-9
PFL 52.61
13,9
45.98
$4.0822.77
55.84
53.41
1002 52.04
CINIC-10
SFL
59.11
10.74
58.71
56.67 11.88
60.82 ::061
59.78
10079
56.87 #1.1
PFL
41.12 44228
$3.19
24.71 +:489
57.70 1..04
55.59+1.2
1:32
#6.9
ResNet-18
SFL
60.36
1.3
51.84
+2.15
44.95+2200
64.17 1.06
58.05
#2.54
56.28
#2.32
Conclusion
In this paper, we have derived the convergence guarantees of SFL for strongly convex, general con- vex and non-convex objectives on heterogeneous data. Furthermore, we have compared SFL against PFL, showing that the guarantee of SFL is better than PFL on heterogencous data. Experimental results validate that SFL outperforms PFL on extremely heterogeneous data in cross-device settings.
Future directions include i) lower bounds for SFL (this work focuses on the upper bounds of SFL), ii) other potential factors that may affect the performance of PFL and SFL (this work focuses on data heterogeneity) and iii) new algorithms to facilitate our findings (no new algorithm in this work).
Acknowledgments
This work was supported in part by the National Key Research and Development Program China under Grant 2021 YFB2900302, in part by the National Science Foundation of China under Grant 62001048, and part by the Fundamental Research Funds for the Central Universities under Grant 2242022k60006.
We thank the reviewers in NeurlPS 2023 for the insightful suggestions. We thank Sai Praneeth Karimireddy for helping us clear some doubts when proving the bounds.
References
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021. URL httpttt///ppeeeeeeee httpp//pppeeeeee.///e/e/ee met/forum?idd B7v4QMR6Z9W.
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Advances Neural Information Processing Systems, 33:17526-17555 2020.
Ghadir Ayache and Salim EI Rouayheb. Private weighted random walk stochastic gradient descent. IEEE Journal Selected Areas in Information Theory, 2(1):452-455) 463, 2021.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling sgd: Random permutations and beyond. arXiv preprint arXiv:2303.077 160, 2023.
Ken Chang, Niranjan Balachandar, Carson Lam, Darvin Yi, James Brown, Andrew Beers, Bruce Rosen, Daniel L. Rubin, and Jayashree Kalpathy-Cranet Distributed deep learning networks

---

among institutions for medical imaging. Journal of the American Medical Informatics Associa- tion, 25(8):945-955 954, 2018.
Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the conver- gence of federated averaging with cyclic client participation. arXiv preprint arXiv:2302.03 109, 2023.
Edwige Cyffers and Aurélien Bellet. Privacy amplification by decentralization. In International Conference on Artificial Intelligence and Statistics, pages 5334-5353. PMLR, 2022.
Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. Cinic- 10 is not imagenet or cifar-10. arXiv preprint arXiv: 1810.0350.. 2018.
Yansong Gao, Minki Kim, Sharif Abuadbba, Yeonjae Kim, Chandra Thapa, Kyuyeon Kim, Seyit A Camtep, Hyoungshick Kim, and Surya Nepal. End-to-end evaluation of federated learning and split learning for internet of things. In 2020 International Symposium on Reliable Distributed Systems (SRDS), pages 91-100. IEEE, 2020.
Yansong Gao, Minki Kim, Chandra Thapa, Sharif Abuadbba, Zhi Zhang, Seyit Camtepe, Hyoung- shick Kim, and Surya Nepal. Evaluation and optimization of distributed machine learning tech- niques for internet of things. IEEE Transactions on Computers, 2021.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic)
gradient methods. arXiv preprint arXiv:2301.11235, 2023.
Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 116:1-8, 2018.
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo A Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186:49-84, 2021.
Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pages 2624-2633, PMLR, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint 1909vv:909.0660 2019.
Divyansh Jhunjhunwala, Shiqiang Wang, and Gauri Joshi. Fedexp: Speeding up federated averaging via extrapolation. In The Eleventh International Conference on Learning Representations, 2023.
URL httph:t///////tt tttttp:///peereeet http///ppppreeeeee/e/ee/ee// net
Björ Johansson, Maben Rabi, and Mikael Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization, 20
19:1157-1170, 2010.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Ad- vances and open problems in federated learning, Foundations and Trends in Machine Learning,
14(1-2):1-210, 2021.
Michael Kamp, Jonas Fischer, and Jilles Vreeken. Federated learning from small datasets. In The Eleventh International Conference on Learning Representations, 2023. URL https:
// wttp:e/wwww...eeeooouiiiiiieeeee
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 1132-5143. PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data, In International Conference on Artificial Intelligence and Statisties, pages 4519-4529. PMLR, 2020.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinske Barwinska, et al. Overcom- ing catastrophic forgetting neural networks. Proceedings of the national academy of sciences, 114(13):3511-3526 2017.
10

---

Anastasia Koloskova, Nicolas Loizou, Sadra Boreini, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pages 5381 5381-5393. PMLR, 2020.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):227--2222 1998.
Jin-woo Lee, Jaehoon Oh, Sungsu Lim, Se- Young Yun, and Jae-Gil Lee. Accurate and scalable federated learning via the ring-based architecture. arXiv preprint
Tornadoaggregate:
arXiv:2012.03214. 2020.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning non-iid data silos: An experimental study. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 965-978. IEEE, 2022.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2019.
Tao Lin, Lingjing Kong, Sebastian Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing 3ystems, 33:2351-22663, 2020.
Grigory Malinovsky, Samuel Horváth, Konstantin Burlachenko, and Peter Richtárik. Federated learning with regularized client participation. arXiv preprint arXIv:2302.03660 2023.
Xianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali H Sayed, and Wotao Yin. Walkman: A communication-effictne random- walk algorithm for decentralized optimization. IEEE Transac- fions Signal Processing, 68:2513-25 1528,, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicaton--eficieentt learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pages 12822 PMLR, 2017.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffting: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33:17309-17320,
2020.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In International Conference on Machine Learning, pages 15718-15749, PMLR, 2022.
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703-4711. PMLR, 2019.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arX1v:1912.13213. 2019.
Liangqiong Qu Yuyin Zhou, Paul Pu Liang, Yingda Xia, Feifci Wang, Ehsan Adeli, Li Fei-Fei, and Daniel Rubin. Rethinking architecture design for tackling data heterogeneity in federated learn ing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10061-10071, 2022.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of sgd without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020.
S Sundhar Ram, A Nedić, and Venugopal V Veeravalli. Incremental stochastic subgradient algo- rithms for convex optimization. SIAM Journal on Optimization, 20(2):691-717, 2009.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Leurning Representations, 2021. URL https: http://ppreeeieeeee///
id=
LkFG31B13U5.
Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 2250-3284 PMLR, 2020.

---

Itay Safran and Ohad Shamir. Random shuffling beats sgd only after many epochs on ill-conditioned problems. Advances in Neural Information Processing Systems, 34:15151-15161. 2021.
Micah J Sheller, G Anthony Reina, Brandon Edwards, Jason Martin, and Spyridon Bakas. Multi- institutional deep learning modeling without sharing patient data: A feasibility study on brain tumor segmentatiin.. In Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 4th International Workshop, BrainLes 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Revised Selected Papers. Part I 4, pages 92-104. Springer, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Con- ference on Learning Representations, 2019a. URL https: /tttpee//ppenreview. contt//orummii id= S1g2JnReFX.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv: 997.04232, 2019b.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint 19Xv5:1009005550,, 2019.
Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, and Seyit A Camtepe. Advancements of federated learning towards privacy preservation: from federated learning to split learning. In Federated Learning Systems, pages 79-109. Springer, 2021.
Chandra Thapa, Pathum Chamikara Mahawaga Arachchige, Seyit Camtepe, and Lichao Sun. Splitfed: When federated learning meets split learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8485-8493, 2022.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. The Journal of Machine Learning Research, 22(1):9709-977) -958, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611-7622 2020.
Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint 044.222006.07223 2022.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client par- ticipation. Advances in Neural Information Processing Systems, 35:19124-19137, 2022.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mema- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343 PMLR, 2020a.
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogencous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6222 2020b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv: 770.007777 2017.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker partici- pation in non-IID federated learning. In International Conference on Learning Representations, 2021. URL https: /t///oppevvvieeeeee http:nttt//oooomoddddooaoaaa/a
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022. net.
Mikhail Yurochkin, Mayank Agarwal. Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Interna- tional conference on machine learning, pages 7252-7261. PMLR, 2019.
Riccardo Zaccone, Andrea Rizzardi, Debora Caldarola, Marco Ciccone, and Barbara Caputo. Speeding up heterogeneous federated learning with sequentially trained superclients. In 2022 26th International Conference on Pattern Recognition (ICPR), pages 3376-3382 IEEE, 2022.
12

---

Dun Zeng, Siqi Liang, Xiangjing Hu, Hui Wang. and Zenglin Xu. Fedlab: A flexible federated learning framework. arXiv preprint arXiv:2107.11621, 2021.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- ent descent algorithm for nonconvex optimization. arXiv preprint arXiv: #rXiv:/708..1012 2017.
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. 2018.
arXiv preprint arXiv:1803.0m
Zhi Zhou, Xu Chen, En Li, Liekang Zeng, Ke Luo, and Junshan Zhang. Edge intelligence: Paving the last mile of artificial intelligence with edge computing. Proceedings of the IEEE, 107(8); 1738-1762, 2019.
13

---

Appendix
Applicable to Split Learning
15
Related work
17
Notations and technical lemmas
19
C.I Notations
19
C.2 Basic identities and inequalities
19
C,3 Technical lemmas
20
D Proofs of Theorem
23
D.I
Strongly convex case
24
................................
D.1.1
Finding the recursion
24
D.1.2
Bounding the client drift with Assumption 3b
26
D.1.3
Tuning the learning rate
27
D.1.4 Proof of strongly convex case of Theorem and Corollary
29
D.2
General convex case
30
D.2.1 Tuning the learning rate
30
D.2.2 Proof of general convex case of Theorem and Corollary
31
D.3 Non-convex case
31
D.3.1 Bounding the client drift with Assumption 3a
32
D.3.2
Proof of non-convex case of Theorem and Corollary
34
E Proofs of Theorem
35
E.1
Strongly convex case
36
E.1.1
Find the per-round recursion
36
E.1.2
Bounding the client drift with Assumption 3b
38
E.1.3
Proof of strongly convex of Theorem 2
39
E.2
General convex case
................................
40
E.2.1
Proof of general convex case of Theorem and Corollary
40
E.3
Non-convex case
40
E.3.1
Bounding the client drift with Assumption 3a
42
E.3.2
Proof of non-convex case of Theorem 2
43
F Simulations on quadratic functions
44
More experimental details
45
G.I Extended Dirichlet partition
45
G.2 Gradient clipping.
46
G.3 Grid search
49
G.4 More experimental results
50
14

---

A Applicable to Split Learning
Split Learning is proposed address the computation bottleneck of resource-constrained devices, where the full model is split into two parts: the client-side model (front-part) and the server-side model (back-part). There two typical algorithms in SL,, i.e., Sequential Split Learning (SSL)² (Gupta and Raskar, 2018) and Split Federated Learning (SplitFed)) (Thapa et al., 2022). The overviews of these four paradigms are illustrated in Figure 4
SFL
Sequential Manner
PFL
Paraliel Manner
Clent
Cheet
Concerscaton
AvD
Cleee
SplitFed
Av2
Conmuntrntion
Avg
Pat
Mivin Servvee
Figure 4: Overviews of paradigms in FL and SL. The top row shows the FL algorithms, SFL and PFL. The bottom row shows the SL algorithms, SSL and SplitFed.
Training process of SSL. Each client keeps client-side model and the server keeps one server- side model. Thus, each client and the server can collaborate to complete the local training of a full model (over the local data kept in clients). Each local step of local training includes the following operations: 1) the client executes the forward pass on the local data, and sends the activations of the cut-layer (called smashed data) and labels to the server; 2) the server executes the forward pass with received the smashed data and computes the loss with received labels; 3) the server executes the backward pass and send the gradients of the smashed data to the client; 4) the client executes the backward pass with the received gradients. After finishing the local training, the client sends the updated parameters of its client-side model to the next client. This process continues until all clients complete their local training. See the bottom-left subfigure and Algorithms 3, 4. For clarity, we adjust the superscripts and subscripts in this section, and provide the required notations in Table 4.
Training process of SplitFed. Each client keeps one client-side model and the server keeps (named as main server) keeps multiple server-side models, whose quantity the same the number of clients. Thus, each client and its corresponding server-side model in the main server can complete the local training of full model in parallel. The local training operations of each client in SplitFed are identical to that in SSL. After the local training with the server, clients send the updated parameters to the fed server, one server introduced in SplitFed achieve the aggregation of client-side models. The fed server aggregates the received parameters and sends the aggregated (averaged) parameters to the clients. The main server also aggregates the parameters of server-side models it kept and updates them accordingly. See the bottom-right subfigure and Thapa et al. (2021)'s Algorithm 2.
Applicable SL. According to the complete training process of SSL and SplitFed, we can conclude the relationships between SFL and SSL, and, PFL and SplitFed as follows:
SSL. and SplitFed can be viewed as the practical implementations of SFL and PFL respectively in the context of SI.
SSI. and SplitFed share the same update rules with SFL. (Algorithm 1) and PFL (Algorithm 2) respectively, and hence, the same convergence results.
Pn SSL, client-side model parameters can be synchronized in two modes, the peer-to mode and cen- tralized mode, In the peer-to-peer mode, parameters are sent to the next client directly, while the centralized mode, parameters are relayed to the next elient through the server. This paper considers the peer-to-peer mode. TThere are two versions of SplitFed and the first version is considered in this paper by default.
15

---

Table 4: Additional notations for Section A.
Symbol
Description
Tm: h
number, index of local update steps (when training) with client nm
full/ctient-siddeserrrrsssii local model parameters (r.k) (r.)), (n.8) Xe.m Xa,m
(r.k) (r,k) (r.k)
/xc.m Ixamm
after &s local updates with client Tm in the r-th round (eatures/lbeel/prcciitooo
(() /o.l)// (irk)
after ko local updates with client Tm in the r-th round
x(11 (r)) xx11/2 /xc""
global model parameters the r-th round smashed data (activation of the cut layer)
htllcclientsiidessereeee
A kn.k)
after & local updates with client T. in the r-th round loss function with client mm
(r.k)
gradients of the loss regarding (r.k)
on input (r.k)
Tm (x,m
(r,
(r.k))
(r.k) gradients of the loss regarding A (r.k) parameters Xg,m
Xg.m
mm (Xem (())))
gradients of the loss regarding x on input x(r.k)
Algorithm 3: Sequential Split Learning (Server-side operations)
Main Server executes:
Initialize server-side global parameters x; for round 0, .., R do
m2:--.; TM of (1,2,.... .,, as clients' update order for m 1, ... M in sequence do
Sample a permutation
Initialize server-side local parameters: (r.0)
X3 (1y7m-1)
m
x 8,m
m
for local update step k = =0...., Tm do (r.k) y((n)) from client
Receive (A (r(rk)
// Com.
Execute forward passes with smashed data A (n,)
Calculate the loss with (fr(n.)) (((kk)
9
Execute backward passes and compute Vl (xe,m (())))
Send Ve.., (A (r,4), (r,K), client
// Com.
(n.)) Update server-side parameters: Xa,m Xe.m
(r.k+1)
1/ Cx (x (r.))
(n,)),
Algorithm 4: Sequential Split Learning (Client-side side operations)
Client T. executes:
Request the latest client-side parameters from the previous client
// Com.
Initialize client-side parameters: (r.0)
m = 1
(r5mm11 x-
x
1
for local update step = O,..., Tm do
Execute forward passes with data features x (r.k) m
(r.k)
Send (A (r.k) y(rkk)) to the server
// Com.
Receive Vl.... (r.k), (r.k)
// Com.
Execute backward passes and compute V (r.k).
(Xe,m X (r.k)
x((n))
Update client-side parameters: xe.m +- xc,m 1) V Ex (rik),
(r.++) (r,k)
x- (rit))
16

---

B Related work
Convergence of PFL. The convergence of PFL (also known as Local SGD, FedAvg) has devel- oped rapidly recently, with weaker assumptions, tighter bounds and more complex scenarios. Zhou and Cong (2017); Stich (2019a); Khaled et al. (2020); Wang and Joshi (2021) analyzed the conver- gence of PFL on homogeneous data. Li et al. (2019) derived the convergence guarantees for PFL with the bounded gradients assumption on heterogeneous data. Yet this assumption has been shown too stronger (Khaled et al., 2020). To further catch the heterogeneity, Karimireddy et al. (2020); Koloskova et al. (2020) assumed the variance of the gradients of local objectives is bounded either uniformly (Assumption 3a) or on the optima (Assumption 3b). Moreover, Li al. (2019); Karim- ireddy et al. (2020); Yang et al. (2021) also consider the convergence with partial client participation. The lower bounds of PFL are also studied in Woodworth al. (2020a,b); Yun et al. (2022). There are other variants in PFL, which show a faster convergence rate than the vanilla one (Algorithm 2), e.g., SCAFFOLD (Karimireddy al., 2020).
Convergence of SGD-RR. Random Reshuffling (SGD-RR) has attracted more attention recently, as it (where data samples are sampled without replacement) is more common in practice than its counterpart algorithms SGD (where data samples are sample with replacement). Early works (Gür- büzbalaban et al., 2021; Haochen and Sra, 2019) prove the upper bounds for strongly convex and twice-smooth objectives. Subsequent works (Nagaraj et al., 2019; Ahn et al., 2020; Mishchenko et al., 2020) further prove upper bounds for strongly convex, convex and non-convex cases. The lower bounds of CGD-RR&a are also investigated in the quadratic case Safran and Shamir (2020, 2021) and the strongly convex case (Rajput et al., 2020; Cha et al., 2023). In particular, the lower bounds in Cha et al. (2023) are shown to match the upper bounds in Mishchenko al. (2020) for the both strongly convex and general convex cases. These works have reached a consensus that SGD-RR is better than SGD least when the number of epochs (passes over the data) is large enough. In this paper, we use the bounds of SGD-RR to exam the tightness of our bounds of SFL.
There are also works studying the randomized incremental gradient methods are also relevant (Ram et al., 2009; Johansson et al., 2010; Ayache and EI Rouayheb, 2021; Mao et al., 2020; Cyffers and Bellet, 2022), which consider a single update each client and focus on random walks.
Shuffling-based methods in FL. Recently, cuuffing--bssed methods have appeared in FL (Mishchenko et al., 2022; Yun et al., 2022; Cho et al., 2023). Mishchenko al. (2022) gave the convergence result of Federated Random Reshuffling (FedRR) as application to Federated Learn- ing of their theory for Proximal Random Reshuffling (ProxRR). Yun et al. (2022) analyzed the convergence of Minibatch RR and Local RR, the variants of Minibatch SGD and Local SGD (Local SGD is equivalent to PFL this work), where clients perform SGD-RR locally (in parallel) instead of SGD. Both FedRR and Local RR are different from SFL. from the algorithm perspective. See Yun et al. (2022)'s Appendix A for comparison.
The most relevant works are FL with cyclic client participation (Cho et al., 2023) and FL with shuffling client participation (Malinovsky et al., 2023) (we note them when preparing this version).
(4.00)
(N
Round
Round
Round 3
(k-.0.0) = (.R) after the 4 cycle-epoch of K rounds
Figure 5: Illustration of FL with eyclic client participation with M = 12 clients divided into K groups. In each training round, N = 2 clients are selected for training from the client group. All groups are traversed once in a cycle-epoch consisting of K training rounds. (Cho et al., 2023).
Discussion about FL with cyclic client participation. Cho et al. (2023) consider the scenario where the total M clients are divided into K non-overlapping client groups such that each group contains M/K clients. In each training round, the sever selects a subset of N clients from group without replacement for training in this round. One example is shown in Figure 5. As said in the paragraph "Cyclic Client Participation (CyCP)" in their Section 3 (Problem Formulation), the groups' training
17

---

order of FL with cyclic client participation is pre-determined and fixed. In contrast, the clients' training order of SFL (precisely, Algorithm will be shuffled the beginning of each round.
It can be verified by Cho et al. (2023)'s Theorem 2. Letting K and N M/K M and K = M and N M/K = 1, we get the bounds for PFL and SFL, respectively;
LZ Lo² + p²M2 PFL: ò (1PMKR
where we have omitted the optimization term and changed their notations ours (change to 0, to S, V to T It).
SFL: Ō (
Lod +
L2
L'C² M
+
12KR R²
where we have omitted the optimization term and changed their notations ours (change a to Ç, ? to 0, v to Ç. T to M It). As we can see, we do not see clear advantage of SFI. like ours.
Clients
Comm, Round
Comm. Round
Double Shuffling (C=2, M=6, N-3)
1
2
Locol stops
Local
Local
Model Flow
Meta Epoch
Server
Figure 6: Visualization of Fl. with shuffling client participation for clients, each with datapoints. Two clients are sampled in each communication round (Malinovsky et al., 2023).
Discussion about FL with shuffling client participation. At the beginning of each meta epoch, FL with shuffling client participation partition all M clients into M/C cohorts, each with size C. These cohorts are obtained using the without replacement sampling of clients. Each meta epoch contains R M/C communication rounds. At each communication round, clients in a cohort participate in the training process. One example is shown in Figure 6. It is noteworthy that SGD-RR is used as the local solver in Malinovsky al. (2023) while SGD is used in this paper.
Letting C = 1, R M, = in their Theorem 6.1, we can get the bounds for SFL:
SFL (Malinovsky et al., 2023): O LL.K + D2 exp (-uMKRn) with S L
SFL (Theorem 1): O (LMK3 nD exp (-MMKRR) with S LMK
where we only considered the heterogeneity terms (let of = 0 for Malinovsky et al. (2023) and for ours) and changed their notations to (change Y to 17. N to K, न. (.). Their bound almost matches ours, with some differences on the constants
caused by using different local solvers. However, their results and restrictions on y, which is limited to the where the number local steps equals the size of the local dataset. It is still uncertain whether their results for SGD-RR can be generalized to situations with varying numbers of local steps.
18

---

C
Notations and technical lemmas
C.1
Notations
Table 5 summarizes the notations appearing in this paper.
Table Summary of key notations.
Symbol
Description
R, r
number, index of training rounds number, index of clients
M, m
K, k
number, index of local update steps number participating clients
{T1, ....... aas is a permutation of (1, } learning rate (or stepsize)
effective learning rate (7j M Knj in SFL and rj == Knj in PFL)
jestrong convexity constant
I-smoothness constant (Asm. 1)
upper bound on variance stochastic gradients at each client (Asm. 2)
B.C
constants in Asm. 3a to bound heterogeneity everywhere
S.
constants in Asm. 3b bound heterogeneity at the optima
F/Fm
global objective/local objective of client m global model parameters in the r-th round local model parameters of the m-th client after local steps in the r-th round
x(r)
x
(r)
m f ( {) denotes the stochastic gradients of Fx,. regarding x xm.k
mankk
ExDir(C, a)
Extended Dirichlet strategy with parameters C' and (see Sec. G.I)
C.2 Basic identities and inequalities
These identities and inequalities are mostly from Zhou (2018); Khaled al. (2020); Mishchenko et al. (2020); Karimireddy et al. (2020); Garrigos and Gower (2023).
For any random variable x, letting the variance can be decomposed as
|
E
[x]1]]
E
||x|
E
(12)
In particular, its version for vectors with finite number of values gives
a. x
3P
(13)
n
where vectors I E Rd are the values of x and their average is T Σn
Jensen's inequality. For any convex function and any vectors 2I...., Fn we have
h
x;
h(xx))
(14)
n
As special case with h(x) = ||>|||
we obtain
2
02
c
(15)
71
n1
19

---

Smoothness and general convexity, strong convexity. There are some useful inequalities with respect to L-smoothness (Assumption 1), convexity and p-strong convexity. Their proofs can be found in Zhou (2018); Garrigos and Gower (2023).
Bregman Divergence associated with function h and arbitrary ar y is denoted
Dr. (x, y) = h(() - h(y) - (Vh(y), y)
When the function h is convex, the divergence is strictly non-negative. A more formal definition can be found in Orabona (2019). One corollary (Chen and Teboulle, 1993) called three-poimt-identie -ideiitt is,
D (z, æ) + (x. y) - (n( y) = (Vh(y) Vh(z), 2 - x)
where y. 2 is three points in the domain. Let h be L-smooth. With the definition of Bregman divergence, consequence of L-smoothness is L
(x y) h(x) hly) (Vh(y), x y) 1 yll
(16)
Further, is L-smooth and lower bounded by h.. then
[[h(<>]] s 2L (h(x)) h.).
(17)
h is T-ssmoohh and convex (The definition of convexity can found in Boyd et al. (2004)), then
Da(x.y) 2 2L [Vh(z) Vh(y))l
(18)
The function h Rd + R is y-strongly convex if and only if there exists convex function g Rdd - such that h(x)) = g(x)) + $ ||=
If h is j-strongly convex, it holds that
x 31²²5 (z(x,))
(19)
C.3 Technical lemmas
Lemma 1 (Karimireddy et al. (2020)). Let {E be sequence of random variables. And the random sequence {x: satisfy that x; E R is a function of Eis Ei. for all i. Sup- pose that the conditional expectation Eg [xilEi-1,... E.. e; (i.e., the vectors {xi ee form a martingale difference sequence with respect to {Ei)), and the variance is bounded by
Eg: ||x: -e,1 E.-1........... L1 S 02 Then it holds that
n
x
ex)
Σ
E
|
S no²
(20)
Proof. This conclusion has appeared in Stich and Karimireddy (2019)'s Lemma 15, Karimireddy al. (2020)'s Lemma 4 (separating mean and variance) and Wang et al. (2020)'s Lemma 2, which is useful for bounding the stochasticity.
|]
E
Σ
-x) e;)
x
Σ
E
|
E [x:
e:)
Tx;; e,)
i=1
jzi
Without loss of generality, we can assume that j. Then the cross terms in the preceding equation can be computed by the law of total expectation:
[x, e,) [x, e,)]
= E E [x, e.) Tx), - e,)le, .,), E
= E (x; e;)) B((x,
=0
0
20

---

Here E[(x; -e))s E1] = 0 can be proved by mathematical induction and the law of total expectation. Then,
E x; eq 12"
x eall² 1 61] S no?
which is the claim of this lemma. Note that since Eg, [xil Iy. Ei] e;, the conditional expec- tation e; is not deterministic but a function of Ei-1,...,5 E1.
Lemma (Karimireddy et al. (2020)). The following holds for any L-smooth and u-strongly convex function h, and any y. in the domain of h:
V (l()); x y) h(z) h(y) + : 1y- -
f1y=21²- =112-1. L || - -x=1²-
(21)
Proof. Using the three-poin--dennttyy we get
(Vh(z), = y) (x (z, x) + h(z) h(y)
Then, get the following two inequalities using smoothness and strong convexity of h:
(Vh()), = y)
/ 2ー
yy x²1
L =| - -=11 + h(z) - h(y)
2
Further, using Jensen's inequality (i.e., 11 =1²² < 2([1x0 - =21²+ 11 - 2²1² we have
M 2
yy x||
d ly =11
1 || x||
4
2
Combining all the inequalities together have
(Vh(z), y) h(z) h(y)
+
/1 11 =1(
L 1
2z - x!?
4
1(z) h(y))
4 11 =1|
L1| x0
which is the claim of this lemma.
Lemma (Simple Random Sampling). Let 21, 22,,... xn be fixed units (e.g., vectors). The popu-
lation mean and population variance are give
x -
== E 11; 1
Draw E [m]= (1.2....,T1) random unity X Xxz.... Xx, randomly from the population. There are two possible ways of simple random sampling, well known as "sampling with replacement (SWR)" and " "sampling without replacement (SWOR)". For these ways, the expectation and variance of the sample mean XS = E Na, satisfies
22
SWR
E
X
(22)
SWOR:
E X
E
X
2
n
(23)
s(n
1)
Proof. The proof of this lemma is mainly based on Mishchenko et al. (2020)'s Lemma 1 (A lemma for sampling without replacement) and Wang et al. (2020)'s Appendix G (Extension: Incorporating Client Sampling). Since the probability of each unit being selected equals 1 in each draw, we can get the expectation and variance of any random unit Xx, at the p-th draw: x
E [
Σ Di Pr(XT,, x;i)
n
i=1
Var(X,,,)
= E ||xTT
27
Σ
|
Pr(xT, = 22)
Σ x x
= c
2m
21

---

where the preceding equations hold for both sampling ways. Thus, we can compute the expectations of the sample mean for both sampling ways as
x
p=1
p=1
which indicates that the sample means for both ways unbiased estimators of the population mean. The variance of the sample mean can be decomposed as
xTp
Var Var(x (x,) + s p= qpp
Cov (X,,, Xxa)
p=1
p=1
Next, we deal with these two ways separately:
SWR: holds that Cov (x Xx,) 0, Vp + y since Xx,, Xn, independent for SWR. Thus, get E X 1 Σp= Var(xx;p <
SWOR: For p + q, we have
Cov(Xx,, XT,)) E [(X,T x. Xx, a;)
(a n., R. a)) Pr(xx, Bi, Xx, x.)),
Since there are n2n2 1) possible combinations of (Xx, Xn,) and each has the same probability, get Pr(x=r 2i;; Xxy 221)) x)n As consequence, have
Cov XTT,) n(n 1)
[ 2, x)]
1=1 jøf
(x:: x)
1
n(n 1)
n 1)
<2
(24)
n1 -
Thus have E. E T
a 1)
6²
(n-e)
c²
=(n-1) 13
When n infinite (or large enough), we get
E F Jswne
1 +. This constant has appeared in
[3]
2 ssux
Karimireddy et al. (2020)'s Lemma 7 (one round progress) and Woodworth et al. (2020b)'s 's Section 7 (Using Subset Machines in Each Round).
Lemma 4. Under the same conditions of Lemma 3, the way "sampling without replacement" and let bm, (i)
K 1,
i S m
Then for S S M (M 2 2), it holds that
b:
m
S
K-1
bmn (5)
E
Xxn
T)
52
(25)
2
m=1 k=
Proof. Let focus on the term in the following:
m Bm
m-3
E
XT:
x)
[x x) + (Xxm x)
0
K²B
Σ XT.
x7)
+ A.2
x1/
+ 2KKE
Σ
(X 3t)
(xim z))
(26)
22

---

For the first term on the right hand side in (26), using (23), we have
m
Σ
23
(m 1)
(m 1)) K2C2
M
For the second term on the right hand side in (26), we have
||
- =
x1
For the third term the right hand side in (26), we have
)
2(m 1)
2KEE Σ (x,r - (X,, 2r)
2K
(x - 2. X
x))
(24)
KkÇ²
M
1=1
where we use (24) in the last equality, since E .1, 10-mm-p + m. With these three preceding equations, we get
m bm, (6)
(m 1)(M (m (m--1) M
2(m - 1) Kkç²
(x,,
F)
K2C² 226
M -
1=0
Then summing the preceding terms over and k; we can get
27
$
m
Bm
(())
Σ
Σ
(xx;
- a.)
m=1
k=0
1=1
f=0
3
8
R3S2 8
K-1
2KÇ²
S
K-1
Σ
(m - 1)
Σ m=1
(m 1)² + SC²
Σ
k22
(m
1) k=
Σ
M -
M
M
m=1
k=0
m=1
Then applying the fact that Ek-1 k the preceding equation as
(K-I)K
and Σ k==
K-1
122
(K - ()K((K 1)
we can simplify
M
K-1
bm, (1)
E
Σ
(Xn; +t)
m=1
k=0
j=0
-
1
SK2 - 1) - SK(K2-1) -
1
M (S - 1)5
(25 1) -
1
1)k-}
1
s 52
1
2 2
which is the claim of this lemma.
D Proofs of Theorem
In this section, we provide the proof of Theorem I for the strongly convex, general convex and non-convex cases in D.1, D.2 and D.3, respectively.
In the following proof, we consider the partial client participation setting. So we assume that permutation 21,2.... M) in a certain training round and only the first selected clients {TI, .T...., T will participate in this round. Without otherwise stated, we use [[]] to represent the expectation with respect both types of randomness (i.e., sampling data samples and sampling clients T))
(T,, (2,, .., TM)
23

---

D.1
Strongly convex case
D.1.1 Finding the recursion
Lemma S. Let Assumptions 1, 2, 3b hold and assume that all the local objectives are p-strongly convex. If the learning rate satisfies n I 6LSK. then it holds that
E | -x x² 19/ $ (1- (1-1 E |1 -x110
M
-
+ 4SK
12
-1) C2
S(M
3 SKnl (r(x((),,,))
2
xx)
8
E
x
(27)
3
k=
Proof. According to Algorithm 1, the overall model updates of SFL after one complete training round (with clients selected for training) is
9 K
Ax = (r+1) - x(() 11
Σ mmm.
m=1
k=0
where (r) Bx V Sm mm,k {) is the stochastic gradient of Fr,.. regarding the vector (r))
Thus,
m,,k
$ K-
E [
E V F
(xm,
m=1 k=0
In the following, focus single training round, and hence drop the superscripts for while, e.g., writing Xm.s to replace x x Specially, we would like to use x to replace xi,0- Without otherwise stated, the expectation is conditioned on xe(")
We start by substituting the overall updates:
E
xx + Ax
x1]
x x" ||
2E (x
x",
Ax)] +E |
K
K
x
x ||
27
E
(VF Tm xxx))
Σ
Σ
8
(28)
k=0
m=
K=U
We can apply Lemma with æ Xm.ks y x", right hand side (28):
and h = Fr... for the second term on the
S K-1
2m
E
BRVF xm x xx)]
m==
k=0
$
Frim Fr -x,((x))+ 1.
||x x"1 L 6l x||²]
22
A=
5 K
< x=2
JuSKn ||x -
1
1x-xx111 2² 2 + 2Ln
|mm,k - x|(
(29)
m= Am
24

---

For the third term on the right hand side in (28), using Jensen's 's inequality, we have
g
mm. dk
K
4E
ggmmi
V xm (Xm,k))
4E
Σ
am (Xm,
V Fa (x))
k=U
12
Σ K
4E
Σ
FT (x) VF (xx))
+ 4E
V (x*)
(30)
K=
Seeing the data sample Sm,k: the stochastic gradient Ba... the gradient V (Em,k) as &,. x, e; in Lemma respectively and applying the result of Lemma 1, the first term on the right hand side in (30) can be bounded by 4SKo". For the second term on the right hand side in (30), we have
K Σ
S Σ Σ
(15)
4E
VF Fi (Xm,k) VF Km (x))
4SK
IVF
Fm (Xm,
V Fm (xx]l²
km0
s K-
Asm.
4122KK
Σ
E [|mm,k
-x|1]
m=1
k=0
For the third term the right hand side in (30), we have
S K-1
K-1
(15)
4E
Fr Rm (x) - VF xm (xx))
4SK
E
V Tm (x) - V mm
(x*)
m=1
kmm
m==
km0
K-1
8LSK
E
DD x))
m== k=
SLS K D=(xxxx))))
(31)
where the last incquality is because E [D.., (x.x") Dx(x,x"). The forth term the right hand side in (30) can be bounded by Lemma as follows:
4E
Σ
K
V m w0/l
||
23)
K² M - S
S(M 1) c.
With the preceding four inequalities, we can bound the third term on the right hand side in (28):
s
K-1
E
San..
de
m=1
k=
K-1
M - S
< 4SKo² 4L2SK Σ
Σ
E
||xm,k
x1(]
S(M 1) 22
k=0
(32)
Then substituting (29) and (32) into (28), we have
x + Ax - xx11]]
1xxxx111]
< (1 μ μSkn
||x - x" + 4 M M-S S
S(M - 1) c
8 K-1
- - - 4LSKK) 21 +2SKg)) Σ
E2
|mmx x13
m=1 k=
x (1- +
452
M M-S
S(M - 1)
8 K-1
2 SKnDr +
8 In Σ Σ
|mm,k - -
E
3
m=
k=0
25

---

where we use the condition that S 1 after recovering the superscripts and taking unconditional expectation.
6LSK in the last inequality. The claim of this lemma follows
D.1.2 Bounding the client drift with Assumption 3b
Similar to the "client drift" in PFL (Karimireddy et al., 2020), define the client drift in SFL:
S
E, Σ
Σ
(r) X m,k
x(>1
(33)
Lemma 6. Let Assumptions 1, 2, 3b hold and assume that all the local objectives are j--strongly convex. If the learning rate satisfies 1) S GLSK then the client drift is bounded:
9 52 E,
9 + + 3LS Dr(x("),
(34)
4
Proof. According to Algorithm 1, the model updates of SFI. from x(r) to x (r)
m, is
m
(m)
(r) = =
m.k
with (1) K 1, is m 1-1,
In the following, we focus on a single training round, and
i i= m
hence we drop the superscripts r for a while, e.g., writing Xm. to replace ((r) x Specially, we would
like to use x to replace X1.0-
(r)
Without otherwise stated, the expectation is conditioned on x(*),
We use Jensen's 's inequality to bound the term E [|xm. x||] = 1)²E
m bm, f=0
Bm..)
[mm,k
x
bm. a
bm. 2())
Σ
(gmiJ V. (X+,a))
+ 4
Σ
V (VF
V VF+;
1=0
==
b
bm, bm.
+ 2
(V (x) VI (x)x())))
+ 2
VF (x*)
Applying Lemma I to the first term and Jensen's 's inequality to the second, third terms on the right hand side in the preceding inequality respectively, can get
E
1mmkk- - x||3]
(i)
bm. (m)
4nl
E
g Viz, (xx + 4n² BanB Bmnk
E
V.F (x:,) (x)(()))
1=0
m bm.uli
m
bi)
+ 4n Bmnk
IIFF, (x) - VFx + 2
Σ
V (x")
(35)
1=0
1=0
where Bm,k = Σm Enmo
bm (m - 1)K + k. The first term on the right hand side in (35) is bounded by ABm an72o2 o² For the second term on the right hand side in (35), we have
E [VF.. VF (x)1 S
1, ||xE]
x||]
26

---

For the third term on the right hand side in (35), we have
(18)
E [v,
Vaa (x S
2LE DF,, -2DD)xxx)
(36)
As result, get
b(8)
E ||xmkk- x1|²
s 4B 4mm
+ B,,
E
|xx x11 + 8L m. Dr (x,x')
1=1 ==
bm.k(()
+ B
Σ
V VP mr (x*)
1=
Then, returning Pr Em= Ek-1 E
||xm,k - x||²]
we have
8 K-1
K
Dm (8)
E, S 41p00 o²
Σ
Bm,k + 412,1/
Bmnk
| - x(|2]
m=1
k=0
12
k=0
f=0
K-1
bm))(()
8Lm2
B DF(X, x²)
447
E
V F (x")
k=0
Applying Lemma 4 with Xx, Vi (x*) and VF(x*)
0 and the fact that
K-1
Bm = = SKISK - 1) - $2522,
m=1
K=
Σ
B2
(SK - 1)SK(SK - S
k,
K=
can simplify the preceding inequality:
E, 2 22 (,
After rearranging the preceding inequality, we get
8 +
(1 - 21=2 < o2 +25
Finally, using the condition that / S
1
which implies
22 /x4 we have
BLSK
E, 9 2 + 2 2 "
The claim follows after recovering the superscripts and taking unconditional expectations.
D.1.3 Tuning the learning rate
Here make clear version of Karimireddy et al. (2020)'s Lemma 1 (linear convergence rate) based on Stich (2019b); Stich and Karimireddy (2019)'s works.
Lemma (Karimireddy et al. (2020)). Two non-negative sequences (rihezo {sih1o, which satis- fies the relation
Tt+1 (1 ax)r: byst + to?
(37)
for all 0 and for parameters b 0, a, 2 0 and non-negative learning rates fre with
Tt 1. Vt 0, for a parameter d 2 d > 0.
27

---

Selection of weights for average. Then there exists constant learning rate = S and the weights wt == (1 07)-(1+1) and WT = Etoo wt. making it hold that:
b
T
T WT
Σ
wtwi
S 3aro(1 - ay) toy S 3aro expl-ay(T 1)] + ey.
(38)
1=0
Tuning the learning rate carefully. By tuning the learning rate in (38). (T+ 1) 2 1
we have
20y
( aro exp
(-a
of
(39)
aT
Proof. We start by rearranging (37) and multiplying both sides with wy:
w1(1 a7)re
WrF++1 + cym W4-1r' wei++1
bsgwe S
+ cyw
By summing from t l. T, obtain telescoping sum:
T
b
1
8,
(wo(1 - ay)ro - wTTT+1) + 4,,
WT
WWT
t=0
and hence
WTTT+1
To
T
w
w +
+ cy
(40)
WT
WT
WT
WTr
t=
Note that the proof of Stich (2019b)'s Lemma used WT 2 wy = (1 - ary) ary)- (T++1 to estimate Wr. It is reasonable given that wr is extremely larger than all the terms We 7) when T is large. Yet Karimireddy et al. (2020) goes further, showing that Wr can be estimated more precisely:
(1- (1-(1-a7))H)
(1 11-
W1 Σ Wi (1 - -(44)
(T+1)
(1- - any) -(F+1) Σ 11 azy"
ay
When (T'
1. (1 - a4) < + + 1)) se < 2/. follows that
2n7'
(1-(1-07)(t))
(1-)))((++1
Wy (1 (I++)
az
3ay
With the estimates
WT (1 (1-aa)-((t1))
-T (1 -7) < 47
(here we leverage ay S à 1),
and Wr (1-07)-(5+1) 30y
we can further simplify (40):
Vr < 3aro - (T+1) + o S 3aro exp (T + 1)] + cy
which is the first result of this lemma.
Now the lemma follows by carefully tuning 7 in (38). Consider the two cases:
If }
Infmax 22 Tc/o] then we choose In(max T//c)) and get that
af
o/'
δ (3ara expl (max ar. T/c)))) +0 (T)) Ô c
aT
2c in case 2> a'roT/citthoo holds aro <
af
28

---

If otherwise 2a( S v
In(max (2.0axx22"
(Note 21(T+1)
In(2) o²
In(max (2.a r/
aT'
al
then we pick 7 = and get that
3aro exp
d (-o1)
oT
+
3aro exp
aT' -
+
cln(max a3roT/c)) = -ō (aro exp
(-d)
oT'
aT
aT
Combining these two cases, we get
(-ot)
aT
V VT= Ö aro arreepp exp
(-d) + aT
Note that this lemma holds when (T+1) 2 20y; so restricts the value of T, while there is no such restriction Stich (2019b)'s Lemma 2.
D.1.4 Proof of strongly convex case of Theorem and Corollary
Proof of the strongly convex case of Theorem 1. Substituting (34) into (27) and using 1 1 GLSK we can simplify the recursion as,
x ( x
19
(1
uSKn 2
(x(() x 1| SKnE (r((((,x))
M - S
4SKKn + 12²
S(M c;
Let ij = MKn, we have
- x -
11-
E x - x11]]
_ Dr(x
2
Aii²0² 02
4772 S)
6LiP0² + 6LiP
+
(41)
SK
S(M - 1)
SK
S
Applying Lemma 7 with = r (T' = R), 7 = îj. Ft = =E [|x(1) - x"1 ||]
/. b 3.
s, = E (xx(),), x²)] We = (1 (r+1)
C1 (r+))
2
1g²
SK
+ 4M 5K2
S(M-1)
C2
6La²
SK
+
6
8
and
1 (7) MKn S a. follows that
R
E ()) - F(x*) )
Σ
W -F())
WR 0=
9
| x(0) x-12 exp (- unj
12ij0²
127( - S 18L7P0² SK +
18L
< 5
+
S(M -1 +
(42)
SK
S
(r) and we use Jensen's inequality (F is convex) the first inequality. Note that there are no terms containing 33 in Lemma 7. As the terms containing 33 is not the determinant factor for the convergence rate, Lemma 7 can also be applied to this case (Karimireddy et al., 2020; Koloskova et al., 2020). Thus, by tuning the learning rate carefully, we get
where x (8)
1 Σ w, (r)
Wa
E ) F(x') - = = (WD' exp
jRR
LO² WSR(M 1) DSSKR
(M- +
LC?
+
+
12L
μSKR
SPS (43)
= 1x x Eq. (42) and Eq. (43) are the upper bounds with partial client participa- tion. In particular, when = M, we can get the claim of the strongly convex case of Theorem and Corollary 1.
where D=
29

---

D.2
General convex case
D.2.1
Tuning the learning rate
Lemma 8 (Koloskova et al. (2020)). Two non-negative sequences (rabeo (8ete which satisfies the relation
T++1 Ti byss + c1 + ozni
for all I. 2 O and for parameters b > 0, C1 2 0 and non-negative learning rates (1e with Th S 2. 11 2 0, for a parameter d. > 0.
Selection of weights for average. Then there exists constant learning rate 7 = 7i S à and the
weights w2 and WT Et= Wt, making it hod that:
T St
b
To + 027
T
S
(44)
T
7T +
Tuning the learning rate carefully. By tuning the learning rate carefully in (44), we have
$ +
T S
20
To T+1
+
2
ro
dro
(45)
T+I
T+1
Proof. For constant learning rates %1 = 7 we can derive the estimate
T
T
(nt r41) + +17 + c2n S (T +1
rp
+ + + c27
7(T +)
which is the first result (44) of this lemma. Let
To -(++1
= City and 7(++1 = c2n yield-
ing two choices of 7,
c((TT and γ
To (1+1)
Then choosing y =
min c1(T+1)
< J. there are three cases:
c2(1+1)
d
If = 3. which implies that y = =/15 c((+1)
and y= 5
then
c2(T+1)
dro
dro
ro
VT T+I
Ci
02
d T
T T+
++1
7 [1(+1]
which implies that 7
then
c1(2+11
(2
Vr S 201
)
ci (T + (T(++1)) )))
To
+ c2
(T)
(T +1)
ro
S $20t
(++))
To
+ x
ro T +
+1
If
which implies that 7
then
(T())
c2(T+1]
2
T S ci
)
(T 1))
To + 2c
To
c
y
To
+
+2
To T+1
T+1
T+1
Combining these three cases, get the second result of this lemma.
30

---

D.2.2 Proof of general convex case of Theorem 1 and Corollary
Proof of the general convex case of Theorem I. Letting μ 0 in (41), we get the recursion of the general convex case,
x -
S E
x())
$1
" (F(xx))))
3
417002
477
S)
+ 6L
6L
+
SK
S(M 1)
SK
S
Applying Lemma 8 with t (T R), 7
91 rt
E
[|x(()) xx" 119 b
3
8, E. (xDr(x(())x')) Wy cI
40² 1(M-9)
8(M-1)
02
6La² + GL
and
(1) MKn = oZ it follows that
R
R(x(R)) - F((x))
1
Σ Wr (F (000)=F(55 (F(x())-F(x)) -F(x*) r=0
WR
3 (0) x=1
12ñj0²
12 M - S)
S(M 1) + 18LiPo²
18L
(46)
iRR
SK
SK
S
where (8)) = WR En= (r)((r) and we use Jensen's 's inequality (F is convex) in the first inequality. By tuning the learning rate carefully, we get
oD VSKR
S S.D
+ (Lo² 1/3
(ICD 1/3
LD²
((x(8))F((x') =
VI- M VSR (52) R2/3
R
(47)
where x (0) x Eq. (46) and Eq. (47) are the upper bounds with partial client participa- tion. In particular, when S = M, we can get the claim of the strongly convex case of Theorem and Corollary 1.
D.3 Non-convex case
Lemma 9. Let Assumptions 1, 3b hold. the learning rate satisfies 1) S 6LSK then it holds that
(() - F(x(1)) s
SKn
LSKnño
2
+
L
s
K-1
E
m,
(r)
-
101
(48)
2
m=1
k=0
Proof. According to Algorithm 1, the overall model updates of SFL after one complete training round (with clients selected for training) is
K
Ax = x
8 k
m=1
k=0
where (r)
8 V (x) m, is the stochastic gradient of F regarding the vector x Thus,
(r). m,k"
K
E [x
E V T.m (xm,))]
m=1
k=0
In the following, we focus on single training round, and hence we drop the superscripts for while, e.g., writing Xm,k to replace x (r) Specially, we would like use x to replace (1)) Without otherwise stated, the expectation is conditioned on x())
31

---

Starting from the smoothness of F (applying Eq. (16), (a y) - I| - with a = x Ax, y x), and substituting the overall updates, have
E [x + Ax) F(x)]
$ E (VF (VF(x) Ax)1 + E ||Ax|||
Lij²
((VF(x)) VT.... (xm,k))
E
Σ Σ
m t
(49)
k=0
For the first term on the right hand side in (49), using the fact that 2 ((a b) = ||lall [all2+1|00 ||b|| with a (x()) and
l|a - b11
VF (Xm,k), we have
s
K
9
B
(x)(,,
V (xmx)))
R=0
EE
[VF(x) 1 + V (Xm,))11 (xm,x)11-111= Fi (Xm,
[x())
Asm
<
|F(x))]
7
EΣ E
8 K-1
am |
(x
+
L'
9 K
E
[mmmi - x
x1(
2
2
2
mal
k==
mm
R=0
(50)
For the third term on the right hand side in (49), using Jensen's inequality, we have
L 2
K
Σ
2
m==1
k=
Σ K-1
K-1
27
K-1
<
T
gT..k
Fr.
(xmikt)
2
Σ
V Fm (Xm,k)
A=
8
K-1
< LSK + LSK
Σ
Σ K=0
IVF (xm
(51)
where we apply Lemma by seeing the data sample Em,k. the stochastic gradient &x. the gradient V. (Em,A) ) as &., x;, e; respectively in Lemma for the first term and Jensen's inequality for the second term in the preceding inequality.
Substituting (50) and (51) into (49), have
E[ + Ax) - F(x)] S - SKr
L
S
|VF(()II + LSK1
X -11²
x||]
2
A=
S K-1
"
- 2LSKg)
ΣΣ
VF Tm
(Xm, x)12
2
m=1
k=0
Since 7) S -1
6LSK the last term on the right hand side the preceding inequality negative. Then
SKn
L'
S
K-1
[ Ax) F(x)
LSK
Σ
Σ
[xm,k
x||
2
The claim follows after recovering the superscripts and taking unconditional expectation.
D.3.1 Bounding the client drift with Assumption 3a
Since Eq. (18), which holds only for convex functions, is used in the proof of Lemma 6 (i.e., Eq. (36)), we cannot use the result of Lemma Next, we use Assumption 3a to bound the client drift (defined in (33)).
32

---

Lemma 10. Let Assumptions 1, 2, 3a hold. If the learning rate satisfies 17 S drift is bounded:
1 6LSK
then the client
F S + +
3
TF ||
(52)
Proof. According to Algorithm 1, the model updates of SFL from x(r) to x x, is
(r)
(r) m - (r) = -1 m bm, (8)
(r)
K - is m-1 In the following, we focus on single training round, and k 1,
with k
i= m
hence we drop the superscripts r for while, e.g., writing X,, to replace (r) Specially, we would Xi.0- Without otherwise stated, the expectation is conditioned on x(r),
like to use to replace x (r)
We use Jensen's 's inequality to bound the term IE
|Xm,k xl|²
2
- ga...
Σ x00)
x|[]]
[mm,k
m (i)
m bm (t)
I 4n
(gm. F.r.J-FF... (xx,)))
+ 2
(VFr, (x FFF, (x))
j 1=0
m bmck (1)
b (1)
4n²² E
Σ
(Fr. - (x)
+4n7EE
Applying Lemma 1, Jensen's 's inequality and Jensen's 's inequality to the first, third and forth terms on the right hand side in the preceding inequality respectively, we can get
x]]]
Km,kk
bmf)(()
m
Dr (1)
4n²²
E
B
V.,, (xx,))l +4n²
Σ
E
V (xx,)) FxF, (x))
Ti + 4B2 m |
(53)
where Bm,k ΣI E/=
(1) (m K + k. The first term on the right hand side in (53)
bounded by 4Bm,,Kfo' o² with Assumption 2. The second term on the right hand side in (53) can be with Assumption 1. Then, we have
bounded by 1 Em En |
x|{]
Bm (+)
E ||xm,k - x|3 < 48 4 Bmik
E
|xxs
-x| + 21 + 4B2 R [VF())]2
1=
Then, returning to E, = Dg
-K- E
[|xm,k - x||2]
we have
5 K-1
8 K-1
m
bm (8)
E, < 0n
Σ
Bin + 4
Bmnk
E
||xis x1|²]
m=1 0=
m==1
1=
im
1=0
K-1
g K
+ 4n²
Σ Σ E
Σ
(VF (x) VF(x))
+ 4nj
Σ
m.kk
m=1 0=0
1=
m=1 k=0
33

---

Applying Lemma 4 with X = VF (x) and E = VF(x) to the third term and
Em= Ek=u Bm,k I k and Σ Σ B S 5 K3 3 to the other terms on the right hand side in the preceding inequality, we can simplify it:
E S 2
1 M
[VF(()) VF((O))
4 5 |VF()))
Asm, 30
E ,
23 |FF())
5 |F(x)]1
3
After rearranging the preceding inequality, we get
(1 - 2
25" 22
+ 5 | |V
3
Finally, using the condition that 17 S 6LSK which implies 1 - 222 2 9. have
9 The claim follows after recovering the superscripts and taking unconditional expectations.
E, 1 9
2 8 +
[[V()))
2 - R |F(x)]
D.3.2 Proof of non-convex case of Theorem 1 and Corollary
Proof of non-convex case of Theorem 1. Substituting (52) into (48) and
using
"
6LSK min { L, vS J. we can simplify the recursion follows:
3
((x((+))) - F(x(()) $ - SKnB
[V=] + LSKI)
+ 9 + 2
9
3
Letting πj == SKT, subtracting 1 from both sides and then rearranging the terms, we have
((x(+)))) F+ S EE F(x(r))
Fm| -
-3 NH
11]
Lii
SK + 9
9
8SK
85
Then applying Lemma 8 with t (I' RR), 7 17, Tt IE (x (r)
F* b
3. 8t
E [[
we C
Lo² 0 SK
C2
8SK
2 and
1 min
1,
/B
3
(f
SKn S oz min 1, /s ). we have
( [|]]
3 (F(x)) - F*)
3Lij
27L2
2
min E OSTER
(54)
nj
SK
8SK
8S
where we use minogrga ||VF(({>))) ||] $ R+1
Σ E
Then, using s
6L(3+]] S min {1,
ys and tuning the learning rate carefully, we get B
-10-0 (Lo 1/2
(L'O2A3)1/3 VSKR (SK)1/3R2/3 p2/3
(L 1/3
min E [ (r)
L3A R
(55)
OSTER
where = F(x")-F* Fr. Eq. (54) and Eq. (55) are the upper bounds with partial client participation.
In particular, when S = M, we get the claim of the non-convex case of Theorem 1 and Corollary 1.
34

---

E Proofs of Theorem
Here slightly improve the convergence guarantee for the strongly convex case by combining the works of Karimireddy et al. (2020); Koloskova et al. (2020). Moreover, we reproduce the guarantees for the general convex and non-convex cases based on Karimireddy et al. (2020) for completeness. The results are given in Theorem 2. We provide the proof of Theorem 2 for the strongly convex, general convex and non-convex cases in Sections E. E.2 and E.3, respectively.
In the following proof, we consider the partial client participation setting, specifically, selecting partial clients without replacement. So we assume that π {TT1 m2...., TM ) is permutation of (1,2..... } in a certain training round and only the first S selected clients {T,, Æ.,..., T will participate in this round. Without otherwise stated, use E[.] represent the expectation with respect to both types of randomness (i.e., sampling data samples & and sampling clients T).
Theorem 2. For PFL (Algorithm 2), there exist a constant effective learning rate ń Kn and weights Wv, such that the weighted average of the global parameters x == Wn Σ 12 w(((r)
(Wn Er Wr) satisfies the following upper bounds:
Strongly convex: Under Assumptions 1, 2, 3b, there exist constant effective learning rate p S
i S 1 GT and weights wr = -1 ) such that holds that
9 E ((x(())) F(xx)] juD' exp (- Jii (-1ij 12
18Lif
+ 12
(56)
MK
K
General convex: Under Assumptions 1, 2, 3b, there exist a constant effective learning rate ñ S and weights Wy = 1, such that it holds that
1
3D2 nR
12
18L
E F(x (R) F(x*) S
+
+
+ +
(57)
MK
K
Non-convex: Under Assumptions 1, 2, 3a, there exist a constant effective learning rate ň S 6L(3+1) and weights wi 1, such that it holds that
min E [IVF(( usrsh
3A1 7
3
27T.212002
9 127
(58)
SK
8K
where D D== -=1|=<10= x²1| for the convex cases and A = F(x(0)) F for the non-convex case.
Corollary 2. Applying the results of Theorem 2. By choosing appropriate learning rate (see the proof of Theorem 2 in Appendix E),
obtain the convergence rates for PFL as follows:
Strongly convex: Under Assumptions 1, 3b, there exist constant effective learning rate pR S
îj S GT.
and weights Wr = (1- 1i) (r+1), such that it holds that
E F(x -F0)))F(())))
F(x*) = HMKR
σ² LO²
LC? + +DD exp
HR
(59)
12KR
12
12L
General convex: Under Assumptions 1, 2, 3b, there exist a constant effective learning rate î S and weights w. such that it holds that
GL
E ((x(R)) -(00))F((()) F(x*)( -F())) =o
oD VMKR K3/3 +
(LORDA)
(LC2D1)
1/3
LD²
(60)
R2/3
R
Non-convex: Under Assumptions 1, 2, 3a, there exist a constant effective learning rate r S 6L(3+1) and weights W. = 1. such that it holds that
min E [IVF((())) = ( (LLO² 1/2 OSTER
(2)02A2)2/3
(1252A3)1/3
L3A
(61)
VMKR
K1/3
R2/3
R
where omits absolute constants, ① omits absolute constants and polylogarithniic factors, D [])(0)) xx [e=] for the convex cases and A == F(x())) F for the non-convex case.
35

---

E.1 Strongly convex case
E.1.1 Find the per-round recursion
Let Assumptions I, 2, 3b hold and assume that all the local objectives are p-strongly convex. If the learning rate satisfies n, I 6LK, then it holds that
Lemma 11.
E xx(tt) - x x0(² $ (1 (1- _ E ||x(0) - x19
OKn2o²
M - S
+
+4K311
S(M 1) c
5
KnB [Dr(el0),
8
1
E
- x((1) 1//
(62)
m,k
k=0
Proof. According to Algorithm 2, the overall model updates of PFL after one complete training round (with clients selected for training) is
8
Ax = x (r+1) xx(1)
7
8 kk
m=
k=
(r) where S k fs (r)
(e {) is the stochastic gradient of Fxm regarding the vector (r) x,,k*
Thus,
s K Σ
E [ = 11
E V 5m (Xm,))]
5 m==1 k=0
In the following, focus single training round, and hence drop the superscripts for while, e.g., writing Xm.s to replace x Specially, we would like to use x to replace otherwise stated, the expectation is conditioned on (*))
(1)) x
Without
We start by substituting the overall updates:
E x + Ax x*]
|x x $12
2B [(x - x" Ax)] +E ||Ax|
[|| x
1
2m
S
S K
E
BRVP Tm (Xm,)),x-x')
n1²
52
E
ΣΣ
K
g
m
&
(63)
m=
K=0
m=
k=U
We can apply Lemma 2 with æ Xm.ks y x", and h = Fr... for the second term on the right hand side (63):
K-1
2n
E
BRVF Rm (xm,)),-x'))
S
m=1 0=
K-1
<
2n
Σ Σ
E
Fr (x) Fa.m (x") + 11
|x- x" x11 112=
||xmm, - x x[|²]
5
A=
K
< -22KnDr(xx*'
- ||x
1
JuKnn
212 +
2L
E
|| Xmm - x1|]]
(64)
S
m=1
k=0
36

---

For the third term on the right hand side in (63), using Jensen's 's inequality, we have
g K-1
E
mum
k
mmml
k=0
8 K
27
K
27
s 4E
(gmm. k
V 5m (Xm,k))
+ 4E
V F (xm,k) - V V. Fm (x))
m=
k=0
m=
k=
K
27
8 K 1
27
+ +E
Σ
(V
(x)
V (x'))
+ 4E
V Fr (x*))
(65)
m=1
0=
m==
k=0
For the first term on the right hand side in (65), we have
5 K
5
K
4E
gg - V Fanm (xmm,))
gg k
(Xm,
m==1 k= 0
m=1
k=0
K
Lem.
E
g
V
Tem (xl
m=1
k=
Asm. 2 S
4SKo²
(66)
where we use the fact that clients are independent to each other in the first equality and apply Lemma 1 by seeing the data sample Sm,k, the stochastic gradient k..... the gradient V F= (Em,k)
as Çi, X;, e; in the second equality. For the second term on the right hand side (65), we have
K Σ m
S K-1
4IE
Tm (Xm,k)= - VF Tm (50))
(1)) S
4SK
Σ
Σ
I
F Tm
(Xmxk)) - V F (x)
m==
k=
K-1
SI2SK
Σ
E [|xmkk -x12
m=
k=
For the third term on the right hand side in (65), we have
S K
K
4E
(V Fm (x) - V Fm (x*))
4SK
E
V
Tm (x)
V V (x )1(²
k=0
K=U
K-1
(18)
8LSK Σ
Σ
E
E
Dr
Frmm (x,x")
K=
8T. x2 =2
where the last inequality is because E [Dr... (x, xx,' -D(xxx*). The forth term on the right hand side in (65) can be bounded by Lemma 3 as follows:
Σ K
VF Tm (x7)
(n
45 M S
4
S(M 1) 2
With the preceding four inequalities, we can bound the third term on the right hand side in (63):
?
s K-1
|]
4KTP0²
K-1
S2
ΣΣ gxm.k
*
S
4L2K1²2
Σ
Σ E
Xm,k
x1|
m=1
M
S
SLK2 DF(xxx)
2
6
(67)
S(M
1)
37

---

Then substituting (64) and (67) into (63), we have
E x + Ax x*11] xxxxx11]] $ (1-150 "
|x x
4K
8(M -1 c
M -
S
9 K-1
4LL + +L + 22k2)
1
Σ
Σ
| x[{]
m=1 km0
$ (1 uKu)
- xx11 +
4KiP0²
+
+4
M -
S
S(M - 1)
K
2 KnDp(x,x* + Lm
8 Lm
E
||xm, x1|²
3
m=1
K=
where we use the condition that 1) S 6LK in the last inequality. The claim of this lemma follows after recovering the superscripts and taking unconditional expectation.
E.1.2 Bounding the client drift with Assumption 3b
The "client drift" (Karimireddy et al., 2020) in PFL is defined as follows:
s
K-1
x x
& =
E
x
(68)
m=1 k=
Lemma 12. Let Assumptions I, 2, 3b hold and assume that all the local objectives are p-strongly convex. If the learning rate satisfies v) S 6LK' then the client drift is bounded:
3 k "L Dr(x
E, - k K2n000 + 2
(69)
Proof. According to Algorithm 2, the model updates of PFL from (()) to x is
(r)
m.k
In the following, we focus on single training round, and hence we drop the superscripts for while, e.g. writing X to replace x x Specially, we would like to use x to replace x(r). Without otherwise stated, the expectation is conditioned on x(").
EE= gmm.J 17]
We use Jensen's inequality to bound the term
[
x||] = =
E ||xm,k - x|(]] < =
(gami - V Frrm (Xm-))
+ 2
V Fr... (Xm.j)
Fx Km
(x))
27
k-1
+ 2
Frmm (x) From (x
(x*))
+ 2
Σ
V mm
(x*)
Applying Lemma 1 to the first term and Jensen's inequality to the last three terms on the right hand side in the preceding inequality, respectively, we get
R-1
k-1
[xm,k - x|[p]
|gmm..
V Fr.m (Xm + 4k
Σ
F
Frrm (Xma) - VF (x)]12)
j=0
j=0
+ 2
|VF Am
(x) - V (xx) )|
+ 2
V am (x*)
38

---

The first term can be bounded by 4 with Assumption 2. The second term can be bounded by 4L2 Eド= E ||xm.. - x||] with Assumption 1. The third term can be bounded by 1 [Dr... (x, x*]] with Eq. (18). Thus, we have
[|m.kk - xx|]] S 4knpo2 + kmp 2
X -xm---11 x|] + 1L [Dr... (x,x*)] + 1 || | |V (x (x')1²)
4knpo² 0² km² 2
Σ E [|xmm -x1² + +8.h2 1p (xxxxx) + 12317
Then returning to & = 1/2 5
m==
Σ
k=
K-1
E
||xmm,k
- -x|3] we have
K-1
8 K
R-1
K-1
K-1
Σ
k 4
E |xxms x|²] + +L1d 2
Σ
Dx 4n7
Σ k=
k2
k=0
j=0
k=0
Using the facts that E k = simplify the preceding inequality:
(K-1)K
I
k² and
HK-1 x2 = (K-1)K(2K-I)
S
ka 3 we can
8 h-1
& S 22KKno000 + 2
1
Σ
Xmm x||
+
8
D xx) + k
5
3
m== 1=
After rearranging the preceding inequality, we get
(1 11-27% 2I, 1)),, S 222 + k k2 LLK', 12 D2 (x,
3
Finally, using the condition that 17 S 6LK which implies 1 - 2T,2 172 2 - we have
E, 9 4 R² 0² + 3 k3 + "f
The claim follows after recovering the superscripts and taking unconditional expectations.
E.1.3 Proof of strongly convex case of Theorem 2
Proof of strongly convex case of Theorem 2. Substituting (69) into (62) and using 1) S 6LK we can simplify the recursion as,
E
(x+t)) x 11]] < (1-
E
(r) x" |7]
1
KnB
[D
3
4K12002
M- S
+ 1k2
2 2 0² + 7
s
S(M - 1)
Let ij Kr, we have
|xx|rt -
x(1
< 1 <(1-
x+(+) x" 1|]
NR Dr (r(x(1)xx))
E
E
2
3
4ij 02
(M 2
S)C2
6LiPO22
+ ALTPS??
(70)
SK
S(M - 1)
K
Applying Lemma 7 with = r (T R), γ = 1 rt E
(xx(0) x" ==]
a b 3
2'
8, EE. (xx((()), ). w, = (1 - ش (r+11, C1 = 102
SK
+ S(M
4M-
02
6L0²
K
+ AL.( and
1 (i Kn ). it follows that
R W -(x(())-F((x))) F(X*))
E F(2( (R)) - -F(x') < WR
-
9 M (0) - xx* 2
|
exp (- (-
+ 12ñ0²
+ 12 - -
18L
+12Li (7))
SK
S(M 1)
K
39

---

where x (R) 1
WR Σド= ),x(()) and we use Jensen's 's inequality (F is convex) in the first inequality.
Thus, by tuning the learning rate carefully, we get
- = δ JuD2 exp
P.R. 12L
(M- PSR(M- - +
Loz P²KR
L
PSKR
p² Rt
(72)
where = |x(0)= x" Eq. (71) and Eq. (72) are the upper bounds with partial client participa- tion. When M is large enough, have (M-S) ~ (1 } This is the constant appearing in S(M-1]
Karimireddy et al. (2020); Woodworth et al. (2020b). In particular, when M, we can get the claim of the strongly convex case of Theorem 2 and Corollary 2.
L
E.2
General convex case
E.2.1 Proof of general convex of Theorem 2 and Corollary 2
Proof of general convex case of Theorem 2. Let μ4 in (70), we get the simplified per-round cursion of general convex case,
10 x
x1]
x*
SE
x
x"
2
E [Dr(x(),x))
xx)]
4772
SK + 4 S)
6L
+ +4L
S(M - 1)
K
Applying Lemma 8 with t r (T R), q 0). rt E -[1x((1)xx111
-x11']_
3 8t
[D)( x*)]. ue 1,01
4a² SK
1 8)C2
8(M - 1) C2
6L
K
+ +4LC2 and 1/ = 1
o9 (n Kn S o..)
it follows that
R
E F(x(11)) - F(x*)
1
Σ
Wy (F(x(1)) - F(x*)) -
S
WR
r=0
(x) - -x"1 1
12njo²
12 - 5)5
18L7
+ 12
(73)
SK
S(M - 1)
K
where x (R)
WR Ex= W, (r) and we use Jensen's inequality (F convex) the first inequality. By tuning the learning rate carefully, we get
( {DD aD
S C.D. (Lo*Dy) M
(LCDD)
1/3
LD
- F(x))=F())- =
VSKR + +V+
+
VSR K3/3
R2/3
(74)
x" ||. Eq. (73) and Eq. (74) are the upper bounds with partial client participa- tion. In particular, when S = M, we can get the claim of the strongly convex case of Theorem and Corollary 2.
where D
(0) xx
E.3 Non-convex case
Lemma 13. Let Assumptions 1, 2, 3h hold. If the learning rate satisfies 17 S then it holds that
6LK.
Kn
TKK1202
E
[[F(((++1))) - F(x(1))
s
E
+
2
s
T2211
K -1
x x 111
+
E
(75)
28
m=1
0=0
Proof. According to Algorithm 2, the overall model updates of PFL. after one complete training round (with S clients selected for training) is
8
Ax = x (r+1)
(r)
7
SS
8
k
m=1
km
40

---

where (r) mx Vsx (xpkk:)) is the stochastic gradient of Fx... regarding the vector (r) m. Thus,
11 R [[AX|= = 5 k=0
Σ
V mm (Xm,k)
In the following, we focus on single training round, and hence we drop the superseripts for while, c.g., writing X to replace x Specially, we would like use x replace xi.0 Without otherwise stated, the expectation is conditioned on x(")
(r)
Starting from the smoothness of F' (applying Eq. (16), Dr y) S 2 || yll with x = x Ax,
y x), and substituting the overall updates, have
E [F Ax) F(x)]
<V(VF( ]x)] + [ ||AX|]]
$ K-1 E ((VF(x), VF (Xmm
Lup²
S K-1
25
Σ
gmm k
(76)
k=0
For the first term on the right hand side in (76), using the fact that 2 (a. b) with
||a||++|B1|]
1|b11
1la b1]
(x(x) and b Fz.m (Xm,k), we have
K
17
E
ERVF(X
(x),
V (xm,)))
5
m=
8
K-1
Σ
E |F(())] + IIV (xm,,))11
// (Xm,k) V Fx))))
25
k=0
Asm
S
[F(())]
7
K-1
I
F
(xm,))
+
L
L2
5 K
E
||x - x(1]
2
25
25
m=1
K=
m==1
k=
(77)
For the third term on the right hand side in (76), using Jensen's inequality, we have
Lafs
E
8
2
m==1
K-1
K-1
S K-1
<
E
Σ
8 Brink
F nm
(xm,
+
L
Σ
V
F Tm
(xm,k)
$2
m==1
k=0
m= k=
m=
k=
o2 S
LK
K-1
Σ
E
|VF mm (xm,))l²]
(78)
S
k=0
where we use independence and Lemma 1 for the first term (see Eq. (66)) and Jensen's 's inequality for the second term in the preceding inequality.
Substituting (77) and (78) into (76), we have
Kn 2
LK
L'
K
E [[ Ax) F(x)]
|F(())]
E ||mm - x1
28
m=1
k=
$ K-1
11
2LK1)
Σ
E
(xm, 113
2S
k=0
Since 17 S GLK the last term on the right hand side in the preceding inequality is negative. Then
E [F F(x)] <
Kn
|VF(x)]]
La
S
K-1
||mm - x|[²]
2
2S
K=D
The claim follows after recovering the superscripts and taking unconditional expectation.
41

---

E.3.1 Bounding the client drift with Assumption 3a
Lemma 14. Let Assumptions I, 2, 3b hold. If the learning rate satisfies 1 drift is bounded:
_
then the client
6LK
E, S 1
K22ppo2 2 n + 2 K
+ 1) [E((<)>)))
(79)
Proof. According to Algorithm 2, the model updates of PFI. from x(r) to x is
(r) x
(r)
m,,k
mmm
In the following, we focus on a single training round, and hence we drop the superscripts r for while, e.g., writing Xm,k to replace x x Specially, we would like to use x to replace x Without otherwise stated, the expectation is conditioned on x(*).
19]
We use Jensen's 's inequality to bound the term E
||Xm, x1|²]
=
kー1 Σド= mm
27
27
||Xm,,k - x1|]]
2
Σ Bani
V (xm3))
+ E
V F (Xm.))
V
(x))
27
V Fr (x)- VF(x))
4 E
F
Applying Lemma 1 to the first term and Jensen's inequality to the last three terms on the right hand side in the preceding incquality, respectively, we get
1
E Xm,. - x11 <
4n²
E
VF mm (xm
4km2
E
V mm (Xm.j) - F nm (x)1l?
0=0
F (x) VF(x)]1
172
|VF
The first term can be bounded by 4kz)²a² with Assumption 2. The second term can be bounded
by 4L kL2 Σラ= E ||xm..j - x|?] with Assumption 1. The third term can be bounded by
1)² 32 [F(() +2² with Assumption 3a. Thus, we have
[|m,, - x|[²] s 4knpo² 41. km
-x|]]]
[| Xmm.i x²] + (122 + 422,222
1=0
Then returning & = 1 DS
- E [|xmm, x(|
have
5
K-1
K-1
K-1
4m
E, =
Σ
k k+
E
[| xx1
Σ
k2
+ 25
Σ k=
k2
k=
m=1 k=
/=0
k=
Using the facts that Ek= simplify the preceding inequality:
(K-1)K 2
< and K- 122 (K-1)K(2-1)
<
k 3 we can
6
K-1
E, +
2T.
Σ
E
||
X -
k
K3 10 +1) +1) + + AK3
m=1
1= 1=
42

---

After rearranging the preceding inequality, we get
(1 1 22 1p2 + n + (8 + 1) /F
Finally, using the condition that 17 S
6LK 1
which implies - 12 2 //. we have
+ 3 9 R2p00 3 n &
1 + 1) ()
4
2
2
The claim follows after recovering the superscripts and taking unconditional expectations.
E.3.2 Proof of non-convex case of Theorem 2
Proof of non-comvex case of Theorem 2. Substituting (52) into (48) and using 7 S GLK(B+1)* we can simplify the recursion as follows:
((x((+))) - F(x(+)) - 1--3-k KT
| |7]
LK 9
L + 3 L
Letting îj == Kr, subtracting F from both sides and then rearranging the terms, we have
[(x(tt)) F+ < IE ((x(r)) F-] - 3
E ( 1
Lif
9
3 L2 12
+ 8K
SK
Then applying Lemma 8 with I (T = R).
17, Tt = E [F((x()) - FF], b 3. 81
()) wt 1, ct
La²
91"0²
12222 and EL(+TI (i) K1 S
3K. C2
88
6L(3+1)) ), we have
min E OSTER
||
11]
-
3 (F(xx) F
3Li
27L3
+ 1'PPP2
(80)
nR
SK
8K
where we use minogreR E learning rate carefully, we get
<
1
ΣR
|
Then, tuning the
min E [| -0 (1.02A) OSTER
1/2
(1202
(T2
1/3
LBA
VSKR +
K3/3
R2/3
+
R
(81)
where A= = F(x")= - F*. Eq. (80) and Eq. (81) are the upper bounds with partial client participation.
In particular, when M, we get the claim of the non-convex case Theorem 2 and Corollary 2.
43

---

Simulations on quadratic functions
Nine groups of simulated experiments with various degrees of heterogeneity are provided in Table as a extension of the experiment in Subsection 4.1. Figure 7 plots the results of PFL and SFL with various combinations of 5 and Ç.-
Table 6: Settings simulated experiments. Each setting has two local objectives (i.c.. M = 2) and shares the same global objective. Choosing large value of S. and å means higher heterogeneity. The definitions of Ç. and 5 can be found Subsection 4.1.
Settings
=
Ç. = 10
S. 100
[Fi(t) 10² + x
[F)x) _ 10x
(1i(z) ς2 + 100x
8
(F((x) 302²
(F(xx) } 10x
(F2(z) 20² 100z
(F) 2022 +
[F(()) 2 10x
(Fi(2) 302 + 100x
=
(2(x)) = 3d²
(2(x)) 30² 10x
(F((x) x²² 100g
(x) x
(F(()) x² + 10x
[Fi(z) x² + 100x
8 =
(2(x) = -
F2(x) = - 110x
F2(x) = -100x
Distance to the optimum
Distance the optimum
20
the
20
PFL K=2
SRL K-2
100
330
200
402
500
300
230
300
402
500
120
200
300
400
500
Training munds
Training rounds
Training rounds
(a) 0, C. =1
(b) 5 = O. C= 10
(c) 0, 100
301
100
231
Disganee to the optmmum
Distannce to the optmmum
Distaince to the optmuum
32
PPL K=
SFL. K=10
210
500
160
320
zie *és
cio
Training rounds
Training rounds
Training rounds
(d) -
(e) 6 3. -
(0 8 5/5 C. 100
Detance the optimum
Dictance to the aptrmum
100
31*
10-
te-r
PFL
SE K-2
K-10
256 Training rounds
300
189
160
280 Training
Training rounds
6 L.
(h) C.
06=
100
Figure 7: Simulations quadratic functions. The best learning rates are chosen from [0.003, 0.006.
0.01, 0.03, 0.06, 0.1, 0.3, 0.6] with grid search. We run each experiments for random seeds. Shaded areas show the min-max values.
44

---

G More experimental details
This section serves supplement and enhancement Section 4. Our code is partly from Gao et al. (2021); Zeng et al. (2021); Jhunjhunwala et al. (2023) (more references are included in the code), and it is available at https: //gp://ggtttt/tt/// com wttp/////yylllgoo//////e/raaaaaa
G.1 Extended Dirichlet partition
(a) 10 clients, ExDir(1, 100.0)
(b) 10 clients, ExDir(1, 10.0)
( 10 clients, ExDir(1, 1.0)
000
1010
(d) 10 clients, ExDir(2, 100.0)
(c) 10 clients, ExDir(2, 10.0)
(f) 10 clients, ExDir(2, 1.0)
gg)
10 clients, ExDir(5, 100.0)
(h) 10 clients, ExDir(5, 10.0)
ii) 10 clients, ExDir(5, 1.0)
1990
10
(j) 10 clients, ExDir(10, 100.0)
(k) 10 clients, ExDir 10.0)
(1) 10 clients, ExDir 1.0)
Figure 8: Visualization of partitioning results on MNIST by Extended Dirichlet strategy. The z-axis indicates client IDs and the y-axis indicates labels. The value in each cell is the number of data samples of label belonging to that client. For the first row, there are only one possible results in the case where each client owns one label with 10 clients and 10 labels in total, so these three partitions are the same. For the second, third and forth rows, data heterogeneity increases from left right.
Baseline. There are two common partition strategies to simulate the heterogeneous settings in the FL literature. According to Li et al. (2022), they can be summarized follows:
a) Quantity-based class imbalance: Under this strategy, each client is allocated data samples from a fixed number of classes. The initial implementation comes from McMahan et al. (2017), and has extended by Li et al. (2022) recently. Specifically, Li et al. first randomly assign different classes to each client. Then, the samples of each class are divided randomly and equally into the clients which owns the class.
b) Distribution-basee based class imbalance: Under this strategy, each client is allocated a proportion of the data samples of each class according to Dirichlet distribution. The initial implementation, to the best of our knowledge, comes from Yurochkin et al. (2019). For each class c, Yurochkin et al. draw Pa Dir(ag) and allocate a Pa.. proportion of the data samples of class k to client m. Here is the prior distribution, which is set to 1.
45

---

Extended Dirichlet strategy. This is to generate arbitrarily heterogeneous data across clients by add a step of allocating classes (labels)
combining the two strategies above. The difference to determine the number of classes per client (denoted by C) before allocating samples via Dirich- let distribution (with concentrate parameter a). Thus, the extended strategy can be denoted by ExDir(C, a). The implementation is as follows (one partitioning example is shown in Figure 8):
ge 1,1,0,0,0
Allocating classes: We randomly allocate C' different classes to each client. After assigning the classes, we can obtain the prior distribution qe for each class c (see Figure 9).
Allocating samples: For each class we draw Pa Dir(age) and then allocate a Pa.m proportion of the samples of class e to client m. For example, q. [1, 1,0,0, 0, ...]] means that the samples of class are only allocated to the first clients.
Client ID
This strategy have two levels. the first level to allocate classes and the second level to allocate samples. We note that Reddi et al. (2021) use a two-level par- tition strategy to partition the CIFAR-100 dataset. They draw a multinomial distribution from the Dirichlet prior at the root (Dir(a)) and a multinomial distribution from the Dirichlet prior each coarse label (Dir(B)).
Class ID
Figure 9: Allocating classes (4 classes in total) to clients.
G.2 Gradient clipping.
Two partitions, the extreme setting C= = 1 (i.e., ExDir(1, 10.0)) and the moderate settings (i.e.. ExDir(2, 10.0)) are used in the main body. For both settings, use the gradient clipping to improve the stability of the algorithms as done in previous works Acar et al. (2021); Jhunjhunwala note that the gradient clipping is critical for PFL and SFL to prevent diver-
et al. (2023). Further, gence in the learning process on heterogeneous data, especially in the extreme setting. Empirically, find that the fitting "max norm" of SFL is larger than PFL. Thus trained VGG-9 CIFAR-10 10 with PFL and SFL for various values of the max norm of gradient clipping to select the fitting value, and had some empirical observations for gradient clipping in FL. The experimental results are given in Table 7, Table and Figure 10. The empirical observations are summarized as follows:
1) The fitting max norm of SFL is larger than PFL. When the max norm is set be 20 for both algorithms, gradient clipping helps improve the performance of PFL, while it may even hurt that of SFL (e.g., see the 12-th row in Table 8).
2) The fitting max norm for the case with high data heterogeneity is larger than that with low data heterogeneity. This is suitable for both algorithms. (e.g., see the 12, 24-th rows in Table 8)
3) The fitting max norm for the case with more local update steps is larger than that with less local update steps. This is suitable for both algorithms. (e.g., see the 4, 8, 12-th rows in Table 8)
4) Gradient clipping with smaller values of the max norm exhibits a preference for a larger learn- ing rate. This means that using gradient clipping makes the best learning rate larger. This phenomenon is more obvious when choosing smaller values of the max norm (see Table 7).
5) The fitting max norm is additionally affected by the model architecture, model size, and so on.
Finally, taking into account the experimental results and convenience, we set the max norm of gra- dient clipping to 10 for PFL and 50 for SFL for all settings in this paper.
46

---

Table 7: Test accuracies when using gradient clipping with various values of the max norm for VGG-9 CIFAR-10. Other settings without being stated explicitly identical to that in the main body. The results are computed over the last 40 training rounds (with 1000 training rounds in total). The highest test accuracy among different learning rates marked in cyan for both algorithms.
Setting
PFL10
2.0
10-1.5
10
10-1.0
10 10-
SSL
10 10-2.0
10- 1.5
10-1.0
VGG-9, C = 1, K = 5, w/o clip
bc
25,43
30.95
30.63
10,00
8c
43.93
53.79
57.69
10.00
VGG-9, C I, K 5, w/ clip
20
21.92
31.04
32.41
24.99
100
43.93
53.79
57.69
10.00
VGG-9, = 1, K = 5, w/ clip
10
12.51
25.67
34.89
28.77
50
43.79
53.73
58.63
10.00
VGG-9, C² C²= I, K = 5, w/ clip
5
10.54
16.72
27.01
35.11
20
43.12
53.17
57.96
10.00
VGG-9, (²= == 1, K = 20, w/o clip
bo
24.23
27.53
26.91
10,00
35.63
10.00
10.00
10.00
VGG-9, C² I, K 20, w/ clip
20
19.44
27.60
26.41
15.00
100
35.63
10.00
10.00
10.00
VGG-9, C² 1, K = 20, w/ clip
10
11.51
22.81
28.79
21.10
50
34.55
27.11
10.00
10.00
VGG-9, C²= I, K = 20, w/ clip
5
10.39
14.56
22.48
27.26
20
30.49
10.00
10.00
10.00
VGG-9, C" 1, K = 50, w/o clip
bo
22.44
23.70
20.97
10.00
25.11
10.00
10.00
10.00
VGG-9, C² [== I, K 50, w/ clip
20
17.82
23.80
20.72
10.00
100
25.11
10.00
10.00
10.00
VGG-9, C= 1, K = 50, w/ clip
10
10.14
20.58
21.95
10.00
50
23.41
10.00
10.00
10.00
VGG-9, C= I, K = 50, w/ clip
5
10.31
10.44
18.25
18.02
20
18.27
10.00
10.00
10.00
VGG-9, -== 2, K = 5, w/o clip
41.36
51.34
55.22
10.00
58.33
69.14
71.55
10.00
VGG-9, C- = 2, K 5, w/ clip
20
41.46
51.30
56.54
47.47
100
58.33
69.14
71.58
10.00
VGG-9, C 2, K 5, clip
10
38.50
50.99
57.09
53.46
50
58.35
68.75
71.24
10.00
VGG-9, = 2, K = 5, w/ clip
5
26.07
46.49
58.26
56.71
20
57.81
69.17
70.94
10.00
VGG-9, C = 2, K = 20, w/o clip
xo
55.64
64.04
10.00
10.00
DO
60.56
67.70
64.94
10.00
VGG-9, C = 2, K = 20, w/ clip
20
55.70
64.14
66.57
10.00
100
59.48
68.11
64.94
10.00
VGG-9, C 2, K 20, w/ clip
10
54.70
63.97
68.07
61.92
50
60.82
67.93
66.50
10.00
VGG-9, C = 2, K = 20, w/ clip
5
47.32
61.61
67.11
63.56
20
58.36
67.65
67.74
10.00
VGG-9, C = 2, K = 50, w/o clip
xc
63.93
67.85
10.00
10.00
61.93
68.05
61.77
10.00
VGG-9, C² = 2, K 50, w/ clip
20
63.94
68.26
67.15
59.46
100
62.36
67.01
62.84
10.00
VGG-9, C 2, K 50, w/ clip
10
62.72
67.57
69.11
64.21
50
62.27
67.52
62.59
10.00
VGG-9, = 2, K = 50, w/ clip
5
58.52
65.34
66.77
64.75
20
59.80
68.72
64.26
38.22
PFL C=1, K-5
PFL, C-1,K-1K K-50
SFL, C-1, K-5
SFL, C-1,, K-50
Bet 3011 Arcureyy 1S1.
Bul BO0 A Accuurecyy 184
Accuracy
ML. P-0. dp
RR. 1-0 cb
STL (-63, woeds
1-1.013 Kt de
ai 20
SEL 6.5.2 100
1-01
(eeL wropest
28 AR Did de 28 a8 Ai8 Rit
300 1h0 Do Am AR AN0 260 100
380 MB0 wid 208 200
PFL C=2, K=5
PFL. C=2, K=50
SFL C=2, K=5
SFL, K=50
K=50
1ost10 Acound (96)
180 -
Twit Topt Accurery
ML Ivd 3,
HR, (wd333 clp
stocle
100, 20
SR, (ee AD
p-0
do
(m6023 clo
SFL 100
1-0
36 J00 Dee We 1960
1000 2006
50
180
190 2i0
2000 200 201
560 180 200 2008
2000 J000 30m
500 180 1008 1900 2000 20m 30m
Figure 10: The corresponding training curves of Table 8 (VGG-9 on CIFAR-10).
47

---

Table The best learning rate (selected Table 7) and its corresponding test accuracies in the short (1000 training rounds) and in the long (4000 training rounds). The results computed over the last 40 training rounds in the short run (the 5-th, 9-th columns) and 100 training rounds in the long (the 6-th, 10-th columns). That the algorithms diverge when without gradient clipping makes the result with The results that deviate from the vanilla case (w/o gradient clipping) considerably
(more than 2%) marked in magenta and teal.
Sctting
PFL Lr
Acc.
Acc.
[SFL
I.r
Acc.
Acc.
(CIFAR- 10, C= =1
VGG-9, K w/o clip
00
10-1.5 30.95
60.75
80 10-15 57.69
78.56
2 VGG-9, K 5. w/ clip
20
10 1.0
32.41
67.97 (+7.2)
100 10 1.5 57.69
78.75
3 VGG-9, K w/ clip
10
10-10 34.89 (43.9)
69.10 (+8.4)
50 10-15 58.63
78.56
4
VGG-9, K 5. w/ clip
5
10-0.5 35.11 (+4.2)
71.07 (+10.3)
20
10-1.5 57.96
79.06
5
VGG-9, 20, w/o clip
0c
1.5 27.53
56.89
2.5 35.63
72.90
6
VGG-9, K 20. w/ clip
20
10-1.5
27.60
57.01
100 10-25 35.63
73.06
VGG-9, K
clip
10
28.79
64.11 (+7.2)
50
2.5 34.55
73.16
8 VGG-9, K = 20, w/ clip
10-0.5 27.26 5
62.31 (45.4)
20
10-2.5 30.49 (-5.1)
69.66 (-3.2)
9 VGG-9, K 50, w/o clip
2o
10-1.5 23.70
48.29
8 10-2.5 25.11
69.10
10 VGG-9, K 50, w/ clip
20
10 1.5 23.80
47.64
100 10 2.5 25.11
69.01
11 VGG-9, 50, clip
10
10-1.0 21.95
46.21 (-2.1)
50
10-2.5
10
2.5 23.41
68.71
12 VGG-9, K 50. w/ clip
5
10 1.0
18.25 (-5.5)
22.58 (-25.7)
20
10
2.5
18.27 (-6.8)
62.70 (-6.4)
(CIFAR-10, C' 2)
13 VGG-9, 9, 5, w/o clip
00
1.0 55.22
76.98
b 1.5 71.58
82.09
14 VGG-9, K 5, w/ clip
20
10-1.0 56.54
78.28
100 10515 71.58
82.17
15 VGG-9, K w/ clip
57.09
78.18
50 71.24
82.18
16 VGG-9, K 5, w/ clip
5
10
1.0 58.26 (43.0)
76.69
20 10 1.5 70.94
82.48
17 VGG-9, K 20, w/o clip
10-1.5 64.04
77.21
D 10-2.0 67.70
81.31
18 VGG-9, K 20. w/ clip
20
10 1.0
66.57 (+2.5)
78.87
100 10 68.11
82.08
19 VGG-9, 9,, 20, clip
10
10-1.0
68.07 (44.0)
78.85
50 10-2.0 67.93
81,50
20 VGG-9, K 20. w/ clip
5
10-1.0 67.11
(+3.1) 76.66
20 10-15 67.74
77.59 (-3.7)
21 VGG-9, K 50. w/o clip
10-15
67.85
10.001
bo 10-2.0 68.05
79.30
22 VGG-9, K 50, clip
20
10
68.26
77.83
100 10 67.01
78.88
23 VGG-9, K 50, w/ clip
10
10-1.0 69.11
78.13
50 10-2.0 67.52
79.42
24 VGG-9, K 50. w/ clip
10 1.0 66.77
75.42
20 10 68.72
78.51
48

---

G.3 Grid search
We use the grid search to find the best learning rate on one random seed "1234". Since we have observed that the best learning rate of PFL is smaller than SFL empirically, the grid for PFL is {10 2.0 10 1.5 1001.0, 1.0, -0.3. (10.01, 0.03, 0.I, 0.3) in fact) and the grid for SFL is {10- 2.5 10 2.0 10 1.5 10 1110--000 (10.003, 0.01, 0.03, 0.1) in fact). We use these grids for all tasks in this paper, including MNIST and FMNIST in the next subsection.
One practical method used in Jhunjhunwala et al. (2023) to find the best learning rate is running the algorithms for a fewer training rounds and then comparing the short-run results by some metrics (e.g., training accuracy) when the computation resources are restrictive and the task is complex (e.g., CIFAR-10). However, we should pay attention to whether the chosen learning rates are appropriate in the specific scenarios, as the best learning rate in the short run may not be the best in the long run. One alternative method is using the short-run results to find some alternatives (coarse- (coarse-grained search) and then using the long-run results to find the best one tine-grained search).
In this paper, for CIFAR- 10 and CINIC- 10, we run the algorithms for 1000 training rounds to find the candidate learning rates (with less then 3% difference to the best result in test accuracy), called as coarse-gratie -ranned search; and then run the algorithms for 4000 training rounds with the candidate learning rates to find the best learning rate (with the highest test accuracy), called fine-grained search. The max norm of gradient clipping is set to 10 for PFL and 50 for SFL for all settings (see subsection G.2). Other hyperparameters are identical to that in the main body.
The results of the coarse-grained grained search are collected in Figure 12, Table 10. Taking the setting training VGG-9 on CIFAR-10 10 as an example. We first find the candidate learning rates, whose short-run test accuracies are only 3% or less below the best accuracy. The candidate learning rates are summarized in Table 9. The training curves are in Figure 11. We then find the best learning rate, whose long-run test accuracy the highest among the candidate learning rates, The final best learning rates are in Table 9, For fine-grand fine-grained search of other settings, please refer to the code.
Table 9: Best learning rates found by the fine-grained search. The candidate learning rates are collected in the cell and the correspond long-run test accuracies in the parentheses. According to the long-run test accuracies, we keep the best learning rate and cross out the others.
Settings
PFL
SFL
CIFAR- 10, VGG-9, C' 1, K = 5
0.1
0.03
CIFAR-10, 10, VGG-9, C' = 1, K = 20
0.1
0.003
CIFAR-10, 10, VGG-9, C 1, K 50
0.03 (28.72), 0.1 (46.21)
0.003
CIFAR-10, VGG-9, C = 2, K = 5
0.1
0,01 (82.008,, 0.03 (82.18)
CIFAR-10, VGG-9, C 2, K 20
0.1
0.01 (81 0.03 (78.35)
CIFAR-10, VGG-9, C = 2, K 50
0.03 (76. 0.1 (78.13)
0.01
HL
SFL
2
cie
2-03
-0
P-13
Figure 11: The corresponding training curves of Table 9. We mark the best learning rate in the short run with **" and other candidate learning rates with som in the legend. The top row shows the first three settings and the bottom row shows the last three settings in Table 9.
49

---

60 900
20000
(a) Left: Logistic/MNIST. Middle: MLP/MNIST. Right: S/NNIST
Co3.6eb
Eekteg
C-2-E=1
K-2
(b) Left: 5/ Right: CNN/FMNIST
6-2,6-5
6-1,6-26
C-2
[-116-)
6-2
6-2
(c) Left: VGG-9/CIFAR-I0 10. Right: Co
Cel.
Cw1.6e3
(d) Left: VCG--/CINIC-I.. Right: ResNet- ICCCNI--
Figure 12: Test accuracies after training for 1000 rounds for various settings. Details are in Table 10.
G.4 More experimental results
More experimental results are provided in this subsection. These include results on MNIST (LeCun et al., 1998), FMNIST (Xiao et al., 2017) and additional results on CIFAR-10 and CINIC-10.
Setup on MNIST and FMNIST: We consider five additional tasks: 1) training Logistic Regression on MNIST, 2) training Multi-Layer Perceptron (MLP) on MNIST, 3) training LeNet-5 (LeCun et al., 1998) on MNIST, 4) training LeNet-5 on FMNIST, 5) training CNN on FMNIST. We partition the training sets of both MNIST and FMNIST into 500 clients by extended Dirichlet strategy == and C - 2 (with a 10.0) and spare the test sets for computing test accuracy. We apply gradient clipping with the max norm of 10 for PFL and 50 for SFL. We find the best learning rate by grid search. This is done by running algorithms for 1000 training rounds and choosing the learning rate that achieves the highest test accuracy averaged over the last 40 training rounds. Note that since tasks on MNIST/FMNIST are quite simpler than that on CIFAR-IO/CINCCS coarse, fine- graingr search. The results of grid search are given in Table 10. Other hyperparameters without being stated explicitly are identical to that of CIFAR- 10/CINIC 10 in the main body.
we do not use the
Results of MNIST and FMNIST. The results of these five tasks are in Figures 13, 14 and Table 11. In the tasks MNIST/MLP, MNIST/LeNet-5, FMNIST/CNN, the performance of SFL better when C' == 1, which is consistent with the analysis in Subsection 4.2. However, we note that SFL shows worse even when C in simpler tasks MNIST/Logistic and FMNIST/LeNet-55, especially when K is large. This may be because the (objective function) heterogeneity on simple models and datasets is limited even with extreme data distributions (i.e., C = 1). Thus, more extensive ex- periments are still required before drawing conclusions, which is beyond the scope of this paper.
50

---

MNIST, Logisitc. C=1
MNIST, Logisitc, C=
MNIST, Logisit. C=1
MNIST, Logisite, C=1
MNIST, Logisitc, C=1
6.00
PTL 5:5
0.00
Stairing hp1 Aucuray (1))
HRL. Km20
3.
K-50
Ki.5
Ku-20
Rrasinn:
Top
8
203
2000
30.0
Thahinn mounds
Tratiing rounds
Taihing rounds
Trannng rounds
Tainnng rounds
MNIST. Logisitc. C
MNIST. Logisitc, Cm2
MNIST. Logisitc. C
MNIST. Logisite. C=2
MNIST. Logisitc, C
0.50
0.00
0.50
FF1, Km5
HRL Km20
Tairing top1 Acourayy
Tost Tusk (90
0.50
PRL Ke50
0.50
Kin
0.00
20:20
K0
0.40
8 8
%
0.30
0.00
0.20
0.20
200
464
669
3000
Thahhing mands
Tratiing mounds
Tailiin rounds
Tasnnng mounds
Tasnnng roUnds
MNIST, MLP. C
MNIST. MLP. C-1
MNIST, MLP, m-1
MNIST, MLP. C
MNIST. MLP. C=1
0.40
0:40
Accuracy 1961
PRL.
Teal Toon Accunicy [S]
KH-0
K0
8 X 8 8 E
K0
0.50
203
70n
Inee
203 A2D
PCS
293
62 POB
1000
190
430
199
Traising
Traiiing
rounds
Traning
Tainnn
MNIST, MLP, 2=2
MNIST, MLP, C=2
MNIST, MLP, ==2
MNIST, MLP, C=
MNIST, MLP, C=
0..43
0140
Trakiing Top3 Accuracy (2))
KH-2
Aicuracy s
K0-00
Talling Lova
bust Topt AcQuracY
0.20
0.00
K-30
0.00
2
Traisingg
0.2h
6mm
222 406
60
1006
220
4LE
G
302
436
669
306
32.0
300
400
B%
3700
20
400 60 B0 270
Training
Traiiing
Taiting rounds
"aannnn
Taining
MNIST, LeNet-5, C=1
MNIST, LeNet-5, C=
MNIST, LeNet-S, C=1
MNIST, LeNet-S, C=1
MNIST, LeNet-5, C=
0.30
0.30
380
Aecuuracy
Tent bost Accuracy (N)
1
&
x
0.55
X
0.50
0.30
283
Inee
0.00
203
22
P2B
201
KCB
66
1230
FSS
130
200
400
170
Training
LoNet-5,
LaNet-5,
C-2
0.10
Tast: Tops Accuraty (54)
0.00
X-50
Training Lenz
0.20
01/27
0.00
222
202
Traliing
K2B
320
Taininground
Figure 13: Experimental results on MNIST. For the best viewing experience, we apply moving average over a window length of 8% of the data points. Note that "Traning Loss/Accuracy" are computed over the training data of participating clients, "Training-R Loss/Accuracy" are computed over the training data of random clients and "Test Accuracy" are computed over the original test set.
51

---

FMNIST, LeNet-S, C=1
FMNIST, LeNet-S, C=1
FMNIST, LeNet-S, C=1
FMNIST, LeNet-5, C-1
FMNIST, LeNet-5, C-1
PLL Ki6
Fairing tep1 Accuracy (h)
"rainng Accurscy
TLux Accurazy 154
K=20
Ke50
N. 5 8
2.30
Kin
K0:20
0.00
K0
0.00
0.50
0.00
2
0.00
0.20
283
toce
209 a2G
203
620
629
3000
3900
400
190
Ttaiiing
Traising
rounds
Tainin rounds
Falnnn
FMNIST, LeNet-S, 2=2
FNNIST, LeNet-S, c=2
FMNIST, LeNet-5, ==
FMNIST, LeNet-5, ===2
FMNIST, LeNet-5, 2=
1.31
Traniigg Toys Accuracy (N4)
PFL, KH20
K-00
Sust bas Acqurao
K000
8
0.00
0..0
252 <06
660
322
ALE
GEB
26
1868
302
636
669
906
1200
300
400
669 BX
3200
73
20
400
609
800 370
Training
Training
Taitiin
Trannin
Taining
FMNIST, CNN, C=
FMNIST, CNN, C=1
FMNIST, CNN, C=1
FMNIST, CNN, C=
FMNIST, CNN. C=
1.50
1.00
0.90
PELL KiHs
0.90
Accussoy (8)
K-20
Talning lops Accuracy
0.50
0.50
0.50
8
0.40
0.20
0.50
202
4D6
600
306
L0c8
0.10
229
AGE
306
2008
70
202
406
669
306
3000
302
400
66)
EX
3000
70
20
400
609
200
CNN, C
CNN,
PMNIST, C
C
0.403
S02t Took Accuracci (S)
Tamnng ong 1op1 Accuracy
0.80
0.50
0.20
223
1028
203 22
42D
201 KCB 66 13:0
3000
400
Figure 14: Experimental results on FMNIST. For the best viewing experience, we apply moving average over a window length of 8% of the data points. Note that "Traning Loss/Accuracy" are computed over the training data of participating clients, "Training-R Loss/Accuracy" are computed over the training data of random clients and "Test Accuracy" computed over the original test set.
52

---

Table 10: Test accuracy results of grid searches for various settings. The results are computed over the last training rounds (with 1000 training rounds total). The highest test accuracy among different learning rates is marked in cyan for both algorithms.
PFL
SFL
Setting
10 2.0
10 1.5
10 1.0
10-0.5
10
10 10-2.5
2.5
10-2.0
10
10
10
MNIST. Logistic, C.
K.K 20
90.95
89.81
87.78
84,33
90.68
87.05
81.38
78.27
MNIST.
Logistic. C
88.98
87.00
86.06
82.49
85.87
76.88
72.82
72.14
MNIST,
Logistic, C
50
86.99
85,50
85.52
81.77
78.45
69.67
67.00
67.09
MNIST, Logistic, C 2, =
91.72
91.48
90.70
89.84
91.97
90.79
86.68
82.43
MNIST. Logistic, C' K 20
91.31
90.54
90.10
89.66
90.29
84.86
78.94
75.18
MNIST, Logistic, C K. 50
90.69
89.89
89.78
89.20
86.45
79.24
73.89
70.85
MNIST, MLP, C
L,K =
91.47
89.51
93.06
91.68
95.13
95.74
95.22
67.44
MNIST, MLP, C L,K 20
78.70
82.53
90.89
87.46
95.79
94.79
91.24
51.06
MNIST, MLP, C K
71.61
78.20
88.73
85.52
94.83
92.46
84.62
26.71
MNIST, MLP, C 2, 55
93.32
94.35
95.66
94.58
95.40
96.14
96.14
93.00
MNIST. MLP, 2.
93.18
94.59
95.62
90.42
96.33
96.25
95.24
55.47
MNIST, MLP, 2.
93.40
94.40
95.28
87.78
96.34
95.36
91.99
43.36
MNIST, LeNet-5, C 1,
68.72
95.46
98.07
98.05
98.28
98.76
98.91
98.29
MNIST, LeNet-5, C 1, 20
58.20
94.30
98.02
97.41
98.43
98.94
98.68
9.84
MNIST, LeNet-5, C= K 50
53.61
93.00
97.23
97.49
98.60
98.77
97.98
9.95
MNIST, eeNet-5, C 2,
96.40
98.43
98.90
98.67
98.62
98.95
98.91
98.55
MNIST, LeNet-5, C= K 20
97.88
98.69
98.86
98.50
98.94
99.17
98.96
97.74
MNIST, LeNet-5, C 2. 50
98.07
98.65
98.93
98.12
98.95
98.99
98.85
97.88
FMNIST, LeNet-S,
5
50.88
71.24
81.83
83.26
82.76
85.34
85.31
82.02
FMNIST. LeNel-5,
20
39.64
69.26
80.73
81.74
78.44
80.84
80.24
61.50
FMNIST, LeNet-5, 5,
50
37.56
68.40
79.73
80.53
73.84
76.51
75.95
42.07
FMNIST, LeNet-5, C = 2,
70.59
81.00
85.44
85.16
80.94
84.51
85.59
83.83
FMNIST, LeNet-5, 5. -2-2, 2, K 20
77.85
84.00
85.70
85.00
80.09
83.20
83.88
77.65
FMNIST, LeNet-5, C 2.
50
81.24
84.17
86.33
84.36
77.73
82.53
81.39
71.13
FMNIST, CNN, C 1, K
75.57
83.44
86.98
86.40
86.83
88.66
87.82
85.01
PMNIST, CNN, C K,K 20
73.84
82.17
85.86
85.11
83.62
87.37
86.14
73.85
FMNIST, CNN, C 1,K
72.94
81.26
84.67
82.41
81.75
85.39
82.42
10.00
FMNIST, CNN, C =22, 5
83.20
86.58
88.26
87.24
86.41
88.71
89.19
87.06
FMNIST. CNN, 2.K
85.12
87.46
88.80
87.08
85.39
89.24
88.48
83.65
FMNIST. CNN, 2.K
85.93
87.82
88.61
86.64
85,53
88.63
87.12
79.50
CIFAR-10, 10. VGG-9, C'= 11=11, 1.K =
12.51
25.67
34.89
28.77
43.79
$3.73
58.63
10.00
CIFAR-10. VGG-9, C K 20
11.51
22.81
28.79
21.10
34.55
27.11
10.00
10.00
CIFAR-10, VGG-9, C
10.14
20.58
21.95
10.00
23.41
10.00
10.00
10.00
CIFAR- 10, VGG-9, C= 21-2,A4 K =
38.50
50.99
57.09
53.46
58.35
68.75
71.24
10.00
CIFAR-10, VGG-9, C =-= K 20
54.70
63.97
68.07
61.92
60.82
67.93
66.50
10.00
CIFAR- 10, VGG-9, C =12 2. K.K 50
62.72
67.57
69.11
64.21
62.27
67.52
62.59
10.00
CIFAR- 10. ResNet-18, C
11.46
19.72
26.50
25.45
33.49
37.77
42.04
36.59
CIFAR-10. ResNet-18, C
1=1,AA K, =
10.56
18.48
23.41
20.86
18.99
26.41
32.70
CIFAR-10, ResNet-18, C K 50
10.55
17.39
22.42
17.86
15.46
17.57
19.39
CIFAR-10 10. ResNet-18 18, C K
23.45
32.71
43.24
47.45
41.24
51.51
65.86
68.17
CIFAR-IO. ResNet-18. 18, C 2, K 20
28.02
42.36
58.07
64.03
42.83
58.43
70.55
58.29
CIFAR-10, R8sNet-18, C 2, K = 50
36.22
46.69
64.75
69.71
47.57
65.33
68.40
46.80
CINIC- 10, VGG-9, 1, = 5
10.36
22.56
29.58
21.02
36.87
42.26
43.27
10.00
1,K CINIC- 10, VGG-9, C 1 20
10.13
19.09
22.83
15.00
28.88
31.54
10.00
10.00
10, VGG-9, C K 50
1,KK
10.37
16.85
17.92
10.00
22.12
10.00
10.00
10.00
CINIC-10. VGG-9, C= K
33.52
42.24
46.12
43.43
43.64
49.28
50.64
10.00
CINIC-10, VGG-9, C
K 20
44.04
48.26
47.80
42.40
48.54
52.10
47.55
10.00
CINIC-10, 10, VGG-9, C K. 50
42.87
46.93
48.29
40.75
48.93
51.11
41.19
13.04
CINIC- 10, R8sNet-18,
1, K 5
10.64
17.16
23.15
21.37
29.52
32.70
33.55
29.92
CINIC-10 10, ResNet-18,
1, K 20
10,29
14.65
18.01
16.68
19.91
20.42
29.57
10.00
CINIC-10, 10, ResNet-18, C == =1, K 50
10.18
13.65
16.27
14.35
14.56
17.72
26.30
10.00
CINIC- 10, 18 C=22 P.K- =
-22,
22.59
28.03
35.78
39.35
34.06
38.73
43.57
44.67
CINIC- 10, R8
C'22 K 20
27.18
34.74
43.40
43.46
30.27
37.96
46.13
36.81
CINIC- 10, R8. C --2. K.K 50
30.36
37.05
40.74
38.90
33.77
43.20
42.32
11.35
53

---

Table 11: Test accuracy results for various settings. We PFL and SFL for 1000 training rounds for MNIST and FMNIST and 4000 training rounds for CIFAR-10 10 and CINIC-10 with different random seeds. The results computed over the random seeds and the last 40 training rounds for MNIST and FMNIST and the last 100 training rounds for CIFAR-10 and CINIC-10. The better re- sults (with more than 1% advantage for MNIST/FMNIST and 2% advantage for CIFAR- CIFAR-IO/CINIC: 10) between PFL and SFL each setting are marked in color.
Setup
C'
C
Dataset
Model
Method K
5
K = 20
K 50
K 5
K
20
K 50
PFL
91.10 89,46
87.82+1.9
91.69 91. 1940.7 90.46+086
Logistic
SFL
91.092007 87. 1200 80.94
91.8910.22 90. 1610 86.521241
MNIST
PFL
93.61 1.42 91.84+220
90.27 #
95.65 +0.3a 95.46+0.7 95.34 +0.51
MLP
SFL
95.91 +0.33 95.90 95.25 o..76
96.26 96.35 +0.2 96.35 #0.32
PFL
98.21 40.00 98.
97.21 11.5
98.94 98 98.97
98.98 10.11
LeNet-5
SFL
98.90 10.18 98.87 10.19 98.79+0.1.
98.91 +0.1 99.07 98.99
PFL
82.57 2200 81.09
78.22
85.8611m 86.35 86.58 2
LeNet-5
SFL
83.97 +2.42 79.39
76.21 +:2.5
86.52 84.69+2.0 83.58 +2.55
FMNIST
PFL
86.61
L.6 85,40
84.62++2.18
88.61 +:.93
$9.16
CNN
SFL
88.03 86.75.139
85.44
89.91 10.96 89.60
89.05
PFL
67.61
14.0 62.00
45.77 =5.91
78.42+1.7
78. 4
1.35 78.01 1:55
VGG-9
SFL
78.43 22.46 72.61
68.86
82.5611.66
82. 12.181199 97 79.67 12.30
CIFAR-10
ResNet-18
PFL
52.12 6.09 44.58
+4439
34.29 ::499
80.27 +:52 82.27 1.55 79.88 #22118
SFL
83.4
+ 1.3 76.97
68.91 +:429
87.16+1.3
84.90+3.55
79.38 1:449
PFL
52.61 #3.19
45.98
34.08=4.77
55.84
53.41 1002 52.04+0.9
VGG-9
SFL
59.1 10.74 58.7 1099 56.67+1.1
60.82+0611
59. 59.7841.79 56.87 (.877110
CINIC-10
PFL
41.12
33. 19477
24.71 14.89
57.70
55.59 46.99
R8
SFL
60.36 +..7 51.84+2215
14.95+2297
64. 58 +8.05+2554
56.28 +2.32
54

---

3.0
Traniing lops Accurss (P))
2.50
K=20
2,50
22 X
K-50
2.00
K0
1.00
5
Thitiin
Tatning
CIFAN-10, VSG.9.C C
CIAR-15, VOG.S, Cm
CIFAR11 VOG-A Cw2
GIAR--D. VGG--1, Ci22
CIFAR-10. VGS-U C-2
Tranting Took Accuracy (14)
PPL, K.-0
3 & 8
I m
PFL, K6-00
3PL Km
0.30
SPL Km20
5RL Km
0.40
0,40
0..00
2200
236
201
12:0
43.0
Traiting rounds
Traiiing rounds
Talting rounds
Tainnng rounds
Training rounds
CIFAR-00 ResNet118, C=1
CIFAR-10. RedNet 18 Cw1
CIFAR-10. Reshiet 18. 1
GFAR-10 Reshiet-1. C=1
CIAR- Resket-1B.
2.00
5.00
4.00
4,00
Training liet Accunta
Tainigg Accuracy
(16)
6.3
Faining
2:20
1,00
1,00
0:00
1009
2000
1069
2300
3289
2000
6300
130
2006
3009
4300
1300
2008
490
1.70
K2-20
Rratingg lost Accuracy (S]
8 28 8 x
Thariing Accuraccy X 8 20
x
K0-00
Top Accurasc
4.00
20
0.79
51L K0
0.00
0.5
Thalingg rounds
Trahingg rounds
Talning roUnds
Tainnng rounds
Tainnn FoUndS
Figure 15: Experimental results CIFAR-10. For the best viewing experience, apply moving average over a window length of 4% of the data points. Note that "Traning Loss/Accuracy" are computed over the training data of participating clients, "Training-R Loss/Accuracy are computed over the training data of random clients and "Test Accuracy" are computed over the original test set. The shaded areas show the standard deviation with random seeds.
55

---

3.00
K=20
Taaitargee Toct Act-aray
K-50
1302 Acturacy
K0:20
2.30
Thiting
Tatning
CNIC-DD VGD-) Cm
CNIC-10 VGG-g, Cww
CINIC-IG VoG-a, Cw2
CINIC-10, VGG-2 Cw2
CINC-20, VSG-2 C=2
1.20
PFL, K-20
Tana Keps. Accu LeCLo (ho)
PFL. K-50
3PL Km
2
5PL Km20
5PL Km30
8
85
0.20
0.00
2200
2250
Traiting rounds
Traiinng rounds
Taiting rounds
Taining rounds
Trannnn rounds
CINIC-10, Restiet-BB. C=1
CINIC300 30, Reshiet- 18.
CINIC-30, ResNet- 18, C=1
CIMC-10 10, Restitt 18, C=1
CIMC-10 RedNet-18,
2.00
5,00
339
&
Paimmpp-f Topt Accuracy
To0t Actumaaa PM
4.00
4,00
Faining
R
2:20
&
1,00
1,00
0:00
1009
2000
1C89
2300
3289
2300
6300
130
300
3009
4300
1300
2.90
K1200
&
1230
Kx500
B 2
20
51L K0
1:30
0.50
Thaling rounds
Traiing rounds
Talning RoUnds
Trannnng rounds
Tainnn FoUndS
Experimental results CINIC-10. For the best viewing experience, apply moving average over a window length of 4% of the data points. Note that "Traning Loss/Accuracy" are computed over the training data of participating clients, "Training-R Loss/Accuracy are computed over the training data of random clients and "Test Accuracy" are computed over the original test set. The shaded areas show the standard deviation with random seeds.
Figure 16:
56


Reviews:
[{"review_id": "LuszPmQMFh", "reviewer": "Reviewer_4Dha", "summary": "This paper provides the first theoretical convergence rates for sequential split learning (SSL) in the presence of heterogeneous data. In each round of SSL, a random permutation of the machines is computed. According to this permutation, each machine performs $K$ local gradient steps on the model sequentially. When the data on the clients is non-iid, due to the sequential nature of the steps, the updates are biased gradients of the true objective, which is the average of losses on all machines. This is the main challenge in analyzing SSL.\n\nThe authors extend the proof of FedAvg to provide tight convergence rates for SSL on non-convex, convex and strongly-convex loss functions under standard assumptions of smoothness, bounded gradient noise and heterogeneity between machines.\n\n\nThey show that SSL has strictly better convergence rates than FedAvg. In particular, the heterogeneity term in the rates decreases by a\nfactor of $\\frac{1}{M}$, where $M$ is the number of machines.\n\n\nThey demonstrate the improvement of SSL over FedAvg empirically for quadratics under high heterogeneity. Additional experiments on CIFAR10 under high heterogeneity support this observation.\n", "questions": "- A recent paper (Yun et al, 2022) considers Minibatch and Local SGD with Random Reshuffling. It would be interesting to compare its theoretical rates with SSL, which has close connections to Random Reshuffling.\n- Does the improvement in the rates for SSL over FedAvg come from a better bound on the client drift?\n\n**References**\n- (Yun et al, 2022) : Minibatch vs Local SGD with Shuffling : Tight Convergence Bounds and Beyond. ICLR 2022.\n", "limitations": "Described in Weaknesses", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Convergence rates** : Clean convergence results are provided under the same assumptions as FedAvg. For local steps, $K=1$, SSL is equivalent to Random Reshuffling, and the obtained convergence rates match its lower bound.\n- **Thorough comparison to FedAvg** : The authors provide thorough comparisons to the best possible rates for FedAvg under full participation and partial participation and demonstrate the improvement due to SSL.\n\n- **Experiments validate theory**: Synthetic experiments show a clear improvement of SSL over FedAvg in high heterogeneity conditions.\n- **Detailed Appendix** : There are several additional experiments in the appendix on more quadratic problems, MNIST and FMNIST, under varying hyperparameters. It might be beneficial to move one of these experiments to the main paper.\n- **Marginally better rates for FedAvg on strongly convex functions**: The authors obtain marginally better rates for FedAvg in terms of constants by combining two existing proofs.\n", "weaknesses": "- **Analysis of Split learning without any explicit splits** :  In SSL, or any form of split learning (Gupta and Raskar, 2018), a crucial component of the algorithm is the model being split into two parts, one for the server and one for the client. The analysis considers sequential local updates only without any form of splits in the model. This could be clarified in the introduction.\n- **Minor improvement in CIFAR10 figures**: This is a minor weakness, but Fig 2 is difficult to read. Using different color schemes for FedAvg and SSL or showing only 2 values of local steps might improve clarity.\n- **SSL as a case of FedAvg with partial participation** : Note that if we perform FedAvg with $S=1$ worker per round sampled without replacement for $R$ rounds, then this algorithm is same as running SSL for $R/M$ rounds. Could the analysis of FedAvg with partial participation then recover the same rates as this paper?\n\n**References**\n- (Gupta and Raskar, 2018) : Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This part contains 5 responses, denoted by R2-R6.\n\n##### **R2: (W1) Analysis of Split learning without any explicit splits.**\n\nAs suggested, we would like to clarify that the operation details (e.g., the form of model split) would not affect the convergence analyses of SSL. To this end, we stated the simplified version of SSL in Algorithm 1 in the Introduction and deferred the details to Appendix D. Please refer to R1 (in the global response) for details.\n\n---\n\n##### **R3: (W2) Minor improvement in CIFAR10 figures.**\n\nAs suggested, we will improve Fig. 2 for better clarity.\n\n---\n\n##### **R4: (W3) SSL as a case of FedAvg with partial participation.**\n\nWith the existing assumptions and techniques in this paper, SSL would exhibit better convergence bound than FedAvg with partial participation. Let us concentrate on the terms containing $\\zeta_\\ast^2$ regardless of the terms containing $\\sigma^2$ for simplicity, and one simple and intuitive comparison is as follows:\n\n+ Following the assumptions in this paper, it is necessary to contain the term $\\tilde{\\mathcal{O}}(\\frac{\\zeta_\\ast^2}{\\mu R})$ ($S=1$) for the final result of FedAvg with partial participation, i.e., the term marked with red in Eq. (12) at line 200 in the paper, which is caused by partial participation variance. In other words, the final result of FedAvg with partial participation will contain at least one term $\\tilde{\\mathcal{O}}(\\frac{\\zeta_\\ast^2}{\\mu R})$. However, the dominant term of SSL is $\\tilde{\\mathcal{O}}(\\frac{L\\zeta_\\ast^2}{\\mu^2MR^2})$ (see Table 1). Then for sufficiently large $R$, the bound of FedAvg with partial participation is worse than our bound of SSL.\n+ In summary, SSL would exhibit better convergence bound than FedAvg with partial participation based on the existing assumptions and techniques in this paper. This may require other assumptions or techniques for FedAvg to fill the gap, and is beyond this work.\n\n---\n\n##### **R5: (Q1) Compare the theoretical results of Yun et al. (2022) with SSL.**\n\nOne main contribution of Yun et al, (2022) [Ref 1] is the convergence guarantees of Minibatch RR and local RR. Considering that local RR with multiple local steps is more relevant to SSL, we focus on the comparison to local RR in the following aspects:\n\n+ *Algorithms*. Local RR is one variant of local SGD, where clients perform Random Reshuffling locally (in parallel) instead of SGD. Note that local SGD and FedAvg can be considered equivalent in the context of this work. For this reason, local RR is different from SSL in the algorithm (mechanism) aspect.\n\n+ *Assumptions*. (1) Yun et al, (2022) considered the non-convex case with the $\\mu$-PL condition, which can be viewed as a nonconvex generalization of strongly convex functions; while we consider three cases of strongly convex, convex and non-convex. (2) Yun et al, (2022) considered a different assumption to bound the heterogeneity among local objectives:\n  $$\n  \\frac{1}{M}\\sum_{m=1}^M\\||\\nabla F_m (x)\\|| \\leq \\tau + \\rho \\||\\nabla F(x)\\||\n  $$\n  According to their analyses in Appendix A, this assumption is weaker than Eq. (4), but stronger than Eq. (5) of our Assumption 3.\n\n+ *Upper bounds*. Since $\\mu$-PL condition is one weaker yet close assumption to $\\mu$-strongly convex, we compare their bound with ours in the strongly convex case. Besides, due to differences in assumptions, we need to translate their bounds into our settings. The translated upper bounds of their Theorem 2 and our bound of SSL are summarized in [Table 1] below.\n\n  [Table 1: Upper bounds of SSL and local RR. Noting that their bounds hold only for the large epoch regime, i.e., $R$ is sufficiently large, the negative exponential term $\\mu D^2 \\exp(-\\frac{\\mu R}{L})$ of our bound can be omitted. The number of instances of each client is denoted as $N$. The difference between the two bounds is marked in red.]\n\n  | Algorithm | Bound                                                        |\n  | --------- | ------------------------------------------------------------ |\n  | local RR  | $\\displaystyle \\tilde{\\mathcal{O}} \\left({\\color{red}\\frac{L^2}{\\mu^2}\\cdot \\frac{N}{KR}}\\cdot \\frac{\\sigma^2}{\\mu MKR} + {\\color{red}\\frac{L}{\\mu}\\cdot M} \\cdot \\frac{L\\sigma^2}{\\mu^2 MKR^2} + {\\color{red}\\frac{L}{\\mu}\\cdot M} \\cdot \\frac{L\\zeta_\\ast^2}{\\mu^2MR^2}\\right)$ |\n  | SSL       | $\\displaystyle \\tilde{\\mathcal{O}} \\left(\\frac{\\sigma^2}{\\mu MKR} + \\frac{L\\sigma^2}{\\mu^2 MKR^2} + \\frac{L\\zeta_\\ast^2}{\\mu^2MR^2}\\right)$ |\n\n  We can observe that the first term of local RR is better than the corresponding one of SSL when $\\frac{KR}{N} \\geq \\frac{L^2}{\\mu^2}$ yet the last two terms are strictly worse than their corresponding terms of SSL. At last, we would like to clarify that this comparison may not be reasonable considering that Yun et al (2022)'s are high-probability bounds while ours are in-expectation bounds, so more research is still required for a comprehensive comparison.\n\n---\n\n##### **R6: (Q2) Does the improvement of SSL come from a better bound on the client drift?**\n\nYes. Similar to the bound of FedAvg, we can divide the terms into three components, global stochastic term, client drift term and optimization term, where the client drift term is caused by \"client drift\" and the other two terms appear in the standard convergence bound of SGD (see the 1-st row of Table 1).\n\nAs we can see, the advantage of SSL shows in the client drift term, which benefits from its sequential and shuffling-based training manner.\n$$\n\\tilde{\\mathcal{O}} \\left(\\underbrace{\\frac{\\sigma^2}{\\mu MKR}}\\_{\\text{global stochastic term}} + \\underbrace{\\frac{L\\sigma^2}{\\mu^2 MKR^2} + \\frac{L\\zeta\\_\\ast^2}{\\mu^2MR^2}}\\_{\\text{client drift term}}+\\underbrace{\\mu D^2 \\exp(-\\frac{\\mu}{12L}R)}\\_{\\text{optimization term}} \\right)\n$$"}, {"review_id": "MF3m1MVDAi", "reviewer": "Reviewer_D6Q7", "summary": "The authors provides the convergence analysis of a FL-like approach where clients updates the model sequentially based on local datasets. Results are provided for the strongly convex, convex, and non-convex case.  Interestingly, the analysis shows that in some setting the sequential approach can outperform the usual FL approach where multiple clients update the local model in parallel and a server aggregates the updates.\nI do not understand why split learning is mentioned in the title and in the rest of the paper, as there is no model split across clients or across the clients and server as far as I can say.", "questions": "* why do the authors refer to split computing? which model is split? Algorithm 1 shows well that all clients train the same model architecture.\n* what is denoted by SFLv1? if it denotes simply the algorithm proposed in (Thapa et al., 2020) just say it. Also in the rest of the paper, including in the experiment section, SFL is never evaluated, but he proposed solution is compared with FedAvg. \n* the paper suggests in different places that increasing the number of local iterations may have a beneficial effect at first and then be harmful, but in reality the bounds in the paper suggest that it is always beneficial to increase K but with a diminishing return, right? If so, some statements while commenting figure 2 should be modified.\n", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The convergence analysis is interesting; it shows the authors master a number of existing techniques used to prove convergence results of distributed training procedures\n* the result about sequential training  outperforming FedAvg is very interesting and indeed counterintuitive as observed by the authors\n* This was the best paper in my batch (6 papers)\n", "weaknesses": "* The reference to split computing, while this paper does not deal with split computing.\n* The result about SSL outperforming FedAvg is interesting, but the paper does not provide any intuitive explanation about why this may be the case. Also the bounds suggest that it should always be the case in the strongly convex setting for any value of $\\zeta^*$, not only in the highly heterogeneous setting (large $\\zeta^*$).\n* I do not find the comparison with FedAvg under partial clients' participation fair. The authors should consider that at each round the clients available will sequentially perform  SSL. Instead, they assume that all clients participate, but the reduce the total number of rounds. \n* there are some papers about the convergence of sequential optimization which should be cited. I think most of them consider a single gradient update at each node and focus on random walks. Examples:\n\t* Ram, S., Nedić, A., and Veeravalli, V. (2009). Incre- mental stochastic subgradient algorithms for con- vex optimization. SIAM Journal on Optimization, 20(2):691–717.\n\t* Johansson, B., Rabi, M., and Johansson, M. (2009). A randomized incremental subgradient method for dis- tributed optimization in networked systems. SIAM Journal on Optimization, 20(3):1157–1170\n\t* Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., and Yin, W. (2020). Walkman: A Communication- Efficient Random-Walk Algorithm for Decentralized Optimization. IEEE Transactions on Signal Process- ing, 68:2513–2528.\n\t* Ayache, G. and Rouayheb, S. E. (2020). Private Weighted Random Walk Stochastic Gradient De- scent. Technical report, arXiv:2009.01790.\n\t* Cyffers, E., Bellet, A., Privacy amplification by decentralization, AISTATS 2022\n* There are some sentence that are poorly worded, some examples\n\t* line 72: \"it cannot follow the theory of SGD\", rather  \"SGD theory does not apply\"\n\t* line 120: \"Or further, it only holds at the optimum.\", it seems the authors mean. \"In alternative, the condition is required only at a global minimizer\"\n\t* line 126 and elsewhere: \"making it hold that\", simply \"and it holds\"?\n\t* line 188, what do the authors mean by \"our comparison is persuasive\"?\n\t* line 210, the section is not really about \"feasability\", it is just providing some numerical \"evidence\" tha the counterintuitive result can appear even for simple quadratic functions. As no intuitive explanation is provided, I think this section should be merged with the experiments one.\n\t* line 218, \"which is tight to capture the gradient diversities\", what the authors mean is that the bound may be pessimistic for fedavg where averaging can limitate the effect of statistical heterogeneity, but less for SSL because of its sequential nature.\n* Others:\n\t* line 67, (Wang et al, 2020) is indicated as an example dealing with unbalanced data, but I would say it rather deals with unbalanced computation.\n\t* line 67 trival -> trivial\n\t* line 114 and elsewhere: using assumption (4) to indicate the equation (4) in assumption 3 may be confusing\n\t* There are some papers which are cited as preprint, but have been published. For example Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion in non-iid federated learning appeared at ICLR 2021\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This part contains 8 responses, denoted by R7-R14.\n\n##### **R7: (W1) Does not deal with split computing.**\n\nDue to space limitation, please refer to R1 (the global response) for details.\n\n---\n\n##### **R8: (W2) No intuitive explanation about why this may be the case.**\n\n*The Intuition about why SSL performs better than FedAvg in the extremely heterogeneous settings*. Intuitively, FedAvg updates the global model less frequently with more accurate gradients (by aggregating the gradients from multiple clients). In contrast, SSL updates the global model more frequently with less accurate gradients (from every single client). In the extremely heterogeneous settings where even aggregated gradients from multiple clients in FedAvg may be still inaccurate, the benefits of frequent updates in SSL turn dominant, and thus SSL can outperform FedAvg.\n\n*The reason why SSL may not perform better than FedAvg in the moderately heterogeneous settings, even the upper bound of SSL is better than FedAvg.* First, we agree that the upper bound (or worst-case error) of SSL is better than FedAvg regardless of the value of $\\zeta_\\ast$, which suggests SSL performs better than FedAvg, at least in the worst case. However, the comparison result may not apply to the \"normal\" cases. The upper bound of SSL is tight considering its sequential training manner, while the upper bound of FedAvg may be too pessimistic (omitting the function of aggregation) in the \"normal\" cases (Wang et al., 2022) [Ref 2]. For this reason, the performance of FedAvg can be comparable to or even better than SSL in the moderately heterogeneous settings.\n\n---\n\n##### **R9: (W3) The fairness of the comparison with FedAvg under partial clients' participation.**\n\nAs pointed out, the comparison result in the paper is based on the traditional training patterns of FedAvg and SSL, which may cause unfairness as SSL does not perform client sampling. As suggested, we provide the theoretical comparison results for FedAvg and SSL with partial participation. The sampling error is caused by sampling partial clients per training round. Sampling without replacement is considered here, and $S$ is the sampling size. We see that the improvement ($1/S$, marked in red) of SSL also exists, similar to the full participation setup. \n$$\n\\text{FedAvg:}\\quad\n\\tilde{\\mathcal{O}} \\left(\\frac{\\sigma^2}{\\mu SKR} + \\underbrace{\\frac{\\zeta\\_\\ast^2}{\\mu R}\\frac{M-S}{S(M-1)}}\\_{\\text{sampling error}} + \\frac{L\\sigma^2}{\\mu^2 KR^2} + \\frac{L\\zeta_\\ast^2}{\\mu^2R^2}+\\mu D^2 \\exp(-\\frac{\\mu}{12L}R) \\right)\n$$\n\n$$\n\\text{SSL:}\\quad\n\\tilde{\\mathcal{O}} \\left(\\frac{\\sigma^2}{\\mu SKR} + \\underbrace{\\frac{\\zeta_\\ast^2}{\\mu R}\\frac{M-S}{S(M-1)}}\\_{\\text{sampling error}}+ \\frac{L\\sigma^2}{\\mu^2 {\\color{red}S}KR^2} + \\frac{L\\zeta_\\ast^2}{\\mu^2{\\color{red}S}R^2}+\\mu D^2 \\exp(-\\frac{\\mu}{12L}R) \\right)\n$$\n\nExperimental validation is also prepared. For convenience, we use the same experimental setups as our new-added experiments (please refer to R22 (in Reviewer K7U9) for results of FedAvg and detailed experimental setups). The experiments are given in [Table 2]. SSL with partial participation is denoted as SSL-II. It can be seen that SSL-II shows a close performance to SSL, with only a loss of less than 1.5 % in test accuracy in all setups.\n\n[Table 2: Test accuracies (%) of FedAvg and SSL with ResNet-18 on CIFAR-10 and CINIC-10. We run both algorithms for 4000 training rounds and report the averaged test accuracies over the last 100 training rounds and 3 random seeds.]\n\n| Dataset  | Method | ExDir(1, 10.0)  | ExDir(1, 10.0)  | ExDir(1, 10.0)  | ExDir(2, 10.0)  | ExDir(2, 10.0)  | ExDir(2, 10.0)  |\n| -------- | ------ | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- |\n|          |        | $K=5$           | $K=20$          | $K=50$          | $K=5$           | $K=20$          | $K=50$          |\n| CIFAR-10 | SSL    | $82.84\\pm 2.07$ | $76.93\\pm 3.64$ | $68.90\\pm 4.59$ | $87.33\\pm 1.27$ | $85.21\\pm 2.57$ | $78.54\\pm 4.76$ |\n| CIFAR-10 | SSL-II | $82.68\\pm 2.33$ | $76.58\\pm 4.84$ | $67.73\\pm 6.46$ | $87.29\\pm 1.35$ | $84.72\\pm 3.51$ | $78.84\\pm 4.15$ |\n| CINIC-10 | SSL    | $60.42\\pm 1.81$ | $53.20\\pm 1.78$ | $45.81\\pm 3.02$ | $64.70\\pm 1.36$ | $58.59\\pm 2.15$ | $57.58\\pm 1.90$ |\n| CINIC-10 | SSL-II | $60.56\\pm 1.49$ | $51.98\\pm 2.02$ | $44.75\\pm 3.46$ | $64.27\\pm 1.12$ | $58.15\\pm 1.92$ | $56.45\\pm 2.29$ |\n\n---\n\n##### **R10: (W4) Some papers about the convergence of sequential optimization should be cited.**\n\nWe will cite and discuss the recommended papers in the revision as suggested.\n\n---\n\n##### **R11: (W5) There are some sentence that are poorly worded.**\n\n+ As suggested, we will improve our presentation of lines 67, 72, 114, 120, 126, 188, 218.\n+ We will reorganize this section with Section 5 Experiments for line 210.\n+ We will adjust our references.\n\n---\n\n##### **R12: (Q1) Why do the authors refer to split computing?**\n\nDue to space limitation, please refer to R1 (in the global response) for details.\n\n---\n\n##### **R13: (Q2) What is denoted by SFLv1? SFL is not evaluated.**\n\nSFLV1 (Thapa et al., 2020) [Ref 3] is one typical algorithm in SL, which shares the same update rule with FedAvg (Algorithm 2), and shows a close performance to FedAvg (Gao et al., 2021) [Ref 4]. For this reason, we do not evaluate it. Please refer to R1 for details.\n\n---\n\n##### **R14: (Q3) Some statements while commenting figure 2 should be modified.**\n\nAs pointed out, increasing the value of $K$ can always cause a diminishing return according to our bound. The phenomenon that increasing the number of local iterations may have a beneficial effect at first and then be harmful is common in the literature, which may be due to overfitting. As suggested, we will improve the statements of Fig. 2.\n"}, {"review_id": "99FHYXum9O", "reviewer": "Reviewer_98XT", "summary": "This paper studies the Sequential SL algorithm in which the at each round, sequentially, each machine performs some local SGD iterations, and then the final iterate is passed on to the next machine.  Such an algorithm may be useful in cross-device, resource constrained settings, where local iterations are expensive.The papers compares the performance of this algorithm to the performance of Federated Averaging, where the local SGD iterations are performed in parallel rather than sequentially. They study a heterogenous data setting, where the distribution of data is different at each machine, under strongly convex, convex, and non-convex settings. While the SL algorithm has larger parallel depth than federated averaging, the authors show that the SSL algorithm outperforms FedAvg in the strongly convex setting. They also show some minor improvements in the convergence of Federated Averaging by reanalyzing this popular algorithm. They provide experiments in a heterogenous environment to show that for high levels of hetergeneity, SSL outperforms FedAvg without contradicting prior experimental evidence.", "questions": "See weakness above.\nMinor comment: Line 134 vanishes --> vanish", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The authors provide a clean analysis of SSL under standard assumptions in strongly convex, convex, and non-convex settings. They also show how to slightly improve the analysis of FedAvg in a heterogeneous setting, which cleans up some small gaps between bounds in the literature. \n- The SSL algorithm they analyze is simple and natural, yet is not immediate to understand with existing analyses. \n", "weaknesses": "*Clarity*:\n- The two last paragraphs on page 1 are somewhat confusing. The 2nd to last P seems to span about FedAvg. But then the last paragraph seems to speak about but SSL and about FedAvg (which is called SFLV1, which is confusing). Could the authors streamline these paragraphs to make it clear the two algorithms considered, and also clarify if SFLV1 = FedAvg or how they are different.\n- What does it mean that the model is trained partially at the server? I don't see this in Algorithm 1?\n- I find the emphasis on \"counterintuitive\" to be off-putting, because it seems natural that SSL, which is a sequentially deeper algorithm will perform better. \n- Could the authors make Assumption 3 clearer by breaking it into assumption 3a and 3b or break its into two assumptions environments. \n\n*Comparison to other theoretical results is confusing or sometimes misleading*\n- The discussion in the paragraph at line 154 is confusing. Perhaps a table would be helpful. Further, it is misleading that the authors say that their bounds are tight, because there seams to be a difference in depenence on M (which is quite significant), and anyways, the tightness would only be for the K = 1 case.\n- In the comparison to FedAvg (line 189 paragraph), the authors only discuss the strongly convex setting. Could they please explain the other cases too. The following paragraph (line 193) is quite confusing - I have no idea what the authors are saying. \n- In the discussion of heterogeneity and in the empirical experiments, the authors claim that SSL is better relative to FedAvg when there is more heterogeneity. But this does not completely make sense, because in the homogenous setting, where there is no heterogenity, SSL would be strictly better than FedAvg. Could the authors please discuss and clarify this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This part contains 7 responses, denoted by R15-R21.\n\n##### **R15: (W1) The two last paragraphs on page 1 are somewhat confusing.**\n\nAs suggested, we will streamline these paragraphs in the revision. We would like to clarify that SFLV1 shares the same update rule with FedAvg despite SFLV1 $\\neq$ FeAvg. Please refer to R1 (in the global response) for details.\n\n---\n\n##### **R16: (W2) What does it mean that the model is trained partially at the server?**\n\nAlgorithm 1 is a simplified version of SSL, and the detailed version was deferred to Appendix D. Please refer to R1 for details.\n\n---\n\n##### **R17: (W3) It seems not counterintuitive that SSL performs better than FedAvg.**\n\nWe would like to clarify that the derived result that SSL can outperform FedAvg is novel.\n\nSSL updates the global model more frequently with less accurate gradients (from every single client). In contrast, FedAvg updates the global model less frequently with more accurate gradients (by aggregating the gradients from multiple clients).\n\nIntuitively, one might say that 1) SSL can outperform FedAvg in the homogeneous setting since the gradients from each client are accurate, 2) while the performance of SSL would be worse than FedAvg in the heterogeneous settings since the aggregated gradients from multiple clients are more accurate than that from one single client. The state-of-the-art work  Gao et al. (2021) [Ref 4] arrives at the same conclusion as the aforementioned intuitive one by empirical experiments.\n\nHowever, in this work, we show the counterintuitive result that SSL can also outperform FedAvg in the \"extremely\" heterogeneous settings, and analyze the effect of data heterogeneity on the comparison.\n\n---\n\n##### **R18: (W4) Break Assumption 3 into two assumptions.**\n\nAs suggested, we will break Assumption 3 into two assumptions in the revision.\n\n---\n\n##### **R19: (W5) The discussion in the paragraph at line 154 is confusing**\n\n[Table 3: The bounds of SSL and Random Reshuffling (RR). The bound of SSL when $K=1$ and $\\sigma=0$ is shown in the first row; the bound of RR (Mishchenko et al., 2020) [Ref 5] in the second row; and the lower bound of RR (Safran and Shamir, 2020) [Ref 6] in the third row. We omit all the constants (including $\\mu$ and $L$) for clarity.]\n\n| Algorithm | SSL                                                          | RR                                                           | RR (lower bound)                                        |\n| --| -- | -- | -- |\n| **Bound** | $\\tilde{\\mathcal{O}} \\left(\\frac{\\zeta_\\ast^2}{MR^2} + D^2 \\exp(-R)\\right)$ | $\\tilde{\\mathcal{O}} \\left(\\frac{\\zeta_\\ast^2}{MR^2} + D^2 \\exp(- {\\color{red}M}R)\\right)$ | $\\Omega\\left(\\min(1, \\frac{\\zeta_\\ast^2}{MR^2})\\right)$ |\n\n+ *The tightness for the case $K=1$ for sufficiently large $R$.* The difference between the upper and lower bounds is the negative exponential term (smaller than the first term when $R$ is sufficiently large), i.e., the bound will match the lower bound. We will add the restriction in the revision.\n\n+ *Difference on* $M$. As pointed out, RR has advantage on the negative exponential term. The advantage can be neglected for sufficiently large $R$.\n\n+ *The tightness for the* $K=1$ *case*. We use the lower bound of RR to validate our tightness. As pointed out, the lower bound designed for SSL is still required, which is currently a theoretical limitation of our work. We will clarify the limitations in the revision.\n\n---\n\n##### **R20: (W6) Explain the other cases**\n\n[Table 4: Upper bounds in the general convex and non-convex cases with absolute constants omitted. We use the bounds of Theorem 2 for FedAvg to keep the same assumptions and setups. $D\\coloneqq\\||x^0-x^\\ast\\||^2$ and $A\\coloneqq F(x^0)-F^\\ast$. ]\n\n| Algorithm | General convex case                                          | Non-convex case                                              |\n| -- | -- | -- |\n| FedAvg    | $\\displaystyle \\frac{\\sigma D}{\\sqrt{MKR}}+ \\frac{(L\\sigma^2D^4)^{1/3}}{K^{1/3}R^{2/3}}+ \\frac{(L\\zeta_\\ast^2D^4)^{1/3}}{R^{2/3}} + \\frac{LD^2}{R}$ | $\\displaystyle \\frac{(\\sigma^2LA)^{1/2}}{\\sqrt{MKR}}+ \\frac{(L^2\\sigma^2A^2)^{1/3}}{K^{1/3}R^{2/3}}+ \\frac{(L^2\\zeta^2A^2)^{1/3}}{R^{2/3}} + \\frac{LB^2A}{R}$ |\n| SSL       | $\\displaystyle\\frac{\\sigma D}{\\sqrt{MKR}}+ \\frac{(L\\sigma^2D^4)^{1/3}}{{\\color{red}M^{1/3}}K^{1/3}R^{2/3}}+ \\frac{(L\\zeta_\\ast^2D^4)^{1/3}}{{\\color{red}M^{1/3}}R^{2/3}} + \\frac{LD^2}{R}$ | $\\displaystyle \\frac{(\\sigma^2LA)^{1/2}}{\\sqrt{MKR}}+ \\frac{(L^2\\sigma^2A^2)^{1/3}}{{\\color{red}M^{1/3}}K^{1/3}R^{2/3}}+ \\frac{(L^2\\zeta^2A^2)^{1/3}}{{\\color{red}M^{1/3}}R^{2/3}} + \\frac{LB^2A}{R}$ |\n\n(1) From [Table 4], we see that SSL shows the similar advantage over FedAvg in the general convex and non-convex cases, to the strongly convex case. (2) We will clarify the following paragraph (line 193) with more details.\n\n---\n\n#### **R21: (W7)  Clarification and discussion for SSL's better performance.**\n\nWe would like to clarify that SSL can outperform FedAvg in the homogeneous and \"extremely\" heterogeneous settings, but may underperform in the \"moderately\" heterogeneous setting.\n\n+ We prove that SSL has better convergence bound than FedAvg (i.e., SSL can outperform FedAvg in the worst case). However, the bound for FedAvg may be loose, since the global aggregation of FedAvg can help improve the gradient accuracy to achieve better performance in practice. \n\n+ In the homogeneous setting (the one-client gradient of SSL is already accurate) and \"extremely\" heterogeneous setting (the gradient aggregation cannot achieve accurate gradient), the gradient aggregation in FedAvg does not significantly contribute to the convergence. Nevertheless, in the \"moderately\" heterogeneous setting (the gradient aggregation does help obtain the accurate gradient), FedAvg can achieve much better performance than its bound and outperform SSL."}, {"review_id": "lVQblESeWa", "reviewer": "Reviewer_K7U9", "summary": "This paper presents an intriguing exploration of the counterintuitive comparison results between Sequential SL (SSL) and Federated Averaging (FedAvg) in the context of heterogeneous data. The authors attribute the surprising performance of SSL over FedAvg in worst-case scenarios to the assumption of data heterogeneity (Assumption 3), which is derived from the convergence theory of SGD. The paper provides a compelling argument and empirical evidence for the counterintuitive performance of SSL over FedAvg in certain scenarios. It offers valuable insights into the role of data heterogeneity in the performance of these algorithms and highlights the need for careful consideration of data heterogeneity in the design and analysis of federated learning algorithms. However, the paper could benefit from a more detailed discussion of the implications of these findings for real-world applications. Further exploration of the conditions under which SSL outperforms FedAvg, as well as potential strategies for mitigating the limitations of FedAvg in extremely heterogeneous settings, would be valuable.", "questions": "While the paper provides a detailed convergence analysis for the newly proposed SSL algorithm, my primary concern lies in the experimental evaluation. The authors have chosen to use relatively simple and dated datasets and models, such as MNIST and CIFAR10 with LeNet and VGG-11. These models, being almost a decade old, may not accurately reflect the complexities and challenges of current practical workloads.\n\nTo strengthen the paper, I recommend that the authors extend their experimental evaluation to include larger datasets and models. This would not only provide a more rigorous test of the SSL algorithm but also enhance the relevance and applicability of the research. If such larger experimental results can be provided, I would be inclined to increase my score by one point, as it would significantly improve the paper's contribution to the field.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides a comprehensive theoretical analysis of the counterintuitive performance of Sequantial SL (SSL) over Federated Averaging (FedAvg) in certain scenarios. The author's exploration of the role of data heterogeneity and its impact on these algorithms is particularly insightful.\n\n2. The authors validate their theoretical findings with empirical experiments, which strengthens the credibility of their claims. The use of one-dimensional quadratic functions for simulation and the consideration of practical scenarios in resource-constrained edge devices add depth to their research.", "weaknesses": "1. The paper primarily focuses on the performance of Sequential SL(SSL) and Federated Averaging (FedAvg) in the context of data heterogeneity. While this focus is important, it might limit the generalizability of the findings. The performance of these algorithms could be influenced by other factors that are not considered in this paper.\n\n2. While the paper does consider practical scenarios in resource-constrained edge devices, it could benefit from a more detailed discussion of the implications of its findings for real-world applications. Understanding how these findings could be applied in practice would add significant value to the paper.\n\n3. The paper establishes that SSL outperforms FedAvg in extremely heterogeneous settings, but it doesn't dive deeply into why this is the case or how it could be mitigated. Further exploration of these areas would enhance the paper's contribution to the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This part contains 4 responses, denoted by R22-R25.\n\n##### **R22: (Q1) Extend the experimental evaluation to include larger datasets and models.**\n\nAs suggested, we have added ResNets (He et al., 2016) [Ref 7] for larger models and CINIC-10 (Darlow et al., 2020) [Ref 8] for larger datasets. The test accuracy results are given in [Tables 5, 6], and the corresponding training curve figures are given in the pdf in the global response.\n\n+ *Experiments of ResNet-18 on CIFAR-10 and CINIC-10*. CINIC-10 consists of images from both CIFAR and ImageNet, which is larger than CIFAR-10. There are 9000 images in the training set of CINIC-10, which is partitioned into 1000 clients by Extended Dirichlet Strategy. We use ResNet-18 in (Jhunjhunwala et al., 2023) [Ref 9]. For the other settings, we keep the same as the paper. Besides, we also add the experiments with ResNet-18 on CIFAR-10. The results are in the [Table 5].\n\n  [Table 5: Test accuracies (%) of FedAvg and SSL with ResNet-18 on CIFAR10 and CINIC-10. We run both algorithms for 4000 training rounds and report the averaged test accuracies over the last 100 training rounds and 3 random seeds.]\n\n  | Dataset  | Method | ExDir(1, 10.0)  | ExDir(1, 10.0)  | ExDir(1, 10.0)  | ExDir(2, 10.0)  | ExDir(2, 10.0)  | ExDir(2, 10.0)  |\n  | -------- | ------ | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- |\n  |          |        | $K=5$           | $K=20$          | $K=50$          | $K=5$           | $K=20$          | $K=50$          |\n  | CIFAR-10 | FedAvg | $53.15\\pm 4.49$ | $43.79\\pm 4.64$ | $33.53\\pm 4.91$ | $80.08\\pm 1.75$ | $82.40\\pm 1.43$ | $79.98\\pm 1.90$ |\n  | CIFAR-10 | SSL    | $82.84\\pm 2.07$ | $76.93\\pm 3.64$ | $68.90\\pm 4.59$ | $87.33\\pm 1.27$ | $85.21\\pm 2.57$ | $78.54\\pm 4.76$ |\n  | CINIC-10 | FedAvg | $40.44\\pm 4.40$ | $33.63\\pm 4.60$ | $24.59\\pm 4.22$ | $58.61\\pm 2.09$ | $56.00\\pm 1.41$ | $47.66\\pm 1.74$ |\n  | CINIC-10 | SSL    | $60.42\\pm 1.81$ | $53.20\\pm 1.78$ | $45.81\\pm 3.02$ | $64.70\\pm 1.36$ | $58.59\\pm 2.15$ | $57.58\\pm 1.90$ |\n\n+ *Experiments for ResNets with different depths and widths*. To study the effect of the model depth and width, we also conduct experiments on ResNets with different depths and widths based on ResNet-20. ResNet-20 used here is the standard model for CIFAR-10 in (He et al., 2016), which is thinner than ResNet-18 used in Jhunjhunwala et al. (2023). From [Table 6], we have the following observations: (1) Both deeper and wider models can improve the performance of FedAvg and SSL. (2) FedAvg suffers from a much heavier degradation (i.e., $\\Delta_{\\text{Acc}}$) than SSL when data heterogeneity increases to the extreme scenario (from ExDir(2, 10.0) to ExDir(1, 10.0)), especially on large models.\n\n  [Table 6: Test accuracies (%) of FedAvg and SSL for ResNets with different depths and widths on CIFAR-10. We set $K = 5$ and run both algorithms for 4000 rounds and report the averaged test accuracies over the last 100 training rounds and 3 random seeds. WRN-20-$k$ ($k$ is the width) is the abbreviation of Wide ResNet (Zagoruyko et al, 2016) [Ref 10]. We use $\\Delta_{Acc}$ to denote the difference of test accuracy between ExDir(2, 10.0) and ExDir(1, 10.0).]\n\n  | Partition      | Method | ResNet-20 | ResNet-32 | ResNet-44 | ResNet-56 | WRN-20-2 | WRN-20-4 | WRN-20-6 |\n  | -------------- | ------ | --------: | --------: | --------: | --------: | -------: | -------: | -------: |\n  | ExDir(1, 10.0) | FedAvg |   $49.16$ |   $50.31$ |   $49.74$ |   $50.46$ |  $53.58$ |  $55.13$ |  $54.93$ |\n  | ExDir(1, 10.0) | SSL    |   $69.57$ |   $71.23$ |   $71.87$ |   $70.73$ |  $76.71$ |  $81.05$ |  $82.84$ |\n  | ExDir(2, 10.0) | FedAvg |   $68.36$ |   $70.47$ |   $70.98$ |   $72.58$ |  $75.52$ |  $78.84$ |  $80.76$ |\n  | ExDir(2, 10.0) | SSL    |   $77.73$ |   $79.52$ |   $81.18$ |   $81.63$ |  $83.58$ |  $86.64$ |  $87.86$ |\n  | $\\Delta_{Acc}$ | FedAvg |   $19.20$ |   $20.16$ |   $21.24$ |   $22.12$ |  $21.94$ |  $23.71$ |  $25.83$ |\n  | $\\Delta_{Acc}$ | SSL    |    $8.16$ |    $8.29$ |    $9.31$ |   $10.90$ |  $12.90$ |   $5.59$ |   $5.02$ |\n\n---\n\n##### **R23: (W1) The generalizability might be limited.**\n\nThanks for the insightful suggestions. The main contribution of this work is the convergence guarantee and other findings are served to support it. For this reason, we fix some settings and primarily study the performance comparison of FedAvg and SSL in the context of data heterogeneity. However, as pointed out, their performance can be influenced by other factors. We leave this for future work.\n\n---\n\n##### **R24: (W2) The implications of the paper's findings for real-world applications.**\n\nAs suggested, we would add a more detailed discussion about the implications of the findings. Here we provide some implications as 1) Broadening the choices of algorithms, 2) Hyperparameter selection, and 3) Inspiring practical and theoretical advancements.\n\n---\n\n##### **R25: (W3) It doesn't dive deeply into why this is the case or how it could be mitigated.**\n\n+ *About why this is the case*. In this work, (1) First, we derive the convergence guarantee of SSL, which is better than that of FedAvg. This means that SSL outperforms FedAvg at least in the worst case. (2) Then, we note that the upper bounds of FedAvg in existing work underestimate the performance of FedAvg. This means that FedAvg performs better than the upper bound in many practical settings. (3) For these two reasons, with the experiments, we find that SSL outperforms FedAvg in extremely heterogeneous settings.\n\n+ *How it could be mitigated*. We agree that this is still one weakness of this work. At the same time, we think this could be our future work."}]

Author rebuttal:
##### **R1: There is no explicit explanation of "Split" Learning (or split computing).**

***Clarification for no explicit explanation of Split Learning***. We would like to clarify that, due to the page limitation, we only state the basic model update rule of Sequential Split Learning (SSL) in Algorithm 1 of the Introduction. Nevertheless, Algorithm 1 has carried all the information for the convergence analysis of SSL in this paper. The complete training process (with operation details) of SSL is shown in Appendix D. In particular, Algorithm 3 and 4 (in Appendix D) are the detailed version of Algorithm 1.

***Introduction on the complete training processes of SSL and SFL***. To address the reviewers' concerns, we also briefly introduce the complete training processes of two typical Split Leaning (SL) algorithms. SL is proposed to address the computation bottleneck of resource-constrained devices, where the full model is split into two parts: the *client-side model* (front-part) and the *server-side model* (back-part). There are two typical algorithms in SL, i.e., Sequential Split Learning (SSL) and Split Federated Learning (SFL). In this work, we consider the first version of SFL, known as SFLV1. Complete training processes of SSL and SFLV1 are as follows:

+ SSL: Each client keeps one client-side model and the server keeps one server-side model. Thus, each client and the server can collaborate to complete the *local training* of a full model (on the local data kept in clients). The local training operations of each client include: 1) the client executes the forward pass on the local data, and sends the activations of the cut-layer (called the smashed data) and labels to the server; 2) the server executes the forward pass with the received smashed data and computes the loss; 3) the server executes the backward pass and send the gradients of the smashed data to the client; 4) the client executes the backward pass with the received gradients. After finishing the local training, the client sends the updated parameters of its client-side model to the next client. This process continues until all clients complete their local training.
+ SFLV1: Each client keeps one client-side model and the server keeps (named as *main server*) keeps multiple server-side models, whose quantity is the same as the number of clients. Thus, each client and its corresponding server-side model in the main server can complete the local training of a full model in parallel. The local training operations of any client in SFLV1 are identical to that in SSL. After the local training with the server, clients send the updated parameters to the fed server, one server introduced in SFLV1 to achieve the aggregation of client-side models. The fed server aggregates the received parameters and sends the aggregated (averaged) parameters to the clients. The main server also aggregates the parameters of server-side models it kept and updates them accordingly.

***Relationship between SFLV1 and FedAvg***. According to the complete training process of SFLV1, we can conclude the relationship between SFLV1 and FedAvg as follows:

+ SFLV1 shares the same update rule with FedAvg (Algorithm 2);
+ SFLV1 can be viewed as the practical implementation of FedAvg in the context of Split Learning (i.e., partitioning the full model into the client-side and server-side portions).

---

##### Some notes

+ We use "R" to represent the response, W to represent the weakness, Q to represent the question;
+ We use "[Table]" to represent the table and "[Ref]" to represent the reference appearing in the rebuttal response.

##### References appearing in the rebuttal

[Ref 1] Yun, C., Rajput, S., & Sra, S. (2021, October). Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond. In *International Conference on Learning Representations*.

[Ref 2] Wang, J., Das, R., Joshi, G., Kale, S., Xu, Z., & Zhang, T. (2022). On the unreasonable effectiveness of federated averaging with heterogeneous data. *arXiv preprint arXiv:2206.04723*.

[Ref 3] Thapa, C., Arachchige, P. C. M., Camtepe, S., & Sun, L. (2022, June). Splitfed: When federated learning meets split learning. In *Proceedings of the AAAI Conference on Artificial Intelligence* (Vol. 36, No. 8, pp. 8485-8493).

[Ref 4] Gao Y, Kim M, Thapa C, et al. Evaluation and optimization of distributed machine learning techniques for internet of things[J]. IEEE Transactions on Computers, 2021, 71(10): 2538-2552.

[Ref 5] Mishchenko, K., Khaled, A., & Richtárik, P. (2020). Random reshuffling: Simple analysis with vast improvements. *Advances in Neural Information Processing Systems*, *33*, 17309-17320.

[Ref 6] Safran, I., & Shamir, O. (2020, July). How good is SGD with random shuffling?. In *Conference on Learning Theory* (pp. 3250-3284). PMLR.

[Ref 7] He, K., Zhang, X., Ren, S., & Sun, J. (2016). Deep residual learning for image recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition* (pp. 770-778).

[Ref 8] Darlow, L. N., Crowley, E. J., Antoniou, A., & Storkey, A. J. (2018). Cinic-10 is not imagenet or cifar-10. *arXiv preprint arXiv:1810.03505*.

[Ref 9] Jhunjhunwala, D., Wang, S., & Joshi, G. (2022, September). FedExP: Speeding Up Federated Averaging via Extrapolation. In *The Eleventh International Conference on Learning Representations*.

[Ref 10] Zagoruyko, S., & Komodakis, N. (2016). Wide residual networks. *arXiv preprint arXiv:1605.07146*.

Meta-review: The paper analyses sequential versions of federated learning in the realistic heterogeneous data case. This is a very relevant and timely research topic. Reviewers all agree that the contributions are valuable in this setting. 

However it remained unclear what the results have to do with the split learning aspect, a particular kind of model parallelism where the server and clients hold different blocks of layers of the model.
The provided results seem to apply in the more general setting of standard learning as well, but it should be clarified what aspects of the analysis are general, as opposed to specific to the split learning setting.
We think this does not diminish the results of the paper but rather could strengthen and generalize them if explained better (even potentially changing the title). 

To improve this, please in the paper clearly formalize the results and implications (and novelty) in both settings: 
1) the more specialized case of split learning and 
2) the more broadly interesting case of general sequential learning.

We hope the detailed feedback can help to clarify the camera-ready version of the paper.
Decision: Accept (poster)