Convergence Analysis of Split Learning on Non-IID Data
Authors: Yipeng Li
Xinchen Lyu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Split Leanring
Convergence analysis

Abstract: Split Learning (SL) is one promising variant of Federated Learning (FL), where the AI model is split and trained at the clients and the server collaboratively. By offloading the computation-intensive portions to the server, SL enables efficient model training on resource-constrained clients. Despite its booming applications, SL still lacks rigorous convergence analysis on non-IID data, which is critical for hyperparameter selection. In this paper, we first prove that SL exhibits an $\mathcal{O}(1/\sqrt{T})$ convergence rate for non-convex objectives on non-IID data, where $T$ is the number of total steps. By comparing the convergence analysis and experimental results, SL can outperform FL in terms of convergence rate (w.r.t. per-client training/communication rounds, and hence, the computation efficiency) and exhibit comparable accuracy to FL on mildly non-IID data. In contrast, FL prevails on highly non-IID data.

Under review as a conference paper at ICLR 2023
CONVERGENCE ANALYSIS OF SPLIT LEARNING ON NON-IID DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Split Learning (SL) is one promising variant of Federated Learning (FL), where the Al model is split and trained at the clients and the server collaboratively. By offloading the computation-intensiv portions to the server, SL enables efficient model training on resource-constraine clients. Despite its booming applications, SL still lacks rigorous convergence analysis on non-IlI data, which critical for hyperparameter selection. In this paper, we first prove that SL exhibits an ((IVVT) convergence rate for non-convex objectives on non-IID data, where I is the number of total iterations. The derived convergence results can facilitate understanding the effect of some crucial factors in SL (e.g.. data heterogeneity and local update steps). Comparing with the convergence result of FL, we show that the guarantee of SL is worse than FL in terms of training rounds on non-IID data. The experimental results verify our theory. Some generalized conclusions the comparison between FL and SL in cross-device settings also reported.
INTRODUCTION
Federating Learning (FL) is a popular distributed learning paradigm where multiple clients collab- orate to train global model under the orchestration of one central server. There two settings in Federating Learning (FL) (McMahan et al., 2017) including (i) cross-silo where clients are orga- nizations and the client number is typically less than 100 and (ii) cross-device where clients are lot devices and the client number can be up to 1000 (Kairouz et al., 2021). To alleviate the computa- tion bottleneck resource-constrained IoT devices in the cross-device scenario. Split Learning (SL) (Gupta & Raskar, 2018; Vepakomma et al., 2018) splits the Al model to be trained at the clients and server separately. The computation-intensin portions are typically offloaded the server, which critical for the model training at eesource-constraing devices. SL is regarded as one of the enabling technologies for edge intelligence in future networks (Zhou et al., 2019).
The comparisons of FL and SL. are of practical interest for the design and deployment of intelligent networks. Existing studies focus various aspects for their comparisons (Thapa et al., 2020; Gao et al., 2020; 2021), c.g., in terms of learn- ing performance (Gupta & Raskar, 2018), computation effi- ciency (Vepakomma et al., 2018), communication overhead (Singh et al., 2019), and privacy issues (Thapa et al., 2021). For example, with the emphasis on the learning performance comparison, Gao al. (2020; 2021) find that SL exhibits (i) faster convergence speed than FL under IID data in terms of communication rounds; (ii) better learning performance un- der imbalanced data: (iii) worse learning performance under (extreme) non-lll) data, etc. The difference arises from the distinct process of model updates of FL. and SL. In particular, FL takes the average of the local model parameters at the end of each round; SL only trains the clients in sequence and does not average the client updates. Fig- ure plots the client drift (Karimireddy et al., 2020; Wang et al., 2020; Li et al., 2022) of FL and SL under both IID and non-III IID data to visualize the update process. Under the IID setting, SL approach the global optima x" faster than FL given the sequential training mechanism. In contrast, under the non-IIID setting, SL. may deviate from the global optima for the same reason.
IID
Non-IID
FL
SL
global model
local oytima
global cptima
Figure I: Illustration of the model updates of FL and SL for 2 clients and local update steps during one round.

---

