Which mode is better for federated learning? Centralized or Decentralized

7. About the question of "Table 1 indicates disparate generalization errors between under full-connection in DFL and CFL":

Sorry for the misunderstanding here. In the scenario of a fully connected network, DFedAvg reduces to FedAvg. From our analysis of generalization, we can see:

Therefore, the full-connection topology in DFL shows the same generalization performance as all participantion in CFL.

What is the meaning of Table 1?

Table.1 considers the joint performance of excess risk, which is, the sum of optimization errors and generalization errors. From the perspective of excess risk, we provide the best selection of active ratio ($n$ in CFL) and best topology (in DFL) respectively in Table 1. Under the best selections of each framework, we also show their generalization performance. Table 1 indicates that in FedAvg, from the excess risk perspective, we do not need all clients to participate in per communication round ($n< m$). Only when $n=m$, FedAvg is equal to the DFedAvg under full-connection topology.

It is a pleasure to discuss this with you, which will help us to further improve this work. We will add all citations in the rebuttal and add a paragraph to summarize the development of decentralized approaches. We compare the mentioned studies with our work in Answer.4. We clarified the misunderstanding of generalization conclusions in Answer.7. If there are any other questions or concerns, we are happy to continue the discussion with you. Thank you again for reading this rebuttal.

4. About the question of "How does the generalization analysis presented in this study differ from that of DSGD without local updates as detailed in [1,2,3]:":

We summarize the difference as follows.

(1) All analysis in [1] only is suitable for the convex function (Assumption 2 in their paper.) In their conclusions, they mentioned "We believe our work opens several directions, with perhaps the most exciting one being the analysis of non-convex objectives.". And, Our analysis targets the smooth and non-convex objectives.

(2) To compare to [2], we provide a table in the following.

First of all, in our proofs, we remove the strong assumption of the Lipschitz function (which indicates the gradient must be upper bounded) in the stability analysis. Bounded gradients force each iteration to be still upper bounded. However, many previous studies learn that this assumption may not always hold, especially in current deep learning models. Our proofs indicate that even the iterations are not necessarily bounded, the final stability is still bounded.

Furthermore, in their Theorem 3.1, 3.2, and 3.3, the stability bound is not related to the spectral gap or information of topology. One of the main targets of the research in decentralized methods is to understand the impact of topology on the final performance. Our paper provides the stability analysis with the topology coefficient, which is dominated by $\mathcal{O}(\left(\frac{1+6\sqrt{m}\kappa_\lambda}{m}\right)^\frac{1}{1+\mu L})$, where $m$ is the number of the total clients and $\kappa_\lambda$ is the coefficient related to the spectral gap $\lambda$. Furthermore, we derive the dominant factors of the partial participation in FL to be $\mathcal{O}(\frac{n^\frac{\mu L}{1+\mu L}}{m})$. These theorems in our paper can fairly compare the performance differences between CFL and DFL under the same assumptions.

(3) [3] not only must rely on the strong assumption of the Lipschitz function, but also require a additional assumption: "the weight differences at the $t$-th iteration are multivariate normally distributed, $w_{1,k}^t-w_{2,k}^t\sim\mathcal{N}(\mu_k^t,\sigma_{t,k}^tI_d)$" (Assumption A.4 in their paper). This assumption is too strong for the stability analysis because it forces the parameters of all layers to be normalized bounded. Compared with their work, we do not require any extra assumptions on the stability analysis, which could be more general in the current deep learning community.

[1] On generalization of decentralized learning with separable data

[2] Improved Stability and Generalization Analysis of the Decentralized SGD Algorithm

[3] Topology-aware generalization of decentralized sgd

5. About the question of "Furthermore, the bounds presented in theorems 1 and 2 demand a comprehensive explanation.":

Thank you for pointing out this issue and we will add more details to demonstrate our theorem 1 and 2. Actually, the most important part is the active coefficient part (related to $n$, $m$, and $\kappa_\lambda$), which reflects the essential difference between CFL and DFL. Our five main conclusions are also derived from the derivation according to this part. Sorry for the impact on reading, we will add some texts to explain the results of stability analysis, which is proposed in [1].

[1] Train faster, generalize better: Stability of stochastic gradient descent (ICML2016)

6. About the question of "What is small $k$ in theorem 1?":

We will add a notation table in section 3 to introduce all marks in our paper. $k$ is the index of the local training iteration, which is limited within $[1, K]$.

Thank you very much for your review and affirmation of our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.

1. About the question of "Table 1 is presented without an explanation of its significance and implications":

Thank you for pointing out this and we are very sorry for the inconvenience with Table 1. We will add a paragraph in the introduction section to describe them in detail.

