Bayesian Coreset Optimization for Personalized Federated Learning

How expensive it is to calculate the coreset samples/weights? Is there any empirical runtime results?

Our approach to computing coreset samples/weights is exceptionally cost-effective, thanks to the utilization of accelerated iterative hard thresholding in the coreset—an incredibly efficient method for rapidly determining coreset weights. Although we haven't conducted explicit runtime experiments for coreset sample weights, we've assessed the overhead cost in terms of computation, revealing an average of only 0.001 seconds per round with a maximum of 10 iterations for coreset computation (which is ideal due to early convergance in coreset weights) per round. Over 200 rounds, this results in an additional overhead cost of just 0.2 seconds compared to random sampling.

We look forward to suggestions regarding details to any additional specific runtime experiments that the reviewer would like us to try out.

 How is $\hat{\pi}$ defined in Eq. (3) and (4)?

We have defined $\hat{\pi}$ as the weighting distribution that has the same support under an embedding Hilbert space as the true posterior $\pi$, for which we consider an L2 norm as the distance metric between the client's overall data likelihood and its corresponding coreset weighted data likelihood.

 Some typo: first sentence in section 3.2 is incomplete. Different places for \hat notation in $q^i(\theta, w)$, on $q$, or $q^i$, or $q^i(theta, w)$.

Thank you for your careful inspection. We have identified this and similar places if any and have fixed the same in our revised version. Additionally regarding the notation for hat notation, $q^i(\theta, w)$ we have chosen to keep it consistent to $\hat{q^i}$. We have identified the sections where there is this notation inconsistency like in Section 4 and Section 6 of the main paper and have fixed them in our final revision. There are currently some portions in the supplementary which we are converting to a consistent notation for the hat operator and which will updated in our upcoming rebuttal revision.

We hope that the rebuttal clarifies the questions raised by the reviewer. We would be happy to discuss any further questions about the work, and would appreciate an appropriate increase in the score if the reviewer’s concerns are adequately addressed.

We appreciate the reviewer's time and effort in reviewing our paper on employing Bayesian coresets in federated learning. Their insightful feedback is invaluable, and we are thankful for the constructive comments provided.

We greatly appreciate the reviewer's positive evaluation of our work, particularly their recognition of the well-motivated approach in incorporating coreset optimization into federated learning. The reviewer's acknowledgment of the our proposed solid theoretical results and the optimism reflected in our empirical studies is truly motivating.

Weakness

The major weakness is the lack of convergence comparison in the empirical part. One of the major concerns in FL is the communication cost. Thus the number of iteration rounds is crucial in FL. The reviewer suggests not only including the comparison of the final accuracy under (maybe different levels, not only 50%) of sample complexity, but also including the convergence speed, i.e., the communication cost comparison.

We appreciate the reviewer's attention to the critical aspect of convergence comparison and its relevance to the communication cost in Federated Learning (FL). While we may have already provided in our theoretical results the convergence rate achieved in the case of our method which is in order of logarithmic bounds of the coreset size $k$ and thereby much faster than full data training, we also get better convergence as compared to random sampling (as indicated in Fig 3). In addition to these, we update on our empirical results to include different subset sample sizes along with their communication cost (total no. of communication rounds) as follows.

In Appendix Section 10.2 we are including new results to show case the total number of communication rounds (where under each setting where we are considering different coreset subsample sizes k=50,30,15,10) which is indicative of the convergence of our proposed method. Empirical results shows that with significant lesser coreset subsample sizes we achieve faster convergence with less number of communication rounds , but however with lesser accuracy than that if we used a larger coreset size or full data training which is as expected.

Table: Comparative results of test accuracies across different coreset sample complexity

We are deeply grateful to the reviewer for the positive support for our paper and the increment in score. We would appreciate the reviewer's support for acceptance of the paper.

The contribution on the coreset construction is limited. Although the authors introduce a new coreset objective, they do not provide sufficient NEW optimization techniques for the new objective. I could only identify some techniques borrowed from previous work.