Under review as a conference paper at ICLR 2023
Convergence analysis is critical for the performance comparison between SL and FL. Specifically, a rigorous analysis is of paramount importance for the vital research questions raised by (Gao et al., 2020) (which are only empirically evaluated but remain unsolved in theory): RQi-"What factors affect SI. performance?" and RQ2-"/n which setting will the SI. performance outperform F1.?". A wealth of work has analyzed the convergence of FL. in the cases of III (Stich, 2018; Zhou & Cong, 2017; Khaled et al., 2020), non-llD (Li et al., 2020; 2019; Khaled et al., 2020; Karimireddy al., 2020) and unbalanced data (Wang et al., 2020). However, with the distinct update process, the convergence analysis of SL has yet to be solved on non-llI data. To this end, this paper first derives a rigorous convergence results of SL and draw the comparison results of FL and SL theoretically.
Main contributions. The main contributions can be summarized with respect to the two research questions above:
We prove the convergence of SL on non-lID data with the standard assumptions used in FL liter- ature I with convergence rate of ((1/vT) in Section 4.2. By this, we find that the convergence of SL is affected by factors such data heterogeneity and the number of local update steps. Experimental results verify the analysis results empirically in Section 5.2. To the best of our knowledge, this work is the first to give the convergence analysis of SL on non-IID data.
We compare 2 and SL in theory (Section 4.3) and in practice (Section 5.3). Theoretically, the guarantee of SL is worse than FL in terms of training rounds on non-IID data. Empirically, we provide some generalized conclusions of FL and SL in cross-device settings, including (i) the best and threshold learning rate SL is smaller than FL; (ii) the performance of SL is worse than FL when the number of local update steps is large highly non-llI data; (iii) the performance of SL can be better than FL when choosing small the number of local update steps is small on highly non- -ID data.
2 PRELIMINARIES AND ALGORITHM OF SPLIT LEARNING
As two of the most popular distributed learning frameworks, both FL and SL aim to train the global model from distributed datasets. The optimization problem of FL and SL with N clients can be given by
f(x) Pp.lit)) }
min xER
(I)
where p; = nn/nnin is the ratio of local samples at client (n and n, are the sizes of the overall dataset D and local dataset D, at client respectively). x is the model parameters, f(x) is the global objective, fx) denotes the local objective function on client i. In particular, [x) := EE (x: = EgEE,, f((x; {s), where &, represents a data sample from the local dataset D..
SL with the global learning rate. The relay-based (sequential) training process across clients makes SL significantly different (from FL), which has been described in Algorithm 1. Considering the massive number of clients cross-device setting, only a subset of clients are selected for model training at each round. The update order of the selected clients can be meticulously designed or randomly determined (used in this paper). The i-th client requests and initializes with the lasted model (step 4) and then performs multiple local updates (step 5-11)². After K local updates, the client will send the model parameters to the next client (i.e., the + 1-th client). The local update
'We only show the convergence for non-convex objective functions here since SL is now often used in large deep learning models whose objective functions are possibly non-convex. Nevertheless, similar methods can he used to get the convergence for general convex functions and strongly convex functions.
FFecAvg is used for comparison in this work.
'The client and the server cooperate to conduct the local updates. Note that in SL, though the model update requires communication between the client and server, the model is still trained on the local dataset. So the process is called local update (Thapa et al., 2020). The concatenation of the client-side and server-side models after each local update is called local model.
2

---

Under review as a conference paper at ICLR 2023
process can be stated as:
x(r10)
x (r.)
Initialize:
(2)
x
1
Update:
x
(nx+1)
(nk)
mig (x (111))
(3)
where x! ((1AA) denotes the complete local model (parameters) after the k-th local update on the local dataset D; in the r-th round, ?p is the local learning rate and g: ((x((r=)) Vi(xx (r.k), ,f rep-
resents the stochastic gradients over on the mini-bated ((r.)) sampled randomly from D,. Note that the complete model x; (r.8) consists of the client-side model (tr.k) and server-side model (r.k) s. as shown in Algorithm 1. The clients and server update their models synchronously and without loss
of generality, we do not highlight the model locations the following.
After the last client in S (i.e., the [S|-th client) completes its local updates, it will request the initial client-side model of the current round. The global update is conducted in both the client and server:
x" + 7g (x(s))
(r.K) x"):
(4)
where x" denotes the complete global model (parameters) in the r-th round (x" equals x; (r,0) only when i 1. which different from FL), Fl is the global learning rate. Note in Eq. (4) that we propose adding the global learning rate ny against the vanilla SL algorithm (Gupta & Raskar, 2018; Vepakomma al., 2018; Thapa et al., 2020; 2021). The global learning rate design mechanism is originally developed in the FL setting (Karimireddy et al., 2020; Reddi et al., 2020; Wang et al., 2020) to reduce the client drift, and can be readily adopted in SL the same function. Algorithm can operate in both the centralized and peer-to-peer mode (see Appendix A) and is reduced to the vanilla SL if steps 13-14 removed. For brevity, we have omitted some unconcerned details of SL in Algorithm 1, e.g., the security and privacy settings. More details about SL can be found in Appendix A or Gupta Raskar (2018); Thapa et al. (2021).
Algorithm Split Learning with the Global Learning Rate
Some notations:
X. denotes the client-side model (parameters)
x, denotes the server-side model (parameters)
== [x,, x,] denotes the complete model (parameters) 1: for round r = O...., R do
2: Sample a subset of clients and determine their update order
3: for client index i I,..., |S| do
4:
Client i: Request the latest client-side model and initialize x X
(r:0)
x =
(r.))
5:
for local update step t: ...... K do
6:
Client i: Forward propagation and send activations to the server Server: Forward propagation with activations from the client
7:
8:
Server: Brok-propag and send gradients to the client
9:
Client Back- proppaarpaggtoon with gradients from the server
Client é: (r,k+1) x (r.k)
(r.A)
mig (x
10:
Local model updates:
Server: x
(r.+1) + (r.k)
mB. (x (r.k)
11:
end for
end for
13:
Client [S]: Request the initial client-side model x" of the current round
Client |S]:
x x" + 7o (x 1.
(r.K)
x()
14:
Global model updates:
Server:
x
x + 7o (x (r,K)
x()
15: Client |S] and Server: Store the global model
end for
3

---

Under review as a conference paper at ICLR 2023
3 RELATED WORK
Variants of SL. SL is deemed as promising paradigm for distributed model training at resource- constrained devices, given its computational efficiency on the client side. Most existing works focus on reducing the training delay arising from the relay-based training manner in the multi-user sce- nario. SplitFed (Thapa et al., 2020) is one popular model parallel algorithm that combines the strengths of FL and SL, where each client has one corresponding instance of server-side model in the main server to form a pair. Each pair constitutes a complete model and conducts the local update in parallel. After each training round, the fed server collects and aggregates updates. The aggregated client-side model will be disseminated to all the clients before next round. The main server does the same operations the instances of the server-side model. Sp1 i Ftvevv2 (Thapa et al., 2020), SplitFedy (Gawali et al., 2021) and SFLG (Gao et al., 2021), FedSeç particular, SFLG (Gao al., 2021) is one
the clien-side local
Zaccone al., 2022) are the variants of SplitFedt generalized variants of Split combining Splits splitFed and SplitFedv2.
Convergence analysis of SL. In the case of IID data, the convergence analysis of SL is identical to standard Minibatch-SGI (Wang et al., 2022; Park et al., 2021), so some convergence properties of Minibatch SGD is applied SL too. The algorithm in Han et (2021) reduces the latency and downlink communication SplitFed by adding auxiliary networks at client-side for quick model updates. Their convergence analysis combines the analysis Belilovsky et al. (2020) and FedAvg. Wang et al. (2022) proposed FedLite to reduce the uplink communication overhead by compressing activations with product quantization and provided the convergence analysis of FedLite. However, their convergence recovers that of Minibatch SGD when there is quan- tization. SGD with biased gradients (Ajalloeian & Stich, 2020) also related. However, it only converges neighborhood of the solution. Furthermore, compared the convergence of distributed Minibatch SGD and local SGD under homogeneous and heterogeneous settings, respectively. To differentiate our work, we show how these algorithms op- erate in Appendix B. As a result, the convergence of SL on non-lID data is still lacking.
find that Woodworth et al. (2020a;b)
CONVERGENCE ANALYSIS OF SL
4.1 ASSUMPTIONS
We make the following standard assumptions on the local objective functions {
Assumption 1 (I-smooth). Each local objective functiio is L-smooth, i E (,, N), i.e. there exists constant L > 0 such that fx(( - f(())) < L|x for all x and y.
Assumption (Unbiased gradient and bounded variance). For each client i, E 21, N), the stochastic gradient g: (x) = V (x) is unbiased (x)] = f.((()) and has bounded variance Ee, Beg V (x) o².
Assumption 3 (Bounded dissimilarity). There exist constants 2 and G 2 0 such that 1 >E fxx)]] < B² f[) G?. In the IID case, B = and G = 0, since all the local objective functions are identical each other. In the non-IID case, B and G measure the heterogeneity of data distribution.
N
4.2 CONVERGENCE RESULT AND DISCUSSION
Without loss of generality, all the clients participate in the SL process ([S) = NN and the unweighted global objective function f(x) = Σ fx(x is adopted. Note that the results in the unweighted case can be readily extended the weighted case of Eq. (1). Following the proof of Wang et al. (2020); Karimireddy et al. (2020); Khaled et al. (2020), we give the convergence results of SL. (details are in Appendix D), as follows:
4

---

Under review as a conference paper at ICLR 2023
Theorem 1. Let Assumptions 2 and 3 hold. Suppose that the local learning rate satisfies my 1
ENKL min- V282-1 }. For Algorithm 1, it holds that
|[)) 4[5(x") [(x))) 12N2 + 66N 6N R
4NngmLo (5)
Tazellent drift enor
To Te:global variance
Ti I'diniiializaiion error
where x 2r= x" is the averaged global model over the R rounds.
Corollary 1. Choose 1l
- and apply the result of Theorem 1. For sufficiently large T
LVT
(T' 2 42 max
21 13). it holds that
( (
[(x))] VT
N2 N N
O
O
(6)
TTT
Ti Vxiiiitializaion error
Tapelient drift error
Ts:global variance
where T is the total number of iterations (i.e., N NKR.R. in SL).
The upper bound of [I[] [[x))( consists of three types of terms: (i) initialization error, (ii) client drift error, caused by the client drift (see Lemma 4 in Appendix D.2), (iii) global variance. We can see that the result demonstrates the relationships between convergence and factors such as the number of clients, the data heterogeneity, the global/local learning rates and the local update steps. According to the result, a large T/I means higher rate that the initialization error decreases at but causes large client drift error and global variance. Next, discuss the convergence rate and the influence factors of SL in detail.
Convergence rate. By Corollary 1, for sufficiently large T. the convergence rate is determined by the initialization error and global variance (see Eq. (6)), resulting in convergence rate of O1I/TT). SGD (Bottou et al., 2018; Wang et al., 2020) when N = 1 and K (i.e., without the client drift error) It is but not shown in Theorem directly, since is complicated to write the constant details in Eq. (5). We defer the discussion to Appendix D.5.
We can recover the convergence
Effect of data heterogeneity. According Theorem 1, when highly non-lII data (B and G are large), a small n is required for the convergence of SL (see the condition of Theorem 1). In addition, the client drift error also increases. As result, large data heterogeneity harms the convergence of SL, which is consistent with the previous study (Gao et al., 2020; 2021).
Effect of K. K is the number of local update steps. An immediate question whether we can improve the convergence by adding local update steps when R is fixed. The answer is yes. By Eq. (5), K increases, the initialization error decreases and the client drift error increases, which implies that the optimal K exists. We can further get that larger data heterogeneity makes the optimal K smaller based on Eq. (5). This property analogous FL (McMahan al., 2017).
Effect of 7g. The global learning rate 7l can be used to reduce the client drift without hurting the progress SL. A large T/ reduces the client drift error, hence improving the convergence rate. For example, by Corollary 1, SL shows O LF+a" X² (F = f(x") f(x*)) )); while it shows convergence rate of O LF+02 + K²Ga K²G=Koo² if fg = N.
convergence rate if 1/g
VT
VT
Some detailed analysis of these factors are deferred to Section 5.2, combined with the experiments.
4.3 COMPARISON BETWEEN FL AND SL
In this section, we first give the convergence result FL based on our setting, and then compare the results of FL and SL to answer the second question "In which setting will the SL performance outperform FL?" theoretically.
We summarize the convergence results of FL ((Wang al., 2020), reproduced by Theorem 2 in Appendix D.3) and SL (Theorem 1) in Table 1. The convergence guarantee of FL one of the best known convergence results for the non-convex functions of FI., which makes comparison
5

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of convergence results between FL (Wang et al., 2020) and SL (Theorem 1) for non-convex functions. The convergence guarantee of FL is given in the 1-st (upper bound) and 2-th (constraints on ?7)) rows. The effective learning rate versions are shown in the 3-rd (FL) and 5-th (SL) row. The number of rounds required to reach accuracy is given in the 4-th (FL) and 6-th
(SL) rows. == ʃ(x") [(x*). Constants (including L) are omitted. fl is set to f1g 1.
F MKR
+ Oni + +n Ko²) + O
N
FL
Constraint:
S 2KT,
min V282411* no
1
(Wang et al., 2020)
ÍAL: 0
O
ip. G2
O
1n NK
1R
R2 = O
F2
eT
+
NK
1²
+
KG
Ke
SL
Ma R
+
i
G2
+
ne a=
K
K
R. 0
F2
2
+
o+ R2
KG to²
Ke
persuasive. Choosing nn linear speedup in FL.
for Theorem 2 provides the OLIVVNT) convergence rate, the LVT
/N
The constraint on the local learning rate of SL is tougher than FL. The local learning rate of SL (see Theorem 1) has tougher constraints than FL (see the 2-nd row of Table 1), which indicates SL is more sensitive to the heterogeneity of data. This is significant for the selection of the learning rate of SL in practice (see the comparison experiments).
Effective learning rate, We next focus on comparing FL and SL in terms of rounds. Note that this comparison (running for the same R) is fair given the same total computation cost (including the computation cost on client-side and server-side). Beginning with the observation that the con- vergence guarantees and constraints seem very alike if choosing (RL))) = /R(F)/ - (FL) and M[ss)) denote the local learning rate of FL and SL respectively, we define the effective learning rate Ti.. Klg for FL and fjsı. = N "nn for SL Karimireddy al. (2020); Wang et al. (2020) did. Note that the effective learning rate is unequal for FL and SL. As a result, we obtain the convergence guarantee of the effective learning rate version exhibited the 3-rd and 5-th rows in Table 1.
The guarantee of SL is worse than FL in terms of training rounds on non-lID data. To make a comparison, we need to choose appropriate for both. Considering 7e. and Íjsı has the same constraints, we can choose MEL
= 1/ R for both bounds (see the 3-rd and 5-th rows in Ta- a²
ble 1). Then we get: (i) O
F
+
KG
+0² + NKVR) FL and (ii) O (F + KG to² + KVR VR
x²
VR
KR
KR
of SL after A rounds, i.e., the round complexity R. shown in 4-th and 6-th rows in Table 1. Then for sufficiently large R, R, is determined by the first and the second term (see the 4-th and 6-th rows). In particular, the only difference the complexity appears in the second term (we have marked it with red), which indicates that the guarantee of SL is worse than FL in terms of rounds. However, we note that the gap is not obvious when K or small. Further, considering the constants advantage of SL (It is true but not shown in Theorem 1, see Appendix D.2), the performance comparison between FL and SL is still uncertain. To make a more detailed comparison, we have conducted adequate experiments and given some generalized conclusions in Section 5.3.
5 EXPERIMENTS
Our experiment environment is ideal (without the communication and computation restrictions), nevertheless, is enough to examine our convergence theory. The convergence rate evaluated in terms of the training rounds. We demonstrate the detailed experimental setup in Section 5.1, evaluate

---

Under review as a conference paper at ICLR 2023
the effect of the factors on the performance of SL in Section 5.2, and compare FL and SL in cross- device settings in Section 5.3. More experimental details are in Appendix E.
5.1 EXPERIMENTAL. SETUP
Datasets and models. We adopt the following setups: (i) training LeNet-5 (LeCun al., 1998) on the MNIST dataset (LeCun et al., 1998); (ii) training LeNet-5 on the Fashion-MNISTT dataset (Xiao et al., 2017); (iii) training VGG-11 (Simonyan & Zisserman, 2014) the CIFAR-IO dataset (Krizhevsky et al., 2009). For SL, the LeNet-5 is split after the second 2D MaxPool layer, with 6% of the entire model size retained in the client; the VGG-11 is split after the third 2D MaxPool layer, with 10% of the entire model size at the client. Ideally, the split layer position has no effect on the performance of SL (Wang et al., 2022).
Data distribution. Both IID and non-III datasets are considered in the experiments, For the non- IID setting, we adopt two mechanisms generate non-IID data: (i) using Dirichlet distribution Dir(a:) to generate mildly non-IlI data, where a smaller indicates higher data heterogeneity (Hsu al., 2019; Zhu et al., 2021); (ii) using a similar mechanism like (McMahan et al., 2017; Zhao et al., 2018) () to generate the pathological non-llD data, e.g.. one distribution in which most clients only contain samples from 2 (5) classes, denoted as
2 (5). Note that the data distribution generated by the first mechanism is unbalanced and the second is balanced. We will use "a #" and "C" #" to represent the different data distributions in the following, where # is the parameter.
5.2 EXPERIMENTAL RESULTS OF SL
2.25
SUIDI
5Lie=1.0) E-1
50
36.
446
114
114
114
2.00
SUC-
2.0
Stlem1.0) 6m
8 40-
34.
33.4
1.50
SUC
Teain Losa
1.5
SLla=1 () E=
SLie-1.0
2.0
46.4
12.
81
118
334
-6
225
6.79
14.
114
0.50
0.0
40.1
33.4
22
25
30
12
20
32
Rounds
Learning
(0g
(a) Effect of data heterogeneity
(b) Effect of
(c) Effect of ml
Figure 2: Results of SL on MNIST dataset.
In this section, we study the effects of data heterogeneity local update steps using the MNIST dataset. The training samples are assigned to 10 clients. For data heterogeneity, we use four distributions: IID, C = 8, 5, 2. For K, we use five settings, E = 1, 2, 4, 8, 10 over Dir (1.0) distribution. E is the local epochs (McMahan al., 2017), which satisfies K max En;/b), /b}, where is the mini-batch size. So E can measure the value of K with n, and b fixed. The results on MaSHIon-MNIST and CIFAR-10 are deferred Appendix E.
Effeet of data heterogeneity. As shown in Figure 2a, the training loss curve of IID distribution the lowest and most stable. When the data heterogeneity increases (C' decreases from 2), SL shows worse performance. The phenomenon is in accordance with our analysis that large data heterogeneity harms the convergence of SL in Section 4.2.
Effeet of K. Figure 2b shows the training loss in terms of communication rounds R. SL shows the best performance when E 2. This verifies that optimal K exists and suitable K can improve the convergence. Over-large K can even harm the convergence rate (see curves F = 8 and F = 10).
Effect of 1g- The effect of my in FL has been empirically studied in Reddi et (2020). They tune Yi and y by grid search. We follow similar method to study fy of SL. by choosing different combinations of πy and T). As shown in Figure 2c, the dark green grids with high test accuracy concentrate on the left bottom triangular regions, which shows that Tly should avoid being too large. Also note that 77 cannot be set infinitely too large and has a limited range, which is also observed in FL (Reddi et al., 2020). Thus tuning 7g in the limited range is suggested. Besides, find that 7, can be introduced to other SL frameworks, like SplitFed. However, further research on fy needed address the issues such how to lane fl gain improvement? ? in FL and SI..
7

