Generalization Performance Gap Analysis between Centralized and Federated Learning: How to Bridge this Gap?

Thanks for reviewing our paper. We appreciate the time and effort you have dedicated to helping us improve our work. Below are our responses to the points you raised:

• For Weaknesses:
  1. Thank you for providing us with these papers. While these studies also explore the generalization of algorithms, their focuses differ from ours. Specifically, $(a)$ the first and second papers aim to understand and improve the generalization ability of federated learning but do not consider comparisons with centralized scenarios; $(b)$ the third paper compares the generalization performance of two different types of federated learning. Moreover, the third paper was published on arXiV after our submission to ICLR, so we were unable to include it in our original submission. In the final version, we will include the three papers in our related work section.
  2. The convex assumption about the loss function (Assumption 2) is a standard assumption in studies exploring the generalization ability of stochastic algorithms [1, 2]. This assumption makes sense when the loss function is smooth and the stochastic process stabilizes into a low-variance quasi-stationary distribution near a deep local minimum. Its validity has been supported by empirical evidence (see [3, p.1, Figures 1(a) and 1(b), and p.6, Figures 4(a) and 4(b)]). While this assumption simplifies the analysis, it does not fundamentally alter the geometry of the objective function or the resulting generalization ability. General cases can be obtained by translation operations.
  3. Thank you for raising this important concern. Our theoretical results are based on the IID assumption, ensuring that the proposed strategies are feasible if the new training data is drawn from distributions similar to the existing data. However, if the new data has significantly different distributions, the situation becomes more complex. While our current analysis does not directly address the non-IID case, we can provide a reasonable hypothesis based on our theoretical framework. Specifically, transitioning from an IID to a non-IID setup would affect Assumption 4 but keep the other setups unchanged, leading to $|A-\bar{A}|^2 \leq \alpha$ and $|\frac{1}{n^\gamma}C - \bar{C}|^2 \leq \beta$, where the hyper-parameters $\alpha \geq 0$ and $\beta \geq 0$ represent the degree of non-IIDness. Under this new assumption, the term $\text{tr}(CA^{-1})$ in Eq.(17) would be reformulated as $\text{tr}(\bar{C}\bar{A}^{-1}) - \text{tr}(CA^{-1}) = \text{tr}(\bar{C}\bar{A}^{-1} - CA^{-1}) \leq \frac{\beta}{n^\gamma}\alpha$. This implies that the generalization gap between the two scenarios increases as the level of non-IIDness grows. Consequently, introducing new training data with distinct distributions in practice would simultaneously decrease the generalization gap (by increasing total data size) and increase it (due to the heightened non-IID level across clients). Since the denominator of Eq.(17) does not include $\text{tr}(CA^{-1})$, our proposed strategies still have the potential to bridge the gap, while the effectiveness would depend on the magnitude of the increase in the degree of non-IIDness across local datasets.
• (Q1) The lower and upper bounds in Theorem 3 are necessarily positive if Assumption 5 is satisfied. This assumption generally holds in current studies, as state-of-the-art models are typically over-parameterized to achieve superior performance, and federated scenarios often involve a large number of clients.
• (Q2) By introducing new clients or additional data, the total data size $mn$ in the federated scenario will increase and can exceed the total data size $D$ in the centralized scenario.
• (Q3) In Figure 1, the experimental results compare the federated and centralized scenarios under equal training conditions. Therefore, the total data size across all clients is kept equal to the total data size in the centralized scenario and remains unchanged throughout the experiments.

[1] Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1–35, 2017.

[2] Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in neural information processing systems, 32, 2019.

[3] Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.

Thanks for reviewing our paper. We appreciate the time and effort you have dedicated to helping us improve our work. Below are our responses to the weaknesses and questions you raised:

• Our theoretical results are applicable to scenarios where clients perform multiple rounds of local updates, denoted as $t$ in our paper. Here, $t$ can be any positive integer. We consider the impact of $t$ on local SGD updates by including it in the analytic solution of the output hypothesis of federated SGD (Eq.(14)). The theoretical expressions for the generalization bounds (Eqs.(13) and (15)) and the performance gap (Eq.(17)) do not include $t$ as $t$ is simplified through integral operations in the proofs. For further details, please refer to Eqs.(30) and (44) in the Appendix, where this simplification is explained more thoroughly.
• Assumption 2 is standard on papers studying the generalization ability of stochastic algorithms [1,2], which makes sense when the loss function is smooth and the stochastic process reaches a low-variance quasi-stationary distribution around a deep local minimum. This assumption has been primarily demonstrated by empirical works (see [3, p.1, Figures 1(a) and 1(b) and p.6, Figures 4(a) and 4(b)]). General cases can be obtained by translation operations, which would not change the geometry of the objective function and the corresponding generalization ability.
• The technical contributions of this paper are clarified as follows:
  • A novel perspective on the generalization gap: Unlike previous works that primarily focus on empirical observations, our paper offers a new theoretical view to analyze the generalization gap. Specifically, we demonstrate that the gap can be formally expressed as the difference between the PAC-Bayes generalization bounds of two scenarios. While PAC-Bayes theory has been extensively studied, this connection between the generalization gap and PAC-Bayes bounds is novel. Furthermore, our derivation reveals how training differences between scenarios lead to the gap, addressing an under-explored question in prior research.
  • Understanding the impact of training parameters: Our derived lower and upper bounds offer valuable evidence for understanding how training parameters influence the generalization gap. Specifically, $(a)$ a gap necessarily exists between centralized and federated scenarios when training conditions are identical; $(b)$ the gap decreases with the number of training rounds $T$ but cannot be entirely eliminated by increasing $T$; $(c)$ the gap increases with the number of clients $n$ and the model size $d$. While previous studies have reported similar trends empirically, they lacked a theoretical foundation to explain why these results occur or whether they hold generally. Our work addresses this gap, providing greater clarity and justifying generality.
  • Guidance on bridging the gap: Beyond identifying the existence and characteristics of the generalization gap, our results offer actionable insights for addressing it. We identify feasible and infeasible strategies for reducing the gap, helping future research focus on promising directions while avoiding ineffective approaches. This guidance enhances the practical relevance of our theoretical contributions.

[1] Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1–35, 2017.

[2] Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in neural information processing systems, 32, 2019.

[3] Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.

Thanks for reviewing our paper. We appreciate the time and effort you have dedicated to helping us improve our work. Below are our responses to the weaknesses and questions you raised:

• Thank you for this suggestion. In the final version, we will revise the introduction to more prominently highlight our technical contributions. The key technical contributions are clarified as follows:
  • A novel perspective on the generalization gap: Compared to the previous studies, our work shows a novel perspective to analyze the generalization gap. Specifically, we demonstrate that this gap can be theoretically defined as the difference between the PAC-Bayes generalization bounds of two scenarios. While PAC-Bayes theory has been extensively studied, this connection between the generalization gap and PAC-Bayes bound has not been previously established. Besides, the derivation of this theoretical expression reveals how the generalization gap resulted from the training differences between the two scenarios, filling an under-explored aspect in previous works.
  • Understanding the impact of training parameters: In addition, our derived lower and upper bounds provide a deeper understanding of the factors influencing the generalization gap. Specifically, $(a)$ a gap necessarily exists between the centralized and federated scenarios if two scenarios are provided with equal training conditions; $(b)$ this gap decreases with the number of training rounds $T$ but cannot be completely closed by increasing $T$; $(c)$ this gap increases with the number of clients $n$ and the model size $d$. While previous works have reported similar results, their conclusions were summarized from the experimental results, so they were unable to explain the underlying causes or establish their general applicability. Our work fills this gap by offering a clear explanation and validating the generality.
  • Guidance on bridging the gap: Beyond identifying the existence and properties of the gap, our work provides valuable guidance on strategies for closing it. Specifically, we distinguish between feasible and infeasible approaches for reducing the gap. These insights help future research focus efforts on promising directions, avoiding wasted resources on approaches that are theoretically non-viable.