We appreciate the reviewer's feedback. It is essential to emphasize that our primary contribution lies not in introducing new optimization techniques for the Bayesian Coreset construction but instead, our innovation centers around proposing a comprehensive algorithm and corresponding optimization strategies for a common unifying framework that governs two distinct optimization problems at hand. This approach leads to a model-dependent coreset sampling technique (in this case the model being trained under a personalized federated learning setup) i.e. along with the model training for federated learning, the coreset weights are also learnt dynamically for each client, which is a novel aspect of our contribution. While drawing inspiration from previous work is a common practice, our work's strength lies in the integration and adaptation of these techniques to address the challenges posed by our unique framework. In particular for bayesian coreset optimization problem, we propose a novel objective loss in Eq 9/8 on top of which we apply Accelerated Iterative Hard Thresholding. It's noteworthy that while AIHT is an efficient optimization strategy in its own right, our emphasis is not on its intrinsic properties. Rather our proposed optimization objective stands out for its considerable complexity and to address the same, we employ optimization strategies tailored to its nuances, such as the use of AIHT. Detailed insights into this choice are provided in the Supplementary section proofs, affirming our confidence in the appropriateness of this approach.

  In my opinion, the primary contribution of this paper is the modified objective (eq. 9) tailored to personalized federated learning. However, the advantages of this modified objective are not adequately elucidated in the current presentation.

We appreciate your recognition of the main contribution being the modified objective function (Eq. 9) tailored for personalized federated learning. Your feedback on the need for a more thorough elucidation of the advantages is duly noted. In Section 3.2, we delve into the rationale and motivation behind our proposed approach, offering a more comprehensive understanding of the modified objective's benefits. Additionally, we have conducted new experiments and updated our explanations in response to Question 2 under Questions, specifically addressing the advantages of the modified objective. This enhancement aims to provide a clearer and more detailed exposition of the strengths associated with our proposed contribution.

We extend our gratitude to the reviewer for dedicating time and effort to assess our paper on the utilization of Bayesian coresets in federated learning.

We appreciate the reviewer's recognition of the innovation in integrating Bayesian coresets framework within the federated learning setting in our paper. The reviewer's positive assessment of this aspect is encouraging, and we are pleased that they find our approach to be innovative. We are equally appreciative of the reviewer's acknowledgement for our novel research proposal and new ideas in this space which we believe will be significantly beneficial to the community.

Now, we go forward to clarify some of the questions raised by the reviewer.

Weaknesses

The paper's content is a bit bloated, and the use of notations can be messy. For instance, sections 3.2 and 4 could be condensed to make them more concise. Additionally, there is potential to simplify the formulaic aspect.

We thank the reviewer for their valuable feedback and insights on the paper's content and notations. In response, we have streamlined and condensed sections 3.2 and 4 to enhance conciseness without compromising the clarity of our presentation, which has been reflected in our updated rebuttal version. We look forward to the reviewer's suggestions in understanding which other specific portions can be further simplified to improve upon our current draft.

It would be beneficial if the author could emphasize their novel contribution, distinguishing it from the techniques previously proposed by others. Currently, these ideas seem to be mixed within the intricate details of the interpretations.

Our primary objective in this proposal is to enhance the efficiency in Federated Learning training via utilizing a fraction of the original data at each client while maintaining near-optimal accuracy, along with minimally possible communication cost. Our proposed theoretical findings showcase that model trained on a client's coreset sample size weighted data show faster convergence rate than in the case when trained fully on the entire training data.

Both Bayesian Coreset Optimization and Federated Learning Optimization problems are two different orthogonal and independent problems. Considering their both distinct challenges, we aim to infuse the two optimization framework in one single unified cohesive framework such that the coreset optimization problem can strategically pick data points for each client in a model dependent manner, i.e. without facing too much penalty in the model training under Federated Learning setup. As of now, to the best of our knowledge, this specific problem remains largely unexplored. Remarkably, there is a significant gap in the existing research landscape concerning subset selection or coreset-based strategies within the context of Federated Learning, with a conspicuous absence of theoretical frameworks in this domain.

Crucially, our work is unique in addressing the absence of research on subset selection or coreset-based strategies within Federated Learning setup and theoretical contributions along with empirical results in terms of near optimal performance under data scarcity setting accompany our contributions.

Lastly we also showcase its applicability in medical domain scenario via medical datasets where data scarcity remains a huge problem and how our proposal can alleviate the same.

 The overall architecture, as well as certain smaller techniques and theoretical analysis methods, seem to be largely derived from previous work.

We thank for the reviewer's feedback in this aspect. However, we respectfully assert a differing viewpoint. While building upon prior research to establish a robust foundation, our contribution is distinctive in its innovative synthesis and adaptation of Bayesian Coresets and Personalized Federated Learning frameworks. The fusion of these domains creates a novel architecture of its own as it can be seen in Algorithm 1 with unique optimization objectives, thereby further leading to new theoretical formulations and findings, as evidenced in our Theoretical Analysis and extensive novel formulations in the Supplementary (Section 9 Lemma 1, Proposition 1, Proposition 3, Proposition 4. ). We further refine and extend these objectives to enhance performance and efficiency. We firmly believe that the synergy of existing knowledge with our novel contributions significantly strengthens the overall impact and applicability of our work. We aim to further clarify certain aspects of the above thread with specific instances as we go forward.

