Understanding the Stability-based Generalization of Personalized Federated Learning
Authors: Yingqi Liu
Qinglun Li
Jie Tan
Yifan Shi
Li Shen
Xiaochun Cao
Venue: ICLR 2025 Poster (2025)
Keywords: stability analysis+generalization gap+excess risk+personalized federated learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation 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.

Published as a conference paper at ICLR 2025
UNDERSTANDING THE STABILITY-BASH GENERAL- IZATION OF PERSONALIZED FEDERATED LEARNING
Yingqi Liu Qinglun Li Jie Tan
Yifan Shi Li Shen 1.2- Xiaochun Cao! 1 School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University, China "Guangdong Laboratory of Artificial Intelligence and Digital Economy (SZ.), China
&Coleee of Systems Engineering, National University of Defense Technology, China "Intelligent Game and Decision Lab, China
Hiuyinggill 9191 i1. com; 1i undutt edu, en; wew.tiieotttooooo...ooo mat mathshenla @gma ill com; caoxiacchunémai pysu.edu.co
ABSTRACT
Despite great achievements in algorithm design for Personalized Federated Learn- ing (PFL), research on the theoretical analysis of generalization is still its early stages. Some theoretical results have investigated the generalization performance of personalized models under the problem setting and hypothesis in convex conditions, which
reflect the real iteration performance during non-convex training. To further understand the real performance from a generalization perspective, we pro- pose the first algorihmm-dependen generalization analysis with uniform stability for the typical PFL method, Partial Model Personalization, on smooth and non-convex objectives. Specifically, 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 Train- ing for personalized aims heterogeneous scenarios, which clearly demonstrates the effectiveness of PFL. from the generalization perspective. Moreover, we demon- strate 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 http://giihuuboomiiieeeee www.iuuii99/nn 999/Understanding-- Stability- Sabblity-bbsed--ee
Seeee--aaee-----aliiiieeee Generalization Porrooollll-eselieeeedee. Feeeeeeteddeeeeeeededee Learnnng
INTRODUCTION
With the rapid development of data and model scales in Machine Learning, PFL effectively improves local performance via flexible client cooperation with heterogeneous data. Although the studies of algorithm design has made considerable progress in PFL, their theoretical analysis is still scarce. Due to the data and training limitations in the real world, theoretical analysis of FL/PFL usually includes two aspects: optimization properties and generalization properties. In this work, we mainly focus the generalization properties of PFL., which come from the overfitting gap between the training and testing datasets.
Currently, the existing generalization analysis for PFL is mainly obtained in three ways: 1) high- probability generalization bounds with concentration inequalities based on the PAC hypothesis complexity like VC dimension complexity (Deng et al., 2020; Marfoq et al., 2022; Xie et al., 2024), Rademacher complexity (Mansour et al., 2020); 2) cntemmation-thorretinn output hypothesis and the prior from PAC- PAC-Bayes generalization (Achituve et al., 2021; Zhang et al., 2022); 3) the privacy-preserving ability of the change in output hypothesis when the algorithm is exposed to attacks (Dai et al., 2022b). Most upper bounds above only depend on the problem setting and hypothesis in the convex condition, which can not apply to the commonly used non- convex functions such neural networks and can not reflect the real iteration performance during personalized training. In other words, they are weak at evaluating the effectiveness of algorithm
distances between the
"Corresponding Author

---

Published as a conference paper at ICLR 2025
Table I: Main results on the upper generalization bounds of PFL. m total nodes number, T training rounds, 1) is local learning stepsize, K is local learning step, n is the selected nodes number and À is about communication topology, is data hetegeneity and NC representation non-conver condition.
Tpye
Reference
Algorithm
Analysis Tools
T
K
n/d
NC
Hardt et (2016)
SGD
Uniform Stability
x
x
SGD, FL
Chen et al. (2021)
FedArg
Uniform Stability
7
v
x
Sun (2024b)
FedAvg
On-average Stability
v
v
Sun al. (2021)
D-SGD
Uniform Stability
v
/
7hu et al. (2022)
D-SGD
On-average Stability
v
x
Deng et al. (2020)
C-PFL
VC Dimension Complexity Rademacher Complexity
x
Mansour et al. (2020)
C-PFL
PFL
Zhang (2022)
C-PFL
PAC-Bayes Complexity
Ours
C-PFL
Uniform Stability
Ours
D-PFL
Uniform Stability
design and hyperparameter selection while building the relationship between global collaboration and local fine-tuning. Despite the optimization design above, the upper generalization bound of PFI. has great significance with both communication topology and data heterogeneity. This insight offers deeper understanding of the fundamental nature of PFL. To this end, we aim to establish framework for algorithm-dependen generalization analysis in PFL, which is designed to align closely with the foundation for further research.
training process and provide clear and community-
Overall, we present the first algorithm-dependent generalization for the typical PFL method Partial Model Personalization with uniform stability in non-convex conditions and evaluate the excess risk for both Centralized PFL (C-PFL) and Decentralized PFL (D-PFL). Intuitively, each shared and personalized update may introduce specific impact on the generalization errors. Therefore, we decompose the generalization errors into aggregation errors and fine-tuning errors, then establish generalization analysis framework corresponding to the gradient estimation process of the person- alized training. From our analysis, some results can be concluded that larger learning steps, larger learning rates, and denser network connections will hurt the generalization performance for both C-PFL and D-PFL, meaning that better testing performance the trade-off between communication cost and computational efficiency. Besides, with different aggregation modes in the shared variables, we demonstrate that C-PFL generalizes better than D-PFI., which aligns with the conclusion of the generalized FL. (Sun et al., 2023c). Moreover, with the analysis of data heterogeneity, we can clearly see how PFL outperforms FL and Pure Local Training in the perspective generalization. Combined with the convergence analysis, we obtain the excess risk and find that personalized performance is the trade-off between optimization and generalization.
We list analysis with the existing bounds of SGD/D-SGD and PFL methods in Table 1. From comparisons, our results innovatively achieve the biased gradient estimation from multi-local up- dates and analyze the generalization interaction between personalized and shared variables during aggregation and local training. In summary, our main contributions are as follows:
New framework of generalization analysis for PFL under non-convex conditions. We build up the first algorithm -eethmm--eeddeentt generalization analysis framework for PFL with the biased gradient from multi-local updates. It is consistent with the personalized training progress and bridges PFL., FL and Pure Local Training with the clever heterogeneity analysis, which reveals the effectiveness of PFL for personalized aims. We also extend it to the decentralized scenarios with different communication topologies.
New results for upper generalization bounds and excess risks for PFL. Our algorithm- dependent results achieve comparable bounds and reflect the iteration nature, effectiveness of algorithm design well the hyperparameters selection of PFL. Then combined with the optimization errors, we obtain the excess risk analysis and find that the better performance is the trade-off between optimization and generalization.
Massive experiments verify theoretical findings. Our experiments on CIFAR datasets with different models under non-convex conditions strongly support theoretical insights.
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORK
Generalization for PFL. PFL is proposed to find the greatest personalized models for each client (related work in Appendix A). Generalization analysis represents the performance in the unseen data of a well-train model, which defined as the difference between the population risk and empirical risk. Various statistical methods have been introduced into PFL., including methods based on PAC-based analysis, Differential Privacy analysis, and PAC-Bayes analysis. For PAC-based analysis, Deng et al. (2020) derives the VC dimension complexity bound of mixture of local and global models, and finds the optimal mixing parameter. Mansour et al. (2020) derives the Rademacher complexity bound of the clusters, data interpolation, and model interpolation. Chen et al. (2021) analyzed the stability and excess risk of both FL and local SGD under different data heterogeneity, but failed to extend them to the non-convex condition. For Differential Privacy analysis, Dai al. (2022a) assumes that the algorithm satisfies (c, 8) differentially private condition and proposes the lower generalization bound with the noisy perturbation. For PAC-Bayes analysis, Zhang et al. (2022) gives an upper bound of averaged generalization error the Bayesian variational inference method and illustrates that the convergence rate of the generalization error is minimax optimal up to a logarithmic factor.
Stability for generalization. The stability -bsse methods measure the sensitivity of the data perturbation of an algorithm via uniform stability (Bousquet & Elissceff, 2002; Hardt ct al., 2016), Bayes stability (Li et al., 2019), model stability (Lei & Ying, 2020; Liu et al., 2017), on-average stability (Lei et al., 2023; Sun et al., 2024b; Kuzborskij & Lampert, 2018), and so on. More information can be seen from the introduction in Lei et al. (2023). For the generalization bounds in FL, Lei et al. (2023) develop the stability analysis for minibatch SGD and local SGD for convex, strongly convex and nonconvex problems. Sun et al. (2024b) show that the generalization performances of FedAvg, FedProx and Scaffold are closely related to the data heterogeneity and the convergence behaviors when training. Sun et al. (2023c) discuss the better generalization performance between the Central FL. and Decentralized FI.. In decentralized training, Zhu et al. (2022) extend the stability- based generalization to D-SGD and discuss the topology effect of it. Zhu et al. (2024) refine the stability analysis for the minimax problem in a decentralized manner.
Nowadays, almost all upper generalization bounds of PFL based on the complexity theory ignore the impact of algorithm design and the iteration nature. Therefore, we try to propose the stability- based generalization analysis to answer how algorithm design and hyperparameter selection impact the generalization capacity. Mcanwhile, extend the non-trivial analysis to D-PFL with various communication network topologies. Extensive experiments also corroborate our theoretical findings.
PROBLEM FORMULATION
In this section, we first propose the problem setup for C-PFL and D-PFL. Then we present the uniform stability for generalization сттог and combine it with convergence error to obtain the excess risk.
3.1 PROBLEM SETUP
Personalized Federated Learning. Compared to typical FL methods, PFL focuses on the average minimization with the personalized models rather than the consensus one. Partial Model Personaliza- tion one of the most significant strategies PFL., which decouples the model as the personalized variables to satisfy the individual requirements and the shared variables to leverage the collective knowledge. We consider the typical setting with m clients, where each client owns the local training data & and it satisfies the data distribution D.. For each client, the model parameter w, Rd are partitioned into two parts: the shared variables u E Rdd and the personalized variables 0; E RRd for i 1, ., m. To simplify the presentation, we denote V (V1...., Um) + So the full model on client i is denoted as w; = (u, 2/). fa (such as cross-entropy function) denote the loss function for each client, is the specific data for client i. The Population Risk Minimization F of PFL is defined as follows:
1 F(u, V) = m Σ F. (u,0), where Ft (u, 0;) = RE I' (u, Uy; Ex)
min
(1)
V.V
From engineering purposes, we set the feature extraction layers (close to the input) as the shared variables and the linear classification layers (close the output) the personalized variables v; as
3

---

