Understanding the Stability-based Generalization of Personalized Federated Learning

Authors: Yingqi Liu, Qinglun Li, Jie Tan, Yifan Shi, Li Shen, Xiaochun Cao
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: stability analysis+generalization gap+excess risk+personalized federated learning

Abstract:
Despite great achievements in algorithm design for Personalized Federated Learning (PFL), research on the theoretical analysis of generalization is still in its early stages. Some theoretical results have investigated the generalization performance of personalized models under the problem setting and hypothesis in convex conditions, which can not reflect the real iteration performance during non-convex training. To further understand the real performance from a generalization perspective, we propose the first algorithm-dependent generalization analysis with uniform stability for the typical  PFL method, Partial Model Personalization, on smooth and non-convex objectives. Specifically, we decompose the generalization errors into aggregation errors and fine-tuning errors, then creatively establish a generalization analysis framework corresponding to the gradient estimation process of the personalized training. This framework builds up the bridge among PFL, FL and Pure Local Training for personalized aims in heterogeneous scenarios, which clearly demonstrates the effectiveness of PFL from the generalization perspective. Moreover, we demonstrate the impact of trivial factors like learning steps, stepsizes and communication topologies and obtain the excess risk analysis with optimization errors for PFL. Promising experiments on CIFAR datasets also corroborate our theoretical insights. Our code can be seen in https://github.com/YingqiLiu1999/Understanding-the-Stability-based-Generalization-of-Personalized-Federated-Learning.

Decision: accept (poster)
Reviewer scores: 6, 3, 6, 8

Reviews and discussion:
<thread>
creation date:
1730173278755

thread_type:
official_review

<thread_object>
creator: reviewer_45sj

<content>
summary:
The paper addresses an important theoretical gap in Personalized Federated Learning (PFL) by focusing on generalization performance beyond convex conditions, specifically analyzing non-convex settings. The authors introduce a generalization analysis that incorporates algorithm-dependent factors through uniform stability. The paper investigates the effect of hyperparameters, learning rates, and communication modes (Centralized vs. Decentralized PFL) on generalization performance. Additionally, they provide excess risk bounds and propose early stopping criteria for optimal risk in PFL, supported by experiments on the CIFAR dataset.

strengths:
The major contribution of this paper is from the theoretical aspect in generalization.

1. Generalization in (personalized) federated learning is critically important yet understudied, largely due to its complexity compared to the extensive body of work on convergence analysis in FL.

2. This paper offers a rigorous analysis, with well-rounded discussions and comparisons that cover various specific cases.

2. By focusing on the “algorithm-matter” generalization through uniform stability, the authors provide a practical framework that incorporates the effects of stepsize, learning steps, and communication structure (C-PFL vs. D-PFL). This analysis fills a significant gap in the field by moving beyond static theoretical assumptions.

3. The detailed examination of hyperparameters like learning steps and stepsizes, along with communication modes, is valuable for both theoretical insights and practical implications. The finding that C-PFL generalizes better than D-PFL is intriguing and has practical relevance.

weaknesses:
I don’t see any major weaknesses in the paper. However, I suggest: 1) incorporating additional datasets and models in the experiments to strengthen the findings; and 2) clarifying the notation throughout, e.g., 'U' in the theorem.

questions:
see the weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730455145910

thread_type:
official_review

<thread_object>
creator: reviewer_nkbg

<content>
summary:
This paper establishes a generalization stability analysis for a widely-used personalized algorithm, partial federated learning (PFL), in both centralized and decentralized federated learning (FL) settings. The authors also discuss the relationship between the derived stability results and previously established generalization stability upper bounds, and provide insights into  how these findings can inform and guide the training process.

strengths:
The paper presents a well-organized structure and provides a clear comparison between its results and prior findings. Additionally, it offers an in-depth discussion on the impact of hyperparameters on generalization performance.