---

Under review as a conference paper at ICLR 2023
5.3 EMPIRICAL COMPARISON BETWEEN FL AND SL
We have compared FL and SL theoretically in Section 4.2. The question arises that how about the learning performance of SL in practice compared to FL? In the previous work, the same learning rates used to evaluate the performances of SL and FL (Gao et al., 2020; 2021). However, theo- retical analyses in Section 4.2 show that the appropriate learning rate for SL may deviate from that of FI.. Thus, we evaluate the performance of SL. and FL with different learning rates for fair com- parison. The learning rates are selected from {0.0005, 0.001, 0.005, 0.01, 0.05, 0.13. To evaluate the effect of K on the performance comparison of FL and SL, we adopt two settings: E 1 and E = 10. We run 1000 rounds of training on MNIST, Fashion-MNIST and 4000 rounds on CIFAR- 10 dataset when E = 1; run 100 rounds of training on MNIST, Reshion-MNIST and 400 rounds on CIFAR-10 10 dataset when E = 10. The average top-1 test accuracy over the last 10% rounds are shown in Table 2, e.g., the average accuracy over the last 400 rounds of the total 4000 rounds on CIFAR-10 when E =
Cross-device setting. We compare the performance of FI. and SI. in cross-device settings, where the client number is enormous and the local dataset size is small. Specifically, (i) MNIST: the training data is split into 1000 clients; (ii) FaShion-MNIST: the training data is split into 1000 clients; (iii) CIFAR-10 10: the training data is split into 500 clients. The number of samples per client depends on the data distribution, e.g., 60 (MNIST), 60 PrashionMMNSS" and 100 (CIFAR- 10) samples per client in the second partition mechanism. The mini-batch size is 10 for all setups under the consideration of low computation power of IoT devices. The original test sets are used to evaluate the generalization performance of the global model (test accuracy) after each training round.
The best and threshold learning rate of SL. is smaller than FL. We refer to the learning rate mak- ing the best test accuracy and minimal learning rate making the training die as the best learning rate and the threshold learning rate. According to our theory, the tougher constraint indicates the smaller threshold learning rate of SL and the math property of Eq. (5) indicates smaller best learning rate. To verify this point, we use the "best" learning rate, which makes the "best" test accuracy among the learning rates we choose, to substitute the actual best learning rate. The "threshold" learning rate is defined alike. As shown in Table 2, the "best" and "threshold" learning rates of SL are smaller than FI., especially on highly non-III) data (e.g., a = 0.2). Furthermore, we note that the "best" and "threshold" learning rate turn small the heterogeneity of data becomes large, which is also in accordance with our theory.
Performance comparison on IID data. SL can obtain faster convergence rate with comparable or even higher test accuracy than FL (see the left plot in Figure 3 and Table 2). This is identical to the conclusion in Gao et al. (2020; 2021).
Performance comparison on non-IID data, Our theory proves that the guarantee of SL is worse than FI. in terms of rounds when K is large. As shown in Table 2, almost all the "best" test accuracy of FL on very highly non-IlI) data (i.e., a = 0.2 and C = 2) beats that of SL when F = 10. When E (K) is large, FL converges faster than SL too (see the middle plot in Figure 3). However, we find that SL has a better performance than FL when E (K) is small (see the E = 1 column in Table 2 and the right plot in Figure 3). Even in some cases (a 0.5 and C 5 on CIFAR-10) when E 10, SL is better.
CIFAR 10)
OIFAR 10 (E=
CIFAR
80
Top-1 Test ALouracc/15
02
20
50
30
PLEM 022
511a
(.2)
Slie- 0.2)
FL(11D)
SUIID
FLIC -
SL0C - 2)
FLGC-22) 20
SUC -2)
200
1500 20to
3003
3000 4000
Rounds
Rounds
Rounds
Figure 3: Top-1 test accuracy of FL and SL on non-III data in terms of rounds. We illustrate some results of CIFAR-10 from Table 2.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Performance comparison between FL and SL in cross-device settings. The "best" test accuracy (%) is in the "Best" accuracy (Ir) column (the "best" learning rate is in the parenthesis) and the "threshold" learning rate in the "Threshold" Ir column. Note that ># means that the "threshold" learning rate is larger than The higher "best" accuracy between and SL is marked bold (excluding the results whose difference is within 1%).
E
Dataset
Distribution
"Rest" accuracy (Ir)
"Threshold""
"Resl" accuracy (Ir)
"Threshold""
FL
SL
FL
SL
FL
SL
FL
SL
IID
99.0 (0.05)
98.9 (0.005)
0.1
0.05
97.9 (0.01)
97.6 (0.005)
0.1
0.05
D
99.1 (0.05)
98.9 (0.01)
> 0.1
98.0 (0.01)
97.8 (0.001)
0.05
0.01
0.5
98.9 (0.05)
98.8 (0.005)
> 0.1
0.05
97.9 (0.01)
97.9 (0.001)
0.05
0.005
MNIST
(0.05)
98.8 (0.005)
96.8 (0.01)
96.8 (0.001)
0.05
0.01
5
(0.05)
98.9 (0.005)
0.1
98.0 (0.01)
98.0 (0.001)
0.01
C 2
98.8 (0.05)
99.0 (0.01)
> 0.1
0.05
96.8 (0.005)
97.1 (0.001)
0.05
0.005
IID
88.1 (0.05)
88.4 (0.005)
0.1
0.1
85.0 (0.01)
84.0 (0.000))
0.1
0.05
(0.05)
(0.0005)
0.05
0.5
86.7 (0.05)
87.6 (0.005)
> 0.1
0.1
83.8 (0.01)
79.2 (0.001)
0.05
0.01
Fashion- MNIST
0.2
83,5 (0.01)
85,9 (0,005)
0.1
0.05
80.4 (0.01)
79.0 (0.0005)
0.05
0.01
(0.05)
(0.01)
(0.01)
80.1 (0.001)
0.05
12
C 2
83.0 (0.1)
87.3 (0.005)
> 0.1
0.05
75.9 (0.01)
72.3 (0.001)
0.1
0.005
13
IID
86.4 (0.05)
87.0 (0.005)
0.1
0.05
77.7 (0.01)
83.7 (0.001)
0.05
0.01
5.0
(0.05)
87.0 (0.005)
77.6 (0.005)
82.7 (0.001)
0.05
0.005
a 0.5
84.1 (0.01)
85.5 (0.005)
0.05
0.01
71.8 (0.01)
76,9 (0.001)
0.05
0.005
16
CIFAR-10
0.2
80.5 (0.01)
83.5 (0.001)
0.05
0.01
66.9 (0.01)
65.0 (0.0005)
0.05
0.001
C 5
(0.05)
86.5 (0.005)
74.2 (0.01)
78.9 (0.001)
0.05
0.005
2
80.0 (0.05)
84.7 (0.005)
0.05
61.6 (0.01)
58.7 (0.0005)
0.05
0.001
CONCLUSION
In this work, we first derived the convergence guarantee of SL for non-convex objectives non- IID data. The results reveal that the convergence of SL is affected by the factors such as data heterogeneity and local update steps. Furthermore, empirically, ending with the conclusions that (i) the best and threshold learning rate of SL is smaller than FL; (ii) the performance of SL is worse than FL when the number of local update steps is large on highly non-IID data; (iii) the performance of SL can be better than FL when the number of local update steps small on highly mon-IID data. Our work can bridge the gap between FL and SL, provide deep understanding of these two approaches and guide the deployment of these two in real-world applications.
compare SL against FL theoretically and
REFERENCES
Ahmad Ajalloeian and Sebastian U Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008.00m) 2020.
Anonymous. Fedexp: Speeding up federated averaging via extrapolation. In Submitted to The Eleventh International Conference on Learning Representations, 2023. URL https: under review.
//openzeview nwt/ test://orumnid-IPPaabbbbe
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Decoupled greedy learning of CNNs. In International Conference on Machine Learning, pp. 736-745. PMLR, 2020.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, (0(2):223-311 2018.
Qiang Duan, Shijing Hu, Ruijun Deng, and Zhihui Lu. Combined federated and split learning in edge computing for ubiquitous intelligence internet of things: State-of-the-att and future directions. Sensors, 22(16))5983, 2022.

