Convergence Analysis of Split Federated Learning on Heterogeneous Data

Due to space limitations, we add additional responses to your comments as follows.

5. Presentation improvement (for W3, W5, W9, W10, W11, W12)

We have carefully refined the presentation of the entire paper mainly including the following:

• For line 128, it is revised as "SFL-V2: the main server computes the loss $F_n([\boldsymbol{x}_{c,n}^{t,i},\boldsymbol{x}_s^{t,i}])$ , based on which it then updates the server-side model $\boldsymbol{x}_s^{t,i}$."

• We will revise the presentation of $\gamma$ in equation (10) to include it only in the strongly convex case.

• For line 487, we define $A^{t}:=A^{t,0}=\mathbb{E}\left[\left\Vert \boldsymbol{x}^{t,0}-\boldsymbol{x}^{t}\right\Vert^2\right]=0$. This is achieved by the fact that $\boldsymbol{x}^{t}=\boldsymbol{x}^{t,0}$ at the beginning of each training round $t$.

• For line 520, the second equality is due to $\left(a+b\right)^2=a^2+2ab+b^2$.

• We will move Table 1 to the main paper and explain the comparison between Mini-batch SGD, FL, SL, and SFL.

• For line 828, we will redefine the notation to avoid confusion. Let $K$ represent the total number of clients involved and $D$ denotes the aggregate size of the data. Let $v$ indicate the size of the smashed layer. The rate of communication is given by $R$. $T_{\rm fb}$ signifies the duration required for a complete forward and backward propagation cycle on the entire model for a dataset of size $D$. The time needed to aggregate the full model is expressed as $T_{\text{fedavg}}$. The full model's size is denoted by $|W|$. $r$ reflects the proportion of the full model’s size that is accessible to a client in SFL. The updated Table 3 is shown as follows.

6. Learning rate of SFL (for W6)

SFL and other deep learning algorithms, such as FL, require a positive learning rate to ensure the model is updated. Therefore, the lower bound of the learning rate is $\eta^t > 0$. We will update this condition in our main paper.

7. Explanation of experimental results (for W8)

The fluctuations in model accuracy observed in Figures 4 and 5 are due to clients' partial participation in SFL. In particular, clients are randomly sampled for training in each training round. Due to the data heterogeneity of the clients, the datasets of the sampled clients in each round may not represent those of the entire client population. Since the model is trained based on the local datasets of the sampled clients in each training round, the varying set of sampled clients makes the model accuracy fluctuate across rounds. This phenomenon has been discussed and verified in [Kairouz et al. 2021, Section 7.2] and [Tang et al. 2023]. Moreover, this explanation on the accuracy fluctuation can be supported by Figure 4, where the fluctuations across training rounds become more pronounced at lower participation probabilities, $q$. On the other hand, regarding the learning rate, we maintain the same learning rate across different participation probabilities to ensure a fair comparison. The learning rate was fine-tuned to achieve the best converged model accuracy under full participation.

[Kairouz et al. 2021] P. Kairouz and et al., ``Advances and open problems in federated learning", arXiv, Mar. 2021.

[Tang et al. 2023] M. Tang and V. W.S. Wong, “Tackling system induced bias in federated learning: Stratification and convergence analysis,” IEEE International Conference on Computer Communications (INFOCOM), May 2023.

8. Theoretical results comparison between SFL-V1 and SFL-V2 (for Q2)

Our convergence bounds demonstrate the same convergence rate with respect to the training round $T$ for both SFL-V1 and SFL-V2. Despite $\alpha_n$, SFL-V1 and SFL-V2 have different bounds on the stochastic gradient variance $\sigma_n^2$. Specifically, SFL-V2 is more centralized than SFL-V1, resulting in a lower $\sigma_n^2$. In the future, we will improve the convergence error rate to make it tighter.

9. Limitation of our paper (for Limitation)

One limitation is that our bounds for SFL achieve the same order (in terms of training rounds) as in FL, yet the experiments showed that SFL outperforms FL under high heterogeneity. This is possibly due to that tighter bounds for SFL are to be derived, which is an important future work. Another limitation is that we did not include the theoretical analysis on how the choice of cut layer affects the convergence. We will add the more detailed discussions of limitations to the main paper.