Actually, Table 1 summarizes the excess risk of FedAvg and DFedAvg. From the excess risk perspective, the best partial participation ratio in CFL is $\frac{n}{m}=\mathcal{O}(m^{-\frac{\mu L}{1+2\mu L}})$ and the best topology in DFL satisfies $\kappa_\lambda=0$. Under their best selections respectively, the generalization in CFL achieves $\mathcal{O}(m^{-\frac{1+\mu L}{1+2\mu L}})$ and the generalization in DFL achieves $\mathcal{O}(m^{-\frac{1}{1+\mu L}})$.

2. About the question of "this work lacks a thorough review of related literature, including [1,2]":

Thank you for pointing out this and we are sorry for causing you misunderstanding. We do not attribute the DFedAvg framework solely to any single work because it has been studied for a long time. [3] summarizes and provides an optimization convergence on the decentralized heterogeneous dataset in the FL framework which is explicitly targeted at DFL scenarios under the general assumptions widely used in the current FL community.

The mentioned paper [2] has been cited in our paper (page 3 paragraph "Decentralized federated learning"). The mentioned paper [1] mainly focuses on the optimization convergence of local-update-SGD under different paradigms. Our paper mainly focuses on the generalization difference between CFL and DFL. We will add [1] to the related work to further summarize the development of the decentralized approaches.

[1] Cooperative SGD: A Unified Framework for the Design and Analysis of Local-update SGD Algorithms (JMLR2021)

[2] A Unified Theory of Decentralized sgd with Changing Topology and Local Updates (ICML2020)

[3] Decentralized Federated Averaging (TPAMI)

3. About the question of "Similarly, numerous studies have explored DSGD, its model consistency, and have proposed corrective methods, including [1,2,3,4,5,6]":

I am very grateful to the reviewer for mentioning several extensions of decentralized approaches.

First of all, I would like to clarify the main target of our paper. We do not focus on proposing a new decentralized method. Our study mainly attempts to answer a question mentioned in the introduction: "Which framework is better for federated learning? Centralized or decentralized?". Several studies have learned the convergence rate in decentralized approaches could achieve a comparable optimization convergence rate as the centralized approaches. However, its performance in empirical studies is always not as good as we expected. This motivated us to explore the generalization performance. Therefore, we focus the related work targeted more on the generalization and stability analysis in decentralized methods. But all mentioned papers [1,2,3,4,5,6] focus more on the convergence analysis in their papers.

In order to dispel the reviewer's concerns, we will add a new paragraph in related work to introduce the development of both the centralized and the decentralized approaches including all missed work mentioned in the rebuttal. Thank you again for pointing out this issue.

[1] On the influence of bias-correction on distributed stochastic optimization

[2] Extra: An exact first-order algorithm for decentralized consensus optimization

[3] A unified and refined convergence analysis for non-convex decentralized learning

[4] Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!

[5] On the performance of gradient tracking with local updates

[6] Local Exact-Diffusion for Decentralized Optimization and Learning

2. About the question of "This paper does not show how the heterogeneity affects the generalization error.":

Thank you for pointing out this question and it may be a misunderstanding on the stability analysis.

(1) The work [1] mentioned by the reviewer also does not show the heterogeneity impacts. Furthermore, many existing generalization studies in FL also do not involve the heterogeneity impacts [2,3,4].

(2) The stability analysis mainly explores the potential model differences when it is trained on two different datasets. The heterogeneity measures the quality and similarity of the local dataset, which mainly affects the optimization convergence, that is, the efficiency to achieve the optimal state. While stability does not care about the final state. In other words, even if the model converges very poorly on a very poor dataset, it may still maintain good stability because the stability is largely decided by the training algorithms. And the final test accuracy is decided by both the optimization errors and stability errors. Therefore, the quality of the dataset is not important for the stability analysis. That's why most of the previous studies of the generalization analysis in FL do not involve heterogeneity.

[1] Generalization Bounds for Federated Learning: Fast Rates, Unparticipation Clients and Unbounded Losses (ICLR2023)

[2] A Robust Federated Learning: The Case of Affine Distribution Shifts (NIPS2020)

[3] Generalized Federated Learning via Sharpness Aware Minimization (ICML2022)

[4] Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization (NIPS2023)

3. About the question of "When the communication graph is fully connected, DFedAvg becomes FedAvg. But the generalization error of this paper does not have this relationship.":

Thank you for pointing out this and this is a misunderstanding. We will provide a table to introduce their relationships in the following.

When the topology is fully connected in DFL, all clients will aggregate the model after the local training. Therefore, it is equivalent to all participation in CFL which indicates $n=m$. Their generalization is the same. Hope this table can avoid this misunderstanding.

It is a pleasure to discuss this with you, which will help us to further improve this work. We compare in detail the mentioned papers with our paper in Answer.1, explain the issues of heterogeneity terms in Answer.2, and provide a table to avoid misunderstanding in Answer.3. If there are any other questions or concerns, we are happy to continue the discussion with you. Thank you again for reading this rebuttal.