---

Under review as a conference paper at ICLR 2023
Yansong Gao, Minki Kim, Sharif Abuadbba, Yeonjae Kim, Chandra Thapa, Kyuyeon Kim, Seyit A Camtepe, Hyoungshick Kim, and Surya Nepal. End-to-end evaluation of federated learning and split learning for internet of things. arXiv preprint arXiv:2003. 13376, 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.
Manish Gawali, CS Arvind, Shriya Suryavanshi, Harshit Madaan, Ashrika Gaikwad, KN Bhanu Prakash, Viraj Kulkarni, and Aniruddha Pant. Comparison of privacy-preserving distributed deep learning methods in healthcare. In Annual Conference on Medical Image Un- derstanding and Analysis, pp. 457-471. Springer, 2021.
Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 116:1-8, 2018.
Dong-Jun Han, Hasnain Irshad Bhatti, Jungmoon Lee, and Jaekyun Moon. Accelerating federated learning with split learning locally generated losses. In ICML 2021 Workshop on Federated Learning for User Privacy and Data Confidentialityy ICML Board, 2021.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cmns at the edge. Advances in Neural Information Processing Systems, 33: 14068-14080, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint
2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-2) 2100, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-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 Statistics, pp.
PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):228--2344 1998.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning on non-iid data silos: An experimental study. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 905-9655-888 978. IEEE, 2022.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- tems, 2:429-450 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint 1181v9190. 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2023
Jihong Park, Sumudu Samarakoon, Anis Elgabli, Joongheon Kim, Mehdi Bennis, Seong-Lyun Kim, and Mérouane Debbah. Communication--ffiiiee and distributed learning over wireless networks: Principles and upplications. Proceedings of the IEEE, 109(5):796-1)) 819, 2021.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint 0000:20033.00955. 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 2014.
Abhishek Singh, Praneeth Vepakomma, Otkrist Gupta, and Ramesh Raskar. Detailed compar- ison of communication efficiency of split learning and federated learning. arXiv preprint
arXiv:1909.091 2019.
Sebastian U Stich. Local sgd converges fast and communicates little. ar8.v: 2018.
arXiv preprint
Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, Seyit Camtepe, and Lichao Sun. Splitfed: When federated learning meets split learning. arXiv preprint arXiv:2004.1200 2020.
Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, and Seyit Camtepe. Advancements of federated learning towards privacy preservation: from federated learning to split learning. In Federrtedd Learning Systems, pp. 79-109. Springer, 2021.
Praneeth Vepakomma, Otkrist Gupta, Tristan Swedish, and Ramesh Raskar. Split learning for health: Distributed deep learning without sharing raw patient data. arXiv preprint 2018.
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 13:7611-7623, 1-7623, 2020.
Jianyu Wang, Hang Qi, Ankit Singh Rawat, Sashank Reddi, Sagar Waghmare, Felix X Yu, and Gauri Joshi. Fedlite: A scalable approach for federated learning on resource-constrained clients. arXiv preprint ar 2tt.::22011116666. 2022.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcma- han, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference Machine Learning, pp. 10334-10344 PMLR, 2020a.
Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for heterogencous distributed learning. Advances in Neural Information Processing Systems, 33:6281 1 1-622, 2020b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnin a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint urXiv: I 770.07747, 2017.
Riccardo Zaccone, Andrea Rizzardi, Debora Caldarola, Marco Ciccone, and Barbara Caputo. Speeding up heterogeneous federated learning with sequentially trained superclients. arXiv preprint arXiv:2201.10883 2022.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806.00555 2018.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradi- 2017.
ent descent algorithm for nonconvex optimization. arXiv preprint
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): 2019.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou Data-free knowledge distillation for heterogeneous federated learning. In International Conference on Machine Learning, pp. 2021.
PMLR,
11

---

Under review as a conference paper at ICLR 2023
CONTENTS
Introduction
Preliminaries and Algorithm of Split Learning
3
Related work
4
Convergence Analysis of SL
4.1
Assumptions
4.2
Convergence Result and Discussion
4.3
Comparison between FL and SL
5
Experiments
5.1
Experimental Setup
5.2
Experimental Results of SL
5.3
Empirical Comparison between FL and SL.
6
Conclusion
More details about Split Learning
13
Additional related work
15
C Summary of theories
16
D Proof of results
16
D.I Basic technical lemmas and Notations
16
D.2 Proof of Theorem
19
D.3 Proof of Theorem 2
................................
22
D.4 Proof of Theorem
22
D.5 Extreme cases
24
More experimental details
25
E.1 More results of SL
25
E.2 More comparisons between FL and SL in cross-device setting
25
12

---