Thank you for your valuable comments! Our response to your comments is as follows. We use "W*" to tag responses to comments in the Weakness and "Q*" for responses to comments in the Questions.

1. Latency of SL and SFL (for W1)

Split learning has higher latency than centralized learning due to the additional transmission of intermediate features and feature gradients between the two agents. In SFL, the communication between clients and the main server results in higher latency per training round compared to FL.

We compare the communication overhead and total model training time for FL, SL, and SFL in Table 3 of the appendix. The total communication time of SFL is primarily determined by the size of model, the proportion of client-side model over the whole model, and the size of smashed layer. It is observed that SFL may induce higher latency when the data size and smashed layer size are large. We will revise our paper to enhance its precision.

2. Theoretical results for SFL and FL comparison (for W2, Q3)

We first explain the reason why SFL outperforms FL/SL under high data heterogeneity. Under high data heterogeneity, FL suffers from the notorious client drift issue, while SL suffers from the catastrophic forgetting problem. SFL (in particular SFL-V2) combines the training logic of FL (at clients) and SL (at server), which can help mitigate the issues of client drift and forgetting. Hence, SFL can lead to a better performance than both FL and SL. On the other hand, the theoretical comparison between SFL and FL/SL will serve as our future work. Through further characterizing the impact of cut layer on client drift and the degree of catastrophic forgetting in the theoretical analysis, we would be able to validate the aforementioned discussions and the theoretical improvement of SFL compared with FL/SL.

Then, since our main focus is analyzing the convergence rate of SFL, we would like to summarize the observations that holds in both theoretical and empirical results. First, the performance of SFL degrades in data heterogeneity. In theoretical analysis, as $\sigma_n^2$ or $\epsilon_n^2$ increases, the convergence error increases. This is consistent with the empirical results that as $\beta$ decreases, the accuracy of the trained model decreases. Second, from both the theoretical and empirical results, as the number of clients participating in each round (i.e., $q$) increases, the convergence error decreases. Third, from the empirical results, the accuracy of the trained model increases with the cut layer. This can be indirectly supported by our theoretical analysis. In particular, we empirically show that as the cut layer $L_c$ increases from 1 to 4, the maximum bound of the gradients across clients (i.e., $G^2$ defined in Eq. (7)) reduces (in particular, its values are 21.53, 19.86, 15.48, 12.81 for Lc = 1, 2, 3, 4, respectively). Based on the theoretical analysis, such a reduction of $G^2$ indicates the reduction of the convergence error and hence the improvement of the model accuracy.

3. Assumptions in different cases (for W4, W7)

The Assumptions used under different cases for SFL-V1 and SFL-V2 are as follows:

• $\mu$-strongly convex: Assumptions 3.1 (smoothness) and 3.2 (Unbiased and bounded stochastic gradients with bounded variance);

• General convex: Assumptions 3.1 (smoothness) and 3.2 (Unbiased and bounded stochastic gradients with bounded variance);

• Non-convex: Assumptions 3.1 (smoothness), 3.2 (6) and (7) (Unbiased and bounded stochastic gradients), and 3.3 (heterogeneity).

The above assumptions are widely applied in the literature. For instance, in the strongly convex case, the assumptions used in our paper are the same as those in Li et al. (2020). The heterogeneity assumption, captured by $\epsilon^2$, is used only for the non-convex case, as in Jhunjhunwala et al. (2023) and Wang et al. (2023).

The difference in assumptions for strongly/general convex and non-convex cases is due to the form of convergence error we obtain. Specifically, we need to compute the model update in each local training with multiple iterations, denoted by $\tilde{\tau}$ and $\tau$. For strongly and general convex loss functions, we propose Lemma C.5, which directly provides the upper bound of the model parameter change over $\tau$ iterations. However, for non-convex loss functions, we compute the relationships between the model updates and the global gradient of the loss functions, as described in Lemma C.6. The upper bound of the squared norm of stochastic gradients, given by equation (7) in Assumption 3.2, and the upper bound of the divergence between local and global gradients, given by equation (8) in Assumption 3.3, are used to prove Lemmas C.5 and C.6, respectively.

[Jhunjhunwala et al. 2023] D. Jhunjhunwala, S. Wang, and G. Joshi, “Fedexp: Speeding up federated averaging via extrapolation,” ICLR, 2023.

[Wang et al. 2023] S. Wang, J. Perazzone, M. Ji, and K. S. Chan, “Federated learning with flexible control,” IEEE Conference on Computer Communications, 2023.

4. Theoretical results on partial participation (for Q1)

Our paper considers a different partial participation mechanism compared to the ICLR paper, resulting in different convergence error bounds. Specifically, the ICLR paper assumes a constant number of participating clients in each training round, with clients randomly selected with equal probability. In contrast, our paper considers independent participation probabilities for each client, allowing for arbitrary and heterogeneous participation probabilities. To prove the convergence error bound with clients' partial participation, we compute the difference between full and partial participation. In the future, we plan to improve these convergence bounds to make them tighter.

Due to space limitations, we will add additional responses to your comments in Official Comments.

Thank you very much for your quick response!

We will enhance our main paper by emphasizing the contributions and simplifying the proof if the paper gets accepted. We will also improve our convergence results to make them more robust, as you suggested, in the future. Thanks again for your time and positive feedback on our paper.

Thank you for your valuable comments! Our response to your comments is as follows.

1. Related work

We enriched the related work as follows. In particular, we have added more discussions on the references.

There are many convergence results on FL. Most studies focus on data heterogeneity. For example, [Li et al. 2020] proved the convergence of FedAvg on heterogeneous data. [Wang et al. 2019] gave the convergence of FL, which is used to design a controlling algorithm to minimize loss under budget constraint. [koloskova et al. 2020] provided a general framework of convergence analysis for decentralized learning. Some studies look at partial participation. For example, [Yang et al. 2021] speeds up FL convergence in the presence of partial participation and data heterogeneity. [Wang and Ji 2022] gave a unified analysis for partial participation using probabilistic models. [Tang and Wong 2023] analyzed how to tackle system induced bias due to partial participation. There are also convergence results on Mini-Batch SGD, where [Woodworth et al. 2020] argued that the key difference between FL and Mini-Batch SGD is the communication frequency.

To our best knowledge, there is only one recent study [Li and Lyu 2024] discussing the convergence of SL. The major difference to SL analysis lies in the sequential training manner across clients, while SFL clients perform parallel training.

[li et al. 2020] Li X, Huang K, Yang W, et al. On the convergence of fedavg on non-iid data. ICLR, 2020.

[Wang et al. 2019] Wang S, Tuor T, Salonidis T, et al. Adaptive federated learning in resource constrained edge computing systems[J]. IEEE journal on selected areas in communications, 2019, 37(6): 1205-1221.

[Koloskova et al. 2020] Koloskova A, Loizou N, Boreiri S, et al. A unified theory of decentralized sgd with changing topology and local updates, ICML, PMLR, 2020: 5381-5393.

[Yang et al. 2021]Yang H, Fang M, Liu J. Achieving linear speedup with partial worker participation in non-iid federated learning. ICLR 2021.

[Wang and Ji 2022] Wang S, Ji M. A unified analysis of federated learning with arbitrary client participation. NeurIPs, 2022, 35: 19124-19137.

[Tang and Wong 2023] Tang M, Wong V W S. Tackling system induced bias in federated learning: Stratification and convergence analysis. INFOCOM, 2023: 1-10.

[Woodworth et al. 2020] Woodworth B E, Patel K K, Srebro N. Minibatch vs local sgd for heterogeneous distributed learning. NeurIPs, 2020, 33: 6281-6292.

[Li and Lyu 2024] Li Y, Lyu X. Convergence analysis of sequential federated learning on heterogeneous data. NeurIPs, 2024, 36.

2. Table of theoretical results

We conclude the convergence results in our paper as follows ($Q:=\sum_{n=1}^N\frac{1}{q_n}$):

Thank you for your valuable comments! Our response to your comments is as follows.

1. More comparing methods

We have included the benchmarks, i.e., FedProx and FedAdam, as suggested. We have used the same hyper-parameters, and trained the models on both CIFAR-10 and CIFAR-100. The results are provided in Figure 1 in the global rebuttal. From the figures, we observe that SFL-V2 continues to be the best performing algorithm. This is consistent with our observations in the main paper.

2. Explanation on the experimental results of CIFAR-10 and CIFAR-100

You are right. On CIFAR-100 we used 10 clients. Hence, after data sampling (with a Dirichlet parameter $\beta=0.1$), each client still has relatively many classes (out of 100), leading to similar performance as in CIFAR-10. We have conducted more experiments with 100 clients on CIFAR-100 using $\beta=0.1$, and the results are given in Figure 2 in the global rebuttal. The key observation is that the accuracy with 100 clients is generally lower than that with 10 clients, as expected. The reason is that each client has fewer types of classes, which can escalate the client drift issue during training.

3. Explanation on the experimental results of loss

The loss plot is based on the training set rather than the test set, which is why, in certain cases, the losses approach zero. We have also plotted the impact of the choice of cut layer on the SFL test loss, as shown in Figure 3 in the global rebuttal. In this figure, we observe that the test loss is higher than the training loss, highlighting the generalization gap and the effect of cut layer selection on model performance.

4. Limitation and future work of our paper

One limitation is that our bounds for SFL achieve the same order (in terms of training rounds) as in FL, yet the experiments showed that SFL outperforms FL under high heterogeneity. This is possibly due to that tighter bounds for SFL are to be derived, which is an important future work. Another limitation is that we did not include the theoretical analysis on how the choice of cut layer affects the convergence. For future work, we can apply our derived bounds to optimize SFL system performance, considering model accuracy, communication overhead, and computational workload of clients. We will add more detailed discussions of limitations and future work to the main paper.

Thank you for your valuable comments! Our response to your comments is as follows.

1. Diminishing stepsize for $\mu$-strongly convex loss functions

We use a diminishing stepsize of $\frac{4}{\mu\tilde{\tau}(\gamma+t)}$ and update the conditions specific to $\mu$-strongly convex loss functions. For these types of loss functions, Theorems 3.5 - 3.8 rely on the hypothesis that $\eta^t = \frac{4}{\mu\tilde{\tau}(\gamma+t)}$ for the client-side model, $\eta^t = \frac{4}{\mu\tau(\gamma+t)}$ for the server-side model, and $\eta^t \leq \frac{1}{2 S\tau_{max}}$. When $\gamma = \frac{8S}{\mu} - 1$, we have $\frac{4}{\mu\tilde{\tau}(\gamma+t)} \leq \frac{1}{2 S\tau_{max}}$ and $\frac{4}{\mu\tau(\gamma+t)} \leq \frac{1}{2 S\tau_{max}}$.

Thus, the hypotheses for the learning rate in different cases are as follows:

• $\mu$-Strongly Convex: $\eta^t = \frac{4}{\mu\tilde{\tau}(\gamma+t)}$ for the client-side model, $\eta^t = \frac{4}{\mu\tau(\gamma+t)}$ for the server-side model.

• General Convex: $\eta^t \leq \frac{1}{2 S\tau_{max}}$.

• Non-convex: $\eta^t \leq \frac{1}{2 S\tau_{max}}$.

Our proofs in the appendix (lines 534, 543, 607, 616, 668, 687, 746, 764) support this analysis.

It is important to note that these hypotheses apply to both SFL-V1 and SFL-V2, under full and partial participation of clients. Additionally, $\tilde{\tau} = \tau$ for SFL-V2. We will revise the presentation in our main paper accordingly.

2. Model aggregation

In SFL algorithms, the clients' local model parameters are aggregated according to equations (2) and (3) for full and partial participation, respectively. This process ensures unbiased model updates. Detailed model updates for both the server and clients in SFL-V1 and SFL-V2 can be found in Appendix C.2. Algorithms 1 and 2 describe the process for full participation only. We plan to revise these algorithms to include partial participation.

In our proof, we consider the features of model aggregation in different scenarios, as outlined in Appendix C.2 (page 15). Specifically, in line 453, which describes the model aggregation for SFL-V2 with partial participation on the server side, the parameter $a_n$ is not needed. This is because the main server updates the server-side model parameter sequentially with each client.

3. Performance comparison between FedAvg and SFL-V1

SFL characterizes dual-paced model aggregation. Specifically, in SFL-V1 and SFL-V2, clients communicate with the main server during every iteration (batch) for sequential model training. Additionally, clients communicate with the fed server every $\tilde{\tau} \geq 1$ iterations (batches) for client-side model aggregation. On the main server side, in SFL-V1, the main server aggregates the server-side models every $\tau \geq 1$ iterations (batches). In contrast, in SFL-V2, the main server does not need to aggregate the server-side model because there is only one server-side model.

In our experiments, we set $\tau = \tilde{\tau}$ to ensure a fair comparison with vanilla FL, i.e., FedAvg. Theoretically, the performance of SFL-V1 should be the same as FedAvg. However, our experiments show that FedAvg outperforms SFL-V1, especially when the data is non-iid distributed across clients, as shown in Fig. 5 (c) and (d).

The reason for this discrepancy lies in the optimizer used in our experiments. We added momentum to the SGD optimizer to stabilize and accelerate model training. In SFL-V1, there are two separate optimizers for the client-side and server-side models. In contrast, FedAvg uses only one optimizer, which provides better global momentum than SFL-V1. As a result, FedAvg performs slightly better than SFL-V1. This phenomenon is also noted in the original SFL paper [1].

We will revise the description of the experimental settings and results in our paper.

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

4. Limitation of our paper

One limitation is that our bounds for SFL achieve the same order (in terms of training rounds) as in FL, yet the experiments showed that SFL outperforms FL under high heterogeneity. This is possibly due to that tighter bounds for SFL are to be derived, which is an important future work. Another limitation is that we did not include the theoretical analysis on how the choice of cut layer affects the convergence. We will add the more detailed discussions of limitations to the main paper.

Thank you for your valuable comments. Our response to your comments is as follows.

1. Choice of $L_c$ and tradeoff

We use the ResNet-18 model in our experiments, which contains four blocks. This means the candidate for $L_c$ is in {$1,2,3,4$}. Thus, $L_c=4$ is already the maximum $L_c$ that can be chosen in SFL with ResNet-18 model. Our experimental results in Figure 2 show that increasing $L_c$ leads to higher model accuracy for SFL. However, the model accuracy of FL is similar to SFL-V1, and both are lower than SFL-V2 under high data heterogeneity. This suggests that even if computational resources allow, it is not always better to use FL than SFL. The main reason is as follows. Under high data heterogeneity, FL suffers from the notorious client drift issue, while SL suffers from the catastrophic forgetting problem. SFL (in particular SFL-V2) combines the training logic of FL (at clients) and SL (at server), which can help mitigate the issues of client drift and forgetting. Hence, SFL can lead to a better performance than both FL and SL.

On the other hand, as suggested in Table 3 of the Appendix, SFL-V1 and SFL-V2 may have higher communication overheads than FL when the number of training data and smashed layer size are large. Therefore, there is a tradeoff between model accuracy and total training time in SFL.

2. Algorithm details

The FL algorithm we use is FedAvg, and the SL algorithm we use is given in [Poirot et al. 2019]. We have also included more recent FL algorithms, i.e., FedProx and FedOpt, as additional comparison. The results are given as follows, which show that SFL-V2 outperforms FL and SL under high data heterogeneity. This is consistent with our main conclusion in the submission.

[Poirot et al. 2019] Poirot M G, Vepakomma P, Chang K, et al. Split learning for collaborative deep learning in healthcare. NeurIPs, 2019.

3. Plot presentation

We have adjusted the fonts and line sizes to make the plots more readable.

4. Limitation of our paper

One limitation is that our bounds for SFL achieve the same order (in terms of training rounds) as in FL, yet the experiments showed that SFL outperforms FL under high heterogeneity. This is possibly due to that tighter bounds for SFL are to be derived, which is an important future work. Another limitation is that we did not include the theoretical analysis on how the choice of cut layer affects the convergence. We will add the more detailed discussions of limitations to the main paper.