• Our theoretical results can apply to different numbers of local updates (denoted by $t$). The theoretical expressions for the generalization bounds (Eqs.(13) and (15)) and the performance gap (Eq.(17)) do not include $t$ because $t$ is simplified through integral operations in the proofs. See Eqs.(30) and (44) in the Appendix for more details.

Thanks for reviewing our paper. We appreciate the time and effort you have dedicated to helping us improve our work. Below are our responses to the weaknesses and questions you raised:

• (Q1 and W1) Compared to the training dataset, the test dataset is often unknown and subject to much greater uncertainty. Without knowing the latent distribution of the test data, the test loss $R$ is not available and cannot be directly used to evaluate the generalization ability of an algorithm. Therefore, it is common practice to use the available training loss $\hat{R}$ to estimate $R$. A well-generalizing algorithm will have a small difference between $\hat{R}$ and $R$, termed the generalization error. This approach is standard in studies on the generalization ability of stochastic algorithms [1,2], and we adopt this definition in our paper. Furthermore, the lower bound indicates the possible minimum generalization error, corresponding to the outcome under ideal conditions. However, due to the uncertainty in the test dataset, such ideal outcomes are rarely achieved. In contrast, the upper bound provides a conservative and robust estimate of the generalization performance, making it more practical for managing the risk of inaccurate estimation.
• (Q2 and W2) Our theoretical analysis supports any positive integer $t$ for the number of local updates. The generalization bounds (Eqs.(13) and (15)) and the performance gap (Eq.(17)) do not explicitly include $t$ because it is simplified through integration during the proof. Detailed explanations can be found in the Appendix (see Eqs.(30) and (44)). Moreover, federated SGD and centralized SGD differ significantly even when $t=1$. Federated SGD operates on decentralized data and involves local SGD updates and aggregation of local models in each iteration. These distinctions lead to different training outcomes between the two approaches, making the bound of the generalization gap not vanish.
• (Q3 and W4)
  • Our theoretical analysis and experiments do not examine the non-IID case as we adopt the IID setup to simplify the comparison problem. We plan on studying the impact of non-IID data on the generalization gap in future work. Based on our current theoretical analysis, we guess that our theoretical results may extend to the non-IID case with some modifications. Specifically, a non-IID setup would affect Assumption 4 while leaving other setups unchanged, resulting in $|A-\bar{A}|^2 \leq \alpha; |\frac{1}{n^\gamma}C - \bar{C}|^2 \leq \beta$ where $\alpha \geq 0$ and $\beta \geq 0$ quantify the degree of non-IIDness. Following this new assumption, the term $\text{tr}(CA^{-1})$ in Eq.(17) will be re-formulated as $(\text{tr}(\bar{C}\bar{A}^{-1}) - \text{tr}(CA^{-1})) = \text{tr}(\bar{C}\bar{A}^{-1} - CA^{-1}) \leq \frac{\beta}{n^{\gamma}}\alpha$, implying that the generalization gap between two scenarios increases with the non-IID level. However, as the denominator of Eq.(17) does not include $\text{tr}(CA^{-1})$, we can recognize that the proposed two strategies that increase the total training data in federated scenarios still have the potential to bridge the gap.
  • We agree that the learning rate affects the generalization ability of an algorithm, as supported by prior work [2]. However, our experiments are designed to validate the correctness of our theoretical results. To align with the problem setup in our theoretical analysis, we use identical learning rates for both centralized and federated scenarios. Additionally, adjusting the learning rate of federated learning to its optimal value would represent a best-case scenario for the generalization gap. Since we express the gap by the difference between the upper bounds of the generalization error, utilizing identical learning rates is more suitable, which corresponds to one of the worst-case scenarios.