Published as a conference paper at ICLR 2025
Arivazhagan et al. (2019); Collins et al. (2021); Pillutla et al. (2022); Liu et al. (2024). Meanwhile, we alternately update the shared variables and personalized variables to distinguish the generalization effects between them explicitly. Algorithm illustrates the specific process. We set V. as stochastic gradients of the shared variables u and V. as stochastic gradients of the personalized variables vi. respectively. Personalized variables U2 first perform the local updating with the shared variables fixed in Line 2, then the shared variables u update with the personalized variables es fixed in Line 5,
C-PFL and D-PFL. We consider both C-PFL and D-PFL in Algorithm 2. For C-PFL, the only central server first distributes the shared variables u' to the n selected clients in Line 3. then aggregates the updated shared vari- ables u to u from the selected clients : vi,+11 + v - v/o V. V. vi,e: x.
Algorithm 1: Local updating for PFL.
Input :Local steps K, local learning rate 1)s, and Tee initialize uf_ = ut', and vř,0 of.
Output :For each client, locally update uf+1 uf- for local update round la 0, 1, ,... Ke 1 do
in Line 7. Different from the general FI., end
partial model personalization only aggregates for local update round the shared variables "; in the central server, 5 ki, + u nu V f (i. while keeping the personal variables e; on the client side. We focus on the case of the av- eraged aggregation, which means or- 1/n. For D-PFI., it allows clients to communicate with their neighbors in a peer-to-peer man- ner without the central server. The commu- nication can be modeled as an undirected connected graph G (W. V. W), where M 21,, m] is the set of all clients, V C N x N is the set of communication channels, and the gossip/mixing matrix W present below records whether the com- munication connects or not between any two clients. Set Gi the neighbors set for each 5 client in the undirected graph.
1, 1,... K do
end
w K. of v.K.
Algorithm 2: C-PFL and D-PFL.
Input
:Total communication rounds T, number of selected clients n, initial the shared and
personal variables u,, v {r])]=
solution x' and v' = {oe Hizo
C-PFI.:
for communication round t 0 to T - do
3 Sample clients |S*| = n uniformly randomly and distribute the shared variables u'.
for client E St in paralle! do
u ++1 1 uut1 +
Local updating (u², vf)
end
Exew utt1
Definition 1 (The gossip/mixing matrix end (Nedic lar, 2009)). The gossip ma- D-PFL:
trix W = [mct]] E [0, 1|mxxm is assumed to 10 for communication round t = 0 to T - 1 do for client i E [m] in parallel do
have these properties: (i) (Graph) If # j
and (i, & V. wij = 0, otherwise, Wa. > 12
end u, ++1 (+1 + Local updating (uf, uf)
O; (ii) (Symmetryy W = WT;
; (ii)) (Null 13
space property) null - W) = span [1}; 14
Receive shared variables uft) with matrix W: w + Eiegro wr,ru
(iv) (Spectral property) I > W > -I. Un-
der these properties, the eigenvalues of W 15 end satisfies 1 (W) > (W) >
Am (W)- > 11 X == max ()L, Pm ())]) and X E (0, 1] is a spectral gap of W measuring the speed of communication parameters converge to their average value (Sun et al., 2022).
3.2 STABILITY AND EXCESS RISK
Generalization Stability. Recalling the unseen data distribution D; in the population risk function in Formula (1), we select the sample & from the local datasets S, and estimate the expectation to represent the real distribution. The training process is rewritten as the Empirical Risk Minimization:
f(u.V) = 1 Σ fi (4, where ft fu, 02) V.V
Σ Ifs (u,):)))).
min
(2)
S
E.ES,
Assuming the joint datasets of local dataset S; as S, we consider a solution A(SS) of specific algorithm A trained on S, the generalization error between the population risk in (1) and empirical risk in (2) can be defined as éa Es (f.A(((((S)) impact caused by both the algorithm A and the datasets S may cause a bad performance from a well-trained model on the testing dataset, which is called overfitting. Motivated by the previous studies in Hardt et al. (2016), we use the uniform stability bound to explore the generalization performance of PFI..
[(A(S)) = E[ V) f(u, V)J. This joint
4

---

Published as a conference paper at ICLR 2025
Definition 2. (Uniform Stability) Considering new joint dataset S. which differs from the vanilla dataset at most one data sample 2. The E-uniformly stability for algorithm A is defined as below:
sup [y-(P:)
The generalization error can be bound by EG S c (Hardt et al., 2016), if the algorithm A satisfies the E-uniformly stability.
Excess Risk. Considering (u" V*) as the optimal model that can be achieved by the algorithm A on the dataset S, the real test performance E. B[F(A(S)) can be measured by the excess risk as follows:
Eg [[((((())) [if("", V*] S F[, fu, V) +
- P((u,V)-
Ec: generaiization crmor
Eo: optimization evror
Actually, if the optimal parameter (u", V*) could fit the personalized datasets well, the loss function [[f("", .V']] will tend to zero when the training time is large enough. Therefore, the real risk of the well-trained model (u, V) on the test datasets can be bounded by the generalization and optimization error. &g represents the performance risk of (u, V) between the training datasets and testing datasets, while Eo represents the empirical risk between the theoretical optimum (u", V*) and the obtained one (u, V). Utill now, most existing studies about PFL focus on the optimization error EO of general C-PFL and D-PFL, but there is still little work to discuss their generalization nature. To further understand the optimization progress of the algorithm design and the iteration nature of personalization, we provide comprehensive analysis of their excess risks.
3.3 BASIC ASSUMPTIONS
Assumption 1 (Smoothness). For each client i = (1....,m}} m.) the function F is continuously differentiable. There exist constants Lus Ly, Luv; Leu such that for each client i {1....,.0 m]:
* Vufi(u,, v.) is Lu Lipschitz with respect to u, and Luv Lipsccitt with respect to
* Vufi(u;, v/) is Lipsschttitz with respect to vi and L Lipschitz with respect to uu Assumption 2 (Bounded Variance). The stochastic gradients both C-PFL and D-PFI. have bounded variance. That is to say.for all us and vs, there exist constants on and og such that:
E Ell Vuf uy Vuf(uu, ot)] o..
(5)
V. e; - Vofilu;, us)ll²] S o²
(6)
Assumption 3 (Partial Gradient Diversity). There exists a constant 8% that reflects the data heterogeneous degree:
Vufi(u, Vufiu, V)Il < 52, Vu, V.
Assumption 4 (G-Lipschitz). For A A(S), ( A(S) E Rd which are well trained by e-uniformly stable algorithm A on dataset S and S, the personalized objective f(u, V) satisfies G-Lipschitz continuity between them:
& GIJA(S) - A(Š)
(7)
Assumptions 1, and 3 are mild and commonly used in the convergence analysis of FL and PFL (Liu al., 2024; Chen al., 2023; Shi et al., 2023a; Li et al., 2023a; Shi et al., 2023d; Pillutla et al., 2022; Sun et al., 2022; Reddi et al., 2021; Li et al., 2025). Assumption 4 is a variant of the vanilla Lipschitz continuity assumption, which widely used in the uniform stability analysis (Elisseeff al., 2005; Hardt et al., 2016; Zhou et al., 2021; Zhu et al., 2022; Sun et al., 2023e; 2024a; Li et al., 2024a;b).
4 THEORETICAL ANALYSIS
In this section, we present the generalization analysis and the excess risk analysis for both C-PFL and D-PFL.. We state the main theoretical results and discussions follows.
5

---

Published as a conference paper at ICLR 2025
4.1 STABILITY AND EXCESS RISK FOR CENTRALIZED PERSONALIZATION
Theorem (Stability of C-PEL), Under Assumplion 1~ let the active ratio per communication round be n/m, and assume the learning rates satisfy TJu
(IK.tt) IK,+k and TJo
(Ko+x) (TKTTR== TKotK They decay per iteration = t + k, where Po and pyy are the specific
constants and satisfy pu I 1 and poo S 1. Let U = 2), then the generalization bound of C-PFL satisfies:
Iu
B [[IS(u", v²:25) f(ū", (2;2))l]]
nUro mS
(TK,)
Mu liu 2G( + ou)
+ (K. botor
Luv TKu guugu
2Go MSL.
(8)
$
+
[
To
mSLn
Liu
To simplify subsequent analysis, we assume μL max { Un Ln poLnt and K max Kn K,). 3. By
selecting To
[2G((,,, (..lo.....)) +8.)L, nttingh fre
THpT. (TK) thaT we can minimize the bound with Ty:
E (llK", v 12)) f(t", V 12))1 S
4 [G((Ta + T.y + t. TIFE (NUTK) 14p (9)
mS
Lubu
Remark 1 (Influencal factors of C-PFL). From the stability-bused results above, severe data heterogeneity (larger gradient diversity 6uh, more selected clients and more local epochs Kn. and K, increase the time of training on only different samples, which leads to a larger generalization gap and worse generalization performance. In contrast. the generalization gap can be alleviated with more total clients m and the number of samples S involved.
Remark 2 (Special cases of C-PFL). If we remove all personal variables vs the problem (2) puby Pata
/m) by degenerates the classical FL problem FedAvg. The stability reduces O (InKTT) T-
removing the K, and a in the result, which is compatible with the upper bound O ( ((KT) = /m) of the stability of central FL algorithm FedAvg (Sun et al., 2023c) with multiple local update. That to say, the upper bound of the stability is only related to the training paradigm, no matter whether training for the consensus model or the personalized models. This finding builds the bridge between the stability of FL and PFL. If we remove all shared variables u, the stability of C-PFL can be reduced to O (nk,T)) 14puttr /mS), which is the stability bound of the whole FL system with partial participation ratio n/m and local updates K For further consideration, we set full participation n/m = 1 and only one local update K = 1, our results can degrade to O (Trhiz /S on each client, which aligned with the vanilla SGD in Hardt et al. (2016).
Personalization performs better than no per- sonalization and Pure Local Training. Con- sidering the impact of data heterogeneity. we list the comparison of generalization bounds for
Table Comparison with FL, PFL, Pure Local Training.
FL, C-PFL,, and Pure Local Training in Table 2. When the data heterogeneity is more severe, PFL significantly improves generalization capabil- ities from no personalized methods by eliminating the influence of the gradient diversity and outper- forms Pure Local Training through collaboration with other clients. Specifically, for the consensus model w in FL., we assume that the global gradi- ent diversity mainly from heterogeneity satisfies
Algorithm
Generalization Bound
FL
aUmo m5
Re 2G(r+
70
MSL
TuU ms
+
TKg
Muko 2G(0, thu)
PFL
mSLu
+
TKp
(1
Luv Lu
2Gdv SL
Local
O
Drn
TK
pL
2Ge
SL
1 E VV (w,)- - F < 62. Correspondingly, for the personalized model (u, v2). the
heterogeneity from the shared variables ö, satisfy + >n IVV.F; (u, vv) FuF(u, V v)] 82 shown in the Assumption 3. When the data distribution is non-iid between each client (0g, 6, + 0), PFL performs better than FL since the gradient diversities satisfy 8 < og during personalized training. As for the generalization performance of Pure Local Training, though it is not affected by the

---

Published as a conference paper at ICLR 2025
gradient diversities from data heterogeneity, the upper bound may be larger without the collaboration among m clients, which consistent with the empirical experience. This analysis builds up the bridge among FL, PFL and Pure Local Training, which first demonstrates the effectiveness and necessity of personalized design from the generalization perspective.
Remark 3 (Comparisons with generalization bounds of C-PFL), The generalization bounds compared in Table in Appendix B calculate the complexity of the PAC problem in infinite space as the generalization error. Although considering the nature of the learning problem, they cannot analyze the impact of algorithum design and personalized iterative nature. Therefore, we highlight our contributions follows: 1) conduct the generalization analysis in the non-convex condition, which is based on the more realistic assumptions adapted to the neural networks; 2) analyze the effectiveness of algorithm design and hyperparameters selection; 3) illustrate the error propagation between model aggregation and local training with the iteration nature.
Corollary 1 (Excess risk of C-PFL.). Assuming that the number of dataset samples S is fixed and combining with the convergence bounds oo S [s(w*) [(w))] =0 (1/VT) proposed in Pillutla et al. (2022), the excess risk of C-PFL satisfies that Eg S E[F(((S))) [[f(w")] uk
O (1/VT-(1KT) (nKT) Leaz /m).
Remark 4 (Influential factors of the excess risks for C-PFL), Assuming that the smoothness constants L, the gradient variance du and o. the gradient diversity 8a. and the total client number are fixed in specific analysis, the excess risk of C-PFL is decided by the number of active clients n, the local intervals Kn, and K the total communication rounds T. Therefore, we can adjust the hyperparameterss n,, Kn, K2 and T optimize the testing performance during training. The preferred choice of the number of active clients n and the local intervals Ku and K2 are the same that in the stability analysis, but increasing the communication rounds T leads to better convergence but worse generalization performance due to the training overfitting. That is to say, the better performance for C-PFL is the trade-off between optimization and generalization.
4.2 STABILITY AND EXCESS RISK FOR DECENTRALIZED PERSONALIZATION
In this section, we first provide the stability analysis of PFL with the peer-to- peer communication in the non-convex objectives. Then we combine its convergence performance obtain the excess risk.
Theorem 2 (Stability for D-PFL). Under Assumption 1~ 4, let clients communicate with each other in peer-to-peer manner, and assume the learning rates satisfy Thu =0 (1K.tk) tk
and :1 = (Ix)TT) - "R.4k They decay per iteration ..K k; where Py and by are the specific constants and they satisfy Huu S 1 and pv Eo Let U supu,,,, J f(u, 06 2). then the generalization bound of D-PFL satisfies:
Uno - 2( G (1 s
1 +67TAA
TKu Puhn
B lf("",, v²;z))= f("", ;2)),)]|
+
SLn
m
(10)
12 12
(Ku,
C0,
(TK,
Pube
m I.
To
SL.
To
where KΛ (2) 2) (I-a)eAIng In
2
2a and X are the widely used coefficient to measure
Aln
different communication connections.
To simplify subsequent analysis, we assume μL = selecting To 2G(a., (L,),, max)+ L., Lm (m+ +6TT)R))
boLy and K = max (a. KoJ. By IouE
(TK) T4pE, we can minimize
Umluh,
the upper generalization bound:
E
[l[(". ..T - -(W", VT: v=:,))]]]
(II)
4 (G + 8., (1 m/mm))) + a.G
6 G m mly
#t (UTK) F
<
Lo (1
S Iym

---

Published as a conference paper at ICLR 2025
Fully-connected
Exponential
Grid
Ring
Figure 1: Illustration of various network topologies in DFL.
Remark (Influential factors of the decentralized stability). The stability of D-PFI. is impacted by the number of samples S, total clients m, total iterations TKu and TK. data heterogeneity E. as well in the analysis of C-PFL. worth noting that also decided by the communication topologies K in decentralized FabTable 3 below and Figure I show the different topological diagrams and their properties.
For KA = (=)
X (1-o)eA
Aln I when À + 1, the upper bound for
2
Table 3: нΛ and Spectral Gap - À of communication lopologies(Sun al., 2023c; Zhu al., 2024).
RA is mainly decided by O (1/(A (In }))- And when - O, the upper bound for Rx is mainly decided by O (1/(2 (In )))
Network Topology
Spectral Cap 1 X
Fully-connected Disconnected
0
From the analysis above, we can clearly see that denser communication topology with a smaller KΛ leads to better generalization performance in D-PFL. Therefore, the fully connected topology achieves the best gener- alization performance of shared variables and is compatible with the central ones.
0 167 1677//m² /3m² O11/mlogs(mm)
Ring
O(m²)
Grid
(mlanm
Exponential
(Inm)
2/(1 (og)(m))
Remark (Special cases of D-PFL). we remove all personalized variables vú the problem (2)
degenerates to the classical DFL algorithm DFedAvg. By removing all personal constants in the proof. the stability of D-PFL reduces O + 6/mmxx/m ttrili (K,,T) "erat. which compatible (K,TT)tt
with the upper bound of the stability of decentralized federated fedeerate learning DFedAvg in Sun et al. (2023c)
of O (1 + 6y/mxx/m I ITEE (KT) THEL. ). The degradation analysis of the shared variables is
the same as C-PFL.
Remark 7 (Comparisons with generalization bounds of D-PFL), The mere generalization analysis of D-PFL can be seen for Dis-PFL in Dai et al. (2022b), which acquires a generalization lower bound through the lens of differential privacy with the inspiration in He el al. (2021). It describes the relationship between the remaining model and generalization performance at each iteration point and suggests that a more sparse network leads to better generalization performance. However, lacks of an understanding of the algorithm design. the impacts with different training parameters as well as the communication topologies in decentralized scenarios.
Corollary 2 (Excess risk of decentralized partial model personalization), Assum- ing that the number of dataset samples S is fixed and combining with the conver- provided in Shi
gence rates of EO S E [[f(w")-f(ee)
O (1/(1-x)3 al. (2023a), the excess risk of D-PFL satisfies EE S B[F(A(S)) [B[((w"]] ntt
O (1/(1- -1L---PVVV--- (1 (1+6//mx//)) FiRE (KT)ITEZ
Remark 8 (Influential factors of the decentralized excess risks). Our analysis shows that the excess risk of D-PFL is highly influenced by the number of the local interval Kg, and K., the total communication rounds T, the total clients the smoothness constants L, the gradient variance on/w the data heterogeneity 5., and the communication topologies X and Kx- Assuming that the total client number is fixed under the specific algorithm and data distribution (with the fixed smoothmess constants L, the gradient variance a and the data heterogeneity 8,), we can adjust the communication networks X and kx, local interval K2, and K2 to optimize the lesting performance.
8

---

Published as a conference paper at ICLR 2025
A denser connection (smaller Ry and smaller x-xx) means better convergence performance and generalization performance, but it brings more communication cost. The better choice for local intervals K₂ and K2 are the same as that stability analysis. And the better testing performance of D-PFL is a trade-off between the convergence errors and the generalization errors.
Remark 9 (Comparisions between the C-PFL and D-PFL). From the comparison between Theorem and Theorem 2, we can clearly see that C-PFL always converges and generalizes better than D-PFL in theoretical analysis. The centralized one largely reduces the propagation of the generalization error, which benefits from the regular averaging on a global server for a better consensus of the shared variables and leads to better generalization. However, to achieve a more reliable performance, the number of active clients n in C-PFL must satisfy at least a polynomial order of Also, the communication burden on the central server becomes big challenge in the training process. It means that the high communication costs are unavoidable when the whole federated system m gets larger. This conclusion is also consistent with the generalization analysis of the typical FL and DEL in Sun et al. (2023c). Therefore, the suitable choice between C-PFL and D)-PFL or the choice of different communication topologies real scenarios is trade-off among communication ability, communication cost and personalized performance.
5 EXPERIMENTS
In this section, we conduct extensive experiments to verify the theoretical findings. We first introduce the typical setting for experiments, then present the empirical results and corresponding analysis.
5.1 EMPIRICAL SETUP
We conduct the experiments CIFAR-10 datasets (Krizhevsky al., 2009) in the Dirichlet distribu- tion (Non-IID a = 0.3) with ResNet-18 (He et al., 2016) and CIFAR-100 datasets in the Pathological distribution (Non-IID
20) with VGG-11 11 (Simonyan & Zisserman, 2014) for C-PFL and D-PFL. Experiments on CIFAR- 100 are in Appendix C.2. To verify the impacts of the key hyperparameters, we follow Hardt et al. (2016) and study the parameter distance when disturbing only one data in Figure 2a, the generalization gap of the difference between training and testing error in Figure 2b. We explore the impact of the four factors: 1) Local Learning Epochs, 2) Local Learning Rates, 3) Client Fraction/ Communication topology, 4) Total Client Number. We keep the same sets for the other factors for fairness. More implementations can be seen in Appendix C.
5.2 EMPIRICAL ANALYSIS
Both less local learning epochs and lower learning rates lead to better generalization perfor- mance, but they affect the convergence speed more seriously. We discuss this phenomenon in the first two columns for Learning Epoch and Learning Rate in Figure 2a-2b. Increasing local learning epochs and learning rates means amplifying the model distance when learning on different samples. It brings about larger generalization error and more severe fluctuation.
More client participation and denser network connections in each communication round enlarge the generalization gap, but they speed up the convergence rate the same extent. We discuss this phenomenon in the third column for Client Selection and Communication Topology in Figure 2a-2b. Increasing the fraction of client selection and choosing denser connection topologies means more frequency in learning unique samples, which enlarges the generalization gap between the two models with the disturbed datasets. This is aligned with our theoretical findings in Theorem 1, 2. Thus, there is trade-off between communication costs and personalized performance in real life.
larger total participation of clients and smaller number of local training samples increase the generalization error and reduce the convergence speed simultaneously. We discuss this phenomenon in the fourth column in Figure 2a-2b. Since the total data number on the dataset remains the same, bigger participation clients mean fewer training samples per one. The generalization gaps get worse with the number of clients increasing in Figure 2b.
C-PFL outperforms D-PFL in both generalization and convergence when their upper communi- cation bandwidths are at the same level. We discuss this difference in the comparisons of each line in Figure 2a-2b. Maintaining the maximum communication capacity of the busiest node, the central

---

Published as a conference paper at ICLR 2025
Localipocc
Learning Rate
Ciient traction
Total Elient Number
Weight DISSAITIO
Weight DISCENTTO
Weight Dis-cancc
kun
Ciss Nun
Weight
Commincation round
Commincation Learning Rate
Commincationriint
Commincation
Epoch
Communication lopelogy
Iotal Client Number
Blech
Weiggh Diseance
Veiight Disterce
Wiiight Dicrafice
Coss
Weeight
Commincation round
Commincation round
Commincation round
Commincation round
Disturbed loss distance of C-PFL and D-PFL on CIFAR-IO.
Learning
Total Client Number
taeck
Lood Distrce
Loss Dusarnce
LOWA DHAPPe
Cive kum
Commincation round
Commincatiion round 7
Commincation round
Commincation round
22 Total Client Number
Local Eooch
Learning Rate
Communication Teplogy
Lose Distarcee
LON Dietarcc
LOSS
201
Kowago
Ciec Kaih
Cost Kun
Commincation round
Commincatiio round
Commincation round
Commincation round
33
(b) Testing and training loss distance of C-PFL and D-PFL on CIFAR-10.
Figure 2: Empirical results C-PFL (first line) and D-PFL (second line) on CIFAR-10.
server in C-PFL mitigates the inconsistencies driven by the updates on different samples, consistent with our theoretical results.
CONCLUSION
In this paper, we develop the first algorithn-depennden generalization analysis and the excess risk analysis for PFL in both centralized and decentralized scenarios under non-convex conditions. It builds up the bridge among PFL, FL and Pure Local Training, and demonstrates the effectiveness of the personalized design from the generalization perspective. Compared with the previous works, this analysis reveals the impact of algorithm design and hyperparameter selection on the iteration properties. Combined with the convergence errors, we obtain the excess risk analysis for PFL. Various experiments verify our theoretical findings.
Limitation. There are numerous avenues for future works: 1) Improve the generalization bounds for PFL with the more advanced stability methods; 2) Discuss the lower bound and tightness of the generalization of PFL. to obtain the optimal training strategies for personalized training.
Acknowledgment: This work is supported by the STI 2030 Major Projects (No. 20212ID020100S Shenzhen Basic Research Project (Natural Science Foundation) Basic Research Key Project (NO. JCYJ2024 0 202 124430041), Open Research Fund from Guangdong Laboratory of Artificial In- telligence and Digital Economy (SZ) (NO. GML-KF-24-23), CCF-Baidu Open fund (NO. CCF. Baidu202413), Guangdong Basic and Applied Basic Research Foundation (202380303000010), Shenzhen Science and Technology Program (KIZD02024403399550000),, National Natural Science Foundation of China (No. 62402499).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021.
Idan Achituve, Aviv Shamsian, Aviv Navon, Gal Chechik, and Ethan Fetaya. Personalized federated learning with gaussian processes, Advances in Neural Information Processing Systems, 34:8392- 8406, 2021.
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Feder- ated learning with personalization layers. arXiv preprint arXiv:1912.0088 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-522 526, 2002.
Hong-You You Chen and Wei-Lun Chao. On bridging generic and personalized federated learning for image classification. arXiv preprin! arXiv:2107.00778. 2021.
Shuxiao Chen, Qinqing Zheng, Qi Long. and Weijie Su. A theorem of the alternative for personalized federated learning. arXiv preprint arXiv:2103.0190) 2021.
Yiming Chen, Liyuan Cao, Kun Yuan, and Zaiwen Wen. Sharper convergence guarantees for federated learning with partial model personalization. arXiv preprint arXiv:2309. /7409, 2023.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared represen- tations for personalized federated learning. In International Conference on Machine Learning, pp. 2089-2099. PMLR, 2021.
Rong Dai, Li Shen, Fengxiang He, Xinmei Tian, and Dacheng Tao. Dispfl: Towards communication- efficient personalized federated learning via decentralized sparse training. In International Confer- ence on Machine Learning, ICML., Proceedings of Machine Learning Research, pp. 4587-4601 PMLR, 2022a.
Rong Dai, Li Shen, Fengxiang He, Xinmei Tian, and Dacheng Tao. Dispfl: efficient personalized federated learning via decentralized sparse training. arXiv preprint arXiv:2206.00 00187, 2022b.
Towards communication-
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint 1rX1: 2020.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient
federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01264, 2020.
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing, Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Mengchen Fan, Keren Li, Tianyun Zhang, Qing Tian, and Baocheng Geng. Pfeddst: Personalized federated learning with decentralized selection training. arXiv preprint arXiv:2502.077750 2025.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586- 19597, 2020.
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.
Fengxiang He, Bohan Wang, and Dacheng Tao. Tighter generalization bounds for iterative dif- ferentially private learning algorithms. In Conference on Uncertainty Artificial Intelligence, 2021.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
11

---

Published as a conference paper at ICLR 2025
Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangchuan Liu, Jian Pei, and Yong Zhang. Personalized cross-silo federated learning on non-iid data. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7865-7873, 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Iija Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 2815-2824. PMLR, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, pp. 6175-6186, PMLR, 2021.
Yunwen Lei, Tao Sun, and Mingrui Liu. Stability and generalization for minibatch sgd and local sgd. arXiv preprint arXiv:2310.01139, 2023.
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint arXiv: 1rXiv:1910.03581,
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization enror bounds of noisy gradient methods for non-convex learning. arXiv preprint arXiv:1902.000 00621, 2019.
Qinglun Li, Li Shen, Guanghao Li, Quanjun Yin, and Dacheng Tao. Dfedadmm: Dual constraints con-
trolled model inconsistency for decentralized federated learning, arXiv preprint arX29,2308.08290, 2023a.
Qinglun Li, Miao Zhang, Nan Yin, Quanjun Yin, and Li Shen. Asymmetrically decentralized federated learning, arXiv preprint arXiv:2310.05093, 2023b.
Qinglun Li, Miao Zhang, Yingqi Liu, Quanjun Yin, Li Shen, and Xiaochun Cao. Boosting the performance of decentralized federated learning via catalyst acceleration. arXiv preprint arXiv:2410.0727.. 2024a.
Qinglun Li, Miao Zhang, Mengzhu Wang, Quanjun Yin, and Li Shen. Oledfl: Unleashing the potential of decentralized federated learning via opposite lookahead enhancement. arXiv preprint arXiv:2410.06482 2024b.
Qinglun Li, Miao Zhang. Tao Sun, Quanjun Yin, and Li Shen. Diedgfm: Pursuing global consistency for decentralized federated learning via global flatness and global momentum. Neural Networks, 184: 187:007084, 2025.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, pp. 5330-5340, 2017.
Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach. David Brent, Ruslan Salakhutdinov, and Louis-PPilippe Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.0155
2020.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing Systems, 33:2351-2363, 2020.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pp. 2159-2167. PMLR, 2017.
Yingqi Liu, Yifan Shi, Qinglun Li, Baoyuan Wu, Xueqian Wang, and Li Shen. Decentralized directed collaboration for personalized federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 23168-23177 2024.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. Computer Science, 2020.
12

---

Published as a conference paper at ICLR 2025
Othmane Marfoq, Giovanni Neglia, Richard Vidal, and Lactitia Kameni. Personalized federated learning through local memorization. In International Conference on Machine Learning, pp- 15070-15092. PMLR, 2022.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61, 2009,
Jaehoon Oh, Sangmook Kim, and Se- Young Yun. Fedbabu: Towards enhanced representation for federated image classificatiwon. arXiv preprint arXiv:2106.0660 06042, 2021.
Krishna Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. In International Conference Machine Learning, pp. 17716-17758, PMLR, 2022.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021. URL https: /openrevieww... net/ forum?
id-LkFG31B13US
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics, 2:00):400-440 407, 1951.
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems, 32(8):3710-3722 2020.
Yifan Shi, Yingqi Liu, Yan Sun, Zihao Lin, Li Shen, Xueqian Wang, and Dacheng Tao. Towards more suitable personalization in federated learning via decentralized partial model training. arXiv preprint arXiv:2305.1511 2023a.
Yifan Shi, Yingqi Liu, Kang Wei, Li Shen, Xueqian Wang, and Dacheng Tao. Make landscape flatter in differentially private federated learning. arXiv preprint arXiv: 1242, 2023b.
Yifan Shi, Li Shen, Kang Wei, Yan Sun, Bo Yuan, Xueqian Wang, and Dacheng Tao. Improving the model consistency of decentralized federated learning. arXiv preprint arXiv:2302.0408. 2023c.
Yifan Shi, Kang Wei, Li Shen, Yingqi Liu, Xueqian Wang. Bo Yuan, and Dacheng Tao. Towards the flatter landscape and better generalization in federated Icarning under client-level differential privacy. arXiv preprint M.Xiv:2335000877 2023d.
Neta Shoham, Tomer Avidor, Aviv Keren, Nadav Israel, Daniel Benditkis, Liron Mor- Yosef, and Itai Zeitak. Overcoming forgetting in federated learning on non-iid data. arXiv preprint arXiv:1910.07796. 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9756-9764, 2021.
Tao Sun, Dongsheng Li, and Bao Wang. Decentralized federated averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Yan Sun, Li Shen, Shixiang Chen, Liang Ding, and Dacheng Tao. Dynamic regularized sharpness aware minimization in federated learning: Approaching global consistency and smooth landscape. In International Conference on Machine Learning, pp. 32991-33013. PMLR, 2023a.
Yan Sun, Li Shen, Tiansheng Huang, Liang Ding, and Dacheng Tao. Fedspeed: Larger local interval, less communication round, and higher generalization accuracy. arXiv preprint 202.422302.10429, 2023b.
Yan Sun, Li Shen, and Dacheng Tao. Which mode is better for federated learning? centralized or decentralized. arXiv preprint arXiv:2310.03461, 2023c.
13

---

Published as a conference paper at ICLR 2025
Yan Sun, Li Shen, and Dacheng Tao. Understanding how consistency works in federated learning via stage-wise relaxed initialization. Advances in Neural Information Processing Systems, 36, 2024a.
Zhenyu Sun, Xiaochun Niu, and Ermin Wei. Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and Statistics, pp. 676-684. PMLR, 2024b.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Peng Wang, Li Shen, Zerui Tao, Shuaida Hc, and Dacheng Tao. Generalization analysis of stochastic weight averaging with general sampling. In Forty-first International Conference Machine Learning.
Chulin Xie, De-An Huang, Wenda Chu, Daguang Xu, Chaowei Xiao, Bo Li, and Anima Anandkumar. Perada: Parameter-efficient federated learning personalization with generalization guarantees. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
23838 23848, 2024.
Xu Zhang, Yinchuan Li, Wenpeng Li, Kaiyang Guo, and Yunfeng Shao. Personalized federated learning via variational bayesian inference. In International Conference Machine Learning, pp. 1-293-26310. PMLR, 2022.
Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards understanding why lookahead generalizes better than sgd and beyond. Advances Neural Information Processing Systems, 34:27290-27304, 2021.
Miaoxi Zhu, Li Shen, Bo Du, and Dacheng Tao. Stabiliity and generalization of the decentralized stochastic gradient descent ascent algorithm. Advances Neural Information Processing Systems, 36, 2024.
Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology- aware generalization of decentralized sgd. In International Conference on Machine Learning, ICMI., pp. 27479-27503. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2025
In this part, we provide the supplementary materials prove the main theorem.
Appendix A: Related Work about PFL.
Appendix Detailed Comparisons of Generalization.
Appendix Implementation Details and Results for Experiments.
Appendix D: Generalization Bounds for C-PFL and D-PFL.
A RELATED WORK ABOUT PFL.
Personalized Federated Learning. FL aims to improve model performance through collaboration
among users (Sun et al., 2023b;a; Shi et al., 2023b;d). PFL aims to produce the optimal personal- ized models for each client via model decoupling (Arivazhagan et al., 2019; Collins et al., 202 I), knowledge distillation (Li & Wang, 2019; Lin et al., 2020), multi-task learning (Huang al., 2021; Shoham et al., 2019), model interpolation (Deng et al., 2020; Diao et al., 2020) and clustering (Ghosh et al., 2020; Sattler al., 2020). More details can be referred the PFL survey (Tan et al., 2022). Among them, the model decoupling method Partial Model Personalization, which divides the model into shared variables and personal variables, has proved achieve better performance than full model personalization with fewer shared parameters. LG-FedAvg (Liang et al., 2020) relieves the data variance and device variance with jointly learning compact local representations on each device and a global model across all devices. FedPer (Arivazhagan et al., 2019), FedRep (Collins et al., 2021) and FedBABU (Oh al., 2021) set the feature extractor as the shared variable and the linear classifiers as the personal variables. They are different from the optimization progress between the shared representation and the private linear parts. Fed-RoD (Chen & Chao, 2021) trains global full model and many private classifiers with empirical risk minimization and balanced risk minimization. Most theoretical analyses for Partial Model Personalization mainly focus on their convergence performance. FedSim & FedAlt (Pillutla et al., 2022) provide the convergence analyses in the general non-convex setting, while FedAvg-P & Scaffold-P (Chen et al., 2023) achieve linear speedup respecting the number of the local steps. DFedSGPSM Li et al. (2023b) investigates the convergence of DFL combined with SAM under non-convex conditions. DFedPGP (Liu et al., 2024) presents the decentralized convergence bound in non-convex conditions under the directed graph and PFedDST (Fan et al., 2025) proposes the selection method for this directed cooperation, while DFedMDC & DFedSMDC (Shi et al., 2023a) focus on the convergence with the undirected network following (Sun et al., 2022; Shi et al., 2023c; Li et al., 2023a; 2024a).
B DETAILED COMPARISON OF GENERALIZATION.
Table 4: Main results on the upper generalization bounds of PFL..
Algorithm
Generalization Bound
T K
1)
m
o (2 (2)) (C)((())))) D D. CV (d log(1 (o((1/6))/N)
APFL, (Deng al,, 2020)
X
X
V
+o (2af(Cn, (11)) log log(1/5))/S GAH(S.))
MAPPER, (Mansour et al, 2020)
22 log th
de log #
+ 2
lunch m
X
X
PledBayes, (Zhang et al., 2022)
o Cym atts log (m))
V
FedAvg & LocalTraining.
( + 189 O(m/N)
J
(Chen et ul., 2021)
C-PFL (Ours)
Gloclatnut Lu
(nUTK)
d
Compared to the above generalization bounds for PFL, the proposed analysis has made the following progress: 1) conduct the generalization analysis in the non-convex condition, which is based on the more realistic assumptions adapted to the neural networks; 2) analyze the impacts of the algorithm design and the hyperparameters selection of the number samples S, the number of selected clients n, total clients m, total iterations TK, and TK, and the local learning rates th, and nus 3) illustrate
15

---

Published as a conference paper at ICLR 2025
the error propagation process between model aggregation and local training with the iteration nature, which provides a reference for the choice of early stopping points when training.
APEL is typical PFL method based on model interpolation. which aims to find the optimal combination of the global model and the local model with the adaptive parameter a; to achieve a better client-specific model. It derives the generalization bound of mixture of local and global models with the analysis of VC dimension complexity. St, i ====,, 1, ..... n is the number of training data ith user, N m1 + Mn is the total number of all data, S; to be the local training set drawn from Di D Dil,, = -= | (mmaj P(m.a))D( dædy. is the difference between distributions D (1/n) Ex= D; and D;, and h; = arg minncH LD, (h).
MAPPER is also a model interpolation method combining local and global models to pursue the better personalized results. It derives the generalization bound with the analysis of Rademacher complexity. He is the hypotheses class for the central model, and H4 is the hypotheses class for the local models. de the pseudo-dimension of He and de is the pseudo-dimension of H4. This bound only depends on the average number of samples and not the minimum number of samples.
PFedBayes novel PFL method via Bayesian variational inference. Each client uses the aggre- gated global distribution as prior distribution and updates its personal distribution by balancing the construction error over its personal data and the KL divergence with aggregated global distribution. It derives the generalization bound with the PAC-Bayes analysis. 8' > ő 1, and C1, C2 > 0 are constants related to Hölder smooth 88 the intrinsic dimension of data d, the number of hidden layers L, the widths of neural network equalwidth M, the balance parameter Ç between personalization and global aggregation, and sample size of each client n.
FedAvg and LocalTraining are the most typical methods for FL and PFL. Though the gener- alization analysis in (Chen et al., 2021) is not designed based on the PFL definition and not in the non-convex condition, it concludes surprising theorem that there exists threshold of data heterogeneity to decide whether FedAvg or LocalTraining could achieve the minimax optimal for PFI.. It derives the generalization bound for LocalTraining with uniform stability and the gen- eralization bound for FedAvg with federated stability under strongly convex conditions. m rep- resenets the client index, and N n1 + + T4m denotes the total number of training samples. R := min Exe(m) n. w - w|22/N measures the level of heterogeneity among clients (here III| denotes the Euclidean distance). Compared with this analysis, we demonstrate how PFL outperforms FL and Pure Local Training from the perspective of data heterogeneity, show how hyperparameter selection affects the generalization bounds and discuss the theoretical performance under the more commonly used non-convex conditions.
C APPENDIX FOR EXPERIMENTS.
C.I IMPLEMENTATION DETAILS FOR EXPERIMENTS.
According Definition 2, we construct distributed neighboring dataset S (Si,..,, and S = -S S.. where each corresponding local dataset pair (S,, S,) only differs on one randomly selected data sample. Then we deploy the same initial model (u, V) with its local dataset pair (S,, S.) to the local client i. To focus on the effect of the essential factors, the regularization methods such as weight decay, data augmentations and dropout are ignored to prevent unnecessary impacts (Zhu et al., 2024; Lei et al., 2021; Wang et al.). We keep the same experiment setting for all methods and perform 300 communication rounds. The number of client sizes is 20. The client sampling radio is 0.2 in C-PFL, while each client communicates with neighbors in D-PFL accordingly. The batch size is 128 and the number of local epochs is 5. We set SGD (Robbins & Monro, 1951) as the base local optimizer with a learning rate = 0.1. We ran each experiment times with different random seeds and reported the mean accuracy with standard deviation for each method.
C.2 MORE EXPERIMENTS RESULTS OF STABILITY ON CIFAR-100.
We explore the impact of the four factors on CIFAR- 100 in Figure 3 and 4: 1) Local Learning Epochs, 2) Local Learning Rates, 3) Client Fraction / Communication Topology, and 4) Total Client
16

---

Published as a conference paper at ICLR 2025
Local Loca Brech
Learning Rate
Cieent Praction
Total Elient Number
Weight Weight Disamoce
Weig Distancee
Weight Disccancc
kon
Ciss Nun 10
Wesght
Commincation
Commincation Rate
Commincation
Commincation
Local Epoch
Communicatin topelogy
Iotal Client Number
Wei Weight Dietance
Weightt Disparce
Wiigght Diorance
Coss
We Wenghn
Commincation round
Commincation round
Commincation
Commincation round
Figure 3: Loss distance of C-PFL and D-PFL on CIFAR-100.
Local Eooch
Learning Rate
Client Fradion
Total Client Number
C-PFL
Loss Disarce
Loos Distrre
Coid bun
Dlss
Commincation
Commincation Rate
Commincation round
Commincation
Communication Epplogy
Total Client Number
Distarce
Loxs Distance
Los Dint Seree
Loze Distar
Ban 11
Comminattion round
Commincation round
Commincation
Commincation round
Figure 4: Training loss distance of C-PFL and D-PFL on CIFAR-100.
Number. The empirical results on CIFAR-100 also verify that 1) Both less local learning epochs and lower learning rates lead to better generalization performance, but they affect the convergence speed more scriously; 2) More client participation and denser network connection each communication round enlarge the generalization gap, but they speed up the convergence rate to the extent; 3) A larger total participation clients and a smaller number of local training samples increase the generalization error and reduce the convergence speed simultaneously; 4) C-PFL outperforms D-PFL in both generalization performance and convergence performance when their upper communication bandwidths are at the same level.
C.3 MORE EXPERIMENTS RESULTS OF TEST ACCURACY AND TRAIN LOSS ON CIFAR.
We explore the impact the four factors in testing accuracy on CIFAR-10 in Figure 5 and CIFAR- in Figure 7, and training loss CIFAR-10 in Figure 6 and CIFAR-100 in Figure 8. The four factors are the same as above. Testing accuracies correspond to the analysis of excess risk, effected by both convergence error and generalization error. Training loss corresponds to the analysis of convergence error, reflecting optimization properties.
D GENERALIZATION BOUNDS FOR C-PFL AND D-PFL.
In this section, we introduce our proof of the generalization bounds in the main context. We first introduce the general lemmas for both C-PFL and D-PFL. Then we prove the uniform stability to measure the generalization eтrоr for them. At the beginning of our proof, we list the important variables used in the study follows.
17

---

Published as a conference paper at ICLR 2025
Local bnech
Learning Rate
Ciient iraction
Total Client Number
CPFLL
Tes: Accurccy
Accurncy
Test 22
Clost Sun 120
Commincation
Commincation
Commincation
Commincation
Local Epoch
Learning Rate
Communicatin lopelogy
total Client Number
D.PFL
Test Accurscy
Bim
Cloe
Commincation round
Commincation round
Commincation round
Commincation round
Figure 5: Testing Accuracy of C-PFL and D-PFL on CIFAR-10.
Local Eaoch
Learning Rate
Client Fradion
Total Client Number
C.PFL
Tran Lozs
Tran LOSS
Trai LONS
Tran
Commincation round
Cotimincation
Commincation round
Commincation
Learning Rate
Communicatinn Eppllgy
Total Client Number
D-PFL
Train LOSS
Tram LONS
Tran
Comm round
Commincation round
Commincation round
Commincation round
Figure 6: Training loss of C-PFL and D-PFL on CIFAR-10.
Local Eoech
Learning Rate
Ciient Fraction
Total Client Number
Acouracy
Per Acuraay
Test Accurnyy
Commincaalla round
Commincation round 7
Commincation round
Commincation
Learning
Communication Eepllogy
Total Client Number
Test D.PFL
Rest ACCL Recuracy
Jest AccurnIy
Jest Mcurary
Bun 11
Commincatian round
Commincation found 7
Commincation round
Commincation round
Figure 7: Testing Accuracy of C-PFL and D-PFL on CIFAR-100.
Local Epech
Learning Rate
Ciient Fraction
Total Client Number
Tain LOSS
Tain LOos
Commincationn round
Commincasion round
Commincation round
Commincation round
Local Epoch
Learning Rate
Communication Topslogy
Total Client Number
231
cng kowep
Tain LOSS
Pain Lode
Cost
Tain
Commincation round
Commincation round
Commincation round
Commincation round
Figure& 8: Training loss of C-PFI. and D-PFL. on CIFAR-100.
18

---

Published as a conference paper at ICLR 2025
Table 5: Some abbreviations of the used terms in the proofs.
Notation
Description
(u e: v(.))
parameters k-th iteration
10
(u², VT)
parameters round with set stability difference of variables u
A u,k
Σ
ie [m] BB/lu* 8"
A = E [m]]
Elluş Tlll
stability difference of variables oy initial function value gap
F
D.1 PRELIMINARY LEMMAS
Lemma 1 (Mixing Matrix for Decentralized FL, Lemma Lian al. (2017)). For any E Zt,
the mixing matrix W E IR" satisfies |[ lop S X, where À = max [x, (W)) and for matrix A, we denote its spectral norm as || A lop- Furthermore, == [1, 1...,... 1] E Rmm and
11 T
P
ER
Lemma (Stability for C-PFL), We follow the definition in (Hardi et al., 2016; Zhou et al., 2021) to upper bound the uniform stability term for the shared and personalized variables and v; after round T in the central FL paradigm. The updated progress of the shared variables u like the vanilla FedAvg, where the local updates and server aggregation are conducted alternately. The updated progress of the personalized variables vi is like the SGD with multiple local updates. Let function fww) satisfies Assumption 4, the models w = A(S) and : = A(S) are generated after T training rounds by the centralized method, we can bound their objective difference as:
fllf(wf :2) ;
nUra mS + GE [||u wi {]
(12)
nU'o
+ GE [||u" - [|]
GE [|Io
of [
ms
where sup = sup,, fu, v552) to is the upper bound of the loss and To toK + ko is specific index of the total iterations.
Proof. Let represent the index of the first time to sample the perturbation sample ž on the dataset S... When toK + Ko 1, A to kp
0. Then define
P(C*) P > 0) S P(T S toK + ko).
Expanding the probability we have:
El f ; -(Wf =)]l
[ P((E)) E -(
+ P((E)) E (II((w);;)) [(Wf;;
< T. [I1[(WT [(0]] =)] | + P(({)) sup ((0gz)
w..
< GI [|lw w || { +U(((E))
S GIE [|I" of' {] + GE [|o] - oe [1 +UP((E)).
Before the j* -th data on - client is sampled, the iterative states are identical on both and S. When the dataset S,- is selected, the perturbation sample Zz. can be selected with probability 1/S. Define x the event sampling dataset S,, and the observation moment Tn lg + kn- Then
19

---

Published as a conference paper at ICLR 2025
have:
P(({T) & (1 tok + ko)
8- K-1
P + x;
Σ
P tok + kx))
to K-1
ko
Σ P( - + x +
ΣΣ
E P = took + 1xx) x)P())
k=0
1-
ko
P(T= tk +
Σ
P(T= 1 + k)
nlto + ku)
mS
TTO
mS'
The random active clients with the probability of n/m in the second equality.
Lemma (Stability for D-PFL), follow the definition in (Hardt al., 2016; Zhou al., 2021) to upper bound the uniform stability term for the shared and personalized variables u and u; after round T the decentralized FL parudigm. Let function [(w,) satisfies Assumption 4, the models w = A(S) and w = A(S) are generated after training rounds by the decentralized method, we can bound their objective difference as:
(l] 2) f("f; ;2)]
UTo GE [m /i [E]
5
(13)
UT S
GE [ll?
of ll E + GIE
[1o of 11
Proof. For the D-PFL, the most part is the same as the proof for the central algorithms except the probability P(x) = 1 in Decentralized Federated Learning setup (because all clients will participate in the training). We bound their objective difference as:
+ Um
[llf(w f(w :2)11
SG
Σ E B iE[ml
(14)
Li
Lemma 4 (Upper Bound of Aggregation Gaps). According to Algorithu 2, the aggregation of C-PFLis un.0 u++1 Eiest uf, K.K., and the aggregation of D-PFL is u u EjeA, aiju
On both setups, we can upper bound the aggregation gaps by:
A A++1 < A
U.K.'
(15)
A 0,0
At K.
Proof. For the personal variable V; they always kept locally without aggregation, which means ptl. that V/ = ",, So obvious to see that of "i = c++ 25. 0.0 which proves that
A.0 At A Then prove the inequation for the shared variables We discuss it in central and decentralized mode respectively.
(1) C-PFL. setup (Acar al., 2021).
20

---

Published as a conference paper at ICLR 2025
In centralized federated learning, we select subset St in each communication round t. Thus have:
A+
11.0
Bllu
E
+1
[m
Σ
E
++
Σ
E1
(ui,K. K.
T2
T1
x [m]
PES*
iES
Σ 72
E
Σ
El| Elluf, K., Ki,
12 m
sE [m]
LiES
iE|ma
=E/m]
Elua
- Kk |= = Σ
Ellu T7 = K..
=
mm
sE[m]
sE[m]
(2) D-PFL setup (Sun et al., 2023c).
In decentralized federated learning, we aggregate the models in each neighborhood. Thus we have: Elluc क
A A
Σ
E
Σ
wij
(u),,. -ū,,K.) II
[E(m]
xE(m]
JEW.
Σ iE(m] JEW;
Why BlyB J.K, - -.KKKlll
Σ
Σ
wy.Blluf,K. - KGSKK
jEIm]
Elu,,, K.J.K.l K..
jE(m)
The last equality adopts the symmetry of the adjacent matrix W WT.
Lemma 5 (Decentralized Topologies Bounds of A). For 0 < X < 1 and 0 < a < 1, we have the following inequality:
Σ
Ky
(16)
1s+1)a ta:
where KY = (a) 2 + (I-a)eAIn 1 + 2
AIn
Proof. According to the accumulation, we have:
X---1 11 ----1
s=t x---11
I 1-1 +
(8+1)a
1)a²
ga
s=1
X --s-
X
1-s-1
= x +
ds +
ds
ga
ga
s=1
1=
/= 1/2
1
2 a
1==1
_1-11 + 1
ds
+
----1
ds
s=
1-a
2
x-1
511-+ a
2
In
Thus we have LHS < 1 (x-1ee+X)
gu +
2a
The first term can be bounded
(1-a)21
A
as 1 < (g)
IT and the second term can be bounded X ex which
indicates the selection of the constant NΛ (2) a
2a 2l) + (I-ajedlng + Ala
2a
Furthermore,
0 < a 1 < 1, we have KY S X(n 4)
2/2 cAin
+
/2 S max X x
(2+c) +
Ain
in 1
O max 1 x x//n Alm
with respect to the constant X.
21

---

Published as a conference paper at ICLR 2025
D.2 GENERALIZATION BOUNDS FOR C-PFL
Lemma 6 (Selecting the Same Sample). Under the Assumplion 1 and Assumption 4, the gradi- ent for the shared and personalized variables satisfy gu,b,k VuFi(ul, vi,x,;2) and g = F.P. uf.55 2), the local updates satisfy u/,x+1 = ui,x - -Vu,.. and of vi,4 = of -P We use E(V., u P. (uf k " K.,K333 =)] = V VuJi 1 "i,K,;2. and F.V.F( m[as==]] VoSi(ud, (1,i2) If we sample the same data 2 (not the z .5*) in dataset S and S at k iteration on round t, we have:
[1 x ill (1 T/. I M.l xll + The Muc El Ul KK
(17)
Bl - 7/,t s (1 + 7/ b. B Th + Th Low Elluf / - ū.ll-
Proof. We first conduct the local update for the personalized variables. The update progress in each round is as follows:
Elle k+1 - 11 || = Bl The no nolo Foll) s [ u k - Nil + n. Bl| (u,,, of, - Veli oh z)1l
S + m7 IT Blle, vll + 77 Bl 0/1l-
The alternative update progress for the shared variables is based on the updated of U.
E3 11, 77 1i1
E Eui, wi, na (Bu.i. Fe.1,))l
s E u - Wh,ell V.V x2 ( Vafi(iia x(x:))]]
I (1 + natn Ellftt whllll + Th I Elo - T.
Lemma 7 (Selecting the Different Sample). Assume Pu.ik VV Fi vl.,.22) and Foak P. Ties;)) the local updates satisfy u/, = whe - -79u... and of 1 = ohe - To we sample the different data samples 2s 5r and Ei- (simplified to and }), we have:
Bl 1 w/ 11 S (1 Ta In Bllli whi + nu Tn Vi, + 2mp(an 8w), E ElluAA - a I (1 + no L. Bll oflell + 1/ Lya Elluf - 7ill + 2mp
(18)
Proof. We first conduct the local update for the personalized variables. The update progress in each round is as follows:
El A+1 o/1 .+11
xll
Ellly x o al + B. V Ser (ufr 1os 2)
VoSr. (T),, x2)l
s Bllu i ll + B. V v. (u/ 1/ x)
Vofr (ūt,, 24 2]
+ E. V Vofe (wi,, 7 2) - Vofr (7%,, 1/ 2)11
$ (1 n. L.
|| + 7) Le Blluf - Will
n. V V.F (0)., 2) Vefu (ū, 0/. x.) V vef. (ū/, u. 2) + V.fi (7..
< (1 L. ال + 17. Low E ū + mm
The last inequality adopts E.. [xc] / (E(z))²
V E [
E[x- - E [T]]² < c.o
22

---

Published as a conference paper at ICLR 2025
The alternative update progress for the shared variables is based on the updated of
1+11
U.K."
Bljufr k+1 - ,i-,++1ll
Eljuir, x. - i/-,A 17u (B, Fu,
Elluße, x xl,, 1l + B. (ul Ao of R.: 2) - Vufi (T) (o x.) 2)
K. S Elluf,, x u//,, + V. f- (uls KK, 2) Vufi (uf (Th
x2,
K. + t. f.: (2) b K. 2) Vufi (u, Ao K,,
$ (1 + Mu Bl
xel + Ellli - VkKK, ||
T. for (0, 56 kK: V fir (ū, d. k.) V fi- Kr, ,..,
Vufi (77 . x.).
(1 MoLa BB u/ xfl + Bl xg + 21% (o + +.).
Lemma (Recursion in local update). Since 4 Aun + A according to the Lemma and 7, can bound the recursion in the local training:
20 + L LunAu.. Ln
Ao,+ (1 TT) (4
SL.
2( + du)
Luv Ku.K).
Au S (1 Lu) (A
SLu
Lu
Proof. In each iteration, the specific -"h data sample in the S₁. and Sy. is uniformly selected with the probability of 1/S. In other datasets S all the data samples are the same. Thus have the recursion for the personalized variables:
1
Σ TE [1 2 14,411ll [I]
E
[llo%
141 6+1
Th x+1l]
< (1 + tobb))
Bllof - T2lell + to Leve Σ Blluy
Kill
+ 1 - 1) 5)
[1 + m7 1B well + my Lo Bllu 775
+ S [11 + n/ Lu D Thull + n Lon Bllf - -Wll + 2n
2n.0. S
= (1 + I,) A + To L +
Similarly, for the shared variables, have the progress in each round
A 1
Σ
[1luf W6 xil+
[[lutr x+1 - -..
$ (1 + nh Iw)
Bllui - Thfall 1lll-10 + Tn Luw
Eluij - -.
1zt2
1
1
[(1 + nu Ellui Whell + The Las Elli 0i,K.11)
5
1
+ 5
[1 + n. L 1. wh + Th Blo - Dt. x |l + 2m, + 8,)]
2n (o + +dw)
(1 + 7/, L..) A + nht A +
S
23

---

Published as a conference paper at ICLR 2025
Then bound the recursion formulation
1o,++1 + 20.
81. + Lou S (1 + MoLo (A +
20.
Lo A1.0
Lo
St
Lo
2( + ōw)
Luw S (1+
2( + 8w)
Luv AioKKn
A A +, +
+ Lu
(A +
+
SLu
SLu
Lu
Zoom out the variables the left-hand side, then we finish the proof.
Main Proof for Theorem 1 According to the Lemma and 8, it is easy to bound the local stability term. We still obverse when the event happens, and we have A O. Therefore, we unwind
the recurrence formulation from T, K to to, kg- Let The = Hu ik and Th = IK+E are
decayed the communication round / and iteration k where thu S Ls and μo S I are specific constants, we have:
L
TK. II
(+ (1+Hul) MuLo
20
L A. u.o
AT K.
ATo +
+
SLi
L
(=(T-1))u++
TK. II
(1+ Molie
AT-1
20
L A u.K.
u.K,
+
SL
Lu
(T- 1)K++1
TK₁
(1+ MoLo (1o )
20
Lva
to 1.,K0
II
+
vi
SL
L
to K
(19)
TK.
20
II
SLe
+
bo (i 1ot1
20%
SLv
TR. < c مoLo In
n0
SL.
TK₁
Polu 20
To
ST.
Similarly, for the shared variables, we have the progress in round T:
(1+ Mulin |
TKK
( Ar + 2( + dd)
Liue AT T
A T
II
K.
STn
Lou
TK.
(1+ Mutiu ]
(TT + 2( + +uu)
TKa II
(1+ Mutun Inu
To AT K.K.
II
+
SLu
Lu
(T1))K++1
==(T-1)Kk+t
TK.
(14 Hoter (1+Natnn) )
A to + 2( + Su)
TK.
1 Nutir
Lig AT u.Ko
II
II
STen
Top
to K +o++
Ktoot
TK.
[4)]
/2(o, 8w)
Lue AT H.
II
+
SIn
Ttto
24

---

Published as a conference paper at ICLR 2025
Expand the first item, then we have:
A S etulia Sapuba(Ettan (Z 2)
2( + &ww)
L D.KK
+
SLu
Lu
< Mu n la tog
2( + Sul
Luu u.
+
SLi
Lu
TKu
Hubi
2( + 5w)
Luu
TK2
20
+
81.u
Tru
ST.
TO
TO
TKg
Nu Lu
2( + 6u)
IKu
Hucen
TKK
2
+
To
SLa
TO
SL, Lu
We that the bound of the local stability term for the shared variables in C-PFL has extra
term TK_ Ma (TK-) - TO
Po 2Laud= This is the alignment error caused by the alternative update for ST.
To
the personalized and shared variables, which related to the smoothness of Tuy Twp Juys the local epochs K,, Ke and the variance bound v..
Therefore, we get the combination of A and A as A
(Tku
pa 2( + 8u)
TKr
poLo
Lae
TKu youlo
20 ST
A K. + A
v.
+
1+
To
STn
To
T.p
TO
According to the Lemma 2, the first term the stability (condition is omitted for abbreviation) can be bound as:
E
T+1
Wi T1
E1|
(W
w(
- DEI
W - w(K)) II
71
11
EE
IE
<
[W'KK wxKk)
1 n
E Σ
(w. w(,K) ||
71
iES!
71 m
xE(m)
1
El| T wxx))
A
iE(m)
TKμ
I. 2(0,, + 8n)
TK₁
Me I.
Lue TKu Souput Lu
20 MSL.
1
TO
mSL
Lu
Therefore, can upper bound the stability in C-PFL as:
E flw :2) f(w]+! ;2)
G T+1 -T +1 +|+ nUTo
m.
TKu
Hubu 2G(o + 8nm)
nu'O
TKg
Hobo
Lae
TKu yea
2Go M.LL.
+
+
1
To
MSL.
mS
To
L,,
To
Obviously, we can select a proper event & with a proper To to minimize the upper bound. For
T E [1, by selecting To 22 Moota...)) as:
1tpe.
(TK) 18t,, we can minimize the bound
nD L.
[[("" (TTT,TTT:20 VT;2)) - - VT: ;T(2)
<
4
G((oa + 6u) + GoLa)
TtNE
(nUTK) 1422.
mS
L,
25

---

Published as a conference paper at ICLR 2025
D.3 GENERALIZATION BOUNDS FOR D-PFL
Lemma 9 (Bounded the local gradients). When (t,k) < ko). the sampled data is always the same between the different datasets, which shows T = When (. lo, only those updates at k 2 ko are different. When 1 > lo, all the local gradients difference during local iterations are non-zero. Thus we can first explore the upper bound of the stages with full K iterations when t to. Let the data sample z be the same random data sample and z/² be a different sample pair for abbreviation, when 2 to, have: If we sample the same data (not the 2iz ,rr in dataset C and C at k iteration on round t. we have:
pubo (0 + 8w)
Il T,,lll S
T TO
(20)
TS
Proof. According to the Lemma 4 and 8, Mu
we can also bound the local stability term for the personal is decayed as the communication round and
variables. Let the learning rate yo T
My
iteration & where Ho a specific constant, we have:
Hube 20,
20
A
(21)
SLy
S
T0
For shared variables, let u.k Da,0.k - Fe I2 Iu " Fumm, - Fu,mak
we have:
B BlImTal' u.k = Bl -u Iu Iu, - Iu Pumm, . ku,
< Thu
Ellya, - N.ll
iE[m)
|8| V..f(uul x) Vuli(TiiAA) 0f, x),,
Th
i
(S
1) E V a (u/ oo k.,, - V Vuls- (7) Ao of. K.: =)]l
S
+ 7u
E fir (u)- o// K. 2) Vufs. (ii'. of K.. 2) + Vufr. (iH 0. x,,,, V (T)) (T)e K., x.. 2)
8
$ 1hu
Σ
(Ir W.lll + Tow Elll - o.t
171
(S
- 1)mu, (Lo.16l1 -i Lu Luu Blle Tg,
S
Mu
(LuBllut, Whall + LuvBl vi k1,
7u
E for (it- o4 x., 2) Vufi- (i/i, "f.,,,,))) k.)) (V
(T o. x.. (uf Ty x.,)))))
21
1/u [L, - wiw Luv Elu - x))xx)) Il)
S
8E|m]
Lie +
20
La
SL
According to the Lemma 4, 8 and (21),), we bound the gradient difference as:
Luv
20u
E Bl
wllll S Tou
A
+
Lu
SIn
< T
pubu
20m + +8u)
Liw
T
Mobv
2,
+
T
Inm
S
where 7 = IK + k.
26

---

Published as a conference paper at ICLR 2025
Lemma 10 (Bounded the local gradients). When k) < (to. Ku), the sampled data is always the same between the different datasets, which shows r = 0. When t= to. only those updates at k 2 Ko different. When >> to, all the local gradients difference during local Ku, iterations are non-zero. Thus we can first explore the upper bound of the stages with full K₂ iterations when &. > to- Let the data sample be the same random data sample and 2/ be different sample pair for abbreviation
and 4. u,k
u0 wh wi,x
Tt -1i,
" k:
When t 2 to. we have:
Afpllo + do)mi
Ku
uulnn
Tuu
K
Mr. Li
E|| (I- P) t K. 1I (I-P)
+
s
TV
t tl-pati Li
Lu S
To
(22)
B|| (W - P) 2pucon + du
Ka
Mu Tea
Liu
K
Mylee
S
TO
11-Hubu
Liu
S
T
1 p1-pc
(23)
Proof. In the decentralized method, the aggregation performs after K local updates which demon- strates that the initial state of each round is U WU It also works on their difference
&t " = w K. Therefore, we have:
K,-1
4 K.
0,O
MoT u,k
W
K.K.
Σ
Mot
u.k
u.k-
k=
k=
Then prove the recurrence between adjacent rounds. Let P = the identity matrix, due to the double stochastic property of the adjacent matrix W, we have:
111 R and I E "=*
WP =P=PP PW=P.
Thus.
K_ -1
(I (I-P) P) 4' ( K. = (I--P) W u.
(I -I- [IP) P)
Mal u,k
k
-Wo 1-1 K.K,
k.-1
Σ Pu
u.k
PW K.K,
+WW u.K.
-p W
u.K.
Σ
nu na. a,k
k=
k=0
By taking the expectation of the norm on both sides, we have:
K.-1
K,-1
E| (I
P) 5 K.
S E
W
Σ
The L PW
K.K. 11 + EE|
Σ
nu rt Thl
k=
Ka-1
< E W6 1-1 K.
- PW
a.K, + 2E
u.kl
k=0
El (W () 15 111 N.K,
||+
m kll
K₂-1
$ AE - (I-P) T2-1
u.K, |1 + 2E
7a T.
The equality adopts (W P) W P - P w PW. We know the fact that $² = 0 where kt, kn). Thus unwinding the above inequality we have: u.k
K,-1
E| (I- (I-P) cr K.
1 (I P) to
+2
X-
Σ
nal "u
K
2 -ー
na r
r
==ta
k=0
27

---

Published as a conference paper at ICLR 2025
To maintain the term of W, we have:
Kg -1
(W P) D K.K,
= (W - P) W a.K, - (W
P)
Σ
7u- It.
a,k
k=
K.
=(W (W (W-P)) (W
P
The u.k
k=0
The second equality adopts (w- - P) PW W WP + PP (W-P) Therefore we have the following recursive formula:
- P) W.
K-1
E
W - -P) th K.
Ell (W P) PW
&) u.K.
+ Bll (W- - P)
Σ
mut
u,k
k=0
K-1
S XB ( - P)
AE
Σ k=0
na Tt xe
a.K.
The same as above, we can unwind this recurrence formulation from & to to as:
Ku -1
E| (W- - PP) D k., |l S X (w - P) th 11
Σ
x x
- E
mu
K.K.
==1o
1 E
nu re pll
Unwinding the summation on i and adopting Lemma 5, we have:
K
Σ 4-88
E
na
ll
1=1p
k=0
K,-1
Σ s=p
X
E| I 1 n.kl
k=0
20 + +oa)
K 11
Puuku
Lwne
20
Σ
X
K_ -1
pacL. Lu
Si lon
Inn Satte ton
8=to
k=0
a=to
k=U
2juu(au + t5))
K.
Luw In
2
Kg
(s juoko
1-8
x-
STutaaia
sKa
STy Lo
8Ka
20uu(ou + 5a)
Kn
Bubu
b
X--
Tuu
2p
Kn
by
X--
+
S
To
s taa Tou
Lu
S
sl -lppotey
s=to
s=to
20 + taa)
Kr
Bh Tr
X
Iran
2p
K
Bby
1-8-1
S
To
(s + 1)
Lu
S
To
(s + 1) to
$=tu
20 + Sa)MA
Kr
uubu
1
Luw T.u
Kn
Lo
1
S
To
[l fl-unt
To
f1-Hub.
28

---

Published as a conference paper at ICLR 2025
Therefore, get upper bound the aggregation gap which is related to the spectrum gap:
K.
B| (I - P)
K.
2
x
E
The u.
amto
k=U
40ulon + +wu)Ai
Ku
Me Te
Luu
AfloToA 5
Ku
Mole
+
S
TO
ft-puce
Luu
TD
(1-
k-1
E|l (W -P) P) th u.
3 Σ x
Bil
Pul'a,kl
s=ta
k=
(pu + +u))Ar
Ku
Lu
1
Luo
Pn s
K2
Lu
1
+
TO
fl-pukn
Luu
TO
tl-pube
The first inequality provides the upper bound between the difference between the averaged state and the vanilla state, and the second inequality provides the upper bound between the aggregated state and the averaged state.
Main Proof for Theorem 2 According to the Lemma and 8. easy to bound the local stability.
We obverse it when the event & happens, and we have A = O. Therefore, we unwind the recurrence
formulation from T, K to to. ko. Let 1/, = Py fuu and me Po ck are decayed as the
communication round and iteration where Huu S I. and He S J. are specific constants, we have:
E B M
K.K. II
km(m
Σ
El|
(1,00
c+1
)
Σ
nh (guss Fu.sk))
EE mm(m)
k=0
K,-1
Σ
Bll
1000
++1
(ui,.. K..) + (ui Wk.
Σ
nu (gu, - -....k))
<E [m]
Kn-1
El (u
2 (ui,k, x. Bll (ui,K, ih x..
+ El|
Σ
nu (ohrii Furcu)) II]
<E [m]
km
K
Σ kE(m)
Ell (wi,K.
wl || + E
Σ k==
Tue (guri - Burck)
xE(m)
1 (u
mE
(ui.
-ūt -it
m
ic(m)
KG,-1
< Σ (E(m)
Ell (wi,
- -i, || +
E
Σ k==
The (Suu - Du.ak)
xE [m]]
+ mE
Σ
|| (u - 27.
(ui.k. - W xx) 12
m
mE(m)
K
Σ
Ell (ui - -t + v mE
01+1
Φb Bi +
The (Bu.sx - Iu.s.k)
0.0
1E mm)
1==0
29

---

Published as a conference paper at ICLR 2025
Let 1
W K,,
K. have:
Σ ie[m]
Bllui, U.KKK II
K=-1
Σ (m(m)
Ell Ku k) || vm Wo.. $ Ku
Σ xE(ml
E
no
(gu,
-ulek) ||
k=0
K,,11 -1
Ell (u K. ||
R
Tu
(Bugi
VE (E(m)
xE(m]
/mm (W- P) K.
/mEl
T K.ll-
Since
1/.00 = 0 for the private variables, then we have the recursion:
K. -1
Σ El
M.K.
Σ kE(m]
B
( 1,0
(gu.i.
- Fo.i,k) II
=E|m]
k=
k.
E|
(u. - 8 k.
||
E
(obrii Ferik) !||
km
k=0
K
Bl (ui,K
E
Thu (Pe.A Do..k) 11-
[m(m
A m
k=
Therefore, we can bound this by two terms in one complete communication round. One the process of local multi-times SGD iterations, and the other is the aggregation step. For the local training process, we can continue to use Lemma 7, 8, and Let T = tK + & as above, we have:
2( + +
A.,k.
SLa
TK_-1
(I + malu))
(A 2(0, + 8m))
TK,-1
II
1 Hutt) )
A4. +
2( + 8w) SLy
SLm
A=0
k=0
FK-1
Puli
A 2(0,, + ōu)
A 2( Em))
SIn
SIu
Selni bo In( (+))
Auuo
2(0 5u))
[ 1+ Pa
A + 2( 8u))
SLu
SLu
Vm(LE] (W - P) of K. + +Bll (P 1) K. 11) + 2( + 6w) SIu
A:11 u.
Mee Teu
+ 2(0, + +dw)
1+1
Mu
1-1 u.K."
+ mm
(E)l (W - d K. + Ell (P I) E &i,k,
Shu
++1
2(0,, + 8u)
6 Bympulo 8,)
K
Inu
+
Io
1-1 u.K.
+
t
SLu
S
t
fl pl-phhh..
local updates
aggrogation
Lue
6 6
Kg Muke
t 1 t
agho
T.n
To
aggregation gaps
30

---

Published as a conference paper at ICLR 2025
The last adopts the (22) and (23), and the fact À S 1. Obviously, in the decentralized federated learning setup, the first term still comes from the updates of the local training. The second term comes from the aggregation gaps, which is related to the spectrum gap X.
For the private variables, since we do not exchange them with neighbors, we have:
KK-1
K, +
20
II (1 Tobo)
(Aio
20, SLo
SL
k=0
K,=1
1+ Mohie ]
A +
20,
ST.
k=
Kk-1
20
A +
SLv
k=
ellibbe _
A +
20
SLu
S Ehiole In 1om 142)
A +
20
SLi
t
Mobo
20
A +
SL.
Unwinding this from to T, have:
AT K,KK + 2(0, + +80)
SLa
TKn
aubu 2(0 + ddu)
6ympuulo + &u)ax
K
Lu
Σ
T
[++
1
bu
1
+
Stn
S
To
t
fl-nubu
to
6 GymplooBiht
Ku
Σ
+
Lu
1 1l-vobo
STv
TO
t=o+1 1
TKu
Mubu 2(0 + 8a)
12/mpuu(ou + Juka
(a Lou
Σ
1
SLu
S
(=
Lue
12 12VmpuOOnN
Ku
Σ
1
Lu
S
To
TKu
Hubu 2(0,, + 8a)
12 12
+ SuuNN
Kg
by Huckn
b=
To
SIn
S
To
Mut
Law
12 OKM
Kn
Mo Lo ganke
1=
Lu
5
To
Ho
11=to+1
TK2
Mubu 2(1 + m/RR)) (oa + 8a)
Liw
(TKu
Hobe
12/TRRxe
+
SLu
Lu
SLu
The second inequality adopts the fact that For the personalized variables, unwinding this from ty to T. we have:
6+1 1
< when and the fact of 0 < $
20 SL.
TK₁
Pr 20
AT +
<
To
SL.
31

---

Published as a conference paper at ICLR 2025
Then the first term in the stability (conditions is omitted for abbreviation) can be bounded as:
B B T+1
-T+1| -
1
Ell
[uf,..
K.,.K.))
m
im[m]
T
Pahu 2 (1 + m)K)) (o + du))
Lnw Iiu
TKK
aoLo
12/TRAT
+
70
mSLu
To
mSL.
1
T
Nole
20.
B| B T+1 +T+11 S
E
T -V, ||
To
SL
3E[m]
Therefore, we can upper bound the stability decentralized federated learning as: [1l :12 - f(w :0) S GE [[lee ++1 - / +11 || {] + TO
S
Un
GE [|Iu - |1 E) GIE [||o
2( + +.wG
MRA
TKu
puli
UTo S
SIma
m
TO
Lue
TKu
12 12
20.G
(TKe
Tuu
TO
STL
Shp
TO
2( + G.]G
(1+6 M
TK₁
le
G
TK₁
SLn
TO
SLn
1 m2
TK2
UTO
+ Lm
S
The same as the centralized setup, we can select proper event & with a proper To to minimize the eггоr of the stability. To simplify subsequent analysis, we assume μL = max (oo and K = max(K,, K,). For [1, by selecting To
(TK) The 2G +8, (1..,,t8,.1,(00066611 (.160 +22r by Ine (m+6VmmK)) ItPE we get the minimal generaliza-
Umh.14
tion bound for D-PFL:
E
| ;2)) " [=i23)l]
(o + Sn)G (1 + 6WmR))) + L.m
JoG Teg (1 + 6 mIy
Time
$ 5 (UTK) 1au
32


Reviews:
[{"review_id": "RoZ38Rf5B2", "reviewer": "Reviewer_wmwb", "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.", "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?\n\n2. What are the main technical difficulties in the analysis, comparing to existing literature?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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). \n\n2. The analysis of the paper is standard as literature, which means there is limited technical contribution of this paper.\n\n3. 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.\n\nI am willing to raise the score if my concerns are addressed.\n\nReference:\n\nSun, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AMMgLCFAXg", "reviewer": "Reviewer_tNFV", "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.\n\n[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.", "questions": "Please address the questions in Weaknesses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "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:**\n\n**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.\n\n**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? \n\n**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. \n\n**Presentation issues:** \n\n**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.\n\n**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. \n\n**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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HO19CZk1Al", "reviewer": "Reviewer_Nkbg", "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.", "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)$.\n2. 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$.\n3. The notation $I$ requires further explanation, as it is unclear how to derive the bound for $P(\\{\\xi^c\\})$;\n4. 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3oEIvUN2xn", "reviewer": "Reviewer_45Sj", "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.", "questions": "see the weakness part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The major contribution of this paper is from the theoretical aspect in generalization.\n\n1. 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.\n\n2. This paper offers a rigorous analysis, with well-rounded discussions and comparisons that cover various specific cases.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)