Understanding the Statistical Accuracy-Communication Trade-off in Personalized Federated Learning with Minimax Guarantees
Authors: Xin Yu
Zelin He
Ying Sun
Lingzhou Xue
Runze Li
Venue: ICML 2025 poster (2025)
Keywords: Personalized Federated Learning
Statistical Complexity
Communication Complexity
Primary area: theory->learning_theory

Abstract: Personalized federated learning (PFL) offers a flexible framework for aggregating information across distributed clients with heterogeneous data. This work considers a personalized federated learning setting that simultaneously learns global and local models. While purely local training has no communication cost, collaborative learning among the clients can leverage shared knowledge to improve statistical accuracy, presenting an accuracy-communication trade-off in personalized federated learning. However, the theoretical analysis of how personalization quantitatively influences sample and algorithmic efficiency and their inherent trade-off is largely unexplored. This paper makes a contribution towards filling this gap, by providing a quantitative characterization of the personalization degree on the tradeoff. The results further offer theoretical insights for choosing the personalization degree. As a side contribution, we establish the minimax optimality in terms of statistical accuracy for a widely studied PFL formulation. The theoretical result is validated on both synthetic and real-world datasets and its generalizability is verified in a non-convex setting.

Understanding the Statistical Accuracy-Communicat Trade-off in Personalized Federated Learning with Minimax Guarantees
Xin Yu Zelin He
Ying Sun
Lingzhou Xue
Runze Li
Abstract
the presence of various data across clients is data hetero- geneity. In such cases, a single global model may fail to generalize well to all clients, motivating the need for model personalization. PFL enhances FL by learning personalized models tailored to individual clients, and has demonstrated strong empirical performance in various applications, such driver monitoring (Yuan al., 2023), and mobile com- puting (Zhang et al., 2024).
Personalized federated learning (PFL) offers a flexible framework for aggregating information across distributed clients with heterogeneous data. This work considers a personalized federated learning setting that simultaneously learns global and local models. While purely local training has communication cost, collaborative learn- ing among the clients can leverage shared knowl- edge to improve statistical accuracy, presenting trade-off in personal- ized federated learning. However, the theoretical analysis of how personalization quantitatively in- fluences sample and algorithmic efficiency and their inherent trade-off is largely unexplored. This paper makes contribution towards filling this gap, by providing a quantitative characterization of the personalization degree on the tradeoff. The results further offers thcoretical insights for choos- ing the personalization degree. As side contri- bution, establish the minimax optimality in terms of statistical accuracy for a widely studied PFL formulation. The theoretical result is vali- dated on both synthetic and real-world datasets and its generalizability is verified in a non-convex setting.
An important question in PFL is determining the degree of personalization, which controls the transition between fully collaborative training and pure local training. higher degree of collaboration (less personalization) typically re- quires more frequent information exchange, potentially im- proving learning accuracy when client data distributions are similar. Conversely, increasing personalization reduces communication costs by prioritizing localized training, but may lead to higher generalization errors due to the limited size client datasets (Paragliola, 2022). Understanding this trade-off is essential for optimizing model performance under communication constraints.
an
Most existing works focus purely on the algorithmic per- spective of PFI. (Lin et al., 2022; Li et al., 2024b; Wang et al., 2022; 2024b). However, the statistical accuracy of the solutions obtained in PFL remains largely unexplored. As a result, the connections between statistical accuracy, communication efficiency, and their trade-offs are not well understood, leaving theoretical gap in understanding how to select the optimal personalization degree. In this paper, we fill in this gap by providing a fine- fine-grained theoretical analysis of widely adopted PFL problem formulation given by (2) that trains simultaneously local and global models. We quantitatively analyze the influence of personalization on both statistical and optimization convergence rates for each of the local models. Specifically, our contribution can be summarized follows:
1. Introduction
Federated Learning (FL) (McMahan et al., 2017) has emerged as a promising learning framework for aggregating information from distributed data, allowing clients to collab- oratively train shared global model communication- efficient manner. However, critical challenge arising in
"Equal contribution 'Department of Statistics, The Pennsyl- vania State University, University Park, PA 16802, USA "School of Electrical Engineering and Computer Science, The Pennsyl- vania State University, University Park, PA 16802, USA. Corre- spondence to: Ying Sun pyu.ui,,0ssuu.uu Lingzhou Xue <lzxue@ <lexue@@ssu.cuu>.
Statistical Accuracy with Optimal Guarantee. We provide a non-asymptotic statistical convergence rate of the solution of Problem (2), revealing how personaliza- tion degree influences the statistical accuracy of each local model. In particular, as the personalization degree increases, the rate approaches that of pure local training, (l/nn). where is the sample size per client. Conversely, decreas-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Understanding the Statistical Accuray-Communication Trade-off in Personalized Federated Learning with Minimax Guarantees
ing the personalization degree allows the models to utilize information across all clients, achieving rate closer to (11((mm) + R²), where mn is the total sample size of all clients and R quantifies the statistical heterogeneity of the local datasets. We further establish the minimax optimality of the derived statistical rates, demonstrating the tightness of our analysis. To the best of our knowledge, this is the first work to achieve such an optimality.
to all clients and the other specific each client. Our work, however, differs in that we focus on a personalized FL set- ting with a mixture of global and local models. Closely related are multi-task learning methods (Liang et al., 2020) and transfer learning methods (Li et al., 2022; He et al., 2024a;b), but the statistical rate is established for either the average of all models or only the target model. Therefore, it remains unclear how personalization influences the sta- tistical accuracy of each individual local model in these settings.
Communication Efficiency under Personalization. On the optimization aspect, we treat Problem (2) as bi-level problem and propose (stochastic) algorithms with an explicit characterization of computation and communication com- plexity. We establish that the communication cost of finding an E-solution is (1 X+L log )) and the computation cost in terms of gradient evaluations is O( log }). where À is a parameter determining the personalization degree. This demonstrates that a smaller X, corresponding to a higher de- gree of personalization, reduces communication complexity without incurring additional computational overhead.
In the FL community. personalized FL methods can be broadly divided into two main strands. Different from the works mentioned previously, studies here primarily focus on the properties of the iterates generated by the algorithms. One line of work (Arivazhagan et al., 2019; Liang et al.. 2020; Singhal et al., 2021; Collins al., 2021) is based on the representation learning formulation. Another line of work (Smith et al., 2017; Li et al., 2020; Hanzely & Richtárik, 2020; Hanzely et al., 2020; Li & Richtárik, 2024) achieves personalization by relaxing the requirement of learning common global model through regularization techniques. In particular, algorithms and complexity lower bounds specific to Problem (2) were studied in (Li et al., 2020; Hanzely et al., 2020: T Dinh et al., 2020; Hanzely & Richtárik, 2020; Li et al., 2021), see Table 1 for detailed comparison. These works study Problem (2) from a pure optimization perspective and have not provided how person- alization influences statistical accuracy and, consequently, the trade-off between statistical accuracy and communica- tion efficiency.
eccuracyCoommunicatii Tradeoff with Empirical Validation. Building on our theoretical results for statistical and optimization convergence, we quantitatively character- ize the trade-off between statistical accuracy and communi- cation efficiency in PFL and discuss practical insights for selecting the personalization degree. We then conduct nu- merical studies on logistic regression with synthetic data and real-world data under our assumptions. The results corroborate our theoretical findings. We further test the numerical performance with CNN models, showing that the theoretical results, though established under convexity assumptions, generalize to non-convex settings.
There are only few recent works we are aware of that study the statistical accuracy of regularization-basse PFL. Specifically, Cheng et al. (2023) investigates the asymptotic behavior of the (personalized) federated learning under an over wver-parameterizes linear regression model; neither a finite- sample rate nor algorithms are provided. Chen et al. (2023c) studies Problem (2) and establishes non-asymptotic sam- ple complexity. However, even with some overly strong as- sumptions, their analysis cannot match the statistical lower bound in most cases. Furthermore, neither of these works reveals the trade-off. While (Bietti et al., 2022) studies the influence of personalization in PFI., their focus is on the trade-off between privacy and optimization error, leaving the accuracy-communicat trade-off unexplored.
2. Related Works
In recent years, FL has become an attractive solution for training models locally on distributed clients, rather than transferring data to a single node for centralized processing (Mammen, 2021; Wen et al., 2023; Beltrán et al., 2023). As each client generates its local data, statistical heterogeneity naturally arises with data being non-identically distributed between clients (Li et al., 2020; Ye et al., 2023). Given the variability of data in network, model personalization is an appealing strategy used to improve statistical accuracy for each client. Formulations enabling model personaliza- tion have been studied independently from multiple fields. For example, meta-learning (Chen et al., 2018; Jiang et al., 2019; Khodak et al., 2019; Fallah et al., 2020) assumes all local models follow a common distribution. By minimizing the average validation loss, these methods aim to learn meta-model that generalizes well to unseen new tasks. Rep- resentation learning (Zhou et al., 2020; Wang et al., 2024a) focuses on a setting where the local models can be repre- sented as the composition of two parts, with one common
Notation. Denote [n] := 21, n.). || lla denotes the & norm for vectors and the Frobenius norm for matri- ces. For two non-negative sequences {an,, ), {bm we denote an S b, if a, I Cbb, for some constant C > 0 when n is sufficiently large. We also use an = O (b..). whose mean- ing is the same as a, S bn. Ö(-) hides logarithmic factors. For two real numbers a, b, we let a b min(a, b) and V b max(a, b).
2

---

Understanding the Statistical Accuracy-Communicite Trade-off in Personalized Federated Learning with Minimax Guarantees
3. Preliminaries
the choice of À also potentially affects solving Problem (2) algorithmically in the FL. setting. Intuitively, for large X, we anticipate more frequent communications among the clients to facilitate collaboration as the local models are more tightly coupled to the global model. In contrast, a smaller À encourages more independent updates and reduces the need for communication, with LocalTrrin (cf.(3)) being an edge case where all clients train independently without any communication.
We consider an FL setting with m clients. Each client has a collection of data S, = {2ig) jejjn] where n, is the sample size of client with elements i.i.d. drawn from distribution D. The data distributions among the clients are possibly heterogeneous, For each client i, the ultimate goal is to find a model that minimizes its local risk at the population level, defined as:
w- E argmin ESwD,
(1)
We quantify both the statistical and optimization error of PFL algorithm applied to Problem (2) by evaluating the Euclidean distance between the algorithm's output after t
where f(w,2) 2) is a loss function measuring the fitness of w to data point 2. We call w E Ie the ground truth model for client i. To understand the influence of model personalization, we study the following widely adopted PFL problem (Hanzely & Richtárik, 2020; Mishchenko et al., 2023; Li et al., 2020):
communication rounds, w!") and the ground truth local model w for each client i E [m]. Let ((() denote the solution of i-th local model in Problem (2). We have the following decomposition:
|m w0''|1 S 2 ll 1 +2 ( w. (0) 1
A (1o())) - -00) Σ ps (.(w" + 2
min we(
optimization error
statistical error
{wo pm
AE/m]
In the rest of the paper, we first establish the statistical and optimization convergence rates independently. We then inte- grate these results to formally provide the trade-off between statistical accuracy and communication efficiency under different levels of personalization.
(2)
where wo()) and (9) are respectively the global and i-th lo- cal model be learned, (ww,, S:) == شي= ((w, 24//me is the empirical risk of client on its local data S,, and the last term is a regularization term with parameter À con- trolling the personalization degree. The set (ps be is a collection of nonnegative weights with Σ P: = 1.
4. Convergence Rate Analysis
4.1. Effect of Personalization on Statistical Accuracy
In Problem (2), each client learns a personalized model
( by fitting to its local data S,, while collaboration is achieved by shrinking the local models w(()) towards com- mon global model w()), As À + O, the influence of the global model diminishes, and Problem (2) increasingly be- haves like the TocilTrain problem:
In this section, we analyze how the choice of À influences the statistical accuracy of the solution to Problem (2). Recall the ground truth local model w (t) I defined in (1). Next, we introduce the measure of statistical heterogeneity and define
the parameter space for the statistical estimation problem. Specifically, we consider estimating w0! (4) from the following parameter space:
LocalTrain: min [, (6) (,,),, Vi E [m].
(3)
w
where each client independently trains its model using only local data. In this case, Problem (2) is fully decoupled into m separate problems, achieving the maximum degree of personalization. On the other hand, as X b oo, the regularization term shrinks all local models w(() towards the global model w()) This corresponds to reducing the personalization degree and eventually pushes Problem (2)
m
P(R) = (w (ww)))
Jm
w
(1)
p pi (8)
S R2
Vi E [m]]
In (5), the statistical heterogeneity is measured as the Eu- clidean distance between the ground truth local models and their weighted average. A larger R indicates a larger dif- ference among the clients' local models, hence stronger statistical heterogeneity. Such measure is commonly im- posed in the existing literature (Li et al., 2023; Chen et al., 2023b;c; Duan & Wang, 2023). More discussion about the parameter space PPR)) (R)) can be found in Appendix A. We assume the model dimension d is finite.
to another extreme given by:
GlobalTrain:
min mu Vie(m)
Σ Ep (,) Si), 1=1
(4)
where the knowledge from all clients is pooled to train a single global model. Adjusting X, therefore, controls the degree of personalization among clients and thus affects the statistical accuracy of the resulting solution. Noticeably,
Under such a parameter space, we aim to investigate the statistical accuracy of the solution to Problem (2) measured
3

---

Understanding the Statistical Accuray-Commmuniatton Trade-off in Personalized Federated Learning with Minimax Guarantees
by E| ( _ I|2 where the expectation is taken with respect to the joint distribution.
first term approaches O(1/N + R²). Here, O(1/N) cor- responds the sample complexity one could obtain if the data distributions of the clients are homogeneous, re- flecting the benefit of collaborative training. Term O reflects the negative impact due to the bias introduced by statistical heterogeneity. In contrast, the second term in (8) increases with X, showing that a smaller X leads to a rate closer to ((1/n) corresponding to that of pure local training. This rate is independent of R. making robust to high data heterogeneity but at the expense of reduced sam- ple efficiency. Together, these results provide a continuous and quantitative characterization of how the personalization degree, governed by X, determines the statistical accuracy of the solution (
Remark 1. Note that some existing literature adopts alter- native metrics, such as individual excess risk (Chen et al., 2023c) to measure the statistical error. These two metrics are equivalent under the strong convexity and smoothness conditions on the loss functions.
We study Problem (2) under the following regularity condi- tions.
Assumption 1 (Smoothness). The loss function E(:, z) is L-smooth, i.e. for any z, y E Rd:
[V 2) Vl(y.2) S L||x vll, 42.
(6)
Assumption (Strong Convexity). The empirical loss L,(,, S,) is p-strongly convex, i.e., for any x. y E R and e [m]:
Minimax-optimal Statistical Accuracy. To demonstrate the tightmess of our analysis, we now show that direct implication of Theorem 1, the local models ( are rate- optimal. Denoting K I//j as the conditional number, we have the following corollary.
1 | L(x,S)) 2 L. S1)+ (v. y)
y11..
2
Corollary 1. Suppose Assumption 1, 2 and 3 hold and consider the parameter space PPR given by (5). If setting
Assumption (Bound Gradient Variance at Opti- mum). There exists a nonnegative constant p such that Eg<D, (V((w (0) 2)]2 S p² for all i E [m]]
A 2 max {GAN² L, (2K V 5) 1 21. +2² } s- when R S "1"""+pp'NN
V then for all i [m], the local model ((() obtained by solving Problem (2) satisfy
Vie and S p² nyRZ when R >> }.
The strong convexity and smoothness assumptions are used to establish the estimation error and are widely adopted in the theoretical analysis of regularization-bu based PFL (T Dinh
2 =
1
R2 H
E W -0:0-w!!
C4
(9)
et al., 2020; Deng et al., 2020; Hanzely & Richtárik, 2020; Hanzely et al., 2020) and FL (Chen et al., 2023c; Cheng et al., 2023). Assumption 3 is used to quantify the obser- vation noise, and is also standard in the literature (Duan & Wang, 2023; Chen et al., 2023c).
where constants C3 and C4 are defined in (91).
See Appendix A.3 for the proof. In addition, Theorem 8 in Chen et al. (2023c) states for all E [m]] and any estimator (t) that is a measurable function of data {5,)m we have
For simplicity, we assume pt 1/m and n; n for all i [m]. The following theorem provides an upperbound of the estimation error E| (+)) - ( l as a function of X.
inf 1609)
sup [w ygL EP(()
E
B
w
1 2 N
+
+R 1
Theorem 1. Suppose Assumption 1, 2 and 3 hold and con- sider the parameter space P(R) given by (5). The local 1 obtained by solving Problem (2) satisfy
Therefore, Corollary shows that with an appropriate choice of X, the established rate achieves the minimax lower bound. A detailed comparison with prior results can be found in Appendix A.5, along with a discussion of several novel techniques developed to derive our result. While this re- sult focuses on statistical accuracy and is not directly tied to the accuracy- communication trade-off, it highlights the tightness of our analysis. Furthermore, the techniques intro- duced to obtain the results are of independent interest. To the best of our knowledge, this is the first work to establish minimax- -ottmalx-ppiimalityy for the solutions of Problem (2).
models (w (w(() (m
E (1()
!
48pp2 1
44822
1
< -min
+
+3
R²
+
112 N
112
91
(A)
(8)
4p2 1 nt2 n
(
(Ap²²)
1
1
4
8
n2 }
+
-
x+
n1
1
where N = mn and 91 (A), defined in (70). is monotoni- cally increasing function of X with lim q (A) co.
Remark 2 (Technical Novelty of The Analysis). Unlike previous results (Chen et al., 2023c) which are algorithm- dependent, our analysis does not rely on any algorithm but directly tackles the objective function, establishing rates us- ing purely the properties of the loss. Specifically, using the
See Appendix A.3 for the proof. The bound given by (8) consists of two terms. The first term decreases as À in-
creases. When À - 0o, the term (qi (A)] -> and the
4

---

Understanding the Statistical Accuray--oommuniatton Trade-off in Personalized Federated Learning with Minimax Guarantees
strong convexity of the loss function, we first proved the esti- mation error is bounded by the gradient norm and an extra statistical heterogeneity term controlled by X, as detailed in Equation (33). This allows us to show for large R. small can be chosen to yield rate (n) and match one of the worst cases in the lower bound. For the complementary case R S 1/1 we leveraged the GlobalTrain solution WGT as a bridge and proved the solutions of Problem (2) to uGT are bounded by a term inversely proportional to X (cf. Lemma 4), implying that they can be made arbitrarily close to wGr by setting X small. This, logether with the rate of WGT, yields a rate of O(1/N + )²²). Combining the two cases, we proved minimax optimality. Not only each piece of the above results are new, but more importantly, identifying they are the key ingredients to show the solution of (2) is minimax optimal, are the technical novelties of this proof.
Lemma 1. Under Assumption I and 2, P3 is pg -y-rronggyy Au convex and Lg-smooth, with Ha = x+a and Lg = AL each h, is pe-strongly convex and Le-smooth, with μee I. + X and Le = L X, and the mapping w :R - R is L Lipschitz with L = 2
X+L
Lemma 2 (Lemaréchal & Sagastizábal (1997)), Under
Assumption 2, each F; Rdd - R is continuously dif-
ferentiable, and the gradient is given by VF((w())) \(w(o) w (w)))).
Lemma and Lemma 2 suggest applying a simple gradient algorithm to optimize w()):
(g) = w.!) VF(W w t++
(g)
1
m
(g) wi - ww. 100 (w)
(12)
= w
7d
m
Notice that Theorem 1 and Corollary focus on establishing the statistical rate for the solution in Problem (2), T To fully quantify the error of the output of PFL algorithms, we need to establish the optimization error from the algorithm as well, as detailed in the next section.
where w!!)) is the update at the communication round 4. ? > 0 is a step size to be properly set (cf. Theorem 2). To implement (12), in each communication round the server broadcasts w((") all clients, then each client updates its local model w. (w, (g) and uploads to the server.
4.2. Effect of Personalization on Communication Efficiency
Note that executing the update (12) requires each client i computing the minimizer (+) (w. In general, the sub- problem (11) does not have a closed-form solution. There- fore, computing the exact gradient V will incur a high computation cost as well as high latency for the learning process. Leveraging recent advancements in bilevel opti- mization algorithm design (Ji et al., 2022), we address this issue by approximating uo (10 (9) with a finite number of K gradient steps. Specifically, we let each client i maintain (1) local model wi,k. Per communication round I, wi,k is ini-
In this section, we provide an FL algorithm for solving Problem (2) along with its convergence analysis, showing the impact of the personalization degree on communication and computation complexity. Notice that if we define the local objective of each client i as
h:(w!() (1) u (0)) = T.,(w' 10 S))
2 2110 w (012
(6)
then Problem (2) can be rewritten in the following bilevel (iterated minimization) form:
(i) (i)
tialized to be 20.0 w 1- as warm start, and updated according to
m m Σ Fi F((w(()))
min F(w(()) w(n)
( w Wt 1,6+1 wiek 17 Vh, (w (.).))
(
(13)
(10)
where (0) == min h,(w (0)). wil)
for k = 0, ...., K - 1, where (w g ( for notation
(t)
simplicity, denotes the partial gradient of h; with respect to ( The overall procedure is summarized in Alg, 1, see Appendix B.1.
The reformulation (10) has finite-sum minimization struc- ture, with each component F; being the Moreau enve- lope (Moreau, 1965; Yosida, 1964) of L4. Let w (t) (1o())) be the minimizer of h w(())) i.e..
Theorem 2. Suppose Assumptions I and 2 hold. Let
(w (9) h120 and (wi, )120 be the sequence generated by Algorithm I with yy < <1/T,, TT.. 7 S 1/Te,, and the inner loop iteration number satisfying
w (6) (w) = prox L. /A (w)
:= arg min he (1) ( w(t)
(0)
(11)
(2 64L (1 mue) ( (11 (14)
then w) converges to ((9)) linearly at rate 1 - (7 (214))2/2, and w converges to w(() linearly at the same rate for any E [m].
The following lemmas provide properties of F., h2 and w instrumental to the algorithm design and rate analysis. The proof can be found in Appendix B.2.
5

---

Understanding the Statistical Accuray--Communicttoo Trade-off in Personalized Federated Learning with Minimax Guarantees
The proof of Theorem 2 can be found in Appendix B.3 and B.3.2. Theorem shows that with sufficiently small step sizes, both the local and global models converge lin- early. The personalization degree, controlled by A, plays critical role in influencing the algorithm's 's communication efficiency. A small À (indicating higher personalization) yields a small Lg. and thus permits a larger choice of the step size 7. By the expression of the convergence rate 1 1 (1(14))/2 - (T/H4)2/2 we can see less communication round would be required to reach an e-optimal solution. However, increasing 7 will also decrease the right hand side of (14), implying that a larger number of local gradient steps K should be taken to fulfill the condition. To pro- vide a more concrete characterization of these dynamies, we present Corollary 2, which quantifies the communication and computation complexities under specific choices of tun- ing parameters. The proof of Corollary 2 can be found in Appendix B.4.
rate of FedCLUP, showing that it takes O
A+u KK X+Z
-log
rounds of communication to obtain an output w!!) within an error ball of size (O(E) + f o² is the variance of the stochastic gradient defined in As- sumption 4 in Appendix B.5 and B is the mini-batch size. Therefore, the influence of À communication complexity is consistent with the noiseless setting presented in Corollary 2. Additionally, one may note that in the stochastic setting, the error due to the stochastic noise scales inversely with the number of participating clients, showing the advantage of client collaboration in reducing the variance of w)
o² p2 around T(0) Here
5. Communication-Accuray Trade-off
Building on the results established in Section 4. and 4.2, we cast insights on the trade-off between communication ef- ficiency and statistical accuracy, and discuss its implications real- world practice.
Corollary 2. In the setting of Theorem 2, if we further
choose the step size n (X L)-1, 7 (X+ (2XL), and the inner loop iteration number K = O((A+ + L)/(A + 1)), then we converges to (6))) linearly at rate - (A +
Corollary 3. Under the conditions of Theorem I and Corol-
(i) lary 2, WT.K generated by Algorithm I satisfies
()/(A<(>+ + p)), and (5) converges to w linearly at the same rate for any i E [m]. Thus the communication and computation complexity for Algorithm I to find an e-solution -o(9) S and 1100700 u 111 < E) are
E
( T.K
w
2
1
1
L-
T
E
(6)
(15)
(i.e., ( (g)
1x
4x(A + 14)
follows (n := L/u):
0
[
1
n²²
+
(
N
(A)
(i) # communication rounds = (m.
A A+/
logg )
A ++I. L
for any i E [m], where qı (A) and (A) defined in (70) and (67), respectively, are monotonically increasing functions of A with lim (A) = 3o and lim 92 (A) = 0.
(ii) # gradient evaluations = Ö 0(x
(k..00g log
1)
Corollary 2 clearly shows the influence of the personaliza- tion degree X on the communication cost. Specifically, as A increases from 0 to co, the communication complexity increases from Olog((1 (1))) to (oxlog(1/))) This fact corroborates our intuition that a higher degree of collabora- tion requires more communication resources. Moreover, the result given by Corollary 2 also indicates that the total com- putation cost is independent of X. As such, can that model personalization can provably reduce the communica- tion cost without any extra computation overhead. Notice that although personalization indeed enhances communi- cation efficiency, doing so may deteriorate the statistical accuracy of the local models. In the next section, we will discuss in detail the trade-off between communication and statistical accuracy.
See Appendix C for the proof. When collaborative learning is beneficial, i.e., when R² S 1/n, in this case, Corollary establishes that the minimax-optime statistical rate is O1// + R²2) As À increases, (2) (A)] monotonically decreases to zero, leading to improved statistical accuracy, approaching the optimal accuracy. However, since the opti- mization error in (15) is monotonically increasing with X, higher degree of collaboration will also results in slower convergence over communication rounds. Consequently, Corollary 3 implies that when the data heterogeneity is relatively low, increasing personalization will improve com- munication efficiency but at the expense of lower statistical accuracy, and vice versa. Such an opposite effect of the personalization degree on the statistical accuracy and com- munication efficiency leads to accuracy- commuiccccommmiiaaiiion trade-off.
We also provide an extension of Alg. 1 to the stochastic set- ting using mini-batch stochastic gradients for the local up- dates. The proposed algorithm, termed FedCLUP, is given in Appendix B.5. Following similar argument to Theorem 2, Theorem 3 in Appendix B.5 establishes the convergence
As the optimization error vanishes when T + co, the statis- tical error dominates the total error in Corollary 3. However, the associated communication cost becomes prohibitively large to achieve such an error. Therefore, balancing the
6

---

Understanding the Statistical Accuray--Communiatton Trade-off in Personalized Federated Learning with Minimax Guarantees
Table I. Comparison of the existing works analyzing Problem (evx denotes convexity and s-evx denotes strong convexity).
Methods
Convexity
Bounded Domain Computation Cost per Round
Communication Cost
Stutistical Error
FedProx (Li et al., 2020)
CYX
O(A/ ((p))
pFedMe (T Dinh et al., 2020)
S-CVX
x
(()((mR))
X
L2GD (Hanzely & Richtárik, 2020)
S-EVX
OU
O 2hx log(
AL2SGD (Hanzely et al., 2020)
S-CVX
X
(inty (ALLE
Oly min (Lin AY log 1)
X
Algorithm (Chen et al., 2023c)
V
O(1/))
FedCLUP
X
O Ae log 5
(1) Controlled by the precision of inexact solution. p > 0 measures the subproblem solution accuracy.
(4) Related the subiteration number R and the precision v.
optimization and statistical errors is crucial for achieving a target total error with efficient resource usage. Under the
6.1. Experimental Details
Synthetic Dataset. We generate two cases of synthetic dataset: (1)As our theoretical analysis is established un- der strong convexity, first, we consider an overdetermined linear regression task, where the choice of hyparamter is strictly followed Corollary 3. (2) We follow a similar procedure to prior works (Li et al., 2020) but with some modifications to align with the setup in this paper. Specifi- cally, for each client we generate samples (Xk. yv), where the labels yı are produced by logistic regression model yk argmax(o((w} X))), with a being the sigmoid func- tion. The feature vectors X; are drawn from multivari- ate normal distribution N( Σ), where 2k ~ (O 1) and the covariance matrix Σ follows a diagonal structure E = 1 112 The heterogeneity is introduced by sampling the model weights uy; for each client from a normal dis- tribution ((( R),, where It E [0,3] controls the statistical heterogeneity across clients' data.
influence of the personalization degree, practical guide- line emerges: when collaborative learning is beneficial (i.e., R2 < 1/Vr),, to achieve target magnitude of total error, we control the optimization errors at the same magnitude as the statistical error. Specifically, we increase À to reduce the statistical error to the same magnitude of the total error, and then gradually increase the communication rounds T until the optimization error reaches the same magnitude as well. Since the communication efficiency will decrease will an increasing X, the above strategy can achieve a given target total error at the highest possible communication efficiency. Later, we will also show that, with the optimal choice of personalization degree, FedCLUP improves communica- tion efficiency significantly compared with GlobalTrran and achieve total error smaller than LocalTrain in Section 6.
Comparison with Existing Literature. As reported in Table 1, our work is the first to quantitatively characterize how changing the personalization degree leads to the trade- off between communication cost and statistical accuracy. In contrast, most prior studies either do not explicitly analyze statistical convergence or fail to provide tight convergence guarantee for optimization and statistical error. For example, Chen et al. (2023c) attempted to establish both optimization and statistical rates simultancously; however, when À + 00, Problem (2) reduces to GlobalTrain, yet their results incorrectly imply that the communication and computation costs diverge to infinity.
Real Dataset. We use the MNIST, EMNIST, CIFAR1O. Sent140 an CelebA datasets for real data analysis. For MNIST, EMNIST and CIFAR1O, they aren't 't naturally par- titioned datasets. Therefore, following Li et al. (2020), to impose statistical heterogeneity, we distribute the data across clients in way that each client only has access to fixed number of classes. The fewer classes each client has access to, the higher the statistical heterogeneity. De- tails on data preprocessing and heterogeneity settings for each dataset are provided in Appendix D. For Sent140 and CelebA datasets, as they are naturally partitioned, we don't t need to create the data heterogeneity and directly apply our algorithm to these datasets with advanced models, like CNN and LSTM model (Sak al., 2014). We strictly follow the previous work (Li et al., 2021) and (Duan et al., 2021) to pre-process the Sent140 and CelebA dataset, respectively.
6. Empirical Study
In this section, we provide empirical validation for our the- oretical results, evaluating Problem (2) on both synthetic and real datasets with convex and non-convex loss func- tions. We first present the experimental setup, and then analyze the impact of personalization on statistical accuracy and communication efficiency, and conclude by analyzing the trade-off between the two. Details about the experi- mental setup are available in Section 6.1 and Appendix D. and the complete anonymized codebase is accessible at https///gihub.com//HHHHHooe
Implementation and Evaluation. For each setup, we eval- uate FedCLUP with three different degree of personaliza- tion: low, medium, and high, with specific personalization degree varying based on the dataset (details provided in Appendix D). For the synthetic dataset, in alignment with theorem 2, we implement FedCLUP using a global step size 7 = (A+ ()LL and a local step size 1) = (L + A)
7

---

Understanding the Statistical Aecuracy-Communintte Trade-off in Personalized Federated Learning with Minimax Guarantees
Dalaset
LocalTrain
FedCLUP
pFedMe
Global/Tran
High
Modium
Low
High
Mediom
Low
MNIST Logit
0.7828
0.8123
0,8213
0,8312
0,8001
0,8239
0,8291
0.8391
MNIST CNN2
0.8194
0.8753
0.8893
0,9032
0.8756
0.8771
0,8749
0.9098
MNIST CNNS
0.7633
0.9091
0,9102
0.9421
0.9340
0,9385
0,9440
0.9433
EMNIST CNNS
0.6111
0.6278
0.6415
0.6672
0.6345
0.6532
0.6717
0.6611
CIFARIO CNN3
0.6238
0.6102
0.6712
0.7302
0.6744
0.7443
0.7732
0.8041
Table Test accuracy of algorithms across datasets under varying personalization degrees. "Logit" refers to logistic regression, while "CNN-k" denotes convolutional neural network with k convolutional layers. "Low," "Medium," and "High" indicate low, moderate, and high personalization levels, respectively. As the personalization degree decreases, the statistical accuracy of FedCLUP and pf pleedMe transitions from resembling LocalTrain to ClobalTrain.
For the real dataset, since L is unknown, we implement the same algorithm with a global step size y set to 1//1, while the local step size is determined via grid search. In terms of evaluation, for the synthetic dataset, we evaluate by tracking the ground truth models and measuring error as the distance from these ground true models. For the real datasets, we report training loss and testing accuracy. Additional details, including hyperparameter settings and evaluation metric definition, can be found in Appendix D.
Symthetic-Logit
R-d35
R-2.
2.50
Totsl Troe
25
&Cmmmu
(6]
MNIST-Logit
MNIST-CNN
6.2. Results
2.30
Effect of Personalization on Statistical Accuracy. We compare FedCLUP, under different personalization degrees, with Global'Trann LocalTrain and pFedMe (T Dinh et al., 2020), an alternative algorithm for solving Problem (2). Implementation details are provided in Appendix D. All methods are run until stable convergence, and their test ac- curacy is reported in Table 2 in the low beterogeneity setting. Table 2 shows that as the personalization degree decreases and collaborative learning increases, the solution of Problem (2) becomes closer GlobalTrain, leading to improved sta- tistical accuracy due to increased information sharing across clients. A similar trend is observed for both FedCLUP and PF FM across different datasets and models, showing that under low heterogeneity, increased collaboration improves statistical accuracy.
Thaving Lees
Communicaiion Rourds OFARIO-ONN
#Communicat en Rounds EMNIST-CNN
Thareed Laun
Commun oction Sourds
CommLIROa2 Roursdy
FORLLPP Neverl
Figure 1. Total error and training loss of FedCLUP with varying personalization degrees. Total eтror (y-axis in (a)) quantifies the distance between the model at each communication round and the ground truth model, i.c. [|w - w ( 12. (a) compares total error under low (R = 0.5) and high (R- = 2.0) heterogeneity. (b) presents training loss across different datascts and models under low heterogeneity. Syathetic-Logit and MNIST-Logit represent logistic regression on synthetic and MNIST data, respectively, while MNIST-CNN, CIFAR 10-CNN, and EMNIST-CNN repre- sent CNN models trained on MNIST, CIFAR-10, 10, and EMNIST datasets. In how-heterogeneity setting, higher personalization (high per) accelerates convergence, while lower personalization (low per) improves final error. In high-heterogeneity setting, higher personalization achieves both smaller error and faster con- vergence.
Effect of Personalization on Communication Efficiency. Figure 2 investigates how personalization impacts commu- nication efficiency in F FedCLUP by analyzing the benefit of increasing local updates under different personalization lev- els. In the powppersonalization setting (left column), more local updates significantly accelerate convergence, reduc- ing the reliance on frequent communication. However, in the personaesoniiiioooonn setting (right column), increasing local updates has limited effect on convergence, indicat- ing that frequent communication is essential for effective learning. This demonstrates that higher personalization re- quires more communication rounds to achieve comparable performance, aligning with our theoretical findings, show-
8

---

Understanding the Statistical Cecuracy-Communcatie Trade-off in Personalized Federated Learning with Minimax Guarantees
Sprthulkooogi
PROCUU llon passonlliation)
PaccuU (ligh pesamahaaiien
hodCuI (ow pessmalattion)
PodCur lrig punpoduustio)
4.0
2.31
2.50
25
2.2
3.50
300
30-
1.0
275
2.50
0.75
.Commnu cit founds
Li Luctbe -20
Loca
Figure 2. Effect of personalization communication efficiency in FedCLUP for Synthetic-Logit (left) and MNIST-Logit (right). Each subfigure compares the impact of varying the number local updates per communication round under different personalization levels.
ing that increased personalization improves communication efficiency.
the expense of slightly higher communication costs. By progressively adjusting in this way, one can finally identify the optimal personalization degree that balances the trade- off and minimizes the total communication cost required to meet a desired performance threshold
The Trade-off under Personalization. The above two observations imply that there shall be a accuracy- communication trade-off in choosing the personalization degree to achieve the smallest total error under given com- munication budget (See Figure 1). To further demonstrate this point, in the left part of Figure 3, we compare the total error over iterations among LocalTrain, GlobalTrain, and FedCLUP under varying levels of personalization. Once the algorithms converge, for any given total error, there exists specific degree of personalization in FedCLUP that incurs the least communication cost among all considered meth- ods. This observation supports the conclusion in Corollary 3 that a unique personalization degree exists in FedCLUP to achieve communication efficiency for a fixed total error. Furthermore, we observe that no fixed personalization de- gree consistently outperforms others across all error levels. This implies that adaptively adjusting the personalization degree is essential for FedCLUP to maintain communication efficiency across different total error regimes. To further validate this finding, we conduct the same experiment on real-world datasets. Results on the CelebA and Sent140 datasets are presented in Figures 9 and 10, respectively. Ad- ditionally, we observe similar phenomenon in pFedMe, another method solving Problem 2, when we vary its per- sonalization degree. Witnessing the insightful results, it motivates to adaptively change the personalization de- gree in FedCLUP for achieving communication efficiency over different total errors.
20
30
Figure 3. Total error versus communication rounds. Left: Compar- ison among LocalTraann, GlobalTrrain, and FedCLUP with varying levels of personalization. For a given target total error, an optimal À exists that has the minimum communication rounds. Right: A dynamic À strategy: we begin with local training (highest personal- ization degree), and once the decrease of the validation error slows down, we gradually decrease the personalization degree. Com- paring the right figure with the left one shows that the dynamic strategy approximates the optimal personalization level needed to meet desired error threshold with minimal communication rounds, demonstrating the practical effectiveness of tuning person- alization dynamically according to the accuracy-ommmunicttio trade-off.
7. Conclusion
In this paper, we provide a precise theoretical characteri- zation of the statistical and optimization convergence of a widely used personalized federated learning problem. Our analysis reveals that when collaborative learning bene- ficial, increasing personalization reduces communication complexity but comes at the cost of statistical accuracy due to limited information sharing across clients. We then vali- date our theoretical findings across convex and non-convex settings, multiple datasets, and different model architectures.
Potential Solution in Practice. After understanding the trade-off under personalization, we propose a dynamic tun- ing strategy for the optimal À with communication effi- ciency(See Figure 3 Right) Beginning with small À for efficiency, as soon as the validation performance plateaus or the statistical error stops improving significantly, we grad- ually increase X. This allows the model to benefit from enhanced generalization through increased collaboration at
9

---

Understanding the Statistical
Trade-off in Personalized Federated Learning with Minimax Guarantees
Acknowledgment
Cheng, G., Chadha, K., and Duchi, J. Federated asymptoties: model to compare federated learning algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 10650-10689, PMLR, 2023.
This work was supported in part by the U.S. National Science Foundation (NSF) grant CCF-2007823 and Na- tional Institutes of Health (NIH) grants R01A1170249 and RO1GM152812.
Collins, L., Hassani, H., Mokhtari, A., and Shakkottai, Exploiting shared representations for personalized feder- ated learning. In International Conference Machine Learning, pp. 2089-2099 PMLR, 2021.
Impact Statement
This paper aims to contribute to the advancement of the field of Machine Learning. While our work has the potential for various societal implications, believe none require specific emphasis in this context.
Deng. Y., Kamani, M. M., and Mahdavi, M. Adap- tive personalized federated learning. arXiv preprint arXiv:2003. 134.610131.11,, 2020.
Duan, M., Liu, D., Ji, X., Liu, R., Liang, L.,, Chen, X., and Tan, Y. Fedgroup: Efficient federated learning via de- composed similarity-based clustering. In 2021 IEEE Inal Conf on parallel & distributed processing with applica- tions, big data & cloud computing, sustainable comput- ing & communications. social computing & networking SSSPA//DCCoad/SsciaCCC///Staii IEEE, 2021.
References
Arivazhagan, M. G., Aggarwal, V., Singh, A. K., and Choud- hary, S. Federated learning with personalization layers. arXiv preprint arXiv: 1912.90828 2019.
Bai, J., Chen, D., Qian, B., Yao, L., and Li, Y. Federated fine-tuning of large language models under heterogeneous tasks and client resources. In The eighth Annual Conference on Neural Information Processing Systems, 2024.
pp. 228-237.
Duan, Y. and Wang, K. Adaptive and robust multi-task learn- ing. The Annals of Statistics, 51(5):2015-2039) 2023.
Fallah, A., Mokhtari, A., and Ozdaglar, A. Personalized federated learning with theoretical guarantees: model- agnostic meta-learning approach. In Proceedings of the 34th International Conference Neural Information Processing Systems, pp. 3557-3568, 2020.
Beltrán, E. M., Pérez, M. Q., Sánchez, P. M. S., Bernal, S. L.., Bovet, G., Pérez, M. G., Pérez, G. M., and Celdrán, A. H. Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges. IEEE Communications Surveys & Tutorials, 2023.
Garrigos, G. and Gower, R. M. Handbook of conver- gence theorems for (stochastic) gradient methods. arXiv preprint 23X1:22311.11335 2023.
Bietti, A., Wei, C.-Y., Dudik, M., Langford, J., and Wu, S. Personalization improves privacy-accuracy tradeoffs in federated learning. In International Conference on Machine Learning, pp. 1945-1962. PMLR, 2022.
Hanzely, F. and Richtárik, P. Federated learning of a mixture of global and local models. arXiv preprint arXi::200..05516 2020.
Chen, D., Gao, D., Xie, Y., Pan, X., Li, Z., Li, Y., Ding, B., and Zhou, J. Fs-real: Towards real-world cross-device federated learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3829-3841, 2023a.
Hanzely, F. Hanzely, S., Horváth, S., and Richtárik, P Lower bounds and optimal algorithms for personalized federated learning. Advances Neural Information Pro- cessing Systems, 33:2304-223 23154, 2020.
Chen, D., Yao, L., Gao. D., Ding, B., and Li, Y. Efficient per- sonalized federated learning via sparse model-adaptaatin. In International Conference Machine Learning, pp. 5234-5256 PMLR, 2023b.
He, Z., Sun, Y., and Li, R. Transfusion: Covariate- robust transfer learning for high high-dimensional regression. In International Conference on Artificial Intelligence and Statistics, pp. 703-711. PMLR, 2024a.
Chen, F. Luo, M., Dong, Z., Li, Z., and He, X. Feder- ated meta- weta-leernnng with fast convergence and efficient communication. arXiv preprint arXiv: 1eXiv=1802.070 1802.07876 2018.
He, Z., Sun, Y., Liu, J., and Li, R. Adatrans: Feature- wise and sample- wise adaptive transfer learning for high- dimensional regression. arXiv preprint arXiv:2403.133 13565, 2024b.
Chen, S., Zheng, Q. Long, Q., and Su, W. J. Minimax estimation for personalized federated learning: An alter- native between fedavg and local training? Journal of Machine Learning Research, 24(262): 2023c.
Ji, K., Liu, M., Liang, Y., and Ying, L. Will bilevel optimiz- ers benefit from loops. Advances in Neural Information Processing Systems, 35:3011-3023, 2022.
10

---

Understanding the Statistical Accuracy-Communicati Trade-off in Personalized Federated Learning with Minimax Guarantees
Jiang, Y., Konečný, J., Rush, K., and Kannan, S. Improving federated learning personalization via model agnostic meta learning. arXiv preprint arXiv: 12488, 2019.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficie learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Khodak, M., Balcan, M.-F. F., and Talwalkar, A. S. Adap- tive muudient-basedd meta-learning methods. Advances in Neural Information Processing Systems, 32, 2019.
Mishchenko, K., Hanzely, S., and Richtárik, P. Conver- gence of first-order algorithms for meta-learning with moreau envelopes. In Federated Learning and Analyt- ics in Practice: Algorithms, Systems, Applications, and Opportunities, 2023.
Lemaréchal, C. and Sagastizábal, C. Practical aspects of the moreau-yosida regularization: Theoretical preliminaries. SIAM Journal on Optimization, 7(2):367-388 1997.
Li, D., Xie, W., Wang, Z.,, Lu, Y., Li, Y., and Fang, L. Feddiff: Diffusson model driven federated learning for modal and multi-clients. IEEE Transactions on Circuits and Systems for Video Technology, 2024a.
Moreau, J.-J. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273- 299, 1965.
Paragliola, G. Evaluation of the trade-off between perfor- mance and communication costs in federated learning scenario. Future Generation Computer Systems, 136: 282-293, 2022.
Li, H. and Richtárik, P. On the convergence of fedprox with extrapolation and inexact prox. arXiv preprint arXiv:2410.01410, 2024.
Li, H., Acharya, K., and Richtarik, P. The power of extrapolation in federated learning. arXiv preprint arXiv:2405. 13766, 2024b.
Sak, H., Senior, A., and Beaufays, F. Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition. arXiv preprint arXiv:142..1 1402.1228 1128, 2014.
Li, S., Cai, T. T., and Li, H. Transfer learning for high- dimensional linear regression: Prediction, estimation and minimax optimality. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):149-173, 2022.
Singhal, K., Sidahmed, H., Garrett, Z., Wu, S., Rush, J., and Prakash, S. Federated reconstruction: Partially lo- cal federated learning. Advances in Neural Information Processing Systems,
2021.
Li, S., Cai, T., and Duan, R. Targeting underrepresented populations in precision medicine: A federated transfer learning approach. The Annals of Applied Statistics, 17 (4):2970-299)) 2023.
Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, A. S. Federated multi-task learning. Advances in Neural Infor- mation Processing Systems, 30, 2017.
Li, Sahu, A. K., Zaheer, M.. Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
T Dinh, C., Tran, N., and Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems,
2020.
Wang, R., Zhao, D., Suh, D., Yuan, Z., Chen, G., and Min, B.-C. Personalization in human-robot interaction through preference preference-based action representation learning. arXiv preprint arXtv:2409.13822 2024a.
Li T., Hu, S., Beirami, A., and Smith, V. Ditto: Fair and robust federated learning through personalization. In International Conference Machine Learning, pp. 6357-6368. PMLR, 2021.
Wang, Y., Lin, L.,, and Chen, J. Communication-efficiee adaptive federated learning. In International conference machine learning, pp. 22802-22838. PMLR, 2022.
Liang, P. P., Liu, T., Ziyin, L., Allen, N. B., Auerbach, R. P., Brent, D., Salakhutdinov, R., and Morency, L.-P. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.0/ 2020.
Wang. Y., Wang, S., Lu. S., and Chen, J. Fadas: Towards federated adaptive asynchronous optimization. In Inter- national Conference on Machine Learning, pp. 51701- 51733. PMLR, 2024b.
Lin, S., Han, Y., Li, X., and Zhang, Z. Personalized fed- erated learning towards communication efficiency, ro- bustness and fairness. Advances in Neural Information Processing Systems, 35:30471-3044 2022.
Wen, J., Zhang, Z., Lan, Y., Cui, Z., Cai, J., and Zhang, W. A survey on federated learning: challenges and applica- tions. International Journal of Machine Learning and Cybernetics, 14(2):513-535 2023.
Mammen, P. M. Federated learning: Opportunities and challenges. arXiv preprint arXiv:2101.05428, 2021.

---

Understanding the Statistical Accurac-Commmuication Trade-off in Personalized Federated Learning with Minimax Guarantees
Wu, F., Li, Z.,, Li, Y., Ding, B., and Gao, J. Fedbiot: Llm local fine-tuning in federated learning without full model. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 3345-3355, 2024.
Ye, M., Fang, X., Du, B., Yuen, P. C., and Tao, D. Hetero- geneous federated learning: State-of-the-art and research challenges. ACM Computing Surveys, 56(3):1 44, 2023,
Yosida, K. Functional Analysis. Springer, 1964.
Yuan, L., Su, L., and Wang. Z. Federated transfer-ordered-
personalized learning for driver monitoring application. IEEE Internet of Things Journal, 10(20):1829)) 6292-18301, 2023.
Zhang, H., Zheng. Z., and Xue, L. Gap-dependent bounds for federated q-learning. arXiv preprint (XXi:25502.0289,, 2025.
Zhang, Y., Wang, X., Wang. P., Wang, B., Zhou, Z., and Wang, Y. Modeling spatio-temporal mobility across data silos via personalized federated learning. IEEE Transac- tions on Mobile Computing. 2024.
Zhao, H., Du, W., Li, F., Li, P., and Liu, G. Fedprompt: coammuiicationneffciie and privacy-preserving prompt tuning in federated learning. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Sig- nal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Zheng, Z., Gao, F,, Xue, L., and Yang, J. Federated q- learning: Linear regret speedup with low communication cost. In The Twelfth International Conference on Learn- ing Representations, 2024.
Zheng, Z., Zhang, H., and Xue, L. Federated q-learning with referencceadvvatagge decomposition: Almost opti- mal regret and logarithmic communication cost. In The Thirteenth International Conference on Learning Repre- sentations, 2025.
Zhou, Y., Dou, Z., and Wen, J.-R. Encoding history with context-aware representation learning for personalized search. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in In- formation Retrieval, pp. 1111-1120, 2020.
12

---

Understanding the Statistical Accuray--oommuicatton Trade-off in Personalized Federated Learning with Minimax Guarantees
A. Proof of statistical converngence
To facilitate our analysis, we denote
À (g)
w. (9)
(16)
stat
w
2 E [m].
(17)
where wx = Eie(m Pra
(9) Á stat is the difference between the true global model and the optimal solution of the global (1) model in Problem (2) and stat is the difference between the true local model and the optimal solution of the local model in (2) for any i [m]. The statistical error bound is established as EE| ( I| and E| A I? where the expectation taken
over all the data. Notably, we should stress that the definition of w (9) is just to serve as a bridge to establish the convergence rate local models, and it is not our focus in the theoretical analysis.
We also denote
= w
Wt
8 == (0) (1)
(18)
where 5 measures the difference between the true global model un!)) and the true local model ! and 5(0 is the estimator of such a difference.
A.1. Discussion on the Parameter Space
When assuming the statistical heterogeneity of each client different (R is related to the client index i), it would provide a more delicate description of statistical heterogeneity, and also requires different personalization degree per client. Therefore, let's consider the following problem with different heterogeneity in personalized federated learning
A 11 1 - w() + (Li(w
min w (
Σ Pi
(19)
FEET 1=1
2
where the i-th client will be shrunk to the global with strength A₁ Therefore, solving (19) will consider different personal- ization degree for different clients. Establish the minimax statistical error bound for Problem (19) would be open for future work.
Under Assumptions 1 and 2 assume, statistical heterogeneity in parameter space (5) would be equivalent to many other similar assumptions for statistical heterogeneity, like B-dissimilarity (Li et al., 2020), parameter difference (Chen et al., 2023c) and gradient diversity (T Dinh et al., 2020; Deng et al., 2020).
A.2. Useful Lemmas
To facilitate our analysis, we first present two important lemmas and provide their proof.
Lemma 3. Under Assumption 2, for the optimal solution (o and ai()) 's in Problem (2), have
V. S.)ll
(
1/
/ + X
Proof. By the p-strongly convexity of Vi,, we have that for any w E Rd
Tu(w, + 2 flw--aid - 10 (o) S.) + (V S:), w m
/
1/0 20)
2
2 (() (1) St) + w - x
( x
2 w 2 || - I ت (0) (1,)s,)1)) (20)
where in the last step, we used the Cauchy inequality.
13

---

Understanding the Statistical
Trade-off in Personalized Federated Learning with Minimax Guarantees
In addition, notice that ( is the optimal solution for the local model ( in Problem (2), thus we have
argmin Li(w,, S.) + 2 ||0 w
This result together with (20) implies that
X
A
L,(w()), = (,( ..)
2 21120000 122 (,(1(()))) ,..)
-/2 |20( -
2
2 ( S.) || - |لاا
[ x
1 x |VVi(( ,.,))
Therefore, since μ + X >> 0 and |0 ااااهه 2 0, rearranging the terms leads to
2 L. S.)ll
[ 6
(21)
+
as claimed.
Lemma 3 is crucial to bridge the solution of the global model with the local model in Problem 2. Note that the difference bounded by the gradient norm of local loss functions evaluated at the optimal solution of the global model, which would be decomposed further and controlled by the global model's statistical accuracy, as we will show later.
Remark:
Lemma 4, Under Assumption 1, 2, 3, for wGn. the solution of the GlobalTrain problem (4), we have
PV Die(m) [m]
1
LR
E ü
w
Be
11/
Proof. By the optimality condition of the GlobalTrain problem in (4) and the strong convexity of Lj 's we have
0 M
P:
(WGG, S.) L.((
iE mm)
Σ Pi
(V St), संदा wl + p
Wer mo(0) 1/2
EE m)
2 Σ
ps (. (9) S.) 00||||000T- ( w0:o + joo 20
1E|m]
Therefore, we have
E Ps (L (g) .S:)
(0)
1/2
Eie(m) Ps (L (1) S.))
+ Eie(m) ps
VIo(no S.) V.. (0) S:)
(22)
1/2
By the L-smoothness property of L 's in Assumption and the bounded gradient property listed in Assumption 3, we have
Σ {m(m)
( (9) S.) - VL.( sall
Σ
- S LR,
iE [m]
E
p.V (w, ( SD) = Σ
v (0)
ا3حي Sp. Σ
m2
vE[m]
sE[m]
JEin.]
#E|m=
14

---

Understanding the Statistical Cecurac--Cmmmuication Trade-off in Personalized Federated Learning with Minimax Guarantees
These results together with (22) implies
PVV
PV Σ
ic
[m]
P LR
+
E PCT
11/2
as claimed.
Remark: Lemma 4 implies that if we solve the GlobalTrain problem exactly, the solution will be close to the ground truth of the global model with a certain error, which is independent of X. After presenting the two useful lemmas in Appendix A.2, we will start prove the theoretical results in Section 4.1. Section A.3, we will prove Theorem first, then we will prove the statistical error bound in Problem 2 as demonstrated in Corollary 1.
A.3. Proof of Statistical Convergence in Theorem
In the discuss below, we always assume w discussed below comes from the parameter space (5). As the local model is shrunk towards the global model under the influence of personalization degree, how fast the global model wils) convergence wo!") can also influence the convergence rate of the local model. In Appendix 1.3.1, will establish the statistical error bound of the global model first. Then in Appendix A.3.2, will provide the local model error bound, where we explicitly show that the statistical accuracy of the local model depends on the statistical accuracy of the global model. Finally, in Appendix A.3.3, we combine the results of local models and the global model to establish the one-line rate for the local model explicitly stated in Theeorm
A.3.1. GLOBAL STATISTICAL ERROR BOUND
To analyze the statistical error bound, we consider two separate cases: R for this distinction lies in whether collaboration among different clients is beneficial.
V
E
Ri and R S V Rs The motivation
Case 1: We first consider the case when R
Ps
Recall that ( and {w hemmm (ie are the minimizers of Problem (2). According to the first-order condition, have
wish Li (1) (n( > (20000) =6(()
(23)
(0) = Σ (1)
(24)
We start with the optimality condition of (() and (0)) which yields
0 P Σ Ps L(,00, S.) + ( 10
Σ pi _i(w"".s .S) + 2 11u
w 10
(25)
iE[m]
iE[m]
Reorganizing the terms, we obtain
0
Σ Pi (((x((), ,21) ((w()22))))
2(5)) +
Σ
Pt A
- -000
Σ
Ps 11 [m]
> 112
(26)
n4
(m(m] JE(n::]
XE
[m]
For the first term on the R.H.S. in (26), apply the justtrogly convexity of the loss function (cf. Assumption 2), we then have
ΣΣ
(1(1b())))) 2.g) - E(uo! , 2
Ps
Ve(w!
(0) =1)),
(1) Am
(E[m) sE(m)
(m(m) se(n:]
(27)
#
Σ
Σ
(
2
74
ie mm
jE(n.]
15

---

Understanding the Statistical Accuracy-Communcatton Trade-off in Personalized Federated Learning with Minimax Guarantees
where we use the definition of A in (17).
Plugging (27) back into (26), it yields
02 ΣΣ Pi
VVllw! (
24)),
A
stat
(8)
ΣΣ
Σ
Pi
ni
2
(28)
+
Σ
P:
(0)
w
Σ
2
P
(0)
- w
112
iE|m]
kE(m
Recall the definition (18) and the assumption about statistical heterogeneity in (5)
02 ΣΣ Pi n
Vi(w
A (9) 25)), 25y,, siul
(0
+ Σ
Ps
A sta
+
Σ
Ps
860
A
R²
(29)
2
2
2
5
Applying Cauchy inequality on the first term of (29), it yields
ΣΣ 3
Pi ([(ww.
(2) 21)),
Σn. Pi
Vl(wo (.) , =ii)); A
(30)
Σ Ths
Vi(w! (1) =iz)
Pi
Consider the Assumption 3 and Biy are i.dd data
2
0²
Σ
u
2is)
S E
Σ
Vllw
(8)
- =25s)
(31)
T2
T2
2
Combining (30) and (31), it yields
ΣΣ
Pi Vl(w!) (
,zy),
10
Ps /n;
EE
{ 2-
(32)
n
Plugging (32) back to (29) yields
0 - Σ Pi
P
( stal
+ 2
Σ E
(1) stat
+
A Σ
P.E
5001
R².
(33)
2
2
After dropping the third term and applying Cauchy inequality, we obtain
0 02 -p (I
Pt nz
P.E.
A ))
P 2
P.E.E
A
2
X
R².
(34)
2
(mmm
If we assume p; 1 and n4 nyyi Vi + j (assumptions used in Theorem 1), we have
E
Ä
(g) stal
<
1
4p²
+ 24XR2)
(35)
u
16

---

Understanding the Statistical Accurac-Coommuication Trade-off in Personalized Federated Learning with Minimax Guarantees
Case 2: Then we consider v Σ; P.. Recall the definition of the global minimizer of GlobalTraining üGr
arg min E, Ps (w; Si), based on the optimality condition of w;; Wgg E [m]] we obtain
Eds pi (i((0())))) (10 1 $ Σ Pi (.(ZGGT, Si) + 211 üGr uoTl?
(36)
Σ PeLe((vor:
Therefore, we obtain
EpLLi(WGT. St) Σ E S.).
(37)
In addition, applying the smoothness assumption in Assumption yields
L (1 S.) (,(ti)), S.) - (L,(1)())))) - - |10 13
(38)
Combining (37) and (38), we have
EptIa(Wer. S:)
Σ 1
(39)
2 EuL((o Si) + Σ (. St) T (1o(1)
x((0)) Σ
ps 2
(40)
Using Cauchy inequality the second term of the R.H.S.,
DiLL S.) 2 Σ (.Li( - pbll ( ( (S)1lel 2
Σ
Σ P (000) 11
L
(41)
On the other hand, note that the optimality condition of üGT is
Σ L S:) 0.
(42)
Using the strong-convexity assumption in Assumption 2, we can show that
Σ Pi Lil (0) - L.(wor, St) VL, L.Lowrr (zb(() warr)
Σ pi (i(200)), ..) L. S1)
Σ Pi 11 [(اs) werl
" ( म.ा!! ?
(43)
17

---

Understanding the Statistical Combining the results (41) and (43), it yields
Trade-off in Personalized Federated Learning with Minimax Guarantees
E Dili((WGT 2i)
Σ PULI Si) + - ( -GGl!
Σ pill (L , 20(0)122 Σ
pt 2 1 - =660)p2
(44)
Reorganizing these terms yields
M
worll 12 s Σ [
1|2
L
(45)
2
2
Using Lemma to bound the term
|| x
we have
| worl?
-
2
Σ
Pi
u++ X
2
+
(a+ X)2
2L
( S.)I?
Σ Pil ( (5) (x+
T.
(46)
Note that by the smoothness Assumption and triangle inequality,
(V SS)11 < ( .S:) - V.( ( S2Ill + 2 (w, (0) Stll?
S 21 2 w2 ( S.)11
(47)
Take expectation w.r.t all data and use Assumption 3 in the parameter space (5), then we have
1
E (160)
< 21"E|| w 12 + 2E
V L( w 2ij)
n4
41 -wo. 10! R2 + 2
(48)
n
where the last term comes from (31).
Plugging (48) back into (46), it yields
1 {11 x+
{ (ALIETIOO 11 + 2
ا 2
<
+ (++ x\K
2
(49)
Next, we are ready to establish the global error bound. Using the result (49) and Lemma 4, we obtain
El(l (9)
10(
(n + x)2 )
4T. - 41.2 R² 2
+
11 + X
n
+ 8 8p2
81,2
+
Ria
(50)
122
N
112
18

---

Understanding the Statistical Cecuracy-Communicti Trade-off in Personalized Federated Learning with Minimax Guarantees
Let's define g( = 1 x
I + (uFA)²) and reorganize (50), which yields
E Bl|l 13 g(A) 12 + +2
+ So² A= N
+ 812
u Rt2
(51)
4L2g((A)
If assume p;
-, m n4 f2 Vi j (assumptions used in Theorem and g(A) S 1/(2) we have
(
9(A)
AL + + +
16p²
16L2
R².
(52)
stat
(A)
1 N
μ²
A.3.2. LOCAL STATISTICAL. ERROR BOUND
Analogous to the analysis of the global model, we examine the statistical accuracy of the local model similar manner. For simplicity, in the following arguments, we denote the upper bound of EE] [ ll as Uo. The expliciate expression would be found in results (35) for R EE Es and (52) for S
(9)
Σ
PL
Case 1: first we consider the case when R
P
To prove the local statistical error bound, start with the optimality condition of w(() and w(()) for single client, which yields that for i E [m).
02 Li (8) S:) + 2
(wls)) 10 Li (w.)) S:)
(6(9) w. (
(53)
Reorganized the terms, we obtain
02 Σ Th:
e ((()))))))) 2is) (10 2is)
)) + A
( -000
A 1²
-
20(000 wo!") 10.0
(54)
jE(n.)
For the first term on the R.H.S., applying the y-strongly convex of the loss function E (cf. Assumption 2) yields
Σ -
(((x)()) - E(wob") z1)) 2 Σ
(Vl(uo)))
A
+ P
Σ
(55)
ns
ns
72
JEImd
JE(N)]
where the definition of ata in (17).
(
Plugging (55) back into (54), it yields
02 - Σ 1 Ve(wo! 2g))
2g)),
A00 stat
+
1
2
(4) stn
2
+
2
12
2
[100(0)
-w. -0
(56)
Apply Cauchy inequality on the first term of (56)
Σ (ve(uol".aa 2.)))
22))) A10)
V((w ..z)) 2.y)) (1)
=
(57)
1 ve(wet (t)
A (
243)
n
19

---

Understanding the Statistical
Trade-off in Personalized Federated Learning with Minimax Guarantees
Consider the Assumption 3 and Fij i.i.d data
1))
2
ve(ww)
215))
S E
Σ
Vi(w.
(") [xs) ,
-
P
(58)
T2
n2b
11
2
Combining (57) and (58), it yields
Σ
- E
A
1
E E
P
(59)
n
vns,
Plugging (59) back to (56) yields
2
p
1
E
A
(6)
+
A
2
+ 2
Bl
11
-wo ,
(60)
n2
2
2
Note that
-1106(0)
W
(9)
w.
(g)
w.
(1)
(g) stat
1|2
||2. (g)
w.
(g)
w.:²
112
(61)
2
(9) stat
R²2 2R
(g)
2
Plug (61) into (60)
E
A
(4)
11 E
A
2
X
((6)
2
X
w!!)
wo!")
w
(3)
74
2
2
(62)
E
(K)
E
>
g(()
2
X
star
(g)
X R²
ARE
A (0)
n4
2
Once we denote the upper bound of E
(g)
as Un. it yields
stal
02
VT4
P
stat
(i)
2
2
B
stat
+
8(0)
2
2
R2
AR Uo
(63)
P1
(
p
A
9
(U + R)²
2
n
If we assume p: m n; = n Vi + j (assumptions used in Theorem 1), we can obtain
4p2 + 4nd (Ug + R²)
(64)
u?
n
Case 2: then consider the when R
Σx
If we assume p: m n, = ny Vi a
(assumptions used Theorem 1), we can obtain
20

---

Understanding the Statistical Cocuuicy-Cmmmuicattio Trade-off in Personalized Federated Learning with Minimax Guarantees
Blll w.a
(4) [|-]
- 3E (1()) i ||
3E (())) ! ||3 + 3E 11 (0)
w (3)
(0)
12
E VL || 3E (600 +
(μ + X)2
12
(T - (2) [2] 4L2 + 2 0²)
+ + (
w. 1 3R²
(65)
(p + 2)?
where step (a) comes from the assumption of parameter space in (5) and Lemma and step (b) comes from result (48).
A.3.3. PROOF THE STATISTICAL ERROR BOUND IN THEOREM
For R
E Pi putting the statistical error of global model (35) into the statistical error of local models (64), we have
E
4p
4p² 2
1
+
8 u
R2
4
AR
(66)
2
therefore the second part (8) in Theorem established. For clarity, we can define
(2)
X² +
4 =AR2
(67)
For R
Σi Pr. plugging the result (52) of the global model into the local model's error bound (65) and reorganizing the
terms yields
E
stal
(4)
[2]
12
4L R2
2-"
+
48L2
+3
U 3n²
(68)
(1 + X)2
11
(1+
X)2
48p²
[482
Rº
(69)
112 N
112
Q1
(A)
where
12
4T. R2 + -
4812
9(2)
RT. +2 202 4I2g(A)
(a)
(μ
2)2
(n ))2
n
(70)
8p²
8I2
(2
+ +2
+2
+
R²
+
[AL'R2
122
42
AL'g(A)
n²
This combining with the definition of 9(A) implies that (A) is monotonically increasing function of À and limx-+ (A) co, as claimed.
A.4. The Proof of Corollary 1
Analogous to the proof of Theorem 1, we will discuss the cases of R² separately as well. For clarity of our analysis, will assume
and n, ny Vi +
1.4.1. THE STATISTICAL CONVERGENCE OF THE GLOBAL MODEL WITH A CHOICE OF
Case 1: For R > Va we have derived the global model error bound in (34) as
02 -p
(< Pc nz
P.E.
(3)
1
Σ
P.
(0)
2
R².
(71)
2
2
1c/m]
21

---

Understanding the Statistical Accuracy-Communicati Trade-off in Personalized Federated Learning with Minimax Guarantees
If we set the λ as
p
(72)
then solving the inequality in (35) w.n.t E, p:lE
cound yield
E
A
Lg]
Σ
|
p.B
5
(1 + v3)p
(73)
PVn
Case 2: For S - we have obtain the results in (52)
9(2)
+
16p²
16T.
(g) stat
S
AL +
112 R?.
(74)
(L2
12
112
If we assume
((
[422
AL
2 + 2 )
g(A) - 8L2
^
WPN
+
(75)
n²
we have
i (g) w. 11 32
0²
+ L2
R2
(76)
122
112
Furthermore, we can get simplified condition for A as
8K
88L v ((21217
/
40² P2N
RI
4L2 R²
(1
44
(77)
12
where k 2 1 and the condition that À is non-negative holds trivially
EL? #
k2 2 p.
Combine two-case arguments, we have
(1+v3)p 2
R t
E Bl(w(() (g) - 1
R//n
(78)
32
p²
N
+
#
12
R2)
3
Thus it yields one-line rate
El w0 12 s Ci
1
+C2l ~ R²),
+
(79)
N
n
where
C = 32 R
122
(80)
(1 (1+v3)) v3)p
32L2
C2
11
n12
22

---

Understanding the Statistical Accurac-CCommunictton Trade-off in Personalized Federated Learning with Minimax Guarantees
A.4.2. THE STATISTICAL CONVERGENCE THE LOCAL MODEL WITH CHOICE OF
Case 1: For R L. Vn"
have derived the result in (64)
4p" + 4ud (Vg + n2))
E
( stat
(81)
2
In addition, recall that, when R Therefore, putting the global model's error bound (See result in (78)) into (64), which yields
we set X
Σ
jn in the statistical convergence analysis of the global model.
v
1
B
stat
ll2
I
P
p
2p
(U + R)))
V
nR
2p
p+
p +
(U + R)²
VnH μ
R2
(82)
p+ (n² 4p² (C2 + 1))
Vn
1
p( + (1 + 4(2 + 1))²)
n
where C2 has been defined in (80).
Case 2: For R < V
from the result (65), we know
12
12 (μ
4L' + R2 + 12
+ 300 + 3R.
(83)
X)2
Then putting the global model's results (78) into (65), it yields
E ((ll
117
(84)
12
p2
L2
0²
p²
L
(1r 2)2
128
112
N
ne
RL.
n.
+ 96
112
+
112
R22
+ 3
12
1281.2
p
+
(128L*/H + A +
0²
+
96p
+ (96 I,2
+ R?
(85)
(p + X)2
n²
N
71
N
412
If we assume À satisfies the following condition
12
96p2/(u² + 99
(86)
(μ + X)2 128p² /N + 132L2 R2 2 /
then we will have
E w0! 10
192p2
+ 198k R².
(87)
212 N
Furthermore, we can get simplified condition for À as
8(64p2/N + 66 + p2/n)
A 2 1
32p² 10p2/111 (1² 33x² R2
11.
(88)
23

---

Understanding the Statistical Accuray-Commmuicatinn Trade-off in Personalized Federated Learning with Minimax Guarantees
Combining two-case arguments, we have
( 1
E
(2)
1
TR N R
(89)
stat
1920 p
+ 192
R R
And yields one-line rate
E
A
( stat
S
SCs N
1
- Cg(RR A -
(90)
where
192p²
C2
x2
p(1++ (4C2 5)
2
(91)
C₁
198k2
1
and C2 specified in (80).
Therefore, combining results from Section A.3.1 and A.3.2 we can obtain the upper bound in (9).
To make the global statistical error bound and local statistical error bound hold simultaneously, we should be aware about the condition the adaptive strategy of specified our proof. could be summarized as
A max(a1, a2)
R <
(92)
X S
p²
RZ
TF
npRa
where
8K
R1 + 1² /n
} 14,
8T.²
a1
4p (x²2 4x R2
and
8(64p² /N +
02
32p² N
We can induce a sufficient condition of for R <
as
v
212R² + 12/n A 2 max 6, V 5)
L + + //N
μ.
(93)
To sum up, we give the one-line rate in (90) for Corollary and provide the potential solution of with a closed-form solution in (92).
A.5. Discussion on the Statistical Convergence Rate and Comparison with Existing Results
Combining the results in A.3.1 and A.3.2, we leave remark below further interpret the effect of personalization in Problem (2) and discuss how to incorporate the conditions of À when establishing the global and local statistical accuracy.
To better understand how such interpolation is achieved through an adaptive personalization degree, we examine the role of À in navigating between the two extreme cases: GlobalTrain and LocalTrain. As the statistical heterogeneity R + oo, we have A + 0, leading to a high degree of personalization. The statistical error bound becomes O(n matching the rate of LocalTrain; as the statistical heterogeneity R - 0, À increases, leading to low degree of personalization. The statistical error bound eventually converges O(N -1),,, matching the rate of GlobalTrain under a homogeneous setting.
24

---

bridge and proved the Understanding the Statistical Aecuray-CCommuniction Trade-off in Personalized Federated Learning with Minimax Guarantees
As R (0)) À transits between the two extremes, making PFL Problem (2) perform worse than LocalTrain while benefiting from global training when clients share similarities.
Our contribution can be summarized into three aspects:
Our results are derived under more realistic assumptions. Chen et al. (2023c) imposes additional stringent conditions including a bounded parameter space D and a uniform bound on the loss function ((,,z). Such conditions are difficult to satisfy in practice. For example, even a simple linear regression model with sub-Gaussian covariates would violate these assumptions.
Our result is established for both global and local models with the same choice of A. In contrast, Chen et al. (2023c) proposes two-stage process where the global model is first estimated, followed by an additional local training phase with a different choice of A. This two-step approach is likely the artifact of their analysis, as existing work on Problem (2) also shows that a single-stage optimization with a chosen À suffices to achieve the desired performance (T Dinh et al., 2020).
We establish a state-of-the-art minimax statistical rate. As shown in Table 3, the established upper bound matches the lower bound established in (Chen et al., 2023c). In a heterogeneous case when R 2 n 1/2, Chen et al. (2023c) establishes a rate that is at least of the order O (n==)t²) as D 2 R. This bound becomes increasingly loose with larger R. In contrast, our bound O (n "t). which shows that properly-tuned Problem 2 always no worse than LocalTrain, independent of In a homogeneous case when Rt S m n -1/2, they can only establish rate slower than O (1/(Vmm)) while our result achieves a rate of O (1/(mn)), leveraging all mn samples and matching the rate of GlobalTrain on the IID data. As the client number could be extremely large (10" devices in (Chen al., 2023a)), order of m is non-trivial. During the transition period when -2 -1/2 than the rate On /2 R)
1/2 < R 1/2, we achieve a rate of O again matching the lower bound, and is strictly faster
/2) established in Chen et al. (2023c).
Table Results Comparison, == sup w || w'll is diameter the parameter space (D 2 R) and ||e|| = inf R: : (() S M, for any =} is a uniform upper bound on the loss function. Statistical rate refers to E| [l(ww w 1?, with constants neglected.
Source
Assumption
Paradigm
Statistical Rate
R V
myR
R
S
VR
R
myn
(Chen et al., 2023c)
A1,2,3, DVV ||0||oo SC
Two-stage
D2 [|]]
[1 Vm
R
[| v/iii
n
Ours
A1,2,3
One-stage n
R2
mn
mn
Lower Bound
R²
Next, we discuss our theoretical contributions. Prior work (Chen et al., 2023c) established the rate through algorithmic stability, and obtain bounded stability, the boundedness of the loss function is needed. This assumption (or bounded gradients) is, in fact, commonly imposed for analysis based on the tool of algorithmic stability. To relax this assumption and obtain a bound independent of the diameter of the domain/gradient norm/loss function norm, we need to jump out of the stability analysis framework and develop new techniques.
Our analysis does not rely on any algorithm but directly tackles the objective function, establishing rates using purely the properties of the loss. Specifically, using the strong convexity of the loss function, we first proved the estimation error is bounded by the gradient variance and an extra statistical heterogeneity term controlled by X, as detailed in Lemma 1. This allows us show for large R, small X can be chosen to yield rate ((1/n) and match one of the worst cases in the lower bound. For the complementary case R < I/, we leveraged the GlobalTrain solution ÜhT solutions of Problem (2) to wer are bounded by a term inversely proportional to À (cf. Lemma 4). implying that they can be made arbitrarily close to Wer by setting À small. This, together with the rate of öer as proved in Lemma 5, yields a rate of O1/N + R²). Combining the two cases, we proved minimax optimality.
25

---

Understanding the Statistical
Trade-off in Personalized Federated Learning with Minimax Guarantees
B. Algorithmic Convergence Rate
In this section, we will start to prove the algorithmic convergence rate rigorously. First, we present our Algorithm I in Appendix 1. In Appendix B.2, we provide some useful lemmas facilitate our analysis, including the proof of Lemma I presented in the main paper and the inner loop and outer loop error contractions in Algorithm 1. Next, in Appendix B.3, we ready prove Theorem 2 with the local and global model convergence. In Appendix B.4, to show the communication cost and computation cost of our method, the proof of Corollary 2 is established. Finally, in Appendix B.5, as stochastic gradient descent would reduce the computation cost over the full sample, we present Algorithm 2 for the noise setting and provably show the benefit of collaboration to reduce the noise.
B.1. Algorithm
Algorithm 1 Federated Gradient Descent with K-Step Local Optimization
Input: Initial global model w("), initial local models ( heem)) global rounds T, global step sizes 7, local rounds K, local step sizes 1) Local models {wT,K Jeeml and global model w
Output:
for f = le..= do
The server sends w (9)
to client i, Vi E [m]]
Set 2000 = u. 1-1KK for k = O,.... ...,. K- do
(5)
w (1)
w with
(1) n Eje(n.) Ve(wu (,0 mn5)
m0! }
Push (F)( (0))
(1) \(w! w to the server
(0) (g)
m Eia(m) (
u 2+1 w
B.2. Proof of lemmas
B.2.1. PROOF OF LEMMA 1
To facilitate our analysis, we state claim first.
Claim: If f is p-ssronngly-oonve,, then the proximal operator
A aigmin min ((v) + = 2010-011 0112)
/rox = arg
(94)
L Lipschitz continuous with L X+
Proof. Based on the definition of prox f/a (x)), it will satisfy the first order condition
V f(pprox - A(x - prox / (z)) = 0.
(95)
Then we have
vf(x1) - -((1 - -11)= =
where x1 = prox & (v),
(96)
fz(2)) - A(e2 x2) = 0 where x2 = prox + (V2).
(97)
Based on the j-strongly convexity of f, we have
(V Vf( 01 -22) 11|211 x221?
(98)
1
||prox - prox (oxxy((2)) (ل2))) S
| 22/1-
(99)
1 X
26

---

Understanding the Statistical Accuray-Commuuication Trade-off in Personalized Federated Learning with Minimax Guarantees
Now, we ready prove Lemma
First, from (Mishchenko et al., 2023), directly obtain the analytic properties of F,. Next, the analytic properties of h, are direct results from Assumption and 1. Finally, to analyze the property of the mapping wi we just need to use the result from the above claim as we know the definition of w ( (-) in (11).
B.2.2. INNER LOOP CONVERGENCE
Lemma 5 (JJi et al., 2022), Inner Loop Error Contraction). Suppose Assumption and hold, then if S 1/L for all t t 0 and the inner loop error bound of all clients can be formulated as:
=m El + (1+ (1 --np)) ||00 - -w -0,-,,11?
(3) c+1 |
w wif -
(100)
Proof.
The proof can be found in Lemma 2 (Ji al., 2022).
B.2.3. OUTER LOOP CONVERGENCE
Lemma 6 (Outer Loop Error Contraction). Suppose Assumption and I hold, then i I Lg. we have for all t > 0 and "g > 0:
||w (9)
11 < (1 7M4 re,) [ - /V 20)
(101)
+ (r) F(. +
+22) [VF((w (0)) FFWw
Eg
Proof. Note
( = A(w (x
(102)
We define
( (g)) = {r((w())) Σ
\(w!
- -w/k
(103)
[E[m]
rE[m]
Thus the global update rule can be written as wit = w0(0) - F (0)).
For the outer loop.
[((2) 1 10
||w (0) FFW(
=11u((0 T 1|2 -2y(w,
(9) Tووا) V F(( + F
(104)
<(1 + ml (g) - E 1 -2 (g) ml))) (F(w())) + + ) (
(")) - VF(w )1,
where we apply the Young's 's inequality with eg > the last line. Next, we bound the inner product term in the last line using the -trongg convexity of F:
=> -y(w( (a) Tls)) VF(w < -- (F(wu()) - - My (w( (9) w(s)|12)
2
(105)
=->(F(mo(2) P)-
1lm (9)
0 + (F(w(()) (g)
27

---

Understanding the Statistical Accuray-Commmuncatton Trade-off in Personalized Federated Learning with Minimax Guarantees
where F = (( and the last term F(w (9) - F(ws
(9)
can be upper bounded using the T.g-smoothness of F:
F( (0) <F(w ())) (VF(w. ) )) -
(
2
(a) F(w, (0)) + 2 (IVF(we! (0) - (
(3) |12 [ (0) ((
(106)
-
2 /F (9) )12
=F (
V F w
(0) |||
2 I=
| (0) + 2 (VF((( (
2
where the step (a) uses the fact- - (a, b)
2 llla
b112
1|11|1
1/161/2
Substituting (105) and (106) into (104) leads to
1 t+1
5(1+ 120, (0) - 1 + (0) )|²
((2)
(2)
A Fl( - (F"
kgg
-2x(F(u0(41) F) 7/4 1/ (0) ( ||
(107)
1| -VIIV((
(7
(((
<11 7/4 + (0) x 12 (+
2 1 + [VF( F
B.3. Proof of Theorem
B.3.1. PROOF OF THE GLOBAL MODEL CONVERGENCE RATE IN THEOREM 2
Recall the definition of c Lemma 5, we define
1
et
(108)
m kE(m)
Recall the definition (F (")), ( in Lemma and eq (103), the gradient approximation error is
[V (F
x² | Σ (wik
- m
m
(0.)) 1| X
(109)
Therefore, the recursion of optimization error given by Lemma 6 can further bounded as:
(0) m 11 = ||2
(0) - -600)11-222-2200000 - (1+ (V (1 -1g + 7e 100
+ 2 + 72 + Log ( (1+ [V & (F(w!(") )1?
Eg
(110)
(
-14 + 7e 7e,) (0) 1 7² 70(1 - + +)) (1++)) (VF(
5
2 + +2
+ +(-1) Iee.
+
Eg
28

---

Understanding the Statistical Accuracy-ommmuniatie Trade-off in Personalized Federated Learning with Minimax Guarantees
where the step (a) comes from the Young's inequality with Ç > 0 to be chosen and the step (b) follows from the step size condition y 1/L.-
Invoking Lemma 1 and Lemma 5, the inner loop optimization error is updated as
C+1 S (1 + -/ne)
( + +
(1+
1 )) (1 mppe))
K m
m
2+1,
w
(4)
| 1
(1+ (1++)(1 - 11)) Ec
K L (1 - (1-mue)*
1 (g) - 11+111 11?
(6)
2 ([+e)(t -me) "kec eet
1+ -
(1 mumn )k 1 (0)
(1II)
12
(1+ c)(l -mp)
kk e +
1 (+ (1 - (-mm ) L 7 22 )1 2X²e,)
11+6+ 2(1 + - ) (1 mue) x et + 2 1 (+ (1 mum) 122 (o) >1
(g) where step (a) is due to Lemma 1, step (b) uses the global update: w/+1 w.!) FF (o) and in step (c), we just
apply Cauchy inequality instead of Young's inequality.
Under S 1/Lx Lt, we have 1 - 18p4 < 1. Therefore, by choosing a large K we can always drive arbitrarily small. Let K be such that
9 1 - 1- S - 1744 + ygg
(112)
Then, we can rewrite (111) as:
1 - 7/g + 7/g + 1 11 + YCg -
C141
Cs
c2
2
(113)
+2 1+ 1 +) (1 (1- mue) (1- K
2 F (9) ||²
Letting C1 1-990
1 + )
X2, we can combine (113) with (110) and obtain
| (1 + ci e1+1
(g)
<(1 - 7i4g + Ttg) ||1! 3/ 112 + . ex) - 7- - 711 + +())
(114)
+ 1 +(1 71'g + 76g 4
2
x²) 22+
.2 [+ (1+ 1) (1 mum) (
Therefore, if the condition (112) and
4
(=+22+++)) (1+ (1 mue) L < 1 - 7L +
(115)
714g + 7eg ạ Eg
hold then (114) implies both || (0) w(ا) 1|2 and converge to zero at rate 1 72g + yCg.
It remains to specify the free parameters (eg: e, () in (112), (115) and others listed in Lemma 6 and Lemma 5.
Convergence Rate, For the connection term in (114), we set
Pg (1 7pg) > 0,
Eg 2
(116)
29

---

Understanding the Statistical Accuracy-Communictton Trade-off in Personalized Federated Learning with Minimax Guarantees
which, substituting into 7 Teg. gives the convergence rate
r :==1 1 1- 7 1-700
(rp2g) )
(117)
Under condition 7 S g. one can verify that E (0,1).
Step size conditions. Under the requirement (112), have
- 7 + 76g q 2Eg.
(118)
which gives the following sufficient condition for (115):
2 +2+ X2 2 1 1 + 2) (1 mue) S - - + ().
(119)
cg
Further restricting 7 such that
7(2 + c Un
1
= 7(2 112 1 c
(120)
2
it suffices to require the following for (119) hold:
2 gg
x2 2
1 (1+2) (1+)) muisu 12, S 0
m (1-)
- > + C)-
(121)
Letting = 1 and (= bg >
we collect all the conditions (116), (121) and (1 on y respectively as follows:
1 م > 0, 1-774 7M4 0,
(122)
(
2
(1 7/1g0² 2² (1 و 2 412 4(1 - mmpe) L2
(123)
1 i2g 2 (2+ + (1 .)
(124)
Using the fact that M4 S Lg. the above conditions simply to
(2+6412(1//g) nuo) S - (1g
7 <<lgg
(125)
B.3.2. PROOF OF THE LOCAL MODEL CONVERGENCE RATE IN THROREM 2
Proof. Note that
|
(4) Tn (0 S 21| - 1, + 211 112
(126)
For the first part on the right-hand side, recalling the definition of e/ in Lemma
2|| [000012= = 2||e, (4) 112
(6)
(127)
For the second term on the right-hand side, first, note the property in (11)
(6) w., prox
/ (o)))
(128)
Based on the first order condition of (2)
W prox /A (z)(1)).
(129)
30

---

Understanding the Statistical Accuracy-Communcction Trade-off in Personalized Federated Learning with Minimax Guarantees
Next, plugging (128) and (129) into (126), it yields
1 1.K
( - 21|et" 12 + 211 L// (10 prox L / (2)
(130)
x 21le ( 12 + 21 10 tū ())
where the last we use Lemma
In the proof of Theorem 2, we have established that both [10 T and e, converges to zero linearly at rate
1 7///22 (TP2)) /2, /2, combining with (130), the proof is finished.
B.4. Proof of Corollary
With 1/Le (A 1)- 1)-1-_11((2L) AtL. and using the fact that L x+ condition (125) for K becomes
An and Mig T4a
(cf. Lemma 1),
2 + 64L (1/Mg)2 ) n1-n
X2
(1+1))
11 A +
K
2 64
(A H)²
(Ap)2
x²
-
x-L
(131)
12
L 11
K
1
64
S
n?2
A +
16"
If L = μs, then the above condition trivially holds. Otherwise, sufficient condition for it is
K-2
L -
1
66*²
S
(132)
A
16'
where we have used the fact that
x L- レール
-
K
(L-M)
K-2
レ
K-2
2
x+L
A +
I
R
A+L
(133)
and k. = L/u 2 1. Finally, using the inequality log(1/2) 2 1 - x for 0 < x S we obtain
A+ L x+ u
K 2
log (1056x3).
(134)
B.5. Global Convergence Rate with Stochastic Noise
Similar to the noiseless case, we propose FedCLUP below which uses stochastic gradient descent to solve Problem (2).
Algorithm 2 FedCLUP: Federated Learning with Constant Local Update Personalization
Input: Initial global model w (9) initial local models (wo Jemm) global rounds T, global step sizes 7, local rounds K, local step sizes 17, stochastic batch size B
Output: Local models (wff) heemm and global model w((")
for = =...,,,, do
The server sends w
(9) to client i, Vi [m]]
Each client randomly draw B data without replacement;
Set 2
(i)
(5)
w. for l O,...,K - (
(1) wik
(6)
3/2 Eje[B] (7(w[1....)
A (w - )
i.k+1
Push (
(9)
= {(w (g) w.k) to the server
w 2+1
(g)
- w
(g) 2 Eielml {
31

---

Understanding the Statistical Accurac-Coommuicatton Trade-off in Personalized Federated Learning with Minimax Guarantees
We the following assumption characterize the stochastic noise when sampling data in each iteration all clients without replacement.
Assumption 4 (Stochastic noise). For any i E [m],j E [ng], E t > O, we assume
Vw, he wo wn /// 5 E Vi,, (, (1) w. wo),
(135)
Let define Fe, be the sigma algebra generated by the randomness by Algorithm 2 up to wiik
(1)
Lemma 7 (Inner Loop Error Contraction with stochastic). Suppose Assumption I and 2 hold, then if S 1/L, for all t 2 0 and > 0, the inner loop error bound of all clients can be formulated as:
91+1 = E
w 1
w1+1,*
(1)
Fet
iE(m)
$ ++c+2 1+ 1 2²
(1 -1-mpo mppe) ge
(136)
+ 2 1
(1 ) L V
2n o²
1d Bm
Proof.
9t+1 =B E
Σ
t+1.
w
(8)
FILLA
SE mm]
E
1/t B
V
1o 1-1--1
(8)
w 22 81g) - w wi+l+
(8)
Fet1,k
141k-1
ie mm
(1)
FettLe
(137)
w/+1,*
+ 1/
mB Σ
w
FiFLK
u.
E
1 Σ
u (
++1A-1
ui wi+1.+ Bm
(8)
Σ
V
m
32

---

Understanding the Statistical Accuray-Commmuication Trade-off in Personalized Federated Learning with Minimax Guarantees
To simplify the result, shall note
2
1
E
m. he w wis)
mB
E
+1 (.) V
V 20 (1 (1)
(2) (2) Nm 11 mf
mB
i
+
wo
m
0²
V w.
-1 w0
Vm, Im: woff))
m.
m
(
0²
2L
Σ
(2)
f, (3) (+,,, w (ffi))
(138)
mB
where step (a) stands due to Assumption 4 and the optimality of w step (b) uses the Lemma 2.29 in (Garrigos & Gower, 2023). Moreover, for the third term in (137), it yields
E
m
w
++1,--1
(
w
++1+:
Bm
1
Σ
Ev.
V hw (: w. ) |Fusa
i
1
w
++ 1,11111 -
(1)
w 1+ m
(1)
(6) Vw, (1 w
(139)
m
1
(f)
h: (8) wn))
1+ w
(211)
Σ
++1--1
(1)
22
2+1,
(6)
m
where the last line comes from the strong convexity of h; in Assumption 2. Plugging the results (138) and (139) into (137), we obtain
E
1
1+1,
(8)
Wit1,
(0)
FILLA
m
< (1 - -1/44)
1
Σ
w (2)
(1)
1+166-1
wi+1.0
m
(140)
+ 21 (Tel) 1)
Σ
hie (h (0) - "1 w221)
o²
+ ni Bm
If we assume ?/. S L we can simplify (140) as
33

---

Understanding the Statistical Accurac-CCommuniation Trade-off in Personalized Federated Learning with Minimax Guarantees
E
1
w 11
(6)
Fe+LI
2
I (1- puam
m71
1
w
1+1,6-1
(6)
211,0
(6)
+ 1h 0²
Bm
<11 <(1-wen)*
1 Σ
(i)
(3)
w (1)
(1 meM)) k-1
men))=+ 2 o²
1
Wi,
+
i,+
1,
Bm
1=0
o² 1/e Bm
+ (1+ !) (1 meee)* 7 (21VF (1) 22
(1++ -Me))* gt
Σ
(1
ueme)
k-1 )
1=0
(141)
Reorganizing all the terms in (141), we get
(8)
(3)
FettA
E
w
1+1,k
1+1,0
m
(142)
< 1+e+2 ( 12 120222² (1 (1- mue)** ge +2 (1 pem))* 1
(2)
2n o²
Pe Bm
(9) Theorem Suppose Assumptions 2 and 4 hold. Let (w, Jezu and {w,, Tezo be the sequence generated by Algorithm 2 with 7 < 1/hhg 11 S 1/ Le, and the inner loop iteration number satisfying
(2 61T2 mme) < <1 (1--71,))*
(143)
then w converges to ((9) linearly at rate (Tp2)/2 (1 within a neighbor of
8 X22 o²
min Mp pen ne
Bm
Proof. Analogy to the proof of Theorem we define
q = 1 +e+ (1+2) (00e++((+1))))1 L (1 =m
(144)
we assume
q 5 1 7/4 7Mg 7Eg.
(145)
and define
1 +22 (2=))++-))) x², Eg
Ci 74 + 7Eg 9
(146)
combining Lemma and Lemma 6, yields
34

---

Understanding the Statistical Accuracy-Communictton Trade-off in Personalized Federated Learning with Minimax Guarantees
B
w
[+1
(9) r0(
Fe+1,8
+ +19++1
(1 7M4 TEa)
-tolos1
+ +c19t) -1² (1+(+ ")
2
(2 2- 7 -=+
5-) x²) 2 (1+ 2) (1 -==))))*** 1 V (
+
1 711 + 7cg a
714
6g
C1 2m7 o²
Pt Bm
For VF (F )|
it suffices to show
47
+1+2++++))
L
x 1 h 12 11- <1->Lg(1 ().
1 7M4 + 7Eg q Eg
(147)
we set Cy = Hg 2. yields the convergence rate
Ykg 2
(148)
And the condition (147) can be reformulated as
4 1 +
x2++5+))
(1(1+- -mm))= 13 < x1 +
cg
kg
(149)
Restrict ?
7: 7(2 (2+ s g
(150)
Then condition (149) yields
1 X + - (1 -0m)*m))** 1
(151)
2
Then if we assume and Ç >bgg the conditions (145), (150) and (151) can satisfied with the following sufficient conditions
1
7
L 1
11 Li"
(152)
+ 4L",,>² (1 mhtee) < 7Mg
64
(1 " 12 x2 < (1 7Tgg)²
"
35

---

Understanding the Statistical Accuray--oommuniatton Trade-off in Personalized Federated Learning with Minimax Guarantees
And can get a more straightforward sufficient condition
1
7
(153)
Lg
7) S Li
(154)
+ 64 1
x² (1 - miee)* (1-mp))*
(11 =
(155)
Under such sufficient condition, the contraction of the combination of inner loop and the outer loop would be rewritten as
E
(o) w
|
FI+1.
+ c1g++1
$ (1 My + 770)
(1w0)0)
+ c19tt
+ Σ
1
2
1
11g
1-1
2
2
Σ
k-1
(1 u27) k-1
(1-4e7))
1p
Bm
o²
1=0
1=0
< (1 2 2710 (+1 (1 (100 (9) m600
1
l-1
2
men) k-t o²
0190
714
12
(156)
2
Bm
9
$ (1 2 )1144) s++
[200 (
+ C190
2
max (1
1
2114 1 - pen)
11
a²
2
eg
Bm
1=0
||
2
8
222 o²
< (1 2 (t1
+ c190
+
min
{ y1g (eng ng
Bm
With 7. = minf p(+L)
1 = 1/(2L,) = X+L 2 . we can get the solution within an error ball with the communication cost On, log(1/E)) = o (k A+a X+L
1
4T(*+))=;
(O(E) - min 4 ()( 1m))
A+u
o²
log ! and the com-
putation cost Ô (R log 1)-
As stated in Theorem 4.2 of (Hanzely & Richtárik, 2020), when p" X the stochastic noise term is independent of the number of clients. Consequently, it does not theoretically demonstrate the expected benefit of collaboration in reducing noise. In contrast, our analysis reveals that even when adjusting X, the noise remains of the same order, specifically O ( 1 Bm
C. Proof in Section 5
Corollary 4. Under the assumptions of Theorem and Corollary 2, w generated by Algorithm I satisfies
(2)
(2)
E
W
W1.K T.K
1
L L- 14
1 -600ll
1 K
E
W0,0
(157)
x(A 1n)
1
1
> ( (-+ [2(N)
0
+ R2
N
Φn (A)
for any i [m]. where (A) and (>( are monotone increasing functions of X with limx (A too and limx-o (2()) O.
Proof. The corollary is a direct result of Theorem and Theorem 2, where gı (A) and (2(A) are defined in (70) and (67).
36

---

Understanding the Statistical
Trade-off in Personalized Federated Learning with Minimax Guarantees
D. Additional Experiment Details and Results
D.I. More Experiment Details
Federated Learning (FL) has emerged as a widely adopted approach with numerous real-world applications, like Large Language Model (LLM) (Bai et al., 2024; Wu et al., 2024; Zhao et al., 2023), Reinforcement Learning (Zheng et al., 2024; 2025; Zhang al., 2025), Diffusion Model (Li al., 2024a). In this section, we provide more details on the implementation of the methods used in the empirical analysis.
Real Dataset. The MNIST dataset consists of 70,000 grayscale images of handwritten digits, each 28x28 pixels, classified into 10 classes (digits 0-9). The EMNIST dataset extends MNIST, including handwritten letters and digits. The Balanced split contains 131,600 28x28 grayscale images across 47 balanced classes (digits and uppercase/lowercase letters). The CIFAR-I0 dataset contains 60,000 color images (32x32 pixels, 3 RGB channels), categorized into 10 classes representing real-world objects (e.g., airplane, car, and dog).
Algorithms. To fully investigate the effect of personalization in Problem (2) with the Algorithm B.1, compare the two extreme algorithms (GlobalTraining and LocalTraining). Furthermore, since there exist other methods solving Problem (2) to do personalized federated learning, we also try to investigate the effect of personalization in other methods, like peedMe (T Dinh et al., 2020). The algorithm DeeMM has a similar design with a double loop to solve the subproblem in each communication round.
Selection of X. For the logistic regression on the synthetic dataset, we selected three values for small = 0.02, medium = 0.1, and large À 0.5. For logistic regression on the MNIST dataset, we used small 0.5, medium À = 1.5, and used small À 0.2, medium À = 0.5, and large À = 2.5. Such choice is to make sure that each line in the figure is clearly separable. Additionally, we implemented an adaptive choice of X following the formula outlined in Corrollary 1, with p set to 2. The value of p was determined through grid search over the range [1, 10] to ensure optimal performance. For other real datasets, the regularization term À is set as small À = 0.1, medium x = 0.5, and large À = 1.
large À = 2.5. For CNN on the MNIST dataset,
Selection of Step Size. For the synthetic dataset, aligned with Theorem 2, we set the global step size y = (A+ + (AL) and the local step size r 1/(L+ A). The smoothness constant L is computed as the upper bound of the L-smoothness constant for logistic regression, specifically 4- Ammmaax. where Amax denotes the largest eigenvalue of the Gram matrix X X. The local step size for the synthetic dataset was further tuned through grid search in {0.001, 0.01, 0.13. For the real dataset, the global learning rate was set to 1/A, while the local learning rate was set to 0.01, chosen via grid search. For both GlobalTraan and LocalTrain training baselines, the learning rate was also chosen via grid search within the range (0.001, 0.01, 0.1 LocalTrain is implemented using a local (S)GD, and GlobalTrain is implemented using FedAvg (McMahan et al., 2017).
Selection of Hyperparameters and Convolutional Neural Network Model. For the MNIST dataset, we implemented logistic regression using the SGD solver with 5 epochs, batch size of 32, and 20 total runs, and the same hyperparameter setup was used, except the batch size was reduced to 16 to ensure stable convergence in CNN with two convolution layers. To make our experiment more comprehensive, we also utilized five-layer CNN to train the MNIST dataset with 10 epochs, a batch size of 16, and 50 total runs. For the EMNIST dataset, we used the same five-layer CNN with the same settings. And for CIFAR1O, we implemented a three-layer CNN with 10 epochs, a batch size of 16, and 50 total runs To study the data heterogeneity, we set the number of classes for each client in the MNIST, EMNIST, and CIFARIO datasets as {2, 6, 10}, (30, 40, 47), and {2, 6, 10), respectively.
Optimizer. For the synthetic dataset, following the analysis in the paper, the loss function is optimized using gradient descent (GD). For the MNIST dataset, all models are implemented in PyTorch, and optimization is performed using the stochastic gradient descent (SGD) solver.
Evaluation Criterion. In terms of evaluation, for the synthetic dataset, we track the ground truth local model w.!" We compute the local statistical error as | w: - 112. To capture the total error at the f-th iteration, we report the local (6) ! which combine both optimization and statistical errors. For the MNIST dataset, we report test total error || w accuracy on the MNIST testing set as measure of the statistical error, and training loss for each client's 's training set as total error at the f-th iteration.
37

---

Understanding the Statistical Accuray-Commuuication Trade-off in Personalized Federated Learning with Minimax Guarantees
D.2. Additional Experiment Results
The Effect of Personalization on Accuracy over different data heterogeneity To further validate our conclusions about the effect of personalization solving Problem 2, we conduct additional experiments on real datasets, including EMNIST and CIFAR-10. For each dataset, explore three levels of statistical heterogeneity, controlled by varying the number of classes each client has access to, which follows widely used setup in federated learning literature. The models are trained using different convolutional neural network (CNN) architectures, denoted as CNN2 and CNN5, where the numbers indicate the number of convolutional layers in the network. As the ground truth underlying model is not accessible for these real datasets, we evaluate model performance based on classification accuracy on the test set, as shown in Tables 4. We also conduct personalization method focusing on Problem (2), PFedMe (T Dinh et al., 2020),
experiments another regularization-batt to demonstrate that our results could be generalized to other regularization-based personalized federated learning methods as well. For the columns corresponding to FedCLUP and pF pFedMe, we conduct experiments with varying regularization parameter X, investigating the role of personalization in the algorithms. Specifically, we experiment with small, medium, and large À values (see Appendix D.1 for detailed parameter settings). In Table 4, we can see that consistently across datasets, as
FedCLUP
GlobalTrain
LocalTTrin
PFodMc
Dataset
Clicat Class
high
median
low
high
median
low
0.5001
0.6011
0.6109
0.7001
0,3214
0.5534
0.6312
0.6712
MNIST Logit
0.6813
0.7001
0.7241
0.7718
0.6000
0.6312
0.7123
0.7681
10
0.8123
0.8213
0,8312
0.8391
0.7828
0.8001
0.8239
0.8291
0.3567
0,4721
0.6019
0.6123
0,3019
0.3973
0.5828
0.6172
MNIST CNN2
0.7001
0.7833
0.7843
0.8092
0.6231
0.7918
0,8093
0,8312
10
0,8753
0.8893
0,9032
0.9098
0,8194
0.8756
0.8771
0,8749
0.8891
0,9000
0,9333
0.9377
0.6536
0,9000
0.9003
0,9380
MNIST CNNS
0.8451
0.8941
0,9392
0.9446
0.7333
0.9288
0.9306
10
0.9091
0,9102
0.9421
0.9433
0,7633
0.9340
0.9385
0.9440
30
0.6084
0.6089
0.6011
0.6102
0.5583
0,6133
0.6129
0.6122
EMNIST CNNS
0.6097
0.6123
0.6357
0.6423
0.5644
0.6012
0.6102
0.6134
47
0.6278
0.6415
0.6672
0.6611
0.6111
0.6345
0.6532
0.6717
2
0.6101
0.6292
0.6340
0.6444
0,5801
0.60156
0.6012
0.6033
CIFARIOCNNS
0.6211
0.6311
0.6712
0.6949
0.5623
0.6163
0.6163
0.6439
0.6102
0.6712
0.7302
0.8041
0.6238
0.6744
0.7443
0.7732
Table Evaluation accuracy of algorithms (FedCLUP, GlobalTrain, LocalTrain, and pFecMe) across datasets and client classes. (CNNK means the CNN has k convolutional layers, low; medium, and high indicate different degree of personalization, and Client Class indicates the number of classes on each client).
personalization degree increase, the accuracy approaches that of LocalTrain, which trains separate models for each client. Conversely, as personalization degree decreases, the accuracy approaches that of GlobalTrrain, which represents purely global training. This interpolation behavior between LocalTrain and GlobalTrain, enabled by Problem (2), aligns well with our theoretical results in Theorem 1.
Moreover, dataset homogeneity increases (i.e., clients share more similar data distributions), we observe a general improvement in accuracy across all methods, regardless of the level of personalization. This result demonstrates that while personalization offers significant benefits in highly heterogeneous settings, its necessity diminishes as heterogeneity decreases. Additionally, experiments with different CNN architectures confirm the robustness of these findings across model designs. Although we did not provide a theoretical analysis for PFedMe in this paper, our results suggest that the empirical behavior of pF edMe is consistent with the theoretical insights derived for FedCLUP. In particular, we observe that pF edMe also exhibits interpolation between local and global learning under varying levels of data heterogeneity. We observe in Table 4 that LocalTrain consistently underperforms across all levels of statistical heterogeneity. This is because. while statistical heterogeneity is introduced by restricting each client's 's exposure to only subset of classes in the training process, evaluation is conducted on the entire dataset, including classes not seen during training. As result, LocalTrain's performance remains lower than that of other methods.
The Effect of Personalization on Statistical Error over different data heterogeneity Figure 4 demonstrates the effect of personalization on statistical error across varying levels of statistical heterogeneity R. As demonstrated in the theory, increasing personalization (moving from FedCLUP (low per) to F FedCLUP (high per)) shifts the solution closer to LocalTrain
38

---

Understanding the Statistical Cecurac-CCommuniction Trade-off in Personalized Federated Learning with Minimax Guarantees
while decreasing personalization makes the model behave more like GlobalTrain. For low heterogeneity, methods with lower personalization (i.e., greater collaboration) achieve lower statistical error, information be effectively shared across clients to improve learning, GlobalTrrann achieves the lowest error in this regime, while FedCLUP with less personalization also performs well. However, as statistical heterogeneity increases, collaborative learning becomes less effective. In this setting, LocalTrain outperforms other methods. Highly personalized FedCLUP also performs better than less personalized variants, aligning with the theory we established in Theorem 1. In Figure 5, we track testing loss as a
10
GiobafTrain
9
LocalTrain
FedCLLUP (high par)
FedCLUP (medium
Local
PedCLUP (low per)
0.0
0.5
1.0
1.5
2.0
2.5
Statistical interogeneity (H)
Figure 4. Impact of personalization on statistical error of RedCLUP solution across different levels heterogeneity (high per means training FedCLUP with high personalization degree).
function of communication rounds. Across all sub-figures, FedCLUP with smaller À (higher personalization) demonstrates faster convergence, especially in the early stages of training. Thus, shows that the trade-off between statistical accuracy and computation cost under the influence of personalization widely exists over statistical heterogeneity. Different Number
Classes-6
Classe5m4
Classess2
2.4
2.4
2.2
2.2
2.0
2.0
2.0
Inwiing Line
1.8
tnanng LaN
18-
1.6
2.6
1.6
1.4
1.-
1.0
1.0
10
20
Communicttio Rounds
Communication Rounds
&Commuiicaiin Rounds
FedCLUP thigh ped)
TedDLUP (medium par) FeOCLUP Low per)
Figure 5. Logistic Regression training loss versus communication rounds for the FedCLUP methods on MNIST dataset (high per refers to training FedClwy JUP with high personalization degree).
of Clients In Figure 6, the top row shows results for 100 clients, and the bottom row shows results for 1,000 clients, and in both results we adopt client sampling of 10% in each communication round. This tests the scalability and generalizability of the our results under typical federated learning setups. Consistent with the findings from Figure 1, FedCLUP with smaller X (higher personalization) consistently achieves faster convergence at the early stages of training, while FedCLUP with larger À (lower personalization) takes more communication rounds to converge. As statistical heterogeneity increases (measured by R), FedCLUP with smaller À gradually outperforms models with larger X, showcasing the adaptability of solving Problem 2 to different levels of heterogeneity. These results further validate the theoretical insights from Theorem I and Theorem 2, highlighting the influence of personalization on statistical and optimization performance in federated setups with larger numbers of clients.
The Effect of Personalization on Communication Cost Figure 2 investigates how personalization impacts communication efficiency in FedCLUP by analyzing the benefit of increasing local updates under different personalization levels. In the wwwppersonalization setting (left column), more local updates significantly accelerate convergence, reducing the reliance on frequent communication. However, in the pisoonnnsoniiizzttonn setting (right column), increasing local updates has a limited effect on convergence, indicating that frequent communication is essential for effective learning. This demonstrates
39

---

Understanding the Statistical Aecuracy-ommmuication Trade-off in Personalized Federated Learning with Minimax Guarantees
# Clients 100
R=0.1
R=1.0
R=2.0
15
14
11
13
10000 Enoor
Toua Enror
12
80
100
80
80
100
20
100
Communication Rounds
Communication Rounds
Communication Rounds
# Clients 1000
R=0,1
R=1.0
R=2.0
12
30
11
To0al EITOr
Tomal Emnor
0
20
60
90
100
20
80
100
20
40
60
80
100
Communication Rounds
Communication Rounds
Communication Rounds
par)
Figure 6. Performance of FedCLUP the Synthetic dataset with 100 clients (top row) and 1,000 clients (bottom row) with 10% client sampling under different levels of statistical heterogeneity (R).
that higher personalization requires more communication rounds to achieve comparable performance, aligning with our theoretical findings.
D.3. Additional Experiment for Rebuttal
1. STRONGLY CONVEX SETTING WITH SYNTHETIC DATA
As the theoretical results is established under strongly- settings, hence some expiremnts under strongly convex setting expected with discussion related to the conditional number k. We conduct an experiment on strongly convex problem: an overdeterminded linear regression task. We strictly follow the choice local step size, local computation rounds, and global step size as specified Corollary 2. As shown in Table and 8, for a fixed personalization parameter X, we observe that longer value of 6 result in slower convergence rates with respect tot he number of communication rounds. This expirical trend is consistent with to achieve given target error scales with (K X+L becomes stronger as À increases. This phenomenon aligns with our theoretical analysis, which shows that the sensitivity of communication complexity to i amplified for larger values of X. Similarly, we observe that increasing the condition number x also leads to a higher total number of gradient evaluations required to reach a target error. This observation is in agreement with our theoretical results where the total number of local gradient evaluations scales O(k log(/)))
theoretical prediction in Corollary 2, where the number of communication rounds required X+x+ log(1/e)) //)). Moreover, we observe that the impact of increasing
40

---

Understanding the Statistical CecuuicyCommmuicattio Trade-off in Personalized Federated Learning with Minimax Guarantees
Small Lambda
Medium Lambda
Large Lambda
10093 200.
Koppa 300.
kogpo 190.
bazpa 1000.0
huppae 3820.0
kuppo 1002.0
Optimizttion 22-
Optimieetee Frior
Optimizztiion
10
15
20
23
70
5
20 20
20
40
20
23
25
30
Communication Rounds
Communiccaton Rounds
Communication Rounds
Figure 7. Optimization error versus communication rounds under varying condition numbers x. The left, middle, and right panels correspond to FedCLUU with small, medium, and large values of X, respectively. Across all settings, we observe that larger x leads to slower convergence, with the effect becoming more pronounced increases.
hoppe 16C.
Optintaation Erme
Figure 8. Optimization error versus total number of local gradient evaluations per elient under varying condition numbers R. As R. increases, the number of gradient evaluations required to achieve given optimization error also increases.
D.3.2. DATASETS WITH NATURAL. PARTITIONS
FedCLUP different personalization degree
pFedMe different personalizaaion degree
1.6
high personeliceto
high personalizatinn
median personolization
1.75
median personaliaation
1.4
low: sonalizzza
low personalization
global model
1.50
globel model
model
1.2
0.8
0.75
0.50
0.4
0.2
0.25
200
300
500
100
400
Communicatio Round
Round
(a) The loss of FedCLUP with CelebA
(b) The loss of PFedMe with CelebA
Figure 9. Loss of FedCLUP (a) and PFedMe (b) with different personalization degrees the CelebA dataset. Low, median, and high personalization correspond to regularization terms 0.5, 0. and 0.001, respectively. For FedCLUP, the test accuracy is highest with low personalization (0.919), followed by median (0.915) and high (0.888). For PFedMe, the test accuracy is highest for low personalization (0.910), followed by median (0.901) and high (0.890). The test accuracy for Global'rran and LocalTrain is 0,91 9 and 0,561, respectively.

---

Understanding the Statistical AccuracyCCommuniatioo Trade-off in Personalized Federated Learning with Minimax Guarantees
purzor alactien cegroe
personalizatio dogroe
2.5
13
1.5
3
Hgn personal cation
Hih persmmalaation metion personaizztion
mision Personolicatto
peszraliation
(a) The loss of FedCLUP with Sent
(b) The loss of PFedMe with 140
Figure 10. Loss of FedCLUP (a) and PFedMe (b) with different personalization degrees on the Sent140 dataset. Low, median, and high personalization correspond regularization terms 0.1, 0.00S, and 0.001, respectively. For FedCLUP,, test accuracy highest for low personalization (0.734), followed by median (0.702) and high (0.696). For pFedMee the test accuracy is highest for low personalization (0.727), followed by median (0.703) high (0.701). The test accuracy for GlobalTrain and LocalTrain is 0.730 and 0.353, respectively.
42


Reviews:
[{"review_id": "FhLadLydrc", "reviewer": "Reviewer_XV8t", "summary": "This paper proposed a personalized federated learning algorithm that captures the relationship between communication cost and the degree of personalization. Convergence theories are derived, showing that the total required gradient steps are irrelevant to the personalization degree $\\lambda$, while the scaling of the communication cost w.r.t  $\\lambda$ is related to the conditional number $\\kappa $. Numerical results further showed the convergence speed of their method under different personalization degree.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point. We hope these clarifications help address your concerns.\n\n**The concern raises for the definition of parameter space**\n\nA natural measure of local model's heterogeneity could be the average of their mutual distance given by $\\frac{1}{m^2}\\sum_{i = 1}^m \\sum_{j = 1}^m \\\\|w_\\star^{(i)} - w_\\star^{(j)}\\\\|^2$, which is equivalent to $\\frac{2}{m} \\cdot \\sum_{i = 1}^m \\\\| w_\\star^{(i)} - w_\\star^{(g)}\\\\|^2$ with $w_\\star^{(g)} := \\frac{1}{m} \\sum_{i=1}^m w_\\star^{(i)}$. Therefore, we define the data heterogeneity over the parameter space as $\\frac{1}{m} \\sum_{i = 1}^m \\\\| w_\\star^{(i)} - w_\\star^{(g)}\\\\|^2\\leq R^2$. The definition is also used in prior works [1][2].\n\n\n\n**Experiment with strongly convex and discuss the condition number -- least square problem, vary the choice of condition number, examine both communication and computation**\n\n\nWe thank the reviewer for this valuable suggestion. In response, we conducted additional experiments on a strongly convex problem: an overdetermined linear regression task. We strictly follow the choices of local step size, local computation rounds, and global step size as specified in Corollary 2. Please refer to [Figure1](https://postimg.cc/BLJmCB4b) and [Figure2](https://postimg.cc/zbRG0K7m) for detailed experimental results.\n\nAs suggested, we study the effect of the condition number $\\kappa$ on convergence behavior. Specifically, for a fixed personalization parameter $\\lambda$, we observe that larger values of $\\kappa$ result in slower convergence rates with respect to the number of communication rounds. This empirical trend is consistent with our theoretical prediction in Corollary 2, where the number of communication rounds required to achieve a given target error $\\epsilon$ scales with $\\mathcal{O}(\\kappa \\frac{\\lambda + L}{\\lambda + \\mu} \\log(1/\\varepsilon))$. Moreover, we observe that the impact of increasing $\\kappa$ becomes stronger as $\\lambda$ increases. This phenomenon aligns with our theoretical analysis, which shows that the sensitivity of communication complexity to $\\kappa$ is amplified for larger values of $\\lambda$. Similarly, we observe that increasing the condition number $\\kappa$ also leads to a higher total number of gradient evaluations required to reach a target error. This observation is in agreement with our theoretical results where the total number of local gradient evaluations scales as $\\mathcal{O}(\\kappa\\log(1/\\varepsilon))$. \n\n\n\n**The study focuses on strongly-convex problems, but the accuracy-communication trade-off may differ in weakly-convex or non-convex cases with non-unique solutions. Further analysis is needed**\n\nEstablishing the statistical rate of the solution relies on the  strong convexity of the loss. This reason is that for strongly convex problems the minimizer is unique, which enables analyzing its property using first order optimality conditions. However, weakly convex and nonconvex problems can have multiple minimizers and stationary points. Under such cases, first order stationarity can no longer distinguish these points, leave alone characterizing their statistical accuracy. One may resort methods such as consider losses with special landscape (e.g., restricted strong convexity, one-point strong convexity) or algorithmic regularization to tackle some subclasses of nonconvex losses, yet such extensions are \nhighly nontrivial and would require a different set of techniques. We acknowledge that analyzing the convergence of the algorithm to a stationary point for weakly convex objectives could be more tractable, but doing so alone without having its statistical accuracy cannot reveal the communication-accuracy tradeoff.\n\n\n[1] Chen, S., Zheng, Q., Long, Q., and Su, W. J. (2023). Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training? Journal of Machine Learning Research, 24(262), 1-59.\n\n[2] Duan Y, Wang K. Adaptive and robust multi-task learning. The Annals of Statistics, 2023, 51(5): 2015-2039.", "claims_and_evidence": "Yes, the claims and results are all backup with proof or evidence.", "methods_and_evaluation_criteria": "Yes, the choice of the datasets makes sense, and the additional data heterogeneity experiments in the appendix showed the difference between various personalization settings.", "theoretical_claims": "I didn't find the definition of 's parameter space quite convincing. The parameter space is a ball build around the weighted average of all local ground truth models. However, if goal this space is to capture the heterogeneity, shouldn't the ball measure the Euclidean distance between the global ground truth (the optimal model of the sum of all local models) instead of the weighted average of the local ground truth? A further explanation of why such measure is chosen to evaluate the statistical error would make the result more persuasive.", "experimental_designs_or_analyses": "The theoretical result in this work is under strongly-convex settings, hence some experiments under strongly convex settings is expected with discussion related to the conditional number $\\kappa$ . However, it seems the experiments are all under weakly-convex/non-convex, hence it would be nice if additional discussion on strongly-convex settings (synthetic data should be enough) can be added.", "relation_to_broader_scientific_literature": "The work provides a new algorithm and theoretical insight for personalized FL to trade-off between communication cost and personalization level.", "essential_references_not_discussed": "Based on my knowledge, the paper provides a reasonable overview of prior work relevant to its key contributions. I am not currently aware of any essential references that are missing.", "other_strengths_and_weaknesses": "The rate they derived is based on strongly-convex. However, it unclear when under weakly-convex/non-convex cases, where possibily non-unique set of optimal/stationary solutions exists, whether if the accuracy-communication trade-off they discover can still hold true. Further analysis should provide a better insight for more real-world optimization problems.", "other_comments_or_suggestions": "I am not currently aware of any typos or minor mistakes.", "questions_for_authors": "There are a few points I wish the authors to address:\n1.\tThe theoretical results are derived under strongly convex settings, but the experiments appear to be conducted in weakly convex or non-convex settings. It would be beneficial to include experiments under strongly convex settings, possibly with synthetic data, and discuss their relation to the condition number $\\kappa$. \n2.\tShouldn't the definition of $w_*$ 's parameter space be centered around the global ground truth model instead? A clearer justification for this choice would strengthen the argument. \n3.\tThe derived rate assumes strong convexity, but it is unclear whether the accuracy-communication trade-off still holds in weakly convex or non-convex settings, where multiple optimal or stationary solutions may exist. Further analysis is needed to understand how these findings extend to real-world optimization problems.", "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": "JcWxftpOkT", "reviewer": "Reviewer_XVuq", "summary": "This paper studies personalized federated learning, i.e., where data owners (clients) have their own distribution.\nThe paper studies in particular the trade off between exploiting more shared knowledge (increasing the communication cost) and relying mire on local data.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point.\n\n**The Structure of the Theoretical Proof** \n\nWe establish the statistical convergence rate (Theorem 1) in Section A.3. Specifically, Section A.3.1 derives the statistical rate for the global model $\\tilde{w}^{(g)}$, and Section A.3.2 builds upon this result to establish the statistical rate for each local model $\\tilde{w}^{(i)}$. We then derive the optimization convergence rate (Theorem 2) in Section B.2. The analysis proceeds in stages: we first establish the convergence rate for the global model in Section B.3, followed by the local convergence rate in Section B.5. We will further refine and reorganize the proof structure later.\n\n**Significance of Experiment, Validation of Theoretical Claims, and Comparison with Existing Algorithms**\n\nThe primary goal of our experiments is *not* to demonstrate that the proposed algorithm statistically outperforms existing methods. Instead, our experiments are designed to validate the theoretical insights. To this end, the experiments focus on evaluating *one algorithm across different levels of personalization*, rather than making direct comparisons across algorithms. This design enables a clean and focused investigation of the trade-offs described in Theorems 1 and 2 and Corollary 3:\n\n$\\bullet$ Statistical Accuracy: As shown in Table 2 and Table 4 (Appendix), when collaborative learning is beneficial, decreasing the personalization degree improves generalization performance. This observation directly supports the theoretical result in Theorem 1.\n    \n$\\bullet$ Communication Efficiency: Figure~1 and Figure 3,4,5 (Appendix) show that decreasing the personalization degree leads to slower convergence in terms of communication rounds. More communication is required to achieve the same level of optimization error, which is consistent with the theoretical analysis in Theorem 2 and Corollary 2.\n    \n$\\bullet$ Trade-off: the trade-off characterized in Corollary 3 is verified: increasing the personalization degree reduces communication cost but may hurt statistical accuracy.\n\nFor practical implications, there exists an optimal choice of $\\lambda$ that uses minimal communication rounds to achieve a given target total error (See Figure 1 or Left of [Figure 3](https://postimg.cc/Dm6w5vdw). This provides a tuning guidance for personalization to utilize the tradeoff. As Right of [Figure 3](https://postimg.cc/Dm6w5vdw) shows, as soon as the validation performance plateaus or the statistical error stops improving significantly, we gradually increase $\\lambda$. The dynamic strategy approximates the optimal  $\\lambda$ and meets a desired error threshold with minimal communication rounds. Due to space constraints, we kindly refer the reviewer to our response to Reviewer Krd5 for a more detailed discussion.\n\n**The communication cost and approaches with compressed gradients** \n\nWe define the communication cost as the total number of communication rounds. The vanilla FedAvg method, as far as we know, also measures the communication cost using this metric[1]. Compression schemes such as top-K pruning and quantization, on the other hand, are extra techniques one can integrate and apply to either the model or the gradient transmitted. This line of work is orthogonal to our study.\n\n**Compare to other work in Table 1, but use different variables. So the comparison is difficult, and it's unclear for the conclusion** \n\nThe key takeaway from Table 1 is that most prior works omit statistical analysis, whereas we fill this gap by deriving a minimax-optimal statistical rate. Our communication cost is also nearly optimal (up to logarithmic factors [2]) and has a clear, interpretable dependence on the personalization parameter. This makes our work the first to quantitatively characterize the communication–accuracy trade-off. Indeed, different works adopt different notations and assumptions, making direct alignment difficult—we will add clarifications later.\n\n**Focuses on a basic algorithm, omitting others that might influence communication costs per round**\n\nThe primary goal of this work is to provably show the trade-off and provide tuning guidance. The algorithm we propose is intentionally designed as a clean, simple, and principled instantiation for solving Problem 2. We have derived a minimax optimal statistical and a sharp linear optimization convergence bounds to clearly disentangle the role of the personalization degree in the trade-off.\n\n**Typo error**\n\nThank you for pointing this out. We will carefully proofread the manuscript and correct all typos in the revised version.\n\nWe hope our responses address your concerns.\n\n[1] Koloskova A, Loizou N, Boreiri S, et al. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates[J].\n\n[2] Hanzely F, Hanzely S, Horvath S, et al. Lower Bounds and Optimal Algorithms for Personalized Federated Learning[J]. 2020.", "claims_and_evidence": "The theorems are supported by proofs in the appendix.\nThe proofs are rather hard to follow\n\nThe paper contains experiments, which are illustrative and compare different levels of personalization but dont really support the claims and dont compare to existing methods.  Table 2 does some comparison with pFedMe but does seem to show significant differences.", "methods_and_evaluation_criteria": "The authors claim to investigate the communication cost, but in reality only study the number of iterations.  The communication cost is assumed to be linear in the number of rounds, but this ignores approaches such as fedavg and approaches which send only compressed gradients in every round.\n\nThe theoretical results are compared to other work in Table 1 but as the several results use different variables the comparison is difficult and it is unclear what we can conclude.\n\nIt would be interesting to see experiments that show how and when the results of the current paper are significantly better than existing work.", "theoretical_claims": "I went through most proofs but they are hard to follow and confirming their correctness would require a huge amount of time", "experimental_designs_or_analyses": "The experiments dont indicate which conclusions are statistically significant.\n\nThe experiments are illustrative, not aimed at proving claims, hence it is not critical that their design is soubd.", "relation_to_broader_scientific_literature": "The work ignores alternative optimization algori5hms and other strategies which may affect the relation between the communication cost per round. The paper analyzes a single (simple) algorithm.\n\nThe paper compares with earlier work analyzing convergence speedn but as said Table 1 is not easy to interpret.", "essential_references_not_discussed": "--", "other_strengths_and_weaknesses": "My main concern is the significance of the work.", "other_comments_or_suggestions": "* 115R : solution of i-th local model -> solution of the i-th local model\n* Eq (5) the variable i in $\\sum_{i=1}^m$ shadows the different variable i used among others in the preceding term $w_*^{(i)}$. Please use another index, e.g., j, instead\n* 282R : a higher degree of collaboration will also results -> result", "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": {"ethical_review_concerns": "--"}}, {"review_id": "6sumEW7dGn", "reviewer": "Reviewer_5cgC", "summary": "The authors theoretically address the accuracy-communication trade-off in personalized federated learning (FL). In other words, $\\lambda$, which controls the regularization between global and local models, represents the accuracy-communication trade-off, and an analysis of this is conducted.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point. We hope these clarifications help address your concerns.\n\n**The summarized key takeaway as our main claim** \n\nFrom a statistical perspective (Section 4.1), we provide a tight generalization bound for Problem 2 under standard assumptions. Our analysis quantifies how the degree of personalization $\\lambda$ affects the statistical accuracy. We show that when collaborative learning is beneficial, increasing personalization reduces collaboration across clients,  which may degrade the statistical accuracy of the problem solution.\n\nFrom an algorithmic perspective (Section 4.2), we analyze the convergence of FedCLUP. Our results characterize how $\\lambda$ influences the number of communication rounds required for convergence. Increasing personalization implies less dependence on server-client communication, which reduces communication overhead and thus improves communication efficiency.\n\nBy combining these two parts, summarized in Section 5—demonstrate a fundamental trade-off: higher personalization may improve communication efficiency but at the cost of statistical accuracy. This claim leads to a key practical insight: to achieve a specific target error, there exists an optimal choice of personalization degree that minimizes the total communication cost required to reach the desired performance. The claim is verified in Figure 1. (See [Figure](https://postimg.cc/Dm6w5vdw) and the response to reviewer Krd5 for a detailed description).\n\n\n**Unsure how Algorithm 1 differs from the existing algorithms** \n\nThe existing algorithms solving Problem 2 are listed in Table 1, where most of the existing works either don't explicitly analyze the local convergence cost, like FedProx and pFedMe, or fail to demonstrate such a trade-off. For the designed algorithm, we quantitatively characterize how changing the personalization degree leads to the trade-off between communication cost and statistical accuracy. In contrast, most prior studies either do not explicitly analyze statistical convergence or fail to provide a fine-grained analysis linking optimization and statistical error, therefore lacking a theoretical guarantee for practical guidance.\n\n\n**The Difference between Algorithm 1 and Algorithm 2**  \n\nAlgorithm 2 is the stochastic version of Algorithm 1, accounting for the scenarios where the sample size is large and computing the full gradient is impractical. We also extended our analysis to this setting, accounting for the injection of stochastic noise into the algorithm.\n\n\n**The models and datasets are all too outdated**\n\nThank you for the suggestion. We have extended our experiments to include more recent datasets and models such as CelebA (image classification) and Sent140 (NLP). We also experiment with more diverse models from CNN to LSTM. Some preliminary results are available [here](https://postimg.cc/H8r5drTd), showing similar trends as in Figure 1 and Table 1. We will add more details on the experiments, elaborate on these findings, and include them in the final version of the paper.\n\n**The performance is lower compared to other algorithms used for comparison, raising concerns about its practicality**\n\nWe would like to clarify that the primary goal of our experiments is not to demonstrate that the proposed algorithm statistically outperforms existing methods. Instead, our experiments are designed to validate the theoretical insights and provide practical tuning guidance. To this end, the experiments mainly focus on evaluating one algorithm across different levels of personalization. This design enables a clean and focused investigation of the trade-offs described in Corollary 3. \n\nBeyond the validation of trade-off, our analysis does provide practical guidance. First, based on the trade-off, there exists an optimal $\\lambda$ for reaching the target error with the minimal communication cost (See Figure 1 or detailed description in Left of [Figure](https://postimg.cc/Dm6w5vdw)). For practicality, when the optimal $\\lambda$ is unknown, we provide tuning guidance (See Right of [Figure](https://postimg.cc/Dm6w5vdw)): as soon as the validation performance plateaus or the statistical error stops improving significantly, we gradually increase $\\lambda$. The dynamic strategy approximates the optimal $\\lambda$, achieving target error with minimal communication cost (See the response under reviewer Krd5 for details).", "claims_and_evidence": "- It is difficult to follow. While the theoretical explanation is well-structured, it would be helpful to summarize the key takeaways more clearly. The main claim is not entirely clear. Please clarify the distinct insights that this theoretical analysis offers beyond the broadly understood existing knowledge.", "methods_and_evaluation_criteria": "- I am unsure how Algorithm 1 differs from the existing algorithms. Additionally, is it correct that Algorithm 2 differs from Algorithm 1 only in terms of batch consideration?", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "- The models and datasets used in the experiment are all too outdated.\n- The performance is lower compared to other algorithms used for comparison, raising concerns about its practicality.", "relation_to_broader_scientific_literature": "This study aims to theoretically analyze the trade-off between communication and accuracy, which is the fundamental aspect of FL.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "- While the theoretical aspects are important, I prioritize the practical aspects more. I wanted to clarify that this evaluation was made with that perspective in mind.", "questions_for_authors": "None", "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": "5hmN2JxXt3", "reviewer": "Reviewer_Krd5", "summary": "This paper studies the trade-off of accuracy and communication in personalized federated learning and presents the theoretical analysis of the effects of personalization degree. The theoretical findings are validated on synthetic and real-world datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point. We hope these clarifications help address your concerns.\n\n**The practical implication on the choice of $\\lambda$**\n\nFor the practical implication of personalization in our experiments, we include an illustrative example on synthetic data (similar to that in Figure~1a of the manuscript) that demonstrates how the personalization degree, controlled by $\\lambda$, influences convergence behavior and total error. Specifically, we compare several settings: (1) local training, corresponding to the limiting case of FedCLUP as $\\lambda \\to 0$, (2) global training, corresponding to FedCLUP as $\\lambda \\to \\infty$, and (3) FedCLUP with three intermediate values of $\\lambda$. \n\nAs Figure 1 (See detail in [Figure](https://postimg.cc/Dm6w5vdw)) shows, different values of $\\lambda$ yield distinct convergence speeds and final total errors. In particular, a smaller $\\lambda$ (i.e., stronger personalization)  results in faster convergence in terms of communication rounds due to the algorithm relying less on communication among clients. However, this comes at the cost of a larger final total error, as reduced collaboration across clients limits the statistical generalization. Conversely, larger $\\lambda$ (i.e., weaker personalization or more collaboration) leads to slower convergence but consistently achieves a lower final total error due to the benefit of collective learning.\n\nAs a direct implication, shown in the left part of [Figure](https://postimg.cc/Dm6w5vdw) when aiming to reach a target total error, there exists a unique optimal $\\lambda$ that minimizes the total number of communication rounds needed to achieve that error compared with FedCLUP with other personalization degree or GlobalTrain. This insight provides an important practical guideline derived from the theory established in Corollary 3.\n\n**The potential solution of $\\lambda$ in practice**\n\nFor the potential solution in practice, we propose a heuristic dynamic tuning strategy for practical guidance to approximate the optimal $\\lambda$. As shown in the right part of [Figure](https://postimg.cc/Dm6w5vdw), the idea is to begin with a small $\\lambda$ (i.e., close to LocalTrain) to leverage its communication efficiency. As soon as the validation performance plateaus or the statistical error stops improving significantly, we gradually increase $\\lambda$. This allows the model to benefit from enhanced generalization through increased collaboration,  at the expense of slightly higher communication cost. By progressively adjusting $\\lambda$ in this way, one can finally identify the optimal personalization degree that balances the trade-off and minimizes the total communication cost required to meet a desired performance threshold. \n\nFor the broader impact, the dynamic strategy would possibly be applied to other regularization-based personalization federated learning algorithms as tuning guidance. It would save the communication cost a lot for achieving a target performance.\n\n\n\n**the definition of personalization**\n\n\nIn D.1. Additional Experiment Details, for each experiment, the small $\\lambda$ value represents a high personalization, the median $\\lambda$ represent the median personalization degree, and the large $\\lambda$ represents high personalization. The specific choice of $\\lambda$ is specified in Appendix D.1.", "claims_and_evidence": "The claims are supported by theoretical analysis and experimental validations.", "methods_and_evaluation_criteria": "The proposed method and evaluation make sense.", "theoretical_claims": "The theoretical claims and proofs seem to be correct.", "experimental_designs_or_analyses": "The experimental design and analysis are sound in general.", "relation_to_broader_scientific_literature": "This paper contributes to the general federated learning community.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "**Strength**\n- The analysis of the trade-off between personalization and communication is useful for the federated learning community.\n\n- The findings are well supported by experimental results.\n\n\n\n**Weakness**\n- The practical implication on the choice of \\lambda is not clear from the corollary 1. It would be helpful to further discuss the potential solution of \\lambda. \n\n- The definitions of high, medium, and low personalization degrees are not clear.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see the weakness part.", "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": "iP8B5EwWRx", "reviewer": "Reviewer_g4zn", "summary": "In this paper, the authors study a personalized FL objective and showed its statistical accuracy under strongly convex, smooth model. The authors then propose a new algorithm to solve the problem. Empirical results show that as the personalization level changes, the model is able to interpolate between pure local training and pure global training.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point. We hope these clarifications help address your concerns.\n\n**Comparison with Ditto [1]** \n\nOur work is significantly different from Ditto (Li et al. 2021 [1]) in multiple aspects and is far from being a simple extension of prior work.\n\n***Different objective*** The formulation considered in Ditto [1] is given by \n\n$$\\min _ {\\\\{w^{(i)}\\\\} _ {i = 1}^m } f _ i(w^{(i)}) + \\frac{\\lambda}{2} \\\\|w^{(i)} - w^{(g)}\\\\|^2, \\quad \\text{s.t.} \\quad w^{(g)} \\in \\operatorname{argmin} _ {w} G(f_1(w), \\ldots, f _ m(w)).$$\n\nDitto first solves the lower-level problem to obtain $w^{(g)}$, then uses it in the upper-level problem to solve for each $w^{(i)}$. This differs from our formulation, where the local models $w^{(i)}$ and the global model $w^{(g)}$ are optimized jointly. Accordingly, we adopt a completely different set of techniques for analyzing the problem.\n\n\n***Different Trade-off*** More importantly, although Ditto also investigates a trade-off phenomenon, they study a different trade-off compared with ours. They primarily investigate the effect of personalization to balance the trade-off between robustness to adversarial clients and the generalization benefits gained from collaboration. As such, the trade-off they study focuses on the strategy to minimize the statistical error of the final solution, and does not explicitly incorporate optimization error. In contrast, our work investigates the trade-off between statistical accuracy and communication efficiency, aiming to optimize the total error, which includes both statistical error and optimization error.\n\nWhile Ditto briefly mentions a communication-utility trade-off in Section 3.2, it is only proposed as a potential direction for future analysis. While they provide some experimental results in their paper that illustrate this phenomenon, the trade-off between communication and statistical accuracy hasn't been *quantitatively analyzed* in the paper. In contrast, our work is specifically centered on the theoretical understanding of this trade-off. We provide a comprehensive theoretical analysis that explicitly characterizes how both statistical accuracy and communication complexity depend on the personalization parameter $\\lambda$. As a unique contribution, our theory gives a principled understanding of how to select $\\lambda$ to optimize the overall performance in federated settings (see our response to the next question for more details).\n\n\n***Different Theoretical Results*** Additionally, we note that the theoretical analysis in Ditto is restricted to a simplified linear regression setting, as acknowledged in their paper under a \"simplified set of attacks and problem settings\". In contrast, we provide a tight theoretical analysis for a general function class $f$. Our statistical error bound is proved to be minimax optimal and our optimization convergence is shown to be linear. Establishing both convergence and generalization bounds in this more general setting is technically non-trivial and constitutes a key contribution of our work.\n\n\n\n\n**Observing the existence scenarios that FedCLUP outperforms GlobalTrain and LocalTrain**\n\n\nSuch scenarios do exist. As shown in the left panel of [Figure](https://postimg.cc/Dm6w5vdw), FedCLUP achieves a lower total error than both LocalTrain and GlobalTrain between 5 and 40 communication rounds. Moreover, to reach a given target total error, there exists a unique optimal $\\lambda$ that minimizes the required number of communication rounds. Based on this, we propose a dynamic tuning strategy to approximate the optimal $\\lambda$, as demonstrated in the right panel of the same figure. Please refer to our response to Reviewer Krd5 for further discussion. \n\n**Perform experiments with varying levels of heterogeneity**\n\nWe indeed consider different levels of heterogeneity in Appendix D.2. Table 4 sets the data heterogeneity by varying the number of classes for the clients' data. \n\n**Perform experiment with natural partitions**\n\nThanks for the reviewer's suggestion. We add more experiments to study the CelebA and Sent140 datasets. The experiment details follow [1] and [2] respectively. As an example, in [Figure](https://postimg.cc/H8r5drTd), we observe similar trends as in Figure 1 and Table 1. We will cover more results, elaborate on these findings, and include them in the final version of the paper.\n\n\n\n\n[1] Li, T., Hu, S., Beirami, A., \\& Smith, V. (2021, July). Ditto: Fair and robust federated learning through personalization. In International conference on machine learning (pp. 6357-6368). PMLR.\n\n[2] Duan M, Liu D, Ji X, et al. Fedgroup: Efficient federated learning via decomposed similarity-based clustering. IEEE SustainCom, 2021: 228-237.", "claims_and_evidence": "- Problem 2 is different from the objective studied in Hanzley & Richtarik et al. 2020. The latter proposed a mean-regularized objective, where Problem 2 is a global-regularized objective. The proposed objective is more similar to what is proposed in Li et al. 2021 [1].\n- In Section 5, it is incorrect to claim \"Our work is the first to quantitatively characterize how changing the personalization degree\nleads to the trade-off between communication cost and statistical accuracy.\" See section below for details.\n\n\n[1] Li, T., Hu, S., Beirami, A., & Smith, V. (2021, July). Ditto: Fair and robust federated learning through personalization. In International conference on machine learning (pp. 6357-6368). PMLR.", "methods_and_evaluation_criteria": "- The proposed FedCLUP method seems to be exactly the same as the method is Li et al. 2021 [1]. I just read through that paper more carefully. It seems [1] has already performed convergence analysis and showed how personalization degree leads to tradeoff between communication and utility. Hence, the novelty and contribution of the proposed work is over claimed. In that case, I wonder whether the contribution is mainly an extended theoretical analysis of this prior work?\n\n[1] Li, T., Hu, S., Beirami, A., & Smith, V. (2021, July). Ditto: Fair and robust federated learning through personalization. In International conference on machine learning (pp. 6357-6368). PMLR.", "theoretical_claims": "- I did not check all the steps of the proof. But the convergence rate seems correct.", "experimental_designs_or_analyses": "- Compared to the results in Li et al. 2021, I'm wondering whether the authors also observe the existence of an optimal lambda where the personalized model outperforms both pure global and pure local training. Currently, it looks like the evaluation does not outperform max{local, global}.\n- Limited evaluation, the authors should perform experiments in settings with 1. varying level of heterogeneity, 2. datasets with natural partitions, such as CelebA, Sent140, etc.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "As mentioned earlier, the key contribution of this work has a non trivial overlap with Li et al 2021, in terms of the method and findings. Please see previous sections for a detailed discussions.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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:

Meta-review: This paper makes a very important theoretical contribution to personalized federated learning (PFL), by analyzing the statistical accuracy and its relation to the personalization coefficient and communication efficiency. Because PFL is essentially about generalization performance, standard approaches that analyze the algorithmic convergence using optimization theory are insufficient to show the gains in PFL. This paper takes the first step to analyze the statistical accuracy, i.e., the gap between the empirical optimal model and the statistical optimal model (the latter assumes knowledge of the full data distribution), for an actual implementable algorithm. The results can enrich the fundamental understanding of PFL.

I feel that the paper would reach an audience with more relevant interest if the title could include keywords like statistical accuracy, theoretical analysis, etc. The current title is too generic. Based on the reviewers' comments, it would be helpful to include a more detailed comparison with related works (parts of such discussions could go into the appendix if the main paper's space is limited) and experiments with more sophisticated datasets and models. Although such additions may not be closely related to the core contribution of this work, they could help readers in the general area of FL and PFL understand this work's contributions better.
Decision: Accept (poster)