Under review as a conference paper at ICLR 2023
A MORE DETAILS ABOUT SPLIT LEARNING
In this section, we provide more details about SL. More discussions can be found in Gupta & Raskar (2018); Thapa et al. (2021); Duan et al. (2022).
In SL, the complete (or full) ML model is split into two portions. The portion of the complete model maintained by the clients is called client-side model. The portion maintained by the server is called server-side model. In SI,, the client-side model is owned by all the clients, while the server-side model is merely owned by the server. Any client can operate with the server to complete the model training task but can not do it independently (without the help of the server). Then we prepare some basic concepts in the paper.
Local update (step) The process that one client and the server cooperate to conduct the model updates, i.e., the inner loop of Algorithm 1. Note that in SI, though the model update requires communication between the client and server, the model still trained on the local dataset. So the process is called local update (Thapa et al., 2020).
Local model The concatenation of the client-side and server-side models after each local update.
Training round The process that all the clients (or a subset of clients selected) complete their local updates, i.e., the outer loop of Algorithm 1. It is also called a global epoch or global round.
Global model The concatenation of the client-side and server-side models after each global round.
Table 3 summarizes the notations. In partieular, the superscripts and subscripts of random vari- ables appearing in the paper have the same form - a! (r.k) where r is the index of rounds, is the index of local update steps, i is the index of clients. It means that the random variable after the k-th local update on the local dataset D; in the r-th round. The random variable a can be x (model parameters), & (random samples) or g (stochastic gradients).
Table 3: Summary of notations appearing in the paper.
Symbol
Description
T
Total number of iterations
R2
Number, index of (training) rounds
N,i
Number, index of clients
S,151
Subset of clients sampled for training every round and its size Number, index of local update steps;
K, k
K represents the maximum local update steps when the number of local update steps varies across clients Sizes of the overall dataset D and local dataset D, client i Local epochs;
n, n4
E
number of training passes each client makes over its local dataset
b
Mini-batch size
ng
The global, local learning rate
They are used to denote different distributions by the two mechanisms generating non-IID data respectively (see Section 5.1) The complete global model (parameters) in the r-th round
C
x
(r.
The complete local model (parameters)
x;
after the k-th local update on the local dataset D, in the r-th round
Xo, Xx
The client-side model, server-side model
Stochastic gradients over on the mini-batch c!r.k) sampled randomly from D,, also denotes as [x(( (r.k), c(r.k))
gi gi (x))
13

---

Under review as a conference paper at ICLR 2023
Two modes of SL. In fact, there are two approaches of training in SL (i) with client-side model synchronization and (ii) without client-side model synchronization (Singh et al., 2019; Duan et al., 2022). In this paper, SL is referred to the first approach, i.c., SL with client-side model synchro- nization. As shown Figure 4, there are two modes SL. with client-side model synchronization, including (i) the peer-to-peer mode and (ii) centralized mode. The only difference between the peer-to-peer and centralized mode is the synchronization way of model parameters'.
Peer-to-peer mode. Clients store the model parameters by themselves after the local up- dates. So clients get the latest model from other clients.
Centralized mode. Clients send the model parameters to the server after the local up- dates. So clients get the latest model from the server. The centralized mode requires more communication than peer-to-peer mode.
Implementation of SL with nl in the peer-to-peee peer and centralized modes. each round, the last client (client N in Figure 4) needs to request for the initial client-side model and conduct the global model update after completing its local update. The server will conduct the global model update synchronously. For the peer-to-peer mode, this process will cause (i) additional communication cost (the red arrow line at the left side Figure 4) and (ii) additional storage cost of devices and the server (storing the global model). For the centralized mode, this process will cause (i) additional communication cost (the red arrow line at the right side Figure 4) (ii) additional storage cost of the server (the client-side global model is also stored in the server). The communication cost of SL with global update is given in Table 4 based on Singh et al. (2019).
Client
peer-to-pee mode
Client
centralized mode
activations
server side model
gradients
Client
Client
model
paramsterss
dien-side model
diec side server sice model
model
complese model
model parometer
additional communiation global update
Figure 4: Two modes of SL. The peer-to-peer mode is illustrated in the left side; the centralized mode illustrated in the right side.
Table 4: Communication cost of FL and SL when running E local epochs for N clients. x. the sizes of the complete model parameters and the client-side model parameters respectively. n, n, the sizes of the overall dataset D and local dataset D, respectively. The size of the smashed layer denoted as q. SL with global update need additional communication cost of one client-side model parameter each round.
Algorithm
Communication of client
Total communication each round
FL
2x complete model
2NN
SL (peer-to- to-peer mode)
En.q + En.g + gradicat
X client-side model
2En + Nx.
activations
(centralized mode)
En.y + En.y +
2x.
2En + 2Nx.
activations
gradicar
client side model
Comm. of vanilla SL + X.
with global update
'The security and privacy issue beyond the scope of this work.
14

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL RELATED WORK
Variants of SL. SL is deemed as a promising paradigm for distributed model training at resource- constrained devices, given its computational efficiency on the client side. Most existing works focus on reducing the training delay arising from the relay-based training manner in the multi-user sce- nario. Sp Fed (Thapa et al., 2020) is one popular model parallel algorithm that combines the strengths of FL and SL, where each client has one corresponding instance of server-side model in the main server to form a pair. Each pair constitutes a complete model and conducts the local update in parallel. After each training round, the fed server collects and aggregates on the clien-side local updates. The aggregated client-side model will be disseminated to all the clients before next round. The main server does the same operations to the instances of the server-side model. However, in SplitFed, the main server is required for great computing power to support the multiple instances of server-side model. To address this issue, Thapa et al. (2020) proposed SplitFedv2. The only change in Spli FtliiFeee Fedv2 is that only one server-side model in main server. So the server-side model has to process the activations (or smashed data) of the client-side model in sequence. The model gets updated in every single forward-backwanl makes more updates than the client-side model. The main point of Sp SplitFedv: (Gawali al., 2021) is substituting alternative client training with alternative the mini-batch training. In vanilla SL, the local model makes one or more training passes over the local dataset (alternative client train- ing). This may cause "catastrophic forgetting" issue (Gawali et al., 2021; Duan et al., 2022). So SplitFedv3 propose to use alternate mini-batch training. where a client updates its client-side model on one mini-batch, after which the client next in order takes over (Gawali et al., 2021), to mitigate the issue. SFIG (Gao et al., 2021) is one generalized variants of SplitFed. The clients allocated to multiple groups. There is one server in each group. The training inside the group is identical to Split Fedv2. Then the server-side "global" models per group are aggregated (c.g., weighted averaging) to obtain the server-side global model of all groups. FedSeq (Zaccone al., 2022) is the same as SFLG except that the training inside the group is identical to vanilla SL. More variants can be found in Thapa et al. (2021); Duan et al. (2022).
propagation, which means that the server-side model
Convergence analysis of SL. The convergence analysis of SL is identical to standard Minibatch- SGD on IID data (Wang et al., 2022; Park et al., 2021), so some convergence properties of Minibatch SGD is applied to SL too. The algorithm in Han et al. (2021) reduces the latency and downlink communication on SplitFed by adding auxiliary networks at client-side to generate the local loss for model updating. Their convergence analysis combines the analysis of Belilovsky et al. (2020) and FedAvg. Wang et al. (2022) proposed FedLi te to reduce the uplink communication over- head by compressing activations with product quantization and provided the convergence analysis of FedLite. However, their convergence recovers that of Minibatch SGD when there is no quan- tization. SGD with biased gradients (Ajalloeian & Stich, 2020) is also related. However, it only converges to a neighborhood of the solution. Furthermore, we find that Woodworth et al. (2020a;b) compared the convergence of distributed Minibatch SGD and local SGD under homogeneous and heterogeneous settings. To differentiate our work, we show how these algorithms operate in Table 5. For Minibatch SGD, there is local update and each client computes K stochastic gradients the same point x". FL and SL make K times more updates than Minibatch SGD. However, models in FL are training in parallel, while models in SL are in sequence.
Table 5: The update rules of Minibatch SGD, FL (Local SGD) and SL. We use the descriptions of Local SGD and Minibatch SGD in Woodworth et al. (2020b) and notations in Section 2. c(!,.)) ~ DD denotes one random sample from client for the k + 1-th local update in the r-th round.
Algoridhm
Global update
Local update of client
Minibatch
R-1 Σ V
m1 NK
SGD
Local SGD
V (1) ((())))
Initialize: x! (r.00) = x"
111 N
Update: ((rk11)) x((.)) 17 Vi (1 g((c))))
(or Fl.)
Initialize: x (n) (n.
SL
++ x
Update: (1)) x(1))) m ()
1-1 Am
15

---

