The Effect of Personalization in FedProx: A Fine-grained Analysis on Statistical Accuracy and Communication Efficiency

Response to Technical Challenges and Contribution

Prior work [1] established the rate of FedProx through algorithmic stability, and to 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, e.g., [5-7]. 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 $\lambda$, as detailed in Lemma 1. This allows us to show for large $R$, a small $\lambda$ can be chosen to yield rate $O(1/n)$ and match one of the worst cases in the lower bound. For the complementary case $R \leq 1/\sqrt{n}$, we leveraged the GlobalTrain solution $\widetilde{\boldsymbol{w}}\_{GT}$ as a bridge and proved the solutions of FedProx to $\widetilde{\boldsymbol{w}}\_{GT}$ are bounded by a term inversely proportional to $\lambda$ (cf. Lemma 4 and Eq. (49) in the Appendix A.3), implying that they can be made arbitrarily close to $\widetilde{\boldsymbol{w}}\_{GT}$ by setting $\lambda$ small. This, together with the rate of $\widetilde{\boldsymbol{w}}\_{GT}$ as proved in Lemma 5, yields a rate of $O(1/N + R^2)$. 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 FedProx is minimax optimal, are the technical novelties of this proof.

Response to Typographical Errors:

We sincerely thank the reviewer for pointing out typos, all of which have been corrected in the revised manuscript.

We hope the above clarifications address the reviewer’s concerns, and we remain happy to provide further details if needed.

---

[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] Niu C, Wu F, Tang S, et al. Billion-scale federated learning on mobile clients: A submodel design with tunable privacy[C]//Proceedings of the 26th Annual International Conference on Mobile Computing and Networking. 2020: 1-14.