weaknesses:
1. Inconsistent Notation: The notation used throughout the paper lacks alignment, which hinders readability. For instance, in Algorithm 2, the aggregation step update is defined as $u^{t+1}=\frac{1}{n}\sum u_i^{t+1}$, but in line 866, the update formula appears as ${\frac{1}{n}}\sum_{i\in \mathcal{N}}u_{i, K_u}^t$. It is unclear what $\mathcal{N}$  represents in this context. Additionally, in line 812, the notation $I$ is introduced without definition. This inconsistency in notation complicates understanding and interpretation.
2. Unclear Experimental Validation of the Proposed Theorem: It is difficult to discern how the experimental results support the theoretical findings. The authors establish generalization stability, yet in the experiments, they only measure the gap between training accuracy and test accuracy. There is no clear implementation of perturbations as discussed in the theoretical framework, making it unclear how the experiments substantiate the proposed stability theorem.

questions:
1. In line 803, could you clarify how the inequality is derived? Specifically, how is $\Vert f(w;z) - f(\tilde{w};z)\Vert^2$ bounded given that $U=sup_{w, z}f(w;z)$.
2. In line 806, it appears there should be an inequality rather than an equality, since $\Vert a + b \Vert \leq \Vert a \Vert + \Vert b\Vert$.
3. The notation $I$ requires further explanation, as it is unclear how to derive the bound for $P(\{\xi^c\})$;
4. Since the authors discuss generalization stability, I recommend comparing the results with similar studies focused on generalization stability rather than generalization bounds as shown in Table 1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730605635520

thread_type:
official_review

<thread_object>
creator: reviewer_tnfv

<content>
summary:
This paper derives uniform-stability-based generalization bounds (as defined in [1]) for personalized federated learning (FL). Bounds are derived in both the centralized setting (where there is a central server) and the decentralized setting. By combining the derived bounds with existing bounds on the optimization error, the paper provides an expression for the number of communication rounds which they claim is the optimal number of rounds to minimize the total (= optimization + generalization) error. Some experiments are performed to validate some of the theoretical insights.

[1]: Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In *International conference on machine learning*, pp. 1225–1234. PMLR, 2016.

strengths:
This paper considers an important problem of trying to quantify the generalization properties of personalized FL. An important by-product of such an analysis is quantifying the optimal number of communication rounds that minimizes the overall error (= optimization error + generalization error); papers on convergence guarantees do not consider the generalization error.

weaknesses:
**Technical issues:**

**1.** In Remark 4/Corollary 1 and Remark 8/Corollary 2, where the authors are deriving the "optimal" number of communication rounds $T^{*}$, how do the authors know that the derived generalization bounds are order-optimal w.r.t. $T$, $K$ and other important quantities. If the tightness of the derived generalization bounds is not shown, then it is unfair to call it "optimal" number of communication rounds. Moreover, in Corollary 1 and 2, the dependence on other problem-specific parameters (such as smoothness constants, stochastic gradient variance, etc.) shouldn't be ignored if they are being used to derive the "optimal" number of communication rounds.

**2.** Can the authors please summarize the technical challenges compared to the seminal analysis in Hardt et al., (2016) for SGD? Is there any particular challenge due to local updates in the clients? 

**3.** Overall I'm not too impressed/surprised by the derived results -- a more satisfactory result for me would have been something that shows the generalization benefits of personalization compared to *no* personalization. 

**Presentation issues:** 

**1.** The presentation of Theorem 1 and Theorem 2 is rather poor and complicated. What is the meaning of "*They decay per iteration $\tau = t K + k$,...*"? And the equations below have $\tau_0$ instead of $\tau$. I'd have directly presented eq. (8) and (10) with the optimal value of $\tau_0$ rather than presenting the intermediate results (eq. (7) and (9)). And what is $\kappa_\lambda$ in the context of D-PFL? Also, it is very hard to parse Table 1.

