Understanding the Statistical Accuracy-Communication Trade-off in Personalized Federated Learning with Minimax Guarantees

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.

Comparison with Ditto [1]

Our 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.

Different objective The formulation considered in Ditto [1] is given by

$\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)).$

Ditto 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.

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.

While 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).

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.

Observing the existence scenarios that FedCLUP outperforms GlobalTrain and LocalTrain

Such scenarios do exist. As shown in the left panel of Figure, 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.

Perform experiments with varying levels of heterogeneity

We 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.

Perform experiment with natural partitions

Thanks 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, 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.

[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.

[2] Duan M, Liu D, Ji X, et al. Fedgroup: Efficient federated learning via decomposed similarity-based clustering. IEEE SustainCom, 2021: 228-237.

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.

The practical implication on the choice of $\lambda$

For 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$.

As Figure 1 (See detail in Figure) 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.

As a direct implication, shown in the left part of Figure 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.

The potential solution of $\lambda$ in practice

For 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, 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.

For 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.

the definition of personalization

In 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.

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.

The summarized key takeaway as our main claim

From 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.

From 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.

By 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 and the response to reviewer Krd5 for a detailed description).

Unsure how Algorithm 1 differs from the existing algorithms

The 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.

The Difference between Algorithm 1 and Algorithm 2

Algorithm 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.

The models and datasets are all too outdated

Thank 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, 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.

The performance is lower compared to other algorithms used for comparison, raising concerns about its practicality

We 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.

Beyond 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). For practicality, when the optimal $\lambda$ is unknown, we provide tuning guidance (See Right of Figure): 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).

We thank the reviewer for the insightful and constructive comments. Below, we provide our detailed responses to each point.

The Structure of the Theoretical Proof

We 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.

Significance of Experiment, Validation of Theoretical Claims, and Comparison with Existing Algorithms

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. 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:

$\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.

$\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.

$\bullet$ Trade-off: the trade-off characterized in Corollary 3 is verified: increasing the personalization degree reduces communication cost but may hurt statistical accuracy.

For 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. This provides a tuning guidance for personalization to utilize the tradeoff. As Right of Figure 3 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.

The communication cost and approaches with compressed gradients

We 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.

Compare to other work in Table 1, but use different variables. So the comparison is difficult, and it's unclear for the conclusion

The 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.

Focuses on a basic algorithm, omitting others that might influence communication costs per round

The 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.

Typo error

Thank you for pointing this out. We will carefully proofread the manuscript and correct all typos in the revised version.

We hope our responses address your concerns.

[1] Koloskova A, Loizou N, Boreiri S, et al. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates[J].

[2] Hanzely F, Hanzely S, Horvath S, et al. Lower Bounds and Optimal Algorithms for Personalized Federated Learning[J]. 2020.

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.

The concern raises for the definition of parameter space

A 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].

Experiment with strongly convex and discuss the condition number -- least square problem, vary the choice of condition number, examine both communication and computation

We 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 and Figure2 for detailed experimental results.

As 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))$.

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

Establishing 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 highly 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.

[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.

[2] Duan Y, Wang K. Adaptive and robust multi-task learning. The Annals of Statistics, 2023, 51(5): 2015-2039.