[3] Chen D, Gao D, Xie Y, et al. Fs-real: Towards real-world cross-device federated learning[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3829-3841.

[4] Chen D, Gao D, Xie Y, et al. Fs-real: Towards real-world cross-device federated learning[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3829-3841.

[5] Fallah, A., Mokhtari, A., and Ozdaglar, A. (2021). Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34, 5469-5480.

[6] Denevi, G., Ciliberto, C., Grazzi, R., and Pontil, M. (2019, May). Learning-to-learn stochastic gradient descent with biased regularization. In International Conference on Machine Learning (pp. 1566-1575). PMLR.

[7] Chen, J., Wu, X. M., Li, Y., Li, Q., Zhan, L. M., and Chung, F. L. (2020). A closer look at the training strategy for modern meta-learning. Advances in neural information processing systems, 33, 396-406.

We thank the reviewer for their insightful comments and detailed feedback. Below, we address each of the specific concerns:

Response to Statistical Error Bounds and Comparisons:

1. Inclusion of optimization error: We would like to point out that the comparison with [1] is fair: the first part of this paper derives the statistical convergence rate of the estimator. In Table 1, we provided a comparison with [1] as given by Theorem 11 and 12 therein (cf. Eqs. (28) and (29)). The analysis in [1] relies on the algorithm update specified by Algorithm 2 to obtain the rate of the estimator, whereas our analysis directly targets the problem formulation and is free from the choice of algorithm employed to solve the problem. In other words, our result ensures that any algorithm solves the FedProx problem exactly and would attain the rate given by Theorem 1. The second part of the paper provides the algorithmic convergence rate. Corollary 1 shows a solution that is $\varepsilon$-close to the FedProx minimizer can be obtained with $\mathcal{O}(\kappa \frac{\lambda+\mu}{\lambda+L} \log\frac{1}{\varepsilon})$ communication rounds and $\mathcal{\widetilde{O}}(\kappa \log\frac{1}{\varepsilon} )$ gradient evaluations. Note that our step size is set to a constant, and the rate is linear. If we combine the two parts using the simple relation

$$\\|\boldsymbol{w}\^{(g)}\_t - \boldsymbol{w}\^{(g)}\_\*\\|\_2 \leq \\|\boldsymbol{w}\^{(g)}\_{t}- \boldsymbol{\tilde{w}}\^{(g)}\\|\_2 + \\| \boldsymbol{\tilde{w}}\^{(g)} - \boldsymbol{w}\^{(g)}\_\*\\|\_2, \quad \forall t,$$

we can immediately obtain the conclusion that a solution $\boldsymbol{w}\^{(g)}\_{T}$ of the same statistical rate as $\boldsymbol{\tilde{w}}\^{(g)}$ can be attained if the communication round $R \gtrsim \kappa \frac{\lambda+\mu}{\lambda+L} \cdot \log\frac{1}{\\| \boldsymbol{\tilde{w}}\^{(g)} - \boldsymbol{w}\^{(g)}\_\*\\|\_2}$ and the total gradient evaluation $T \gtrsim \kappa \cdot \log\frac{1}{\\| \boldsymbol{\tilde{w}}^{(g)} - \boldsymbol{w}^{(g)}_*\\|\_2}$. The complexity is better than that provided in [1], where a bounded gradient assumption is imposed, the step size is diminishing, and the computation complexity is sublinear.

2. Definition of statistical accuracy: Indeed, we defined the statistical accuracy using model difference rather than excess risk. However, the two error measures are comparable under strong convexity. Take the error of $\widetilde{\boldsymbol{w}}^{(i)}$ as an example. Our error measure is $\\|\tilde{\boldsymbol{w}}\^{(i)} - \boldsymbol{w}\_{\star}\^{(i)}\\|\^{2}$ whereas the individualized excess risk (IER) defined in [1] is $\mathbb{E}\_{z\_i} \left[ \ell(\tilde{\boldsymbol{w}}\^{(i)}, z\_i) - \ell(\boldsymbol{w}\_\star\^{(i)}, z\_i) \right].$ By strong convexity and the optimality of $\boldsymbol{w}\_\star\^{(i)}$ we have the error bound $\mathbb{E}\_{z\_i} \left[ \ell({\boldsymbol{w}}\^{(i)}, z\_i) - \ell(\boldsymbol{w}\_\star\^{(i)}, z\_i) \right] \geq \frac{\mu}{2} \\| {\boldsymbol{w}}\^{(i)} - \boldsymbol{w}\_{\star}\^{(i)} \\|^2$ hold for any $\boldsymbol{w}^{(i)}$. Furthermore, assuming smoothness we have $\mathbb{E}\_{z\_i} \left[ \ell({\boldsymbol{w}}\^{(i)}, z\_i) - \ell(\boldsymbol{w}\_\star\^{(i)}, z\_i) \right] \leq \frac{L}{2} \\| {\boldsymbol{w}}\^{(i)} - \boldsymbol{w}\_{\star}\^{(i)}\\|^2$. Under our common problem assumptions, the two measures are equivalent if $\mu$ and $L$ are treated as constants. In Table 1 of the manuscript, we did a fair comparison by transforming their result into our metrics $\mathbb{E}\\|\boldsymbol{w}_{\star}^{(i)} - \widetilde{\boldsymbol{w}}^{(i)}\\|^2$.

3. Improved rate: As noted by the reviewer, our original result already improves over that in (1) by $O(1/\sqrt{m})$ in the case $R \leq \frac{1}{m\sqrt{n}}$. The improvement is not minor since in federated learning settings where $m$ can be very large. In [4], the cross-device federated learning considers the number of clients as $10^5$. In addition, we proved this rate without assuming the boundedness of the loss function and compactness of the domain (cf. Assumption A (a) and (b) in [1]).

Minimax Optimality: In the revised manuscript, we have improved our bounds to $O\left(\frac{1}{N} + R^2 \wedge \frac{1}{n}\right)$, which matches the lower bound established in [1]. To the best of our knowledge, our work is the first to establish the minimax optimality of FedProx.

Dear Reviewer han2,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

We sincerely thank you for your comments, and greatly appreciate your recognition of the theoretical contributions and the validation provided through our experimental results.

We have carefully considered your suggestion regarding figure sizes and have adjusted both of them in the revised version to improve readability and enhance visual clarity.

If there are any specific aspects of the manucript that require further clarification, we are more than happy to provide additional explanations. Please feel free to highlight any areas of concern, and we will do our best to address them and ensure our contributions are presented as clearly and precisely as possible.

Weakness 2 Lack of clarity in the description and analysis of the experiments

We thank the reviewer for the comment. We have updated the descriptions to accurately reflect the figures and provide more precise interpretations. We have revised the text on Lines 1664 to 1673 to clearly indicate that Fig. 4(a) displays accuracy variation and to ensure consistency between the figure and the main text. We have also reviewed the entire experimental section to improve clarity and ensure all references are accurate.

Weakness 3 Extended to partial participation of clients

Once the regularization strategy for $\lambda$ under data heterogeneity is determined, $\lambda$ remains fixed, and the optimization objective together with the estimators $\\{\widetilde{\boldsymbol{w}}\_i\\}\_{i = 1}\^m$ are fully defined by (1). In other words, the choice of $\lambda$ depends solely on the problem parameters, and the statistical error holds universally for any algorithm that solves the FedProx problem, regardless of whether client sampling is employed. On the computation side, our algorithm that uses full gradient update and full client participation to compute $\\{\widetilde{\boldsymbol{w}}\_i\\}_{i = 1}\^m$ as the solution to (1) can potentially be extended to client partial participation. If the participation is modeled as uniformly at random per communication round, we anticipate the convergence analysis to be similar to the extension from using full gradient update to unbiased mini-batch stochastic gradients. To validate the performance empirically, we report the statistical accuracy of the proposed algorithm under varying levels of client participation per round on the MNIST dataset in the table below.

Other participation patterns, such as cyclically or even arbitrarily but just requiring all clients not to leave the system permanently, would require a different technical analysis or algorithmic design to avoid the bias introduced by partial participation.

We greatly appreciate the reviewers’ feedback. We have provided our responses below:

Weakness 1 Expanded experiments: additional datasets, complex models, and accuracy evaluation

We have conducted additional experiments using more diverse datasets, including CIFAR-10 and EMNIST Balanced, which cover a broader spectrum of heterogeneity levels. Furthermore, we have extended our analysis by employing more complex non-convex models, such as CNNs with different number of layers. All of the models, as the reviewer requested, are evaluated in classification accuracy instead of model's error. These new results are consistent with our theory: as $\lambda$ increases, FedProx transitions from behaving similarly to LocalTrain towards GlobalTrain. While GlobalTrain performs best in this scenario due to the relatively weak statistical heterogeneity, FedProx, with increasing $\lambda$, moves closer to GlobalTrain performance. We have included these new results below, and their corresponding analyses can be found in the revised version of the paper (see Appendix C.2).

Dear Reviewer bMut,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

We sincerely thank the reviewers for the comments. Below, we address each point in detail:

Weakness 1 Comparison with other works like Scaffold

Scaffold computes the minimizer/stationary point of the finite sum minimization problem

$$\widetilde{\boldsymbol{w}}\_{GT} \in \arg\min\_{\boldsymbol{w}} \frac{1}{m} \sum\_{i = 1}^m L\_i (\boldsymbol{w},S\_i).$$

It uses a variance reduction technique to eliminate the impact of gradient heterogeneity on the algorithm convergence, and consequently, the rate does not depend on $R$. Note the rate here is the algorithmic convergence rate, meaning how many iterations are needed to reach a solution that is $\varepsilon$-close to $\widetilde{\boldsymbol{w}}\_{GT}$. However, under model heterogeneity, $\widetilde{\boldsymbol{w}}\_{GT}$ can be far away from any of the $\boldsymbol{w}_i^\star$s and the difference does depend on $R$ (cf. Lemma 1). On the other hand, our result directly quantifies the distance of the FedProx solution $\widetilde{\boldsymbol{w}}\_{i}$ to $\boldsymbol{w}\_i\^\star$. Their difference called the statistical rate/accuracy, is minimax optimal.

We would like to clarify in this paper we are considering a personalized federated learning problem, where the major concern is the statistical accuracy for each client's model, i.e., the local statistical error specified in Line 229. Such an error would be naturally related to the statistical heterogeneity measure $R$. On the other hand, Scaffold are concerned with the statistical accuracy of the finite-sum problem and, therefore is not dependent on $R$. As the statistical problem concerned by Scaffold is different from ours, the error bound is not directly comparable.

Weakness 2 Empirical result

First we would like to note that in the original version, we have already considered both a convex setting (logistic regression) but also a non-convex setting (CNN). Thus, our analysis has already extended beyond logistic regression. We would also like to reiterate that the primary objective of our empirical study is to emphasize the role of personalization in objective (1). To this end, we primarily compare our approach with global training and purely local training under varying levels of data heterogeneity. We acknowledge that exploring other personalization methods aligned with objective (1) could provide additional insights into whether the influence of personalization is universally observed. For instance, we notice that pFedMe [2] focuses on the same objective (1) and can address non-iid data. However, the effect of personalization is not fully exploited in their work. We include their method in our numerical analysis and we refer the reviewer to Appendix C.2 for more details.

Weakness 3 Choice of $\lambda$ and contribution

We would like to clarify the contribution of this paper is primarily theoretical: providing the performance guarantees FedProx--a well-known personalized FL method. With properly chosen penalty $\lambda$, FedProx can achieve a minimax optimal statistical rate. This performance limit was unknown before, and our result improves the state-of-the-art [1] upperbound by (i) enlarging the family of applicable loss functions and (ii) obtaining a tighter rate. Indeed, the choice of $\lambda$ depends to some degree on $R$ (through the cut-off threshold). Such a dependency is intuitive as one should rely on $R$ to decide to what extent the $\boldsymbol{w}_i$s should be pulled together, and also exist in [1] as well as related works [4][5]. How to choose $\lambda$ in a purely data-driven way while not degrading the statistical rate is an important, very challenging problem. We view this as a natural next step for future work, while the current study focuses on addressing the foundational question of whether FedProx serves as an effective personalization strategy under model heterogeneity in the idealized scenario where $R$ is known.

---

[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] T Dinh, C., Tran, N., and Nguyen, J. (2020). Personalized federated learning with Moreau envelopes. Advances in Neural Information Processing Systems, 33, 21394-21405.

[3] Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. (2020). Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2, 429-450.

[4] Li S, Zhang L, Cai T T, et al. Estimation and inference for high-dimensional generalized linear models with knowledge transfer[J]. Journal of the American Statistical Association, 2024, 119(546): 1274-1285.

[5] He, Zelin, Ying Sun, and Runze Li. "Transfusion: Covariate-shift robust transfer learning for high-dimensional regression." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

Dear Reviewer KgRk,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

Dear Reviewer,

As the author-reviewer discussion period will end soon, we will appreciate it if you could check our response to your review comments. This way, if you have further questions and comments, we can still reply before the author-reviewer discussion period ends. If our response resolves your concerns, we kindly ask you to consider raising the rating of our work. Thank you very much for your time and efforts!

Noiseless setting

First, we would like to clarify that the "noiseless setting in optimization" refers to using full gradient update but not mini-batch stochastic gradient when solving the FedProx objective (1). It is not the same concept as $\rho =0$, which means the empirical loss $L_i$ is equal to the population loss. In the practical case with $\rho \neq 0$, quantifying how to choose $\lambda$ under data heterogeneity in theoretical analysis is precisely the main contribution of the paper. Under such a choice of $\lambda$, the section on the optimization provides the computation and communication complexity analysis of the proposed algorithm. In particular, our Corollary 1 shows the communication complexity is $\mathcal{O} (\kappa (\lambda + \mu)/(\lambda + L) \log 1/\varepsilon)$. We want to emphasize that this result does not "suggest setting $\lambda = 0$ to do purely local training". Instead, our point is that one must first choose the right $\lambda$ based on model heterogeneity to define the right problem to solve (whose optimal solution has high statistical accuracy), as suggested by Theorem 1, and then run an algorithm to find the solution at low costs, whose guarantee is provided by Corollary 1. Even though setting $\lambda = 0$ will require the lowest communication cost algorithmically, it is pointless if the solution generated by the algorithm is far from the ground truth.

In addition, we also want to clarify we have never claimed that extension to use stochastic gradients is trivial, but just meant to say proving convergence is potentially doable. For example, [3] considered the analysis of bilevel algorithms in the deterministic case, while stochasticity and variance reduction have been studied in, e.g., [4,5]. That said, we fully acknowledge that incorporating stochastic noise and analyzing its interaction with the deterministic part in the rate analysis requires significant effort. However, our main focus is the effect of personalization on statistical accuracy and communication efficiency. To avoid misunderstanding, we have revised the statement in the manuscript.

Question 1

In this work, we call $\boldsymbol{w}\^{(g)}\_{\star}$ the global model and defined it to be the average of the $\boldsymbol{w}\_\star^{(i)}$'s. Consistently, our analysis quantifies the difference between $\tilde{\boldsymbol{w}}\^{(g)}$, which is the solution of the FedProx problem defined by (1), and $\boldsymbol{w}\^{(g)}\_{\star}$, as a function of sample size and model heterogeneity $R$. Such a $\boldsymbol{w}\^{(g)}\_{\star}$ represents the population-level counterpart of $\tilde{\boldsymbol{w}}\^{(g)}$. Similar notation has been used in multiple prior works [1][6] for their analysis. Throughout the paper, we have never indicated that $\boldsymbol{w}\^{(g)}\_{\star}$ or $\tilde{\boldsymbol{w}}\^{(g)}$ should be "the optima of the average function". Indeed, FedAvg aims to recover the optima of the average function, which is defined as the global model therein (we denote it $\boldsymbol{w}\_{GT}\^\star$). However, it is not a consensus that the terminology ``global model'' means exclusively $\boldsymbol{w}\_{GT}\^\star$, and we have never made or used the wrong claim $\boldsymbol{w}\^{(g)}\_{\star} = \boldsymbol{w}\_{GT}\^\star$ throughout this work.

Question 2

The local models $\widetilde{\boldsymbol{w}}\^{(i)}$, along with $\widetilde{\boldsymbol{w}}\^{(g)}$ are defined as the optimal solutions to the FedProx problem (1).

We sincerely hope that the above clarifications address the reviewer’s concerns, and we would be more than happy to provide additional details if needed.

---

[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] Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. (2020). Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2, 429-450.

[3] Ji, K., Liu, M., Liang, Y., and Ying, L. (2022). Will bilevel optimizers benefit from loops. Advances in Neural Information Processing Systems, 35, 3011-3023.

[4] Dagréou, M., Ablin, P., Vaiter, S., and Moreau, T. (2022). A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35, 26698-26710.

[5] Chen, X., Xiao, T., and Balasubramanian, K. (2024). Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151), 1-51.

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

We sincerely thank the reviewer for the thoughtful comments, which have inspired us to make substantial improvements to our previous results. Our current result proves FedProx achieves minimax optimality by improving the upper bound from $O\left(\frac{1}{mn} + R^2 \wedge \frac{1}{n} + \frac{R}{\sqrt{n}} \wedge \frac{1}{n}\right)$ in the original submission to $O\left(\frac{1}{mn} + R^2 \wedge \frac{1}{n}\right)$. In addition, we have carefully refined the proofs to address concerns related to units and clarity. Below, we provide detailed responses to each comment:

Incorrect units

We first discuss this issue based on the results of our original submission. In our previous analysis, our focus was on how sample and client number affect the accuracy and considered the limit that $n$, $m$, and $R$ can go to infinity. Problem parameters such as $\mu$ and $L$ were treated as fixed constants. So when choosing $\lambda$ we did not account for the scenario mentioned by the reviewer where $\mu$, $L$, or $\rho$ are also allowed to diverge. Our original choice of $\lambda$ still makes sense if we aim to interpret the result w.r.t. $n$, $m$, and $R$. The comparison of $R$ with $1/\sqrt{n}$ is meaningful, as $1/\sqrt{n}$ represents the critical threshold where the statistical rate transitions from $R^2$ to $1/n$. This transition aligns with the point at which purely local training becomes the optimal strategy. Such a discussion is also reflected in existing literature [1]. Regarding the second sanity check, we have double-checked that the right-hand side of (4), which depends on $\rho$ through $C_1$ and $C_2$ defined respectively as $C_1 = \rho^2/\mu^2$ and $C_2 = (\frac{(1 + \sqrt{1 + 2 \mu}) \rho}{2 \mu})^2 \vee (2 \rho /\mu)$, and they do not contain any term involving $\rho^4$. Still, we appreciate the reviewer pointing it out and we take it into account in our new analysis. Such a unit issue can be addressed by a modification on the choice of $\lambda$, with the original proof staying valid and both $\lambda$ and the error bound having the correct units.

Vacuous guarantees

We appreciate the reviewer's question and the mean estimation example, which have inspired us to further improve our analysis and the result. The new version of Theorem 1 states if \lambda \geq \max \left\\{64\kappa^2L, \left(2\kappa\vee5\right)\mu \frac{2L^2R^2 + \rho^2/n}{L^2R^2+\rho^2/N}\right\\} -\mu when $R\leq \frac{1}{\sqrt{n}}$, and $\lambda \leq\frac{\rho^2}{n\mu R^{2}}$ when $R > \frac{1}{\sqrt{n}}$, then we have

\mathbb{E}\left\\| \widetilde{\boldsymbol{w}}\^{(i)} -\boldsymbol{w}\^{(i)}\_{\star} \right\\|^2 \leq \frac{C_3}{mn}+ C_4\left( \frac{1}{n}\wedge R^2\right) \quad \text{ for all }i \in [m],$$ $$ C_1 = 32\frac{\rho^2}{\mu^2}, C_2 = \big(\frac{(1+\sqrt{3})\rho}{\mu}\big)^2\vee \frac{32 L^2}{\mu^2}, C_3 = \frac{192\rho^2}{\mu^2}, C_4 = \left(\frac{\rho(1 + (4C_2+5)^{\frac{1}{2}})}{\mu}\right)^2 \vee 198\kappa^2.$$ This new upper bound is $O\left(\frac{1}{mn} + R^2 \wedge \frac{1}{n}\right)$ and matches the rate of the dichotomous strategy proposed by the reviewer across any level of statistical heterogeneity $R$. Both the choice of $\lambda$ and the error bounds have the correct units. Furthermore, we note that the rate $O\left(\frac{1}{mn} + R^2 \wedge \frac{1}{n}\right)$ is in fact the *information-theoretic lower bound* for the estimation problem (1), as established in prior work [1]. Thus, our new result demonstrates that FedProx is *minimax optimal*. We may reiterate that the key contribution of our work is analyzing the performance of FedProx, a method that has demonstrated great empirical success [2] and whose statistical guarantees were not fully understood. This is an important contribution in its own right, even though the rate matches the dichotomous strategy suggested by the reviewer. It remains an open question whether FedProx can outperform this ‘simple baseline’—a baseline that is already minimax optimal, and the point of this paper is not to prove that Fedprox must be better over the baseline. The latest work [1] provided the estimation error of FedProx under more restricted problem assumptions and is larger even compared to the result in our original submission. In [1], it was noted that the minimax optimality of FedProx was an open question (see the discussion at the end of Section 3). In this work, we addressed and closed this gap by establishing its minimax optimality. As a side note, if one seeks to understand why FedProx could be advantageous over the dichotomous strategy in practice, we provide an additional discussion and numerical comparison (See Table 4) in Appendix C.3.

Dear Reviewer iwVj,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

Area Chair

Dear Reviewer,

As the author-reviewer discussion period will end soon, we will appreciate it if you could check our response to your review comments. This way, if you have further questions and comments, we can still reply before the author-reviewer discussion period ends. If our response resolves your concerns, we kindly ask you to consider raising the rating of our work. Thank you very much for your time and efforts!

Dear Reviewer iwVj,

Since you gave the most negative review and the authors have provided detailed responses to try to address your concerns, it is very important to hear your opinions before we can recommend a decision on this paper. Please reply with whether you think the authors have addressed (some of) your concerns and whether you will keep or modify your assessment.

Thank you again.

Area Chair