Under review as a conference paper at ICLR 2023
C SUMMARY OF THEORIES
There are two methods to give the convergence of SL: (i) bounding the progress of all clients in one round; (ii) bounding the progress of one client in one round. The second method can be given based on the techniques of FL (Khaled et al., 2020; Karimireddy et al., 2020; Wang et al., 2020) directly. However, it only converges to a neighborhood around the stationary point of the global function. This case is similar to the biased SGD (Ajalloeian & Stich, 2020). is intuitive to get the conclusion since the local stochastic gradient (x {,) (5, DD; generated by local data of any client i is biased gradient estimator of the global gradient fx() of the global function. For the first method - bounding the progress of all clients in one round, our main contribution, shows that SL can converge to the stationary point of the global function. The main theories summarized in Table
Table 6: Summary theories for SL. 1j is the effective learning rate defined Section 4.3, 7j in "progress of all clients in round" is defined as N nn while i) in "progress of one client in one round" is defined as Km. fl 1. F = f(x") f(x").
Outline
Theory
Progress of all clients in round (7 N (1n))
=[IV < 0 ((x0)-(00111))
(++
8²0² K
+
Go²
Thm.
9
E|| [[
F
+
6202) K
Thm.
K
E[[V/((> [[
VTT)
F
+0
N2 ko²
vT
Cor.
KG++00 KR
o²
+
+
Cor. 2
KVR
Fv (282+1)
r +
R
Fga (K(++1)
Cor. 3
R+1
(8+1))
Progress of one client in one round (f) = Km)
||| E(| (-
0
(mx)m= (ox())))))))) (m.0))
+
1 +
8202 0
(xx²
+ (G9)
Thm. 3
ΣΣ 1=1
R-1 N
11 O
+0
if0²
+ +0
1j0
0
(G²)
Thm.1 3
NR
NNR
K
K
D PROOF OF RESULTS
D. BASIC TECHNICAL LEMMAS AND NOTATIONS
Lemma 1. æ1,.... NN are N vectors, then
| + x
< 1 + +2
(7)
+ (1 2 ||2,,11
|x + æı
(1+ ||
|2
for any 0,
(8)
N
x
16

---

Under review as a conference paper at ICLR 2023
Lemma 2 (Jensen's inequality). For any convex function f and any vectors , NN have
f
2j
f(x)).
(10)
N
As a special case with f(x)) = ||a||
we obtain
(11)
N
Lemma 3. Suppose {A&]k=1 is sequence of random matrices and B( Ak
2 Ai]
0, vk. Then,
T
T
E
A
Σ
B
[
(12)
Proof. This is the Lemma 2 of Wang et al. (2020).
T
T
T
T
E
A
E
|
+ Σ
Σ
E [[TAATA]) A;
(13)
A
im
IE
||
Σ
Σ
THE A
(14)
Assume <.j. Then, using the law of total expectation,
E [ A E EIA A
A.] =0
(15)
Lemma 4 (Bounded Drift). For any local learning rate satisfying m S 2NKL the client drift caused by local updates is bounded, as given by:
2N K2 1 02
K3
(B [+
Σ
E
(r.))
x² 111
(16)
4N2
k=0
Proof. This proof is based on the proof of Theorem et al. (2020). Considering
Convergence of Surrogate Objective of Wang
(r,k)
x"
=
-x!rih)
(r,b))
x +
(r:0)
x;
(r,0)
x
(r:0)
... + x2
(r.0)
x(
(r:0)
(17)
i-1 K-1
=-
Σ
g: (rit)
(x
m Σ
Ba (21)))
(18)
t=0
17

---

Under review as a conference paper at ICLR 2023
have
(n) x x112
E
k-1
1-1K-1
= F
(x (1))))
Σ Σ
(x(((t))))
(19)
1=
K-1
s En
Σ (x) (1,4)
(x
(r(e)) +
(x(
K-1
+ E
(20)
1=0
(
Σ
g (x)
Vf((x(
Σ
Be (x(((i) ([f((((())))
K-1
+ 2E
Σ
(x(((t)tt)
+
Σ
V
(21)
Applying Lemma 3 to the first term on the right hand side in Eq. (21) and Jensen's 's Inequality to the second term respectively, we get
E
x (ni))
x²
11²
< 22 21 2
E
(x(
V
(22)
t=
_ 2: Knj 02 + 4ik
Σ
[[V.fx('']]
K-1
+ 4iK ΣΣ
-
-
(23)
5=1 1=1
2 21²Kn + +
Σ
E
K-1
x |1
42 Σ Σ
E
(24)
1=0
21 Knp
4iK m
[|
N K-1
+ +4iK
(25)
18

---

Under review as a conference paper at ICLR 2023
Summing up
E
x
(r,k)
x
x113
over and k, we get
N K-1
Σ
R
||
x112
2k2 0
Σ 2
4K m
N
R
Σ
+ +4K Σi
(26)
I <2N 4N
E
[V
+4N2K2 338
(27)
Term & is equivalent to Σ R-1 |[||x (rin)
x" 11.. so we can rearrange the equation and get:
N
(1 - 1 & 22 + K2 :f
Σ
E
ff
(28)
Asm.
K2 + K tM B [+ + I
(29)
Using 4N2K2nn 1 and dividing both sides by it yields the claim of Lemma 4.
D.2 PROOF OF THEOREM 1
Proof. Beginning with Assumption 1, we have
L | - x²
- < [Vf(x)),, x ---1-xx) -x')
(30)
From Algorithm know the global model update in round can be written as:
x x" = (x(xx (r x²) -
g (x((x))
(31)
A=0
For the expectation on x", we get
Ex - 1 -xx())
E
V[((x), m
K-1
Σ ((())))))
+ 2
L
!/
Σ
K-1
8: (x((((rb))
(32)
1=1 K=
K=U
K-1
)
K-1
--N
Σ
E Vf(x'), 1 Σ (f((((("1)) (T.A))
+ 1
L
1
Σ
8x
(rAbg))
(33)
19

---

Under review as a conference paper at ICLR 2023
where we use Elg;(x)) = (x) in the equality (see Assumption 2). For the second term on the right hand side (RHS) of Eq. (33), we have:
K-
E
Bx(x(Txh))
S 2E
Bi (rk))
V V (r))
0=
i=1 K=
N K-1
+ 2E
V (
(34)
k=
(9)1 3
8i [x - (xx /|2
2E
N
k=
+ 21E
fi
(35)
k=0
N
K-1
Asm 2 S 2N²Ko² +2
Σ
ΣΣN
(36)
K==
Note in Eq. (35) that we apply Jensen's Inequality first before Lemma the first term of RHS, since the data across clients are non-llD. However, if the data across clients are IID, we can get tighter bound of 2K2.. Then plugging Eq. (36) into Eq. (33), we have:
[[ f(x"
K-1
N Σ i=1
)1
N K-1 Σ
!?
$ n
fx(x")
V fo (xf (22(111)
DEEE
f(
N
k=O
R=
+ N K K.nin 02
(37)
N1g
K-1
|Vf('')1
+E
N
V fi(x (m))))
-E
1 N
fx(xx
(rck))
Vf(x*)
2
N
N
km
t=1
1=1
N
K-1
27
+ DI
Vf((x((
+ NN Lnn 0²
(38)
K=
where we use the fact that 2 (a, b) = ||a112
+16111
||a bll in the last equation. Note that
K-1
N
N K-1
m
Σ
E
f((
(r(d))
A=
(9)
2 11
11
K-1
Σ
E
V
Vi((((Ta))
L K
K-1
E
Σ
N
V(((x(rA0))
K-1
N
2N (1
2N L
ΣE E
(r.))
(39)
k=
N N Σ
17
N
and
E
- Vx((')) -vfx))
=E
[ (ra v.((x"))
V V)((x*)
Asm. 1
Σ
LE
x (r. - x* -19
(40)
N
1=1
20

---

Under review as a conference paper at ICLR 2023
where the first equality of Eq. (40) results from the fact that Vf(x*)
N Σ vfi(x'). By
plugging Eq. (39) and Eq. (40) into Eq. (38) and using 2N K 7
I 1, we get
N K
x11
5(x))
N N VI(x")|| + 2
n
Σ
E
2
+ No 1
(41)
Then we use Lemma 4:
Blf(x* f(x))
DB²
|V + L
NK
2
1-
1
2N
(42)
where D = 4N2K<2222 Then using DS
2B*41 and B2 1, we get
_ - [V]((x)| NIggn
NKng
+ + 1 KN2
22
(43)
2B
3 N K 1.2 1/0² + 33N2 (44) S - [ No
Taking unconditional expectation, rearranging the terms and then averaging the above equation over R 1), have
{0,
4[f(x)) f(x"))
+ 12N2* + 6N + 4N
R P=0
NR
Using the fact that E.
)
R Σド=0 [VV[((")) 2 where x
R RR-1 x", we get the
Eq. (5). Finally, we summarize the constraints:
D = K2 < 2B2 +1
(45)
2NK 1 2N Lmp 1
(46)
(47)
where the last inequality is from Lemma 4. The overall constraint is given as:
1
1 S 2NKL min
(48)
222B2 +1+ Tla
Now we complete the proof Theorem 1.
Corollary 2. Choose NKng holds that
VT and apply the result of Theorem 1. For sufficiently large R.
KG +02 x22 (F))+0(
[[ (|2) O
F +
(K
VKR +
(49)
(RR
KVR
where F= [(x") f(x"), R is the total rounds, &
ni IR- x" is the averaged global model
over the R rounds.
Corollary 3. Apply the result of Theorem 1. There exits T). such that
F [2 +1)
+0 G o2 )
Foz (
<
(50)
R+1
(R (R+1) 1)
where F = f(x9)= [xx),, R is the total rounds, x 1 R is the averaged global model over the R rounds.
Rt
Proof. Applying Lemma (sub-linear convergence rate) of Karimireddy et al. (2020) to Eq. (44),
get the the claim of this corollary.
21

---

Under review as a conference paper at ICLR 2023
D.3 PROOF OF THEOREM 2
Theorem 2. Let Assumplions 1, 2 and 3 hold. Suppose that the local learning rate satisfies Tn S
2KL min
V2B=4I' No For Algorithm 1, it holds that
4l5(x)) [(x))] R Ti cinitializztionn ervor
4ng La
+12K 1)n +6( 1)nf
N
Tisoliont drift orear
Ts:global variance
(51)
where R
Er=o x" is the averaged global model over the R rounds.
Proof. This is almost the same as Theorem of Wang al. (2020), we reproduce here for conve- nience of comparison between FL and SL. The proof is similar to that of Theorem 1.
D.4 PROOF OF THEOREM 3
Here Assumption to replace Assumption 3, one stronger assumption (than Assumption 3) used Lian et al. (2017).
Assumption 4. There exist constants G 2 0 such that
EA [IV]((x) - VI(x)]lI S G?; where is uniformly sampled from {1.....N} N}. In the IID case, G G=0,
(52)
Theorem 3 (Progress of one client in one round). Let Assumptions 1. and 3 hold. Suppose that the local learning rate satisfies 17I I 2V5KL" For Algorithm holds that
R-1
N
4 - f(x)) + L0
E
NR
NKyR
10KL2 ALmpo² + 4G²,
(53)
where x EP-o x" is the averaged global model over the R rounds.
Proof. Different from Theorem 1, we bound the progeress of one client in one round. Beginning
with Assumption 1, we have:
E [(x(11) s(x(r10))] S (V (11
L +
|| ((:00) 11=00) (54)
From Algorithm know the local update of client in round be written
K-1
(r.0) i+1 x;
(r.0)
17
Σ
gi (x (r.k))
(55)
km
For the expectation (r.0)
we get
E
f(x (10))
-(x((-10)
K-1
))
K-1
18
v.((((r00)
Σ g: (x
(r.))
(r.))
+ 1B
m Σ g: (2))))
(56)
K-1
K-1
Σ
[
(1.0)) (xxxx()))))
L
Σ
8 (x11))
(57)
A=0
22

---

Under review as a conference paper at ICLR 2023
where use Eig, (x)] = (x) in the equality (see Assumption 2). For the second term on the right hand side (RHS) of Eq. (57), we have:
E
Σ (x
(
< 21
g (x (.ck)) (x((((())))
fx((X (m)b))
+ 2E
(58)
Lem. 3 S 2E
gi (x (1))
(x( ( ||
K
+ 2E
(59)
k=0
Asm. 2
S 2Ko² +E
Σ
V (1)))
(60)
Then plugging Eq. (60) into Eq. (57), we have:
E
[( (r.0)
- [xx (x)) }
K- 1
K
Vf((x( 17
S Th
Σ
E
(V ()(((/(()))) |} + Lnj'E
Σ
+
K Lnfo²
(61)
k=0
K Σ
|| |0)))/
||
+ E (x /| - E V fi((((( -V
K
K-1
+ E
+ K oT
(62)
A=O
where we use the fact that (a, b) = ||a||
|bb|| - ||a
bl] in the last equation. Note that
111
E
2
Σ K=
E
(x
+ Lnf K
E
K-1
(x))))
n (1- - 2KTm)
E
(63)
k=0
E |
||] 1
V fx(((( - (x /19
and
2E
Vii(((--0) VS(x (0) >17
+ 2E
(64)
Asm.
|| -x x((-0) 19]
<
2
+ 2G
(65)
By plugging Eq. (63) and Eq. (65) into Eq. (62) and using 2K 2KnL. L < 1, we get
K Σ
(1:0)) E [(x(11)) - f(x(1:0) s Km [(x(( (1:0)) /|2
||
+ I
E
x
(r.k)
x, 1/00011
k=0
Gm + KImZ02
(66)
23

---

Under review as a conference paper at ICLR 2023
Then using the bounded client-drift in Wang al. (2020), i.e.,
4K nf
V [x((x (1:0))
||
2K 12
E
x (r.))
x
11:0011
(67)
4K21211
k=
we can get
f(x
(1.01) ((xc!-011)
2D )
|
5
1
+ Lino² G
Kmp
2
D)
2D
2K 2K1211002
G²
(68)
1-D
where D = 423 Then using D
1
I-D
1
<
| and B 2 1, we get
((x(m))) - 5(xx [
1
V (00)
+ Lmpo + G²
Ktp
5 KL nf
10K 1
(69)
Taking unconditional expectation, rearranging the terms and then averaging the above equation over i == {1, 1. Nr,r {0, .... R - 1}, we have
E ΣΣ 0=
R-1
|
4l5(x)) - - [(x*)]
4,
NR
NK
10KL' 4Lmoo + 4G
(70)
Using the fact that E
< R. Σ
[xx'''| 2
where x R -R-1 x", we get the
Eq. (53). Finally, we summarize the constraints:
= 4K2 S
(71)
21 <
(72)
The overall constraint is given
111 5 2V5KL
(73)
Now we complete the proof of Theorem
D.5 EXTREME CASES
Theorem recovers the convergence of SGD when N = 1 and K 1. Let focus the proof of Lemma 4. When N = and K = 1, the client drift will reduce to:
Σ
N K-1
(m.))
17 = E
x 0.0
x" 11 = O.
(74)
(r.0) x" (see Algorithm 1). Thus the client drift error of Eq. (5) will be removed, which where x1 recovers the result of SGD (Bottou al., 2018).
24

---

Under review as a conference paper at ICLR 2023
E MORE EXPERIMENTAL DETAILS
Platform. We train LeNet-5 on MNIST and Fashion-MNIST with Nvidia GeForce RTX 3070 Ti, VGG-11 on CIFAR-10 with Nvidia 3090 Ti. The algorithms implemented by Porohh. We use the random seed "1234" by default. We use vanilla SGD algorithm with momentem = 0.9 and weight decay le-4 as He et al. (2020). The detailed information of the models and other information be found in our code.
E.1 MORE RESULTS OF SL
This section is complimentary Section 5.2 to study the factors that affects the performance of SL. We report the details of the experiments, such as 1/1, Tl. b.
Effect of data heterogeneity.
MNVIST
Fashion-MNIST
2.5
CIFAR-10
2.25
2.25
SLIIK5)
SLCC
Suridi
-LIC-5)
2.00
SUC-
SLCC=5)
-.10-21
SLI 2)
1.50
1.20
Their
3.0
1.00
0.75
0.0
0.25
1.
1.0
300 250
(a) MNIST
(b) Aishion-MNIST
(c) CIFAR-10
Figure 5: Effect of data heterogeneity. (a) MNIST, 10, 11000 7 0.01, 1l 1.0: (b)
Fashion-MNIST, N = 10, b 1000, ? = 0.01, f/g = 1.0; (c) CIFAR-10, N = 10, 10 Vi 0.001, flg 1.0.
Effect of K.
MNIST
Pashion-MNIST
CIFAR-10
SLtp1101 E-1
2.25
SLie-1.0 01 E-1
2.0
Lite=101
2.00
Stie=1.00 5=2
SLip-1.01 E-4
Lets
1.55
S1te=1.01 E-d
S1le-1.0) E-8
Thil Love
SL
Silg-1 1.01 E-10
SLie-1.01 E-10
Stia-1.0 [:0 E-2
1.0
1:25
3.5
Stiom11. End
SLiu=1.61 E-d
3.00
3.-
10
20
22
10c
Rounds
Rounds
Rounds
(a) MNIST
(b) Fashion -NISST
(c) CIFAR-10
Figure 6: Effect of K. Dir1o(1.0) is used. (a) MNIST, N = 10, 1000, 0.01, 77 = =10;
(b) Fashion-MNIST, N 10, 1000, m7 0.01, ng 1.0; (c) CIFAR-10, N 10, 6 100,
= 0.005, fly 1.0.
Effect of ng. The experimental results on Fashion- -NIIST and CIFAR-10 are shown in Figure 7. We can see that Fly can be helpful in some cases, especially when is small. However, there is still a big gap between theory and practice. Further research is required.
E.2 MORE COMPARISONS BETWEEN FL AND SL IN DDVVIEE SETTING
The learning rates of FL. and SL are selected from (0.0005, 0.001, 0.005, 0.01, 0.05, 0.1}. We report the overall results of comparisons between FL and SL on MNIST, Fashion-MNIST and CIFAR- datasets with different learning rates in Table 7, Table 8 and Table respectively. Table 2 in the main body are based on these three tables here. "L-M". "L-M" and "V-10" denote LeNet-5 on MNIST, LeNet-5 Fashion-MNIST and VGG-11 on CIFAR-10 respectively. We highlight the "best" test accuracy among all chosen learning rates with blue for FL and red for SL. We underline the test accuracy of the "threshold" learning rate with blue for FL and red for SI..
25

---

Under review as a conference paper at ICLR 2023
5.-
33.4
31.4
50.
160
180
559
Giotal Learming Rate
1.0
114
11.
11.4
11-
9.
350
124
187
150
10.0
Learming
114
28.6
92.1
211
16.
233
584
22.
100
20:0
-3
10.
215
20.5
473
160
714
70.6
00.0
30.2
56.
96.0
183
114
14
18.5
423
15.
15
84
14.
485
90.2
05.0
05.4
23.0
12-
12.4
114
12.
15.3
355
159
66.
552
642
32.4
26.7
14.00
1:41
a1-1
1991
58.40
E:41
18:00
-1-1
-3
Local Learning Rate (10x) = logisle)
Local Lesining Rate (f3r) logusk))
Local Learning Rate (f3r) logule))
Figure 7: Test accuracy for various local/global learning rates combination. Dir (1r10(10.0) used. For MNIST, N = 10, b = 1000, E' = 1; We average test accuracy over the last 10 rounds from 30 total rounds; (b) For Fashion- MNNIT, N 10, b 1000, E. 1 We average test accuracy over the last 10 rounds from 30 total rounds; (c) For CIFAR-10, N = 10, b 100, F = 1. We average test accuracy over the last 20 rounds from 100 total rounds.
Table 7:
The detailed results of FL. and SL. with different learning rates MNIST dataset. We average the test accuracy over the last 100 rounds from 1000 total rounds when F 1; average the test accuracy over the last 10 rounds from 100 total rounds when E' 10.
0.0005
0.001
0.005
0.01
0.05
0.1
Tag
N
Dist.
E
b
FL
LMM
1000
IID
1
10
67.8
97.8
92.0
98.4
98.3
98.9
98.7
89.2
99.0
11.3
99.0
11.3
LM
1000
10.0
10
78.1
98.3
93.2
98.7
98.5
99.0
98.7
98.9
99.0
11.3
98.7
11.3
L-M
1000
α 5.0
10
80.2
97.9
93.4
98.7
98.5
98.9
98.8
98.9
99.1
11.3
98.8
11.3
LM
1000
0.5
1
10
81.3
97.9
93.6
98.6
98.4
98.8
98.8
98.7
98.9
11.3
98.3
11.3
L-M
1000
0.2
10
85.9
98.3
94.0
98 6
98.3
98.8
98.7
98.7
98.7
11.3
11.3
LM
1000
C
10
65.3
98.3
91.6
98.6
98.3
98.9
98.7
98.9
99.0
11.3
98.9
11.3
LM
1000
C 2
10
56.4
98.2
89.2
98.6
97.9
99.0
98.5
99.0
98.8
11.3
98.8
11.3
L-M
1000
I1D
10
10
93.4
97.3
95.6
87.91
97.6
97.66
97.9
96.2
95.5
11.3
11.3
11.3
L-M
a 10.0
10
10
93.8
96.2
97.5
97.4
97.4
11.3
L-M
1000
a 5.0
10
10
93.9
88.3
96.2
97.8
97.8
69.3
98.0
11.3
11.3
11.3
11.3
11.3
L-M
1000
0.5
10
10
92.6
87.9
94.9
97.91
97.3
11.3
97.9
11.3
11.3
11.3
11.3
11.3
LM
0.2
10
10
93.4
96.8
95.6
11.3
L-M
1000
C = 5
10
10
91.9
88.3
95.0
98.0
97.7
77.7
98.0
11.3
9.8
11.3
11.3
11.3
L-M
1000
C
10
10
70.8
96.9
88.4
97.1
96.8
11.3
87.6
11.3
11.3
11.3
11.3
11.3
Table The detailed results of FL and SL with different learning rates on Fashion-MNIS" dataset. We average the test accuracy over the last 100 rounds from 1000 total rounds when F = 1; average the test accuracy over the last 10 rounds from 100 total rounds when = 10.
0.0005
0.001
0.005
0.01
0.05
Tag
N
Dist.
FL
SL
FL
SL
FL
SL
EL
SL
FL
SL
FL
SL
L-F
1000
IID
54.4
75.0
85.9
83.7
88.4
86.
88.2
88.1
87.8
10.0
I.F
1000
a
10.0
10
57.4
84.0
71.0
86.5
84.4
88.8
86.4
88.6
88.1
80.2
87.5
10.2
L-F
1000
5.0
10
57.4
84.6
74.0
86.3
84.2
88.6
86.3
88.4
88.2
79.9
87.6
10.0
L.F
1080
72.9
87.3
86.7
85.2
10.0
I.F
1000
0.2
10
60.8
81.6
71.3
84.3
80.8
85.9
83.5
84.9
83.4
10.0
10.0
10.0
L-F
1000
C
5
10
53.8
82.4
67.0
85.6
81.7
88.0
84.6
88.1
87.5
10.0
86.8
10.0
1080
80.4
77.5
10.0
L-F
1000
75.6
82.7
78.8
84.0
82.5
80.0
46.4
10.0
10.0
L-F
1000
10.0
10
10
76.0
83.6
79.4
84.1
84.0
81.7
84.8
63.7
10.0
10.0
10.0
10.0
L-F
1000
5.0
76.0
83.2
79.5
76.6
83.9
80.8
84.5
77.0
10.0
10.0
10.0
10.0
L-F
1080
a 0.5
72.7
78.0
75.8
79.2
82.8
76.8
83.8
10.0
10.0
10.0
10.0
10.0
L-F
1000
0.2
10 10
65.1
79.0
68.4
78.6
79.3
70.9
80.4
10.0
10.0
10.0
10.0
10.0
L-F
1000
C 5
68.6
78.9
72.7
80.
80.6
77.5
82.7
25.8
78.0
10.0
10.0
10.0
L-F
1000
C 2
52.8
72.0
59.5
72.3
73.3
10.0
75.9
10.0
34.5
10.0
10.0
10.0
26

---

Under review as a conference paper at ICLR 2023
Table 9: The detailed results of FL and SL with different learning rates on CIFAR-10 dataset. We average the test accuracy over the last 400 rounds from 4000 total rounds when E = 1: average the test accuracy over the last 40 rounds from 400 total rounds when E' 10. We don not execute the experiments whose learning rates are larger than the "threshold" learning rate (*- " in the table).
0.0005
0,001
0.005
0.01
0.05
0.1
NN
Dist.
FL.
SL
FL
SL
FL.
SL
FL
SL
FL.
SL
FL
SL
V-10
500
10.0
47.4
86.4
84.2
86.9
85.7
84.2
86.3
10.0
10.0
V-10
500
5.0
47.2
86.5
84.2
87.0
85.6
84,5
86.1
10.0
10.0
V-10
500
0.2
10
22.9
81.2
39.4
83.5
78.1
83.0
80.5
10.0
10.0
V-10
500
C'
14.4
83.7
37.6
85.9
82.3
86.5
84.7
83.4
85.5
10.0
10.0
V-10
81.9
73.7
12.9
80.0
10.0
V-10
500
IID
$1.5
83.2
83.7
77.3
78.3
77.7
10.0
10.0
10.0
10.0
10.0
V-10
500
10.0
10
10
53.3
82.8
69.1
83.0
76.3
10.0
77.9
10.0
10.0
10.0
V-10
82.7
77.6
10.0
V.10
500
0.5
40.6
75.1
58.4
76.9
71.0
10.0
71.8
10.0
10.0
10.0
10.0
10.0
V-10
500
0.2
27.1
65.0
41.0
10.0
66.2
10.0
66.9
10.0
10.0
10.0
10.0
10.0
V-10
C
36.3
77.6
78.9
73.9
10.0
V.10
500
C 2
20.3
58.7
27.8
10.0
51.8
10.0
10.0
10.0
27


Reviews:
[{"review_id": "aDl-P6LXkLL", "reviewer": "Reviewer_434u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the convergence rate of split learning theoretically. With constant step sizes in both inner and outer loops, the outer loop complexity is $T^{-1/2}$ with additional terms depending on noise and dissimilarity. Then it compares the rate between SL and FL and presents discussions/explanations.", "summary_of_the_review": "I think the paper is important and solid, and the clarity is great. With a few more revision regarding my questions above, I believe it's ready for acceptance.", "strength_and_weaknesses": "The topic is of great importance for theoretical analysis of optimization in distributed machine learning. I believe the proof is correct and solid. The experiments are concrete.\n\nSome questions:\n- I suggest a table for notations, and highlight the super/sub-scripts of $x$. \n- Eq (2) is correct but a bit misleading for readers. Although there is a sum over $k$, one cannot get all $x_i^{r,k}$ over $k$ at the same time because the $k$ stands for iterations, so the $x_i^{r,k}$ comes sequentially like in Algo 1 box. When I saw a sum, I felt the terms can somehow be parallelized but actually not, so it would be great to clarify in a footnote, or always write as in Algo 1. \n- Assumption 3: Could you explain why “In the IID case, $B = 1, G = 0$”? I suspect (e.g. in stochastic case) $E\\|\\nabla f_i\\|^2 = \\|\\nabla f\\|^2 + Cov(\\nabla f)$, was it wrong? Could you use a few simple examples in appendix calculating $B,G$, like linear functions, $f(x) = ax$ and $f_i(x) = a_i(x)$, and so on?\n- Step size: you choose $T=NKR$, where is $B$? In Thm.1, the third term in $\\min$ depends on $B$. \n- Rate: Is the rate outer loop complexity, and the total gradient calculation $K$ times that number? Could you compare it with SGD, and GD if you simply calculate all stochastic gradients together and average them? I didn’t mean SL has to beat them, but it would be helpful and interesting to compare. If the rate is not as good, it would be great to explain the reason. Is it due to the fact that you cannot shuffle or randomize the individual/local gradients? Are you aware of any lower bound of RHS of Cor. 1 and how suboptimal the result is from that optimal rate?\n- Constant step size: if the step size depends on $T$ and error depends on $T$, would it be better to choose a larger error and a small $T$ at the beginning, i.e. use a large step size at the beginning, then refine the error, increase $T$ and decrease the step size? In SGD one can use the decreasing step size.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "TzB24RXMlGb", "reviewer": "Reviewer_SLb6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper derives the convergence guarantee of SL for non-convex objectives on non-IID data.  It compares also SL against FL theoretically and empirically,", "summary_of_the_review": "-In Algo 1. I have a problem understanding exactly what is the communication round here, because in step 8 and 10 there is communication between clients and server. You don't count that as a communication round?\n\nTo have the local update in step 12 (local model update) according to algo 1, communication is needed between the server and the client, so what is local here since there is a communication between server and client?...\n\nIt seems that there are \"local\" communication rounds which are denoted by k=0.1,...K and there are \"global\" communication rounds which are r=0.1...R can you clarify what this is, because for me the communication happens for both iterations k and r? am i missing something?\n\n-In step 12 you put, client-side and server-side updates, again I'm confused here, how the server can access the local gradients to do this local update.\n\n- In step 3, since in SL things work in parallel, why do you need to sample a subset of clients only?\n\n-Table 1: in local updates for SL, is it a typo of indices there x_{i}^{r,k+1} = x_{i-1}^{r,K}- ... or am I missing something again?\n\n-if my understanding is correct, x^r of FL is the same as x^{r,K} of SL. Then from Table 1, SL and FL and producing the same iterations if they use the same learning rates and batches? if my understanding is wrong, can you tell what prevents SL from using x^r in local updates.\n\n-The reported complexity bounds between SL and FL are the same up to the multiplicative constant N.\nThe reason is, I think, the choice of learning rates. \nIf you change the lr of SL by the lr of FL over N you get the same bounds for FL and SL!\n\n-Does K depend on i? you have K=En_i/b.\n\n\n------after rebuttal----\n\nAfter discussions with authors and rebuttal with other reviewers. The authors addressed some of my concerns. I still think that the complexity results given in the first version of the paper, SL and FL have exactly the same complexity bounds by choosing the right learning rates. See my comments and discussions on this. I decided to increase my rating of the paper to 6.", "strength_and_weaknesses": "See Below", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MTJgWzXQUFb", "reviewer": "Reviewer_4bP6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work establishes the convergence bound of split learning (SL) for non-convex objectives with non-iid data. The convergence results provide some insight on the parameter tuning and potential benefits/limitations of split learning, compared with standard federated learning (FL, local SGD). The authors also conduct empirical comparison between spilt learning and federated learning with respect to data heterogeneity, which provides a deeper understanding between them.", "summary_of_the_review": "This work provides some new analysis of SL on non-iid data and compare it with FL, which is only marginally interesting from my perspective. It is not clear what are the technical difficulties of proving the theorems, and the discussion of the theorems is inadequate. The overall presentation also needs to be improved.\n\n---------------------------------------------------\nAfter rebuttal: Thank the authors for the detailed responses and revision, I really appreciate the effort. I have also checked other reviews and responses. The revision greatly improved the clarity of this paper. However, I still think the novelty of this paper is below the bar as there seems to be no strong or really exciting result. I keep my score but will not be upset if this work gets accepted.", "strength_and_weaknesses": "Strengths:\n- The analysis seems solid and correct, though I didn't go through all the details in the appendix.\n- To my knowledge, the convergence result is new, which complements the theoretical study of split learning.\n\nWeaknesses:\n- The main takeaway of this work is that SL is faster than FL and generalizes similar to FL on mildly non-IID data, while FL prevails on highly non-IID data. This conclusion does not seem surprising to me since previous works (e.g., Gao et al. (2020; 2021) cited in the submission) already made such observations.\n- For the theoretical results, since split learning runs sequentially for its local updates, it is basically minibatch SGD with biased updates. Thus, as long as the accumulated error (client drift) can be bounded, establishing its convergence seems straightforward to me. I hope the authors can discuss the technical difficulties on deriving the convergence bound.  \n- The discussion (or guidance for hyperparameter selection) for the theorem is inadequate. For example, in section 4.1, \"one needs to meticulously design the value of K for the best performance\", \"large value of K forces SL prone to converge to local optima\", \"to reduce the communication overhead without hurting the convergence rate\" all require further discussion, such as to analyze the communicated bits of split learning. The Effect of $\\eta_g$ seems interesting, but it is not thoroughly studied. It seems that we can choose an arbitrarily large $\\eta_g$?\n- The presentation also needs to be improved (see below). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject