There are two categories of methods in Federated Learning (FL) for joint training across multiple clients: i) parallel FL (PFL), where clients train models in a parallel manner; and ii) sequential FL (SFL), where clients train models in a sequential manner. In contrast to that of PFL, the convergence theory of SFL on heterogeneous data is still lacking. In this paper, we establish the convergence guarantees of SFL for strongly/general/non-convex objectives on heterogeneous data. The convergence guarantees of SFL are better than that of PFL on heterogeneous data with both full and partial client participation. Experimental results validate the counterintuitive analysis result that SFL outperforms PFL on extremely heterogeneous data in cross-device settings.
Paper
Similar papers
Peer review
Summary
This paper presents an intriguing exploration of the counterintuitive comparison results between Sequential SL (SSL) and Federated Averaging (FedAvg) in the context of heterogeneous data. The authors attribute the surprising performance of SSL over FedAvg in worst-case scenarios to the assumption of data heterogeneity (Assumption 3), which is derived from the convergence theory of SGD. The paper provides a compelling argument and empirical evidence for the counterintuitive performance of SSL over FedAvg in certain scenarios. It offers valuable insights into the role of data heterogeneity in the performance of these algorithms and highlights the need for careful consideration of data heterogeneity in the design and analysis of federated learning algorithms. However, the paper could benefit from a more detailed discussion of the implications of these findings for real-world applications. Further exploration of the conditions under which SSL outperforms FedAvg, as well as potential strategies for mitigating the limitations of FedAvg in extremely heterogeneous settings, would be valuable.
Strengths
1. The paper provides a comprehensive theoretical analysis of the counterintuitive performance of Sequantial SL (SSL) over Federated Averaging (FedAvg) in certain scenarios. The author's exploration of the role of data heterogeneity and its impact on these algorithms is particularly insightful. 2. The authors validate their theoretical findings with empirical experiments, which strengthens the credibility of their claims. The use of one-dimensional quadratic functions for simulation and the consideration of practical scenarios in resource-constrained edge devices add depth to their research.
Weaknesses
1. The paper primarily focuses on the performance of Sequential SL(SSL) and Federated Averaging (FedAvg) in the context of data heterogeneity. While this focus is important, it might limit the generalizability of the findings. The performance of these algorithms could be influenced by other factors that are not considered in this paper. 2. While the paper does consider practical scenarios in resource-constrained edge devices, it could benefit from a more detailed discussion of the implications of its findings for real-world applications. Understanding how these findings could be applied in practice would add significant value to the paper. 3. The paper establishes that SSL outperforms FedAvg in extremely heterogeneous settings, but it doesn't dive deeply into why this is the case or how it could be mitigated. Further exploration of these areas would enhance the paper's contribution to the field.
Questions
While the paper provides a detailed convergence analysis for the newly proposed SSL algorithm, my primary concern lies in the experimental evaluation. The authors have chosen to use relatively simple and dated datasets and models, such as MNIST and CIFAR10 with LeNet and VGG-11. These models, being almost a decade old, may not accurately reflect the complexities and challenges of current practical workloads. To strengthen the paper, I recommend that the authors extend their experimental evaluation to include larger datasets and models. This would not only provide a more rigorous test of the SSL algorithm but also enhance the relevance and applicability of the research. If such larger experimental results can be provided, I would be inclined to increase my score by one point, as it would significantly improve the paper's contribution to the field.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Yes.
Summary
This paper studies the Sequential SL algorithm in which the at each round, sequentially, each machine performs some local SGD iterations, and then the final iterate is passed on to the next machine. Such an algorithm may be useful in cross-device, resource constrained settings, where local iterations are expensive.The papers compares the performance of this algorithm to the performance of Federated Averaging, where the local SGD iterations are performed in parallel rather than sequentially. They study a heterogenous data setting, where the distribution of data is different at each machine, under strongly convex, convex, and non-convex settings. While the SL algorithm has larger parallel depth than federated averaging, the authors show that the SSL algorithm outperforms FedAvg in the strongly convex setting. They also show some minor improvements in the convergence of Federated Averaging by reanalyzing this popular algorithm. They provide experiments in a heterogenous environment to show that for high levels of hetergeneity, SSL outperforms FedAvg without contradicting prior experimental evidence.
Strengths
- The authors provide a clean analysis of SSL under standard assumptions in strongly convex, convex, and non-convex settings. They also show how to slightly improve the analysis of FedAvg in a heterogeneous setting, which cleans up some small gaps between bounds in the literature. - The SSL algorithm they analyze is simple and natural, yet is not immediate to understand with existing analyses.
Weaknesses
*Clarity*: - The two last paragraphs on page 1 are somewhat confusing. The 2nd to last P seems to span about FedAvg. But then the last paragraph seems to speak about but SSL and about FedAvg (which is called SFLV1, which is confusing). Could the authors streamline these paragraphs to make it clear the two algorithms considered, and also clarify if SFLV1 = FedAvg or how they are different. - What does it mean that the model is trained partially at the server? I don't see this in Algorithm 1? - I find the emphasis on "counterintuitive" to be off-putting, because it seems natural that SSL, which is a sequentially deeper algorithm will perform better. - Could the authors make Assumption 3 clearer by breaking it into assumption 3a and 3b or break its into two assumptions environments. *Comparison to other theoretical results is confusing or sometimes misleading* - The discussion in the paragraph at line 154 is confusing. Perhaps a table would be helpful. Further, it is misleading that the authors say that their bounds are tight, because there seams to be a difference in depenence on M (which is quite significant), and anyways, the tightness would only be for the K = 1 case. - In the comparison to FedAvg (line 189 paragraph), the authors only discuss the strongly convex setting. Could they please explain the other cases too. The following paragraph (line 193) is quite confusing - I have no idea what the authors are saying. - In the discussion of heterogeneity and in the empirical experiments, the authors claim that SSL is better relative to FedAvg when there is more heterogeneity. But this does not completely make sense, because in the homogenous setting, where there is no heterogenity, SSL would be strictly better than FedAvg. Could the authors please discuss and clarify this.
Questions
See weakness above. Minor comment: Line 134 vanishes --> vanish
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
2 fair
Limitations
Yes
Summary
The authors provides the convergence analysis of a FL-like approach where clients updates the model sequentially based on local datasets. Results are provided for the strongly convex, convex, and non-convex case. Interestingly, the analysis shows that in some setting the sequential approach can outperform the usual FL approach where multiple clients update the local model in parallel and a server aggregates the updates. I do not understand why split learning is mentioned in the title and in the rest of the paper, as there is no model split across clients or across the clients and server as far as I can say.
Strengths
* The convergence analysis is interesting; it shows the authors master a number of existing techniques used to prove convergence results of distributed training procedures * the result about sequential training outperforming FedAvg is very interesting and indeed counterintuitive as observed by the authors * This was the best paper in my batch (6 papers)
Weaknesses
* The reference to split computing, while this paper does not deal with split computing. * The result about SSL outperforming FedAvg is interesting, but the paper does not provide any intuitive explanation about why this may be the case. Also the bounds suggest that it should always be the case in the strongly convex setting for any value of $\zeta^*$, not only in the highly heterogeneous setting (large $\zeta^*$). * I do not find the comparison with FedAvg under partial clients' participation fair. The authors should consider that at each round the clients available will sequentially perform SSL. Instead, they assume that all clients participate, but the reduce the total number of rounds. * there are some papers about the convergence of sequential optimization which should be cited. I think most of them consider a single gradient update at each node and focus on random walks. Examples: * Ram, S., Nedić, A., and Veeravalli, V. (2009). Incre- mental stochastic subgradient algorithms for con- vex optimization. SIAM Journal on Optimization, 20(2):691–717. * Johansson, B., Rabi, M., and Johansson, M. (2009). A randomized incremental subgradient method for dis- tributed optimization in networked systems. SIAM Journal on Optimization, 20(3):1157–1170 * Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., and Yin, W. (2020). Walkman: A Communication- Efficient Random-Walk Algorithm for Decentralized Optimization. IEEE Transactions on Signal Process- ing, 68:2513–2528. * Ayache, G. and Rouayheb, S. E. (2020). Private Weighted Random Walk Stochastic Gradient De- scent. Technical report, arXiv:2009.01790. * Cyffers, E., Bellet, A., Privacy amplification by decentralization, AISTATS 2022 * There are some sentence that are poorly worded, some examples * line 72: "it cannot follow the theory of SGD", rather "SGD theory does not apply" * line 120: "Or further, it only holds at the optimum.", it seems the authors mean. "In alternative, the condition is required only at a global minimizer" * line 126 and elsewhere: "making it hold that", simply "and it holds"? * line 188, what do the authors mean by "our comparison is persuasive"? * line 210, the section is not really about "feasability", it is just providing some numerical "evidence" tha the counterintuitive result can appear even for simple quadratic functions. As no intuitive explanation is provided, I think this section should be merged with the experiments one. * line 218, "which is tight to capture the gradient diversities", what the authors mean is that the bound may be pessimistic for fedavg where averaging can limitate the effect of statistical heterogeneity, but less for SSL because of its sequential nature. * Others: * line 67, (Wang et al, 2020) is indicated as an example dealing with unbalanced data, but I would say it rather deals with unbalanced computation. * line 67 trival -> trivial * line 114 and elsewhere: using assumption (4) to indicate the equation (4) in assumption 3 may be confusing * There are some papers which are cited as preprint, but have been published. For example Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion in non-iid federated learning appeared at ICLR 2021
Questions
* why do the authors refer to split computing? which model is split? Algorithm 1 shows well that all clients train the same model architecture. * what is denoted by SFLv1? if it denotes simply the algorithm proposed in (Thapa et al., 2020) just say it. Also in the rest of the paper, including in the experiment section, SFL is never evaluated, but he proposed solution is compared with FedAvg. * the paper suggests in different places that increasing the number of local iterations may have a beneficial effect at first and then be harmful, but in reality the bounds in the paper suggest that it is always beneficial to increase K but with a diminishing return, right? If so, some statements while commenting figure 2 should be modified.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes.
Summary
This paper provides the first theoretical convergence rates for sequential split learning (SSL) in the presence of heterogeneous data. In each round of SSL, a random permutation of the machines is computed. According to this permutation, each machine performs $K$ local gradient steps on the model sequentially. When the data on the clients is non-iid, due to the sequential nature of the steps, the updates are biased gradients of the true objective, which is the average of losses on all machines. This is the main challenge in analyzing SSL. The authors extend the proof of FedAvg to provide tight convergence rates for SSL on non-convex, convex and strongly-convex loss functions under standard assumptions of smoothness, bounded gradient noise and heterogeneity between machines. They show that SSL has strictly better convergence rates than FedAvg. In particular, the heterogeneity term in the rates decreases by a factor of $\frac{1}{M}$, where $M$ is the number of machines. They demonstrate the improvement of SSL over FedAvg empirically for quadratics under high heterogeneity. Additional experiments on CIFAR10 under high heterogeneity support this observation.
Strengths
- **Convergence rates** : Clean convergence results are provided under the same assumptions as FedAvg. For local steps, $K=1$, SSL is equivalent to Random Reshuffling, and the obtained convergence rates match its lower bound. - **Thorough comparison to FedAvg** : The authors provide thorough comparisons to the best possible rates for FedAvg under full participation and partial participation and demonstrate the improvement due to SSL. - **Experiments validate theory**: Synthetic experiments show a clear improvement of SSL over FedAvg in high heterogeneity conditions. - **Detailed Appendix** : There are several additional experiments in the appendix on more quadratic problems, MNIST and FMNIST, under varying hyperparameters. It might be beneficial to move one of these experiments to the main paper. - **Marginally better rates for FedAvg on strongly convex functions**: The authors obtain marginally better rates for FedAvg in terms of constants by combining two existing proofs.
Weaknesses
- **Analysis of Split learning without any explicit splits** : In SSL, or any form of split learning (Gupta and Raskar, 2018), a crucial component of the algorithm is the model being split into two parts, one for the server and one for the client. The analysis considers sequential local updates only without any form of splits in the model. This could be clarified in the introduction. - **Minor improvement in CIFAR10 figures**: This is a minor weakness, but Fig 2 is difficult to read. Using different color schemes for FedAvg and SSL or showing only 2 values of local steps might improve clarity. - **SSL as a case of FedAvg with partial participation** : Note that if we perform FedAvg with $S=1$ worker per round sampled without replacement for $R$ rounds, then this algorithm is same as running SSL for $R/M$ rounds. Could the analysis of FedAvg with partial participation then recover the same rates as this paper? **References** - (Gupta and Raskar, 2018) : Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications.
Questions
- A recent paper (Yun et al, 2022) considers Minibatch and Local SGD with Random Reshuffling. It would be interesting to compare its theoretical rates with SSL, which has close connections to Random Reshuffling. - Does the improvement in the rates for SSL over FedAvg come from a better bound on the client drift? **References** - (Yun et al, 2022) : Minibatch vs Local SGD with Shuffling : Tight Convergence Bounds and Beyond. ICLR 2022.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Described in Weaknesses
Thanks for your reply. I appreciate the new fairer comparison between sequential training and FedAvg. I still do not understand why the authors decided to frame their contribution in the split computing framework, as nothing seems really specific to split computing. Ok, the model is split between the client and the server in Algorithm 4, but the model is updated exactly how it would be in the classic federated learning setting. Simply some operations are executed at the client and others at the server. Am I right?
##### **R26: Nothing seems really specific to split computing.** Yes. As pointed out, the split computing in SSL only partitions the operations to be executed at clients and the server collaboratively. Our convergence results are also applicable to the classic distributed machine learning setting (where each client keeps one full model). To highlight, the main feature of our study is the convergence of sequential training manner (not the typical parallel training manner, i.e., Federated Learning) in distributed machine learning (not limited to the split learning). Thanks for the constructive comment. We understand that the comparison between sequential training and parallel training manners in distributed machine learning would be more general and may increase the impact of this paper. We will clarify the applicability of our convergence results in the revision. The reasons that we focus on the setting of sequential split learning (SSL) may include: + Sequential training manner is popular and widely adopted in SL (i.e., SSL considered in the original paper of SL (Gupta 29 and Raskar, 2018) [Ref 11]). SL is also the recent research hotspot. The convergence analysis of SSL is also of great practical and theoretical value. + The experimental settings (e.g., the "cross-device" setting and the "extremely heterogeneous" data partitioning) are more natural and practical in SL (designed for resource-constrained edge devices). [Ref 11] Gupta, O., & Raskar, R. (2018). Distributed learning of deep neural network over multiple agents. *Journal of Network and Computer Applications*, *116*, 1-8.
Thanks for the answer. Yes, I would really advise the authors to frame the whole paper in terms of sequential learning. I do not know how much it is possible at this stage (e.g., if it is possible to change the title). In any case, I think this is a good paper.
We would like to express our sincere gratitude for approving the quality of our paper. We will carefully consider your advice in the revision.
Additional Comments
Thanks for the rebuttal. The comparison to (Yun et al 2022) seems relevant and I would suggest including them in future versions of the paper. Some additional comments -- - **SSL as a special case of FedAvg with partial participation**: I made an error when comparing FedAvg with partial participation to Algorithm 1 and apologize for this. Algorithm 1 is FedAvg with client selection similar to "randomized reshuffling" and cannot be equivalent to any version of FedAvg with partial client participation. - **Comparison to Randomized Reshuffling**: Is there a reason why the optimization term of Algorithm 1 is worse than Randomized Reshuffling by a factor of $M$? - **Algorithm 1 v/s SSL**: I would suggest the authors should use SSL only as motivation as Algorithm 1 is basically Sequential FL or FedAvg with "randomized reshuffling" client selection.
Thanks for the careful proofreading. The responses to the additional comments are provided below. **R27: More detailed comparison to Random Reshuffling** The reason is that Theorem 1 in Mishchenko et al. (2020) [Ref 5] for the bound of Random Reshuffling (RR) applied one meticulously designed technique (i.e., introducing their Definition 2, Shuffling variance), which yet can not be applied to the convergence analyses of Algorithm 1 (with multiple local steps). The details (combined with our proof) are as follows: + The difference in the optimization term arises from the constraint of the learning rate. For Algorithm 1, the constraint (upper constraint) of the strongly convex case in Theorem 1 is $\eta \leq \mathcal{O}(\frac{1}{{\color{red}M}L})$ when $K=1$. In contrast, for RR, the constraint of Mishchenko et al. (2020)'s Theorem 1 is $\eta\leq \mathcal{O}(\frac{1}{L})$. As a larger value of $\eta$ leads to better convergence rate in the optimization term (Please refer to our Lemma 7, tuning the learning rate, in Appendix B.2), the difference of the learning rate constraints causes the worse bound (by a factor of $M$) of Algorithm 1 than RR. + The tougher constraint of the learning rate in Theorem 1 (Algorithm 1) arises from bounding the client drift error (Please refer to our Lemma 6, Bounding the client drift, in Appendix B.2). Mishchenko et al. (2020) introduced the shuffling variance (see their Definition 2) to bypass bounding the client drift error (they called it as "deviation"). Such technique leads to the relaxed learning rate constraint ($\eta \leq \mathcal{O}(\frac{1}{L})$) and better optimization term ($\tilde{\mathcal{O}}\left(D^2 \exp(-\frac{\mu {\color{red}M}R}{L})\right)$) for RR than that (the constraint $\eta \leq \mathcal{O}(\frac{1}{{\color{red}M}L})$ and the optimization term $\tilde{\mathcal{O}}\left(D^2 \exp(-\frac{\mu R}{L})\right)$) for Algorithm 1. However, it is hard to apply this trick to our Theorem 1 due to multiple local steps in Algorithm 1. + We also want to highlight that, in the general convex and non-convex cases (not the strongly convex case above), our convergence bounds (Theorems 1 and Corollary 1) for Algorithm 1 (when $\sigma=0$ and $K=1$) are identical to the bounds of RR (Theorems 3, 4 in Mishchenko et al. (2020)). This is because the introduced shuffling variance technique is not applicable (and not used) in the general convex and non-convex cases in Mishchenko et al. (2020). We will provide more discussions about these two cases in the revision. --- **R28: Clarification for the other additional comments** + *Discussion about Yun et al, (2022)*. We will include the discussion about Yun et al, (2022) [Ref 1] in the revision as suggested. + *SSL as a special case of FedAvg with partial participation*. As pointed out, Algorithm 1 is similar to Random Reshuffling (RR) and cannot be equivalent to FedAvg with partial participation in the scope of this paper. We will add more comparison analysis with RR in the revision (as stated in R27 above). + *Algorithm 1 v/s SSL*. As suggested, we will clarify the difference between Algorithm 1 and SSL, and the applicability of our convergence results in the revision.
I have read the reply of the authors, thank you!
please acknowledge author response
dear reviewer as the discussion phase is ending very soon: could you please let us know if you read the author response and if the response or the discussions here change your assessment? thanks AC
I thank the authors can provide experiments on larger datasets. After reading the comments and rebuttals in other reviewers, I decided to increase my score to 6.
Decision
Accept (poster)