Hyperparameter Tuning with Renyi Differential Privacy
Authors: Nicolas Papernot
Thomas Steinke
Venue: ICLR 2022 Oral (2022)
Keywords: differential privacy
hyperparameter tuning

Abstract: For many differentially private algorithms, such as the prominent noisy stochastic gradient descent (DP-SGD), the analysis needed to bound the privacy leakage of a single training run is well understood. However, few studies have reasoned about the privacy leakage resulting from the multiple training runs needed to fine tune the value of the training algorithm’s hyperparameters. In this work, we first illustrate how simply setting hyperparameters based on non-private training runs can leak private information. Motivated by this observation, we then provide privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Our results improve and extend the work of Liu and Talwar (STOC 2019). Our analysis supports our previous observation that tuning hyperparameters does indeed leak private information, but we prove that, under certain assumptions, this leakage is modest, as long as each candidate training run needed to select hyperparameters is itself differentially private.

Published as a conference paper at ICLR 2022
HYPERPARAMETER TUNING WITH RENYI DIFFERENTIAL PRIVACY
Nicolas Papernot
Thomas Steinke"
Google Research, Brain Team rxpernotee google le com
Google Research, Brain Team
wewerr@ttmmssssseeee net
ABSTRACT
For many differentially private algorithms, such as the prominent noisy stochastic gradient descent (DP-SGD), the analysis needed to bound the privacy leakage of single training run is well understood. However, few studies have reasoned about the privacy leakage resulting from the multiple training runs needed to fine tune the value the training algorithm's 's hyperparameters. In this work, we first illustrate how simply setting hyperparameters based on non-private training runs can leak private information. Motivated by this observation, we then provide privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Our results improve and extend the work of Liu and Talwar (STOC 2019). Our analysis supports our previous observation that tuning hyperparameters does indeed leak private information, but we prove that, under certain assumptions, this leakage is modest, as long as each candidate training run needed to select hyperparameters is itself differentially private.
INTRODUCTION
Machine learning (ML) systems memorize training data and regurgitate excerpts from it when probed (Carlini et al. 2020). If the training data includes sensitive personal information, then this presents unacceptable privacy risk (Shokri et al., 2017). It may however still be useful to apply machine learning to such data, e.g., in the case of healthcare (Kourou et al. 2015) Wiens et al. 2019). This has led to significant body of research learning methods. Differential privacy (DP) (Dwork et al. 2006b a) provides a robust and quantitative privacy guarantee. It has been widely accepted as the best framework for formally reasoning about the privacy guarantees of a machine learning algorithm.
the development of preccceeeeeeiingggg machine
A popular method for ensuring DP is noisy (stochastic) gradient descent (a.k.a. DP-SGD) (Song it al. 20133: Bassily et al.] 2014 Abadi et al., 2016). DP-SGD differs from standard (stochastic) gradient descent in three ways, First, gradients are computed on per-example basis rather than directly averaged across minibatch of training examples. Second, each of these individual gradients clipped to ensure its 2-norm bounded. Third, Gaussian noise added to the gradients as they are averaged and applied to update model parameters. These modifications bound the sensitivity of each update so that the added noise ensures differential privacy. The composition (Dwork et al., 2010) and privacy amplification by subsampling (Balle et al. 2018) properties of differential privacy thus imply that the overall training procedure is differentially private. We can compute tight privacy loss bounds for DP-SGD using techniques like the Moments Accountant (Abadi al. 2016) the closely related framework of Rényi DP (Mironov) 2017 Mironov et al. 2019).
Machine learning systems have hyperparameters, such as the learning rate, minibatch size, or choice of a regularizer to prevent overfitting. Details of the model architecture can also be treated as hyperparameters of the optimization problem. Furthermore, learning within the constraints of differential privacy may introduce additional hyperparameters, as illustrated in the DP-SGD optimizer by the 2-norm bound value for clipping, the scale of the Gaussian noise, and the choice of stopping time. Typically the training procedure is repeated many times with different hyperparameter settings in order to select the best setting, an operation known as hyperparameter tuning. This methodology implies that even if each run of the training procedure is privacy-preserving we need to take into
Alphahetical author order.

---

