Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work suggests a differentially private federated Bayesian optimization framework, which is extended Bayesian optimization to federated learning. Following the previous work [1], this work optimizes an objective in respective agents and occasionally updates the information obtained from the agents to a central server. However, [1] did not guarantee a rigorous privacy, which is the most important part of federated learning. By leveraging a differential privacy concept and distributed exploration, the authors propose differentially private federated Thompson sampling with distributed exploration (DP-FTS-DE), which theoretically guarantees a sublinear regret. Finally, the authors demonstrate that the proposed method outperforms other baselines including Thompson sampling and FTS-DE.
main_review: This paper solves an interesting topic, which can be widely adopted in a practical scenario. In particular, as a real-world problem, a federated learning scheme is able to preserve a privacy information as well as solve a target task in each agent. In this paper, from the idea of online regression with random Fourier features, it communicates the coefficients between central server and agents by incorporating the concepts of distributed exploration and differential privacy. However, I have some concerns on assumptions and numerical experiments. Please read the comments described below and provide a response in the rebuttal.

Pros

+ Interesting topic.
+ Well-written and well-organized paper.

Cons

- Limited novelty.
- Unrealistic assumptions.
- Weak numerical experiments.

Detailed Comments

1. Could you provide an intuitive explanation on subsampled Gaussian mechanism at the beginning of Section 3.3? If this is added, a potential reader would understand well about the concept of subsampled Gaussian mechanism.
2. I do not want to point out the novelty of this work directly, but the components in the proposed method have been already suggested in the existing studies [1, 2]. If I misunderstood, please let me know in the rebuttal.
3. Importantly, I think the choice of $1 - p_t$ is unrealistic. If $1 - p_t \in \mathcal{O}(1/t^2)$, Line 7 of Algorithm 2 would not be operated with a very high probability after a few iterations. This is not the authors' intention for the proposed method. Moreover, it implies that the regret bound becomes almost same to the standard GP-UCB.
4. Related to the comment above, in the experiments, the authors choose a slowly decreasing $1 - p_t$ such as $\mathcal{O}(1/\sqrt{t})$. Such a choice makes a regret bound not hold. I would like to be informed about any thoughts on this.
5. For Figure 3, Bayesian optimization with 60 iterations is not enough, because they do not converge yet.

Minor issues

* Could you provide a reason why there are the experiment results before 0 iteration in Figure 2?
* For Algorithm 2, the part from Line 4 to Line 7 should be declared by if-else statement.
* In Line 84, what is $\mathcal{R}$? It seems like $\mathbb{R}$. There exist wrong notations like this. Please fix them.
* In Line 18, DNN should be DNNs.
* In Line 99, RFF should be RFFs.

[1] Z. Dai, K. H. Low, and P. Jaillet. Federated Bayesian optimization via Thompson sampling. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, Virtual, 2020.

[2] Z. Ji, Z. C. Lipton, and C. Elkan. Differential privacy and machine learning: a survey and review. arXiv preprint arXiv:1412.7584, 2014.
limitations_and_societal_impact: I do not have any comments on limitations and societal impact. Please see "Main Review" for the detailed reviews.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper prosed the first algorithm with a rigorous guarantee on the user-level privacy in the federated bayesian optimization setting. The proposed method integrated differential privacy federated Thompson sampling. Many theoretical insights of the privacy-utility trade-off are given, and the performance of proposed algorithm are validated on real-world experiments. 

main_review: Strength:
1. The paper are well written and presented, and the problem is very important. 
2. The technical parts seem solid. It is good to see that a differentially private federated learning algorithm can handle the heterogeneity of local devices.

Weakness:
No major weaknesses. This is a strong submission.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a differentially private FTS with distributed exploration. The contributions include (1) the development of the algorithm; (2) theoretical analysis of its privacy-utility tradeoff; and (3) experimental evaluation. 
main_review: Pros:
- the paper is nicely structured and well-written
- theoretical analysis for the proposed algorithm on utility is solid
- empirical study is presented to validate the effectiveness of the proposed algorithm