Questions

  What is the benefits to apply coreset in the personalized federated learning? I think one of the most important is that it can reduce the communication complexity. It would be valuable to investigate and quantify the extent to which the coreset approach reduces communication complexity in the specific optimization task addressed in this work. This can be done theoretically, by providing a complexity formula, and practically, by presenting numerical results from experiments that show the reduction in communication complexity achieved.

We value the reviewer's input on comprehending the computational complexity and the effectiveness of our approach in this context. Consequently, we perform an analysis of communication complexity to assess the total number of communication rounds required for full convergence across various coreset subsample sizes. We present our results as follows (Additionally we have included these results under Supplementary section 10.2)

Dear Reviewer QB83,

We appreciate your helpful feedback and suggestion towards the importance of testing across multiple communication rounds threshold. We are therefore reporting new results on Test accuracy coresponding to the settings where only a limited number of communication rounds are now allowed (limited communication rounds settings 15,25,40 and 70 across all 3 datasets and for different sample subset size threshold).

This is in addition to the previous results as requested https://openreview.net/forum?id=uz7d2N2zul&noteId=dkzGM5rRfF where we are not considering any limitation on the number of communication rounds.

We hope that the rebuttal clarifies the questions raised in this aspect.

Thank you for your detailed response. I believe that the coreset optimization offers advantages in terms of the communication complexity. And the additional experiments indicate that the coreset has better performance than random sampling. However, the comparision to the full data is not very competitive since the sampling size is of the same magnitude as the full data, which is also mentioned by other reviewers. The authors point out that the coreset method leads to smaller communication rounds. Therefore, i would like to see the performances of the full data and coresets of varying sizes in the case where the number of communication rounds is limited to different thresholds. It would be valuable to assess the advantages of coresets in scenarios where only a limited number of communication rounds are allowed. If such advantages are demonstrated, I would be inclined to raise my rating accordingly.

Dear Reviewer QB83,

We deeply appreciate the increase in score and yours positive acknowledgement on the concerns raised earlier in terms of the motivation for our framework and experimental analysis in efficiency and outperformance over random sampling.

We would like to point our here as well, that when we considered around 50% of sample size, that leads to around half the chunk of the training data that is lost. We have further decremented it to 10% data (i.e. only considering 10% of the original training size). In any case when we train on only a few samples as opposed to the entire training set we would expect less accuracy. 10% , 25% and 40% and 50% data are significantly smaller chunks of our original training data and hence it is imperative that we have a low performance as compared to full data training. In all these cases the sample size is very much less in the order than that of training set (even in the case of 50%).

Our main experimental contribution is to show case the utility of coreset optimization in the case of Bayesian-PFL framework over random sampling of training data points or even applying popular submodular function based subset selection strategies where we get very less significant drop in accuracy (achieve near optimal accuracy as compared to the baselines).

Not a question but a suggestion. Algorithm 1 is not easy to follow for anyone unfamiliar with existing work or similar algorithms. How exactly is the coreset getting constructed? It would be good to give a high-level description of the same.

In Algorithm 1, our approach involves evaluating the client side objective function both the full data-based likelihood and the coreset weighted likelihood for each client. Subsequently, we calculate the objective function using Equation 8 ( now changed Eq number due to revised manuscript). To compute the coreset samples, we employ the highly effective Accelerated IHT algorithm atop this objective function. Supplementary Section 10.5 provides comprehensive details on the Accelerated IHT algorithm for a deeper understanding of its application in our methodology.

We hope that the rebuttal clarifies the questions raised by the reviewer. We would be happy to discuss any further questions about the work, and would appreciate an appropriate increase in the score if the reviewer’s concerns are adequately addressed.

Questions

Why the prior in equation 1 is replaced by *z* in eq.6 - the modified client-side objective. Please clarify.

Thank you for your inquiry regarding the substitution of the prior in Equation 1 with 'z' in Equation 6. In Equation 1, we initially introduce the concept of a prior distribution when formalizing the client-side objective. For the sake of clarity and ease of understanding, we denote this prior probability distribution as $\pi$ as it represents a more nuanced notation to indicate probability and also as it encompasses additional terms such as $\pi(\theta|D)$. In Equation 6, we streamline and simplify the representation while retaining the essence of the prior distribution in a more concise form using z. We have also adequately defined after the equation to resolve any confusion for the same.