Published as a conference paper at ICLR 2022
account the fact that the training procedure is repeated (possibly many times) when reasoning about the privacy of the overall learning procedure.
Can the tuning of hyperparameetess reveal private information? This question has received remarkably little attention and, in practice, it is often ignored entirely. We study this question and provide both positive and negative answers.
1.1 OUR CONTRIBUTIONS
We show that, under certain cireumstances, the setting of hyperparamters can leak private information. Hyperparameters are narrow channel for private information to leak through, but they can still reveal information about individuals if we are careless. Specifically, if we tune the hyperparameters in an entirely non-private fashion, then individual outliers can noticeably skew the optimal hyperparameter settings. This is sufficient to reveal the presence or absence of these outliers à la membership inference (Shokri et al. 2017); it shows that we must exercise care when setting hyperparameters.
We provide tools for ensuring that the selection of hyperparameters is differentially private. Specifically, if we repeat the training procedure multiple times (with different hyperparameters) and each repetition of the training procedure is differentially private on its own, then outputting the best repetition is differentially private. Of course, a basic version of such a result follows from the composition properties of differential privacy (that is the fact that one can "sum" the privacy loss bounds of multiple differentially private analyses performed on the same data to bound the overall privacy loss from analyzing this data). However, we provide quantitatively sharper bounds.
Specifically. our privacy loss bounds are either independent of the number of repetitions or grow logarithmically in the number of repetitions, whereas composition would give linear bounds. Rather than repeating the training procedure a fixed number of times, our results require repeating the training procedure a random number of times. The privacy guarantees depend on the distribution of the number of runs; we consider several distributions and provide generic results. We discover a tradeoff between the privacy parameters and how heavy-tailed the distribution of the number of repetitions is.
1.2 BACKGROUND AND RELATED WORK
Differential privacy (DP) is a framework reason about the privacy guarantees of randomized algorithms which analyze data (Dwork et al. (2066] a). An algorithm is said to be DP if its outputs on any pair of datasets that only differ on one individual's data are indistinguishable. A bound on this indistinguishability serves as the quantification for privacy. Formally, a randomized algorithm M x" + +V's is (s, 6)- if for any imputs x, x' E X differing only on the addition, removal, or replacement of one individual's 's records and for any subset of outputs S C V. we have
PP [Mx) E S] S (M(()) E S]+
Here, the parameter is known as the privacy loss bound the smaller is, the stronger the privacy guarantee provided is, because it is hard for an adversary to distinguish the outputs of the algorithm on two adjacent inputs. The parameter 8 is essentially the probability that the guarantee fails hold. One of the key properties of DP is that it composes: running multiple independent DP algorithms is also DP and composition theorems allow us bound the privacy parameters of such sequence of mechanisms in terms of the individual mechanisms' privacy parameters (Dwork& & Roth 2014).
There is vast literature on differential privacy in machine learning. popular tool is the DP-SGD optimizer (Abadi et al. 2016). Because the noise added is Gaussian and DP-SGD applies the same (differentially private) training step sequentially, it easier to reason about its privacy guarantees in the framework of Rényi differential privacy (Mironov] (017). Rényi differential privacy (RDP) generalizes pure differential privacy (with 8 = 0) as follows. An algorithm M said to be (A, (A,E)-RDP with > >1 1 and 0, if for any adjacent inputs x, x
1 DA (M( = - log E M())
(PM (PM(a') -Y
SE
(2)
where D (PI(Q) is the Rényi divergence of order À between distributions P and Q. In the framework of RDP, one obtains sharp and simple composition: If each individual mechanism M, is (), RDD.
2

---

Published as a conference paper at ICLR 2022
then the composition of running all of the mechanisms on the data satisfies (A, E, E4) RDD.. For instance, the privacy analysis of DP-SGD first analyzes the individual training steps then applies composition. Note that it is common to keep track of multiple orders X in the analysis. Thus should be thought of as a function e (A), rather than a single number. In many cases, such as Gaussian noise addition, this is linear function i.e., <(A) = p À for some p R and such linear bound yields the definition of zero-Concentrated DP with parameter (p-zCDP) (Bun & Steinke 2016))
One could naively extend this composition-bast approach to analyze the privacy of training algorithm which involves hyperparameter tuning. Indeed, if each training run performed to evaluate one candidate set of hyperparameter values DP, the overall procedure is also DP by composition over all the hyperparameter values tried. However, this would lead to very loose guarantees of privacy. Chaudhuri & Vinterbo (013)) were the first to obtain improved DP bounds for hyperparameter tuning, but their results require stability property of the learning algorithm. The only prior work that has attempted to obtain tighter guarantees for DP hyperparameter tuning black-box fashion the work of Liu & Talwar 2019). Their work is the starting point for ours.
Liu & Talwar (2019) show that, if we start with (e, O)-DP algorithm, repeatedly run it a random number of times following a geometric distribution, and finally return the best output produced by these runs, then this system satisfies (3e, -)differrential privacy| [
Liu & Talwar (2019) also consider algorithms satisfying (e, 6D for ò > O. However, their analysis is restricted to the (e. 5) formulation of DP and they do not give any results for Rényi DP. This makes it difficult to apply these results modern DP machine learning systems, such as models trained with DP-SGD.
Our results directly improve on the results Liu & Talwar (2099). We show that replacing the geometric distribution on the number of repetitions in their result with the logarithmic distribution yields (2e, -)-differential privacy as the final result. We also consider other distributions on the number of repetitions. which give a spectrum of results. We simultaneously extend these results to the Rényi DP framework, which yields sharper privacy analyses.
Independently Mohapatra et al. (2021) study adaptive hyperparameter tuning under DP with compo- sition. In contrast, our results are for non-adaptive hyperparameter tuning, i.e., "random search."
closely related line of work is on the problem of private selection. Well-known algorithms for private selection include the exponential mechanism (McSherry & Talwar) 2007) and the sparse vector technique (Dwork al., 2009 Zhu & Wang, 2020). However, this line of work assumes that there is low-sensitivity function determining the quality of each of the options. This is usually not the case for hyperparameters. Our results simply treat the MI. algorithm as black box; we only assume that its output is private and make no assumptions about how that output was generated. Our results also permit returning the entire trained model along with the selected hyperparameters.
2 MOTIVATION
A hyperparameter typically takes categorical values (e.g., the choice of activation function in a neural network layer), or is single number (e.g., real number for the learning rate or integer for the number of epochs). Thus, it is intuitive that a hyperparameter provides little capacity as a channel to leak private information from the training data. Nevertheless, leakage can happen, in particular when training is done without preserving privacy. We illustrate how with the constructed example of hyperparameter tuning for a support vector machine learning (SVM) learned from a synthetic data distribution. We consider a SVM with soft margin; we use stochastic gradient descent to minimize the corresponding objective involving the hinge loss and weight penalty:
(x, u) = || + a max(0, 1 - y(w x xx+00 b)}
where y E 1- indicates the label of training example E R2. Because our purpose here is to illustrate how leakage of private information can arise from hyperparameter tuning, we work with synthetic data distribution for simplicity of exposition: we draw 40 inputs from isotropic 2D Gaussians of standard deviation 1.0 to form the training set D. The negative class is sampled from a Gaussian centered at p-1 (7.86, 3.36) and the positive μl = (6.42, -9.17).
Our learning procedure has a single hy hyperparameter a controlling how much importance is given to the hinge loss, i.e., how much the SVM is penalized for using slack variables to misclassify some of
Liu & Talwar 2019 prove several other results with slightly different formulations of the prohlem, but this result representative and is most relevant to our discussion here.
3

---

Published as a conference paper at ICLR 2022
the training data. We first tune the value of a with the training set D and report training accuracy as a function of a in Figure I Next, we repeat this experiment on a dataset D' to which we added 8 outliers 2, (7.9, -8.0) to the negative class. The resulting hyperparameter tuning curve is added to Figure By comparing both curves, it is clear that the choice of hyperparameter a which maximizes accuracy differs in the two settings: the best performance is achieved around = 8 with outliers whereas increasing a is detrimental to performance without outliers.
This difference can be exploited to perform variant of a membership inference attack (Shokri al. 2017): Here, one could infer from the value of the hyperparameter a whether or not
1.00
no outtlers outtlers
0.55
Moxell accuracy
the outlier points Io were part of the training set or not. While the example is constructed, this shows how we must be careful when tuning hyperparameters: in corner cases such the one presented here, it possible for some infor- mation contained in the training data to leak in hyperparameter choices.
0.80
m
0.75
0.70
066
Regulerzzatio parameter
In particular, this implies that the common prac- tice of tuning hyperparameters without differen- tial privacy and then using the hyperparameter values selected to repeat training one last time with differential privacy is not ideal. In Sec- tion 3 we will in particular show how training with differential privacy when performing the different runs necessary to tune the hyperparameter can bound such leakage effectively if one carefully chooses the number of runs hyperparameters are tuned for.
Figure 1: Accuracy of the model as a function of the regularization weight a, with and without outliers. Note how the model performance exhibits a turning point with outliers whereas increasing the value of is detrimental without outliers.
3 OUR POSITIVE RESULTS
3.1 PROBLEM FORMULATION
We begin by appropriately formalizing the problem of differentially private hyperparameter tuning, following the framework of Liu & Talwar (219). Suppose we have m randomized base algorithms M2,... Mm : X" + D. These correspond to m possible settings of the hyperparameters. Ideally we would simply run each of these algorithms once and return the best outcome. For simplicity, we consider finite set of hyperparameter possibilities; if the hyperparameters of interest are continuous, then we must pick a finite subset to search over (which is practice sufficient).
Here we make two simplifying assumptions: First, we assume that there is total order on the range V, which ensures that "best" well-defined. particular, we are implicitly assuming that the algorithm computes quality score (e.g., accuracy on test set) for the trained model it produces; this may require allocating some privacy budget to this evaluation P Second, we are assuming that the output includes both the trained model and the corresponding hyperparameter values (i.e., the output of M, includes the index j) These assumptions can be made without loss of generality.
3.2 STRAWMAN APPROACH: REPEAT THE BASE ALGORITHM A FIXED NUMBER OF TIMES
The obvious approach to this problem would be to run each algorithm once and to return the best of the m outcomes. From composition, we know that the privacy cost grows at most linearly with m. turns out that this is in fact tight. There exists (s, D)-DP algorithm such that if we repeatedly run it m times and return the best output, the resultant procedure is not (ms - T, 0)-DP for any T > O. This was observed by Liu & Talwar 2019 Appendix B) and provide an analysis in Appendix D.I This negative result also extends to Rényi DP. To avoid this problem, we will run the base algorithms random number of times. The added uncertainty significantly enhances privacy. However, must carefully choose this random distribution and analyze it.
IIf the trained model's quality is evaluated the training set, then must increase the privacy loss budget account for this composition. However, if the model evaluated held set, then the privacy budget need not split; these data points are "fresh" from privacy perspective.
NNote that in the more well-studied prohlem of selection, usually we would only output the hyperparameter values (i.c., just the index j) and not the corresponding trained model its quality score.
4

---

Published as a conference paper at ICLR 2022
3.3 OUR ALGORITHM FOR HYPERPARAMETER TUNING
To obtain good privacy bounds, we must run the base algorithms a random number of times. We remark that random search rather than grid search is often performed in practice (Bergstra & Bengio 2012), so this not a significant change in methodology. Specifically, we pick a total number of runs K from some distribution. Then, for each run A 1,2, K, pick index ja [mi] uniformly at random and run M Then, at the end, we return the best of the K outcomes.
The privacy guarantee of this overall system then depends on the privacy guarantees of each of the mechanisms Mj as well as the distribution of the number of runs K. Specifically, we assume that there exists uniform (Rényi) DP bound for all of the mechanisms M,. Note that DP is "convex" where "convexity" here means that if M₁ M2 ... Mn are each individually DP, then running Mj for random j&s E [m]] is also DP with the same parameters.
2 To simplify notation, we also assume that there is a single mechanism Q 2 + y that picks a random index j E [m]] and then runs M,. In essence, our goal is to "boost" the success probability of Q by repeating it many times. The distribution of the number of runs K must be chosen to both pick good setting of
ensure good privacy guarantees and ensure that the system is likely hyperparameters. Also, the overall runtime of the system depends on K and we want the runtime to be efficient and predictable. Our results consider several distributions on the number of repetitions K and the ensuing tradeoff between these three considerations.
3.4
MAIN RESULTS
There are many possible distributions for the number of repetitions K. In this section, first consider two the truncated negative binomial and Poisson distributions and state our main privacy results for these distributions. Later, in Section 3.5 we state a more general technical lemma which applies to any distribution on the number of repetitions K.
Definition 1 (Truncated Negative Binomial Distribution). Let E (0. 1) and nj E (-1, Define distribution P on 21,2.... follows. If # and K is drawn from Dacy then
E P[K= - (1
{++
(3)
e+1
E=
and E [K] y-(1-7) --
If K is drawn from Da.y- then
(1 7k
[KK- = k] k log(1 (1/7)
(4)
and TE [K]
1/y-1 (og()
This is called the "negative binomial distribution," since II:
2+1 = ((*2-1) if we extend the
definition of binomial coefficients to non-integer 1). The distribution is called "truncated" because P KK = 0] = O, whereas the standard negative binomial distribution includes in its support. The n 0 case Do,- is known as the "logarithmic distribution". The 1 case Di,7 is simply the geometric distribution. Next, we state our main privacy result for this distribution.
Theorem 2 (Main Privacy Result - Truncated Negative Binomial). Let Q : X + be a randomized
algorithm satisfying (X,s)-RDP and (), (RDP)- for some ê 2 0, E o.), and À E [1,x)) ) Assume y is totally ordered.
Let y E (-1,00) and y E 10, Define an algorithm A 2 + y as follows. Draw K from the truncated negative binomial distribution D (Definition) 7.. Run Q(x) repeatedly K times. Then A(x) returns the best value from the K runs.
Then A satisfies (>,E')-RDP where
e +=+((++)) (1-
++ (1+m) m) 1og(1/7) log [K]
(5)
'If Ā = 1, then é corresponds the KI. divergen;; see Definition in this case, so is irrelevant.
9 However, és multiplied by 1 1 1/ = 0
5

---

Published as a conference paper at ICLR 2022
Rend vvergance (b, (400AAX11
10
halve ropetttionn
Remp sereee (D) (ww.//A
Logerithemic n
Geometiic n=1
(unrepeated)
10a
3-
K- (naive repetttion)
<1K] 10
K-1 (unrepcotedi
10
=100
1000
X 10 Inaive repetition)
Legarithmic
10'
X]K]
2/K] 100000
cIK] 10 g=5
=IK]- Goometric f=1
10-
EIK) 1000000
ElK] 10 Paisson
107
40
Renyl
Beeryli
Figure 2: Rényi DP guarantees
Figure 3: Rényi DP guarantees
Figure 4: Privacy versus ex- pected number of repetitions using different distributions or naïve composition. Rényi DP guarantees are converted to ap- proximate DP - i.e., we plot such that we attain (e, 10 --DP The base algorithm is 0.1-zCDP.
from Corollary D for various ex-
for repetition using different dis- tributions or naive composition with mean 10, with 0.1-zCDP base algorithm.
pected numbers of repetitions of
the logarithmic distribution (i.e.,
truncated negative binomial with
=
0), compared with base al-
gorithm (0.1-zCDP) and naïve composition.
Theorem 2 shows a tradeoff' between privacy and utility for the distribution Pno of the number of repetitions. Privacy improves as 17 decreases and y increases. However, this corresponds to fewer repetitions and thus lower chance of success. We will study this aspect in Section 3.6,
Theorem 2 assumes two RDP bounds, which makes it slightly hard to interpret. Thus we consider two illustrative special cases: We start with pure DP (a.k.a. pointwise DP) i.e., (E, 6DP with d = 0, which is equivalent to (po,e) ED-DP. This corresponds to Theorem 2 with X 30 and Å - co. Corollary (Theorem 2 for pure DP). Let Q X - y be a randomized algorithm satisfying
(e, DD. Let 1) (-1, oc) and y E (0, 1). Define A X + Y as in Theorem 2 Then A satisfies
((2 + n),, D).
Our result is generalization of the result of Liu & Talwar 2019) they show that, if K follows a geometric distribution and Q satisfies (e. 0)-DP, then satisfies (3r, 0)-DP. Setting 7) = 1 in Corollary recovers their result. If we set 7 < then obtain improved privacy bound.
Another example is if Q satisfies concentrated DP (Dwork & Rothblum 2016 Bun & Steinke 2016).
This is the type of guarantee that is obtained by adding Gaussian noise to a bounded sensitivity function. In particular, this is the type of guarantee we would obtain from noisy gradient descent F
Corollary 4 (Theorem 2 for Concentrated DP). Let 2 - y be randomized algorithm satisfying p-2CDP - i.e., (λ, p Ré-Rén DP for all > 1. Let n E (-1, oo) and y E (0, 1). Define A: x y and K D as in Theorem Assume p log(1/7) Then A satisfies (), (,,g")-éény)
DP for all X > 1 with
2 pvp
p log (E KT) + 2(1 +
- np
if S +
log ( [K]
p. (- + - log (E [K]) + 2(1 + 17) plog(1/7) - mp if > 1
log (E [K)
Figure 2 shows what the guarantee of Corollary 4 looks like. Here we start with 0.1-zCDP and perform repetition following the logarithmic distribution (17 = 0) with varying scales (given by 7) and plot the Rényi DP guarantee attained by outputting the best of the repeated runs. The improvement over naive composition, which instead grows linearly, is clear. We also study other distributions on the number of repetitions, obtained by varying 7), and Figure 3 ggives a comparison. Figure shows what these bounds look like if we convert to approximate ODP with 5 10-6
Remark 5. Corollary uses the monotonicity property of Rényi divergences: Xf < Ag then DA, (PI(Q) < Dx, (P(Q) (Van Erven & Harremos 2014 Theorem 3), Thus (>2, RDD implies
(A1,e) (h,e)-RI -RDP for any X S X2. In particular, the hound of Theorem 2 yields e' - DG as X 1, so we use monotonicity to bound s' for small X.
Note that the privacy of noisy stochastic gradient descent, (DP-SGD) is not well characterized by concentrated DP Bun al. 2018). but, for our purposes, this is close enough approximation.

---

Published as a conference paper at ICLR 2022
Poisson Distribution. We next consider the Poisson distribution, which offers a different privacy- utility tradeoff than the truncated negative binomial distribution. The Poisson distribution with mean
f 0 is given by P [ A] c 1e" for all Is O. Note that IP K = 0 e 0 here, whereas the truncated negative binomial distribution does not include 0 in its support. We could condition on K here too, but we prefer stick with the standard definition. We remark that (modulo the issue around P [K = O) the Poisson distribution is closely related to the truncated negative binomial distribution. If we take the limit as 77 + oo while the mean remains fixed, then the negative binomial distribution becomes Poisson distribution. Conversely, the negative binomial distribution can be represented as a convex combination of Poisson distributions or as a compound of Poisson and logarithmic; see Appendix for more details.
Theorem 6 (Main Privacy Result - Poisson Distribution). Let Q x 7 y be a randomized algorithm satisfying (X,E)-RDP and (É. DD for some X E (1, and E, E, 8 2 O. Assume y is totally ordered. Let μ >
Define an algorithm A : xx + Y as follows. Draw K from a Poisson distribution with mean i.e., P [KK k] en. 1. n² for all l 2 Run (zz) repeatedly K times. Then A(x) returns the best value from the K runs. If K = 0, A(z) returns some arbitrary output independent from the input x.
If e 1 x-1 then A satisfies (X, -RDP where
e' = + p 6+ log 1
x 1
The assumptions of Theorem 6 are different from Theorem We assume a Rényi DP guarantee and an approximate DP guarantee on Q, rather than two Rényi DP guarantees. We remark that a Rényi DP guarantee can be converted into an approximate DP guarantee (A,e)-RDP implies (é, 8DD for all É 2 and e(A-1)(f-c)) 1 (1 - -))=1 (Mironov 2017 Canonne et al. 2020). Thus this
statement can be directly compared to our other result. We show such a comparison in Figure 3 and
Figure 4 The proofs of Theorrms 2
and 6 are included in Appendix B.2
3.5 GENERIC RÉNYI DP BOUND FOR ANY DISTRIBUTION ON THE NUMBER OF REPETITIONS
We now present our main technical lemma, which applies any distribution the number of repetitions K. Theorems 2 and 6 are derived from this result. It gives a Rényi DP bound for the repeated algorithm in terms of the Rényi DP of the base algorithm and the probability generating function of the number of repetitions applied to probabilities derived from the base algorithm.
Lemma 7 (Generic Bound). Fix À >> 1. Let K be a random variable supported on N U (0). Let f: :0, 1] - R. be the probability generating function of -ie.e,, f(x) : Ex P = k) h/hh
Let Q and Q' be distributions on y. Assume y is totally ordered. Define a distribution A on y as follows. First sample K. Then sample from independently K times and oulput the best of these samples 6 This output is a sample from A. We define A' analogously with Q' in place of Q. Then
DA (AIIA) DA (Q112)
x-1 log (f'(a)* f'()))->))
(6)
where applying the same postprocessing to Q and Q' gives probabilities q and of respectively - i.e. there exists an arbitrary function g y [0, 1) such that q
E
[g(X)] and o' x- lo (X))
x+Q
The proof of this generic bound is found in Appendix B.1 To interpret the theorem, we should imagine adjacent inputs I, x' X²,, and then the distributions correspond the algorithms run on these inputs: A = A(x), A' = A(z'), ) Q = Q(x). and Q' Q(z'). The bounds on Rényi divergence thus correspond to Rényi DP bounds. The derivative of the probability generating function x K-| is somewhat mysterious. A first-order intuition is that, if q q' then f'(g)> 1' (q) (1) E [K] and thus the last term in the bound (6) is simply
fz)(z) = E
K
K[ A second-order intuition that q = q' by DP and postprocessing and, if f is smooth, then f(()) s f'(d') and the first-order intuition holds up to these approximations. Vaguely, f' being smooth corresponds to the distribution of K being spread out (i.e., not point mass) and not too
'If K= 0, the output be arbitrary, as long as it is the same for both A and A'.
7

---

Published as a conference paper at ICLR 2022
1.0
12000
hatre repation
Lugenthmiic
0.36
0.9
0.8
0.94
Polwan
0.92
Expeted soande
A- 0.5
Success probabloo
Logaritimic 9=0
logarishmic distrsstion
0.5.5
geometti: disr burinn
0.6
Geometrig
0.58
nogotlive b binomla (j= 05
poisson datr busoon
Poisson
0.00
baseline tron- prizatt search)
0.5
0.0
Privacy for (r, 001-07
Privacy lass bound e for In. 10 D61-DP
Privacy budget
Figure 5: Expected quantile of the repeated algorithm A as function of the final privacy guarantee (e, 10 1 DDP for vari- ous distributions K, where each invocation of the base algorithm Q is 0.1-2CDP.
Figure 6: Final success prob-
Figure Accuracy of the CNN model obtained at the end of the hyperparameter search, for the different distributions on the number of repetitions K we con- sidered. We report the mean over 500 trials of the experi- ment.
ability (6) of the repeated algo- rithm A as function of the final privacy guarantee (s, 1006000000 D-DP for various distributions, where each invocation of the base algo- rithm Q has a 1/100 probability of success and is 0.1-zCDP.
heavy-tailed (i.e. K is small most of the time). The exact quantification of this smoothness depends on the form of the DP guarantee = g'.
In work, primarily compare three distributions on the number of repetitions: point mass (corresponding to naïve repetition), the truncated negative binomial distribution, and the Poisson distribution. A point mass would have polynomial as the probability generating function i.e., if P P[K = k] = 1, then fx) = [ x The probability generating function of the truncated negative binomial distribution (Definition is
(w) = K K+D D.
[x.K]
-
(1-(1=))))
log i-
i
(7)
if =
The probability generating function of the Poisson distribution with mean μ is given by f(x)
(1)(2=11, We discuss probability generating functions further in Appendix A.2
3.6 UTILITY AND RUNTIME OF OUR HYPERPARAMETER TUNING ALGORITHM
Our analytical results thus far, Theorems 2 and and Lemma 7 provide privacy guarantees for hyperparameter tuning algorithm A when it is used with various distributions repetitions K. We now turn to the utility that this algorithm provides. The utility of a hyperparameter search is determined by how many times the base algorithm (denoted Q in the theorem statements) is run when we invoke the overall algorithm (A). The more often Q is run, the more likely we are to observe good output and A is more likely return the corresponding hyperparameter values. Note that the number of repetitions K also determines the algorithm's 's runtime, so these are closely linked.
the number of
How does this distribution on the number of repetitions K map to utility? As first-order approxi- mation, the utility and runtime are proportional to E [K]. Hence several of our figures compare the different distributions on based on a fixed expectation and Figure plots E []] on the vertical axis. However, this first-order approximation ignores the fact that some of the distributions we consider are more concentrated than others; even if the expectation is large, there might still significant probability that K is small. Indeed, for 1) < 1, the mode of the truncated negative binomial distribution K 1. We found this to be an obstacle to using the (truncated) negative binomial distribution in practice in our experiments, and discuss this further in Appendix A.2.
We can formulate utility guarantees more precisely by looking at the expected quantile of the output to measure our algorithm's 's utility. If we the base algorithm Q once, then the quantile of the output (by definition) uniform on [0, 1] and has mean 0.5. If we repeat the base algorithm a fixed number of times k. then the quantile of the best output follows Beta 1) distribution, of k independent uniform random variables. The expectation in this case is A
is the maximum
K If
8

---

Published as a conference paper at ICLR 2022
repeat random number of times K, the expected quantile of the best result is given by
K
[ x (xxx)==== -1 (()dde
E
R
(8)
K ++1
K+1
E [x is the probability generating function of K; see Appendix A.2.1 for further details. Figure 5 plots this quantity against privacy. We see that the Poisson distribution performs very well in an intermediate range, while the negative binomial distribution with 7) = 0.5 does well we want strong utility guarantee. This means that Poisson is best used when little privacy budget available for the hyperparameter search. Instead, the negative binomial distribution with 1j - 0.5 allows us to improve the utility of the solution returned by the hyperparameter search, but this only holds when spending a larger privacy budget (in our example, the budget has to be at least = 4 otherwise Poisson is more advantagcous). The negative binomial with r7 -0.5 does very poorly.
where f(x)
From a runtime perspective, the distribution of K should have light tails. All of the distributions we have considered have subexponential tails. However, larger 1) corresponds better concentration in the negative binomial distribution with the Poisson distribution having the best concentration.
Experimental Evaluation. To confirm these findings, apply our algorithm to a real hyperpa- rameter search task. Specifically, we fine-tune the learning rate a convolutional neural network trained on MNIST. We implement DP-SGD in JAX for an all-convolutional architecture with stack of 32, 32, 64, 64, 64 feature maps generated by 3x3 kernels. We vary the learning rate between 0.025 and on a logarithmic scale but fix all other hyperparameters: 60 epochs, minibatch size of 256, & clipping norm of 1, and noise multiplier of 1.1. In Figure 7 we plot the maximal accuracy achieved during the hyperparameter search for the different distributions considered previously as a function of the total privacy budget expended by the search. The experiment is repeated 500 times and the mean result reported. This experiment shows that the Poisson distribution achieves the best privacy-utility tradeoff for this relatively simple hyperparameter search. This agrees with the theoretical analysis we just presented above that shows that the Poisson distribution performs well in the intermediate range of utility, this is simple hyperparameter search.
CONCLUSION
Our positive results build on the work of Liu & Talwar (019) and show that repeatedly running the base algorithm and only returning the best output can incur much lower privacy cost than naïve composition would suggest. This however requires that we randomize the number of repetitions, rather than repeating a fixed number of times. We analyze a variety of distributions for the number of repetitions, each of which gives different privacy/utility tradeoff.
While our results focused on the privacy implications of tuning hyperparameters with, and without, differential privacy, our findings echo prior observations that tuning details of the model architecture without privacy to then repeat training with DP affords suboptimal utility-privacy tradeoffs (Papernot al. 2020); in this work, the authors demonstrated that the optimal choice of activation function in neural network can be different when learning with DP, and that tuning it with DP immediately can improve the model's utility at no changes to the privacy guarantee. We envision that future work will be able to build on our algorithm for private tuning of hyperparameters to facilitate privacy-ave searches for model architectures and training algorithm configurations to effectively learn with them.
Limitations. We show that hyperparameter tuning is not free from privacy cost. Our theoretical and experimental results show that, in the setting of interest, the privacy parameter may double or even triple after accounting for hyperparameter tuning, which could be prohibitive. In this case, one compromise would be to state both privacy guarantees that of the base algorithm that does not account for hyperparameter tuning, and that of the overall system that does account for this. The reader may wonder whether our positive results can be improved. In Appendix [ we explore give some intuition for why they cannot (casily) be improved. We also note that our results are only immediately applicable to the hyperparameter tuning algorithm from Section 3.3 Other algorithms, in particular those that adaptively choose hyperparameter candidates will require further analysis.
Finally, among the distributions on the number of repetitions K that we have analyzed, the distribution that provides the best privacy-utility tradeoffs will depend on the setting. While it is good to have choices, this does leave some work to be done by those using our results. Fortunately, the differences between the distributions seem to be relatively small, so this choice is unlikely to be critical.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY & ETHICS STATEMENTS
Reproducibility. We give precise theorem statements for our main results and we have provided complete proofs in the Appendix, as well as all the necessary calculations and formulas for plotting figures. We have also fully specified the setup required to reproduce experimental results, including hyperparameters. Our algorithm is simple, fully specified and can be easily implemented.
Ethics. Our work touches privacy, which is an ethically sensitive topic. If differentially private algorithms such as ours are applied to real-world sensitive data, then potential harms to the people whose data is being used must be carefully considered. However, our work is not directly using real-world sensitive data. Our main results are theoretical and our experiments use either synthetic data or MNIST, which is standard non non-private dataset.
ACKNOWLEGMENTS
The authors would like to thank the reviewers for their detailed feedback and interactive discussion during the review period. We also thank our colleagues Abhradeep Guha Thakurta, Andreas Terzis, Peter Kairouz, and Shuang Song for insightful discussions about differentially private hyperparameter tuning that led to the present project, as well as their comments on early drafts of this document.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. arXiv preprint arXiv:1807.01644 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEFE, 2014.
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. SIAM Journal on Computing. (0):TOCC163777, 2021.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 1-10, 2014.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86, 2018.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. arXiv preprint arXiv:2004.00010, 2020.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song. Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. arXiv preprint arXiv:2012.07880 2020.
10

---

Published as a conference paper at ICLR 2022
Kamalika Chaudhuri and Staal A Vinterbo. A stability- -bsed validation procedure for differentially private machine learning. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran As- sociates, Inc., 2013. URL https: http::ss/////ooeeennggosss nerggssneeurre neurips cc/pappe//0..///11... 2668545daa42dk5 4 25a4b1747633888
pdf
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations
and Trends in Theoretical Computer Science, 933-4)2111-00 2014.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint
1rXiv:1003.01877 2016.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privaey via distributed noise generation. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284, Springer, 2006b.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 381-390, 2009.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pp. 51-60. IEEE, 2010.
Konstantina Kourou, Themis Exarchos, Konstantinos P Exarchos, Michalis Karamouzis, and Dim- itrios I Fotiadis. Machine learning applications in cancer prognosis and prediction. Computational and structural biotechnology journal, 13:8-17, 2015.
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, pp. 298-309, 2019, URL
https: http://xww...rr//a//111111111
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE
Symposium on Foundations of Computer Science (FOCS'07, pp. 94-103. IEEE, 2007.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275, IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. R) enyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:1908, 10530, 2019.
Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. The role adaptive optimizers for honest private hyperparameter selection. arXiv preprint arXiv:21 1.04906, 2021.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint arXiv:2007. 14191, 2020.
Ryan Rogers and Thomas Steinke. A better privacy analysis of the exponential mech- anism. DifferentialPriiacy.org 07 2021. httpss//ddfferrenaaallivvvyy///
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp.
245-248. IEEE, 2013.
Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 552-563. IEEE, 2017.
11

---

Published as a conference paper at ICLR 2022
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. 1EEE Transactions on Information Theory, 60(7):797-33200, 2014.
Jenna Wiens, Suchi Saria, Mark Sendak, Marzyeh Ghassemi, Vincent X Liu, Finale Doshi-Velez, Kenneth Jung, Katherine Heller, David Kale, Mohammed Saeed, Pilar N. Ossorio, Sonoo Thadaney- Israni, and Anna Goldenberg. Do no harm: a roadmap for responsible machine learning for health care. Nature medicine, 25(9):1337-1340, 2019.
Yuqing Zhu and Yu-Xiang Wang. Improving sparse vector technique with renyi dif- ferential privacy. In Advances in Neural Information Processing Systems 33 pre- proceedings (NeurIPS 2020), 2020. URL https:://ppp::r: nips.com cC/ cttpppppp/2p./////////// Baa1///9f..aatSrrSSADDDDEEEEEE.B wwteer-bbtttttt.eae html
A FURTHER BACKGROUND
A.1 DIFFERENTIAL PRIVACY RÉNYI DP
For completeness, we provide some basic background on differential privacy and, in particular, Rényi differential privacy. We start with the standard definition of differential privacy:
Definition 8 (Differential Privacy). A randomized algorithm M : X - ) is (c,8) -)dffffrrentilll private if. for all neighhouring pairs of inputs x, x' E X and all measurable S s,
P (x) E S) S ef P[M(2') E)
When O, this is referred as pure (or pointwise) differential privacy and we may abbreviate (e, DD to E-DP. When 8 >> 0, this is referred to as approximate differential privacy.
The definition of pure DP was introduced by Dwork et al. (2006b) and approximate DP was introduced by Dwork et al. (2006a). Note that the notion of neighbouring datasets is context-dependent, but this often glossed over. Our results are general and be applied regardless of the specifics of what is a neighbouring dataset. (However, we do require symmetry - i.e., if (xr, x²) are a pair of neighbouring inputs, then are (x'x).) Usually two datasets are said be neighbouring if they differ only by the addition/remova or replacement of the data corresponding to a single individual. Some papers only consider addition or removal of a person's 's records, rather than replacement. But these are equivalent up to factor of two.
In order to define Rényi DP, we first define the Rényi divergences:
Definition 9 (Rényi Divergences). Let P and Q be probability distributions on a common space Ω. Assume that P absolutely continuous with respect to Q i.e., for all measurable S C if Q(S)= = O, then P(S) = O. Let P(x) and Q(x) denote the densities of P and Q respectively! 7 The KL divergence from P to Q is defined as
(P(X))
P((x)
D1 (PII)) = E
log
P(x) log
dz.
X
5n
Q(x)
The max divergence from P to Q is defined as
Dx (PIIQ) = sup { log
P(S)
P(S) > >0}-
of
Q(S)
For A E o1), the Rényi divergence from to Q of order À is defined as
1
(P(X)) ((()))
DA (PI())
--1 log
E x
1
(((x)
'1)
E log
((())
X-Q
1
log (L, (()))(())) - dd)
dx)
"n general, we can only define the ratio ((x)/((x) to be the Radon-Nikk Nikodym derivative of P with respect to Q. To talk about P(z) and Q(z) separately we must assume some base measure with respect to which these are defined. In most cases the base measure is either the counting measure in the case of discrete distributions or the Lesbesgue measure in the case of continuous distributions.
12

---

Published as a conference paper at ICLR 2022
We state some basic properties of Rényi divergences; for further information see, e.g.. Van Erven & Harremos (2014). Lemma 10. Let P.Q. P', and Q' be probability distributions. Let À E [1, oo). The following hold.
Non-negativity: D, (PIIQ) 2 O.
Monotonicity & Continuity: D (PIIQ) is continuous and non non-decreasing function of X.
Data processing inequatity (a.k.a. Postprocessing): Let (P) denote the distribution ob- tained by applying some (possibly randomized) function to a sample from P and let [(Q) denote the distribution obtained by applying the same function to a sample from Q. Then Dx (f(P)))(((2) & (PI)Q).
Finite case suffices: We have Dx (PIQ) = (F())(((())))( even when f is re- stricted to functions with finite range.
Chain rule (a.K.a. Composition): Dx (P x P') Dx (PI[) + Dx (P)) where P x P and Q x Q' denote the product distributions of the individual distribu- tions.
The function (P.Q) + (PII)) convex for all E (1, The function (P,Q) - Dx (PI)Q) convex if and only if x 1.
Convexity:
Now we can state the definition of Rényi DP (RDP), which due to Mironovv (2017).
Definition 11 (Rényi Differential Privacy). A randomized algorithm M X + y is Rényi differentially private for all neighbouring pairs of inputs x, E X", DA (M(z)) I
closely related definition is that of 7ero-concentrated differential privacy (Bun & Steinke 2016) (which based on an earlier definition (Dwork & Rothblum 2016) of concentrated differential privacy that does not refer to Rényi divergences).
Definition 12 (Concentrated Differential Privacy). A randomized algorithm M : X - is PDDCDP if. for all neighbouring pairs of inputs x, x' E X and all X E (1, o0), Dx (M(z)) S P.A.
Usually, we consider family of (A, = =(A)) guarantees, where e(A) is function, rather than single function. Concentrated DP is one example of such family, where the function is linear, and this captures the behaviour of many natural algorithms. In particular, adding Gaussian noise to bounded sensitivity function: If f X - R2 has sensitivity i..., llf()) f(z') ( I|2 < for all o
neighbouring 2, x and M 2 Rd is the algorithm that returns a sample from N (((z))
then satisfies - -CDP.
We can convert from pure DP to concentrated or Rényi DP as follows (Bun & Steinke 2016).
Lemma 13. If M satisfies (e, -)-diferrent privacy, then M satisfies ee - i.e., (2, 1 22) RDP for all X E (1, oc).
Conversely, we can convert from concentrated or Rényi DP to approximate DP as follows al. 2020).
(Canonne
Lemma 14. M satisfies (A,E)-RDP, then M satisfies (DDD) where 2 0 is arbitrary and
exp((A 1)(E =))
(1-1) 1 A-1
A.2 PROBABILITY GENERATING FUNCTIONS
Let K be a random variable supported on U {0}. The probability generating function (PGF) of K defined by
f(x) = E [ =
K - k2 rh.
k=
The PGF f(x) is always defined for x E [o, 1]. but may or may not be defined for x > 1. The PGF characterizes K. In particular, we can recover the probability mass function from the derivatives of
13

---

Published as a conference paper at ICLR 2022
the PGF (hence the name):
(()) k!
P [K k]
where (z)) denotes the hthh derivative of f() and, in particular, PIK = 0] = f(0). We remark
that is is often easiest to specify the PGF and derive the probability distribution from it, rather than vice versa; indeed, we arrived at the truncated negative binomial distribution by starting with the PGF that we want and then differentiating.
We can also easily recover the moments of K from the PGF: We have ff xf-k -k f. (e- - 1) (L- 2). (e k + 1). In particular, f(1) E [1] and f'1 = [K] and
(1) EK((K - 1)]. Note that the PGF is rescaling of the moment generating function (MGF)
g(() := E [eek]] f(e').
The PGF can be related to the MGF in another way: Suppose A is a random variable on [0. oo). Now suppose we draw K <- Poisson( A). Then the PGF of K is the MGF of A i.e., E
E
[x*]]
[eA](x-1]] = g(x - 1), where y is the MGF of A. In particular,
A K (Aisson()))
drawn from Gamma distribution, then this would yield K from negative binomial distribution
which has a PGF of the form (x) = (اتس
Note that our results work with a truncated
negative binomial distribution, which is negative binomial conditioned on K * 0. This corresponds to an affine rescaling of the PGF, namely fINB(x)-
(sm(z))fun(U) SNu fxa
We can also obtain a negative binomial distribution as a compound of a Poisson distribution and a logarithmic distribution. That is, if we draw 7 from Poisson distribution and draw K1, K.. Kr independently from logarithmic distribution, then K Ei= K, follows a negative binomial distribution. The PGF of the logarithmic distribution is given by fK, (x) = E [. (0
log(7)
and the PGF of Poisson is given by fx = E [=-] = (z-(x1) Hence
T
= [fk, (x))² frlfk. (x)) = exp ( logg(1 - (1 7)x)
-1))
(x) = E I
=
E
II
E K
log(7)
which is equivalent to fNB (I) = ( (1-(1-))w) with r)= = 1og(1/")-
Finally remark that can also the PGF to show convergence in probability. In particular,
lim [Z 0- 84F
lim
))
lim 1 14 (x (1)
c1(x-1)
y
77
Wep
wep
That is, if take the limit of the negative binomial distribution as 7 oc but the mean p = 1] و
remains fixed, then we obtain a Poisson distribution. If we take 7) - O, then fNB(I) + 1, which is to say that the negative binomial distribution converges to point mass at 0 77 - 0. However, the truncated negative binomial distribution converges to a logarithmic distribution as - 0.
A.2.1 PROBABILITY GENERATING FUNCTIONS AND UTILITY
Recall that in Section 3.6 we analyzed the expected utility and runtime of diffferent distributions on the number of repetitions K. Given our discussion of probability generating functions for these distributions, we can offer an alternative perspective on the expected utility and runtime.
Suppose each invocation of Q has probability 1/m of producing a "good" output. This would be the case if we are considering m hyperparameter settings and only one is good-where here we consider the outcome to be binary (good or bad) for simplicity and what is good or bad is determined only by the total order on the range y' and some threshold on the quality score (e.g., accuracy). Then A has probability
8 = 1- P [A(c) E Bad] =
E P [((()) E Bad] []] = 1 E 11- (1- 1/m) = 1- f(1 [1 - 1/m) K
'The PGF of Binomial(n, is f() (1 p pr) This expression is similar to the PGF of the negative binomial, except the negative binomial has negative exponent.
14

---

Published as a conference paper at ICLR 2022
of outputting good output, where f(x) E [x*] is the probability generating function of the distribution. If we make the first-order approximation f(1 1/m) & f(1) (1) 1/m = 1 - TE. [K]/m, then we have 3 xs E [K]/m, m. In other words, for small values of 1 1/m, the probability of success is amplified by multiplicative factor of E [K].
However, the above first-order approximation only holds for large m and, hence, small overall success probabilities B. In practice, we want B R 1. The different distributions (Poisson and truncated negative binomial with different values of 17) have very different behaviours even with the same expectation. In the regime where want the overall success probability to be high (i.e., 3 x 1), smaller v performs worse, because the distribution is more heavy-tailed. The best performing distribution is the Poisson distribution, which is almost as concentrated naïve repetition. Figure show the success probability 3 as a function of the final (e, 10 D-DP guarantee. This demonstrates that there is a tradeoff between distributions.
More generally, we can relate the PGF of K to the expected utility of our repeated algorithm. Let X IK be random variable corresponding to the utility of one of the base algorithm Q. E.g. X could represent the accuracy, loss, AUC/AUROC, or simply the quantile of output. Now let Y E R be the utility of our repeated algorithm A which runs the base algorithm Q repeatedly K times for random K. That is, Y = max (X1, ... Xx) where X1, "..... are independent copies of X. Let odf x (x) = P [X S 2|| and
cdly (x) = PY S = FPI
x) 1 [(eff
K
is the PGF of the number of repetitions K. Assuming for the moment that X is a continuous random variable, we can derive the probability density function of Y from the cumulative distribution function:
where f(x) E k
(xf = dz cdfx = dr f(edf (x)) = f'(cfxx (2)) pdfx(x))
This allows to compute the expected utility:
B / x pdf (x)
/ x f'ddfx (z)) pdf (x)dr = E f f'(cfxx
In particular, hence, x (x) = x and pdf (x) = for x E [0, 1]. Integration by parts gives
compute the expected quantile 8 in which case X is uniform on [0, 1] and,
EV S/" x- x-)'(r) S/' ( do ( - f())dr = 15(1) 110)00000000 L ((=)d==1-) f( (()dd.
Note that
[ f(x)do= fooddd-[[""<eeee ===
[
x
da
=
E
K
Finally, we also want to ensure that the runtime our hyperparameter tuning algorithm is well- behaved. In particular, we wish to avoid heavy-tailed runtimes. We can obtain tail bounds on the number repetitions from the PGF or MGF too: For all >> O, we have
P K 2 A: P (K- > 1
E
[k)]
f(et) .
Thus, if the PGF f(x) = E [ is finite for some I = e² >> 1, then we obtain subexponential tail bound on K.
B PROOFS FROM SECTION 3
B.1 PROOF OF GENERIC BOUND
Proof of Lemmal 7 We assume that ) is finite set and that IP KK 0] = 0: this is, essentially,
without loss of generality Denote Q(S v) := Eyey Hly < w) Q(y") and similarly for Q(< v)
Our proof can be extended to the general case. Alternatively, if y is infinite, quantities arbitrarily well with finite partition; see Lemma or Van Erven Harremos (004 Theorem 10).
approximate the relevant
15

---

Published as a conference paper at ICLR 2022
and analogously for Q' in place of Q. For each y V we have
A(v) Σ PlK= = kt] (Q(5 v)*h Q(= 8)
k=1
f(Q(S v)) - f(Q(< v)
(ISS))
(Q(Ev) ('(x)d
Q(1)
[((X)]
x 3x-14sa)) trilee
and, likewise, A'(u) = QQ())
E
['(X')].
Thus
unthem
((A=1)Dx(allA)) Σ A(v)* -((1)t~
NEY
Σ Q(v) Q((1)~~
E
[f(X))
E x-R11E))
[f(x'))
yEY
Σ Q()) ('(1)) DEY < (c
[F((X) 1((') [((X)*-((X))) X ((ec))
E
max NEY
X (o (=
The second inequality follows from Hölder's inequality. The first inequality follows from the fact that, for any À E I, the function h (0, oo)2 + (0, oo) given by h(u, v) u. w--2 is convex and, hence, E [V]' 1-> h(E [(U) S E [h(U, [)] = E [U> VI-A] for any pair of positive random variables (U, V). Note that require X to be uniform on [Q(< v), Q(S y)] and X' to be
uniform on [Q'(<< y). Q'( y)]. but their joint distribution can be arbitrary. We will couple them
so that X-Q(sv) X X'=Q'(<x) In particular, this implies that, for each y y, there exists some
Q(3)
t [0, such that
E
((X))~ s f'(((=))) +t + f +t Q')))
x- ("t)).0000 (SS)).
Hence
DA (AIIA) < DA (QI1Q)) +
1
log
max l'(((< v) + ((v)()))* ('(0(<<)) +1 +l. +(-))))))+- wEy tEjo.11
To prove the result, we simply fix y. y and t, E [0, 1] achieving the maximum above and define
y y-
2(v)
l.
if y
if f > D+
B.2 PROOFS OF DISTRIBUTION-SPECE BOUNDS
Truncated Negative Binomial Distribution
Proof of Theorem The probability generating function of the truncated negative binomial distribu-
tion is
(1-(1-9)2) ~-1
if 17 # 0 if 17 0
f(x) =
xx
K =
log(1 2 (1-)))
KrD nm
log(
16

---

Published as a conference paper at ICLR 2022
Thus
T:11: -
if 0 0
[())) = (1 (1 (1- (1-7)z)
if if =0
Tog! 1/7) 1 [K].
= (1- (1-
Now we delve into the privacy analysis: Let Q - Q(x) and Q' Q(x)) denote the output
distributions of Q on two neighbouring inputs. Similarly, let A(x) and A' = ((x') be the corresponding pair of output distributions of the repeated algorithm. By Lemma 7 for appropriate
values q. q [o, 1] and for all X > 1 and all Ả > 1 10
have
DA (AIIA')
< Dx (QIlQ") + X - log (J' (*
DA (QIlQ)) + X log (nrrt2, IE [K] (1-(1 (1-11))) -xctt) (1- (1 7/// (1-)))))---iiiii (1-b))))))))
DA (QII0) + - 1
log (nitt2. E [ ((++ (1 () 4)) (7 (1 - 7)(1 ()) )))))/²
(A== (A 1)(1))((1111 + 7) and (1 - \)v uu= - (1-(11))0+ 2))*)
S DD (Q1lQ)) + x log (yrt1. (r/tt.((]] [K]. (7 + (1 - 7) مع رaر , (1112) " (1--)(1--)))
(1 - q and - are postprocessings of Q and Q' respectively and e! (11 convex and v 22
< Dx (Qll0)) x log (gut2 E [K] (7 + (1 el e 1)D, ()) " .7t))
(7 5 (1 - 7) 9) and S 0)
Dx (QIl0)) X-1 log (7 (7+ (1 - 7) (
_ = log (7 E [K] 77
DA (Q110)) + X-1 ((a 1))D; (Q'11Q) + log (1 (1 (1- (Á- -(-1)Dx(((((0)))
+ x log (7 x TE [K])
D2 (Q11Q") + (1 ++m) m))
D2
1+
i log (1 11 (1-e- (0-(1-1-11-- (1-=-d-3D,(00100)
log (E [K])
1 1+ log(1/7)
(w= (A-1)(1+n) and u -(1 + n)( +1)
+
2-1 +
(1-
1
+ 1+ log
(1 -1- (100--111 + log (TF) [K))
DA (QIl0))+
+ (1)
D3 (Q'1l))
7
--1
(1-1)
1
1 + n
1
log (E [K])
< (Q111))+
D3 (Q'1()+
log
x
Proof of Corollary 4 We assume that Q : X + y is randomized algorithm satisfying p-zCDP
i.e., (X,p- p. A)-Rényi DP for all 1. Substituting this guarantee into Theorem 2 (i.e., setting E = p. and É = p 2) gives that the repeated algorithm A satisfies
for
é' (' (1-2) p. At (1 (1+ log(1/7) log E K
1
This holds for all X E (1, 0o) and all Å E (1)
Ourr proof here assumes Â > 1, but the result holds for Å = too. This can shown either by analyzing this separately or simply by taking the limit Ā + and using the continuity properties of Rényi divergence.
17

---

Published as a conference paper at ICLR 2022
We set Á /log(1/7)/p minimize this expression. Note that assume p log(1/7) and hence this is a valid setting of Å 1. This reduces the expression
E' (1 7)) p 2(1 + n) V p log(117) + log E [K]
This bound is minimized when x-1= Vlog log((E K [ A apply the monotonicity property of Renyi DP (Remark 5 with this optimal X. That is, we obtain the bound
log (E KK)/p. then we can and Lemma 10 and substitute in the bound
e'
p. A
(1 + m) + 2(1 + m)
vp 1og(1/7) log B[K] X-1
A > 1 +
Tog E KK]//
2 log E K + +21++ + 17) v log(1/7) np
if - 1 log [К)/рp
L
Proof of the Poisson Distribution Bound
Proof of Theorem 6 The probability generating function for the Poisson distribution is f(x) =
[<>x] = ex (o(x-11] 1), Thus f'(x) 11 (-ee((r-1) (1) As in the previous proofs, let x and x' be neighbouring
inputs. Denote Q = Qxx). Q' = Q(x')(()))))))))))))))))))))QQ A A(x), and A' A(x). By Lemma
DA (AllA')
S Dx (QIIQ)) + A-1
log (f((g)* -
= (QII') + - log |.. (
1
DA (QIQ)) + 1(1g - (A - 1) 1) + log
2-1
DA (QIQ)) + 1(1 1)(1 4/) - >21 -4)) log
--1
S DA (QIQ)) + 1(1
1) ((E-))(ef(11 9) 8) X(1 (1) log n
x A-1
(by (e, -D assumption Q and since
q and 1 o' are postprocessings)
DA (QI(') + μ (1-9) (ee
A
+ # 8+ log 1
x
< DA (QIQ") + 4- 8+ log A-T'
where the final inequality follows from our assumption that e $ X-I
C CONDITIONAL SAMPLING APPROACH
In the main text, we analyzed the approach where we run the underlying algorithm Q a random number of times according to carefully distribution and output the best result from these independent runs. An alternative approach also studied by Liu Talwar (2019) - is to start with a pre-defined threshold for "good enough" output and to run Q repeatedly until it produces such a result and then output that. This approach has some advantages, namely being simpler and avoiding the heavy-tailed behaviour of the logarithmic distribution while attaining the same kind of privacy guarantee. However, the disadvantage of this approach is that we must specify the acceptance threshold priori. If we set the threshold too high, then we may have keep running for a long time [II
If we set the threshold too low, then we may end up with a suboptimal output.
One solution to avoid an overly long runtime in the case that Q(S) is too small is to modify Q to output 1 with some small probability and then have A halt if this occurs. This would represent failure of the algorithm produce a good output, but would avoid privacy failure.
18

---

Published as a conference paper at ICLR 2022
We analyze this approach under Rényi DP, thereby extending the results of Liu & Talwar (019))
Our algorithm A now works as follows. We start with a base algorithm Q and a set of good outputs S. Now A(x) computes y Qx))) and, if y S, then it returns y and halts. Otherwise, A repeats the procedure. This is equivalent to sampling from a conditional distribution Q(+)[Q(x) E S. The number of times Q is run will follow geometric distribution with mean 1/Q(S).
Proposition 15. Let E (1, Let Q and Q' be probability distributions on 52 with DA (QIIQ") < Let S с 92 have nonzero measure under Q'' and also under Q. Let Qs and Q's denote the conditional distributions of Q and Q' respectively conditioned on being in the set S. That is, (s(E) = Q(E n (S) and (Es(E) (E S)/ (S) for all measurable E c. Sh Then, for all p, E [o] satisfying 1 1/p + 1/9 1/r r = 1, we have
À -- 1/p 1/r
X + 1
1/r +1 A-1 log
DA (QsllQss < 1-1
1/2) (Q11Q))+
D (Q'11))
--
Q(S)
Proof. For E Ω denote the various distributional densities at (relative to some base measure) by Qs(x), Q'((r), Q(r), and ('(x). We have Qs(x) = Qxx) E SI/Q(S) and ('s(x)
('(x)l(z E (S). Now we have
eld (D- [ Qs(x)) Q=()))((())t~~a)
Q(())) I 1| e (1Q()) dx
<Q())~>((S))~) (((t)aa)) 1/8 ( (((a)ae))
1/4
1/r
dx
(Hölder's 's inequality)
= Q(S)))=~((()))))))> (1. (()))-))00(())---)))))))))))))))
1/r
= Q(0)>"((S)) (f Q())) dx:
1/r
(No X 1/9 A := r=r-rrr/p r/p)
S ()D0 (2'1l)) QQ())-11-- (10)))))(1111)))((()))-
(0)))")),0((2))) 1/r
(Postprocessing & non-negativity)
The number of parameters in Proposition 15 is excessive. Thus we provide some corollaries that simplify the expression somewhat.
Corollary 16. Let X, Q Q', S, S, Q's be as in Proposition
15
The following inequalities all hold.
D (QsllQ's) I Da (QllQ') ) + D (Q'1I)).
DA (Qsll(ss < Dx (QllQ') + X 2 (Q-1()) + x -
2
log
x
- 1
Q(S)
A- 2
2
1
DA (Qsll('s E Dx (Qll()) + À - Dx-1 (Q-1()))
+ À 1
log
Q(S)
1
DA (Qsll('s E --1 D (QIlQ)) + DA (Q'lQ)
log
A-1
Q(S)
A-2 2
2 x D2-1
+ 1/r
Vr 21 DA (Qsll('s < D (Q1Q)) +
log
A-1
Q(S)
The first inequality in Corollary 16 is essentially the result given by Liu & Talwar 2019 If Q satisfies E-DP, then A satisfies DP.
Figure plots the guarantee of the second inequality in Corollary 16 when D, (QllQ") = 0. and Da-1 ('I(Q) 0.1 - 1).
19

---

Published as a conference paper at ICLR 2022
D NEGATIVE RESULTS ON IMPROVEMENTS TO OUR ANALYSIS
It is natural to wonder whether our results could be further improved. In this section, we give some examples that demonstrates that quantitatively there is little room for improvement.
D.1 WIIY A FIXED NUMBER OF REPETITIONS DOES NOT RESULT IN GOOD PRIVACY.
We first consider more closely the strawman approach discussed Section 3.2 the base algorithm Q repeated a fixed number of times k and we return the best output. This corresponds to picking from a point mass distribution. To understand why performs so poorly from privacy standpoint, we first apply our main result from Section 3.5 to the resulting point mass distribution.
Point Mass: Suppose K is just point mass i.e., P 1. So A runs the algorithm Q deterministic number of times. Then the probability generating function (PGF) is f(x) - x² and its derivative is fz(x) === Let Q denote the base algorithm. We abuse notation and let Q (z) and Q' = Q=''), where x and x' are neighbouring inputs. Similarly, let A = A(z) and A' = A(r') be the final output distributions obtained by running Q and Q' repeatedly times and returning the best result. We follow the same pattern of analysis that we applied to the other distributions in Theorems 2 a
Lemma gives the bound
Da (AI)4) < DA (QIlQ)) + À
1
log k (1r . -
k- (c(a-1)D, (eAA-1)Dx(Bermt) [|Bem(a')) k-1
S DA (Q11Q))
log
k (c1--))DD((())))) 8-1
S DA (QII0))
log
A-1
log k
k- DD (QIQ))
X 1'
where the final incquality follows from the fact that Bern(q) and Bern(g') are postprocessings of Q and Q' respectively.
This bound is terrible. In fact, it is slightly worse than naïve composition analysis which would give D, A') < DA (Q**) Q* [Q**]|
k DD (QI))). It shows that a deterministic number of repetitions does not yield good privacy parameters, at least with this analysis.
surprising that running the base algorithm Q a fixed number of times i and returning the best output performs poorly from a privacy standpoint. We will now give simple example that demonstrates that this is inherent and not just a limitation of our analysis. Liu & Talwar (0019) Appendix B) give a similar example.
Proposition 17. For all > O, there exists e-DP algorithm Q X + y such that the following holds. Define an algorithm A X + y that runs Q a fixed number of times k and returns the best output from these runs. Then A is not E-DP for any ê < ke. Furthermore, for all X > 1, A is not (X, ((A))-Rény DP for any ()) < EA),, where
k. 1o-log(111 (
s'(2) = kg
Proof. The base algorithm is simply randomized response. We will let y {1,2) with the total order preferring 1, then 2. We will define a pair of distributions Q and Q' on {1,2] and then the base algorithm is simply set so that these its output distributions pair of neighbouring inputs.
We let
1
e
Q
1 lte'
lte
1
Q'
1 ct'
it
20

---

Published as a conference paper at ICLR 2022
Then Do (Qll2) 20 (Q'IlQ) Thus ensure that the base algorithm yielding this pair of distributions is E-DP.
Now look at the corresponding pair of distributions from repeating the base algorithm & times. have
e
1 Ef
A = 1
1 + E0
1
A'
+ c
1
The first part of the result follows:
Itee
Doo (AIAA) 2 log
ka.
I+c7
For all X 1,
((a-1))(a(lla))
e
(1+er) )²)
1
B
1+ ee
chd e6)
Hence
skλ h log(1
+ +ee)
k: loog(1 + t
DA (AII))
kg
2-1
A-1
The second part of Proposition 17 shows that this problem is not specific to pure DP. For À 2 1 1+ 1/E, we have e' E'(x) ((kE), so we are paying linearly in k.
However, Proposition 17 is somewhat limited to pure e-DP or at least (A, (A))--DDD with not-too- small values of A. This because the "bad" event is relatively low-probability. Specifically, the high privacy loss event has probability (1 + e -) This is small, unless e 2 9(log k).
We can change the example make the bad event happen with constant probability. However, the base algorithm will also not be pure e-DP any more. Specifically, we can replace the two distributions Proposition 17 with the following:
Q (1 - 2xp(-11/),
Q'
1 (x)())eex(((a))) -1k), 1/k)).
If we repeat this base algorithm fixed number of times k, then the corresponding pair of distributions given by
A (1 exp (xpp-lp)pcc_ocooe expp(_)))))((())).
A' (1 exp(- -e, 1), exp(-keo keo 1)).
Now we have Doc (Al]A') ke and the bad event happens with probability e1 0.36. On the
other hand, Dxo (Q) = 8o like before, but Dax (Q) log(1 exp( 1/k)) log(1 exp(-1/k)) 2 log(ken + 1). But we still have a good guarantee terms of Rényi divergences. In particular, D2 (Q' (Q) (Eo + 1/k) tog(Ke, + 1), and we can set Eo < o(1/ log k) to ensure that we get reasonable (A, (A))(A))RRD guarantees for small A.
At higher level, it should not be surprise that this negative example is relatively brittle. Our positive results show that it only takes a very minor adjustment to the number of repetitions to obtain significantly tighter privacy guarantees for hyperparameter tuning than what would obtain from naive composition. In particular, rumning a fixed number times & versus running Poisson(k) times not that different, but positive results show that it already circumvents this problem in general.
21

---

Published as a conference paper at ICLR 2022
We also remark that composition behaves differently in the low-order RDP or approx DP regime relative to the pure-DP or high-order RDP regime covered by Proposition 17 Thus the naive composition baseline compare to is also shifting from basic composition (e- (P-DP becomes ke-DP under k-fold repetition (Dwork et al. 2006b)) to advanced composition (s-DP becomes (O(s:
2..0 Proving tightness of basic composition is easy, but proving tightness for advanced composition non convalivial (in general, relies on the machinery of fingerprinting codes (Bun et al. 2014)). This means it is not straightforward to extend Proposition 17 to this regime.
log((1))))) 8)-DP (Dwork et al.
D.2 TIGHT EXAMPLE FOR CONDITIONAL. SAMPLING.
We are also interested in the tightness of our generic results. We begin by studying the conditional sampling approach outlined in Appendix C This approach is simpler and it is therefore easier to give a tight example. This also proves to be instructive for the random repetition approach in Section 3
Our tight example for the conditional sampling approach consists of pair of distributions Q and Q'. These should be thought as the output distributions of the algorithm Q on two neighbouring inputs. The distributions are supported on only three points. Such a small output space seems contrived, but should be thought of representing a partition of large output space into three sets. The first set is where the privacy loss is large and the second set is where the privacy loss is very negative, while the third set everything in between.
Fix t >> 0 and [0, 1/4]. Note (1 (1-2a)-² 2a)-1 S 30 Let
Q = (a la.e a e
Q' (a.e- s-t ,0, - . 5-1)
5 [1,2] C (1,2,3).
1
Qs = 2'2
-- 1
Q's 1 T+e-0-1
Intuitively, the set corresponds to the outputs that (1) have large privacy loss or (2) very negative privacy loss and we exclude (3) the outputs with middling privacy loss. Once we condition on S we still have the outputs (1) with large privacy loss, but that privacy loss is further increased because of the renormalization. Specifically, the negative privacy loss means the renormalization constants very different Q(S)) = a 2e < Q'SS) = a (1 te----t s-t) ) - if is large. In effect, the negative privacy loss becomes positive privacy loss that is added to the already large privacy loss.
22

---

Published as a conference paper at ICLR 2022
12
Dx(QslQ's upper bound
10
(x(Q))') = =
Renyi divergence
8
6
4
2
0
0
5
10
15
20
25
À
Figure 8: Upper and lower bounds for Rényi DP of conditional sampling. For each X. we pick the parameters and f such that D, (QIIQ") Dx (Q'IlQ) 0.1 X and we plot the upper bound from the second inequation Corollary along with the exact value of D, (Qsll
We make the above intuition more precise by calculating the various quantities. For all À > 1, we have
Q(S) 2a c
(A-1)D((Ql(()) -11-(040(1-N) a +a.e e 8d + (1 2a 1.0---99
< a. (A-1)e-s + - +e -2a0
200 22 "A(00=(111 A(1 20)1->
a e(fe--1)-- +a (a(-11)
= (a-e--
(assuming is large)
Q(S) c1-1))1
log (og(2Q((S)
= (1QQ))) $
A-1
(1=11)) = e (1--))((+t))) +a.e - x(1-1) + 2a - -))2->(1 -1---a----7
< a aa + a (A-1) + 30 -ad
= ((-1(11-1)
(assuming is large)
Q(5) a
log (2(((S)))
DA (x(111)) S a
-
23

---

Published as a conference paper at ICLR 2022
((=_)))((_(l(a)) 2- (1 + (0-1)-- (e +
22 ((
Alog 2
Dx (Qs 1Q's) 2 8 +t
--1
We contrast this with our upper bound from the second part of Corollary I6
Da (Qsll0's) < Da (Q110) + X - 2 D2- (Q111) +
2
--1 log
X
Q(S)
S t log(2/((S))
A 2
8 log(2/((S))
2 lo (lgg(1/((S))
8
+ A-1
A-1
A
X 2
2
8 1
À A-1
This example shows that our upper bound is tight up to small factors, namely the lower order terms we ignore with ~ and 2-2
x-1 log 2. Figure illustrates how the upper and lower bounds compare.
D.3 TIGHTNESS OF OUR GENERIC RESULT.
Now we consider the setting from Section 3 where our base algorithm is run repeatedly a random number of times and the best result given output.
Let Q: X - y' denote the base algorithm. Assume Y' is totally ordered. Let K E NN be a random variable and let f(x)
[ K be its probability generating function. Define A Xm + y be the
algorithm that runs Q repeatedly K times and returns the best output.
For tight example, we again restrict our attention distributions supported on three points:
Q (xx) (1 - b - b,,,)).
Q' = Q(=')=)==)))))) = (1-88-6,8'')
A = A(x) (1 -(+
A' = A(x')= (1- +c), ((()))(((()))11
Here the total ordering prefers the first option (corresponding to the first coordinate probability), then the second, and then the third, which implies the expressions for A and A'. Note that the probability values are not necessarily ordered the same way as the ordering on outcomes.
Now we must set these four values to show tightness of our results.
We make the first-order approximation
A ~ (1 - f(b+c), b, f()),
A' ~ (1 f(6' (6)+)) (, ((..)
We take this approximation and get
() 2 (f((c) b)* - (f((')
(A- (1))) (F(E)))
where the final approximation assumes that the second term is dominant in the equation (Qlle)) (1 b- -)> - V
+ (6)) (c) (c)
Contrast this with our upper bound (Lemma 7 which says (A-1)))(A|( < (A- ())l (f(4)) (
where g and q' are arbitrary postprocessings of Q and Q' In particular, that q = e and q' = c'. This is not a formal proof, since we make imprecise approximations. But illustrates that main generic result (Lemma 7 is tight up to low order terms.
set the values so
24

---

Published as a conference paper at ICLR 2022
D.4 SELECTION & LOWER BOUNDS
Private hyperparameter tuning is generalization of the private selection problem. In the private selection problem we are given a utility function u: u x [m]] + R which has sensitivity in its first argument i... for all neighbouring 2, x' E X and all [m]] {1,2, m). we have [u(x,)) j) u(=', .)] & 1. The goal is to output and approximation to arg max u(z,j) subject to differential privacy.
The standard algorithm for private selection is the exponential mechanism (ceSherry & Talwar 2007]. The exponential mechanism is defined by
exp (fu(z,,j)
Vj [m] P[M(x) = Σ Ee|m exp (app551 (5 ())
It provides (s, D)-DP and, at the same time, 2E2DDD (Rogers & Steinke 2021). On the utility side, we have the guarantees
2 log m,
E (u((x,(()) 2
max u(x, jE(m]
2
u(z, M())) 2 max u(x
log
1-
jEIm
for all inputs and all B Bassily et al. 2021 Lemma 7.1) (Dwork & Roth 2014 Theorem 3.1
It is also well-known that the exponential mechanism is optimal up constants. That is, (e, OP selection entails an additive error of (2(log(m)/s) (Steinke & Ullman 2017).
Our results can be applied to the selection problem. The base algorithm (xx) will simply pick an index j E [m]] uniformly at random and the privately estimate u( by adding Laplace or Gaussian noise & and output the pair (j, u(x, ji) E). The total order on the output space [m]] x R simply
selects for the highest estimated utility (breaking ties arbitrarily). If we take to be Laplace noise with scale 1/E, then Q is (e, 0)-
Applying Corollary 3 yields ((2 + m)s, D)-DP algorithm A with the following utility guarantee. Let K be the number of repetitions and let (Jı, u(x, fi) + E)), ... (iK, u(x, jx)) ) + [K) be the outputs from the runs of the base algorithm. The probability that the repeated algorithm A will consider j. ==
arg maxxe(m) (( is P [j. E (ii,... .jj.) }] = - E [[æ_[K] [j. + jx] = - f(1 - 1/m).
K
where f(x) E x is the probability generating function of the number of repetitions K. For each noise sample, we have vk IP [|Exl < t] 1-e for t >> 0. Thus, for all t 0, the probability that all noise samples are smaller than is |Ak E [
I t] = f(1 - E -- ). By a union bound, we
have P [u(ar, ((x)) > j. 21] Z f(1 e Et
f(1 /m) for all & 0. Setting 1) 0, yields
f(x) log(1 10g(1-(1-0) (1-7)ar) so PP [u(zz M (x)) u [z, j.) log
21 >
1/g log
Now set
1+
t log(m 1)/5 and 7 exp(et)+I
so that 1-2
and
9
Then
7
m
P [u(a, M (xx) 2 ul uxx.j.) 20
a log m] T0logm log
m +1 1- 1/m
9
10 That is, we
I0
can match the result the exponential mechanism up to (large) constants. In particular, this means that the lower bounds for selection translate to our results i.e., our results are tight up to constants.
E EXTENDING OUR RESULTS TO APPROXIMATE DP
Our results are all in the framework of Rényi DP. A natural question is what can be said if the base algorithm instead only satisfies approximate DP - i.e. (c, 5)DP with 5 > 0. Liu & Talwar (2019) considered these questions and gave several results. We now briefly show how our results can be extended in a black-box fashion to this setting.
We begin by defining approximate Rényi divergences and approximate Rényi DP:
25

---

Published as a conference paper at ICLR 2022
Definition 18 (Approximate Rényi Divergence). Let P and be probability distributions over Ω2 Let À E [1, oo] and E [0, 1]. We define
DÅ (PII)) = inf {Dx (P"IQQ)) P +8 -1-
where P= (1 8P denotes the fact that P can be expressed as convex combination of two distributions Pt and p" with weights å and â respectively.
Definition 19 (Approximate Rényi Differential Privacy). A randomized algorithm M : x - - is
5-approximately (X, -Réényi differentially private if. for all neighbouring pairs of inputs I. x/ X DÅ (M (x))) S.
Definition 19 an extension of the definition of approximate zCDP (Bun & Steinke 2016). Some remarks about the basic properties of approximate RDP are in order:
(c, 6DD is equivalent to 5-approximate
(c, DD implies 6-approximate (A, _ RDD for all À E (1,
6-approximate (A, RDDD implies (é, 8 for
8 - á exp((A - 1)(6 ()(6-))) (1-
X
6-approximate (A, -Réényi differential privacy is closed under postprocessing.
If M1 81 b1-approximately (X, (1) 1 differentially private and M2 is 62 approximatell (X, E2) -Rényi differentially private, then their composition is (81 +52) -ppp)xxppol (A, E1 R2)
Our results for Rényi DP can be extended to approximate Rényi DP by the following Lemma.
Lemma 20. Assume Y is totally ordered set. For distribution Q on y and random variable K supported on N {0), define AK as follows. First we sample K. Then we sample from Q independently K times and output the best of these samples. This outpul is a sample from A.
Let QQQ'QQQQQ00 Q1-60: Qba Pi-ba Vo,, be distributions on y satisfying Q = 01 (1-16))6 -10) + +50 and
Q' (1- (1-5n)Q'-a, + 500 Let K be a random variable on N J [0) and let f(xx) = E [ be
the probability generating function of K. Define a random variable K' on NU [0} by P K = k)
PIK- k]] 60)* f 60)
Then, for all A 2 1, we have
D (A A S DA (AQ
AA
where
8 8= f(1 - 5g).
How do we use this lemma? We should think of A as representing the algorithm we want to analyze. The base algorithm Q satisfies ap-approxe (A, The above lemma says it suffices to analyze the algorithm AK where Q satisfies eD,E)-RDP. We end up with a 6-approximate RDP result, where the final 8 depends dn and the PGF of K.
As an example, we can combine Lemma 20 with Theorem to obtain the following result for the approximate case.
Corollary 21. Let Q X" + y be randomized algorithm satisfying (Eu, 8u)-DP. Assume y is totally ordered. Let μ >
Define algorithm A X" + y) as follows. Draw K from Poisson distribution with mean Run ((x) repeatedly K times. Then A(x)) returns the best value from the K runs. (If K 0, A(x) returns some arbitrary output independent from the input x.))
Note that the PGF of K' is given by E k2
-x
P 1E 600* - 80) = f(x(1
bo))/f( f(1 8o).
26

---

Published as a conference paper at ICLR 2022
For all X $ 1 -. the algorithm A satisfies 8' -aappoxximate (X,E')-RDP where
e' = + (e 1) llg ,4
8' = 1 -v.0 1100 p 6g.
For distribution on y and an integer A: 2 O. let max pk denote the distribu- tion on y obtained by taking independent samples from and returning the maximum value per the total ordering on ). (If l O, this is some arbitrary fixed distribution.)
Proof of Lemina 20
Using this notation, we can express AQ as a convex combination:
PKK
P
k] max Q*
Suppose P (1 -1- P' is convex combination. We can view sampling from P as a two-step process: first sample Bernoulli random variable B E {0, 1] with expectation if B return sample from and, if B = 1, we return a sample from P" Thus, if we draw independent samples from P like this, then with probability (1 8) all of these Bernoullis are and we generate k samples from P" otherwise, we generate some mix of samples from l and p". Hence we can write max pk (1 5) max + (1 (1 8) pM for some distribution p"
It follows that we can express
AQ =
P IK = k] max Q*
k=0
Σ
P KK = k|] ((1 50)* max Q + (1 - (1- Px)
=
km0
f(1 - -8)) A +(1 fl1
for some distributions Po, PI. ... and (1 f(1 6o)) Σi= [K k](1 -11 )k.
Similarly, we can express AB = ((1 5o) A A 01 + +11 - 1(1(1 - 6o)) " for some distribution PC
Using these convex combinations have, by the definition of approximate Rényi divergence,
K D (45 (5) <DD DA (A5'-.,
80
as 8 = 1 f(1 60).
Proof of Corollary 27 Fix neighbouring inputs x, and let Q Q(x) and Q' Q(z') be the corresponding pair of output distributions from the base algorithm. Then, in the notation of Lemma A(x) AB and A(x') AK for K Poisson(μ). Setting 8' =1- 1-f(1-
4. < u.op.
we have
DI (A())]A((z))) = DI ( AA)) S DA (A AA5:mm))
where K' Poisson( (1 dg)).
Now we apply Theorem 6 to the algorithm corresponding to the pair distributions A5 and The base algorithm, corresponding to the pair Q1-50 and Qi satisfies (co. 0)-DP. This
AK'
O so
yields
log( (1 8p) 11) X A-1
D, Q1-10 AQ) S En +
T <1+1/00 - 1). Setting 1 + 1/ 1) and applying monotonicity (Remark 5 and
Lemma 10 and obtain the result.
27

---

Published as a conference paper at ICLR 2022
E. TRUNCATING THE NUMBER OF REPETITIONS
Another natural question is what happens if we truncate the distribution of the number of repetitions K. For example, may have upper limit the acceptable runtime. This does not require relaxing to approximate DP, as done by Liu & Talwar (2019).
Let K be the non-truncated number of repetitions and let f(x) EE [x be the PGF. Let m E N. Let K be the truncated number of repetitions. That is, N = k
= I[K S m] IP IK k [ S m].
Let [(x) = E [ be the corresponding PGF.
We have (x) Ex= k. x P P[K- k] and (((x) Ek= h: x²
P[K= P(K Sm)
Hence, for
x E [0, 1].
0 (f) - (()) K 1 mm]
Σ k k-1
P PKK
S x t
Σ
K. K R.]
k=m+1
= x
E KK T > mi]-
Now (x))) P PIK ml
Ex=
k x²
PP KK = k) 2 z-
E [K I[K S ml]. Thus
fz(x)
Th E KK IK > ml]
E K I[ > m]]
15 (x) K S m]
1+
-m E EK I[K S m]]
E|K] E [[K I[K ml]
Now we can bound the quantity of interest in Lemma 7 For all q, E E00,1] 1]. we have
1-A
IPK I ml )²
(((()
f((4))
PIK S m]
(1
E[K-LIK ml]]
B[K]-B[K B.KKBKKKPP I[ Sm]]]
1
E [K 1[K > m]]
A-1
ff f((d)
1+
PIK S m]
E [K]
E K [[K m]]
This gives us a generic result for truncated distributions:
Lemma 22 (Generic Bound (ef. Lemma 7 for Truncated distributions). Fix X > 1 and m E N. Let
K be a random variable supported on N U (0). Let f [0, - TR. be the probability generating function of K i.e., f(x) ;= Ek=o IP [K- k] x
Let Q and Q' be distributions on y. Assume y totally ordered. Define a distribution A on y as fol- lows. First sample KK which is K conditioned K S m m-iie P
K = P PK k|K s m).
Then we sample from Q independently K times and output the best of these samples sample from A. We define A' analogously with Q' in place of Q.
13 This output is
Then
1 DA (AIIA) S DA (Q11Q)++ X-1 - log (f'())* ((())->) log
T-F +log
K I[K > ml
1
2-1
K
E
- E
K I[K m
where q and g' are probabilities attained by applying the same arbitrary postprocessing to Q and and
Q' respectively - i.e., there exists a function g : y + [0,1] 1] such that q = E x-Q
[(x))
E. Lx [x('))
x'=q'
This will give almost identical bounds to using the non- con-truncteed distribution as long as P [K > m] <<
1 and E JK- [[K > ml] << E [K]. which should hold for large enough
Iff K 0, the output be arbitrary, as long as it is the same for both A and A'.
28


Reviews:
[{"review_id": "udun_vLx--Z", "reviewer": "Reviewer_SYbz", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "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": "DP-focused machine learning systems would benefit from this work, as most of them require hyperparameter tuning. The algorithms provided in this work help us avoid a large cost of composition and perform tuning at much smaller privacy loss. In addition, the generic bound allows us to be flexible on the distribution of the number of runs ($K$), though it requires some effort to translate the logarithmic term into something usable. I have checked all the proofs and there are no critical errors.\n\nThe authors have sufficiently compared their method with previous approaches. Specifically, using the main results, the authors show that their method extends and improves upon the work of Liu and Talwar (2019). The authors also compare their method with the exponential mechanism-based method (Gupta et al., 2010; Theorem 10.2) and show in Section D.4 that both methods have the same lower bounds of the utility guarantees up to constants.\n\nNonetheless, the authors might want to compare their method with the noise perturbation method proposed by Chaudhuri et al. (2013). This method requires the “stability” condition on the training procedure, which might not be tractable for neural networks. But for linear classifiers, the algorithm (Algorithm 1) only adds noises of size $O(1/n\\varepsilon)$ to the scores, which is quite attractive for training on large datasets.\n\nThe paper is mostly written with DP-SGD in mind, but it does not consider when the model's evaluation on a hold-out validation set is incorporated in the base algorithm $Q$, which is a common practice in training an ML model. From an application point of view, the authors might want to discuss a bit how the model’s evaluation (in classification or regression) can be made DP or RDP as a part of $Q$. \n\nI see that distributions with finite support (e.g. the truncated binomial) are not considered in this study. But in practice, one might want to limit the number of hyperparameter searches (e.g. due to computational constraints), so such distributions might come into play. Have the authors performed some experiments on these against the truncated negative binomial and Poisson distribution? I wonder if the privacy-utility tradeoff is better when restricting to finite support.\n\nCould the authors comment on how to determine an appropriate size of the candidate set ($m$)? A simple heuristic is $m=\\mathbb{E}[K]$ but the authors might have something better in mind.\n\n### **Specific comments**\n* Page 2: In Eq (2), the special case where $\\lambda=1$ should be mentioned here, as it is also in the range of $\\hat\\lambda$ in the main results.\n* Page 6: When I tried to derive (6) from (5), I got an extra $-\\rho\\eta$ term from rewriting\n$$\\epsilon+\\rho(\\lambda-1)+(1+\\eta)\\left(1-\\frac1{\\hat\\lambda}\\right)\\hat\\epsilon=\\rho\\lambda+\\rho(1+\\eta)(\\hat\\lambda-1)=\\rho(\\lambda-1)+\\rho\\hat\\lambda(1+\\eta)-\\rho\\eta,$$\ncombining this with the rest of the terms, and then choosing $\\lambda$ and $\\lambda'$ so that the equality holds in the following inequality:\n$$ \\left(\\rho(\\lambda-1) + \\frac{\\log\\mathbb{E}[K]}{\\lambda-1} \\right)+\\left(\\rho\\hat\\lambda(1+\\eta) + \\frac{(1+\\eta)\\log(1/\\gamma)}{\\hat\\lambda}\\right)- \\rho\\eta \\\\\n  \\geq  2\\sqrt{\\rho\\log\\mathbb{E}[K]} +2(1+\\eta)\\sqrt{\\rho\\log(1/\\gamma)}-\\rho\\eta. $$\nTo clarify this, I think the authors should provide the proof of Corollary 4 somewhere in the Appendix, as I find the bound to be non-trivial.\n* Page 7: In Lemma 7, “$q$ and $q'$ are arbitrary probabilities” is misleading. When I saw the statement for the first time, I read this as “$q$ and $q'$ can be anything in $[0,1]$”, but the proof indicates that they take specific forms in order for the Lemma to hold true. One way to resolve this issue is by directly stating the definition of $q$ and $q'$ after (7).\n* Line 1-2 in Page 8:\n> Vaguely, $f'$ being smooth corresponds to the distribution $K$ being spread out (i.e. far from being a point mass).    \n>\nThis is not true; if $X$ is a point mass at $1$ i.e. $\\Pr{[X=1]}=1$, then the PGF of $X$ is $f(x)=x$, and so $f'(x)=1$ which is smoother than any polynomial.  \nLooking at the definition of PGF, the smoothness of $f'$ should depend on the right-tail heaviness of the distribution of $K$. Specifically, a heavier right tail corresponds to a faster growth rate of $f'$, which in turn leads to a larger RHS of Eq. (7) when $q > q'$. This observation is in line with the privacy-utility tradeoff: more probabilities of sampling a large $K$ (i.e. more utility) lead to a larger privacy loss.\n* Page 18: when $p=r=\\infty$, then the value of $r/p$ is unclear. What is the convention for this case?\n* Page 23: It is mentioned below the definition of $Q,Q',A,A'$ that “the total ordering prefers the first option (corresponding to the first coordinate probability)” which should refer to the ones with the probabilities $1-b-c$ and $1-b'-c'$. In other words, we assume that $1-b-c>b$ and $1-b'-c'>b'$. However, the approximations below suggest that $b>c>1-b-c$ and $b'>c'>1-b'-c'$.\n* Page 25: The proof of Lemma 20 is missing. Does it appear in Bun & Steinke (2016)?\n\n### **Minor corrections**\n* Page 6: In Remark 5: “$(\\lambda_2,\\varepsilon)$-RDP implies $(\\lambda_2,\\varepsilon)$-RDP” $\\rightarrow$ “$(\\lambda_2,\\varepsilon)$-RDP implies $(\\lambda_1,\\varepsilon)$-RDP” and “ann” $\\rightarrow$ “any”.\n* Page 14: In the footnote, “experssion” $\\rightarrow$ “expression”\n* Page 16: In the definition of $g(y)$, $t$ should be $t^*$.\n* Page 21: In the third display equation, the equal sign should be replaced with $>$.\n* Page 23: First line in Section D.4: “hyperparamter” $\\rightarrow$ “hyperparameter”\n\n### **References**\nBun, M., & Steinke, T. (2016). Concentrated differential privacy: Simplifications, extensions, and lower bounds. TCC'16.  \nChaudhuri, K., & Vinterbo, S.A. (2013). A Stability-based Validation Procedure for Differentially Private Machine Learning. NIPS'13.  \nGupta, A., Ligett, K., McSherry, F., Roth, A., & Talwar, K. (2010). Differentially private combinatorial optimization. SODA '10.  \nLiu, J., & Talwar, K. (2019). Private selection from private candidates. STOC'19.\n", "summary_of_the_paper": "The authors make the following contributions regarding differentially private hyperparameter tuning :\n* As an example, the authors train an SVM with a weight penalty and show that, in presence of an outlier, a membership inference attack can be employed to infer from the hyperparameter whether or not the outlier was a part of the training set.\n*The authors provide an algorithm for private hyperparameter tuning, which consists of running a learning algorithm that satisfies Rényi differential privacy (RDP) for a *random* number of times ($K$), each with a hyperparameter drawn uniformly at random from a finite candidate set. The authors first prove RDP guarantees of the algorithm when $K$ is sampled from a truncated negative binomial distribution and Poisson distribution. Then they proceed to prove RDP guarantees for any distribution of $K$ supported on $\\mathbb{N}\\cup \\{0\\}$ ¹.\nThe authors propose a way to measure the utility of the algorithms by looking at the expected quantile of the output. The results of their utility analysis, coupled with an experiment on MNIST, show that the algorithm with Poisson distribution performs better than those proposed by Liu and Talwar (2019) in an intermediate range of privacy budget ($\\varepsilon$).\n\n¹ From what I understand, we can obtain a tighter generic bound by going through the proof of Lemma 7. But the authors opt to use (7) since the postprocessing often leads to a bound that is independent of $q$ and $q'$ when plugging in a specific distribution.\n", "summary_of_the_review": "This work provides careful privacy and utility analysis of private algorithms for hyperparameter tuning. All of the analyses and the proofs are sound, and the experiments give good comparisons between various distributions.  To make the methods widely applicable, the authors might want to comment on how the model’s evaluation on a hold-out validation set can be integrated into the DP workflow. Overall, this is a strong paper and I recommend it for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "cTN7rY4rDiU", "reviewer": "Reviewer_CBQT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 problem studied here is a really important one, since it is directly related to actual deployment of DP models in real life settings. The proposed method seems solid and the experimental results look promising. I do have a few clarification questions:\n\n1. How would this method be extended to be used with adaptive search methods? Grid search can be too time consuming/inefficient, especially when used with DP-SGD (as DP-SGD needs per-example gradients that are expensive to obtain) and there are some reinforcement learning based methods that can yield optimal hyper parameters much faster than grid search. Can this method be modified, maybe with a higher privacy expenditure, to be used in those cases?  \n \n2. What kind of real-life attack scenario would you envision that could actually use the best models obtained by hyper parameter tuning to extract information. Basically, what type/how much information about a model do the set of optimal hyper parameters leak?\n\n", "summary_of_the_paper": "This paper studies the problem of hyper parameter tuning in the setting of differentially private training of machine learning models. The paper first shows that the hyper parameters used to train a model and the corresponding utility can leak information about training (through experimenting with outliers). They then go on to introduce and analyze ways that would help release DP models trained with the \"best\" set of hyper parameters, with small privacy leakage. If for hyper parameter tuning, $m$ models are trained with DP, then the leakage for releasing  the best model would be $m\\epsilon$ with simple composition. The  method introduced by the paper, however, builds on prior work by Liu&Talwar and improves this to become $2\\epsilon$, through randomly choosing and running hyper parameter settings. ", "summary_of_the_review": "I don't see any major issues with the paper and I find the problem addressed very relevant. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FaGWKUw1Khv", "reviewer": "Reviewer_4Ysq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 is very well written and the analysis seems solid (though I did not check every line). The problem is important and the paper improves the state-of-the-art so its merits are clear.\n\nMy only critique:\n\nAs emhpasised in Sec. 3.2, the ‘strawman approach’ of fixing m does not work for pure eps-DP. However, I find this a bit misleading since you are not observing (eps,0)-DP of hyperparameter tuning but (eps,delta) (or RDP). So the delta might actually play a crucial role here. Allowing bit of delta in the DP bound, the randomness in choosing the number of repetition might perhaps be not that crucial. Or vice versa, in (eps,0), you would not get great gains from that randomness.\n\nI suspect that this fact that you have to have the randomness in the number of repetitions actually is a requirement of the RDP analysis that you carry out. As far as I see, in Proposition 17 you claim it is not, but I do not fully see why that would be the case. The result of Proposition 17, i.e., that the RDP of k repetitions is not RDP for less than eps’(lambda), does not really give a ‘counter-example’ in the same  way as that result for pure epsilon. For example, suppose the underlying mechanism is eps=0.5 - DP. Then, you choose lambda = 1.9483. Then, eps - (log(1+exp(-eps))/(lambda-1)) ~ 1e-4 in which case the bound does not really say anything even for quite large numbers of k. And you can of course make that bound arbitrarily small by choosing lambda appropriately. I.e., if you let delta > 0, I think there is room for tighter analysis also for fixed k.\n\nCould you comment on this tradeoff between lambda and eps in the bound of Proposition 17?\n\nCould you give more intuition on why the randomness in number of repetitions k would be crucial or some other example that illustrates this?\n\nOther:\n- There is something strange at the bottom of p. 22: equation going over the line.\n", "summary_of_the_paper": "The paper provides an considerable improvement to the DP analysis of hyperparameter tuning of DP algorithms (such as DP-SGD). The analysis is carried out using Rényi differential privacy (RDP), and the DP bounds are RDP bounds that contain the RDP parameters of the underlying mechanisms (that give the private candidates). Most importantly, the paper considerably improves the state-of-the-art of Liu and Talwar (2019). Also, a nice counterexample using SVMs is constructed, that shows the importance of this problem.\n", "summary_of_the_review": "All in all I think this is a very nice analysis and improves the state-of-the-art. Also, this is a very important problem. With small modifications I think this ought to be accepted. My only critique: I am just not entirely convinced that randomness in the number of repetitions is crucial for having tight bounds for DP hyperparameter tuning, I hope the authors can clarify my concerns.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0qJRDAo9N8", "reviewer": "Reviewer_mxg8", "summary": "", "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 considers an interesting and important problem: how hyperparameter tuning on private dataset can leak information, where it provides an intuitive SVM example. The paper then considers how to reduce the leakage. The problem is formalized in the following way: we pick a total number of runs $K$ from some distribution. Then, for each run  $k = 1, 2,\\ldots, K$ , we pick an index $j_k \\in [m]$ uniformly at random and run $M_{jk}$ . Then, at the end, we return the best of the $K$ outcomes. The paper proposes theoretical guarantees when $K$ comes from truncated negative binomial distribution, or Poission distribution, which strictly generalizes the previous results. Furthermore, it also proposes a new method of computing privacy leakage when $K$ comes from a general distribution, which should be of independent interest. Finally, the paper conducts empirical experiments to show the improvement if the new method.\n\nMy only concern for this paper is the problem formalization. First, for the current problem formulation, it is possible that the same parameter will be tried multiple times, which is definitely a waste of privacy. Not sure whether people will do it in practice. Second, the paper assumes the following scheme satisfies DP: randomly choose $j \\in [m]$, and run $M_j$. Note that this is not equivalent with assuming each $M_j$ is DP, where the latter is more realistic. For example, in the hyperparameter tuning of DP-SGD, it easily holds that each run (with different clipping norm) satisfies DP. However, it is not clear to me whether randomly selecting one clipping norm, and then running DP-SGD is differentially private. The authors need to justify the relationship between these two assumptions. Naively speaking, the second can not lead to the first assumption. Please correct me if I miss something.", "summary_of_the_paper": "This paper has made the following contributions. Firstly, this paper illustrates how simply tuning hyperparameters based on non-private training runs can leak private information. Second, this paper provides privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Their results improve and extend the work of Liu and Talwar (STOC 2019).", "summary_of_the_review": "Generally speaking, I recommend acceptance of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles a problem at the intersection of AutoML and trustworthiness that has not been studied much before, and provides a first solution, leaving much space for a lot of interesting future research.
All reviewers agree that this is a strong paper and clearly recommend acceptance.
I recommend acceptance as an oral since the paper opens the door for a lot of interesting follow-ups.
Decision: Accept (Oral)