Thank you very much for your review and valuable comments on our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.

1. About the question of "it is not clear what new contributions this paper compared with [2,3]":

(1) Our contributions: Firstly thank you for pointing out these related works. There are really many independent studies based on centralized or decentralized approaches. However, to our best knowledge, there is no complete conclusion to indicate which one of them performs better in the FL framework. Since [1] learns D-PSGD could achieve comparable convergence as C-PSGD, it is generally believed that the decentralized methods will achieve the same performance as the centralized methods. However, decentralized experimental performance has always been poor. Therefore, we want to learn their stability under the same general assumptions via the same analysis framework to fairly compare their generalization performance. Our paper completes the further exploration of the comparison within these two modes in FL. Meanwhile, we also find some novel and interesting conclusions based on the stability and excess risk analysis. We summarize them in the following table.

(2) Let us summarize a simple comparison between our work and the mentioned work [2,3]. Though they focus on the exploration of centralized or decentralized stability, they are still largely different from our work.

First of all, in our proofs, we remove the strong assumption of the Lipschitz function (which indicates the gradient must be upper bounded) in the stability analysis. Bounded gradients force each iteration to be still upper bounded. However, many previous studies learn that this assumption may not always hold [4,5,6,7], especially in current deep learning models. Our proofs indicate that even the iterations are not necessarily bounded, the final stability is still bounded.

[2] introduces several additional assumptions to analyze the unparticipated clients without bounded losses, but this analysis does not guide us in understanding whether CFL or DFL is better. [3] provides an analysis of D-SGD, but in their Theorem 3.3, the stability bound is not related to the spectral gap or information of topology. One of the main targets of the research in decentralized methods is to understand the impact of topology on the final performance. Our paper provides the stability analysis with the topology coefficient, which is dominated by $\mathcal{O}(\frac{1+6\sqrt{m}\kappa_\lambda}{m})$, where $m$ is the number of the total clients and $\kappa_\lambda$ is the coefficient related to the spectral gap $\lambda$. Furthermore, we derive the dominant factors of the partial participation in FL to be $\mathcal{O}(\frac {n^\frac{\mu L}{1+\mu L}}{m})$. These two theorems in our paper can fairly compare the performance differences between CFL and DFL under the same conditions.

[1] Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (NIPS2017)

[2] Generalization Bounds for Federated Learning: Fast Rates, Unparticipation Clients and Unbounded Losses (ICLR2023)

[3] Improved Stability and Generalization Analysis of the Decentralized SGD Algorithm (arXiv2023)

[4] The Lipschitz Constant of Self-attention (ICML2021)

[5] Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness (ICML2021)

[6] Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradients: Convergence, Divergence and Limitations of Its Continuous Approximation. (arXiv)

[7] Beyond Uniform Lipschitz Condition in Differentially Private Optimization (ICML2023)

Thank you for the review. Due to rebuttal time constraints, we have not received any response yet. We want to know if our rebuttal resolves the original misunderstanding.

3. About the question of "the proof heavily relies on those in [2] with some modification in the later recursion":

We disagree with this point. Uniform stability analysis in deep learning is proposed by [1,2] and has been widely used in a lot of previous studies to analyze various algorithms [3,4,5,6]. As a good analysis framework, many classic conclusions in generalization are obtained based on this analysis. Furthermore, we must emphasize our additional contributions in this work:

(1) To our best knowledge, this is the first work to prove uniform stability without adopting the assumption of Lipschitz continuous function (bounded gradient assumption). Many previous studies have learned the Lipschitz function assumption is too strong in deep models which may not always hold. Our work further refines the uniform stability analysis.

(2) We focus on fairly understanding the difference in generalization performance between CFL and DFL with the help of a uniform stability framework. This is not a simple incremental work. We not only prove that the generalization performance of DFL is always worse than CFL but also find a novel conclusion, that is, in the DFL scenarios, the topology still has a theoretical minimum requirement to avoid the collapse (summarized in the Table in Answer.1). We also conduct empirical studies to validate the conclusions proposed in our paper. Both theoretical analysis and experiments confirm our conclusions.

(3) Beyond [2], we analyze how the topology affects the generalization in DFL, and how active ratio affects the generalization in CFL. In our analysis, we can effectively compare the generalization efficiency of CFL and DFL and give strict theoretical differences in the stability and generalization performance.

[1] Stability of Randomized Learning Algorithms. (JMLR 2005)

[2] Train Faster, Generalize Better: Stability of Stochastic Gradient Descent (ICML2016)

[3] Uniform Stability for First-Order Empirical Risk Minimization (NIPS2018)

[4] Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent (ICML 2020)

[5] Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond (NIPS2021)

[6] Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization (NIPS2023)

