Practical Differentially Private Hyperparameter Tuning with Subsampling
Authors: Antti Koskela
Tejas Kulkarni
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
hyperparameter tuning
Rényi differential privacy
computational efficiency
DP-SGD
TL;DR: We lower the privacy cost and the compute cost of DP hyperparameter tuning

Abstract: Tuning the hyperparameters of differentially private (DP) machine learning (ML) algorithms often requires use of sensitive data and this may leak private information via hyperparameter values. Recently, Papernot and Steinke (2022) proposed a certain class of DP hyperparameter tuning algorithms, where the number of random search samples is randomized. Commonly, these algorithms still considerably increase the DP privacy parameter $\varepsilon$ over non-tuned DP ML model training and can be computationally heavy as evaluating each hyperparameter candidate requires a new training run. We focus on lowering both the DP bounds and the compute cost of these methods by using only a random subset of the sensitive data for the hyperparameter tuning and by appropriately extrapolating the optimal values to a larger dataset. We carry out a Rényi differential privacy analysis for the proposed method and experimentally show that it consistently leads to better privacy-utility trade-off than the baseline method by Papernot and Steinke.

Practical Differentially Private Hyperparameter Tuning with Subsampling
Antti Koskela Nokia Bell Labs
Tejas Kulkarni
Nokia Bell Labs
antti www.kolllllkkiaaabboooooo llbs.
com com
tejas kulkarni@nokia bell llass com
Abstract
Tuning the hyperparameters of differentially private (DP) machine learning (ML) algorithms often requires use sensitive data and this may leak private information via hyperparameter values. Recently, Papernot and Steinke (2022) proposed a certain class of DP hyperparameter tuning algorithms, where the number of random search samples is randomized. Commonly, these algorithms still considerably increase the DP privacy parameter over non-tuned DP ML model training and can be computationally heavy as evaluating each hyperparameter candidate requires a new training run. We focus on lowering both the DP bounds and the compute cost of these methods by using only random subset of the sensitive data for the hyperparameter tuning and by extrapolating the optimal values to a larger dataset. We provide a Rényi differential privacy analysis for the proposed method and experimentally show that it consistently leads to better privacy-utility trade-off than the baseline method by Papernot and Steinke.
Introduction
Our aim is two-fold: decrease the computational cost as well the privacy cost of hyperparameter tuning of DP ML models. The reasons for this are clear. As the dataset sizes grow and models get more complex, blackbox optimization of hyperparameters becomes more expensive since evaluation of single set of hyperparameters often requires retraining new model. On the other hand, tuning the hyperparameters often depends on the use of sensitive data, so it requires privacy protection well, illustrated by the example by [Papernot and Steinke (2022). Intuitively, the leakage from hyperparameters is much smaller than from the model parameters, however, providing tuning algorithms with low additional DP cost has turned out challenging. Current best algorithms (Papernot and Steinke 2022) still come with a considerable DP cost overhead.
Although our methods and results are applicable to general DP mechanisms, we focus in particular on tuning of the DP stochastic gradient descent (DP-SGD) (Song et al., [0033] Bassily et al., 2014 Abadi al. 2016) which has become the most widely used method to train ML models with DP guarantees. Compared to plain SGD, DP brings additional hyperparameters to tune: the noise level o and the clipping constant C. Additionally, also the subsampling ratio y affects the DP guarantees, as well as length of the training. Tuning all the hyperparameters of DP-SGD commonly requires use of sensitive data.
We use the results by Papernot and Steinke (022) as building blocks our methods. Their work was based on the analysis of Liu and Talwar (2019) who provided the first results for DP black- box optimization of hyperparameters, where, if the base training algorithm is (e. 0)-DP, then the tuned model is approximately (3s, OD-DP, Papernot and Steinke (2022) provided Rényi differential privacy (RDP) analysis for class black-box tuning algorithms, where the number runs in the hyperparameter tuning is randomized. As the privacy bounds are in terms of RDP and assume only RDP bounds about the candidate model training algorithms, they are particularly suitable to tuning
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

DP-SGD. However, still, running these algorithms increase the e-values two or three-fold or more, and they can be computationally heavy as evaluating each candidate model requires training a new model. Our novelty is to consider using only a random subset of the sensitive data for the tuning part and use the output hyperparameter values (and potentially the model) for training subsequent models. Using random subset for the privacy and computation costly part automatically leads to both lower DP privacy leakage as well as computational cost. We also consider ways to appropriately extrapolate the optimal value from the small subset of data to larger dataset.
The RDP bounds for the DP tuning methods by Papernot and Steinke (002)) assume that the RDP- values of the candidate model training algorithms are fixed. We also consider ways to use these bounds for tuning hy hyperparameters that affect the RDP-values of the base algorithm, being the noise level or the subsampling ratio and the length of training in case of DP-SGD.
1.1 Related Work Hyperparameter Tuning
Chaudhuri and Vinterbo (013)) were the first ones to focus on DP bounds for hyperparameter
tuning. An improvement was made by Liu and Talwar (2019) who considered black-box tuning of (e,6)-DP mechanisms. Mohapatra et al. (2022) showed that for reasonable numbers of adaptively chosen private candidates a naive RDP accounting (i.e., RDP parameters grow linearly w.r.t. the number of model evaluations) often leads to lower DP bounds than the methods by Liu and Talwar (2019). Papernot and Steinke (2022) gave RDP bounds for black-box tuning algorithms that grow only logarithmically w.r.t. the number of model evaluations. In a non-DP setting, hy hyperparameter tuning with random subsamples has been considered for SVMs (Horváth et al.] 2017) and for large datasets in healthcare (Waring et al.) (020).. Small random subsets of data have been used in Bayesian optimization of hyperparameters (Swersky et al.) 2013) Klein et al.. (017). Recent works (Killamsetty
et al. 2021 1 2022 consider using subsets of data for hyperparameter tuning of deep learning models.
1.2
Our Contributions
We propose a subsampling strategy to lower the privacy cost and computational cost of DP hyperparameter tuning. We provide tailored RDP analysis for the proposed strategy. Our analysis is in terms of RDP and we use existing results for tuning Papernot and Steinke (0022) and DP-SGD (Zhu and Wang 2019) as building blocks.
We propose algorithms to tune hyperparameters that affect the RDP guarantees of the base model training algorithms. We provide rigorous RDP analysis for these algorithms.
We carry out experiments on several standard datasets, where we are able to improve upon the baseline tuning method by clear margin. While our experiments focus mainly on training of deep learning models with DP-SGD and DP-Adam, our framework is currently applicable to any computation that involves selecting the best among several alternatives (consider e.g.. DP model selection, Thakurta and Smith 2013).
2 Background: DP, DP-SGD and DP Hyperparameter Tuning
We first give the basic definitions. An input dataset containing n data points is denoted X (I Denote the set of all possible datasets by X. We say X and Y are neighbors if we get one by adding or removing one data element to or from the other (denoted X ~ Y). Consider randomized mechanism M X + O, where O denotes the output space. The (e, -)-deinitio of DP can be given as follows (wwork 2006).
Definition 1. Let 0 and ō E [o, 1]. We say that mechanism M is (e, (), ifr all neighboring datasets X and Y and for every measurable set E C O we have:
Pr(M(X) E E) < PT(M))))))))EE)E E)
We will also use the Rényi differential privacy (RDP) Mironov 2017) which is defined as follows. Rényi divergence of order a > 1 between two distributions P and defined as
Da(lI)Q) = - log /
(
P()) ((1))
Q(t) dt.
(2.1)
2

---

Definition 2. We say that mechanism M is (a,E)-RDP, for all neighboring datasets X and Y, the output distributions of ( and MYY have Rényi divergence of order a at most E, i.e.
max D. (M(X))MM)) S. X-Y
We convert from Rényi DP approximate DP using, for example, the following formula:
Lemma 3 Canonnee al. 2020). Suppose the mechanism M is
Then M is also
(E, for arbitrary
with
8(e) exp ((a- - 1)(s" - -e))
(1 (1-2)
a-1
(2.2)
a
As is common in practice, carry out the RDP accounting such that do bookkeeping of total e(a:) for a list of RDP-orders (e.g. integer a s) and in the end convert to (e, 00gguraantess by minimizing over the values given by Equation 2.2 w.r.t. RDP accounting for compositions of DP mechanisms is carried using standard RDP composition results (Mironov) 2017).
DP-SGD differs from SGD such that samplewiis gradients of random mini-batch are clipped to have an L2-norm at most C' and normally distributed noise with variance o² is added to the sum of the gradients of the mini-batch (Abadi et al. 2016). One iteration is given by
Oj+1 = 00 -11
(i), REB;
(2.3)
where the noise 7. ~ No, [B Ta). Ta) denotes the loss function, 0 the model parameters, 7/ the learning rate hyperparameter at iteration j and B is the expected batch size (if we carry out Poisson subsampling of batches [B; varies). There are several results that enable the RDP analysis of DP-SGD iterations (Abadi et al. 2016, Balle et al. 2018 Zhu and Wang 2019). The following result by Zhu and Wang (2019) is directly applicable analyzing DP-SGD, however, also for ana analyzing a variant of our hyperparameter tuning method.
Theorem 4 (Zuu and Wang 2019). Suppose M is a (a, mechanism, w.r.f. to the add/remove neighbourhood relation. Consider the subsampled mechanism (M subsampplepaisoonn)))) (X). where subsamplepaisonny) denotes Poisson subsampling with sampling
ratio 7; M is (a, ((a))))))RL) -RDP then M subsamplepuisontt)) is (a)) (a 2 2 is an integer), where
- (ay 7((1 (
é'(a) = a- log (1 (1--))
+ 3 E J=3 (1) -xppl= 1)((())))()))
We remark that the recent works (Koskela et al. 2020 Gopi et al. 2021 Zhu et al. 2022) give methods
carry out (c, d)-analssss of DP-SGD tightly. As the state-of -f-heeat bounds for hyperparameter tuning methods are RDP bounds (Papernot and Steinke 2022), for simplicity, we will also analyze DP-SGD using RDP.
Intuitively, the leakage from hyperparameters much smaller than from the model parameters, however, considering it in the final accounting is needed to ensure rigorous DP guarantees. Currently the most practical (s, ( guarrantees for DP hyperparameter tuning algorithms are those of (Papernot and Steinke, 2022). In the results of Papernot and Steinke (2022) it is important that the number of runs K with the hyperparameter tuning is randomized. They analyze various distributions for drawing K, however, we focus using the Poisson distribution it is the most concentrated around the mean among all the alternatives. The corresponding hyperparameter tuning algorithm and its privacy guarantees given by Thm
First recall: K is distributed according to a Poisson distribution with mean μ > 0, if for all non- negative integer values k: IPK k) = E

---

Theorem 5 (Papernot and Steinke 2022). Let Q XN - y be randomized algorithm satisfying (a, ((a)) -RDP and (E, DD for some E (1, ,, 2 O. Assume y is totally ordered. Let the Poisson distribution parameter P O. Define the kyperparameter luning algorithm A X² y as follows. Draw K from a Poisson distribution with mean μ.. Run Q(X) for K times. Then A(X) returns the best value of those K runs (both the hyperparameters and the model parameters). If
K = 0, A(X)) returns some arbitrary output. If e I 1+ a then A satisfies (a, (a)) -RDP, where g' (a) = E(a:) + p.. log
3 DP Hyperparameter Tuning with a Random Subset
We next consider main tool: carry out the private hyperparameter tuning random subset, and if needed, extrapolate the found hyperparameter values to larger datasets that we use for training subsequent models. In approach the subset of data used for tuning is generally smaller than the data used for training the final model and thus we extrapolate the hyperparameter values.
3.1 Our Method: Small Random Subset for Tuning
Our method works as below:
1. Use Poisson subsampling to draw X1 X: draw a random subset X1 such that each X is included in X, with probability q.
2. Compute (01, f2) = Mtune (x1) where Maune is a hyperparameter tuning algorithm (e.g..
the method by Papernot and Steinke 2022) that outputs the vector of optimal hyperparame- ters t and the corresponding model parameters fj.
3. If needed, extrapolate the hyperparameters t to the dataset X Xx; f - t2-
4. Compute 02 MMasse (01, 22 X XX)). where Mbase is the base mechanism (e.g., DP-SGD)
Denote the whole mechanism by M.. Then, may write
M(X)= (X1), Mbase (MunneX))), (x2)),
(3.1)
where X1 ~ subsamplepoisoutgg] (X). (X)) Additionally, we consider a variation of our method in which we use the full dataset X instead of X \ Xx from step onwards, i.e., the mechanism
M(X) (Meune (X1,, Mbaee (Meune (oann((X) (X))
(3.2)
where X1 subsample (X). We call these methods variant and variant 2, respectively. The RDP bounds for the variant can be obtained with standard subsampling and composition result (e.g., Thm We provide tailored privacy analysis of the variant in Section 3.3
3.2 Extrapolating the DP-SGD Hyperparameters
We simple heuristics to transfer the optimal hyperparameter values found for the small subset of data to a larger dataset. The clipping constant C, the noise level a, the subsampling ratio y and the total number of iterations T are kept constant in this transfer. As consequence the (c, -privaac guarantees are also the same for the models trained with the smaller and the larger dataset. For scaling the learning rate, we the heuristics used by van der Veen al. 2018): we scale the learning rate ? with the dataset size. Lee., if we carry out the hyperparameter tuning using a subset of size m and find an optimal value vy", we multiply 17" by n/m when transferring the dataset of size n.
This can also heuristically motivated as follows. Consider T iterations of the DP-SGD (2.3). With the above rules, the distribution of the noise that gets injected into the model trained with dataset of size n is
T Σz,~ ~ N (0. T. (mn") 022 (..00. Ia ~ N~ >>N(0,
T (0. Id
(7-
(7 .y.mo m)²
J=1
which is exactly the distribution of the noise that was added to the model trained with the subsample of size m. This principle of keeping the noise constant when scaling the hyperparameters was also used by /Sander et al. (2022).

---

We arrive at our scaling rule also by taking a variational Bayesian view of DP-SGD, Mandt et al. (2017) model the stochasticity of the SGD mini-batch gradients in a region approximated by constant quadratic convex loss by invoking the central limit theorem, and arrive at a continuous-time multivariate Ornstein- -hheein- (OU) process for which the discrete approximation is given by
A (0) + " LAW,
AW (a),
(3.3)
VB
where [B] denotes the batch size of the SGD approximation, g(0) the full gradient and LLT the covari- ance matrix of the SGD noise. By minimizing the Kullback-Leible divergence between the stationary distribution of this OU-process and the Gaussian posterior distribution f(0) x exp (-n-Z(0)). where [()) denotes the quadratic loss function and n is the size of the dataset, they arrive at the expression
B
2 n Tr(LL")
for the optimal learning rate value (see Thm. 1, Mandt al. 2017). We consider the where the additive DP noise dominates the SGD noise, and instead of the update (3.) consider the update
A (0) 1 ..O.C. AW,
AW ~ (a)
(3.4)
B
which equals the DP-SGD update 2.3
with the mini-batch gradient replaced by the full gradient.
Essentially the difference between
3.3 and (3.4) is v replaced by [B], and by the reasoning
used in (Thm. 1. Mandt et al. 2017). we see that the learning rate value that minimizes the KL
divergence between the approximate posterior and the Gaussian posterior f() then given by
B
d
G2C -2 -22n 22n
|B|
1f"
Tr(2C22T)
=
0²C²
(3.5)
The scaling rule (3.5) also indicates that the optimal value of the learning rate should be scaled linearly with the size of the dataset in case y, a and C' are kept constant.
Training of certain models benefits from use of adaptive optimizers such as Adam (Kingma and Ba 2014) or RMSProp, e.g., due to sparse gradients. Then the above extrapolation rules for DP-SGD not necessarily meaningful anymore. In our experiments, when training a neural network classifier using Adam with DP-SGD gradients, we found that keeping the value of the learning rate fixed in the transfer to the larger dataset lead to better results than increasing it as in case of DP-SGD. We mention that there are principled ways of extrapolating the hyperparameters in non-DP setting such as those of Klein et al. 2017)
3.3 Privacy Analysis
The RDP analysis of the variant 2 given in Equation 3.2)
is straightforward. Since the tuning set Xi sampled with Poisson subsampling with subsampling ratio q, we may write the mechanism as an adaptive composition
M(X) (X), (M (X), (x).
where M (Meune subsampleeposeeuf (X). Using the RDP values given by Thm.
5 for
Mtune and the subsampling amplification result of Thm. 4 we obtain RDP bounds for M X). Using RDP bounds for Mbase (e.g.. DP-SGD) and RDP composition results, we further get RDP bounds for the mechanism M given in (3.2).
Tailored RDP-Analysis. When we use the variant 33.1. i.e., we only use the rest of the data XXX, for Mbases we can get even tighter RDP bounds. The following theorem gives tailored RDP bounds for the mechanism (3.I. Similarly to the analysis by Zhu and Wang 2019) for the Poisson subsampled Gaussian mechanism, we obtain RDP bounds using the RDP bounds of the non-subsampled mechanisms and by using binomial expansions (the proof is given in Appendix C
Theorem 6. Let M be the mechanism (3.I), such that the subset X, is Poisson sampled with subsampling ratio q, 0 S < 1 and let T. Denote by (tune(a) and (base (a) the RDP-values of mechanisms Monee and Muase, respectively. Then, M is (a, -RDP for
E(a) max(er(().
5

---

where
1
E1(a)= a-
log (8* exp ((a exp
1) (a)) (1 q)a exp ((a 1) (a))
(3.6)
a-1
a
qr ga-1 1 (1 (1-q)² q)- exp ((a -j 1)Eencc - j)) exp ((j 1) (i))
and
1
e2(a)
log (1 (1-9)² 11--))--1 .exp ((a ba)aasc(a))
Q Q-1
a -
q² (1 g)--1- exp (j étune (j + 1j) exp ((a - jj- b (a 1))
j
(3.7)
Remark 7. The RDP bound given by Thm. o is optimal in sense that it approaches êtune (a) and (a) as + 1 and + O, respectively.
Remark We can initialize the subsequens model training Mbase using the model 0j. This adaptivity included in all the RDP analyses of both mechanisms
3.1 and 3.2
Notice that in the bounds (3.6) and 3.7 the RDP parameter of the tuning algorithm, Stune (a), is weighted with the parameter q and the RDP parameter of the base algorithm. Ebase (a), weighted with 1 This lowers the overall privacy cost in case the tuning set is chosen small enough.
Figure illustrates how the (e, bbbuddsss of the two variants (3.1) and 3.2 behave functions of the sampling parameter used for sampling the tuning set X1, when the base mechanism DP-SGD for 50 epochs with the subsampling ratio y 0.01 and noise level variant 1 given in Equation (3.1) are computed using the RDP results of Thm. 6 and the bounds for the variant 2 are computed using the subsampling amplification result of Thm. The RDP bounds
2.0. The bounds for the
are converted to (e, 6)-buunds using the conversion rule of Lemma 3 with 10-5 The fact that
the bounds for the variants and 2 cross when μr 45 small values of q suggests that the bounds of Thm. could still be tightened.
epachs=50, y=0.01, d=2.0, 15
epachs=50, y=0.01, 0=2.0, 4=45
10
5.0
8
4.0
finll
5nal
7
3.0
basel
baseline
method variant
5
method variant our method -- variant (Thm.
2.0
our method variant (Thm.
4
subsampling ratio
subsampling ratio
Figure 1:
Comparison of (s, bbbundd for the variant given in Equation (3.1) and the variant
given in Equation (3.2) as a function of the subsampling ratio used for sampling the tuning set X1- Also shown the (z, b-ound for the baseline algorithm described in Thm. 5 Here y refers the expected number of model evaluations in the tuning algorithm.
3.4 Computational Savings
Our scaling approach for DP-SGD described in Section ratio y, the noise level and the number iterations are the same when evaluating the private candidate models using the tuning set X1 and when evaluating the final model using the larger dataset.
3.2 implies that the DP-SGD subsampling

---

Thus, if we run the base algorithm for E epochs, we easily see that the expected number of required gradient evaluations for the variant given (3.T) is given by E- (1-------(-11)) -)) and for the variant 2 given in (3.2) it is given by E. (ju q- n + n), whereas the baseline requires in expectation Je n E. evaluations in case it is carrying out tuning with the same hyperparameter candidates as our method. Since the number of iterations 7 is kept fixed, there are some constant overheads in the compute cost such as those coming from the model updates. Therefore the actual speed ups are slightly smaller.
For example, in our experiments with μ = 15 and q = 0.1, the baseline requires x R 6 times more gradient evaluations than our method and when j = 45 and = 0.1 the baseline requires ~ 8 times more gradient evaluations. The actual speed ups are shown in the figures of Section [
4 Dealing with DP-SGD Hyperparameters that Affect the DP Guarantees
Thm. 5 gives RDP-parameters of order a for the tuning algorithm, assuming the underlying candidate picking algorithm is (ax, (()))))RD)) In case of DP-SGD, if we are tuning the learning rate v or clipping constant C, and fix rest of the hyperparameters, these (a,e(a)) -RDP bounds are fixed for all the hyperparameter candidates. However, we are tuning hyperparameters that affect the DP guarantees, i.e., the subsampling ratio 7. the noise level or the length of the training T, it is less straightforward to determine suitable uniform e ((a)) bounds. As is common practice, we consider grid of a-orders for RDP bookkeeping (e.g. integer values of a' s).
4.1 Grid Search with Randomization
To deal with this problem, we first set approximative DP target value (c, 6) that we use to adjust some of the hyperparameters. For example, if we are tuning the subsampling ratio y and training length T, we can, for each choice of (y, T), adjust the noise scale so that the resulting training iteration is at most (s, dD. Vice versa, we may tune y and a, and take maximal value of T such that the resulting training iteration is at most (e, ODDP.
More specifically, we first fix e, 5 > which represent the target approximative DP bound for each candidate model. Denote by e(T, 8, a)) the e-value of the subsampled Gaussian mechanism with parameter values y, a and T and for fixed 5. To each pair of (7. T), we attach a noise scale T,,T such that it is the smallest number with which the resulting composition is (s, DDDP:
T, minfa E R+ <(T, 2, 7, Se).
As the RDP values increase monotonously w.r.t. the number of compositions, it is straightforward to find J,HT, e.g.. using the bisection method. Alternatively, we could fix a few values of a, and to each combination of (7, attach the largest T (denoted T,,x) such that the target (e, 8) guarantte holds.
We consider a finite grid of possible hyperparameter values t (e.g.. = (7, T),, where T is adjusted y and σ). Then, for all / r, we compute the corresponding RDP value (x(a)) for each E A. Finally, for each a E A, we set
E(a)
max (a). tET
Then, since for each random draw of I, the DP-SGD trained candidate model is s(a)-RDP, by Lemma 9 given below, the candidate picking algorithm Q is also (aD)-DDP. This approach used in the experiments of Figure 4 where we jointly tune T, 7 and
4.2 RDP Analysis
For completeness, in Appendix we prove the following result which gives RDP bounds for the case we randomly draw hyperparemeters that affect the privacy guarantees of the candidate models.
Lemma 9. Denote by 3 the random variable of which outcomes are the hyperparameter candidates (drawing either randomly from a grid or from given distributions). Consider an algorithm Q. that first randomly picks hyperparameters
B, then runs randomized mechanism M(t, Suppose M(t, X) is (a,s(a)) -RDP for all t. Then, Q is (e.)=())) RDP.
7

---

Experimental Results
We perform evaluations standard benchmark datasets for classification: CIFAR-10 (Krizhevsky
and Hinton 2009), MNIST (LeCun et al., 1998). FashionMNIST (Xiao et al. 2017) and IMDB (Maas al. 201 Full details of the experiments are given in Appendix A When reporting the results,
set 10 in all experiments.
Learning rate tuning. Figures anddd summarize the results for learning rate tuning using our methods and the baseline method by Papernot and Steinke (022)) The learning rate grid size either 9 or 10 and the grid values are specified in Table 2 (Appendix). We fix the subsampling ratio y and the number of epochs to the values given in Table (Appendix) for all models. The batch sizes the submodels are defined by scaling 7 on the corresponding dataset sizes. We use = 0.1 which means that, for example, if the Poisson subsampling DP-SGD gives expectation batch size of 128 in the tuning phase of our methods, the expected batch sizes for the final models of variant 1 and 2 are 1 1152 and 1280, respectively. We use μ 15 (the expected number of runs for the tuning algorithm).
MNIST, 15
FashionMNIST, 1==5
0.98
0.85
0.84
0.97
0.83
0.96
0.82
0.95
0.81
baseline --- 3.18 our method --- variant 1
0.80
baseline -.. 3.64 our method --- variant our method -.. variant
0.94
0.79
0.93
our method --- variant 2
0.78
no tuning cost - single run
no tuning cost - single run
0.92
0.77
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
final 8
final g
(a) trained with DP-SGD
(b) trained with DP-SGD
CIFAR-10, 1=15
IMDB, 1=
0.74
0.67
0.72
0.70
0.66
0.68
0.66
0.65
baseline --- 6.06 our method - variant 1
0.64
baseline -.. 3.6
our method -- variant
0.62
our method -- variant 2
our method --- variant
0.64
0.60
no tuning cost --_ single run
no tuning cost single run
0.58
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
final g
final E
(c) trained with DP-SGD
(d) trained with DP-SGD
Figure 2: Tuning learning rate with DP-SGD. Test accuracies averaged across 10 independent runs and the error bars denote the standard error of the mean. The numbers in the legends refer to the mean training timings of the baseline scaled with respect minimum of variant and 2. For example, for CIFAR-10, 10, the average training time for the baseline method is 6.06 times bigger than for the fastest of methods. For perspective, we also add curves showing the privacy cost of training single model with optimal hyperparameters obtained from the baseline.
Tuning all hyperparameters. Next, we jointly optimize the number of epochs, the DP-SGD subsampling ratio 7, and the learning rate y) using the hyperparameter candidates given Table 2 (Appendix). The remaining setup is the same in the previous experiment. Figure shows the same

---

MNIST, 1==15
FashionMNIST, 4=
0.97
0.84
0.83
0.96
0.82
0.95
0.81
0.94
baseline --- 8.45 our method --- variant 1
0.80
baseline ... 9.03 our method --- variant
0.93
0.79
our method --- variant 2
our method -.- variant
0.92
no tuning cost - single run
0.78
no tuning cost - single run
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5 3.0
final E
final E
(a) trained with DP-Adam
(b) trained with DP-Adam
CIFAR-10 10, 1=
IMDB, 4=
0.67
0.74
0.72
0.66
0.70
0.65
0.68
baseline --- 4.89 our method -- variant
0.66
baseline ... 3.8
0.64
0.64
our method --- variant
our method --- variant 2
our method --- variant
0.62
0.63
no tuning cost --- single run
no tuning cost single run
0.60
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
final E
final E
(c) trained with DP-Adam
(d) trained with Dd-Adam
Figure 3: Tuning learning rate with DP-Adam. Test accuracies averaged across 10 independent runs and the error bars denote the standard error the mean. The numbers in the legends refer to the mean training timings of the baseline scaled with respect minimum of variant and 2. For example, for FashionMNIST, the average training time for the haseline method 9.03 times bigger than the fastest of methods. For perspective, also add curves showing the privacy cost of training single model with optimal perraraameters obtained from the baseline. Figure 6 (Appendix) shows more detailed version of this plot.
quantities Figures 2 and however, higher values of μ are used to accommodate to increased hyperparameter spaces.
Takeaways. Overall, for both DP-SGD and DP-Adam, we observe that both variants of our method provide better privacy-utility trade-off and have lower computational cost than the baseline method. Additionally, we also note the benefits of tailored analysis (Thm 6) in Figure 2 in terms slightly higher accuracy for variant compared to variant 2 for DP-SGD. In Figure where
are also tuning the batch size and epochs, the noise levels are higher compared to Figure 2 One reason for slightly better privacy-utility trade-off for variant 2 with DP-SGD is possibly the fact that our tailored bound is less tight for higher values of and small values of (see Figure
6 Discussion
We have considered a simple strategy for lowering the privacy cost and computational cost of DP hyperparameter tuning: we carry out tuning using random subset of data and extrapolate the optimal values to the larger training set used to train the final model. We have also provided methods to tune the hyperparameters that affect the DP guarantees of the model training themselves. those

---

MNIST, 4==5
FashionMNIST, 1==50
0.97
0.83
0.96
0.82
0.95
0.81
0.94
0.80
0.93
baseline ..- 5.46 our method --- variant 1
0.79
baseline ... 5.85 our method --- variant
0.92
0.78
0.91
our method --- variant 2
0.77
our method -.- variant
0.90
no tuning cost - single run
no tuning cost single run
0.76
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5 3.0
final E
final E
(a) trained with DP-SGD
(b) trained with DP-SGD
CIFAR-10, 10, 40
IMDB, 41=45
0.67
0.70
0.66
0.68
0.65
0.66
0.64
0.64
baseline --- 6.81 our method -- variant
baseline -.. 9.37 our method --- variant our method --- variant
0.62
0.63
our method --- variant 2
0.62
no tuning cost - single run
0.60
no tuning cost - single run
0.0
0.5
1.0
1.5
2.0
2.5 3.0
0.0
0.5
1.0
1.5
2.0
2.5 3.0
final E
final E
(c) trained with DP-SGD
(d) trained with DP-SGD
Figure 4: Tuming of subsampling ratio, training epochs, and learning rate with DP-SGD. Test accuracies are averaged across 10 independent runs and the error bars denote the standard error of the mean. The numbers in the legends refer the mean timings of the baseline method scaled with respect to the minimum of variant and 2. For perspective, we also add curves showing the privacy cost of training single model with optimal hyperparameters obtained from the baseline. Figure 7 (Appendix) shows more detailed version of this plot.
being the noise level and subsampling ratio in of DP-SGD. Our experiments show clear improvement over the baseline method by Papernot and Steinke 2022) when tuning DP-SGD for neural networks and using simple but well-justified heuristics for the extrapolation. One obvious limitation of our method is that is limited to DP-SGD although we show also positive results for the Adam optimizer combined with DP-SGD gradients. Finding out whether effective scaling rules could be derived for DP-SGD with momentum, DP-FTRL (Kairouz et al. (202I) or more refined adaptive DP optimizers such DP2 Rp2-Ropp Li al. 2023). is left for future work. An interesting avenue of future work is also to find more black-box type of extrapolation methods, something that has been considered in the non-Dr case (see, e.g. Klein al. (017). Another interesting question how to carry out more accurate privacy analysis using the so-called privacy loss distributions (PLDs) and numerical accounting. The main reason for using RDP instead of PLD accounting this work was that the tightest privacy bounds for DP hyperparameter tuning are given in terms of RDP. We have used Poisson subsampling to obtain the tuning set as is relatively easy to analyze, however, other sampling methods could be analyzed as well.
10

---

7 Broader Impact Statement
Our present work makes DP machine learning more appealing and potentially more widespread in practice. This can improve privacy protection in general but can also carry negative side effects. The proposed method can make DP learning more appealing by improving DP hyperparameter tuning leading to higher utility machine learning models at equivalent provable total privacy cost. Our method has lower compute cost than some alternatives, potentially leading to considerable resource savings. While DP gives strong privacy guarantees, it may have negative impacts well, as some DP learning methods have for example been shown to have a relatively lower utility for minorities.
Acknowledgments
We would like to thank our colleague Laith Zumot for discussions about hyperparameter tuning methods at the early stages of the project.
References
Abadi, M.. Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-315
Balle, B., Barthe, G., and Gaboardi, M. (2018). Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, volume 31.
Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE.
Bun, M. and Steinke, T. (2016). Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer.
Canonne, C., Kamath, G., and Steinke, T. (2020). The discrete Gaussian for differential privacy. In Advances in Neural Information Processing Systems, volume 33.
Chaudhuri, K. and Vinterbo, S. A. (2013). A stability- validation procedure for differentially private machine learning. Advances in Neural Information Processing Systems, 26.
Dong, J., Roth, A., Su, W. J., et al. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B, 84(1):3-37.
Dwork, C. (2006). Differential privacy. Proc. 33rd Int. Colloq. on Automata, Languages and Prog. (ICALP 2006), Part 11, pages 1-12.
Gopi, S., Lee, Y. T., and Wutschitz, L. (2021). Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:11631-1164..
Horváth, T. Mantovani, R. G., and de Carvalho, A. C. (2017). Effects of random sampling svm hyper-parameter tuning. In International Conference on Intelligent Systems Design and Applications, pages 968-278, Springer.
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Z. (2021). Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213-5225. PMLR.
Killamsetty, K., Abhishek, G. S., Lnu, A., Ramakrishnan, G., Evfimievski, A., Popa, L., and Iyer, R. (2022). Automata: Gradient based data subset selection for compute-efficient hyper-parameter tuning. Advances in Neural Information Processing Systems, 35:28721-28733.
Killamsetty, K., Durga, S., Ramakrishnan, G., De, A., and Iyer, R. (2021). Grad-match: Gradient matching based data subset selection for efficient deep model training. International Conference Machine Learning, pages 5464-5474. PMLR.

---

Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. In International Conference on Learning Representations.
Klein, A., Falkner, S., Bartels, S., Hennig, P., and Hutter, F. (2017). Fast Bayesian optimization of machine learning hyperparameters on large datasets. In International Conference on Artificial Intelligence and Statistics, pages 228--36. PMLR.
Koskela, A., Jälkö, J., and Honkela, A. (2020). Computing tight differential privacy guarantees using FFT. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569. PMLR.
Krizhevsky, A. and Hinton, G. (2009). Learning multiple layers of features from tiny images. Technical report, University of Toronto.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, (1998). Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11) 1):2278- 11:227-22224
Li, T., Zaheer, M., Liu, K. Z., Reddi, S. J., McMahan, H. B., and Smith, (2023). Differentially private adaptive optimization with delayed preconditioners. In International Conference on Learning Representations.
Liaw, R., Liang, E., Nishihara, R., Moritz, P., Gonzalez, E., and Stoica, (2018). Tune: A research platform for distributed model selection and training. arXiv preprint
Liese, F. and Vajda, (2006). On divergences and informations statistics and information theory. IEEE Transactions Information Theory, 52(10):43944412.
Liu, and Talwar, K. (2019). Private selection from private candidates. In Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, pages 298-309.
Maas, A., Daly, R. Pham, P. T., Huang, D., Ng. A. Y., and Potts, C. (2011). Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150.
Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent as approximate Bayesian inference. Journal of Machine Learning Research, 18:1-35.
McSherry, D. (2009). Privacy integrated queries: an extensible platform for analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19-30.
data
Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE.
Mironov, I., Talwar, K., and Zhang, I.. (2019). Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv:1908.. 10530.
Mohapatra, S., Sasy, S., He, X., Kamath, G., and Thakkar, O. (2022). The role of adaptive optimizers for honest private hyperparameter selection. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7806-7813.
Papernot, N. and Steinke, T. (2022). Hyperparameter tuning with Rényi differential privacy. In International Conference on Learning Representations.
Papernot, N., Thakurta, A., Song, S., Chien, S., and Erlingsson, Ó. (2020). Tempered sigmoid activations for deep learning with differential privacy. In AAAI Conference on Artificial Intelligence.
Sander, T., Stock, P., and Sablayrolles, A. (2022). Tan without burn: Scaling laws of dp-sgd. arXiv preprint arXiv:2210.034000
Smith, J., Asghar, H. J., Gioiosa, G., Mrabet, S., Gaspers, S., and Tyler, P. (2022). Making the most of parallel composition in differential privacy. Proceedings on Privacy Enhancing Technologies, 1:253-273.
12

---

Song, S., Chaudhuri, K., and Sarwate, A. D. (2013). Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing, pages 245-248. IEEE.
Steinke, T. (2022). Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597.
Swersky, K., Snoek, J., and Adams, R. P. (2013). Multi-task Bayesian optimization. Advances in neural information processing systems, 26.
Thakurta, A. G. and Smith, A. (2013). Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pages 819-850. PMLR.
van der Veen, K. L., Seggers, R., Bloem, P., and Patrini, G. (2018). Three tools for practical differential privacy. NeurlPS 2018 Privacy Preserving Machine Learning workshop, arXiv: /8/2.02890
Van Erven, T. and Harremos, P. (2014). Rényi divergence and kullback-leibles divergence. IEEE Transactions Information Theory, 60(7):3777-3220.
Waring, J., Lindvall, C., and Umeton, R. (2020). Automated machine learning: Review of the state-of-the-ard and opportunities for healthcare. Artificial intelligence in medicine, 101:101822.
Xiao, H., Rasul, K., and Vollgraf, R. (2017), Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. Technical report.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D.., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj. A., Zhao, J., et al. (2021). Opacus: User-friendly differential privacy library in PyTorch. In NeurlPS 202/ Workshop Privacy in Machine Learning, arXiv:2109. /2298.
Zhu, Y., Dong, J., and Wang, Y.-X. (2022). Optimal accounting of differential privaey via characteris- tic function. In International Conference Artificial Intelligence and Statistics, pages 4782 4817. PMLR.
Zhu, Y. and Wang, Y.-X. (2019). Poisson subsampled Rényi differential privacy. In International Conference Machine Learning, pages 7634-7642.
13

---

Appendix
A
Full Description of Experiments
Quality Metric and Evaluation. In all of our experiments, we have a partitioning of the available data into train and test sets and we choose the best model based on the test accuracy. The quality score applied on the test set is a relatively low sensitivity function, and therefore, even for a private test set, parallel composition (for an RDP bound of parallel compositions, we refer to Appendix E can accommodate DP evaluation of quality metric in the training budget itself. However, we assume that only the training dataset is private and the test data is public for simplicity. This assumption of test dataset being public and the approach of making only two (train and test) partitions of available data instead of three (train, validation, and test) has been considered in many prior works (Mohapatra itt al. 2022. Papernot and Steinke 2022) to study the proposed method in isolation.
Our utility plots (Figures 2 Figure X show the test accuracy of the final model against the final approximate DP e which includes the privacy cost of the tuning process and of the final model for all methods. We fix 8 10-5 always when reporting the e-values. We fix g = 0.1 for all of our methods in all experiments. We mention that in several cases smaller value of would have lead to better privacy-accuracy trade-off of the final model, however, we use the same value q = 0.1 in all experiments for consistency.
Methods. We consider the both variants of proposed approach in our experiments. The RDP parameters for the variant are obtained by using Thm. (new RDP result) and for variant by combining Thm. | (subsampling amplification) with Thm. (RDP cost of the hyperparameter tuning). We scale the hyperparameters in our methods for the training data of the final model as discussed in Sec. 3.2
The method by Papernot and Steinke (022) described in Thm. is the baseline.
We carry out our experiments on the following standard benchmark datasets for classification: CIFAR-10 10 (Krizhevsky and Hinton| 2009), MNIST (LeCun et al., 1998), Fash- ionMNIST (Xiao et al. 2017) and IMDB (Maas et al. 2011). For MNIST and IMDB, we use the convolutional neural networks from the examples provided in the Opacus library Yousefpour et al. (202I). For FashionMNIST, we consider a simple feedforward 3-layer network with hidden layers of width 120. For CIFAR-IO, 10, we use Resnet20 pre- preitreined on CIFAR- 100 (Krizhevsky and Hinton 2009) dataset so that only the last fully connected layer is trained. We minimize the cross-entropy loss in all models. We optimize with DP-SGD and DP-Adam for all datasets. As suggested by |Papernot ct al. (020)). we replace all ReLU activations with tempered sigmoid functions in CIFAR-10, MNIST, and FashionMNIST networks, which limits the magnitudes of non-private gradients and improves model accuracies.
Datasets and Models.
Hyperparameters. For these datasets, in one of the experiments we tune only the learning rate (1)) and in the other one 1j. " (subsampling ratio), and the number of epochs, while fixing the clipping constant C. For DP-Adam, we do not scale the learning rate. The number of trainable parameters and the hyperparameter grids are provided in Table 2 (Appendix BB. The numbers of epochs are chosen to suit our computational constraints. Following the procedure described in Section 4.1 we always adjust a such that we compute the smallest a that satisfies a target final (c, 5) bound for each (7, epoch) pair. Furthermore following the RDP accounting procedure desribed in Section 4.1 we obtain uniform RDP guarantees for the candidate models and furthermore RDP guarantees for our methods.
Implementation. For the implementation of DP-SGD and DP-Adam, we use the Opacus li- brary (Yousefpour et al. 202T). For scalability, we explore the hyperparameter spaces with Ray dedicated multi-GPU cluster. We use two sets of gpus and one set is
Tune (Liaw et [ 8) much weaker than the other. All three methods have independent randomness (c.g. K hyperparameter candidates sampled, DP noise). Ray tune maintains a job queue and the number of models trained parallelly depends on the gpu count. Each model is trained on 0.5 gpu, and each gpu has enough memory to accommodate 2 models. Models finish their entire training the same gpu that was allocated to them at the start of their training.
Measuring training time. We want to reduce the dependence of our measurements on the available hardware resources (e.g. number of gpus). For each method, we store the per epoch time in seconds for each model being trained in parallel, and finally sum the timings for all epochs of all K models (as if they were trained serially). The clock for each model starts only when is under execution. Among variant 1 and 2, the final training time depends mainly on the value of K sampled, though
14

---

variant trains the final model with slightly smaller data. The baseline method takes much more time run compared our methods on weaker GPUs, which explains the differences in speed gains.
2515
NNST, pm15
UNN51,2-15
1,4
$0.96
Optima
3.10
our mattodd
0.
our curmettodd variant nuring cost gingle nn
0.5
0.5
10
20
25
30
0.0
05
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
2.5
255
30
trained with DP-SGD
FastiorMNSST 1515
Fasiientiis u-15
FashienMSST 1-15
1.0
...0
0.0
3.81
0.20
baseliee..
0.70
144
0.5
1.0
1.5
2.0
2.5
3.0
Snall
trained with DP-SGD
1915 aCCUUsCy
Optrmal 77
baseite 6.05
our ourmethod variant
our metheol variant no brring tost singe nn
2.0
0.
2.0
3.0
Smail
(c) trained with DP-SGD
IMDB, 1-15
MOB y-15
IMD8, gw15
0.74
0.00
30
Optimal
040
single
32
1. 2.0
2.5
0.2
trained with DP-SGD
Figure 5: Tuning only the learning rate with DP-SGD. Test accuracies are averaged across 10 independent runs and the error bars denote the standard error the mean. The number in the legends in the first column refer to the scaled mean training timings for the baseline method with respect to the fastest variant and 2. The second column plots final E vs. mean a. Our methods inject significantly smaller noise compared to the baseline for all regimes. We also observe that due to tight analysis in Thm 6 a for variant is consistently lower than for variant 2. As a result, we see slightly higher accuracy for variant in many cases. The third column plots final
optimal Note that due to randomess in the candidate selection process, optimal 17's s for all three methods need not be the same. For perspective, also add curves showing the privacy of training single model with optimal hyperparameters obtained from the baseline.
15

---

0.97
166 ACCURNO
baselite 8.45
our netheete vitaan
murmetted veriand
Bunking coe singl
final
Snall
Tirllc
(a) trained with DP-Adam
FactinoMNiST 1o15
FashionMMiST 1n
FathionMiST. we15
0.00
0.80
0.79
mathod variand
method varine
0.0023
0.0900
hyning coe aigge
0.0113
0.5
0.5
1.0
1.5
2.0
25
20
0.0
0.
1.0
1.5
2.0
2.5
300
2.0
05
2.0
2.5
2.0
2.5
(b) trained with DP-Adam
CIFAR-10, 15
CIFAR-10, 2=15
CIFAR: g-15
0.010
1e0t sOcuINCS
0.00
baselit
0.000
100
10
final
Srall
fanal
(c) trained with DP-Adei IP-Adam
1515
p-15
p-15
2.070
0.13
25
0.00
beseliiee... 3.8
mothod varbort3
methed 2
10
6:05
bantin cost strgle
47
0.5 0.5
3.0
23
2.5
30
05 0.5
3.0
1.5
2.5
2.5
3.0
0.
0.5
3.0
2.5
2.0
2.5
3.0
(d) trained with DP-Adam
Figure 6: Tuning only the learning rate with DP-Adam. Test accuracies are averaged across 10 independent runs and the error bars denote the standard error of the mean. No learning rate scaling was applied. The number in the legends in the first column refer to the scaled mean training timings for the baseline method with respect the fastest of variant and 2. The second column plots final vs. mean a. Our methods inject significantly smaller noise compared to the baseline for all regimes. We also observe that due tight analysis in Thm a for variant is consistently lower than for variant 2. As result, we see slightly higher accuracy for variant in many cases. The third column plots final vs. mean optimal 17. Note that due to randomess the candidate selection process. optimal r/'s for all three methods need not be the same. For perspective, we also add curves showing the privacy cost of training a single model with optimal hyperparameters obtained from the baseline.
16

---

MNIST,
MINST,
Optmal 21
1.50
Optimal
Dosimnal
2..0
bosettt 3.60
0230
0.01
ou mettod variare
mormeeteddee vartenz
10 luring wingl
Ahate
fnal
Ahal
fnnll
(a) trained with DP-SGD
FathionMMSS 1r
FastionMMiST 1m
FachionWisst uo
PactooMMiST uudt
0.0020
0.60
(..01
Po0.3500
3.00
Optrmal
0.3375
2.79
Doneline
0.3300
3.10
metred Variant1
0.9355
0.70
niinn cost siglle
mette varient2
02230
0.225
0.
05
2.0
25
20
25
02
05
10
25
20
25
3.
0.0
25
1.0
1.
2.
25
20
30
05
1.0
1.1
2.
2.5
20
(h) trained with DP-SGD
CIFAR 60600
GFF8-10 4w40
CFAR-10 p-40
CIFAR-1O 4-
0.224
Lest secunncc
Optimal
6.15
01000
0-010
0:19
2.05
0.014
0.00
Brald A
fnal
Ainal
final
(c) trained with DP-SGD
u-45
4-45
p-44
0.00
Optimaal
Optimal
2.60
E 1
cuT metiedd varient
9.37
0.025
our method vartent
tuning cost aingle
0.55
53
05
3.4
20
50
55
100
25
20
25
3.
00
25
1.0
20
30
05
1.0
1.5
23
2.5
30
(d) trained with DP-SGD
Figure 7: Tuning all hyperparameters (7), epochs, and 7) with DP-SGD. Test accuracies are averaged across 10 independent runs and the error bars denote the standard error of the The numbers in the legends in the first column refer to the scaled mean training timings for the baseline method with respect the fastest of variant 1 and 2. The second column plots final inject significantly smaller noise compared to the baseline for all & regimes even at high values of u. Since there several hyperparameters play together, it is difficult to attribute slightly higher accuracy for variant compared to to any one factor. However, we suspect slight inferiority of our bound for higher values variant 2 could be the main reasons. The third (and fourth) column plots final E vs. mean optimal (and 7). Noise level a is proxy for number of epochs, since we obtain a for each combination of and number of epochs. Therefore, we omit plots showing final vs. epochs plot for readability. Note that due to randomness in the candidate selection process, optimal 17's and 7 for all three methods need not be the same. For perspective, also add curves showing the privacy cost of training single model with optimal hyperparameters obtained from the baseline.
mean a.. Our methods
(Figure right plot) and higher training dataset for the final model in
17

---

FashizuMMist
FaslicuMNSS
FastiorMNiST,
FashiuntNiST
3.01
0.10
>-0.330
0.300
1.70
3.19
0.77
our memoo varbent
besemme 10.13
varentz
0.575
0.550
0.3350
0.2275
baning ringlerun
0.000
finll
fial
rinal
Anal
(a) trained with DP-Adam
CIPAP: 10-60 11:60
CIPAR umd0
CIFAR1D,
CIFR-10.
U.009
lest MECOINE
0.60
0.0550
0.022
04:024
Optimal
0.E045
0.62
tuning oott
metted varient2
varient1
shogle run
MBB
0.0
05
1.0
25
2.
25
20
35
100
2.
2.0
25
3.
0.0
0.5
1.0
1.5
2.0
2.5
2.0
0.0
0.5
1.0
3.5
23
2.5
20
(b) trained with DP-Adam
INDB pwd5
IND8 p-45
IND8, IND8,
JMDB 2w445
0.20
0.050
0.003
Optima
0.10
3..0
mathod
Bialx
fnal
Anal
final
(c) trained with DP-Adam
Figure 8: Tuming all hyperparameters (n) epochs, and ?) with DP-Adam. Test accuracies are averaged across 10 independent runs and the error bars denote the standard errors of the means. The number in the legends in the first column refer the scaled mean training timings for the bascline method with respect to the fastest of variant I and 2. The second column plots final vs. mean a.. Our methods inject significantly smaller noise compared to the baseline for all E regimes even at high values of u.. Since there are several hyperparameters at play together, it is difficuut to attribute slightly higher any one factor. However, we suspect slight inferiority of our
accuracy for variant compared bound for higher values of (Figure [] right plot) and higher training dataset for the final model in variant 2 could be main reasons. The third (and fourth) column plots final & vs. mean optimal (and 7). Noise level a is proxy for number of epochs, since we obtain for each combination of and number of epochs. Therefore, we omit plots showing final e vs. epochs plot for readability. Note that due to randomness in the candidate selection process, optimal and y's for all three methods need not be the same.
18

---

B Hyperparameter Tables
Table 1: Tuning np of the hyperparameters fixed these values. The hyperaparameter grids for the learning rates are the same as in the second experiment and are given in Table 2
MNIST
FashionMNIST
CIFAR-I0
IMDB
0.0213
0.0213
0.0256
0.0256
epochs 40
40
40
110
Table Tuning o, 17 and T: datasets and the corresponding hyperparameter grids.
tainilest
parmeeeess
learning
epochs
MNIST
60K/100K
266
{128, 256)
[10 (C(48662621660000
110 [10")
[10,30,3044)
MNIST
60%/10K
~ 109k
(528,
18)
[10,00330440
CIFAR-10
50%/10K
0.6k
[64, 128)
( [10"
[20.30400]
<-464k
(64, 128)
[10 1c1446326221.11
[70.0.110]
C Proof of Thm 6
Proof. For the proof, let us denote for short Mtume =: M1 and Miuse =: M2. Let E Xm and x' E We first consider bounding the Rényi divergence Da ( (x'))))M(()))) Looking at our approach which uses Poisson subsampling with subsampling ratio to obtain the dataset X and conditioning the output on the randomness in choosing X1, we can write the mechanism as a mixture over all possible choices of X
M(X) Σ Pxi
(C.1)
where px, is the probability of sampling X1. Since each data element is in X2 with probability g, can furthermore write M(X U ( as a mixture
Σ px, (a (M, Uz')), MMM
(C.2)
+ (1--)) (MIMXMMMMMMMMMMMMMMMXMXXXXXXXXX
From the quasi-convexity of the Rényi divergence it follows that
Van Erven and Harremos
2014) and the expres-
sions
C..I and (C.2
Da (M fa (x I sup Da (M
X.
+ (1
(C.3)
Our aim is to express the right-hand side of the inequality (C.3 in terms of RDP parameters of Mi and M2. To this end, take arbitrary X1 C X, and denote by
Ptt) the density function of M
U
P(t) the density function of M1(X1),
(1,,s) s) the density function of M2(1, XXXi U (x')) for auxiliary variable (the output of Mi),
st, the density function of M2 Xi) for auxiliary variable
Then, we see that
((MM(X)),,((MX(X))) =(t,s) P(()) P(t) Q(t,s)
19

---

and similarly that
(1--g) - |MM1 = (t,
= (U = (1,8))
+ (11-0,,(((MM155).MMMMMMxxxXxxx))
(t,s))
= s) + +1 (1-q) P(t) (tt, s).
By the definition of the Rényi divergence, we have that
exp (a
+ (1 ())
= - q P.P(t) Q(t, 8) (1 - Q(t,s) " P(t) Q(t,8)
P(t) Q),, dt ds.
(C.4)
which can be expanded
q: P(()) Q(t,s) + (1 q) P(t) P(U)QQ) P(() ((1,s)
P(I) Q(1, 8) dt ds
= - 9 P(t)
P(()
@(t,)) 8)
+ (1 -1--))
P(t) Q(t, dt ds
(tt,s)
P(()
P(() Q(1, dt ds
P(t)
((t,,))
+ -1)-
P(t) Q(t, ds
(Q(t.s)
(C.5)
+ / a ga-l a-1. (1 (1-
a.ga-1
P(()
a-1
P(t) ((t)) s) dt ds
P(t)
+ / a q. a1
()t,s)
a-1
Q(1,s) P(() dt ds
((1,8)
+ Σ 2
P(t) P(()
a-j
@(t,s) Q(1,8)
a-- 1-- (1 (1-1)²
P(I)
Q(1,)) 8)
di ds.
We next bound five integrals on the right hand side of Equation use the RDP-bounds for M1 and M2 to obtain
C.5
For the first two integrals, we
/
P(1)
(
(((1) ((tt)
P(t) 8) dt ds dsds P(t)
P(t) dt < exp (la ())_a))
(C.6)
and
( @(1,5) -(1,s)
((1,s)((1)d ds s f ((a - 1))2(a)) P(() exp - ())2(a),
(C.7)
where E and 82 give the RDP-parameters order a for Mi and M2, respectively. The third and fourth integral can be bounded analogously. In the second inequality we have also used the fact
20

---

that the RDP-parameters of M2 are independent of the auxiliary variable t. Similarly, for the third integral. we have
P(()
a-j
( ((t.ss)
P(t)
@(t,s) ds dt
P(t)
P(t)
a-j
(C.8)
P(t)
exp (G - 1)E2(i) dt
P(t)
S exp ((ar 1)51(a -)) exp (Gj 1)s2(i)).
Substituting C.6
C.7 (and similar expressions for the third and fourth integral) and (C.8) to
Equation (C.5). we get a bound for the right-hand side of Equation (C.4). Since X1 X was
arbitrary, we arrive at the claim via the inequality (C.3)
Next, we consider bounding Da (M(M(X)))M())) The proof goes similarly as the one for Da (a(MM(Y))M(())) Denote
(a = Da (M(M(I))M((XU(()))
With the notation of proof of Thm. 6 we see that, instead of the right-hand side C.4 we need to bound
exp - 1))2(a)
(a )
-/ʃ
P(t) 8(t,8)
+ (1- P()) (tt, 8)) di ds.
9 P(t) Q(t,s)) + (1 - 4) P(t) ((t,s))
In order use here the series approach, need Lemma 10
P.Q
+ (q-))
(q.
P. Q + (1 -1)) P.Q
a-1
P.Q
.P.Q
P.P.Q (1 (1--)--- .PQ
1-a
P
Q
1 ''p + 4)
P.Q
Q
PQ (1-
1-a
Q
1-n
.PQQ
(C.9)
PQ
Q
PQ (1 9)
1-a
a-1
9 PQ
PPQQ
P
Q
1 "P (1- 9)
.P.Q
P
a-1
Q
9 PP
+ (1-
Q.
21

---

Now we can expand (1: F.8 -1 a-1
where in the inequality we have used Lemma
10
pa)-
P
Q
1 1 4-
pQ)
P.Q
a - q² (1 - (1-9)a-1) 1)--11
P 1
(
) (
P.Q
p
1=0
a-1
$ Q a-)
Σ
a - 1 qp
j ) (1 -1 -1)--11--
.PQ
p
j=0
Σ
a-1
a
j )
1
qp (1 9)
P
j+1
P
Q.
p
1=0
Then, the known E1 (a) and E2 (2(a)-valuu as in the inequalities (C.8) to arrive at the claim.
C.1 Auxiliary Lemma
We need the following inequality for the proof of Thm 6
Lemma 10 (Lemma 35, Steinke 2022). For all p E [0, 1] and (0, oc),
1- $ 1 x.
D Additional Details to Section 4
D.1 Random Search
Here, we assume are given some distributions of the hyperparameter candidates and the algorithm Q draws hyperparameters using them. In order to adjust the noise level for each candidate, we take a-line as an RDP upper bound. More specifically, we require that the candidate models (a, e- a) -RDP for some e > and for all a E A. Then the noise scale og for each draw of (7, T) is the minimum scale for which the (a, c a) -RDP bound holds, i.c.,
Og,7 = min E R+ T (o) S c a for all a E A).
Similarly, we can find the maximum T based on a and y such that the mechanism is (a, c a) RDDP for all E A. Again, by Lemma 9 the candidate picking algorithm Q is then e a-RDP and we may use Thm. 5 to obtain RDP bounds for the tuning algorithm.
D.1.1 Adjusting the Parameters T and for DP-SGD
We next diseuss the reasons for the success of strategies described in Section It is often good approximation to say that the RDP-guarantecs of the Poisson subsampled Gaussian mechanism are lines as functions of the RDP order a, i.c., that the guarantees are those Gaussian mechanism with some sensitivity and noise level values. For example, (Thm. 11, Mironov et al. 2019) show that the Poisson subsampled Gaussian mechanism is (a, 2//a//²) 2/0aa/22-BBB - when a suffiientlyy small. Also, (Thm. 38, [Steinke 2022) show that if the underlying mechanism is p-zCDP, then the Poisson subsampled version with subsampling ratio y is (a, 10, pa)) p RDDP when a is sufficiently small. Notice that the Gaussian mechanism with T--sensitivity A and noise level (A2/260 (22/20²)- zCDP Bun and Steinke 2016).
22

---

We numerically observe, that the larger the noise level a and the smaller the subsampling ratio the better the line approximation of the guaraaarnte (see Figure 9
In case the privacy guarantees (either 6)DDP or RDP) are approximately those a Gaussian mechanisms with some sensitivity and noise level values, both of the approaches for tuning the hyperparameters
and I' described in would lead to very little slack. This is because for the Gaussian mechanism, both the RDP guarantees (Mironov) 2017) and (s, 0)-D guarantees (Dong et al. 2022) depend monotonously on the scaled parameter
This means that if we adjust the training length T based on values of by having some target (6, -boundd for the candidate model with grid search of Section 4.1 the resulting RDP upper bounds of different candidates will not be far from each other (and similarly for adjusting based on value of T). Similarly, for random search of Section D.I when adjusting based on values of a, the RDP guarantees of all the candidate models would be close to the upper bound (c. ar >> 0), i.e., they would not be far from each other.
0.35
Gauss RDP (o-2)
T= 1000
Gauss RDP-Iit (o-2)
6-2. T-
0.30
6m4, T 4000
Gauss RDP fit (o-4)
(a=4)
a= 8000
g=6, 7= 8000
Gauss RDP (a-6)
Gauss RDP fit (o-6)
0.15
0.10
10
20
10
25
DP-SGD RDP curves for different values of noise level a and number of compostions T. Left: y 1/100, right: y 1/50 and the corresponding lines with the smallest slope that give upper bounds for the RDP orders up to a 24.
Figure 9:
D.2 Proof of Lemma
Lemma 11. Denote by 3 the random variable of which outcomes are the hyperparameter candidates (drawing either randomly from grid or from given distributions). Consider an algorithm Q, that first randomly picks hyperparameters
B, then runs randomised mechanism M(t,X), Suppose M(t, X) is (a, (0,)) -RD:))RRDP -RDP for all t. Then, Q is (o,, (a)))
Proof. Suppose the hyperparameters | are outcomes of random variable Let X and Y be neighbouring datasets. Then, if p(l, s) and q((, 8) (as functions of s) give the density functions of X) and M(t, Y), respectively, we have that
Q(X) Ei- s) and Q(Y) ErwB st,
Since for any distributions and q, and for any > exp ((a 1)Da =
((() a(t)
(t) dt
gives an f-divergence (for fxx = x²), it is also jointly convex w.r.t. p and (Liese and Vajda 2006). Using Jensen's 's inequality, we have
/
(Big p(t,s)
a
exp - ((0=1)).(0(X)IIQ
-END g(t, ds
Eing q(t,s))
Er / p(t,, 8)
(((1,)) ds
((1,8))
< Enn exp ((a 1) (M(t.)))MMMM
= exp ((a - 1)s(a))
from which the claim follows.
23

---

E f-Divergence of Parallel Compositions
We first formulate the parallel composition result for general f-divergences (Lemma 12 We then obtain the RDP bound for parallel compositions as a corollary (Cor. 13
Our Lemma 12 below can be seen an f-divergence version of the (s, D)-DP result given in (Thm. 4 McSherry, 2009). Corollary 2 by (Smith et al. 2022) gives the corresponding result in terms of μ u-Gaussian differential privacy (GDP), and it is special case of our Lemma 12 p-GDP equals the (e, 8 (i.e., the hockey-stick divergence) of the Gaussian mechanism with a certain noise scale (Cor. 1. Dong al. 2022).
We define /ddivergence for distributions on I& follows. Consider two probability densities P and Q defined on RR, such that if Q(x)) = 0 then also P(æ) = 0, and convex function f [0, 0o) + R. an
f f-divergence (Liese and Vajda 2006) is defined as
(y(1)) - f P(t) Q(t)
Q(t) dt.
In case the data is divided into disjoint shards and separate mechanisms are applied to each shard, the f-divergence upper bound for two neighbouring datasets be obtained from the individual f-divergence upper bounds:
Lemma 12. Suppose dataset X XN is divided into is disjoint shards X i E [R], and mechanisms M,, E [k:]. are applied to the shards, respectively. Consider the adaptive composition
M(X)
MMM... M Ma-1(Xx-1)))
Then, we have thut
Dj (M(X)IIM(Y) X~Y
max D, (M(()))))M(()) iE[M] X~Y
Proof. Let X and Y be divided into equal-sized disjoint shards and suppose Y is a neighbour- ing dataset such that X and Y differ in jth shard, ie., X2 Yy and Y (Y,, ...... Yx) (X1....,xj-1, Yg, Xft1...., Xx).
Then, we see that
F(M(X) (a)...., ax))
P(M(Y) (a1, ..,, .a))
P(M)(()) 01) .PM)).P(MMM)) PPMM
02) PPMMs 01.,0, ak-1) 41}
P(Mi(( a1) PP(M (Y2, 02) ..P(Mi 01, 0k-1) ak)
(X, 01. Q-)) aj)
(Y.,).)).............. ag)
and furthermore, denoting a = (a1,..., akk),
D((M(I)I(((M))
P(M(Y)= a) da = =Js P(M(Y)= P(M(X)= =0)
= =f1 PXM,((,,, 01 (.,,,))))- a;;
P(M(Y) = a) da
P(M,(Y, 01 (.. a,)
(0-1)
= /s (X,, (X).)))...... a;) P(MM(H)) = a1) -PM)))==)PPPPM(( az)) = 02)
P(M,(Y, a1 (. = a,)
IYM, 01 (1..).,(-11) = =a) de da,
= DD (X,, MI / /P(M = a1) (Y2 = a2)
a)-1) dap daj-1
= -D((M((,))LM,
24

---

Thus,
([(X)))MMM))-)MMM,,,)) & x Dj ()(M,(X))MM((0))
and also, we have that
max X-y
max max Dy ((()(())))MM00)) ZE|M X.
Corollary 13. Suppose a dataset X X is divided into k disjoint shards X i E [R]. and
mechanisms M, i E [k], are applied to the shards, respectively. Consider the mechanism
M(X) (M.(X))..... (x(k))
Suppose each M, (()=;(a)) RDP, respectively. Then, M is (a, max E:(a)) -DDP.
Proof. This follows from Lemma
12
since
exp ( ((co=1))a((())))M0))) - /
P(M(()= =a)
P(M(Y)= = - P(M(Y) - a) da
is an f-divergence for f(x: = 2a. Thus, by Lemma 12 we have that
max exp - ((==I)).((M()))MM)))) < max max exp ((xx ()D_(MM.())
kE(k]
from which it follows that
xay Pa(M(()))M(()) <
max wax [E|k
Dr. (M(M((()))MMM)) = max Er(a))
(E(R]
25


Reviews:
[{"review_id": "SnOoixlnx2", "reviewer": "Reviewer_VkdY", "summary": "The paper addresses private hyper-parameter tuning using privacy amplification by sampling. It introduces two versions of private fine-tuning on a sampled subset, which improves upon existing methods that fine-tune the entire private set. The problem involves deriving amplified privacy analysis and scaling the optimal hyper-parameters back to the original dataset. The authors employ linear scaling for hyper-parameter transfer and provide a Renyi differential privacy (RDP) analysis. Empirical results demonstrate that their approaches achieve better trade-offs between privacy and utility.\n", "questions": "The authors propose to use a linear scaling to transfer hyper-parameters. Is it generally hold for all hyper-parameters? For example, shall we also scale the optimal clipping threshold to the dataset size? ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  The paper builds upon the existing results of \"RDP of hyper-parameter fine-tuning\" and \"amplification by sampling of RDP\" for their privacy analysis. They propose two algorithms for fine-tuning on a sampled set. The first algorithm directly applies the amplification by sampling rule of RDP to the fine-tuning algorithm with a known RDP. The second algorithm involves conducting a hyper-parameter tuning on a subset and then running the mechanism with the selected hyper-parameter on the dataset that does not include the subset.\n\n2. While the contribution of the privacy analysis may appear limited, the authors successfully propose a comprehensive framework capable of tuning both DP and non-DP parameters on a subset. Their empirical results also support their findings regarding the transfer of optimal parameters from the subset to a larger set.", "weaknesses": "The contribution of the paper may be considered  incremental as it combines existing two techniques in a straightforward manner, specifically plugging one mechanism's RDP into another amplification by sampling rule that takes a RDP as an input. The privacy analysis of the second algorithm may be considered the only novel theoretical result in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The privacy analysis of the second algorithm may be considered the only novel theoretical result in the paper.\n\nWe agree that the paper is more on designing a framework for lowering the privacy cost and computational cost of DP-SGD, than on providing new theoretical insights. However, we respectfully disagree with the implicit prerequisite that a DP paper should have a heavy theoretical contribution, especially for a generally applied venue like NeurIPS. As the field has become increasingly applied, there are numerous examples where simple techniques commonly used in non-private settings inspire their DP variants and provide practical utility improvements. While perceived as incremental in retrospect, it is indeed a contribution that our framework gives a much better privacy-utility trade-off and lower computational cost without having to invent a new tuning method/analysis. \n\nNevertheless, in addition to the RDP analysis, we would like to highlight also our Section 4 (and the related theoretical result of Lemma 9, proof given in Appendix D.2) where we give ways to tune the hyperparameters that affect the RDP guarantees of the candidate models (i.e., when not just tuning the learning rate and clipping constant etc.). In Appendix Section E we state the parallel composition for the Rényi divergence (and for $f$-divergences, more generally) which can be used in case we want to have privacy guarantees, e.g., for the test set as well (we could not find a result suitable for RDP composition in the literature).\n\n> The authors propose to use a linear scaling to transfer hyper-parameters. Is it generally hold for all hyper-parameters? For example, shall we also scale the optimal clipping threshold to the dataset size?\n\nNo, this does not hold for all hyperparameters. We explain the DP-SGD scaling in Section 3.2: to keep the privacy costs the same for the candidate models and for the final model, we scale the batch size linearly and keep the noise scale $\\sigma$ the same in the transfer. We also keep the clipping constant the same.\n\nAs requested by reviewer kuHB we also experimented with an adaptive optimizer, DP-Adam. For DP-Adam we used the same scaling of hyperparameters as for DP-SGD except that we did not scale the learning rate. Our method gives positive results then also (see the attached pdf file)."}, {"review_id": "o8eRNLTCbc", "reviewer": "Reviewer_zJd6", "summary": "This work proposes a practical variant of tuning hyperparameters under differential privacy (DP) which has a better privacy-utility tradeoff and less computational time compared to the SOTA private hyperparameter tuning algorithm. Instead of using all datasets to tune hyperparameters as in previous works, this work proposes to use a subsampled dataset for hyperparameter tuning and provides a Renyi DP (RDP) analysis of the proposed approach. In addition, this work considers tuning hyperparameters that can affect the privacy loss. Both theory and experimental results demonstrate the superior performance of the proposed approach in terms of the utility-privacy tradeoff and computation time.", "questions": "There is no description of the subsampling ratio $\\gamma$. Is $\\gamma$ the subsampling ratio for selecting minibatches in DP-SGD? \n\nRegarding figure 1:\n\n-\tAre the blue curves generated by taking max{Eq.(3.6), Eq.(3.7)} in Theorem 6?\n-\tWhat is the alpha used here?\n-\tSince the caption says “($\\epsilon$, $\\delta$)”-bounds, is it that the privacy loss of the proposed method is stated in RDP, and when generating the plots for comparison, the RDP bound is converted to a DP bound?\n-\tIs the $\\delta$ part in the DP bound comparable?\n\nWhat is $\\Delta W$ in Eq.(3.3)?\n\nLine 227: What is $\\Lambda$ (the set containing all alpha values) used in the experiments?\n\nWhat are the major challenges of analyzing an extended version of this approach to tune the hyperparameters of other private optimizers, e.g., DP-Adam? \n\nMinor comments: when describing the approach (line 126 ~ 132) it might be clearer to use different letters for the base algorithm and the hyperparameter tuning algorithm.\n\nMinor issue: M subsample Poisson(q) should be M subsample Poisson ($\\gamma$) in Theorem 4.\n\nMinor issue: it seems the right parentheses is missing in Eq.(3.1), Eq.(3.2). \n", "limitations": "Limitations and broader impact are well discussed in the main paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Clear and well-structured presentation.\n\nSimple yet effective approach.\n\nInteresting results.\n", "weaknesses": "There are a few confusing points. See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for all these comments and suggestions. These will definitely improve the readability of the paper.\n\n> There is no description of the subsampling ratio $\\gamma$. Is the subsampling ratio for selecting minibatches in DP-SGD?\n\nYes, it is the subsampling ratio for DP-SGD. Its meaning is stated explicitly only on line 141 although we use the notation in the statement of Theorem 4 (line 100). We will add a clarification of the notation before Thm. 4. \n\n> Regarding figure 1:\n\n> Are the blue curves generated by taking max{Eq.(3.6), Eq.(3.7)} in Theorem 6?\n\nYes. By Def. 2, $\\mathcal{M}$ is $\\varepsilon(\\lambda)$-RDP for max{Eq.(3.6), Eq.(3.7)} . We will add a line in the statement of Thm. 6 where we describe that the mechanism $\\mathcal{M}$ is $\\varepsilon(\\lambda)$-RDP for maximum of the expressions given in Eq.(3.6) and Eq.(3.7). This should make it more readable. \n\n> What is the alpha used here?\n\nWe convert the RDP-bounds to $(\\varepsilon,\\delta)$-bounds using Lemma 3 (Eq. (2.2)), as described on lines 85-87. The statement of Lemma 3 holds for any $\\alpha$ so we minimize the expression of Eq. 2.2. w.r.t. $\\alpha$ (a common practice). For Figure 1, $\\varepsilon(\\lambda)$ is always evaluated using our Theorem 6. We will add on line 87: “minimizing over the values given by (2.2) w.r.t. $\\alpha$.” and add a short description to lines 193-197 that we use Lemma 2 for the conversion. \n\n> Since the caption says “($\\varepsilon,\\delta$)”-bounds, is it that the privacy loss of the proposed method is stated in RDP, and when generating the plots for comparison, the RDP bound is converted to a DP bound?\n\nYes, exactly, we convert using Lemma 2, as described on lines 85-87. We will add a short description to lines 193-197 to clarify this.\n\n> Is the $\\delta$ part in the DP bound comparable?\n\nYes, in all plots of Fig. 1 $\\delta$ is fixed to $10^{-5}$, but we notice we have not stated this value. We will add it to lines 193-197. This is only mentioned on line 402 of the Appendix, we will add this also in the experiments section.\n\n> What is $\\Delta W$ in Eq.(3.3)?\n\nHere is a typo, there should be $\\Delta W \\sim \\mathcal{N}(0, I_d)$. The same thing in Eq. (3.4).\n\n> Line 227: What is $\\Lambda$ (the set containing all alpha values) used in the experiments?\n\nWe use integer $\\alpha$’s 2 to 64. We will add this at least in the Appendix. Using an integer grid is a common practice in software implementations (e.g. TF privacy) as well. We would be free to choose any grid on $(1,\\infty)$, however we do not see noticeable improvement in ($\\varepsilon,\\delta$)-bounds by enlarging or refining the $\\Lambda$ - grid.\n\n> What are the major challenges of analyzing an extended version of this approach to tune the hyperparameters of other private optimizers, e.g., DP-Adam?\n\nOne challenge is that we don’t have similar reasoning about the scaling of hyper parameters as we have for DP-SGD (our section 3.2). However, we heuristically find that we get similar improvements when we tune DP-Adam: the scaling of hyperparameters is same as for DP-SGD (Sec. 3.2), except that we keep the learning rate the same when training the final model with the larger dataset. See the attached pdf for experimental comparisons.\n\n> Minor comments: when describing the approach (line 126 ~ 132) it might be clearer to use different letters for the base algorithm and the hyperparameter tuning algorithm.\n\nThank you, this is a good suggestion, we will try to think of a better notation.\n\n> Minor issue: M subsample Poisson($q$) should be M subsample Poisson ($\\gamma$) in Theorem 4.\n> Minor issue: it seems the right parentheses is missing in Eq.(3.1), Eq.(3.2).\n\nIndeed, thank you!"}, {"review_id": "YZ2dfDUGUv", "reviewer": "Reviewer_on32", "summary": "This paper is about the efficient tuning of hyperparameters of machine learning models in a differentially private (DP) way. Previous works have shown that hyperparameter optimization can be computationally demanding and, more importantly, often uses sensitive data that might get leaked. However, this leakage can be reduced. Specifically in this paper, the authors aim for lowering not only the DP bounds but also the computational demand. The latter is achieved by only using a random subset of data for the hyperparameter optimization. As in previous work, a Rényi DP analysis is provided. Experiments under various settings and data sets demonstrate a better privacy-performance trade-off than baseline competitors while also being faster.", "questions": "- Q1: What is meant by \"extrapolate the hyperparameter values to a larger dataset\"? Can you provide an example? It is mentioned multiple times (lines 10, 43, 123, 131, ...) and I think it should be clarified (earlier). If the main example is in lines 140-146, I think it might help to tease it earlier as I was unsure what might be meant by extrapolating. Additionally, is there another example of extrapolation of hyperparameters?\n- Q2: Why is $X_1$ being excluded from $X$ in step 4 in line 132? I see the second variant as being meaningful but what is the motivation/intuition/reasoning behind variant 1?\n- Q3: Regarding the adjustment of the learning rate (lines 140-146): Didn't van der Veen et al. (2018) consider a change in batch size with a fix data set size? If the same batch size is used for the subsampled data set and the data set, it should not matter, or?\n- Q4: I am slightly confused by the difference of $\\gamma$ and $q$, i.e., in Theorem 4 (and lines 193-197). My understanding is that $\\gamma$ is for the batch and $q$ is for the subset $X_1$ (line 126). Can you clarify the difference between $\\gamma$ and $q$?\n- Q5: Can you elaborate on how Figure 1 was created? As in, where do the numbers come from and how do the specific choices (title of the subfigures) go into that?\n- Q6: Can you elaborate on what is shown in Figures 2 and 3? Is the complete hyperparameter optimization cycle run ten times and the figures show the averaged test accuracies of the final models (i.e., the ten models with the best hyperparameters)? What are the individual dots per line?\n- Q7: The choice of $\\mu$ is fixed for Figure 2 but quite differs in Figure 3. CIFAR-10 is harder than MNIST but has less \"candidate models\". How did you come up with those $\\mu$ values? Does CIFAR-10 has the smallest $\\mu$ because it uses a pre-trained model and all others are trained from scratch?\n- Q8: How is the choice of Adam (DP-SGD gradients) justified when the results only hold for DP-SGD? Did IMDB not work with DP-SGD? What was the reason for this choice?\n- Q9: Can you provide a table with data set sizes (and dimensionalities) as well as the used subset sizes?\n- Q10: Regarding the computational savings it is stated that the number in the plots next to baseline refers to the mean training time of the baseline scaled wrt the minimum of the variants. Can you provide more insight in those computational savings? Is it just the worst performing model on the smallest subset that yielded this saving once? Are your variants sometimes even slower than the baseline? Is there a substantial difference between the variants?", "limitations": "Limitations and potential negative societal impact are discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- the problem of having efficient differentially private strategies for hyperparameter optimization is relevant and important\n- using subsampling to improve the computational efficiency and using its privacy amplifying effect is natural\n- the paper is mostly easy to read and follow (there are some issues, see below)\n- the theoretical analysis and experimental evaluation shows that either a better performance for the same privacy budget or a better privacy budget for the same performance can be achieved\n- the approach is computationally less demanding than previous works", "weaknesses": "Overall, the paper appears to be solid, however, I think the paper lacks (a bit of) clarity. Some concepts (e.g., extrapolating hyperparameters) are insufficiently or too late introduced and other choices such as the training on all data but the previously used subset are insufficiently justified. Similar clarity issues appear for the mathematical notation. Moreover, the language should be revised/improved. However, I believe that those issues can be fixed. For almost all points, I provide a list of remarks, suggestions, and questions below. \n\n\n### Remarks:\n- Section 1.1: Using subsets for hyperparameter tuning specifically for deep learning models (in a non-DP setting) was also recently considered, e.g., in:\n\t- Killamsetty, K., Durga, S., Ramakrishnan, G., De, A., & Iyer, R. (2021, July). Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning (pp. 5464-5474). PMLR.\n\t- Killamsetty, K., Abhishek, G. S., Lnu, A., Ramakrishnan, G., Evfimievski, A., Popa, L., & Iyer, R. (2022). Automata: Gradient based data subset selection for compute-efficient hyper-parameter tuning. Advances in Neural Information Processing Systems, 35, 28721-28733.\n- Definition 2: How is $\\mathcal{M}$ an output distribution?\n- Theorem 4: Consider mentioning/introducing $\\gamma$ for completeness.\n- line 106: I consider \"number of candidate models $K$\" is sub-optimally phrased. A hyperparameter can also be the learning rate, which does not change the model, but the optimization/learning of it. Perhaps something like \"the number of runs $K$ within the hyperparemeter tuning\" is clearer? This related to my first minor remark (lines 4-5).\n- Theorem 5: The notation $\\mathcal{X}^N$ was used in Papernot and Steinke but the superscript $N$ was not introduced in this paper. Besides, $n$ instead of $N$ was used. Moreover, $\\mathcal{Y}$ denotes the outputs in Papernot and Steinke whereas in this paper, $\\mathcal{O}$ was used!\n- line 128: How is $\\mathcal{M}_1$ different from $A$ in Theorem 5? Both are \"hyperparameter tuning algorithms\".\n- line 130: Aren't $\\theta_1$ the model *parameters* instead of the model itself? In Equation (2.3), $f$ is the model with parameters $\\theta$.\n- Equation (3.1): $\\mathcal{M}_1(X_1)$ returns a tuple but in Equation (3.1) it is assumed that it only returns the second entry of that tuple. Besides, the output of $\\mathcal{M}(X)$ would then be $((\\theta_1, t_1), \\theta_2)$.\n- Theorem 6: The notation $\\mathcal{X}^n$ was never introduced. Besides, if a data set $X$ is an element of $\\mathcal{X}$, then a single data point $x$ cannot be. Instead, it should be $x$ in curly brackets, no?\n- Lemma 9: First, $C$ was used as a scalar within the clipping strategy. Hence, the variable name cannot be used anymore for something else. Second, $\\mathcal{M}$ never took $t$ as an argument before. Consider adapting the notation.\n\n\n\n### Minor remarks and suggestions:\n- lines 4-5, 35-36: I think \"where the number of random search samples is randomized itself\" could be stated more clearly.\n- line 21, 96, 105, 107, 253, 280: however,\n- line 34: \"provided a\" instead of \"gave\" (there should be an a)\n- lines 53, 56, 225: w.r.t. the number\n- line 54: \"than\" instead of \"then\"\n- line 56: In a non-DP\n- line 74: curly brackets for sets\n- line 85: \"As is common in practice,\"\n- line 87 (and others): Equation (2.2)\n- line 90: to have an $L_2$-norm of at most\n- Equation (2.3): Consider mentioning $f$ and $\\theta$ for completeness. You could also connect $Z_j$ with the noise mentioned in line 90.\n- line 95, 106, 171: Wrong citation style (direct instead of indirect, i.e., by Zhu and Wang, (2019)).\n- line 97: If you want to gain space you can try adding `\\looseness=-1` after \"method.\" which tells $\\LaTeX$ to try to fit \"method.\" into the paragraph. Might also work for the caption of Figure 3. It is a neat trick worth knowing.\n- line 124: Inconsistent capitalization: Method should be capitalized\n- line 129: the method by\n- line 134: either use or consider\n- Consistency: \"dataset\" vs \"data set\" (e.g., lines 131 vs 134)\n- line 135: Math (Equation (3.2)) is always a part of a sentence. Hence, use rather a colon instead of a full-stop.\n- line 136: , respectively\n- line 137: with a standard [...] Theorem 4\n- line 142: The number of iterations $T$ appear for the first time. Consider introducing them earlier, i.e., around lines 89-97.\n- line 165: Adam is an ICLR paper, not a preprint.\n- line 169: the learning rate\n- Consistency: \"Thm.\" vs \"Theorem\" (e.g., lines 173 vs 212)\n- line 193-194: methods [...] as functions\n- line 194: mechanism DP-SGD is run\n- It is slightly confusing to mix \"variants 1 and 2\" and \"(3.1) and (3.2)\".\n- Figure 1: the three dashed lines between \"our method\" and \"variant\" might be confusing in black and white prints since they look like the blue curve. The crossing of lines around $q=0.1$ could be highlighted with an arrow.\n- Consistency: $E$ vs E in lines 202-204.\n- [Section 4.1 (but also before): It is slightly weird that some lines are missing line numbers.]\n- Section 5: Please name briefly at least the data sets and the learning task. Space can be gained be vertically shrinking Figures 2 and 3.\n- line 245: on the\n- line 247: 1150 and 1278, respectively.\n- line 251: Next,\n- line 254: typo in hyperparameter\n- Figure 2: What about \"$6.06 \\times$ slower\"? Perhaps that is more clear/less confusing.\n- Figure 2 caption: Figure 4 (appendix) shows a more detailed version of this figure.\n- line 273: e.g. already means for example\n- line 276: \"question is\" or \"questions are\"\n- line 280: remove on\n- Tables: Captions go above tables and vertical lines should be avoided, see https://media.neurips.cc/Conferences/NeurIPS2023/Styles/neurips_2023.pdf\n\n### After the Rebuttal:\nI have read all other reviews and all rebuttals. Furthermore, I thank the authors for their answers and the additional insights provided in the extra rabuttal pdf. I keep my original score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the careful reading. Addressing these comments will definitely improve the paper. Thank you also for the references on related non-DP methods that went unnoticed, we will add them to the literature section. Below we answer the questions, we will address the minor remarks and suggestions in the possible final version of the paper.\n\n> Q1: What is meant by \"extrapolate the hyperparameter values to a larger dataset\"? \n\nThank you for pointing out this. We are thinking of the optimal hyperparameters as a function of the dataset size, and by finding the optimal values for a small dataset, we can determine the hyperparameter values for the larger dataset using our scaling rules (Section 3.2). We admit that this is a bit vaguely expressed and we can change the word ‘extrapolating’ to ‘transferring’. For example on line 10 we could say instead: \"… and by transferring the optimal values to a larger dataset.”, on line 131 “ Transfer the hyperparameters $t_1$ to the dataset…”.\n\n> Q2:  .. what is the motivation/intuition/reasoning behind variant 1?\n\nBy dedicating $X_1$ for the tuning part, the overall privacy costs becomes smaller since $X_1$ does not participate on the final model training (see Fig. 1). We also have in mind some practical scenarios, where there could be a data owner that would only report the optimal hyperparameters. Although not reflected by the DP guarantees, one could claim that the attack surface of the hyperparameter values is small compared to the model parameters and thus the tuning data would have a different kind of protection. One could think of, e.g., a federated learning scenario, where this could be utilized.\n\n> Q3: Didn't van der Veen et al. (2018) consider a change in batch size with a fix data set size?\n\nYou are right, van der Veen et al. scale with the batch size. We will replace “dataset size” with “batch size” on line 145. In our case however these are equivalent, since in order to have the same privacy guarantees for the candidate models trained using the small dataset and using the large dataset, we need to keep the subsampling ratio constant (which means scaling the batch size).\n\n>Q4: ... My understanding is that $\\gamma$ is for the batch and $q$ is for the subset $X_1$ (line 126). \n\nIndeed, $\\gamma$ is for the mini batches and $q$ is for the subset $X_1$. There is a typo in statement of Thm. 4: $q$ should be $\\gamma$. We will add a short clarification before Thm. 4 on the meaning of $\\gamma$.\n\n> Q5: Can you elaborate on how Figure 1 was created? As in, where do the numbers come from and how do the specific choices (title of the subfigures) go into that?\n\nThese are simply some commonly used parameter values for DP-SGD (see, e.g., the experiments of Abadi et al., 2016) used to illustrate the differences between the various DP bounds. Notice that increasing $\\mu$ increases the privacy cost of the tuning part.\n\n>Q6 (Figures 2 and 3) Is the complete hyperparameter optimization cycle run ten times and the figures show the averaged test accuracies of the final models ... ? \n\nYes, exactly, with 10 different seeds.\n\n>What are the individual dots per line?\n\nEach dot corresponds to different overall $(\\varepsilon,\\delta)$-bound we predefine. In case of learning rate tuning (Figure 2) we keep the subsampling ratio $\\gamma$ of DP-SGD constant and the $\\sigma$ will be determined by the $\\varepsilon$-bound ($\\delta$ is fixed to $10^{-5}$ as described in the appendix). In Figure 3, where we tune also $\\gamma$ and number of epochs, $\\sigma$ is again determined by the $\\varepsilon$-bound. We will clarify this more carefully.\n\n> Q7: How did you come up with those $\\mu$ values? Does CIFAR-10 has the smallest because it uses a pre-trained model and all others are trained from scratch?\n\nYes, that is roughly the reasoning. Pretrained CIFAR-10 is a fairly small convex model (only the last layer trained). Fashion MNIST has the most number of hyperparameter choices (80 combinations in total, see Appendix Table 2) so it has slightly larger $\\mu$ than IMDB and MNIST (54 and 72 combinations, respectively). However, we believe we would observe similar improvements also when fixing $\\mu$ values, as the baseline method uses the same $\\mu$ values as well.\n\n> Q8: How is the choice of Adam (DP-SGD gradients) justified when the results only hold for DP-SGD? Did IMDB not work with DP-SGD? What was the reason for this choice?\n\nThis was choice was dictated by the Opacus repository recommendation: Adam with DP gradients seems to work better than DP-SDG for IMDB (https://github.com/pytorch/opacus/blob/main/examples/imdb_README.md). We observed that tuned DP-SGD was better using our approach than using the baseline tuning method (see the first figure in the attached pdf file). \n\n> Q9: Can you provide a table with data set sizes (and dimensionalities) as well as the used subset sizes?\n\nYes, we will add this in the appendix.\n\n> Q10: Are your variants sometimes even slower than the baseline? Is there a substantial difference between the variants?\n\nIn expectation our variants are much faster than the baseline. The main speedup comes from the fact that in the tuning procedure our methods run in expectation the same number of candidate models as the baseline, however with much less data. For same combination of hyperparameters values, for training a candidate model, our methods run the same number of iterations as the baseline, however with much smaller batches (since the subsampling ratio is kept constant). E.g., if the tuning set $X_1$ is 10 times smaller than the whole data $X$, there will be in expectation 10 times fewer gradient evaluations in the tuning procedure, compared to the baseline. Our variant 1 is slightly faster than variant 2, since the final model training is carried out with less data, however the overall difference is small."}, {"review_id": "ue9KmPRDsd", "reviewer": "Reviewer_kuHB", "summary": "The paper focuses on the problem of differentially private (DP) hyperparameter tuning for DP ML algorithms. The authors propose a method that subsamples the sensitive data for hyperparameter tuning, and extrapolates optimal values from the small dataset to the larger dataset. The authors provide a Renyi DP (RDP) analysis for their method, show that their method lowers the DP bound and computational complexity of hyperparameter tuning, and empirically show their method leads to better privacy-utility trade-offs than the existing SOTA method.\n", "questions": "I have listed the main limitation I felt in the weaknesses section.\n\n\n------------\nPost-rebuttal update: It is great to see the authors being able to provide guidance on DP-Adam using their tuning! I am raising my score since this addresses my main concern for the paper. ", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper focuses on improving private hyperparameter tuning from all facets: using subsampled inputs to save on privacy cost, using the model output by the tuned choices for initializing the training over the larger dataset, as well as extrapolating optimal values for various hyperparameters from the smaller dataset to the larger dataset.\n2. The paper is well written.\n", "weaknesses": "Though the authors discuss this in Section 6, I feel one of the main shortcomings of the proposed method is the extrapolation heuristics designed specifically for DP-SGD. Having the method being applicable to commonly used adaptive optimizers (also discussed in Section 6) would make it more general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Though the authors discuss this in Section 6, I feel one of the main shortcomings of the proposed method is the extrapolation heuristics designed specifically for DP-SGD. Having the method being applicable to commonly used adaptive optimizers (also discussed in Section 6) would make it more general.\n\nWe believe our method is applicable also to other optimizers, however the scaling laws may need to be considered case by case for each optimizer. In the attached pdf file we show positive results for Adam with DP gradients. We use the same scaling of the hyperparameters as for DP-SGD except that we keep the learning rate constant when transferring the optimal hyperparameters from the tuning dataset to the larger dataset. This can be heuristically motivated by the non-DP case. For example, the original Adam paper by Kingma and Ba (2015) (https://arxiv.org/pdf/2305.13209.pdf) recommends using the same initial learning rate $\\alpha=0.001$ for all (non-DP) ML model training. We experimentally found that the DP-SGD scaling where we scale the learning rate proportionally to the dataset size works poorly for DP-Adam. We plan to add the DP-Adam results to the appendix.\n\nLastly, we think that building a working hyperparameter tuning framework for DP-SGD which cuts the privacy costs and saves computations is already sufficient for a single paper. More generally, we think any practical and well-motivated solution is a worthwhile contribution on its own even if it would be limited to DP-SGD."}]

Author rebuttal:
We would like to thank all the reviewers for their helpful comments! Addressing them will definitely improve the paper, and our impression is that the required changes are not major. We have replied each review below individually.

We have attached a pdf file with new figures. Here background on them:

Reviewer on32 had a question

> How is the choice of Adam (DP-SGD gradients) justified... Did IMDB not work with DP-SGD? What was the reason for this choice?

Indeed DP-SGD with our tuning method seems to work also for IMDB. The results of the Opacus repository indicated that DP-Adam is the best choice (https://github.com/pytorch/opacus/blob/main/examples/imdb_README.md). However tuned DP-SGD seems to give similar results, and our tuning method is competitive then also. A comparison is given in the pdf.

Reviewer kuHB commented:

> Having the method being applicable to commonly used adaptive optimizers (also discussed in Section 6) would make it more general.

To this end, we have experimented with DP-Adam now on all the four datasets considered, and we notice that we can improve upon the baseline tuning method for DP-Adam as well. The IMDB comparison can already be found in the main text, rest of the DP-Adam comparisons for the learning rate tuning are in the attached pdf.

For DP-Adam we change the learning rate scaling used of DP-SGD (Section 3.2 in our paper) such that we keep the learning rate the same when transferring the optimal hyperparameters to the larger dataset. This can be heuristically motivated by the non-DP case. For example, the original Adam paper by Kingma and Ba (2015) (https://arxiv.org/pdf/2305.13209.pdf) recommends using the same initial learning rate $\alpha=0.001$ for all (non-DP) ML model training. We experimentally found that the DP-SGD learning rate scaling works poorly for DP-Adam. We plan to include the DP-Adam comparisons to the appendix.

Meta-review: This paper proposes methods for making differentially private hyperparameter tuning more efficient. The paper builds on existing tools for differentially private hyperparameter optimization that are not efficient if used directly. To make them efficient, it relies on privacy amplification by sampling, plus heuristics for extrapolating hyperparameter performance on a sample to the full dataset.

This work addresses an important practical problem. It carefully combines various tools to develop a theoretically sound solution and then provides an experimental evaluation. Overall, the reviewers found this submission to be clear and interesting and thus support acceptance at NeurIPS.
Decision: Accept (poster)