**2.** Definition 2 is not clear to me -- what is the index $j$ (subscript of $z$)? In eq. (4), a bracket is missing at the end in $F(\mathcal{A}(S)$ and $f(\mathcal{A}(S)$. In Assumption 2, what is $F_i$? Only $f_i$ was introduced earlier. 

**3.** Paper writing needs to be improved. For instance, I'd suggest using "algorithm-dependent" instead of "algorithm-matter". Also, it should be "influential" in Remarks 4, 5 and 8.

questions:
Please address the questions in Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745004866

thread_type:
official_review

<thread_object>
creator: reviewer_wmwb

<content>
summary:
The paper studies the generalization gaps of personalized federated learning (PFL) under centralized and decentralized cases. Uniform stability tools are used to derive generalization upper bounds that reflect the influences of graph topologies.

strengths:
The paper provides generalization bounds leveraging uniform stability of the algorithm for PFL under both centralized and decentralized settings. The bounds are topology-related, which provides new insight in how graph structures affect the generalization.

weaknesses:
1. The main weakness of the paper is that the bounds do not recover the centralized training with SGD. To be specific, PFL reduces to centralized SGD when $K=1$ and $v_i$ is constant $\forall i \in [m]$. However, the proposed bounds in Theorem 1 indicate a worse performance than SGD (Hardt et al., 2016). 

2. The analysis of the paper is standard as literature, which means there is limited technical contribution of this paper.

3. Shown by (Sun, Niu, Wei, 2024), the generalization of FL is affected by different data heterogeneity levels, while this paper does not capture such phenomenon.

I am willing to raise the score if my concerns are addressed.

Reference:

Sun, Z., Niu, X., & Wei, E. (2024, April). Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and Statistics (pp. 676-684). PMLR.

questions:
1. Why does not the bound Theorem 1 match the centralized SGD if $K=1$ without personalization? Is it due to technical analysis? Could the authors solve such technical issue?

2. What are the main technical difficulties in the analysis, comparing to existing literature?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733150822813

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary to Reviewers, AC and SACs

comment:
Dear ACs, SACs,

Thank you for taking the time to thoroughly review our paper and for engaging in thoughtful discussions with us over the past two weeks. We greatly appreciate the reviewers' valuable comments, which have helped us refine and improve our work. We hereby reiterate the core contributions of our work and summarize this rebuttal to facilitate subsequent review. 

**Core Contributions:**

- **First work on the algorithm-dependent generalization for both C-PFL and D-PFL under non-convex conditions.** We build up the first uniform stability-based
generalization for PFL with the biased gradient from multi-local updates. Our analysis establishes the interaction mechanism between global aggregation and local fine-tuning, then provides valuable guidance for alternating personalized optimization. We also extend this analysis to decentralized scenarios with different communication topologies, which have a huge impact on generalization bounds. The analysis achieves the tightest bound in decentralized training without strong assumptions.

- **New theoretical results for upper generalization bounds and excess risks for PFL.** Our theoretical results reveal the impacts of the trivial factors on generalization performance. Following the framework, we can creatively analyze the advantages of PFL over FL with data heterogeneity. Moreover, we analyze how communication topologies influence the upper generalization bounds of D-PFL and demonstrate that C-PFL generalizes better than D-PFL. Combined with the convergence errors, we finally obtain the excess risk of both C-PFL and D-PFL.

- **Massive experiments to verify the theoretical findings of PFL.** We evaluate important factors to verify our theoretical findings on CIFAR10/100 with different VGG/ResNet under non-convex conditions. The empirical results strongly support our theoretical insights.

**Rebuttal Summary:**

- **Adding comparisons with stability analysis and highlighting our advantages over the current PFL analysis.** We add the comparisons of stability analysis of SGD、FL and D-SGD in Table 1. We are the first to analyze the generalization impact from personalized variables to shared variables, which uncovers the interaction mechanism between these two updating processes and provides valuable guidance for alternating personalized optimization. Compared to the existing analysis of PFL in Table 2, we are the first to conduct the generalization analysis in the non-convex condition in both CFL and DFL, which includes the impacts of the algorithm design and the hyperparameters selection for personalized training. 
- **More detailed verification experiments with different datasets and models.** We follow the reviewers' advice to add the experiments of model parameter difference between the perturbations datasets and add more experiments on CIFAR-100 with VGG11 in Appendix D.2. The additional results can further strongly support our theoretical findings. 
- **Correct typos and polish the paper writing.** We polish the contributions and technical innovations of this paper. We add more details in the analysis and further optimize the comparison with SGD in the remark. In the appendix, we add more detailed information about the existing generalization analysis of PFL. 
- **Explore the future work.** Based on the reviewers' comments, we discuss three interesting and open problems in future work: 1) the lower bound and tightness of PFL; 2) the unique stability design for PFL; 3) the impact of data heterogeneity on PFL and FL.  Each of these three issues deserves careful discussion in separate works.  In the rebuttal, We preliminarily present the generalization advantage of PFL over FL with data heterogeneity and compare the generalization upper bounds of FL and PureLocalTraining. The above three open problems are of great significance to the FL community. 


We would like to thank the reviewers, ACs, and SACs again for your hard work and valuable suggestions for this paper. Please reconsider our contributions to the FL community. 

Best wishes,

Authors.
</content>
</thread_object>

</thread>


Metareview:
metareview:
a) Summary

This work analyzes the generalization properties of federated learning with personalization by studying the stability of models trained under non-convex loss functions. It provides bounds on generalization error, decomposing the contributions of global aggregation and local updates, and examines the effects of hyperparameters like learning rate and number of communication rounds. The results show that centralized training schemes achieve better generalization than decentralized ones, and the analysis offers guidance on selecting training parameters to minimize excess risk.

b) Strengths
- Non trivial generalization bounds in FL: The paper tackles the underexplored area of generalization analysis in personalized federated learning (PFL), particularly under non-convex settings, providing insights beyond the commonly studied convergence guarantees.
- Dependence on algorithms, topology, and hyperparameter: the analysis based on uniform stability can be used to study the effects of the algorithm choice, communication topology, and hyperparameters on model performance.
- Empirical Validation: Experimental results on CIFAR datasets support the theoretical findings and show the utility of the bounds. 
- Interesting finding: both theory and empirical evidence suggests that current that centralized schemes generalize better than decentralized ones. Understanding this better and overcoming this promises to be an interesting research agenda for the FL community.

