Learning the Privacy-Utility Trade-off
with Bayesian Optimization
Borja Balle

Joint work with B. Avent, J. Gonzalez, T. Diethe and A. Paleyes

Utility
PrivacyTheory vs PracticeO<latexit sha1_base64="9kDpveEaFLU+Unv7fLX8RADi8cg=">AAADgXicbVLbbtNAEN3WXEq4pcAbLxZVpUSKgl1UKKqQKkCUBySKIG2lOIo267Gzynptdsch0coSH8ILX8MrPPIXfAJru0h1wkhrzZ4zF8/smWSCa/S83xubzpWr165v3WjdvHX7zt329r1TneaKwYClIlXnE6pBcAkD5CjgPFNAk4mAs8nsVcmfzUFpnspPuMxglNBY8ogzihYatw/fBwIi7ASRoswE+rNCE7qBSOOO/zgIQSDtFoWRbjCnCjLNRSqLQPF4it1xe8fre5W5645/4ewcvfn64Fv69M/JeHuzH4QpyxOQyATVeuh7GY4MVciZgKIV5BoyymY0BhNDmgCqpUX/uQZhgV94iNMXvseSRvzQupImoEem2krh7lokdKNU2SPRrdBGB5povUwmNjKhONWrXAn+jxvmGB2MDJdZjiBZ3SjKhYupW67YDbkChmJpHcoUt7O5bErtftE+RKML5ALUvDmIqRpmwJroIpecpeHKkhYCF6ioBTVgQrksRzXHXAj3I5W6aO3WhK1YMp3XPOaoe+/s68vesQKYdS9HX55yAXbbPZYsZyOzqFfasoKIrNCqm0mWZd2aMWVcYbz+84Oe1y+Pt28//r7NAau/KtQE64n1nwuQcclnVHEZWnXYUhkWLaswf1VP687pXt9/0vc+WKm9JLVtkYfkEekQnzwjR+QtOSEDwsh38oP8JL8cx+k6nrNXh25uXOTcJw1zDv8C/mMsAg==</latexit>!"d HQ;(R/δ)
nε#Plot from J. M. Abowd “Disclosure Avoidance for Block Level Data and Protection of Confidentiality in Public Tabulations”(CSAC Meeting, December 2018)
22

8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4

In the pseudo-code below, the function clipL (v) acts as the identify if kvk2  L, and otherwise returns (L/kvk2 )v. Thisclipping operation ensures that kclipL (v)k2  L so that the `2 -sensitivity of any gradient to a change in one datapoint in z
is always bounded by L/m.

Example: DP-SGD

Algorithm 4: Differentially Private SGD
Input: dataset z = (z1 , . . . , zn )Hyperparameters: learning rate ⌘, mini-batch size m, number of epochs T , noise variance
Initialize w
0
for t 2 [T ] dofor k 2 [n/m] do
Sample S ⇢ [n] with |S| = m uniformly at random
P
1
2L
2
Let g
I)
j2S clipL (r`(zj , w)) + m N (0,mUpdate w
w ⌘g2, clipping norm L

return w• 5+ hyper-parameters aﬀecting both privacy and utility• For convex problems can be set to achieve near-optimal rates• For deep learning applications we don’t have (good) utility bounds[Bassily et al. 2014; Abadi et al. 2016]

395 Figure 3. Far left, center left: Hypervolumes of the Pareto fronts comp
396 the Adult and MNIST datasets (respectively) by both DPARETO and ran
397 architecture on the MNIST dataset with DPARETO and random sampling,
398 right: Adult dataset DPARETO sampled points and its Pareto front compar
399
MNIST Pareto Fronts
byDesiderata
1.0
400
MLP1
Fig
401
MLP2
0.8
for
402
1. Eﬃcient to compute
0.6
tip
403
Par
0.4
2. 404Use empirical utility measurements
tur
405
0.2
3. Enable fine-grained comparisons
Ad
406
0.0
wa
10
10
10
407
com
408
wh
Figure4.
Left:
Paretofrontsforcombinationsofmodelsand
op409
timizers on the Adult dataset. Right: Pareto fronts for different
priClassification error

Privacy-Utility Pareto Front

0

1

0

1

Problem Formulation
Parametrized Algorithm ClassA = {Aλ : Z → W | λ ∈ Λ}

Eg. DP-SGD

E : Λ → [y- R]

Eg. Expectedclassification
error<latexit sha1_base64="CUn8cS7i9fYIDlg1WBH2pLx6Qzk=">AAADi3icbVLdbtMwGPUafkZh0IHEDVxYmyYNqYoSpokxmLQB07jYxRB0nWiqynW+tlYdJ7KdkcjkWXgArngULoGXwUmKtHRYcnRyzmd/+U7OOOFMac/7tdJybty8dXv1TvvuvbX7DzrrD89VnEoKPRrzWF6MiQLOBPQ00xwuEgkkGnPoj+dvS71/CVKxWHzSeQLDiEwFmzBKtKVGneMgInpGCTdHBT7AgcFHIxNwe0FICryPP+NAx7iPg1f4a/lYSDhgAgenC1yMOpue61ULXwf+AmwebqDWt8c/np6N1ltuEMY0jUBoyolSA99L9NAQqRnlULSDVEFC6JxMwUwhjkDL3LL/oNGQ6S8s1LMD36NRo35goSARqKGp/CnwlmVCPIml3ULjim10IJFSeTS2laUbalkryf9pg1RP9oaGiSTVIGjdaJJybC0rzcYhk0A1zy0gVDI7G6YzIgnV9pc0ukDKQV42BzFVwwRok81SwWgcLpmUcZ1pSSypQEeEiXJUc8I4xx+JUEV7qxbsjaWy/Y5NmVbdU5sD0T2RAPNnV6uvTpmBdbtLo3w+NFltaTsIYWIjV72ZKK9CVCmmrCuM577c63puub1d+/B37RmwSaxKTXD9YP3lHMS01BMimQhtOuxViS7aNmH+cp6ug/Pnrr/jeh9s1N6geq2iJ2gDbSMfvUCH6D06Qz1E0Xf0E/1Gf5w1Z8fZd17Xpa2VxZlHqLGc478R0ytG</latexit>

Error (Utility) Oracle<latexit sha1_base64="yFd9fxwOuuVIYFyEkmawDQxwenc=">AAADW3icbVJda9RAFJ1u/Kix6lapL/owtBQqLCFRilUQih/Uhz5UdNvCJpTZyd3dYWcmYWZSE4b9LeKrPvlzfPC/OEkqNLsOTDg559x7c2/uOOdMmzD8vdbzbty8dXv9jn934979B/3Nh6c6KxSFIc14ps7HRANnEoaGGQ7nuQIixhzOxvN3tX52CUqzTH4xVQ6JIFPJJowS46iL/tYH/BrHxy4gJTg2GR6Fgyi56O+EQdgcvAqiK7BzuI163x7/enpysdkL4jSjhQBpKCdaj6IwN4klyjDKYeHHhYac0DmZgp1CJsCoyrH/oDVQmq8sNbM3UUhFxz9yUBIBOrFNvwu865gUTzLlrjS4YTsViNC6EmPnFMTM9LJWk//TRoWZHCSWybwwIGlbaFJw7OZSDw+nTAE1vHKAUMVcb5jOiCLUuBF3qkDBQV12G7FNwRxoly0LyWiWLg2p5KY0ijhSgxGEybpVe8Q4x5+J1At/txVcxlrZe8+mzOjBsfuvcnCkAObPrruvd1mCm/aAimqe2LIdqR+nMHEr1LxZUdV5W8XWvoUNg1cHgzCob7jvHtG+iwG3WY3VxquB7ZdzkNNaz4liMnXb4VLlZuG7DYuW92kVnD4PohdB+Mmt2lvUnnX0BG2jPRShl+gQfUQnaIgosug7+oF+9v54nud7G621t3YV8wh1jrf1FwsCGbM=</latexit>

Privacy Oracle

P : Λ → [y- ∞)<latexit sha1_base64="oyXPwVlGjlMOWU17+3SHjT4QY0c=">AAADYHicbVJNa9tAEN3Y/XDdj9gt9JD2IBICCRghpYSmhUJoC+khB5fWScAyYb0a2YtXK7E7Si2Eof+kt17b/pxe+0s6klKI7Q6smH3vzYxmdsapkhY97/dGo3nr9p27rXvt+w8ePtrsdB+f2SQzAgYiUYm5GHMLSmoYoEQFF6kBHo8VnI9n70r+/AqMlYn+jHkKo5hPtIyk4EjQZWer77x2glMKCLkTYOIMvV4gdYT5/mVnx3O9ypx1x792do63WePb01/P+5fdhhuEichi0CgUt3boeymOCm5QCgWLdpBZSLmY8QkUE0hiQJMT+s8tEOb4RYY4feN7Il7SD8nVPAY7KqqmF84uIaETJYaORqdClyrw2No8HpMy5ji1q1wJ/o8bZhgdjQqp0wxBi7pQlCmHhlNO0AmlAYEqJ4cLI6k3R0y54QJpzktVIFNgrpYbKaqCKYhldJ5pKZJwZUhzhXM0nEALGHN6F2q1OJFKOZ+4tov2bk1QxpLZey8nEm3vlB5X904MwGz/pvpml3OgafdEnM9GxbweaTsIIaI9qm5FnJd5a6YodYvCc18d9Ty3PN4hffxDigFar0paBOuB9Z8r0JOST7mROqTtoFQpLtq0Yf7qPq07Zweu/8L1PtKqvWW1tdgzts32mM9esmP2gfXZgAn2lX1nP9jPxp9mq7nZ7NbSxsZ1zBO2ZM2tvzIPHBE=</latexit>

Eg. Epsilon for
fixed delta

ErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceErrorPareto-Optimal Points

Privacy Loss
Hyper-parameter SpaceBayesian Optimization (BO)• Gradient-free

optimization for blackbox functions• Widely used inapplications (HPO in
ML, scheduling &planning, experimental
design, etc)

Bayesian Optimization (BO)Input:• Gradient-free

optimization for blackbox functions

Goal:

F:Λ⊂R →Rp<latexit sha1_base64="7mCaJAcfnko16yIWReBdRKtLbmA=">AAADdXicbVLdbtMwFPZafkb56+ASgSzK0JCqLAFNDCTEBIhxsYsN6DZpKZXjnLZWHSeynZHIyuUegXdB4hYegmfgHm5xkiE1LUdydPx95yfn8wkSzpR23Z8rrfaFi5cur17pXL12/cbN7tqtQxWnksKAxjyWxwFRwJmAgWaaw3EigUQBh6Ng9rrkj05BKhaLjzpPYBiRiWBjRom20Ki7+RY/x/6eTQgJ9lUaKNDYj4ieBoF5X3xKsK/jOWDU7bmOWxledrxzp/fy99m9rwe/zvZHay3HD2OaRiA05USpE89N9NAQqRnlUHT8VEFC6IxMwEwgjkDL3KL/XKMh059ZqKcvPJdGjfgT6woSgRqaSokCr1skxONY2iM0rtBGBxIplUeBjSxHUotcCf6PO0n1eHtomEhSDYLWjcYpx1acUlYcMglU89w6hEpmZ8N0SiSh2orf6AIpB3naHMRUDROgTTRLBaNxuCBSxnWmJbGgfauIMFGOanYZ5/gDEarorNeErVgyG2/YhGnV37MvLvq7EmD2aD56fsoMrNp9GuWzoclqSTt+CGO7XNXNRHlZt2ZMGVcY13m23Xed8rhb9uNt2RywO1eFGn85sf5zDmJS8gmRTIR2O2ypRBcdu2He4j4tO4ePHe+J4x64vZ1XqLZVdAfdRxvIQ0/RDnqH9tEAUfQFfUPf0Y/Wn/bd9oP2wzq0tXKecxs1rL35FxbGKAY=</latexit>⋆

λ = argmin F(λ)<latexit sha1_base64="TGEkGqWC2Y2pTh7doXDXE9iPXAA=">AAADiHicbVJdb9MwFPVWPkb56uCRF4tpUidVVQKqtj1MmgpiPOxhCLpNakrlOretVduJ7JvRysof4Jfwa3gF3vkZPOAkRVpbLDk6OefYN/fmjFIpLAbBr63t2p279+7vPKg/fPT4ydPG7rNLm2SGQ48nMjHXI2ZBCg09FCjhOjXA1EjC1Wj2ptCvbsBYkehPuEhhoNhEi7HgDD01bHQj6c0x++wii8zk9IRGiuE0SR0zEyV0PnRLC42EptF5iXP6rrmkD4aNvaAdlItugnAJ9k675HfU+frnYri73Y7ihGcKNHLJrO2HQYoDXxAFl5DXo8xCyviMTcBNIFGAZuHZf9AhzPGLiHF6EgZcrfj7HmqmwA5cOZyc7nsmpuPE+K2RluxKBaasXaiRdxaN23WtIP+n9TMcHw2c0GmGoHlVaJxJigktJk1jYYCjXHjAuBG+N8qnzDCO/n+sVIFMgrlZbcSVBVPgq+w804In8dqQ5hLnaJgnLaBiQhetujMhJf3ItM3r+5XgbyyU5lsxEWhb5z4EunVmAGYHt923u5yDn3aLq8Vs4ObVSOtRDGOft/LNqUVxb6W4wpe7oH181AraxQ46/hF2/BnwMSytLto8WH25BD0p9JQZoWOfDn9VinndJyxcz9MmuHzVDl+3gw9l1Kq1Q16Ql6RJQnJITsl7ckF6hJNv5Dv5QX7W6rWgdlg7rqzbW8szz8nKqnX/Aix3LoY=</latexit>• Widely used inapplications (HPO in
ML, scheduling &planning, experimental
design, etc)λ∈ΛExpensive,
non-convex,
smoothBayesian Optimization (BO)Input:• Gradient-free

optimization for blackbox functions

Goal:

F:Λ⊂R →Rp<latexit sha1_base64="7mCaJAcfnko16yIWReBdRKtLbmA=">AAADdXicbVLdbtMwFPZafkb56+ASgSzK0JCqLAFNDCTEBIhxsYsN6DZpKZXjnLZWHSeynZHIyuUegXdB4hYegmfgHm5xkiE1LUdydPx95yfn8wkSzpR23Z8rrfaFi5cur17pXL12/cbN7tqtQxWnksKAxjyWxwFRwJmAgWaaw3EigUQBh6Ng9rrkj05BKhaLjzpPYBiRiWBjRom20Ki7+RY/x/6eTQgJ9lUaKNDYj4ieBoF5X3xKsK/jOWDU7bmOWxledrxzp/fy99m9rwe/zvZHay3HD2OaRiA05USpE89N9NAQqRnlUHT8VEFC6IxMwEwgjkDL3KL/XKMh059ZqKcvPJdGjfgT6woSgRqaSokCr1skxONY2iM0rtBGBxIplUeBjSxHUotcCf6PO0n1eHtomEhSDYLWjcYpx1acUlYcMglU89w6hEpmZ8N0SiSh2orf6AIpB3naHMRUDROgTTRLBaNxuCBSxnWmJbGgfauIMFGOanYZ5/gDEarorNeErVgyG2/YhGnV37MvLvq7EmD2aD56fsoMrNp9GuWzoclqSTt+CGO7XNXNRHlZt2ZMGVcY13m23Xed8rhb9uNt2RywO1eFGn85sf5zDmJS8gmRTIR2O2ypRBcdu2He4j4tO4ePHe+J4x64vZ1XqLZVdAfdRxvIQ0/RDnqH9tEAUfQFfUPf0Y/Wn/bd9oP2wzq0tXKecxs1rL35FxbGKAY=</latexit>

Expensive,
non-convex,
smooth⋆λ = argmin F(λ)λ∈Λ<latexit sha1_base64="TGEkGqWC2Y2pTh7doXDXE9iPXAA=">AAADiHicbVJdb9MwFPVWPkb56uCRF4tpUidVVQKqtj1MmgpiPOxhCLpNakrlOretVduJ7JvRysof4Jfwa3gF3vkZPOAkRVpbLDk6OefYN/fmjFIpLAbBr63t2p279+7vPKg/fPT4ydPG7rNLm2SGQ48nMjHXI2ZBCg09FCjhOjXA1EjC1Wj2ptCvbsBYkehPuEhhoNhEi7HgDD01bHQj6c0x++wii8zk9IRGiuE0SR0zEyV0PnRLC42EptF5iXP6rrmkD4aNvaAdlItugnAJ9k675HfU+frnYri73Y7ihGcKNHLJrO2HQYoDXxAFl5DXo8xCyviMTcBNIFGAZuHZf9AhzPGLiHF6EgZcrfj7HmqmwA5cOZyc7nsmpuPE+K2RluxKBaasXaiRdxaN23WtIP+n9TMcHw2c0GmGoHlVaJxJigktJk1jYYCjXHjAuBG+N8qnzDCO/n+sVIFMgrlZbcSVBVPgq+w804In8dqQ5hLnaJgnLaBiQhetujMhJf3ItM3r+5XgbyyU5lsxEWhb5z4EunVmAGYHt923u5yDn3aLq8Vs4ObVSOtRDGOft/LNqUVxb6W4wpe7oH181AraxQ46/hF2/BnwMSytLto8WH25BD0p9JQZoWOfDn9VinndJyxcz9MmuHzVDl+3gw9l1Kq1Q16Ql6RJQnJITsl7ckF6hJNv5Dv5QX7W6rWgdlg7rqzbW8szz8nKqnX/Aix3LoY=</latexit>• Widely used inapplications (HPO in
ML, scheduling &planning, experimental
design, etc)

Bayesian Optimization Loop:
Given k evaluations (λR - F(λR ))- X X X - (λk - F(λk ))<latexit sha1_base64="iwGSn4DImkd/v9Z3cKjJVJgXYmk=">AAADgnicbVJfb9MwEPeaAaP8WQcSL/AQbZrUoipKmCaGNKQJEOOBhyHoNqmpKte5tlZsJ7KdkcjqZ0HiG/AteIU3vg1OMqBpOcnR+ff73V3ufJOUUaV9/9dGy9m8cfPW1u32nbv37m93dh6cqySTBAYkYYm8nGAFjAoYaKoZXKYSMJ8wuJjEr0v+4gqkoon4pIsURhzPBJ1SgrWFxp3jbsisOsLjoO++/Xfp9fpuyKJEq777F42XJXGvN+7s+Z5fmbvuBNfO3skuan159O3J2Xin5YVRQjIOQhOGlRoGfqpHBktNCYNFO8wUpJjEeAZmBgkHLQuL/nGNhlx/ppGevwx8whv6oXUF5qBGphrLwt23SOROE2mP0G6FNipgrlTBJ1bJsZ6rVa4E/8cNMz09Ghkq0kyDIHWhacZcnbjljN2ISiCaFdbBRFLbm0vmWGKi7Us0qkDGQF41GzFVwRRIE80zQUkSrQwpZzrXEltQgeaYirJVc0oZcz9ioRbt/ZqwGUum+4bOqH3T9/b5Rf9UAsS9ZfVylznYafcJL+KRyeuRtsMIpnbTqpvhRZm3ZkypWxjfe3HU973y+If2ExzaGLALWElNuB5Y/zkDMSv5FEsqIrsdNlWqF227YcHqPq0758+84MDzP9hVe4Vq20KP0S7qogA9RyfoHTpDA0TQV/Qd/UA/nU3nqRM4B7W0tXEd8xA1zDn+DUsdJ0Q=</latexit>

1. Build a surrogate model for F (eg. Gaussian process)2. Find most promising next evaluation

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

BO: 1-Dimensional Example

HVv† (P) = µ({v 2 R | v v , 9u 2 P u v}), whereµ denotes the standard Lebesgue measure on Rp . Henceforth we assume the anti-ideal point is fixed and drop it fromour notation.

248
249
250
251
252 Larger hypervolume means the points in the Pareto front are
253 closer to the ideal point (0, 0). Thus, HV(PF(V)) provides
254 a way to measure the quality of the Pareto front obtained
255 from the data in V. Furthermore, hypervolume can be usedprivacy-utility
Paretofronthyperparameto designacquisition functions
for selecting
256Findters thatwill improve the Pareto
front. Start by defining the257using
multi-objective
Bayesian
258 increment in the hypervolume given a new point v 2 Rp :259optimization
HV(PF(V)) .
260
PF (v) = HV(PF(V [ {v}))261
Usetransformed
Gaussian
262 This quantity is positive only if v lies in the set ˜ of points
tobymodel
andnon-dominated
PF(V). privacy
Therefore, theprobability of
263processes
improvement
(PoI)
over
the
current
Paretofront
when
se264error
oracles
265 lecting a new hyperparameter can be computed using the
266 model trained on I as follows:
267Acquisition function optimizes
PoI( ) = P[(f1 ( ), . . . , fp ( )) 2 ˜ | I](1)
268
probabilityofZp269hyper-volume basedY( ;al.
vj )dv
270improvement=[Couckuytjet
j ,
2014]
˜
v2
j=1
271
272
4
The anti-ideal point must be dominated by all points in
273 PF(V). See [11] for further details.
274

acquisition function given in Eq. (2) to obtain the next query
point, which is then added into the dataset. This is repeatedk times until the optimization budget is used up. Further
implementation details are provided in Appx. E.1.

The DPareto Algorithm

•

•

•

Algorithm 2: DPARETO
Input: hyperparameter set ⇤, privacy oracle P,
error oracle E, anti-ideal point v † , numberof initial points k0 , number of iterations k,prior GP
Initialize dataset D;
for i 2 [k0 ] do
Sample random point 2 ⇤Evaluate oracles v(P( ), E( ))Augment dataset D
D [ {( , v)}
for i 2 [k] do
Fit a GP to the transformed privacy using D
Fit a GP to the transformed utility using D
Optimize the HVPoI acquisition function in
Eq. (2) using anti-ideal point v † and obtain a
new query point
Evaluate oracles v(P( ), E( ))Augment dataset D
D [ {( , v)}
return Pareto front PF({v | ( , v) 2 D}))b(see Appx. A for

Example: Sparse Vector Technique[Lyu et al. 2017]6000

25
20
4000

15

1

0

1

2

10

2000

10

10

1

10

0

10

1

10

2

F1

10

2

10

1

10

0

10

1

10

2

30

Pareto inputs

25
20

0.6

0.2

0.4

5

0.0
10

0

b

10

1

10

2

0.0

15
10

0.2

10 1

100

101

"

102

0.2

1

1.0
0.8

0.4

0.0

b

Pareto front

0.6

0.0

b

0.4

10

0.2
5

2

0.8

15
10

5

0.6

1

0.6
0.4

0.8

2

C

Lap(b1 )

C

20

3
4000
Setup
15
The split15 used by the algorithm
is basedon the privacy budget

2

0.8

6000

20

sensitivity
110
allocationsuggested
inoutput,[26, Section
4.2].
• 100 queries
10 with 0/1
2000
return 1 (randomly selected)• 10% queries
5
5
analysis• Privacy: SVT
10
10
10
10
10
10
b over 50 runs)• Error: 1 - F-score (avg.

1.0

25

25

20

30

8000

F1

1

F1

30

C

return 25w"

1

Algorithm 1: Sparse Vector Technique
Input: dataset z, queries q1 , . . . , qm
Hyperparameters: noise b, bound Cmc0, w(0, . . . , 0) 2 {0, 1}
1/3
b1
b/(1 + (2C) ), b2
b b1 , ⇢for i 2 [m] do⌫Lap(b2 )1
if qi (z) + ⌫
+
⇢
then
2
wi
1, c
c+1
1
" then return w
if
c
C
30
30
8000

F1

-

1

1

.

2/3

C

-

)(1 + (2C)C-

P0 = (1 + (2C)
more details).

1/3

10 2

10 1

100

b

101

102

0

Example: Sparse Vector Technique
0.8

6000

0.6

0.2

5
10

0

10

1

10

2

10

1.0

2

10

1

10

30

30

25

25

0.8

0.4

0.0

15
10

0.2
5

10

1

10

2

10

100

2
10
0
10

1

5

0.8
0.6

1000

10 2 1 10 1 2 100
10
10

"

b

101

102 2
10

10 1

102

b

10

2

10
0.2

5
10 2 010b

10 1

101 10

0

b

1
10102

102

0.2

100 1
10

100 1
10

101

b

10

2 10

0.4

0.2

0.2

0.0

0.0

2

3.5
3.0

25

2.5

20

True Pareto
Empirical Pareto
Observation outputs
Non-dominated set ˜

0.4

HVPoI

30

0.6
0.4

2

b

15
0.4

110

10

0.8

20

2000

101

5

1.0

25

3000

100 2
10

0.6

15

1000

Pareto front

30

6000

10 1 1
10

"

0.0

10 1

5

0.6

10

C

C

15

0.0
2

0

4000

10

0.2

7000

20

0.6

C

F1
1

0.4

5

0.0

15 3000
10 2000

0.2

F1 (predicted)
Pareto 1inputs

5000

20

0.6

0.4

b

C

0.8

15

2.0
15
1.5
10

1.0

5

0.5

Next location

0.0

0.0
101

102

"

0.8

0.8

20

20

0.0

b

Pareto front" (predicted)

5000

1.0

4000

F1

10

1

25

0.6

1

10

5
2

6000

10

10

2000

25

0.8

15
0.4

10

25

C

4000

15

30

20

20

C

C

20

30 7000

F1

25

C

25

30

1

1.0

1 inputs
F1 (predicted)
Pareto

C

30

8000

Pareto "front(predicted)

F1

30

F1

1

1

"

10 2

10 1

100

b

101

102

Implementing the Oracles
Privacy Oracle• Epsilon for fixed delta / Others DP variants / Attacks success metrics• Closed-form expression / Numerical calculation (eg. moments accountant)Error Oracle• Fixed input / Distribution over inputs / Worst-case (over a set of) inputs• On expectation / With high probability• Exact expression / Empirical evaluation

Implementing the Oracles
Privacy Oracle• Epsilon for fixed delta / Others DP variants / Attacks success metrics• Closed-form expression / Numerical calculation (eg. moments accountant)Error Oracle• Fixed input / Distribution over inputs / Worst-case (over a set of) inputs• On expectation / With high probability• Exact expression / Empirical evaluation

Machine Learning Experiments• Adult dataset (n=40K, d=123)• Logistic regression (SGD and ADAM)• Linear SVM (SGD)

1.0

LogReg+SGD
LogReg+ADAM
SVM+SGD

0.275
0.250
0.225
0.200
0.175
0.150
10

1

10

0

"

Adult Pareto Fronts

1.0

LogReg+SGD
LogReg+ADAM
SVM+SGD

0.275

Classification error

0.300Classification error• MNIST dataset (n=60K, d=784)• MLP1 (1000 hidden)• MLP2 (128-64 hidden)

Adult Pareto Fronts
Classification error

Classification error

0.300

0.250
0.225
0.200
0.175
0.150
10

1

10

"

0

MNIST Pareto Fronts
MLP1
MLP2

0.8
0.6
0.4
0.2
0.0

10 1

100

"

101

MNIST P

0.8
0.6
0.4
0.2
0.0

10 1

DPareto vs Random Sampling

Evolution

Hypervolume Evolution

0.24

LogReg+SGD Samples
1500 RS
256 BOADAM (BO)GD (RS)

8.0
MLP1 (RS)
MLP1 (BO)

7.5

MLP2 (RS)GD (BO)

0.6
0.4
0.2

MLP2 (BO)
7.0

200

0.8

0.0
0

100

Sampled points

200

Classification error

ADAM (RS)8.5Classification error

SGD (BO)

PF hypervolume

9.0

SGD (RS)

ints

1.0

MLP2 Pareto Fronts

Initial+256 RS+256 BO

0.22

0.20

0.18

0.16

10 1

100

"

101

10 1

100

"

101

Conclusion• Empirical privacy-utility trade-oﬀ evaluation enables application-specificdecisions• Bayesian optimization provides computationally eﬃcient method torecover the Pareto front (esp. with large number of hyper-parameters)

Future work:• Address leakage in Pareto front (when error oracle is input-specific)• Include further criteria (eg. running time of parametrized algorithm)