Con:
- the proposed algorithm introduces some additional hyperparameters like #/ exploration regions, exploration temperature on top of DP-FTS. They need to be tuned to get good performance. but the tuning of these parameters will introduce additional privacy loss. It'll be good if the authors can provide a discussion of tuning the parameters and their privacy implications.

limitations_and_societal_impact: Yes, the authors addressed the limitations
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an algorithm for performing Federated Bayesian Optimisation using differential privacy—differentially private federated Thompson sampling. Differential Privacy is maintained by aggregating local updates using a subsampled Gaussian mechanism. Additionally, distributed exploration is applied to warm-start the algorithm, and allows for more efficient exploration, especially in the earlier iterations. 

One sentence summary: the authors propose DP-Federated BO using Thompson sampling with a distributed initial random search. 
main_review: Please note that I have organised my points in this review by category, and also whether they are a strength of a weakness of the work. Points marked * I deem to be especially important, and should be addressed in the author response if the authors would like me to reconsider my score.

EDIT: I have increased my score to 7 based on the authors response. 

---
- Originality (O)
    - (+O1) The authors primarily combine known techniques in the DP and BO literature to propose this algorithm. Of course, some modifications are necessary. The combination of these ideas is well executed, and a strength of the paper. 

---
- Quality (Q)
    - (+Q1) I was impressed by the theoretical analysis of the regret of the DP-FTS-DE algorithm. The conclusions from the theory match intuition, and it is reassuring to see this reflected in the theory. Note that however I was unable to verify the "correctness" of the theory, because it is far from my area of expertise.  
    - (Q2) The analysis assumes that all objective functions have a bounded normal induced by the RKHS associated with kernel k. Please comment on whether this is a key limitation of the work. 
   - (Q3) The theoretical analysis hinges on d_n, which quantifies the similarity in the objective functions between clients. Is this known in practice? We are performing Bayesian Optimisation because function evaluation is difficult. 
    - (-Q4)** There is insufficient discussion of the threat model and the specific setting that this algorithm can be applied in. Specific questions that I have regarding the settings are: (i) which data is considered private, and which data is considered public? Or is all data considered public (ii)** i assume that leaking f_i(x) would leak data relating to client i only, because otherwise the analysis of the algorithm would be incorrect. For example, if f_i(x) is the validation accuracy when training on the data from all clients (and each client has the same f_i(x)), when releasing f_i(x) actually leaks information about **all** users, rather than just one, and the true privacy protection is significantly diminished. Perhaps I missed discussion of this point, but I believe that the assumptions made are critical. (iii) Is it assumed that every client is able to update and send parameter updates simultaneously? Often in FL, clients have different network capabilities. (iv) Who is trusted, and who is not trusted? Line 148 "FTS requires an agent to receive all vectors from other agents so the transformations requires by the general DP framework cannot be easily incorporated". This is assuming that other clients are not trustworthy; this should be made clear in the problem setting. (v) What are adjacent datasets considered to be, in terms of defining DP? Considering the algorithm description, adjacent datasets seem to be datasets where all of the data on a specific client varies. This might be excessive, if for example, a "client" is actually a hospital, and the data at that client is actually from several different individuals. 
    - (-Q5)* Information from different clients is combined using a weighted average, where the weight is determined by whether a particular client was "assigned" an area or search initially. The weighted average does not seem principled to me. How would it compare to, for example, using a Gaussian Process on all of the clients data? How are we accounting for how each client has their own f_i, and thus the value of f_i at client m may not be representative of the the value of f_i at client n. Ideally we would allow for uncertainty in how the values of f may different across clients. 
    - (-Q6) Proposition 1 shows that the algorithm is DP. However, I think it would be better to make clear exactly how the privacy loss was computed (i.e., the moments accountant), rather that state a theorem that is effectively identical to that of Abadi et al. 
    - (-Q7)* The authors have shown that the algorithm is asymptomatically no regret. As I understand, this means that, over time, the algorithm will select closer to optimal actions. However, the constants matter. What happens if the f_i are chosen very different for each client? While this algorithm is asymptotically no-regret, how does it compare to simply performing local Bayesian Optimisation for each client? This could be evaluated experimentally, by adding a synthetic example where the f_i are "significantly" different across clients, and comparing local BO to federated BO. 
    - (Q8) The first term in Theorem 1 is sub-linear for the squared exponential kernel (see Line 253). Are there kernels for which this term is not sublinear?
    - (+Q9) As I understand, the value of distributed exploration is particularly high in the few iteration regime, such as when there is a strict privacy budget. Using distributed exploration in the differential privacy context is a good combination. 
   - (-Q10)* In Figure 3, only 60 iterations are run, even though the algorithms have clearly not converged. Why did you stop at 60 iterations? The experiments should be run with more experiments. 
   - (-Q11)* I was disappointed to see that authors did not engage with the limitations of the work. Perhaps thinking carefully about the specific context this algorithm can be applied in (See Q4) may reveal some limitations e.g., certain settings that the algorithm cannot be applied. 