• (Q4 and W3) Assumptions 2 and 3 are commonly used in studying the generalization of stochastic algorithms [1,2]. Previous papers have found that the stochastic process can be modeled as the multivariate Ornstein-Uhlenbeck process [3] consisting of three regimes. At the beginning, there is a search phase where the algorithm approaches the optimum. In this early phase, our assumptions may not hold. However, with more iterations, there is a second phase where SGD has converged to the vicinity of a local minimum. Here, the objective looks already quadratic if the loss function is smooth, but the gradient noise is small relative to the average gradient. Thus SGD takes a relatively directed path towards the optimum. This is the regime where Assumption 2 becomes valid. A recent paper has also validated this with experimental results (see [4, p.1, Figures 1(a) and 1(b) and p.6, Figures 4(a) and 4(b)]). Finally, after a sufficient number of iterations, the iterates of SGD are near the local optimum, where the average gradient is small, and the sampling noise becomes more important. In this final phase, the iterates can be approximated as samples from the stationary distribution. Since this phase follows the second phase, the covariance $\Sigma$ of the stationary distribution is closely linked to the Hessian matrix $A$ at the optimum. Assumption 3 provides a reasonable estimation of this connection.
• (Q5) In the experiment in Section 5.2.2, the federated scenario has an advantage over the centralized scenario in one training parameter. If the advantage is in the number of clients $n$ or the average amount of local data $m$, the total data will differ between the federated and centralized scenarios. If the advantage is in the model size $d$ or the number of training rounds $T$, the total data will remain equal in both scenarios.
• (Q6)
  • Analyzing federated SGD in a discrete setting introduces a summation symbol ($\sum_{0}^t$) over the number of local updates $t$, which is difficult to simplify in the derivation. In contrast, by treating the iterates of federated SGD as its continuous limit, we can simplify the analytic solution for the SGD iterates using integral operation. Besides, to estimate true generalization performance, our analysis assumes that the models are well-trained, which typically involves a large number of iterations. When $t$ approaches a large value, it is only feasible to derive the analytic solution in a continuous setting.
  • Results from the continuous analysis can often approximate those from discrete settings when derived through reasonable discretization (e.g., partitioning the continuous domain into sufficiently small grids). In our problem, each grid is an iterate of the SGD update. Since the training will be repeated for a significant number of iterations to ensure that the model is well-trained, individual grids represent only an extremely small fraction of the entire optimization domain. Therefore, our theoretical conclusions derived under a continuous setting also hold approximately in the discrete case.

[1] Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1–35, 2017.

[2] Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in neural information processing systems, 32, 2019.

[3] On the theory of the brownian motion. Physical review, 36(5):823, 1930.

[4] Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.

4. The experiments in Section 5.2.2 are not intended to compare the generalization between centralized and federated SGD under equal training conditions. Our theoretical analysis demonstrates that a generalization gap necessarily exists between the two scenarios when training resources, including the total data size, are equal (see Theorem 3). Therefore, the complete close of this gap would require the federated scenario to have advantages in training resources (see Theorem 4). To empirically validate which advantage can bridge the gap, we conduct experiments to compare a centralized scenario with a federated scenario that has an advantage in one training resource (i.e. the number of clients $n$, the average data across clients $m$, the model size $d$ and the communication rounds $T$). The experimental results are provided in Section 5.2.2 and Appendix A.3. Based on these empirical results, Theorem 4 is validated, showing that the gap can only be fully closed by introducing new clients or adding data to existing clients.
5. We would like to emphasize that the approximation is valid, and the concern of error accumulation does not apply in our case. In our theory, expressing the SGD iteration in discrete settings primarily impacts the analytic solution. Specifically, Eq.(14) would be changed to:

Therefore, the difference between the continuous and discrete formulations is captured by the approximation error between Eq.(14) and the above equation, which does not involve further error accumulation. Since each grid represents a single SGD iterate and training typically involves numerous iterations to ensure the model is well-trained, an individual grid contributes only a tiny fraction of the entire optimization domain. As a result, results from the continuous analysis closely align with those from a discrete analysis. Furthermore, our paper focuses on analyzing the generalization gap between scenarios, not deriving precise analytic solutions for SGD iterates. This approximation does not lead to a wrong understanding of the generalization bound and the generalization gap. Continuous approximations are widely used for studying the generalization of stochastic algorithms, as shown in previous works [1,2], which also validate their theoretical conclusions through extensive experiments.

[1] Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1–35, 2017.