4. About the question of "some typos":

We will fix all $\Vert f() - f()\Vert$ to $\vert f() - f()\vert$ and add a notations table in Section 3 to summarize all marks in this paper. Thank you again for pointing out this issue.

It is a pleasure to discuss this with you, which will help us to further improve this work. We explain some misunderstanding about the assumption of PL-condition and selection of learning rate in Answer.1 and .2 and summarize the novelty of our work in Answer.3. If there are any other questions or concerns, we are happy to continue the discussion with you. Thank you again for reading this rebuttal.

Thank you very much for your review and valuable comments on our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.

1. About the question of "All discussions must rely on PL-condition:"

(1) We first would like to clarify the misunderstanding about the PL-condition and our paper. Our main theoretical contribution is to fairly compare the generalization performance between CFL and DFL via the same analysis framework under the same assumptions. Though we mentioned comparing their excess risk, however, most of our conclusions provided in our paper are based on the stability comparison, which never adopts the PL-condition. So we think the comment "so all in all the study and follow-up discussion comparing CFL and DFL in fact focuses on PL functions only" is very inaccurate. Here we make a table in the following to summarize our main novel conclusions and the conditions required.

From the above table, we can clearly see that in the five main conclusions in our paper, four of them do not rely on the PL-condition. Therefore, we object to the statement that our discussion is limited to the PL-condition only.

(2) In the excess risk, the test error is bounded by the sum of optimization error and generalization error, which is $\varepsilon_e=\varepsilon_{gen}+\varepsilon_{opt}=\mathbb{E}[F(w^T)-f(w^T)] + \mathbb{E}[f(w^T)-f(w^\star)]$. Current non-convex analysis only provides the $\frac{1}{T}\sum_t\Vert\nabla f(w^t)\Vert^2$ term is upper bounded. Therefore, in many studies of analyzing the excess risk, to approximate the bound of $\varepsilon_{opt}=\mathbb{E}[f(w^T)-f(w^\star)]$ term, many additional assumptions are adopted. We follow the studies [1,2] to select the PL-condition to provide the $\varepsilon_{opt}$ term.

[1] Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond (NIPS2021)

[2] Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization (NIPS2023)

2. About the question of "learning rate selections are different in optimization and generalization":

(1) The same as the answer above, in the five main conclusions in our paper, only one relies on the combination of optimization and generalization errors. Therefore, the other four conclusions about CFL and DFL in the main body of the paper do not face the issue of different selections of the learning rate.

(2) Previous work [1] has succeeded in analyzing the efficiency of the "lookahead" via the excess risk. In Section 4.3 in [1], they introduce the learning rate is selected as $\mathcal{O}(\frac{1}{t})$ in optimization under smoothness and PL-condition in non-convex objectives. In Section D.5 (proof of generalization on page.13) in [1], they clearly introduce that the learning rate is selected as $\mathcal{O}(\frac{1}{t-1})$ in generalization. The selections of the learning rate are the same in both optimization and generalization. The same, in our paper, we follow the same selection and let the learning rate be $\mathcal{O}(\frac{1}{t})$ in generalization analysis. In the non-convex federated optimization analysis, under the smoothness and PL-condition, the learning rate is selected as $\mathcal{O}(\frac{\log{t}}{t})\approx\mathcal{O}(\frac{1}{t})$, which is basically consistent with the generalized analysis [2].

[1] Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond (NIPS2021)

[2] Decentralized Federated Averaging (TPAMI)

Thank you for the review. Due to rebuttal time constraints, we have not received any response yet. We want to know if our rebuttal resolves the original misunderstanding.

Thank you very much for your review and affirmation of our work. We'll answer your questions one by one in the following, including some misunderstandings and some essential academic questions worth exploring. We are also very honored to share some of our understandings with you.

1. About the question of "Some notations are not defined in the main body":

Thank you for pointing this and we are very sorry that some missing notation definitions have caused difficulty in reading and we will add a comprehensive notation table to clarify each symbol.

2. About the question of "The paper seems to require the sample gradient to be Lipschitz":

We are very grateful to the reviewer for checking our proof section and we will fix Assumption 1 to a sample gradient formation. Lemma 6 in our paper refers to Lemma 1.1 in [1] and the expansion of Lemma 3.6 in [2]. In the study of stability analysis, Lemma 6 in our paper is a very general recursive formula and many classical works adopt this property to upper bound the difference on the same data sample.

[1] Towards Understanding Why Lookahead Generalizes Better Than SGD and Beyond (NIPS2021)

[2] Train faster, generalize better: Stability of stochastic gradient descent (ICML2016)

It is a pleasure to discuss this with you, which will help us to further improve this work. We explain some concerns mentioned in the reviews. If there are any other questions or concerns, we are happy to continue the discussion with you. Thank you again for reading this rebuttal.