---
Overall, I believe improving the clarity and precision of the text in the paper would greatly benefit the submission. 

- Clarity (C)
    - (-C1) Additional clarity could be provided about the Federated Bayesian Optimisation setting. For example, Introduction line 20-22 "BO has recently been extended to .... without requiring them to share their raw data" could be interpreted as parallel Bayesian optimisation, where there is only one single objective function. 
    - (-C2) The authors write (lines 43/44) that "DP-FedAvg guarantees that an adversary ... cannot infer whether data from a particular user has been used by the algorithm", is too strong. DP-FedAvg often uses epsilon, delta differential privacy, and therefore there is a delta chance (ie non-zero) of their being potentially catastrophic privacy breach. 
    - (-C3)* The authors write that "every agent can explore the local sub-region more effectively because its GP surrogate can model the objective function more accurately in a smaller local-subregion" (lines 60-62). My understanding of reference [16] is that better local perform is due to being able to fine-tune parameters locally i.e., for each subregion. Is that what is happening here? Or does this approach ensure better that the full search space is explored e.g., by having users not search in the same area. Please clarify. Later, the authors write "smaller sub-regions are easier to model for the GP surrogate, and hence can be better explored" (line 312/313)—is this specific to GPs? Is this some property of inference?.  
    - (-C4) Line 82 "An interesting trade-off between privacy and utility in real-world applications"—what does this mean? 
    - (-C5) The algorithm suggested in the paper builds heavily on the Federated Thompson Sampling algorithm, but this algorithm is not explained in detail in the background section. Ideally, much more space would be devoted to this prior work. For example, intuition on why randomly sampling the optimal point from another agent is a good idea. 
    - (-C6) As I understand, the privacy loss is calculated using the moments accountant. I suggest adding a line similar to "update privacy loss using moment accountant" to the algorithm box. This point should be made clearer.
    - (-C7) I think lines 251 to 300 could be written in a more reader friendly way e.g., by reminding the reader of what certain symbols mean. 
    - (-C8) Figure 2 is hard to read, and not colorblind friendly. 

---
- Significance (S)
    - (S1) The specific combination of ideas in this paper, to my knowledge, are novel, and could be used in practice. On the other hand, it is unclear to me how others in the community will be able to build upon this work. Since this work is the first to consider federated, private BayesOpt, the results are state of the art. 

---
- Miscellaneous (M)
    - (M1) Abstract Line 14 "competitive performance"—how is this measured? Relative to non-private performance?
    - (M2) Abstract Line 15 "practical trade-off between privacy and utility". Please clarify. Are you stating that the algorithm performs "well" and achieves a favourable trade-off, or that the algorithm allows for trading off privacy and utility e.g., through choice of hyperparameter. 
    - (M3) Line 56 "elegant combination, please omit elegant. 
    - (M4) What is the reason for the instability in results in Figure 3(c)—increasing the privacy budget/loss sometimes degrades performance?
    
limitations_and_societal_impact: Unfortunately, there seems to be only a token engagement with the broader societal implications of the work and the limitations of the work.
review_title: null

Meta-review: The paper introduces the first federated Bayesian optimisation method with a rigorous privacy guarantee together with theoretical and empirical analysis of its utility. All reviewers recommend acceptance, noting that this is a strong submission.
Decision: Accept (Poster)