c) Weaknesses
- Lack of Tight Bounds: The theoretical results do not include lower bounds, making it difficult to assess the tightness or optimality of the derived generalization error bounds.

- Limited Technical Novelty: The analysis primarily extends existing stability results (e.g., Hardt et al., 2016) without introducing significantly new proof techniques or theoretical insights.

- Incomplete Treatment of Data Heterogeneity: While data heterogeneity is acknowledged as important, the generalization bounds fail to fully quantify its impact, leaving a key aspect of federated learning underexplored.

- Effect of personalization is not properly captured by the current analysis as raised in the discussion by Reviewer tNFV.

d) Reasons to recommend **accept**

This paper provides a first step in understanding the generalization properties of personalized federated learning (PFL), an area that remains underexplored compared to convergence analysis. Though far from optimal and despite the lack of novel theoretical progress, the work derives bounds that seem to offering actionable guidance for practical FL settings. I believe that this work will spark interesting discussions among the FL community and lead to further interesting research.

This is not to say that the concerns raised by the reviewers, especially in the lengthy discussions with Reviewer tNFV who remained unconvinced by the authors, can be dismissed. This paper really **needs additional polishing**. I strongly recommend the authors to incorporate the comments, especially **flesh out the generalization advantage of PFL over FL with data heterogeneity** which was developed over the discussion with tNFV.