The subsample size is 50%. Is it not quite large? Does it give significant computational time benefits when compared with full data? Other than figure 3, there are no experiments mentioning computational efficiency.

We do agree that taking subsample size = 50% can be considered somewhat large, but at the same time dropping too many data points may also result in degradation in performance (accuracy) irrespective of what sampling strategies we use. Hence we thought 50% to be a respectful threshold where we can measure the effectiveness of our proposed approach for maintaining near-optimal performance as compared to other baselines. Keeping in consideration the importance of studying across different thresholds we have included some of the baseline comparisons on less percentage data as follows.

In Appendix Section 10.2 we are including new results to show case the total number of communication rounds (per setting where we consider different coreset subsample sizes k=50,30,15,10) which is indicative of the convergence of our proposed method. Empirical results shows that with significant lesser coreset subsample sizes we achieve faster convergence with less number of communication rounds but with lesser accuracy than that if we used a larger coreset size or full data training. Table: Comparative results of test accuracies across different coreset sample complexity

We sincerely appreciate the time and effort that the reviewer has invested in reviewing our paper on utilizing Bayesian coresets in a federated learning setting. The reviewer's insightful feedback is invaluable to us, and we are grateful for the constructive comments that they have provided.

Firstly, we are pleased to hear that the reviewer has found the paper to be well-written and acknowledges its potential significance to the community given the lack of such work in this space. Secondly we are thankful to the reviewer for acknowledging the thoroughness of our comparative analysis and theoretically motivated framework and that they found our method's performance commendable across a variety of scenarios, especially when benchmarked against both federated learning algorithms and diverse sampling strategies. The reviewer's positive assessment encourages us and reaffirms the effectiveness of our proposed approach.

Weaknesses:

 I am not sure what is the challenge in incorporating the Bayesian coreset framework in federated learning setting. It would be better to explain clearly why this is a significant contribution. Both the algorithm and proof techniques appear to be heavily inspired from Zhang 2022b. The only modification seems to be use of Bayesian coresets.

One of the core problems that we try to address here is how to achieve efficiency in training in a Federated Learning setup using only a fraction of the original data at each client yet achieving near optimal performance in terms of accuracy (theoretical results on our logarithm bounded convergence rate using coreset indicates better convergence than full training while empirical results across a diverse set of baselines including diversity based subset selection techniques show promising results in terms of accuracy). Both the Bayesian Coreset optimization framework and Personalized Federated Learning framework which in itself involves a bilevel optimization problem are two separate entirely different orthogonal problems.

Our goal in this proposal is thus to bridge the two towards a common optimization framework whereby we can utilise a Bayesian coreset framework for strategic selection of data points at each client level and at the same time we do not need to pay for a bigger penalty while solving the Federated Learning optimization problem. Both these problems represent independent optimization challenges that need to be addressed concurrently. The difficulty arises when striving to learn the coreset in an optimized manner that minimizes the overall penalty incurred while training within the Federated Learning setting. Hence our work focuses on seamlessly interleaving these two optimization frameworks into a single, cohesive framework, introducing novel optimization formulations as evident in Eq 8 and 7 (updated equation numbers due to manuscript revision), along with corresponding strong theoretical guarantees. Importantly, our contribution addresses a gap in the existing literature. To the best of our knowledge, this specific problem has not been thoroughly explored. There is a notable absence of research on subset selection or coreset-based strategies within a Federated Learning context, let alone the formulation of theoretical frameworks in this domain.

Additionally, as an application setting we also showcase the usefulness and applicability of our method on real-world medical datasets where in many cases there is a severe dearth of medical data. To address the challenges in infusing the two optimization frameworks together and propose new findings on top of it, we draw upon some of the proof techniques from papers like Polson & Roˇckov ́a (2018), and others, one of them being Zhang 2022b, particularly due to the similarities observed in Eq. 1. We utilize certain existing lemmas and theorems, on top of which we provide novel theoretical formulations and new results as seen in theorem 1 and theorem 2, and their accompanied proofs in Supplementary (Section 9 Lemma 1, Proposition 1, Proposition 3, Proposition 4. ) which are our primary contributions.

[1] Nicholas G Polson and Veronika Roˇckov ́a. Posterior concentration for sparse deep learning.

 There are minor grammatical errors. Please do a grammar check.

We thank the reviewer for their careful inspection. We have made a thorough proofread pass and have identified the specific areas and have fixed them in our recent revision.