Differentially Private Federated Bayesian Optimization with Distributed Exploration
Authors: Zhongxiang Dai
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian Optimization
Federated Learning
Federated Hyperparameter Tuning
Differential Privacy
Distributed Exploration

Abstract: Bayesian optimization (BO) has recently been extended to the federated learning (FL) setting by the federated Thompson sampling (FTS) algorithm, which has promising applications such as federated hyperparameter tuning. However, FTS is not equipped with a rigorous privacy guarantee which is an important consideration in FL. Recent works have incorporated differential privacy (DP) into the training of deep neural networks through a general framework for adding DP to iterative algorithms. Following this general DP framework, our work here integrates DP into FTS to preserve user-level privacy. We also leverage the ability of this general DP framework to handle different parameter vectors, as well as the technique of local modeling for BO, to further improve the utility of our algorithm through distributed exploration (DE). The resulting differentially private FTS with DE (DP-FTS-DE) algorithm is endowed with theoretical guarantees for both the privacy and utility and is amenable to interesting theoretical insights about the privacy-utility trade-off. We also use real-world experiments to show that DP-FTS-DE achieves high utility (competitive performance) with a strong privacy guarantee (small privacy loss) and induces a trade-off between privacy and utility.

Differentially Private Federated Bayesian Optimization with Distributed Exploration
Zhongxiang Dai", Bryan Kian Hsiang Low', Patrick Jaillet Dept. of Computer Science, National University of Singapore, Republic of Singapore! Dept. of Electrical Engineering and Computer Science, MIT, USA (daizhongxiang, wowkwlowwhooo @comp. nus mus.edu.s...... edu.sg', , jaallettmit.eddiee
Abstract
Bayesian optimization (BO) has recently been extended to the federated learning (FI.) setting by the federated Thompson sampling (FTS) algorithm, which has promising applications such as federated hyperparameter tuning. However, FTS is not equipped with a rigorous privacy guarantee which is an important consideration in FL. Recent works have incorporated differential privacy (DP) into the training deep neural networks through a general framework for adding DP to iterative algorithms. Following this general DP framework, our work here integrates DP into FTS to preserve user-level privacy. We also leverage the ability of this general DP framework to handle different parameter vectors, as well as the technique of local modeling for BO, to further improve the utility of our algorithm through distributed exploration (DE). The resulting differentially private FTS with DE (DP-FTS-DD algorithm is endowed with theoretical guarantees for both the privacy and utility and is amenable interesting theoretical insights about the Privacy-utlliny trade-off. We also use real-world experiments to show that DP-FTS-DE achieves high utility (competitive performance) with strong privacy guarantee (small privacy loss) and induces a trade-off between privacy and utility.
1 Introduction
Bayesian optimization (BO) has become popular for optimizing expensive-to-evaluat black-box functions, such as tuning the hyperparameters of deep neural networks (DNNs) (56). Motivated by the growing computational capability of edge devices and concerns over sharing the raw data, BO has recently been extended the federated learning (FL) setting [46] derive the setting of federated BO (FBO) [2] The FBO setting allows multiple agents with potentially heterogeneous objective functions to collaborate data. For example, mobile phone users can use FBO to collaborate in optimizing the hyperparameters of their DNN models used in smart keyboard application without sharing their sensitive raw data. Hospitals can FBO to collaborate with each other when selecting the patients perform a medical test (67] without sharing the sensitive patient information. An important consideration in FL has been rigorous protection of the privacy of the users/agents, i.c., how to guarantee that by participating in a FL system, an agent would not reveal sensitive information about itself (29] Furthermore, incorporating rigorous privacy preservation into BO has recently attracted increasing attention due to its importance to real-world BO applications B3 36 48 71]. However, the state-of-the-ar algorithm
black-box optimization tasks without requiring them to share their raw
in the FBO setting, federated Thompson sampling (FTS) 112, is equipped with privacy guarantee and thus lacks rigorous protection of the sensitive agent information.
Differential privacy (DP) 20) provides rigorous privacy guarantee for data release and has become
the state-of-the-art method for designing has been applied to the iterative training of DNNs using stochastic gradient descent (DP-SGD) [I]
ML algorithms (28). Recently, DP
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and the FL algorithm of federated averaging (DP-FedAvg) 47). which have achieved competitive performances (utility) with a strong privacy guarantee. Notably, these methods have followed a general framework for adding DP to generic iterative algorithms 45 (referred to as the general DP framework hereafter), which applies a subsampled Gaussian mechanism (Sec. 2 in every iteration. For an iterative algorithm (e.g., FedAvg) applied to a database with multiple records (e.g., data from multiple users), the general DP framework [45] can hide the participation of any single record in the algorithm in principled way. For example, De-FedAvg [47] guarantees (with high probability) that an adversary, even with arbitrary side information, cannot infer whether the data from a particular user has been used by the algorithm, hence preserving user-level privacy. Unfortunately, FTS [12] is not amenable to a straightforward integration of the general DP framework [45] (Sec. 3.1 So, we modify FTS to be compatible with the general DP framework and hence introduce the DP-FFS algorithm to preserve user-level privacy in the FBO setting. In addition to the theoretical challenge of accounting for the impact of the integration of DP in our theoretical analysis, we have ensure that DP-FTS preserves the practical performance advantage (utility) of FTS. To this end, we leverage the ability of the general DP framework to handle different parameter vectors [45), well as the method of local modeling for BO, to further improve the practical performance (utility) of DP-FTS.
Note that FTS, as well as DP-FTS, is able to achieve better performance (utility) than standard TS by accelerating exploration using the information from the other agents (aggregated by the central server) [1]. That is, an agent using FTS/DP-FTT benefits from needing to perform less exploration in the early stages. To improve the utility of DP-FTS even more, we further accelerate exploration in the early stages using our proposed distributed exploration technique which is a combination of local modeling for BO and the ability of the general DP framework to handle different parameter vectors. Specifically, we divide the entire search space into smaller local sub-regions and let every agent explore only one local sub-region at initialization. As a result, compared with the entire search space, every agent can explore the local sub-region more effectively because its Gaussian process (GP) surrogate (i.e., the surrogate used by BO to model the objective function) can model the objective function more accurately in smaller local sub-region 22.. Subsequently, in every BO iteration, the central server aggregates the information (vector) for every sub-region separately: For a sub-region, the aggregation (i.e., weighted average) gives more emphasis (i.e., weights) to the information (vectors) from those agents who are assigned to explore this particular sub-region. Interestingly, this technique can be seamlessly integrated into the general DP framework due to its ability to process different parameter vectors (i.e., one vector for every sub-region) while still preserving the interpretation as single subsampled Gaussian mechanism 45 (Sec. (33
[ As a result, the information aggregated by the central server can help the agents explore every sub-region (hence the entire search space) more effectively in the early stages and thus significantly improve the practical convergence (utility), demonstrated in our experiments (Sec. 5). We refer to the resulting DP-FTS algorithm with distributed exploration (DE) as DP-FTS-DE. Note that DP-FTS is a special case of DP-FTS-WT -E with only one sub-region (i.e., entire search space). So, will refer to DP-FTS-DE as our main algorithm in the rest of this paper.
In this paper, we introduce the differentially private FTS with DE (DP-FTS-DE) algorithm (Sec. 3). the first algorithm with a rigorous guarantee on the user-level privacy in the FBO setting. DP-FTS-DE guarantees that an adversary cannot infer whether an agent has participated in the algorithm, hence assuring every agent that its participation will not reveal its sensitive information 2 We provide theoretical guarantees for both the privacy and utility of DP-FTS-DE. which combine to yield number of elegant theoretical insights about the privacy- trade-off (Sec. D. Next, we empirically demonstrate that DP-FTS-DE delivers an effective performance with a strong privacy guarantee and induces a favorable trade-off between privacy and utility in real-world applications (Sec. 55)
2 Background
Bayesian optimization (BO). BO aims to maximize an objective function ff on a domain X' RRD through sequential queries, i.e., to find x" E arg maxxe f(x) Specifically, in iteration & E [T] (we use [N] to represent [1...., N) for brevity), an input x, E is selected to be queried to yield
By analogy, the vectors for different sub-regions in our algorithm play a similar role to the parameters of different layers of DNN in De-FedAvg (47..
Following [47], we assume that the central server trustworthy and that the clients are untrustworthy.
$ For simplicity, we assume X' to be discrete, but our theoretical analysis can be extended to compact domains through suitable discretizations [7].
2

---

an output observation: Y/ _ f(x)) + Ç where Ç is sampled from Gaussian noise with variance o²: Ç <~N (O, 0²). To select the x, intelligently, BO uses a Gaussian process (GP) [4 as a surrogate to model the objective function f. A GP is defined by its mean function and kernel function k. We assume w.l.o.g. that (u(x) = 0 and k(x, x') S 1, Vx, x' E X. We mainly focus on the widely used squared exponential (SE) kernel in this work. In iteration & + 1, given the first i input-output pairs, where
the GP posterior is given by (),
[x(x)= A (x) (K + AII-Tyy o & x(x,x') - k((x) (K, + -I)- (x')))
(1)
in which (x) & (A(x, (e(x,xe)) Drego Yt & (yr)TE K, - (k(X), X(") wrre and À > 0 is a regularization parameter 77] In iteration + 1, the GP posterior (I) is used to select the next query Xx+1- For example, the Thompson sampling (TS) 77] algorithm firstly samples function fi+1 from the GP posterior ① and then chooses X,+1 = arg maxxex ft+1 (x). BO algorithms are usually analyzed in terms of regret. A hallmark for well-performing BO algorithms is be asymptotically no-regret, which requires the cumulative regret Rr - E
(xx)) to grow sub-linearly.
Random Fourier features (RFFs) 53 has been adopted to approximate the kernel function k using M- dimensional random features Φ: k(x,x') ((xx) x(x'). RFFs offers high-probabilit guarantee
on the approximation quality: sx [x(x, - <(x) xxx')l where & ((M-1/2) (53) Of note, RFFs makes it particularly convenient to approximately sample a function from the GP posterior. Specifically, define 4; _ (Ø((x)) (i.e., a t x M-dimensional matrix), Σ, -
& 2; + XI, and Mr & E2 2, Ye. To sample a function f from approximate GP posterior, we only need sample
w N(P
(2)
and set f(x) ((x)
(w( ww E X. RFFs has been adopted by FTS 12 since it allows avoiding the sharing of raw data and improves the communication efficiency 12]
Federated Bayesian Optimization (FBO). FBO involves N agents A A,....,AA.. Every agent An attempts to maximize its objective function f :''' - X R. i... to find x E arg maxxex' (x), by querying x and observing vi', Vt E [T]. Without loss of generality, our theoretical analyses mainly focus on the perspective of agent Ai. That is, we derive an upper bound on the cumulative regret of A₁: R4 () (x (x()) in Sec. 4 We characterize the similarity between Ai and An by dn A maxxex (x) - -X"(x) such that d; - and a smaller dn indicates larger degree of similarity between A₁ and An. Following the work of [12). we assume that all participating agents share the same of random features ((x), Vx E X. In our theoretical analysis, we assume that all objective functions have bounded norm induced by the reproducing kernel Hilbert space (RKHS) associated with the kernel k. i..., Ie S B, Vn E [N]. The work of [[2] has introduced the FTS algorithm for the FBO setting. In iteration t + 1 of FTS, every agent A.. (2 S S N) samples a vector W,,t from its GP posterior (2) and sends it to A₁. Next, with probability p. (0, 1], Ai chooses the next query using a function fit1 sampled from its own GP pt. pr. Ai firstly randomly samples an agent An (2 < n S N) and then chooses X1+1 = arg maxxe. x(x)" Wn,t-
posterior: X++1 = arg maxxex (x); with probability
Differential Privacy (DP). DP provides a rigorous framework for privacy- preneeviig data re- lease 19.. Consistent with that of [47], we define two datasets as adjacent if they differ by the data of a single user/agent, which leads to the definition of user-level DP:
Definition 1. A randomized mechanism M : D + R satisfies (e, O), for any two adjacent datasets Dj and D22 and any subset of outputs S c R. (P(()))) ES S P(M(D2) E S) 8.
Here. and d are DP parameters such that the smaller they are, the better the privacy guarantee. Intuitively, user-level DP ensures that adding or removing any single user/agent has an imperceptible impact on the output of the algorithm. DP-FedAvg (47 has added user-level DP into the FL setting by adopting general DP framework [45. In DP- the central server applies subsampled Gaussian mechanism to the vectors (gradients) received from multiple agents in every iteration t:
1. Select subset of agents by choosing every agent with fixed probability q.
2. Clip the vector Wa,t from every selected agent so that its La norm is upper-bounded by S,
3. Add Gaussian noise (variance proportional to 52) to the weighted average of clipped vectors.
3

---

The central server then broadcasts the vector produced by step 3 to all agents. As result of the general DP framework, they are able to not only provide rigorous privacy guarantee. but also use the moments accouniant method []] to calculate the privacy loss 4 More recently, the work of [45] has formalized the methods used by [ and 447 as a general DP framework that applicable to generic iterative algorithms. Notably, the general DP framework [45] can naturally process different parameter vectors (c.g., parameters of different layers of a DNN), which is an important property that allows us to integrate distributed exploration (See. 3.2) into our algorithm.
3 Differentially Private FTS with Distributed Exploration
Here we firstly introduce how we modify FTS to integrate DP to derive the DP-FTS algorithm (Sec.B.Il) Then, we describe distributed exploration which can be seamlessly integrated into DP-FTS to further improve utility (Sec. 3.2 Lastly, we present the complete DP-FTS-DE algorithm (Sec. 3.3
3.1 Differentillly Private Federated Thompson Sampling (DP-FTS)
The original FTS algorithm 12 is not amenable to a straightforward integration of the general DP framework. This is because FTS [2] requires an agent receive all vectors Wn.t's 's from the other agents (Sec. - so the transformations to the vectors required by the general DP framework (e.g.. subsampling and weighted averaging of the vectors) cannot be easily incorporated. Therefore, modify FTS by (a) adding a central server for performing the srivacy-preservingg transformations, and (b) passing a single aggregated vector (instead of one vector from every agent) to the agents. Fig. [ illustrates our DP-FTS algorithm which is obtained by integrating the general DP framework into modified FTS. Every iteration of DP-FTS consists of the following steps:
O, ② (by Agents): Every agent An, samples a vector Wn. 2 using its own current history of t input-output pairs (step () and sends Wn.t to the central server (step 2).
3 + (by Central Server): Next, the central server processes the N received vectors Wn,t using a subsampled Gaussian mechanism (step D): It (a) selects a subset of agents S, by choosing each agent with probability q, (b) clips the vector Wn,t of every selected agent s.t. its L2 norm is upper-bounde bounded by S, and (c) calculates weighted average of the clipped vectors using weights {1p,, Vn E [N]]. and adds to it a Gaussian noise. The final vector w, is then broadcast to all agents (step (+).
3 (by Agents): After an agent A,, receives the vector w, from the central server, it can choose the next query x (step ()) With probability Pc+1 E (0, A,, chooses x using standard
TS by firstly sampling function fitz from its own GP posterior of GP (.), of (. )2) ①I
where 3e & B + / 2((n-11 +1 + log(4/5) 3 and then choosing x = arg maxxex
with probability
Pt+1, An chooses x using w, received from the central server: x[+1
arg maxxex Φ(x) T wi. Consistent with that of [1]. (Pt)cez) is chosen as a monotonically increas-
ing sequence such that P. (0. 11, Vt and p. + 1 as f + oc. This choice of the sequence of (pt)tezt
ensures that in the early stage (i.e., when - Pt is large), an agent can leverage the information from the other agents (via wi) to improve its convergence by accelerating its exploration.
After choosing x(+1 and observing vf+1. An adds (x*+1: v(+11) to its history and samples new vector wn,t+1 (step (). Next, An sends w wn.++1 to the central server (step 2), and the algorithm repeated. The detailed algorithm will be presented in Sec. 3.3 since DP-FTS is equivalent to the DP-FTS-DE algorithm with P = 1 sub-region.
3.2 Distributed Exploration (DE)
To accelerate the practical convergence (utility) of DP-FTS, we introduce DE to further accelerate the exploration in the early stages (Sec. [T]. At the beginning of BO, a small number of initial points are usually selected from the entire domann using an exploration method (e.g.. random search) to warm- start BO. We use DE allow every agent to explore a smaller local sub-region at initialization, which is easier to model for the GP surrogate (11. and leverage the ability of the general DP framework to handle different parameter vectors 45 to integrate DE into DP-FTS a seamless way.
1 'Given a 8, the privacy loss is defined as an upper hound on e calculated by the moments accountant method. S- is the max information about the objective function from any t - queries and å (0. 1) (Theorem 1

---

choose x
Min
subsompled
1000 ois0 Tull Foo - of
Gaussian mechanism
waggts
joing
Agost
Agemtt
Agrett
W
weight
X
X2
w
(b)
(c)
Figure I: (a) DP-FTS algorithm (without distributed exploration). (b-c) Replacing steps 3 and ( (a) with that in (b) and (c) respectively to derive the DP-FTS-DE algorithm (P 2).
in
Specifically, we partition the input domain X' into P disjoint sub-regions: _,,,.., Rp such that P.Y; = X' and X; n 0, Vi * j. At initialization, we assign every agent A,, to explore (i.e., choose the initial points randomly from) a particular sub-region X F Note that if an agent A.. assigned to explore a sub-region X,,, (instead of exploring the entire domain), its vector Wn.t (2) sent to the central server is more informative about its objective function in this sub-region X.,
As a result, for a sub-region X, the vectors from those agents exploring X; contain information that can help better explore X₁ So, we let the central server construct separate vector w for (2)
every sub-region X, and when constructing w( give more weights to the vectors from those agents exploring X; because they are more informative about X, Consequently, the central server needs to construct different vectors {w) (4) Vi [P]] with each w using a separate set of weights (geh) Vn E [N]] Interestingly, from the perspective of the general DP framework [45, the different vectors {wi() (0) Vi E [P]} can be interpreted as analogous to the parameters of different layers of a DNN and can thus be naturally handled by the general DP framework. After receiving the P vectors
from the central server, every agent uses ( to reconstruct the sampled function in the sub-region X; fi(x) = ((x) T (1) Vx E X, and then (with probability 1 - pt) chooses the next query by
maximizing the sampled functions from all sub-regions (Fig. [ : see more details in Sec. 3.3
After initialization, every agent is allowed to query any input in the entire domain X' regardless of the sub-region it is assigned to. So. as t becomes larger, every agent is likely have explored (and become informative about) more sub-regions in addition to the one it is assigned to. In this regard, for
every sub-region X, we make the set of weights {phh Vn [N]] adaptive such that they (a) give more weights to those agents exploring X; when is small and (b) gradually become uniform among all agents t becomes large. We adopt the widely used softmax weighting with temperature T. which has been shown to provide well-calibrated uncertainty for weighted ensemble of GP experts (
Σm= (1)T) and gradually increase the temperature T from 1 to +00 (more details App. B). The dependence of the weights on / only requires minimal modifications to the algorithm and the theoretical results. So, we drop this dependence for simplicity.
Concretely, we let ypn (6)
exp((a1()) +1)/7)
3.3 DP-FTS-DE Algorithm
Our complete DP-FTS-DD algorithm after integrating DE (Sec. 3.2 into DP-FTS (Sec. 3.1 is
presented in Algo. (central server's role) and Algo. _ (agent's role), with the steps in circle corresponding to those in Fig. Th. DP-FTS-DE differs from DP-FTS two major aspects: Firstly, at initialization (t 0), every agent only explores local sub-region instead of the entire domain (line 2 of Algo. 2. Secondly, instead of a single vector w;, the central server produces and broadcasts P
vectors {w (5) Vi [P]], each corresponding to different sub-region X, and using different set of weights. Applying different transformations to different vectors (e.g., parameters of different DNN layers) can be naturally incorporated into the general DP framework (45). Different transformations performed by our central server to produce P vectors can be interpreted as a single subsampled
'For simplicity, we choose the sub-regions to be ryper-rectangles with equal volumes and assign an approxi- mately equal number of agents ( N/P) to explore every sub-region.
Because its GP surrogate can model the objective function in this local sub-region more accurately 21] $ 8y(1) is an indicator variable that equals 1 if agent is assigned to explore X; and equals 0 otherwise. a > 0 is constant and we set = 15 in all our experiments.
5

---

Gaussian mechanism producing single joint vector w - (w) NE(PI (Fig. [b). Next, we present these transformations performed by the central server (lines 5-12 of Algo. I from this perspective.
Subsampling: To begin with, after receiving the vectors Wn,t's 's from the agents (lines 3-4 of Algo. [ the central server firstly chooses a random subset of agents S by selecting each agent with probability q (line 6). Next, for every selected agent St, the central server constructs P x M-dimensional
joint vector: w n.t
joint
(+) Pin Wn, (eE))-
Algorithm 1 DP-FFS FTS-DES (central server)
1: " 0
2: for iterations t = 2, 2......... . do
3: for agents n 1, .., .V in parallel do
4: Wn.t < BO-Agent-An(4 w
5: w/ 0, Vi E [P]
6: Choose a random subset S. C [N] of agents
7:
for sub-regions 1.2,.... do for agents n E St do
8:
|
9:
Wn,t Wn,t/ max (1,
S/VP
w()) += (sh)) /1) Wn.t
10:
11:
w/ += N (0, S/q)
Broadcast Joint (w) )c((P] to all agents
13:
Update the privacy loss using the moments accountant method
Algorithm 2 BO-AAgett-An w Joint = (01=1))(PP)
1:
/ then
2:
Randomly select and query Nun initial points from sub-region X.,,
3: else
4:
Sample from the uniform distribution over [], ~~ U(0
5: if < Pr then
6:
x arg maxxex 13 (x), where f GP
5
7:
else
8:
x arg maxxex ((x) wi
(169
9: Query x;" to observe y/f"
10: Sample Wn, and send it to central server
1. 2
Clipping: Next, clip every selected vector Wn,t obtain Wn,t such that || S/VP. This is equivalent to clipping whit joint to obtain: Wiiint A (Nypl @n.))eepp, whose L2 norm is bounded by n,t [105) ||2 & 2N max E I| [2)2/2 < Nymmax where Pmax max:e]p). ph
Weighted Average: Next, calculate weighted average of the clipped joint vectors by giv- ing equal weights from the concatenation of the vectors from all sub-regions: w.
10 to all agents: w.iit
(gN)-'Enen nnt II Note that Loint results
(w)) )<{(P) where w.
(1)
~ Nopl
(1) -
in !f @ (line 10 of Algo.
Gaussian Noise: Finally, add to each element of w (w) (1)
)EE[P] zero-mean Gaussian noise
with standard deviation of 2(N Pmxx () = 2Pmax S/q (line 11).
Next, the output join (w) je[p is broadcast to all agents. After agent An receives joint with probability Pe+1, An, chooses the next query x by maximizing a function fi sampled from its own GP posterior GP(HF (1), 1811)1881071 o7
(line 6 of Algo. B, A B
2(2-1 +1+ log( (4/855 with probability - Pc+ An uses wi juint
[w) kE[P received from
9g1a represents the sub-region x is assigned to.
This weight is only used aid interpretation and different from weights ypx ( used in our algorithm.
The summation divided by gN (i.e.. expected number of agents selected) to make unbiased [47).

---

the central server to choose 1 by maximizing the reconstructed functions for all sub-regions (line 8 of Algo. ( as illustrated in Fig. Tr. Finally, it queries x to observe yf+ samples a new vector wn,t+1 and sends it to the central server (line 10 of Algo. 2 and the algorithm is repeated.
4 Theoretical Analysis
In this section, we present theoretical guarantees on both the privacy and utility of our DP-FTS-DE, which combine to yield interesting insights about the privacy-utility trade-off.
Proposition 1 (Privacy Guarantee). There exist constants 01 and 02 such that for fixed q and T and any é < "i 0, DP-FTS-DE (Algo. 1 is (e, if 2 Z 029. logg((//)//
Proposition formalizes our privacy guarantee, and its proof (App. A.I follows directly from shows that a larger (i.e., larger variance for Gaussian noise), a smaller q (i.e., smaller expected of selected agents) and smaller T (i.e., smaller no. of iterations) all improve the privacy guarantee because for fixed 6, they all allow to be smaller.
Theorem 1 of [. Proposition |
Theorem 1 (Utility Guarantee). Assume that all fr 's lie in the RKHS of kernel k: IIf" S B, Vn E [N]. Let i/t be the max information gain on f from any set of t observations, & denote an upper bound on the approximation error of RFFs (Sec. 2). C.
- {n E [NT][[wn,elz > SS//P),
6 E (0, X = 1 + 2/T and Bt _ B + -o 20002(1111111 + 1+ log(4/0) (Algo. 2 Choose (pt)tez) to be monotonically increasing s.t. Pt = ((1/tt) Then, with probability of least 1 (Ö hides all logarithmic factors),
R4 = ( 11pr) TT + Ei the + + BEE
21=1 8.)
where vi, & Õ((1 Pt) P - (A, + M)) A. - ΣN Anto An & Ö(BBt + VM- + d, + vT., and 02 a (1-Pt) p:) El= Enec, Pn
Theorem D (proof in App. A.2p gives an upper bound on the cumulative regret of agent AA. Note that all three terms in the regret upper bound grow sub-linearly: The first term is sub-lineat because 'r = =O(ooo T P+1) for the SE kernel (D is the dimension of the input space), and the second and third terms are both sub-linear since we have chosen 1 - Pt 0(1 112 2 So. DP-FTS-DE preserves the no-regret property of FTS [2]. That is, agent A is asymptotically no-regrel even all other agents are heterogeneous, i.e., all other agents have significantly different objective functions from A.. This is particularly desirable because it ensures the robustness of DP-FTS-DE against the heterogeneity of agents, which is an important challenge in both FL and FBO 12 29 and has also been an important consideration for other works on the theoretical convergence of FL 43 44). To prove this robust guarantee, we have upper-bounder the worst-case error induced by the use of any set of agents, which explains the dependence of the regret bound on dn - maxxex If (x) - (x)) and (Pt)aez+. Specifically, larger d 's indicate larger differences between the objective functions of An and the other agents and hence lead to a worse regret upper bound (through the term
(r.). Smaller
values of the sequence (Pe >rez increase the utilization of information from the other agents (line 8 of Algo. /
becomes more likely be executed), hence inflating the worst-case error resulting from these information.
Theorem | when interpreted together with Proposition D also reveals some interesting theoretical insights regarding the privacy-utility trade-off.. Firstly, a larger = (i.e., larger variance for Gaussian noise) improves the privacy guarantee (Proposition [ and yet results in worse utility since it leads to worse regret upper bound (through 2/2). Secondly, larger q (i.e., more selected agents in each iteration) improves the utility since tightens the regret upper bound (by reducing the value of 4))) at the expense of a worse privacy guarantee (Proposition] IT. A general guideline for choosing the values of z and q is aim for a good utility while ensuring that the privacy loss within the single-digit range (i.e., < 10) I The value of the clipping threshold S exerts no impact on the privacy guarantee. However, affects the regret upper bound (hence the utility) through two conflicting effects: Firstly, smaller S reduces the value of th: and hence the regret bound. However, smaller S is likely to enlarge the cardinality of the set C, hence increasing the value of d, (Theorem I]. Intuitively, a
The requirement of 1 - Pt = ((1tt)) is needed only to ensure that DP-FTS- DE is no-regret even if all other agents are heterogeneous and is hence conservative choice. Therefore, it is reasonable to make - Pt decrease slower in practice show our experiments (Sec. 5)
7

---

15
15
15
15
FTS-DE
FT5-00
FT5-00 50
8
DR-TS-0E 11
DR- 13
Ce 00-775-06 1p 0..0.
DR-ITS Iew 121 OPVITS 1.
30
20
(a)
(b)
(d)
Figure 2: (a) Benefit of DE. (b) Impact of S. (c) Impacc of q privacy losses after T 40 itera- tions are 5.93. 9.91, 20.12 for the respective q = 0.15, 0.25, 0.5. (d) Impact of 2; privacy loss are 9.91, 7.39, 5.22 for the respective 2 = 1.0, 1.2, 1.5. Every curve is averaged over N = 200 agents, each further averaged over 5 runs with different random initializations of size Nint 10. The results before iteration 0 correspond to the initialization period.
smaller S impacts the performance positively by reducing the noise variance (line 11 of Algo. I and yet negatively by causing more vectors to be clipped (line 9 of Algo. D. A general guide on the selection of S is choose a small value while ensuring that a small number of vectors clipped.
Regarding the dependence of the regret upper bound on the number of random features M, in addition to the dependence through An.; which has been analyzed by (12), the integration of DP introduces another dependence that implicitly affects the privacy-utility trade-off. Besides increasing the value of e/t, larger M enlarges the value of 02 as larger dimension for the vectors wn,t's 's is expected to increase their Ly norms, hence increasing the cardinality of the set C, and consequently the value of the (Theorem [p. So, the additional dependence due to the integration of DP loosens the regret upper bound with an increasing M. As a result, if M is larger, we can either sacrifice privacy to preserve utility by reducing z or increasing q (both can counter the increase of 1bx), sacrifice utility to preserve privacy by keeping z and unchanged. The number of sub-regions also induces a trade- off about the performance of our algorithm, which is partially reflected by Theorem [] Specifically, the regret bound depends on P through three terms. Two of the terms (P' in 1h and the summation of P terms in U³)) arise due to the worst-case nature of our regret bound, as discussed earlier: They cause the regret upper bound to increase with P due to the accumulation of the worst-case errors resulting from the P vectors: {w] Vi E [P]] Regarding the third term (in the definition of G+), larger P is expected to increase the cardinality of the set Ct (similar to the effect of a larger M discussed above), consequently loosening the regret upper bound by inflating the value of 0,. In this case, as described above, we can choose to sacrifice either privacy or utility. On the other hand, a larger J' (i.e., larger number of sub-regions) can improve the practical performance (utility) because it allows every agent to explore only a smaller sub-region which can be better modeled by its GP surrogate (Sec. 3.2). As a result of the worst-case nature of the regret bound mentioned earlier, the latter positive effect leading Therefore, we instead verify this trade-off
to better practical utility is not reflected by Theorem [ induced by P about the practical performance in our experiments (Fig. 6 App. B.
Experiments
Note that the privacy loss calculated by the moments accountant method is an upper bound on the value of for given value of 8 When calculating the privacy loss, we follow the practice of [47] and set 8 = 1/ 1/N1.1 All error bars denote standard errors. Due to space constraints, some experimental details are deferred to App. B
5.1 Synthetic Experiments
In synthetic experiments, we firstly sample a function from a GP with the SE kernel, and then apply different small random perturbations to the values of the sampled function obtain the objective functions of N 220 different agents. We choose MM = 50 and 1 - Pa /t, Vt E Z+ We firstly demonstrate the performance advantage of modified FTS and FTS-DE (without DP) over standard TS. As shown in Fig. 2 FTS converges faster than standard TS and more importantly, FTS-DE (Sec. 3.2) further improves the performance of FTS considerably. Moreover, using a larger number P of sub-regions (i.e., smaller sub-regions) brings more performance benefit. This is consistent with our analysis of DE (Sec. suggesting that smaller sub-regions are easier to model for the GP surrogate and hence can be better explored. Moreover, we have also verified that after the integration of DP, DP-FTS-DE (P- = 2) can still achieve significantly better convergence (utility) than DP-FTS for the same level of privacy guarantee (Fig. 4 in App- B.T). These results justify the practical significance of our DE technique (Sec. 3.2). We have also shown (Fig.) 5 App. B.I that both components in our
8

---

BROTSAOE TORy DI-TT-OE (very
0.236
Valisation Ermor
0.00
TS
Validdation Error
0.21
FTS
0.235
0.07
FTSICE
0.20
0.234
0.06
0.19
0.233
2.5
5.0
7.5
15.0
12.5
15.0
15.0
loss
(a)
(b)
(c)
0.250
0.150
0.30
orumi-oe ja- bas 1.00
0.125
seuris-c 12-w0 1.00
Veiddation Eroo
0.25
-i-0 de 6-
0.100
0.20
goant 1p-02t..m 1.00
0.235
0.075
0.15
0.230
0.060
50
100
150
200
0.025
100
150
200
50
100
150
200
(d)
(c)
(f)
Figure 3: (a.b,c) Privacy loss vs. performance after 60 iterations for landmine detection, human activity recognition, and EMNIST. The more to the left (bottom), the better the privacy (utility). (d,e.f) Convergence results for some settings in each experiment. Results are averaged over N agents, each further averaged over 100 (a,d) and 10 (b,c,e.f) random initializations (Niit 10). Some error bars overlap because the agents are highly heterogeneous and thus have significantly different scales.
DE technique (i.e., letting every agent explore only a local sub-region and giving more weights to those agents exploring the sub-region) are necessary for the performance of DE.
Fig. [2b explores the impact of the clipping threshold S. From Fig. 2b, an overly small S may hinder the performance since it causes too many vectors to be clipped, and an excessively large S may also be detrimental due to increasing the variance of the added Gaussian noise. This corroborates our analysis in Sec. 4 The value of S = 11, which delivers the best performance in Fig. [b,, has been chosen such that only a small percentage (0.8%) of the vectors are clipped. Figs. - and d show the privacy-utilin trade-off of our DP-FTS-DD TED algorithm induced by and z. The results verify our theoretical insights regarding the impact of the parameters q and z on the privacy-utility trade-off (Sec. 4. i.e., a larger (smaller 2) leads to better utility at the expense of a greater privacy loss. Lastly, we also verify the robustness of our algorithm against agent heterogeneity. show that when the objective functions of different agents are significantly different, our FTS-DE algorithm is still able to perform comparably with standard TS and letting the impact of the other agents decay faster (i.e., letting Pt decrease faster) can improve the performance of FTS-DE in this scenario (see Fig. in App. B.1.2).
particular, we
5.2 Real- World Experiments
We adopt commonly used datasets in FL. and FBO 12
We firstly use a landmine detection dataset with N = 29 landmine fields (66) and tune 2 hyperparameters of SVM for landmine detection. Next, we use data collected using mobile phone sensors when N 30 subjects are performing activities [2) and tune 3 hyperparameters of logistic regression for activity classification. Lastly, we use the images of handwritten characters by N = 50 persons from EMNIST (a commonly used benchmark in FL) [8] and tune 3 hyperparameters of convolutional neural network used for image classification. In all 3 experiments, we choose P = 4, S = 22.0, M = 100, and P Pt 1/t. In the practical deployment of our algorithm, if the values of these parameters tuned by running additional experiments, the additional privacy loss can be easily accounted for using existing techniques [
60
Figs. b.c. plot the privacy (horizontal axis, more to the left is better) and utility (vertical axis, lower is better) after 60 iteration [3] The green dots correspond to 1.1.6,2 2, 3, (q 0..5) and the red dots represent = 0.1, 1.115,000 0.2, 0.25, 0.35 (z = 1). Results show that with small privacy loss (in the single digit range). DP-FTS-DE achieves a competitive performance (utility) and significantly outperforms standard TS in all settings. The figures also reveal a clear trade-off between privacy and
II practice, we recommend that the agents switch to local TS after the value of 1 Pc becomes so small (e.g.. after 60 iterations) that the probability of using the information from the central server is negligible (i.e., line& 8 of Algo. i unlikely to be executed), after which privacy loss is incurred.

---

utility, i.e., smaller privacy loss (more to the left) generally results in worse utility (larger vertical value). In addition, these two observations can also be obtained from Figs.Bi.et which plot some convergence results: DP-FTS-DE and FTS-DE converge faster than TS; a smaller privacy loss (i.e.,
larger or smaller 4) in general leads to a slower convergence. Figs. bbc also justify the importance of DE (Sec. (32) since FTS-DE (and some settings of DP-FT'-DDE outperforms FT' without DE in all experiments. We also verify the importance of DE when DP is integrated in App. B.2 (Fig. (8) Furthermore, we demonstrate the robustness of our results against the choices of the weights and the number of sub-regions in App. [32.3 Lastly, our DP-FTS- can be easily adapted to use Rényi
DP 63 14 which, although requires modifications to our theoretical analysis, offers slightly better privacy loss with comparable performances (Fig. 11 in App. B.2
Related Works
BO has been extensively studied recently under different settings 3 7 25
51
52 56 61
Recent works have added privacy preservation to BO by applying DP to the output of BO [36.. using a different notion of privacy other than DP 48 adding DP to outsourced BO 33 adding
local DP to BO 7T.. However, none of these works can tackle the FBO setting considered in this paper. Collaborative BO involving multiple agents has also been considered by the work of [59], however, (59) has assumed that all agents share the same objective function and focused on the issue of faimess. Moreover, BO in the multi-agent setting has also been studied from the perspective of game theory 55). Our method also shares similarity with parallel BO [10]
[4]
[5]
23 24, 3T].
However, parallel BO optimizes single objectíve function while we allow agents have different
because utilizing information received from the central server can be viewed querying low-fidelity function. Our DE technique bears similarity to [21] which has also used separate GP surrogates to model different local sub-regions (hyper-rectangles) and shown significantly improved performance.
objective functions. Our algorithm is also related to multi-fidelity BO
13
30
68
69
FL has attracted significant attention recent years [29 37
38
42
46).
In particular, privacy including both central
preservation using DP has been important topic for FL
27
41
62
651
DP (with trusted central server) [47 and local [32 64 70 or distributed DP [4 6 [8] [58] (without trusted central server). In addition to setting of FBO which can be equivalently called federated GP bandit, other sequential decision-making problems have also been extended to the federated setting, including federated multi-armed bandit (57 72 federated linear bandit [17), and federated
reinforcement learning [22]. Lastly, federated hyperparameter tuning (i.e., hyperparameter tuning of ML models in the federated setting) has been attracting growing attention recently [26 35
7 Conclusion and Future Works
We introduce DP-FTS- DE, which equips FBO with rigorous privacy guarantee and is amenable to privacy-utility trade-off both theoretically and empirically. Since our method aims to promote larger-scale adoption of FBO, it may bring the negative societal impact of fairness: some users may become discriminated against by the algorithm. This can be mitigated by extending our method to consider fairness [59], suggesting an interesting future work. A limitation of our work is that the privacy loss offered by the moments accountant method (1) is not of For example, the more advanced privacy-preserve losses than moments accountant and has been widely applied in practice. So, a potential future work techniques such as Gaussian DP.
technique of Gaussian DP 5S] [6] can deliver smaller privacy
is to extend our method to adopt more advanced privacy-preservie Another limitation of our paper is that we have not accounted for the different network capabilities of different agents, which is a common problem in the federated setting. That is, our algorithm requires every agent to send its updated parameter vector to the central server in every iteration (lines 3 and of Algo. [. which may not be realistic in some scenarios since the messages from some agents may not be received by the central server. Therefore, accounting for this issue using principled method represents an interesting future work. Other potential future works include adapting our method for other sequential -aaiinn problems such as reinforcement learning (22], and incorporating risk aversion 49 50 into our method for safety-critical domains such clinical applications (Sec. [
WWe only need modify step of Algo. 1 s.t. randomly select fixed number of Ng agents.
10

---

Acknowledgments and Disclosure of Funding
This research/project supported by the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative. Any opinions, findings and conclusions recommen- dations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communicutions Security, pages 308-318, 2016.
[2] D. Anguita, A. Ghio, L. Oneto, X. Parra, and J. L. Reyes-Ortiz A public domain dataset for human activity recognition using smartphones. In Proc. ESANN, 2013.
[3] S. Balakrishnan, Q. P. Nguyen, B. K. H. Low, and H. Soh. Efficient exploration of reward functions in inverse reinforcement learning via Bayesian optimization. In Proc. NewrIPS, 2020.
[4] A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, Tinnes, and Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proc. SOSP, pages 441-459, 2017.
[5] Z. Bu, J. Dong, Q. Long, and J. data science review, 2020(23), 2020.
J. Su. Deep learning with gaussian differential privacy, Harvard
[6] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Proc. EUROCRYPT, pages 375-403. Springer, 2019.
[7] R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. Proc. ICML, pages 844-853, 2017.
[8] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik. EMNIST: Extending MNIST handwritten letters. In Proc. IJCN,, pages 2921-2926. IEEE, 2017.
[9] S. Cohen, R. Mbuvha, T. Marwala, and M. Deisenroth. Healing products of gaussian process experts. In International Conference on Machine Learning, pages (068-2077. PMLR, 2020.
[10] E. Contal, D. Buffoni, A. Robiequet, and N. Vayatis. Parallel Gaussian process optimization with upper confidence bound and pure exploration. In Proc. ECML/PKDD, pages 225-240, 2013.
[11] Z. Dai, Y. Chen, B. K. H. Low, P. Jaillet, and T.-H. Ho. R2-B2: Recursive reasoning- based Bayesian optimization for no-regret learning in games. In Proc. ICML, 2020.
[12] Z. Dai,
Low, and Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurlPS, 2020.
[13] Z. Dai, H. Yu, B. K. H. Low, and P. Jaillet. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, pages 1496-1506, 2019.
[14] E. A. Daxberger and B. K. H. Low. Distributed batch Gaussian process optimization. In Proc. ICML, pages 951-960. 2017.
[15] T. Desautels, A. Krause, and J. W. Burdick. Parallelizing exploration-exxllitation tradeoffs in Gaussian process bandit optimization. Journal of Machine Learning Research, 15:3873-3923, 2014.
[16] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy, arXiv preprint arXiv:1905.022 023383. 2019.
[17] A. Dubey and A. Pentland. Differentially-priaal federated linear bandits. Proc. NeurIPS, 2020.

---

[18] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Proc. EUROCRYPT, pages 486 503. Springer, 2006.
[19] C. Dwork, F, McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proc. TCC, pages 365-284. Springer, 2006.
[20] C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-400 2014.
[21] D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek. Scalable global optimization via local Bayesian optimization. In Proc. NeurlPS, 2019.
[22] X. Fan, Y. Ma, Z. Dai, W. Jing, C. Tan, and B. K. H. Low. Fault-tolerant federated reinforcement learning with theoretical guarantee. In Proc. NeurIPS, 2021.
[23] J. Garcia-Bareos and R. Martinez-Cantin. Fully distributed Bayesian optimization with stochas- tic policies. In Proc. IJCAI, 2019.
[24] M. Hernández- J. Requeima, E. O. Pyzer-Knaph and A. Aspuru-Guus Guzik. Parallel and distributed Thompson sampling for segle-ccleeaae accelerated exploration of chemical space. In Proc. ICML, 2017.
[25] T. N. Hoang, Q. M. Hoang, R. Ouyang, and B. K. H. Low. Decentralized high-dimensional Bayesian optimization with factor graphs. In Proc. AAAI, volume 32, 2018
[26] S. Holly, T. Hiessl, S. R. Lakani, D. Schall, C. Heitzinger, and J. Kemnitz, Evalua- tion of hyyerppuraeteeroppiiizztooo approaches in an industrial federated learning system. arXiv:2110.08202, 2021.
[27] R. Hu, Y. Guo. H. Li, Q. Pei, and Y. Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10):550-9559, 2020.
[28] Z. Ji, Z. C. Lipton, and C. Elkan. Differential privacy and machine learning: survey and review. arXiv:1412 1412.5444, 2014.
[29] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. arXIv:1912.04977, 2019.
[30] K. Kandasamy, G. Dasarathy, J. B. Oliva, J. Schneider, and B. Póczos. Gaussian process bandit optimisation with multi-fidelity evaluations. In Proc. NeurIPS, pages 992-1000, 2016.
[31] K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Póczos. Parallelised Bayesian optimisa- tion via Thompson sampling. In Proc. AISTATS, pages 133- 2018.
[32] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-88) 826, 2011.
[33] D. Kharkovskii, Z. Dai, and B. K. H. Low. Private outsourced Bayesian optimization. In Proc. ICML, pages 5231-5242. PMLR, 2020.
[34] D. Kharkovskii, C. K. Ling, and B. K. H. Low. Nonmyopic Gaussian process optimization with macro-actions. In Proc. AISTATS, pages 4504-4604. PMLR, 2020.
[35] M. Khodak, R. Tu, T. L. L. Li, M.-F. Balcan, V. Smith, and A. Talwalkar. Federated hyperpa- rameter tuning: Challenges, baselines, and connections to weight-sharing. arXiv:2106.04502. 2021.
[36] M. Kusner, J. Gardner, R. Garnett, and K. Weinberger. Differentially private Bayesian optimiza- tion. In Proc. ICML, pages 918-927, PMLR, 2015.
[37] Q. Li, Y. Diao, Q Chen, and B. He. Federated learning on non-iid data silos: An experimental study,
2021.
12

---

[38] Q. Li, B. He, and D. Song. Model-contrastive federated learning, In Proc. CVPR. pages 10713-10722, 2021.
[39] Q. Z.
Z. Wen, and B. He. Federated learning systems: Vision, hype and reality for data privacy and protection. urXiv:1907009699 2019.
[40] Q. Li. Z. Wen, and B. He. Practical federated gradient boosting decision trees. In Proc. AAAI, pages 4642-4649, 2020.
[41] Q. Li, Z. Wu, Z. Wen, and B. He. pereeyypreserving gradient boosting decision trees. In Proc. AAAI, pages 784-791, 2020.
[42] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and 1908.007777 2014.
future directions.
[43] Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. arXiv:1812.06127, 2018.
[44] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of FedAvg on non-iid data. In Proc. ICLR, 2020.
[45] H. B. McMahan, G. Andrew, U. Erlingsson, S. Chien, I. Mironov, N. Papernot, and P. Kairouz. A general approach to adding differential privacy to iterative training procedures. In Proc. NeurIPS Workshop on Privacy Preserving Machine Learning, 2018.
[46] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, al. Communication-effiiinnn learning of deep networks from decentralized data. In Proc. AISTATS, 2017.
[47] H. B. McMahan, D. Ramage, K. Talwar, and L.. Zhang. Learning differentially private recurrent language models. In Proc. ICI.R, 2018.
[48] D. T. Nguyen, S. Gupta, S. Rana, and S. Venkatesh. A privacy preserving Bayesian optimization with high efficiency. In Proc. PAKDD, pages 543-555. Springer, 2018.
[49] Q. P. Nguyen, Z. Dai, B. K. H. Low, and P. Jaillet. Optimizing conditional Value-At-Risk of black-box functions. In Proc. NeurlPS, 2021.
[50] Q Nguyen, 7. Dai, B. K. H. Low, and P. Jaillet. Value-at-Risk optimization with Gaussian processes. In Proc. ICMI., 2021.
[51] Q P. Nguyen, S. Tay, B. K. H. Low, and P. Jaillet. Top-k ranking Bayesian optimization. In 2021.
Proc. AAAI, volume 35, pages
[52] Q. P. Nguyen, Z. Wu, B. K. H. Low, and P. Jaillet. Trusted- maximiieaai entropy search for efficient Bayesian optimization. In Proc. UAI, 2021.
[53] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Proc. NeurIPS, pages 1177-1184, 2008.
[54] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
[55] G. Sessa, I. Bogunovic, M. Kamgarpour, and A. Krause. No-regret learning in unknown games with correlated payoffs. In Proc. NeurIPS, 2019.
[56] B. Shahriari, K. Swersky, Z. Wang. R. P. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104( 2016.
[57] C. Shi, C. Shen, and Yang. Federated multi-armed bandits with personalization. Proc. AISTATS, pages 2917-2925. PMLR, 2021.
[58] E. Shi, T. H. Chan, E. Rieffel, R. Chow, and D. Song. time-series data. In Proc. NDSS, volume 2, pages 1-17. Citeseer, 2011.
aggregation of
[59] R. Sim, Y. Zhang, B. K. H. Low, and P. Jaillet. Collaborative Bayesian optimization with fair regret. In Proc. ICML, pages 9691-9701, PMLR, 2021.
13

---

[60] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar. Federated multi-task learning. In Proc. NeurIPS, pages 4424 4434, 2017.
[61] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. Proc. ICML, pages 1015-1022, 2010.
[62] S. Truex, N. Baracaldo, A. Anwar, T. Steinke, H. Ludwig, R. Zhang, and Y. Zhou. A hybrid approach to privacy preservig federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pages 1-11. 2019.
[63] Y.-.. Wang, B. Balle, and Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In Proc. AISTATS, pages 226--123 PMLR, 2019.
[64] L. Warner. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-000 090 1965.
[65] K. Wei, Li, M. Ding, C. Ma, H. Yang, F. Farokhi, S. Jin, T. Q. Quek, and H. V. Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3669, 2020.
[66] Y. Xue, X. Liao, L. Carin, and B. Krishnapuram. Multi-task learning for classification with dirichlet process priors. Journal of Machine Learning Research, 8(Jan):35-63, 2007.
[67] S. Yu, F. Farooq, A. Van Esbroeck, G. Fung, V. Anand, and B. Krishnapuram. Predicting readmission risk with iestitution-speciffe prediction models. Artificial intelligence in medicine, 65(2):89-96, 2015.
[68] Y. Zhang, Z. Dai, and K. H. Low. Bayesian optimization with binary auxiliary information. In Proc. UAI, pages 1222-1232, 2020.
[69] Y. Zhang, T. N. Hoang, B. K. H. Low, and M. Kankanhalli. Information-based multi-fidelity Bayesian optimization. In Proc. NeurlPS Workshop on Bayesian Optimization, 2017.
[70] Y. Zhao, J. Zhao, M. Yang. T. Wang, N. Wang, L. Lyu, D. Niyato, and K.-Y. Lam. Local differential privacy-based federated learning for internet of things. IEEE Internet Things Journal, 8(1 11:83666-88,, 2020.
[71] X. Zhou and J. Tan. Local differential privacy for Bayesian optimization. arXiv:2010.06709. 2020.
[72] Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SYGMETRICS/nteenation Conference Measurement and Modeling of Computer Systems, pages 3-4, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 7
(C) Did you discuss any potential negative societal impacts of your work? [Yes] See Sec. 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sections 4nd
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you experiments..
14

---

(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] Our code is here: https://github... cttp dawp///aiziionnggga/.. Barg
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] See Figures
2
(the error bars can be better seen after
zooming in) and 3
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix B
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix B
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're
using/curating? [Yes] See Appendix B
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Appendix B
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "lXx_cKKsKgK", "reviewer": "Reviewer_YPjs", "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. \n\nOne sentence summary: the authors propose DP-Federated BO using Thompson sampling with a distributed initial random search. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "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.\n\nEDIT: I have increased my score to 7 based on the authors response. \n\n---\n- Originality (O)\n    - (+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. \n\n---\n- Quality (Q)\n    - (+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.  \n    - (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. \n   - (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. \n    - (-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. \n    - (-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. \n    - (-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. \n    - (-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. \n    - (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?\n    - (+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. \n   - (-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. \n   - (-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. \n---\nOverall, I believe improving the clarity and precision of the text in the paper would greatly benefit the submission. \n\n- Clarity (C)\n    - (-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. \n    - (-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. \n    - (-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?.  \n    - (-C4) Line 82 \"An interesting trade-off between privacy and utility in real-world applications\"—what does this mean? \n    - (-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. \n    - (-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.\n    - (-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. \n    - (-C8) Figure 2 is hard to read, and not colorblind friendly. \n\n---\n- Significance (S)\n    - (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. \n\n---\n- Miscellaneous (M)\n    - (M1) Abstract Line 14 \"competitive performance\"—how is this measured? Relative to non-private performance?\n    - (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. \n    - (M3) Line 56 \"elegant combination, please omit elegant. \n    - (M4) What is the reason for the instability in results in Figure 3(c)—increasing the privacy budget/loss sometimes degrades performance?\n    ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "I do not have ethical concerns with this paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "aXT5r593nfc", "reviewer": "Reviewer_wuG4", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "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.\n\nPros\n\n+ Interesting topic.\n+ Well-written and well-organized paper.\n\nCons\n\n- Limited novelty.\n- Unrealistic assumptions.\n- Weak numerical experiments.\n\nDetailed Comments\n\n1. 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.\n2. 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.\n3. 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.\n4. 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.\n5. For Figure 3, Bayesian optimization with 60 iterations is not enough, because they do not converge yet.\n\nMinor issues\n\n* Could you provide a reason why there are the experiment results before 0 iteration in Figure 2?\n* For Algorithm 2, the part from Line 4 to Line 7 should be declared by if-else statement.\n* In Line 84, what is $\\mathcal{R}$? It seems like $\\mathbb{R}$. There exist wrong notations like this. Please fix them.\n* In Line 18, DNN should be DNNs.\n* In Line 99, RFF should be RFFs.\n\n[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.\n\n[2] Z. Ji, Z. C. Lipton, and C. Elkan. Differential privacy and machine learning: a survey and review. arXiv preprint arXiv:1412.7584, 2014.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not have any comments on limitations and societal impact. Please see \"Main Review\" for the detailed reviews.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Zw9B7WtG-LW", "reviewer": "Reviewer_bP1K", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "Pros:\n- the paper is nicely structured and well-written\n- theoretical analysis for the proposed algorithm on utility is solid\n- empirical study is presented to validate the effectiveness of the proposed algorithm\n\nCon:\n- 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors addressed the limitations ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "AN8n1VRuao", "reviewer": "Reviewer_7UgD", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "Strength:\n1. The paper are well written and presented, and the problem is very important. \n2. The technical parts seem solid. It is good to see that a differentially private federated learning algorithm can handle the heterogeneity of local devices.\n\nWeakness:\nNo major weaknesses. This is a strong submission.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1 hour"}, "extra_text": {}}]

Author rebuttal:

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)