[2] Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in neural information processing systems, 32, 2019.

[5] Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pp. 605–638. PMLR, 2018.

[6] A pac-bayesian analysis of randomized learning with application to stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.

[7] Federated pac-bayesian learning on non-iid data. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5945–5949. IEEE, 2024.

[8] Personalized federated learning of probabilistic models: A pac-bayesian approach. arXiv preprint arXiv:2401.08351, 2024.

[9] Lessons from generalization error analysis of federated learning: You may communicate less often! In Forty-first International Conference on Machine Learning, 2024

Thank authors for the clarification, but my concerns still remain unresolved. Thus, I will keep my score.

When $t=1$, even in the heterogeneous setting, centralized SGD and FedAvg are statistically the same. To see this, recall the fact $\frac{1}{S} \sum_i E_{\zeta_i \sim D_i}(\cdot) = E_{\xi \sim D} (\cdot)$ due to independence across $D_i \forall i$ and its underlying distribution.

Thank you for your reply before the rebuttal deadline.

Clarification of the differences between centralized and federated SGD when $t=1$ has been provided in the second point of our previous response. We are surprised that the reviewer still insists that centralized SGD and FedAvg are statistically the same. If they are the same, the generalization performance of FL and CL should be the same (statistically). It is exactly our paper's contribution to prove that the gap necessarily exists between the generalization performance of FL and CL, and we further derive the non-vacuous bounds for this gap. In addition, many previous papers have empirically revealed this performance gap. For example, in paper [10], Table 1 compares the Top-1 accuracies between their proposed method FedU on a federated setup with each client conducting $E = 1$ local epochs and a centralized baseline using BYOL [11]. The accuracy of FedU is $86.48 \\%$, while the accuracy of centralized BYOL is $91.85 \\%$. This performance gap of nearly $5\\%$ provides clear empirical evidence that training differences inherently exist between the two setups.

To help the reviewer better understand our work, we would like to further explain the underlying cause of the performance gap between centralized SGD and FedAvg. The main reason lies in the differences on the training datasets and the training processes. According to the equation $\frac{1}{S} \sum _i \mathbb{E} _{\zeta _i \sim \mathcal{D} _i} = \mathbb{E} _{\xi \sim \mathcal{D} _i}$ provided in the reviewer's reply, it seems the reviewer assumes that the average of the local SGD iterates directly equals the global SGD iterates. However, this equation does not hold, as the local dataset on each client is only a subset of the global dataset. Even though the data sets have the same statistical distribution, the descent direction of the gradients calculated from local SGD is not as same as the direction of the gradients calculated from global SGD (see Figure 3 in [10]). If the federated scenario is constructed in a non-i.i.d setup with highly heterogeneous local data, then the divergence on updating directions will be even greater. A recent paper accepted in ICML has also claimed that the divergence issue cannot be simply resolved through the averaging operation used in FedAvg and theoretically studied this inequality (see Eq.(3) in [12]).

Again, we refer to our paper and emphasize the significant differences between the training processes of federated and centralized SGD. Specifically, the iterates of federated SGD with $t=1$ are given by:

whereas the iterates of centralized SGD with $t=1$ are written as:

By comparing Eq.(1) and Eq.(2) provided above, we can find that the left term in the right part of Eq.(1) is different from that in Eq.(2), with an additional averaging operation in Eq.(1). Moreover, the right term in the right part of Eq.(1) and Eq.(2) also differs to each other, with not only an extra averaging operation across clients but also the data sampled from different distributions.

We hope that the above explanation resolves your concern. If you have further questions or require additional details, we are more than happy to provide further clarifications. We would appreciate it if you could consider increasing your score about our paper.

[10] Collaborative unsupervised visual representation learning from decentralized data. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4912–4921, 2021.

[11] Bootstrap your own latent - a new approach to self-supervised learning. In Advances in Neural Information Processing Systems, volume 33, pages 21271–21284, 2020.

[12] FedSC: Provable Federated Self-supervised Learning with Spectral Contrastive Objective over Non-iid Data. In Forty-first International Conference on Machine Learning.