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, wowwwlowwoooo @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)- (xx)))
(1)
in which (x) & (A(x, (e(xxxe)) 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 fe+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))((P)
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 10 to all agents: w.iit
(gN)-'Enen nnt II Note that Loint results
from the concatenation of the vectors from all sub-regions: w.
(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 () = xPmax 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(H) (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, 9n
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
(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 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.11,,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 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-prieas 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. Wen, and B. He. Federated learning systems: Vision, hype and reality for data privacy and protection. urXiv:1907009699 2019.
Z.
[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-1123 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": "pFo8M_gFJq", "reviewer": "Reviewer_Hm8b", "summary": "This paper proposes an approach to build differential privacy (DP) into federated bayesian optimization, in which users try to find high performing values (e.g. hyper-parameters) for a given scoring function (e.g. accuracy of a trained model) by sampling new values to try from the posterior of a Gaussian process mapping the values to their score. The proposed algorithm adapts an existing federated solution to make it amenable to the typical approach to making iterative procedures DP, imports input space splitting heuristics to improve both utility and privacy, and analyse the worst case utility guarantee of the approach.\n", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies and important setup, in which users privately cooperate to solve local hyper-parameter tuning with reduced computational costs. The technical solution is not very novel in the sense that the mapping of existing federated bayesian optimization schemes to popular iterative DP schemes is fairly straight forward, but the results are good. The paper would gain to expanding some of the contributions further.\n\nFor the clipping value p. 6, does the bound have to depend on $\\varphi_{max}$, or could it be on something like $|| \\varphi ||_2$, which should be smaller?\n\nWhat are the assumptions under which the utility guarantee is derived? It would be nice to state and discuss them in the core of the paper, or at least in the appendix in a more centralized fashion before the proofs.\nThe utility guarantee also seems to mostly ignore (even degrade) due to the federated approach,  and hence mostly rely on local GP results. This is a bit disappointing, as in practice the federated part is supposed to help. It’d be useful to see an analysis of when the federated learning can improve utility, and under which conditions it happens.\n It would also be nice to at least add the intuition of why the utility guarantee holds despite averaging other contributions in the core of the paper, and a discussion of why this is useful in practice (and when it might not be), as opposed to the typical approach of choosing a contribution at random.\n\nWhat is the finial outcome for each client? Do they just keep their last posterior, and the federated approach was used exclusively to guide sampling/exploration? If that is indeed the case, it would be useful to show the computational improvement empirically in the evaluation (that is, when does TS reaches the same level of performance as FTS, or at least the DP versions). The evaluation should then give the epsilon/delta values used is different experiments, and this could be contrasted with the computational gains. \n\nIn the evaluation, it would be interesting to see more complex problems (e.g. deep learning hyper-parameter tuning). How will the proposed solution fare under higher dimensional input spaces? Similarly, what data sizes / change in the local loss can be supported before improvements vanish?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5h"}, "extra_text": {}}, {"review_id": "h9oOwGWNxJ5", "reviewer": "Reviewer_Tavh", "summary": "\n\nThe paper studies the Bayesian optimization problem in the differentially private federated learning setting. The authors integrate DP into the federated Thompson sampling (FTS) algorithm and  propose a distributed exploration technique to accelerate exploration in the early stages.\n", "questions": "", "limitations": "", "rating": 5, "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": "Clarity: Though the paper is generally well written, the writing of the algorithm part can be improved. I find it hard to fully understand the algorithm.\n\nStrong points:\nThe DP extension of FTS is of interest to the ML community though I do not know much about Bayesian Optimization.\n\nWeak points:\nThe paper does not have sufficient algorithmic novelty compared to the prior work [10], and the extension to the DP setting seems to be straightforward under the DP-FedAvg framework. The privacy guarantee comes from DP-FedAvg directly, and the utility guarantee builds upon the proof from [10]. From my understanding, the main novelty compared to [10] is the distributed exploration. \n\nThe second concern is about the correctness of privacy guarantees. On page 3 line 113, the authors claim that ``all participating agents share the same set of random features follow [10]’’. However, [10] assumes sharing the first layer of a neural network between all clients (see Appendix A in [10]), which violates the privacy requirement. \n\nGiven the limited algorithmic novelty and the privacy guarantee issues (please correct me if my understand is wrong), I tend to reject the paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "f27gU1vgGe1", "reviewer": "Reviewer_PjxP", "summary": "This paper proposes a differentially private version of FTS-DE algorithm. Theoretically, the authors provide not only the privacy guarantee of the proposed algorithm, but also provide the privacy-utility trade-off. Experimentally, the impact of different parameters is verified. The results match the privacy-utility trade-off theorem in the theoretical section.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Since I am not an expert in Federated Learning or Bayesian Optimization. My evaluation focus on the differential privacy part of this paper.\n\nThe main theorems of this paper express clear messages about the proposed algorithms. With this theorem, engineering scientists can set their desired privacy level according to the utility requirement, which is meaningful.\n\nThe related works are not well-discussed. There is a lot of literature on federated learning + DP. For example,\n1. Federated learning with differential privacy: Algorithms and performance analysis\n2. Local differential privacy-based federated learning for internet of things\n3. Personalized federated learning with differential privacy\n4. A hybrid approach to privacy-preserving federated learning\nHow is your work related to/different from those works?\n\nI tried my best to understand the BO and FBO part in the background section, but I am still not able to understand them. In line 95, what does $f_{t+1}$ means and how is it related with the objective function $f$?  In line 100, how is the random feature $\\phi$ generated? It seems like $\\phi$ is a function of $x$ and cannot be totally at random. In the FBO, the notation $f^{n}$ also looks confusing. How is it related with $f_t$ and $f$? I totally gave up on understanding the settings of FBO here.\n\n\n--------------------------\nI have read the feedback from the authors. I will change my score from 4 to 5 because writing is not a big problem for the expert in the community of FL, but I think the presentation still needs to be improved if the authors seek broader impacts.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think there is no potential negative social impact of their work", "review_text": "", "extra_scores": {"ethical_concerns": "I think there are no ethical concerns about their work", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "9j0MJuwLiU", "reviewer": "Reviewer_PEdv", "summary": "This paper propose DP-FTS-DE, the first differentially private federated Bayesian optimization protocol. To augment FTS with DP, the paper introduces a centralized server and tweaks the workflow so that the protocol follows a similar pipeline like FL. Hence, the standard process of clipping and adding noise can be used to add DP. The paper also evaluate the proposed protocol both theoretically and empirically. The empirical results show that the information from other clients accelerates convergence.", "questions": "", "limitations": "", "rating": 6, "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": "The work augments FTS with DP by modifying the FTS workflow and applying standard process of clipping and adding noise. It further introduces distributed exploration to accelerate convergence.\n\nThe idea of distributed exploration is innovative and works well as shown in the evaluation. The novelty on the privacy side is limited because the standard process is directly applied. The tweak on the BO side to enable the direct application, on the other side, is not trivial but also not very challenging.\n\nThe paper is complete, providing both theoretical utility guarantee and empirical evaluation.\n\nThe paper is well-written and easy to follow. \n\nSome minor points:\n(1) In the evaluation, the privacy budget is as high as 20. Such high privacy cost does not provide strong privacy guarantee. Is it possible to achieve similar performance with smaller privacy budget?\n(2) I am not sure if the comparison in the evaluation is fair. Seems the federated version has access to more data points? How does it compare to centralized version with all the data points? It will be good to provide it as a baseline to compare with.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper combines differential privacy with federated Bayesian optimization using the federated Thompson sampling algorithm. We appreciate this research direction, but find that the paper falls below the (high) bar for NeurIPS for a combination of the following reasons.
- The technical novelty of the contribution is limited. The proposed algorithm uses the now standard approach to differentially private federated learning of reducing the problem to iteratively averaging vectors, clipping them, and adding Gaussian noise. The privacy and utility analyses seem to closely mirror prior work.
- Several reviewers were uncertain how to interpret the main utility guarantee (Theorem 1) and its various parameters. This was clarified by the author response, but concerns remain. In particular, it shows limited improvement over the baseline of local learning. Thus the significance of the contribution is not sufficiently clear.
- The clarity of the exposition needs to be improved. The problem setup and motivation for this work are not adequately explained. A high level issue is that the introduction focuses on *algorithms* instead of discussing the *problems* that they are meant to solve.
Decision: Accept (Poster)