DP-HyPO: An Adaptive Private Framework for Hyperparameter Optimization
Authors: Hua Wang
Sheng Gao
Huanyu Zhang
Weijie J Su
Milan Shen
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Hyperparameter Tuning
Deep Learning
TL;DR: We propose the first adaptive private hyperparameter optimization framework - DP-HyPO; it allows practitioners to freely use existing non-DP hyperparameter optimization methods at a small extra privacy cost.

Abstract: Hyperparameter optimization, also known as hyperparameter tuning, is a widely recognized technique for improving model performance. Regrettably, when training private ML models, many practitioners often overlook the privacy risks associated with hyperparameter optimization, which could potentially expose sensitive information about the underlying dataset.
Currently, the sole existing approach to allow privacy-preserving hyperparameter optimization is to uniformly and randomly select hyperparameters for a number of runs, subsequently reporting the best-performing hyperparameter.
In contrast, in non-private settings, practitioners commonly utilize "adaptive" hyperparameter optimization methods such as Gaussian Process-based optimization, which select the next candidate based on information gathered from previous outputs.
This substantial contrast between private and non-private hyperparameter optimization underscores a critical concern. In our paper, we introduce DP-HyPO, a pioneering framework for "adaptive" private hyperparameter optimization, aiming to bridge the gap between private and non-private hyperparameter optimization. To accomplish this, we provide a comprehensive differential privacy analysis of our framework. Furthermore, we empirically demonstrate the effectiveness of DP-HyPO on a diverse set of real-world datasets.

DP-HyPO: An Adaptive Private Hyperparameter Optimization Framework
Hua Wang
Sheng Gao
Department of Statistics and Data Science
Department of Statistics and Data Science
University of Pennsylvania Philadelphia, PA 19104
University of Pennsylvania Philadelphia, PA 19104
wanghua@wharton. wpw.n. edu
shenggao@xharton. upw.n. edu
Huanyu Zhang
Weijie J. Su
Meta Platforms, Inc. New York, NY 10003
Department of Statisties and Data Science
University of Pennsylvania Philadelphia, PA 19104 suw@wharton upenn edu
huanyuzhangdmest..cmm
Milan Shen
Meta Platforms, Inc Menlo Park, CA 94025
mi lanshen@gmail com
Abstract
Hyperparameter optimization, also known as hyperparameter tuning, is widely recognized technique for improving model performance. Regrettably, when training private ML models, many practitioners often overlook the privacy risks associ- ated with hyperparameter optimization, which could potentially expose sensitive information about the underlying dataset. Currently, the sole existing approach to allow sivaacy-reeeervng hyperparameter optimization to uniformly and ran- domly select hyperparameters for a number of runs, subsequently reporting the best-performing hyperparameter. In contrast, in non non-private settings, practition- ers commonly utilize "adaptive" hyperparameter optimization methods such Gaussian process-basse based optimization, which select the next candidate based on information gathered from previous outputs. This substantial contrast between private and non- non-private hyperparameter optimization underscores a critical con- cemn our paper, we introduce DP-HyPO, a pioneering framework for "adaptive" private hyperparameter optimization, aiming to bridge the gap between private and non-private hyperparameter optimization. To accomplish this, we provide comprehensive differential privacy analysis of our framework. Furthermore, we empirically demonstrate the effectiveness of DP-HyPO on a diverse set of real-world datasets.
Introduction
In recent decades, modern deep learning has demonstrated remarkable advancements various applications. Nonetheless, numerous training tasks involve the utilization of sensitive information
pertaining to individuals, giving rise to substantial concerns regarding privacy 22 6). To address
these concerns, the concept of differential privacy (DP) was introduced by 012 13.. DP provides
mathematically rigorous framework for quantifying privacy leakage, and it has gained widespread
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

acceptance as the most reliable approach for formally evaluating the privacy guarantees of machine learning algorithms.
When training deep learning models, the most popular method to ensure privacy is noisy (stochastic) gradient descent (DP-SGD) 353 DP-SGD typically resembles non-private gradient-based methods; however, it incorporates gradient clipping and noise injection. More specifically, each individual gradient clipped to ensure bounded Eg norm. Gaussian noise is then added to the average gradient which is utilized to update the model parameters. These adjustments guarantee a bounded sensitivity of each update, thereby enforcing DP through the introduction of additional noise.
In both non private and private settings, hyperparameter optimization (HPO) plays a crucial role in achieving optimal model performance. Commonly used methods for HPO include grid search (GS), random search (RS), and Bayesian optimization (BO). GS and RS approaches are typically non-adaptive, they select the best hyperparameter from a predetermined or randomly selected set. While these methods are straightforward to implement, they can be computationally expensive and inefficient when dealing with large search spaces. As the dimensionality of hyperparameters increases, the number of potential trials may grow exponentially. To address this challenge, adaptive
HPO methods such as Bayesian optimization have been introduced [34] 14 40). BO leverages
probabilistic model that maps hyperparameters to objective metrics, striking a balance between exploration and exploitation. BO quickly emerged as the default method for complex HPO tasks, offering improved efficiency and effectiveness compared to non-adaptive methods.
While HPO is a well-studied problem, the integration of DP constraint into HPO has received little attention. Previous works on DP machine learning often neglect to account for the privacy cost associated with HPO [ 39
These works either assume that the best parameters known in advance or rely on a supplementary public dataset that closely resembles the private dataset distribution, which not feasible in most real-world scenarios.
Only recently have researchers turned to the important concept of honest HPO 28, where the privacy cost during HPO cannot be overlooked. Private HPO poses greater challenges compared to the non non-private case for two primary reasons. First, learning with DP-SGD introduces additional hyperparameters (c.g.. clipping norm, the noise scale, and stopping time), which hugely adds complexity to the search for optimal hyperparameters. Second, DP-SGD is more sensitive to the selection of hyperparameter combinations, with its performance largely influenced by this choice 28 [0]31]
To tackle this challenging question, previous studies such 124 32 propose running the base algorithm with different hyperparameters a random number times. They demonstrate that this approach significantly benefits privacy accounting, contrary to the traditional scaling of privacy guarantees with the square root of the number of runs (based on the composition properties from [19). While these papers make valuable contributions, their approaches only allow for uniformly random subsampling from a finite and rre-fixed set of candidate hyperparameters at each run. As a result, any advanced technique from HPO literature that requires adaptivity is either prohibited or necessitates a considerable privacy cost (polynomially dependent on the number of runs), creating a substantial gap between non-private and private HPO methods.
Given these considerations, a natural question arises: be adaptive, without a huge privacy cost? In this paper, we provide affirmative answer to this question.
Can private hyperparameter optimization
1.1 Our Contributions
We introduce the pioneering adaptive private hyperparameter optimization frame- work, DP-HyPO, which enables practitioners to adapt to previous runs and focus on potentially superior hyperparameters. DP-HyPO permits the flexible use of non-DP adaptive hyperparameter optimization methods, such as Gaussian process, for enhanced efficiency, while avoiding the substantial privacy costs due to composition.
contrast the non- our adaptive framework. DP-HyPO, effectively bridges the gap between private and non-private hyperparameter optimization. Importantly, our framework not only encompasses the aforementioned non-adaptive methods as special cases, but also seamlessly integrates virtually all conceivable adaptive methods into the framework.
adaptive methods presented in [32 24

---

We provide sharp DP guarantees for the adaptive private hyperparameter optimization. Specifically, when the training procedure executed multiple times, with each iteration being DP on its own, outputting the best repetition is DP ensured by the composition property. However, applying composition results in excessively loose privacy guarantees. Prior work in [24] 32 presents bounds that are either independent of the number of repetitions or depend logarithmically on it. Nevertheless, these results require that the hyperparameter selection for each iteration follows a uniform sampling distribution. In contrast, DP-HyPO allows arbitrary adaptive sampling distributions based on previous runs, Utilizing the Rényi DP framework, we offer strict generalization of those uniform results by providing accurate characterization of the Rényi divergence between the adaptive sampling distributions of neighboring datasets, without any stability assumptions.
Empirically, we observe that the Gaussian process-basee based DP-HyPO algorithm outper- forms its uniform counterpart across several practical scenarios. Generally, practitioners can integrate any non-private adaptive HPO methods into the DP-HyPO framework, opening up a vast range of adaptive private HPO algorithm possibilities. Furthermore, DP-HyPO grants practitioners the flexibility to determine the privacy budget allocation for adaptivity, empowering them to balance between the adaptivity and privacy loss when confronting various hyperparameter optimization challenges.
2 Preliminaries
2.1 Differential Privacy and Hyperparameter Optimization
Differential Privacy is mathematically rigorous framework for quantifying privacy leakage. A DP algorithm promises that an adversary with perfect information about the entire private dataset in use except for single individual would find it hard to distinguish between its presence or absence based on the output of the algorithm [12]. Formally, for > 0, and 0 I 8 < 1, we consider a (randomized)
algorithm M z + that takes as input a dataset.
Definition 2.1 (Differential privacy). randomized algorithm M is (e. 8)-DP for any neighboring dataset D, D' E -" differing by arbitrary sample, and for any event E, we have
P(M(D) E F < (P E F +
Here, E and 6 are privacy parameters that characterize the privacy guarantee of algorithm M. One of the fundamental properties of DP is composition. When multiple DP algorithms are sequentially composed, the resulting algorithm remains private. The total privacy cost of the composition scales approximately with the square root of the number of compositions [19
We now formalize the problem of hyperparameter optimization with DP guarantees, which builds upon the finite-candidate framework presented in 24 32) Specifically, we consider set of base DP algorithms M, t + )/ where E A represents a set of hyperparameters of interest, Z" the domain of datasets, and Y' denotes the range of the algorithms. This set A may be any infinite set, e.g.. the cross product of the learning rate 17 and clipping norm in DP-SGD. We require that the set A is measure space with associated measure μu. Common choices for include the counting measure or Lebesgue measure. We make a mild assumption that (<A) < 0o.
Based on the previous research [32), we make two simplifying assumptions. First, we assume that there is total ordering on the range V, which allows us compare two selected models based on their "performance measure", denoted by g. Second, we assume that, for hyperparameter optimization purposes, we output the trained model, the hyperparameter, and the performance measure. Specifically, for any input dataset D and hyperparameter X, the return value of M, is (I, q) ~ Mx(D), where represents the combination of the model parameters and the hyperparameter X, and q is the (noisy) performance measure of the model.
2.2 Related Work
In this section, we focus on related work concerning private HPO, while deferring the discussion on non-private HPO to Appendix F
3

---

Historically. research in DP machine learning has neglected the privacy cost associated with HPO
[
39 42..
It is only recently that researchers have begun consider the honest HPO setting 22 in
which the cost is taken into account.
A direct approach to addressing this issue involves composition- -based analysis. If each training run of a hyperparameter satisfies DP, the entire HPO procedure also complies with DP through composition across all attempted hyperparameter values. However, the challenge with this method is that the privacy guarantee derived from accounting can be excessively loose, scaling polynomially with the number of runs.
Chaudhuri et al. 7 were the first to enhance the DP bounds for HPO by introducing additional stability assumptions on the learning algorithms. (24] made significant progress in enhancing DP bounds for HPO without relying on any stability properties of the learning algorithms. They proposed simple procedure where hyperparameter each training run. This selection process was repeated a random number of times according to a geometric distribution, and the best model obtained from these runs was outputted. They showed that this procedure satisfied (3e, 0)-DP as long as each training run of a hyperparameter was (e, O)-DP. Building upon this, 322 extended the procedure
randomly selected from uniform distribution for
accommodate negative binomial or Poisson distributions for the repeated uniform selection. They also offered more precise Rényi DP guarantees for this extended procedure. Furthermore, selection, considering (s, 6)-DP guarantees.
[ explored generalization of the procedure for top-k
In related context, 28 explored setting that appeared superficially similar to ours, their title mentioned "adaptivity." However, their primary focus was on improving adaptive optimizers such as DP-Adam, which aimed to reduce the necessity of hyperparameter tuning, rather than the adaptive HPO discussed in this paper. Notably, in terms of privacy accounting, their approach only involved composing the privacy cost of each run without proposing any new method.
Another relevant area of research is DP selection, which encompasses well-known methods such as the exponential mechanism [25] and the sparse vector technique [13], along with subsequent studies. However, this line of research always assumes the existence of a low-sensitivity score function for each candidate, which is unrealistic assumption for hyperparameter optimization.
3 DP-HyPO: General Framework for Private Hyperparameter Optimization
The obvious approach to the problem of differentially private hyperparameter optimization would be to run each base algorithm and simply return the best one. However, running such an algorithm on large hyperparameter space is not feasible due to the privacy cost growing lincarly in the worst case.
While 24 32 have successfully reduced the privacy cost for hyperparameter optimization from linear to constant, there are still two major drawbacks. First, none of the previous methods considers the case when the potential number of hyperparameter candidates is infinite, which is common in most hyperparameter optimization scenarios. In fact, we typically start with range of hyperparameters that we are interested in, rather than a discrete set of candidates. Furthermore, prior methods are limited to the uniform sampling scheme over the hyperparameter domain A. In practice, this setting is unrealistic since we want to "adapt" the selection based on previous results. For instance, one could use Gaussian process to adaptively choose the next hyperparameter for evaluation, based on all adaptive hyperparameter optimization method has been proposed
the previous outputs. However, or analyzed under the DP constraint. In this paper, we bridge this gap by introducing the first DP adaptive hyperparameter optimization framework.
3.1 DP-HyPO Framework
To achieve adaptive hyperparameter optimization with differential privacy, we propose the DP-HyPO framework. Our approach keeps an adaptive sampling distribution π at each iteration that reflects accumulated information.
Let Q(D, It) be the procedure that randomly draws a hyperparameter À from the distribution T D(A).. and then returns the output from My(D). We allow the sampling distribution to depend on both the dataset and previous outputs, and we denote (5)) the sampling distribution at the j-th
Here, D(A) represents the space of probability densities on A.

---

iteration on dataset D. Similarly, the sampling distribution at the j-th iteration on the neighborhood dataset D' is denoted as π (())
We now present the DP-HyPO framework, denoted A(D, π (1)), T,C,c) c) in Framework | The algorithm takes a prior distribution T(") E D(A) input, which reflects arbitrary prior knowledge about the hyperparameter space. Another input is the distribution of the total repetitions training runs. Importantly,
require it to be random variable rather than fixed number to preserve privacy. The last two inputs are C/ and c, which are upper and lower bounds of the density of any posterior sampling distributions. A finite C' and positive required to bound the privacy cost of the entire framework.
Framework 1 DP-HyPO A(D, (0) c.
Initialize π T()), prior distribution over A. Initialize the result set A = {
Draw T' ~
for j = to T do
(x,9) ~ Q()
A = Au (z.g))
Update r(++) based on A according to any adaptive algorithm such that for all A E A,
π (A)
SC
x (1)
end for
Output (z, q) from A with the highest q
Note that intentionally leave the update rule for x(+1) unspecified in Framework to reflect the fact that any adaptive update rule that leverages information from previous runs can be used. However, for non-private adaptive HPO update rule, the requirement of bounded adaptive density
(2) S C' may be easily violated. In Section 3.2, We provide simple projection technique (A)
to privatize any non-privee non-private update rules. In Section 4 provide an instantiation of DP-HyPO using
Gaussian process.
We now state our main privacy results for this framework in terms of Rényi Differential Privacy (RDP) 27 RDP is a privacy measure that is more general than the commonly used (c, dD and provides tighter privacy bounds for composition. We defer its exact definition to Definition A.2 in the appendix.
We note that different distributions of the number of selections (iterations), T, result in very different privacy guarantees. Here, we showcase the key idea for deriving the privacy guarantee of DP-HyPO framework by considering special case when T follows a truncated negative binomial distributior" NegBin(0, 7) (the same assumption as in (32). In fact, as we show the proof of Theorem in Appendix A the privacy bounds only depend on T directly through its probability generating function, and therefore one can adapt the proof to obtain the corresponding privacy guarantees for other probability families, for example, the Possion distribution considered in [32). From here and on, unless otherwise specified, we will stick with T = NegBin(O,1) for simplicity. We also assume for simplicity that the prior distribution π (0) is a uniform distribution over A. We provide more detailed discussion of handling informed prior other than uniform distribution in Appendix D
Theorem 1. Suppose that T follows truncated negative Binomial distribution T ~ NegBin(O,,) 7)-
Let 0 E (-1, sc). 7 E (0, 1), and 0 < e S. C. Suppose for all Mx 2" + over X E A, the base algorithms satisfy E)DD and (å, E)DP for some E, 2 0, a E (1, 20), and â E [1, 20). Then satisfies (a,e') RDDD where
the DP-HyyP algorithm A(D, (U), NegBBin(0,7),C
= (1 (1 (1- Et aa=1 + 1 +00 log
C (1 + 0) log(1/>) à
log [[]]
'Truncated negative binomial distribution is direct generalization of the geometric distribution. See Appendix B for its definition.
5

---

To prove Theorem I one of our main technical contributions is Lemma A.4 which quantifies the Rényi divergence of the sampling distribution at each iteration between the neighboring datasets. We then leverage this crucial result and the probability generating function of 'I to bound the Rényi divergence in the output of We defer the detailed proof to Appendix
Next, we present the case with pure DP guarantees. Recall the fact that (e, D is equivalent to (0o,e) RRDDP [27]. When both a and & tend towards infinity, we easily obtain the following theorem in terms of (s, O)-D..
Theorem 2. Suppose that T follows truncated negative Binomial distribution T ~ NegBin(O, 7) Let E (=1,00) and y E (0, 1). afl the base algorithms MM, satisfies (e. 0)-DP, then the DP-HyPO algorithm A(D, N (0) NegBin(O, (), C, c) satisfies ((2 + (E + log () 0) -DP.
Theorem D and Theorem provide practitioners the freedom to trade off between allocating more DP budget to enhance the base algorithm or to improve adaptivity. In particular, a higher value of S signifies greater adaptivity, while larger E improves the performance of base algorithms.
3.1.1 Uniform Optimization Method as Special Case
We present the uniform hyperparameter optimization method 32 23 in Algorithm 2 which is special case of our general DP-HyPO Framework with = c = 1. Essentially, this algorithm never updates the sampling distribution æ.
Algorithm 2 Uniform Hyperparameter Optimization U(D,0,7.4)
Let Unif( .... |A])) }), and A O
Draw ~ NegBin(O,7)
for j = to 7 do
(I. ~ QD.
==Au ((x
end for Output (2r, g) from A with the highest q
Our results in Theorem I and Theorem gennrrllleee the main technical results of 32 24 Specifically, when C c and A is finite discrete set, Theorem precisely recovers Theorem 2 in 32.. Furthermore, when we set = 1, the truncated negative binomial distribution reduces to the geometric distribution, and our Theorem recovers Theorem 3.2 in 24
3.2 Practical Recipe to Privatize HPO Algorithms
In the DP-HyPO framework, we begin with a prior and adaptively update it based on the accumulated information. However, for privacy purposes, we require the density x() to bounded by some constants and C. which due the potential privacy leakage when updating π(1) based on the history. is crucial note that this distribution z() can be significantly different from the distribution a/6) if we given different input dataset D'. Therefore, require the probability mass/density function to satisfy μ(A S (A) < C for all X E A to control the privacy loss due to adaptivity.
M[Aj
This requirement is not automatically satisfied and typically necessitates modifications to current non-private HPO methods. To address this challenge, we propose a general recipe to modify any non-private method. The idea is quite straightforward: throughout the algorithm, non-private version of the distribution density (i)), When sampling from the space A, we perform projection from - to the space consisting of bounded densities. Specifically, we define the space of essentially bounded density functions by Sc.- {ʃ E A ess sup ʃ < C
maintain
μ[Aj ess inf >
m(N) JnEN f(a)da = 1}. For such a space to be non-empty, we require that c < S C, where is the measure A. This condition is well-defined assume ((A)

---

To privatize x(0 at the j-th iteration, we project it into the space Sc,., by solving the following convex functional programming problem:
min ||5 - x 1
(3.1)
s.t. Sc.e
Note that this is convex program since Sc.. convex and closed. We denote the output from this optimization problem by ( Theoretically, problem (3.1) allows the hyperparameter space A to be general measurable space with arbitrary topological structure. However, empirically, practitioners need to discretize A to some extent to make the convex optimization computationally feasible. Compared the previous work, our formulation provides the most general characterization of the problem and allows pratitioners to adaptively and iteratively choose proper discretization as needed. Framework tolerrats much finer level of discretization than the previous method, as the performance of latter degrades fast when the number of candidates increases. We also provide examples using CVX to solve this problem in Section 4.2 In Appendix C we discuss about its practical implementation, and the connection information projection.
4 Application: DP-HyPO with Gaussian Process
In this section, we provide instantiation of DP-HyPO using Gaussian process (GP) 38 GPs popular non-parametric Bayesian models frequently employed for hyperparameter optimization. At the meta-level, GPs are trained generate surrogate models by establishing probability distribution over the performance measure q. While traditional GP implementations are not private, we leverage the approach introduced in Section 3.2 design a private version that adheres to the bounded density contraint.
We provide the algorithmic description in Section 4.1 and the empircal evaluation in Section 4.2
4.1 Algorithm Description
The following Algorithm (AgP) a private version of Gaussian process for hyperparameter tuning. In Algorithm we utilize GP to construct surrogate model that generates probability distributions
Algorithm 3 DP-HHy DP-HyPO with Gaussian process S.T.A....
Initialize (0) Un),(A), and A = {
Draw ~ NegBin(O,,)) for 1orl=00 to T T do
Truncate the density of current (0) to bounded into the range of [c, C] by projecting to Sc.e-
(t) Psc.c (7)
Sample (x, g) ~ ((D,+()), and update A = A AUR (z. 9))
Update mean estimation and variance estimation of the Gaussian process yrx o and get the score 8λ = μA + TT
exp(2-ex) Update true (untruncated) posterior ((++)) with softmax, by (1+1)((2) Jwee " end for Output (x from A with the highest q
for the performance measure q. By estimating the mean and variance, assign "score" to each hyperparameter X, known as the estimated upper confidence bound (UCB). The weight factor controls the balance between exploration and exploitation, where larger weights prioritize exploration by assigning higher scores to hyperparameters with greater uncertainty.
To transform these scores into sampling distribution, we apply the softmax function across all hyperparameters, incorporating the parameter 3 as the inverse temperature. A higher value of signifies increased confidence in the learned scores for each hyperparameter.
7

---

4.2 Empirical Evaluations
We now evaluate the performance of our GP-based DP-HyPO (referred as "GP") in various settings. Since DP-HyPO is the first adaptive private hyperparameter optimization method of its kind, we compare it to the special case of Uniform DP-HyPO (Algorithm 2). referred to as "Uniform", as proposed in [24 32]. In this demonstration, we consider two pragmatic privacy configurations: the white-box setting and the black-box setting, contingent on whether adaptive HPỘ algorithms incur extra privacy cost. In the white-box scenario (Section (.ccioon4.2.11 4.2.). we conduct experiments involving training deep learning models on both the MNIST dataset and CIFAR-10 10 dataset. Conversely, when considering the black-box setting (Section 4.2.3 our attention shifts to a real-world Federated Learning (FL) task from the industry. These scenarios provide meaningful insights into the effectiveness and applicability of our GP-based DP-HyPO approach.
4.2.1 MNIST Simulation
We begin with the white-box scenario, in which the data curator aims to provide overall protection to the published model. In this context, accommodate adaptive HPO algorithms, it becomes necessary to reduce the budget allocated to the base algorithm.
In this section, we consider the MNIST dataset, where we employ DP-SGD to train standard CNN. The base algorithms in this case are different DP-SGD models with varying hyperparameters, and we evaluate each base algorithm based on its accuracy. Our objective is to identify the best hyperparameters that produce the most optimal model within given total privacy budget.
Specifically, we consider two variable hyperparameters: the learning rate and clipping norm ft while keeping the other parameters fixed. We ensure that both the GP algorithm and the Uniform algorithm operate under the same total privacy budget, guaranteeing fair comparison.
Due to constraints computational resources, conduct semi-real simulation using the MNIST dataset. For both base algorithms (with different noise multipliers), we cache the mean accuracy of independently trained models for each discretized hyperparameter and treat that as proxy for the "actual accuracy" of the hyperparameter. Each time we sample the accuracy of a hyperparameter, we add Gaussian noise with standard deviation of 0.1 to the cached mean. We evaluate the performance of the output model based on the "actual accuracy" corresponding to the selected hyperparameter. Further details on the simulation and parameter configuration can be found in Appendix E.
In the left panel of Figure I we demonstrated the comparison of performance of the Uniform and GP methods with total privacy budget e = 15th and 8 = 1e - 5. The accuracy reported is the actual accuracy of the output hyperparameter. From the figure, GP method is slightly worse than Uniform method as GP spends log(C/c) budget less than Uniform method for each base algorithm (the cost of adaptivity). However, exploration, GP consistently outperform Uniform, mostly due to the power of being adaptive. The superiority of GP is further demonstrated in Table aggregating over geometric distribution.
that when T' is very small (T < 8),
that after short period of
4.2.2 CIFAR-10 Simulation
When examining the results from MNIST, a legitimate critique arises: our DP-Hypo exhibits only marginal superiority over its uniform counterpart, which questions the assertion that adaptivity holds significant value. Our conjecture is that the hyperparameter landscape of MNIST is relatively uncomplicated, which limits the potential benefits of adaptive algorithms.
To test the hypothesis, we conduct experiments on the CIFAR-10 dataset, with a setup closely mirroring the previous experiment: employ the same CNN model for training, and optimize the same set of hyperparameters, which are the learning rate vj and clipping norm R. The primary difference lies in how generate the hyperparameter landscape. Given that single on CIFAR-10 is considerably more time-consuming than on MNIST, conducting multiple runs for every hyperparameter combination is unfeasible. To address this challenge, we leverage BoTorch (3]
'The values are seemingly very large. Nonetheless, the reported privacy budget encompasses the overall cost of the entire HPO, which is typically overlooked in the existing literature. Given that HPO roughly incurs three times the privacy cost of the base algorithm, an e as high as 15 could be reported as only 5 in many other works.
8

---

0.90
0.6
undtm
026
uKfbm
Accuaay
022
Loos
10"
20
30
25
40
Figure 1: Left: The accuracy of the output hyperparameter in MNIST semi-real simulation, with E 15, 8 = 0.00001. Middle: The accuracy of the output hyperparameter in CIFAR-I0, with 12, 0.00001. Right: The loss of the output hyperparameter FL. Error bars stands for 95% confidence. Curves for GP are calculated by averaging 400 independent runs, and curves for Uniform calculated by averaging 10000 independent runs. For a clearer demonstration, we compare the performance for each fixed value of T, and recognize that the actual performance is weighted average across different values T.
an open-sourced library for HPO, to generate the landscape. Since we operate in the white-bos setting, where the base algorithms have distinct privacy budgets for the uniform and adaptive scenarios, we execute 50 runs and generate the landscape for each case, including the mean (fxx) and standard error (a of accuracy for each hyperparameter combination X. When the algorithm (GP Uniform) visits a specific X, our oracle returns a noisy score ((A) drawn from a normal distribution of (ux, xx). A more detailed description of landscapes and parameter configuration can be found in Appendix E.2
In the middle of Figure L we showcase performance comparison between the Uniform and GP methods with a total privacy budget of = 12 and 8 = 1e 5. Clearly, GP consistently outperforms the Uniform method, with the largest performance gap occurring when the number of runs is around 10.
4.2.3 Federated Learning
In this section, algorithm remains fixed, while we allow extra privacy budget for HPO. That being said, the adaptivity can be achieved without compromising the utility of the base algorithm.
to the black-box setting, where the privacy budget allocated to the base
We explore another real-world scenario: Federated Learning (FL) task conducted on proprietary dataset [l] from industry. Our aim is to determine the optimal learning rates for the central server (using AdaGrad) and the individual users (using SGD). To simulate this scenario, we once again rely
on the landscape generated by BoTorch [3] as shown in Figure 3 in Appendix E.3
Under the assumption that base algorithms are black-box models with fixed privacy costs, we proceed with HPO while varying the degree of adaptivity. The experiment results are visualized in the right panel of Figure D and Table 2 presents the aggregated performance data.
We consistently observe that GP outperforms Uniform in the black- box setting. Furthermore, our findings suggest that allocating larger privacy budget the GP method facilitates the acquisition of adaptive information, resulting in improved performance in HPO. This highlights the flexibility of GP in utilizing privacy resources effectively.
Geometric(7)
0.001
0.002
0.003
0.005
0.01
0.02
0.025
0.03
GP
0.946
0.948
0.948
0.947
0.943
0.937
0.934
0.932
Uniform
0.943
0.945
0.945
0.944
0.940
0.935
0.932
0.929
Table I: Accuracy of MNIST using Geometric Distribution with various different values of ry for Uniform and GP methods. Each number is the mean of 200 runs.
WWe have to respect confidentiality constraints that limit our ability to provide extensive details about this dataset.

---

Geometric(7)
0.001
0.002
0.003
0.005
0.01
0.02
0.025
0.03
GP (C = 1.25)
0.00853
0.0088
0.00906
0.00958
0.0108
0.0129
0.0138
0.0146
GP (C = 1.33)
0.00821
0.00847
0.00872
0.00921
0.0104
0.0123
0.0132
0.0140
GP =
0.00822
0.00848
0.00872
0.00920
0.0103
0.0123
0.0131
0.0130
Uniform
0.0104
0.0106
0.0109
0.0113
0.0123
0.0141
0.0149
0.0156
Table 2: Loss of FL using Geometric Distribution with various different values of 7 for Uniform and GP methods with different choice of C' and 1/C. Each number is the mean of 200 runs.
Conclusion
In conclusion, this paper presents novel framework, DP-HyPO. As the first adaptive HPO framework with sharp DP guarantees, DP-HyPO effectively bridges the gap between private and non non- non-private HPO. Our work encompasses the random search method by [24 32 as a special case, while also granting practitioners the ability to adaptively learn better sampling distributions based on previous runs. Importantly, DP-HyPO enables the conversion of any non-private adaptive HPO algorithm into private one. Our framework proves to be powerful tool for professionals seeking optimal model performance and robust DP guarantees.
The DP-HyPO framework presents two interesting future directions. One prospect involves an alternative HPO specification which practically more favorable. Considering the extensive literature on HPO, there is a significant potential to improve the empirical performance by leveraging more advanced HPO methods. Secondly, there interest in establishing theoretical utility guarantee for DP-HyPO. By leveraging similar proof methodologies to those in Theorem 3.3 in [24), it is feasible to provide basic utility guarantees for the general DP-HyPO, or for some specific configurations within DP-HyPO.
6 Acknowledgements
The authors would like to thank Max Balandat for his thoughtful comments and insights that helped us improve the paper.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC conference computer and communications security, pages 408-315 2016.
[2] Martin S Andersen, Joachim Dahl, Lieven Vandenberghe, et Cvxopt: A python package for convex optimization. Available at cvxopt. org, 54, 2013.
[3] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 33:21524 22-1522--11888, 2020.
[4] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464 473. IEEE, 2014.
[5] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. Advances in neural information processing systems, 24, 2011.
[6] Nicholas Carlini, Chang Liu, Úlfar Frlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In USENIX Security Symposium, volume 267, 2019.
[7] Kamalika Chaudhuri and Staal A Vinterbo. A stability-based validation procedure for differ- entially private machine learning. Advances in Neural Information Processing Systems, 26, 2013.
10

---

[8] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized private selection and testing with high confidence. arXiv preprint arXiv:2211.12063. 2022.
[9] Imre Csiszár and Frantisek Matus. Information projections revisited. JEEE Transactions on Information Theory, 49(6): 1474-1490, 2003.
[10] Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint 0rXiv:2204.136500 2022.
[11] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
[12] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[13] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-firs annual ACM symposium on Theory of computing, pages 381-390, 2009.
[14] Matthias Feurer and Frank Hutter. Hyperparameter optimization. Automated machine learning: Methods, systems, challenges, pages 3-33, 2019.
[15] Yonatan Geifman and Ran Yaniv. Deep active learning with neural architecture search. Advances in Neural Information Processing Systems, 32, 2019.
[16] Xin He, Kaiyong Zhao, and Xiaowen Chu. Automl: survey of the state-of-the-art, Knowledge- Based Systems, 212:10662: 2021.
[17] Andrew Hundt, Varun Jain, and Gregory D Hager. sharpdarts: Faster and more accurate differentiable architecture search. arXiv preprint arXiv:1903.0990 09900, 2019.
[18) Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Sequential model optimization for general algorithm configuration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pages 507-523. Springer, 2011.
[19] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1320 1385. PMLR, 2015.
[20] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. Advances in neural information processing systems, 31, 2018.
[21] Rajiv Khanna, Joydeep Ghosh, Rusell Poldrack, and Oluwasanmi Koyejo. Information projec- tion and approximate inference for structured sparse variables. In Artificial Intelligence and Statistics, pages 1358-1366 PMLR, 2017.
[22] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, pages 367-377. PMLR, 2020.
[23] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyper- band: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1))6765-6866 2017.
[24] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51 Annual ACM SIGACT Symposium Theory of Computing, pages 298-309, 2019.
[25] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103, IEEE, 2007.

---

[26] Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Towards automatically-tunel neural networks. In Workshop on automatic machine learning. pages 58-65. PMLR, 2016.
[27] Iyya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263 225. IEEE, 2017.
[28] Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. The role of adaptive optimizers for honest private hyperparameter selection. In Proceedings of the aaai conference on artificial intelligence, volume 36, pages 7806-7813, 2022.
[29] Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pages 739-753. IEEE, 2019.
[30] Renato Negrinho, Matthew Gormley, Geoffrey J Gordon, Darshan Patil, Nghia Le, and Daniel Ferreira. Towards modular and programmable architecture search, Advances in neural informa- tion processing systems, 32, 2019.
[31] Ashwinee Panda, Xinyu Tang, Vikash Sehwag, Saced Mahloujifar, and Prateek Mittal. Dp-raft: differentially private recipe for accelerated fine-tuning. arXiv preprint arXiv:2212.06 04.4666 2022.
[32] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2021.
[33] Carl Edward Rasmussen, Gaussian processes in machine learning. In Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2-14, 2003, Tübingen, Germuny, August 4-16, 2003, Revised Lectures, pages 63-71. Springer, 2004.
[34] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-175 2015.
[35] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing, pages 245-248. IEEE, 2013.
[36] Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptog- raphy: Dedicated to Oded Goldreich, pages 347-450, 2017.
[37] Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, and Weijie J Su. Analytical composition of differential privacy via the edgeworth accountant. arXiv preprint Stti:220060423366 2022.
[38] Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes machine learning. volume 2. MIT press Cambridge, MA, 2006.
[39] Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Yan Liu. Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning, pages 12208-12218, PMLR, 2021.
[40] Tong Yu and Hong Zhu. Hyper-parameter optimization: A review of algorithms and applications. arXiv preprint arXiv:2003. 056899 2020.
[41] Arber Zela, Aaron Klein, Stefan Falkner, and Frank Hutter. Towards automated deep learning: Efficient joint neural architecture and hyperparameter search. arXiv preprint 1rXiv:/807..00 06606, 2018.
[42] Huanyu Zhang, Ilya Mironov, and Meisam Hejazinia. Wide network learning with differential privacy. arXiv preprint arXiv:2103.01294 2021.
12

---

A Proofs of the technical results
A.1 Proof of Main Results
First, we define Rényi divergence as follows.
Definition A.1 (Rényi Divergences). Let P and Q be probability distributions on common space Q. Assume that P is absolutely continuous with respect to Q i.c., for all measurable E' C 92 Q(E) 0, then P(E) = O. Let P(x) and Q(x)) denote the densities of P and Q respectively. The KL divergence from to Q defined as
P(X) ) Q(X)
P((x)
Qi()) == X-P
log
=
P(x) log
Q(x)
dæ.
The max divergence from P to Q defined as
P(E) Q(F)
P(E) > of
(PI = sup log
For a E 00), the Rényi divergence from P to Q of order a is defined as
Da(l)IQ) = 1-1
log
E xtr
(Q(x))
1
[( (((x)) '7)
log
E X+QQ
0
1
(% ((x) dx
log
0F
We now present the definition of Rényi DP (RDP) in 27
Definition A.2 (Rényi Differential Privacy). A randomized algorithm M : x + y is (a, Rényi differentially private if, for all neighbouring pairs of inputs D, D' E x", D. (M(x) (x' S 8.
We define some additional notations for the sake of the proofs. In algorithm I for any 1 S < <, and neighboring dataset D and D', we define the following notations for any (z, q) E y, the totally ordered range set.
Py(y) Py-Q(D,=0)) (g v) and
Pj(v) P y Q(D' 21) (0 = (ū=
P5(s y) Fy-Q(D,=0)) (ū v) and
Pj(s y) = P PP x -0)(i 51)
Py(c y) = -P un) un) < y) and
Pj(< v) = PP x0) - (0 <)).
By these definitions, we have (5 y) (5 v) + Py(v), and P5 y) Pj(<< v) + P)()) And additionally, we have
= Pv( JAEA = sup AEA = (
PDM (1)
P)(() JAEA ((M) = ())
C P(MA = :) sup AEA PDM, = v)
(A.1)
Here, the first inequality follows from the simple property of integration, and the second inequality follows from the fact that of ( has bounded density between e and C. Similarly, we have
P v) < C' sup (D) < v) PJ 3) c
(A.2)
NEA (D', S v)
and
Pz(C v)
C. PDM < v)
<
sup
(A.3)
P v)
c
NEA PD')(D") < <)
13

---

Note that D and D' are neighboring datasets, and MM satisfies some DP guarantees. So the ratio (D)EE for any event E can be bounded.
P(MA(D")ER)
For simplicity, we define the inner product of distribution π with the vector MDD (P(M)(D) y) A A) as
π TM = / P(M)(D) (A)dA
JAEA
(A.4)
Now, we define additional notations to bound the probabilities. Recall Sc,, is given by {ʃ E A ess sup f S C, ess inf f 2 c, JaeA f(a))da 1.). straightforward to see this a compact set as it is the intersection of three compact sets. We define
pt
sup EESc AEA
P(M)(D) 1) = +D)),,
M(D),
(A.5)
where at is the distribution that achieves the supreme in the compact Sc.c- Similarly, define p'- (v) for D' as given by
P' (v) = inf / P(Mx(D') y) - (A)d) = x'= M. xESC, AEA
(A.6)
Similarly, we can define (y+ and P (y) accordingly. From the definition, we know that
P (v) - Pv) S Pt() and P' (z) s - P*+ (y))
(A.7)
We also have
p+ (1) x². .M(D)
P(MA(D) = 9) C X P(M)(D) =
P (y) n'_ -M(D) I sup
(A.8)
It is similar to define
p+( sup 7ESE,e AEA
P(MA(() () and p²) sup
P(MA(D)) S)
TESO, AEA /
( v) = inf TESC.e JAEA PDMA(D) S 5) and P' (5 == inf TESC.e JXEN P(MA(D)) Sv)
p+(< y) = sup TESE, I
PDM <) and p* (< 9) sup rESC, AEA
P(M)(D) <v)
p-(-))= inf TESO,e AEA
PDM,(D) < v) and P (--(4)) == inf
P(M)(D)) <)
TESC AEA
Following the exact same proof, we have
PT 2 v) < (+ v) and P' S ()(s)) S PP*(5))
(A.9)
(- < 9) < Pt (< and
(² ()( S p**(<g)
(A.10)
pt < sup (D') < w)
PD) < y)
p+(< < sup P-((w) x P(Mx(D") <)) C
P(M <g) C
and is also straightforward to verify from the definition that
(A.1I)
p+ = y) + P+)) and
p'+ v) = p*+ + p'+(y)
(A.12)
p+ -- y) + P and P' v) = P-- + P' P1)
(A.13)
Lemma A.3. Suppose ax, b non-negative and cx, d positive for all X. Then have
Exars Exax Extac Σx
sup X.X
bx
Proof of Lemma This lemma is pretty straight forward by comparing the cocfficient for each term in the full expansion. Specifically, we re-write the inequality
cx d2
Eaxo Σ
E
as Σ
Bac sup
(A.14)
X.X
14

---

For each term axb2, its coefficient on the left hand side of (A.14) is Cx2 but its coefficient on the right hand side of (A.14) is ci / ea we know the inequality (A.14) holds.
Since we always have cj ssuxi 5
and وхb² 2 0,
Next, in order to present our results in terms of RDP guarantees, we prove the following lemma. Lemma A.4. The Rényi divergence between P+ and P be bounded as follows:
C log Da(Pt P ) S a c
sup Da (M)(D)))(((')) xyλ
Proof of Lemma A.4
We write that
E a (A) = 8))* VEy (Σx X' (A)P(MA(D" y)) (A.15)
cla-1)Do(P=11P")
Σ Pt())) P' (v) NEY
Σ
Here, π and n' are defined in (A.5) and (A.6). so they are essentially o and TV as they depend on the value of y. Therefore, need to "remove" this dependence on y to leverage the RDP guarantees for each base algorithm M2- We accomplish this task by bridging via æ, the uniform density on A (that is (A) xXx' for any X, X A). Specifically, we define as (A)P((M)) v).
(A) 6Λ (A) v). ca x(A)
x (A) m(A]
and cj
We see that
T (A)/T(()) sup X.X'
FV (A)) (X)
sup A,X'
sup A
By (X)/=(X)
S $C/c
(A.16)
since ι is the uniform, and n. and n. belongs to Sc,.- We now apply Lemma notations for each y to (A.15), and we have
A.3 with the above
+ (A)F(M) "))*
Σ VEY
(A))(M((D)) = v))a
Ex (N)((M)) = v) T (xx (A) = v)
(A()) x(A)
Σ TATAMM(MDD = 7(A)
NEY
Exax EATANP(M(D) v) xt
7(A)
Exbb- .G)aaaaa
VEY
a-1 Exax)~11 (AF(A)((M( = 9)
='(N)
=(A)
sup
(Exbra-t
X
yEy
a-1 Exas)a-1(E 10,011Exxx0
CX CA
sup
(Ex ba)a-1
nEY
Caa (Exax) ax) supx ex
sup NEY A.
EEx ba
C
E -- (Ex ax) (2)
bsbs)at
E (WD =)))
Σ
Ex (A) 8))=
NEY
15

---

The first inequality is due to Lemma A.3 the second inequality is because aλ are non non-negative, and the last inequality is because of AA.16) and the fact that both π TA() and π (A) are defined in Sc,e- and thus their ratio upper bounded by c
for any X.
Now we only need to prove that for any fixed distribution that doesn't depend on value y, we have
Σ Cx (())))((M(())== x))²
supe /
sup λελ
(A.17)
yEY (AT(MM)(M(()) v))
With this result, immediately know the result holds for uniform distribution иT as special case. To prove this result, we first observe that the function f(u, v) = ul-- is a convex function. This is because the Hessian of is
a1(a - 1)u0 1220-202-0 -a(aa - 1)2a-t100 -a(a - 11)00-1- afa 1 1
which casy to see to be positive semi-definite. And now, consider any distribution म, denote (A) (D) y) and v(A) = P(M)((D) = v) by Jensen's inequality, we have
f( (A) E I((A)((A)) = E xx())(((A))
By adding the summation over on both side of the above inequality, we have
Σ (xx (XF(A)(MM(D)) = u))
ΣΣ (A) P(MA(D) = y)
VEY (WD(MM(M) = y))
P(MA(D) y)
P(Mx(D) = y)
ΣΣ Σ
T (A)
P(M)(D") = y)a-1
DEY
P(Mx(D)= y)
$ sup
Σ yEV
F(MA(D") = y)
The first equality is due to Fubini's theorem. And the second inequality is straight forward as one observe (A) only depends on X. This concludes the proof as we know that
C
P(Mx(D) y) P(Ma(D)) y)a
sup X
C'
sup (a (O-I)DD(MM(DD)IMM(1))
or equivalently,
Da Da(P+I(P')
< a
log
C
sup D. (D)))) xEA
We now present our crucial technical lemma for adaptive hyperparameter tuing with any distribution on the number of repetitions T. This a generalization from (32).
Lemma A.S. Fix a > 1. Let T be random variable supported on N Let f: [0. + R be the probability generating function of K. that is, f(x Ex= P(T = k]æ²
Let M2 and M', be the base algorithm for X A on y on D and D' respectively. Define A A(D, (0) ,T, C), and Ag A(D', (0) T, C,C.). Then
C a-1 log a-1 log - (())
Da (A1llA2) S sup D. (M)
c
where applying the same postprocessing to the bounding probabilities p+ and p gives probabilities
q and o' respectively. This means that, there exist a function set g y + 10, 1] such that = E lo(X), and q²
E [g (X)).
x-p+
p
16

---

Proof of Lemma A.3
We consider the event that A1 outputs By definition, we have
k P(T = k)
k
A1(1) =
Σ
II[
P3(s
v) - II P((
1=1
1=1
8
Σ
P(T = k)
II ()(0))
II j=1+1
P)(
J=1
$
Σ
P(T = R)]
Pt (V)
II p*(
1=1
j=++1
Σ P(T = k))
P+()) P (<())) pt y)
k=1
==1
Σ P(T = k)) (s y)* - (= y)*1
k=1
= f((P v)) - f(pt((((->>------ (< 8)
pv)
E Xi
[f)()]
The second equality by partitioning on the events of the first time of getting y, we use to index such a time. The third inequality is using (A.7). (A.9). and (0. The third to last equality is by (2.12) and algebra. The second last equality is by definition of the probability generating function f. The last equality follows from definition of integral.
Similarly, we have
A2(1)
Σ (n)
U-Uunfomm( (c)), (sw))) [f()))
The rest part of the proof standard and follows similarly as in 32 Specifically, we have
Σ A1 A2(1)²
yEY
< Σ (t (P'
X-IPt(co) [(()]] X'-IP' (<-) (<u). (5' [ (X'))'-a
E
yEY'
< Σ p+()) p' (v) 1-a
E X+ xt-ppt<< (<y), (SV))
[(()) of ff (x))-a]
NEY
x' p' (<D), pr (5w)
C &
< sup (a (I. (MM))
max VEy
E (<p) x' ('-(p'-<s))) [Svi]
The last inequality follows from Lemma A.4 The second inequality follows from the fact that, for any a E R. the function h. (0, oc)2 + (0, oo) given by h(u, u² pl-- is convex. Therefore, EV]]= = M(E[(U, V))) & (E((U,)) V)] = E [U V2la] all positive random variables (U, V). Note that X and X' are required to be uniform separately, but their joint distribution can be arbitrary. As in [32]. we will couple them so that X-pi(<v)
x'pp" (<w) In particular, this (v)
P (v)
implies that, for each E V, there exists some / E [0, 1] such that
(()) o ((x)' <
(P' (P' y) +t. p' (1)) 1-a
X- (e)) X' X'=(p' "<y)."<v)) (Sv)
17

---

Therefore, we have
C
Dr (2) sup Dr (MAlIM)) + a-1 log
log a
f'(P+(<)) (t) (P- +t. ( +t
yEY [tE[0.]]
To prove the result, we simply fix yv E y and t. E [0, achieving the maximum above and define
1
i < y+ y =
0(v) =
t.
0 y > y-
The result directly follows by setting 9
E [o(X) and q'
E X'e
(X*).
X+
Now we can prove Theorem T. given the previous technical lemma. The proof share similarity to
the proof of Theorem 2 in [32 with the key difference from the different form Lemma A.5 We demonstrate this proof as follows for completeness.
Proof of Theorem binomial distribution
We first specify the probability generating function of the truncated negative
(1-(1-7)x)- 7- 6-1 log(1-1
if 0 i
f(x)
E
[x07]
NoN
log(?)
Therefore,
f(x) = (1 (1 7)2) 8-1 9-(1-))
if #0
-ーーー1
i
log[1/7]
(1 (1 2) 8-1 _00 ETT).
By Lemma
A.5 for appropriate values q, of [0, 1] and for all > 1 and all & > 1, we have
18

---

Da (2)llA2)
Ssup (M^IlMK)
+
a
log
C
log (f())) 8 (0') (7)
a
c
a
8et
log
C
+
1
log (70t1, .[(T] (1 (1 - 7))))) ()0))))(++)))) a
(1- -11-2)
a-1 1
1
C
=E+ +
log
1
log (,041. E[T]
(1 + (1- 7) -1)) -))= (( (1 - 7) (1 (1- -6 (1-))(11 )))*
+ a a-1
(Here, we let áv (a- 1)(1 + 8) and (1 â)v + u = -a(6 + 1))
1et a log C + 1 log gt1 B[T] (7 + (1 7) cl 1)Da | (P)))))()))))) (x + (1 7) -1))")
1
(Here,1 - q and - o' are postprocessings of some p+ and P' respectively and ( is convex
Set a log + a-1 1
1
log (,0t1. -E(T] (7 + (1 - 7) (a sup sups Da (Mll)M)))+ log 8)² (7 + (1-)
(By Lemma A.4
log C
1
log (,0t1 B[T] (7 + (1 - -7) -e(ā- sunp Du (MAllA log 8)² (77 + (1 (1 -9))*)
S a-
+
a -
a log
1
log (00t1. .[T] (7+ (1 - 7) c(à sup, Do (Mallee +a x .g"))
+ -
1
(Here 7 S 7 + (1 7) - v) and S 0)
a log
+ V
log (7 + (1 - 7)) (o- Da (MAJIMS) t 8) + log (70+1. 1/T7179
+
--1 1
C + a-1 - ()= sup D& (MaIlA()) + & log
v
C
a +
log
c
+ log 1 y. (1 - - (a-1) shns tans Da (AM (MMS +alog $ 8)) + a a-1 log (nut0t1. BTT)
1
+ a a-1 log C
+ (1 + 0) 11 21- sup Da (Ma M M1 + (1 + log C
1 1-0 log (1 11-7. (1 - E 1da-l)s Da (M + log 8) log(B
1 ++ 0
+
ā log (1/7)
(a 1)(1 + 0)
and u = -(1 ( a 1 (a-++1) +1
(Here we have v=
ā
à
+
log
C
+ (1 + (1
21- sup Da (M/l) + (1 + 0) log
1) )
α Q-1 1
c
x
1
1 + e (b-1)s-pp Da (Mx | !
log (E(T))
+
log
à
a a-1
C + (1 (1+ 0) (1- + (1+ (1+0)log
C +
1 1+0 0
log (E[T)
S 8 +
log
log
+
a
ā
which completes the proof.
B Truncated Negative Binomial Distribution
We introduce the definition of truncated negative binomial distribution [32 in this section.
Definition B.I. (Truncated Negative Binomial Distribution 32 Let 7 E (0, 1) and 0 E (-1,
Define distribution NegBin (0, 7) on N+ as follows:
19

---

If 0 o 0 and T' is drawn from NegBin 0, y), then
c+
VKEN FIT k]
c+1
t=U
and E[T] = 8-(1-7) .-(1->") Note that when 0 = 1, it reduces to the geometric distribution with
parameter 7,
If 0 = and T is drawn from NegBin(O, y), then
(1 7)
P(T = k]
k 1og(og(1)) 1/7)
and T
1/7-1 log(1/7)*
Privatization of Sampling Distribution
C.1 General Functional Projection Framework
In section 3.2
define the projection onto convex set Sc,e optimization in terms of &g loss. More generally. y, we can perform the following general projection at the j-th iteration by considering an additional penalty term, with constant
min |lʃ /V--""1aa (KL(T f
(C.1)
s.t. f f
When v = O, we recover the original l2 projection. Moreover, it's worth noting that our formula- tion has implications for the information projection literature ( 21]. Specifically, the penalty term parameter v approaches infinity, the optimization problem evolves into a minimization of KL divergence, recovering the objective function of information projection (in this instance, moment projection). However, the constraint sets in the literature of information projection are generally much simpler than our set Sc.e. making infeasible to directly borrow methods from its field. To the best of our knowledge, our framework is the first to address this specific problem in functional projection and establish connection to information projection in the DP community.
C.2 Practical Implementation of Functional Projection
essentially functional programming since function on A. However, when A represents non-discrete parameter space, such functional minimization is typically difficult solve analytically. Even within the literature of information projection, none of the methods considers our constraint set Sc.c. which can be viewed as the intersections of uncountable single-point constraints on f. To obtain a feasible solution to the optimization problem, we leverage the idea of discretization. Instead of viewing (3.1) as a functional projection problem, we manually discretize and solve (3.T) as minimization problem over discrete set. Note that such approximation unavoidable numerical computations since computers can only manage discrete functions, even when we solve the functional projection analytically. Moreover, we also have the freedom of choosing the discretization grid without incurring extra privacy loss since the privacy cost is independent of the size of parameter space. By converting Sc,e into a set finite constraints, we are able to solve the discrete optimization problem efficiently using CVXOPT (2).
Optimization program 3.1
D DP-HyPO with General Prior Distribution
In the main manuscript, we assume (0) follows a uniform distribution over the parameter space A for simplicity. In practice, informed priors can be used when we want integrate knowledge about the parameter space into sampling distribution, which is common in the Bayesian optimization framework. We now present the general DP-HyPO framework under the informed prior distribution.
To begin with, define the space of essentially bounded density functions with respect to (()
(c = {f E A R* ess sup (0) < C, ess inf f/ (0) 2 c, JAEA
f(a)da = I, < r ())
20

---

When (0))
x(A)' we recover the original definition of Sc.e. Note that here f < x means that f is absolute continuous with respect to the prior distribution x (0)) and this ensures that (c,((=!!)) is non-empty. Note that such condition is automatically satisfied when ((") is the uniform prior over the entire parameter space.
To define the projection of density at the j-th iteration, T0), into the space ()),( we consider following functional programming problem:
min II 1
s.t. J )
which is a direct generalization Equation (.1)). As before, (c.e(T(")) is also convex and closed and the optimization program can be solved efficrently via discretization on A.
E
Experiment Details
E.1 MNIST Simulation
We now provide the detailed description of the experiment in Section 4.2.1 consider two variable hyperparameters: the learning rate and clipping norm R, while keeping all the other hyperparameters fixed. We set the training batch size to be 256, and the total number of epoch to be 10. The value of a is determined based on the allocated budget for each base algorithm. Specifically,
As specified therein,
0.71 for GP and to 2 and to 0.75 in the GP method, so each base algorithm of Uniform has log C/cc more privacy budget than base algorithms in GP method. Algorithm 3 we set 7 to 0.1 and 1. To facilitate the implementation of both methods, we discretize the learning rates and clipping norms as specified in the following setting allow simple implementation of sampling and projection for Uniform and GP methods.
0.64 for Uniform. For demonstration purposes,
set C
Setting E.1. we set a tog-spaced grid discretization on 17 in the range [0.0001, 10) with a multiplica- tive factor of V10, resulting in 16 observations for 11- We also set a linear-spaced grid discretization on R in the range (0.3, 6) with an increment of 0.3, resulting 20 observations for R. This gives total of 320 hyperparameters over the search region.
We specify the network structure we used in the simulation as below. the standard CNN in Tensorflow Privacy and Opacus
class ConvNet (nn Module))
def iseli)
self convi = nn. Conv2d (1, 16, 8, 2, padding=3)
self. conv2 nn. Conv2d (16, 32, 4, 2)
self nn. Linear (32 4 * 4, 32)
self nn. Linear (32, 10)
def forward x):
F. F.relu(self convi (x))
x mmax__poll2dxx, 2, 1)
F.relu(self.r conv2(x))
X = m_ax_pool2ddx, 2, 1)
X x-view(-1, 32 4 4)
X = Freeluseeff. fci fx))
X self.fc26
return
Despite the simple nature of MNIST, the simulation of training CNN with the two methods over each different fixed 7 still take significant computation resources. Due to the constraints on computational resources, we conduct a semi-real simulation using the MNIST dataset. We cache the mean accuracy of 5 independently trained models for each discretized hyperparameter and treat that as proxy for the
21

---

"actual accuracy" of the hyperparameter. Each time we sample the accuracy of hyperparameter, we add Gaussian noise with standard deviation of 0.1 the cached mean. We evaluate the performance of the output model based on the "actual accuracy" corresponding to the selected hyperparameter.
E.2 CIFAR-10 Simulation
We also provide description of the experiment in Section 4.2.2) We the training batch size be 256, and the total number of epoch to be 10. The value of a is determined based on the allocated budget for each base algorithm. Specifically, our GP method, we adopt the same set of hyperparameters as used in our MNIST experiments, which include C
0.65 for GP and
0.6 for Uniform. Regarding
0.75. 0.1, and norms as specified in the following Setting.
1. As usual, we discretize the learning rates and clipping
Setting E.2. we set log- log-spaced grid discretization on 1j in the range [0.0001, 1] with multiplicatiiv factor of 100.1, resulting in 50 observations for 1). We also a linear-spaced grid discretization R in the range [0, 100] with an increment of resulting in 50 observations for R. This gives a total of 2500 hyperparameter combinations the search region.
We follow the same CNN model architecture with our MNIST experiments.
In Figure 2
provide the hyperparameter landscape for 0.65, generated by BoTocch 3
Figure 2: Mean and standard error the accuracy DP-SGD over the two hyperparameters for
= 0.65. The learning rate (log-scale) ranges from 0.00001 (left) to (right) while the clipping norm ranges from (top) to 100 (bottom). The landscape for 0.6 is similar, with a better accuracy.
E.3 Federated Learning Simulation
281
Meon
600
Standard Deviation
600
5022
10
563
500
10-1
680
1001
28
10
1080
10-4
10.
16-1
12-1
300K
AcaCred
Figure 3: Mean and Standard Error of the loss of the FL over the two hyperparameters.
We now provide the detailed description of the experiment in Section considered FL task on proprietary datase Our objective is to determine the optimal learning
specified therein, we
We are unable to report lot of detail about the proprietary dataset due confidentiality.
22

---

rates for the central server (using AdaGrad) and the individual users (using SGD). To simulate this scenario, we utilize the landscape generated by BoTorch [3), as illustrated in Figure and consider as our reference landscape for both mean and standard deviation of the loss for each hyperparameter. When the algorithm (GP or Uniform) visits a specific hyperparameter X, our oracle returns a noisy score (A)) drawn from normal distribution N N(xx, xx). Figure diguraBdssplays
displays a heatmap that presents the mean (μx) and standard error (σx) structure of the loss over these two hyperparameters, providing insights into the landscape's s characteristics.
F Additional Related Work
In this section, we delve into a more detailed review of the pertinent literature.
We begin with non-private Hyperparameter Optimization, a critical topic in the realm of Automated Machine Learning (AutoML) [16]. The fundamental inquiry revolves around the generation of high- performing models within a specific search space. In historical context, two types of optimizations have proven significant in addressing this inquiry: architecture optimization and hyperparameter optimization. Architecture optimization pertains to model-specific parameters such as the number of neural network layers and their interconnectivity. while hyperparameter optimization concerns training-specific parameters, including the learning rate and minibatch size. In our paper, we incorporate both types of optimizations within our HPO framework. Practically speaking, A can encompass various learning rates and network architectures for selection. For HPO, elementary methods include grid search and random search (22 [5]. Progressing beyond non-adaya non-adaptive random approaches, surrogate model-based optimization presents an adaptive method, leveraging information from preceding results to construct a surrogate model of the objective function [26] 20 30
These
methods predominantly employs Bayesian optimization techniques, including Gaussian process [3
Random Forest [8], and tree-structured Parzen estimator [5].
Another important topic in this paper is Differential Privacy (DP). DP offers a mathematically robust framework for measuring privacy leakage. A DP algorithm promises that an adversary with perfect information about the entire private dataset in use except for single individual - would find it hard to distinguish between its presence or absence based on the output of the algorithm [[2].
Historically, DP machine learning research has overlooked the privacy cost associated with HPO [
39
42
The focus has only recently shifted the "honest HPO" setting, where this cost is factored Addressing this issue directly involves employing a composition-
analysis. If each training run of hyperparameter upholds DP, then the overall HPO procedure adheres to DP through composition across all attempted hyperparameter values. A plethora of literature on the composition of DP mechanisms attempts to quantify better DP guarantee of the composition. Vadhan et al. 13 demonstrated that though (s, DDD possesses a simple mathematical form, deriving the precise privacy parameters of a composition #-P hard. Despite this obstacle, numerous advanced techniques are available to calculate a reasonably accurate approximation of the privacy parameters, such as Moments Accountant [. GDP Accountant (T)) and Edgeworth Accountant [37]. The efficacy of these accountants is attributed to the fact that it is casier to reason about the privacy guarantees of compositions within the framework of Rényi differential privacy 27 or f f-differential privacy [I]]. These methods have found widespread application in DP machine learning. For instance, when training deep learning models, one of the most commonly adopted methods to ensure DP via noisy stochastic gradient descent (noisy SGD) 4 35 which uses Moments Accountant to better quantify the privacy guarantee.
in
28
Although using composition for HPO is a simple and straightforward approach, it carries with it a significant challenge. The privacy guarantee derived from composition accounting can be excessively loose, scaling polynomially with the number of runs. Chaudhuri et al. / were the first to enhance the DP bounds for HPO by introducing additional stability assumptions on the learning algorithms. 24] made significant progress in enhancing DP bounds for HPO without relying any stability properties of the learning algorithms. They proposed simple procedure where hyperparameter was randomly selected from a uniform distribution for each training run. This selection process was repeated a random number of times according to a geometric distribution, and the best model obtained from these runs was outputted. They showed that this procedure satisfied (3e, O)-DP as long as each training run of hyperparameter was (c, O)-DP. Building upon this, (32) extended the procedure to accommodate negative binomial or Poisson distributions for the repeated uniform selection. They also
23

---

offered more precise Rényi DP guarantees for this extended procedure. Furthermore, g explored generalization of the procedure for top-k selection, considering (E, 6)-DP guarantees.
In a related context, 28 explored a setting that appeared superficially similar to ours, as their title improving adaptive optimizers such as DP-Adam, which aimed to reduce the necessity of hyperparameter tuning, rather than the adaptive HPO discussed in this paper. Notably, in terms of privacy accounting, their approach only involved composing the privacy cost of each run without proposing any new method.
mentioned "adaptivity." However, their primary focus
Another relevant area of research is DP selection, which encompasses well-known methods such as the exponential mechanism [25] and the sparse vector technique [13], along with subsequent studies. However, this line of research always assumes the existence of now-sensitivity score function for each candidate, which is an unrealistic assumption for hyperparameter optimization.
24


Reviews:
[{"review_id": "DJSF03hHn8", "reviewer": "Reviewer_11th", "summary": "This work proposes a differentially private (DP) adaptive hyperparameter optimization algorithm called DP-HyPO, which encompasses several existing DP non-adaptive hyperparameter optimization algorithms. DP-HyPO is able to deal with hyperparameters that come with infinitely many values and by leveraging the previous output from the base algorithm, DP-HyPO outperforms the non-adaptive algorithms. The paper gives a privacy analysis of the proposed DP-HyPO and showcases two practical applications of private hyperparameter tuning by instantiating the DP-HyPO framework with Gaussian Process (GP).", "questions": "How can one interpret $\\hat{\\pi}^{(0)} = \\pi^{(0)} \\cdot \\mu(\\Lambda)$ in Framework 1, which is a product of two distributions?\n\nWhat is the run time of performing the projection in Eq.(3.1)? Since one needs to find the optimal function in $S_{C, c}$ at every iteration of DP-HyPO, a long computation time might limit the practicality of DP-HyPO.\n\nIn Section 4, is it possible to derive convergence guarantees (i.e., the utility of the private algorithm) for DP-HyPO with Gaussian Process? \n\nIn Section 4.2.1 MINST simulation, how does DP-HyPO perform in the low privacy regime, say, each base algorithm has a privacy loss $\\epsilon = 0.1$ (which is also practical), and the total privacy loss of DP-HyPO needs to be $\\epsilon = 1$?\n\n In Section 4.2.2 applying DP-HyPO to federated learning, what is the privacy loss $\\epsilon$ here?\n", "limitations": "Some limitations of this work were discussed in the conclusion. \nBroader impact was not discussed.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Clear and intriguing presentation. The problem and several design choices are well motivated. \n\nNew theoretical result analyzing the privacy loss of an adaptive private hyperparameter optimization algorithm.\n", "weaknesses": "Experiment results are not appealing enough. They do not suggest a significant advantage of DP-HyPO compared to the existing non-adaptive algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback!\n\n**MNIST is simplistic**: We acknowledge that the current experiment settings like MNIST are indeed overly simplistic, and hypothesize that could be the underlying cause why our experiments have not shown a significant gain. To address this, we conducted new experiments on CIFAR10, and revealed a **substantial disparity** between our proposed approach and the baseline. Please refer to our \"general\" rebuttal for more detail. \n\n**Definition of $\\mu(\\Lambda)$**: Here, $\\mu(\\Lambda)$ is the total measure of the hyperparameter space, which is a real number, and it is a scalar multiplication. We will make this clearer in the writing.\n\n**Run time of projection in Eq (3.1)**: The projection is a convex optimization problem over the space of $\\Lambda$. We treat this as an abstract and separate subproblem in the theoretical part of the paper, as it requires the specification and the discretization of $\\Lambda$. In our experiment part, we use CVX to solve this convex problem and the runtime of any discretization is negligible compared to the base algorithm. \n\n**The utility guarantee of DP-HyPO with Gaussian Process**: We agree this is a very important problem. However, it is also hard to obtain meaningful utility guarantees. In the previous paper by Liu & Talwar (2019), they provided several utility guarantees for different instantiations of the uniform method. The only relevant result to our algorithm is Theorem 3.3 therein, which proves the the (iterated) uniform method can achieve at least as good as one-iteration of uniform selection with high probability. In the other paper by Papernot & Steinke (2021), no utility result is presented. We believe useful utility results of DP-HyPO are even more challenging than results of uniform methods, and the specification to Gaussian Process requires in-depth analysis of the selection as well as the GP itself. We will list it as an important future direction.\n\n**The performance for MNIST when $\\epsilon = 0.1$**: This is actually the high privacy regime. Training deep learning model from scratch with this small privacy budget is super challenging. Empirically, $\\epsilon$ should be at least 2 to have meaningfully performance for deep learning tasks (for example, De et al. (2023) shows a state-of-art accuracy of 60% for CIFAR 10 when $\\epsilon = 1$, as compared to >95% in the non-private case). \n\n**Section 4.2.2**: In this section, we present a synthetic experiment where we use the **same** loss landscape from a practical federated learning task (Figure 2) for both DP-HyPO and uniform method. This reflects the scenario where DP-Hypo has a larger privacy budget than the uniform algorithm. In this case, we experiment on different choices of $C$ to see the benefit of using the extra privacy budget for better adaptivity. The results in Table 2 demonstrate a larger $C$ means a lower loss.\n\n**Reference**:\n\n[1] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 298–309, 2019.\n\n[2] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy.\nIn International Conference on Learning Representations, 2021.\n\n[3] De, Soham, et al. \"Unlocking high-accuracy differentially private image classification through scale.\" arXiv preprint arXiv:2204.13650 (2022)."}, {"review_id": "8jGmxNYTbd", "reviewer": "Reviewer_6uG2", "summary": "In the paper \"DP-HyPO: An Adaptive Private Framework for Hyperparameter Optimization\" the authors propose a framework for differential privacy HPO turning adaptive aka. model-based HPO methods into privacy preserving HPO methods. In their empirical study, the authors demonstrate that despite restrictions and cuts for achieving DP, the adaptive HPO method involving a GP is still performing consistently better compared to uniformly sampling.", "questions": "- What about deterministic learning algorithms? Is DP also preserved via the framework?\n- Could not model-free HPO methods like Hyperband be used to maintain differential privacy? Since Hyperband is a relatively strong HPO method, this could potentially be another argument to stick to such approaches without using a model.", "limitations": "A discussion of limitations is missing in the paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ Flexible framework that allows to turn commonly used model-based HPO methods into DP-HPO methods\n+ Improvement over uniform baseline\n+ Theoretically guarantees for maintaining DP", "weaknesses": "- I am not an expert in DP but I think that privacy concerns should definitely be considered also in HPO. However, it seems like the framework is mostly centered around deep learning methods. At least there are certain assumptions for the guarantees to hold, e.g., that an ML algorithm run can be repeated to achieve a certain degree of privacy and also the experiments are solely limited to deep learning scenarios. As HPO methods are typically used in a much broader sense, it is therefore questionable to what extent the proposed framework also generalizes to other learning algorithms/models.\n\n- The common HPO community might not be familiar with the term \"privacy cost\" and it could make sense to at least briefly explain what the auhtors mean by privacy cost.\n\n# Minor\nl. 82: \"gurantees\"\nl. 168: \"bridges\"\nl. 198 \"proportion\"\nl. 227 \"update\"\nl. 228f the sentence is broken, maybe a word missing?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback!\n\n**For general ML problems**: We clarify that our results hold for much broader HPO problems beyond deep learning. The requirement of “an ML algorithm run can be repeated to achieve a certain degree of privacy” is not an assumption of our framework. Although our framework runs an iterative meta-algorithm that has a similar structure like deep learning, we do not limit the base algorithms to be deep learning. Actually, our framework is beneficial to any DP algorithm which has hyperparameters. For example, the sparse vector technique and propose-test-release (Cynthia & Roth, 2014) are two fundamental DP algorithms whose performance largely depends on the choice of hyperparameters.\n\n**Minors**:\nWe appreciate the reviewer's careful reading of our paper. We will correct all those good catches in the updated version. We will also make the meaning of private cost more clear.\n\n**DP and deterministic algorithms**: The notion of differential privacy (Dwork et al., 2006) is a probabilistic guarantee, which inherently requires the algorithm to be randomized. That being said, any nontrivial deterministic algorithm does not satisfy DP.\n\n**DP-HyPO with Hyperband**: Thanks for the advice. As we discussed in the paper, Gaussian Process is only one instantiation of the framework. Hyperband, as a bandit-based approach to HPO, should be suited with our DP-HyPO framework. We will list exploring this method as a future direction.\n\n[1] Dwork, Cynthia, and Aaron Roth. \"The algorithmic foundations of differential privacy.\" Foundations and Trends® in Theoretical Computer Science 9.3–4 (2014): 211-407\n\n[2] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to 375 sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography 376 Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. 377 Springer, 2006.\n"}, {"review_id": "aT0DuzudYF", "reviewer": "Reviewer_sjks", "summary": "Hyperparameter optimization (HPO) is an important step for enhancing the performance of private model training methods such as DP-SGD. Currently, most advanced HPO algorithms (e.g., Bayesian optimization) require to adaptively select the hyperparameters, but existing private HPO methods are non-adaptive. To fill in this gap, this paper proposed a differentially private adaptive HPO framework (DP-HyPO) which enables the conversion of any non-private HPO algorithm into a private one. The proposed DP-HyPO is shown to achieve a theoretical DP guarantee and outperform the non-adaptive DP-HPO baselines.\n", "questions": "1. Line 203-204: It is claimed that \"one can easily adapt the proof to other probability families?\". This is a strong statement without any justification. Can you provide any example?\n\n2. How is the constraint in Section 3.2 related to that in Framework 1? Is the method proposed in Section 3.2 only work when $\\pi^{0}$ is uniform?\n\n3. In Section 4.2.1, how is the budget $\\varepsilon$ selected? How is the tradeoff between adaptivity and privacy (Lines 220-223) demonstrated in the empirical results?", "limitations": "The limitations of the simple empirical settings are discussed but left to future work.\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This work has tackled an important problem of private HPO. It contributes some new ideas for converting the non-DP adaptive HPO algorithm into a DP one without incurring substantial privacy cost. The proposed Framework 1 is simple but has good generalization ability.\n", "weaknesses": "1. The presentation of this paper needs to be improved. To be specific,\n\n* The paper doesn't flow well. Some important information (e.g., definition of RDP) is referred to the appendix and other literature. I suggest to re-organize the paper, moving some less important information (e.g., Algorithm 2) into the appendix and including the key definition/concept in the main paper.  \n\n* Only showing the equations of the theoretical results is not enough, they need to be deeply analyzed for supporting the claims. For example, why is the base algorithm required to satisfy two RDP? Is this assumption realistic? Given the result of $\\varepsilon'$, what's the insight for each term in it and why is it considered as a \"sharp DP guarantee (Line 79)\"? \n\n2. This work has highlighted several times that handling infinite hyperparameter space is one of the key contributions. However, it is not clear how this is achieved. In Algorithm 3, the update rule of $\\pi^{t+1}$ seems to be intractable for infinite $\\Lambda$. In the experiments (Line 294), the hyperparameters are still discretized for the GP method.\n\n3. Other minor issues:\n\n* $\\mathcal{T}$ and T are used inconsistently in the paper.\n\n* The reference format needs to be carefully checked. The up-to-date paper should be cited instead of the arXiv version. For example, [20] has been published in ICLR. Some conference/paper titles should be capitalized (e.g., aaai -> AAAI, Dp-raft-> DP-RAFT, etc).\n\n* The DP Gaussian process and DP Bayesian optimization works are related but not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for valuable feedback.\n\n**Structure and flow**: We will restructure the paper to be of a better flow. \n\n**Advantage and practicality of Theorem 1**: The statement of Theorem 1 involves two RDP guarantees that **can be the same**, that is, we can have $\\alpha = \\hat{\\alpha}$, and $\\epsilon = \\hat{\\epsilon}$. Our results can improve the final privacy guarantee by optimizing the choice of $\\alpha, \\hat{\\alpha}, \\epsilon, \\hat{\\epsilon}$, but does not require the base algorithm to satisfy two different RDP guarantees. We believe this is realistic and provides more freedom for practitioners to obtain a better and sharp DP guarantee if the base algorithms happen to have more than one RDP guarantee. More importantly, most common algorithms in DP ML satisfy $(\\alpha, \\epsilon)$-RDP for any $\\alpha>1$, including DP-SGD. This Theorem generalizes a similar theorem that is “sharp” for the Uniform method in Papernot and Steinke (2021) which relies on exactly the same assumptions. We will add more discussions in our next version.\n\n**Infinite hyperparameter space**: Theoretically, our framework allows the hyperparameter space $\\Lambda$ to be of any topological structure, including being an infinite set with some continuous structure like a subset of $\\mathbb{R}^p$. One benefit of this perspective is that it allows us to adaptively and iteratively choose proper discretization of the space as we need. Meanwhile, as pointed out by the reviewer, empirically we require discretization to make the convex optimization solvable. However, as compared to the previous work, we can tolerate a much finer level of discretization since the performance of the Uniform algorithm degrades a lot with the number of candidates increasing. We will make this point more clear in the updated version.\n\n**Adoption to other probability families**: The crucial observation here is that our results depend on the probability through its probability generating functions as in Lemma A.5 on line 513 in appendix. By using the corresponding pgf in the proof for the derivations in line 530, one can generalize our proof to other probability families. There are other probability families that are proved in Papernot & Steinke (2021), which we believe is easy to generalize as the pgfs are already computed and used in their proofs for uniform method. Although the idea is straightforward, it is loose to say this would be “easy” for an arbitrary family. We will revise this statement and make it strict in our next version.\n \n**General priors for DP-HyPO**: Our framework also works for the general priors other than uniform distribution. We spend two separate sections in Appendix C and D discussing this point. We limit the prior to be uniform distribution mostly due to its mathematical simplicity, but other general priors are also considered in our framework.\n\n**Selection of $\\epsilon$**: In Section 4.2.1, the privacy budgets for both the GP-instantiated DP-HyPO and Uniform are selected to make a fair comparison between the two methods. In line 220-223, we discussed that a higher value of $\\frac{C}{c}$ means more privacy budget spending on adaptivity. We demonstrate the effect of this trade-off mostly in Section 4.2.2, where we vary the value of $C$ (and set $c = \\frac{1}{C}$). The detailed results can be found in Table 2. Our selection of $\\epsilon$ for the base algorithms is very typical in the DP literature. For example, it’s similar to the selection in Abadi, et al. (2016).\n\n\n**Reference**:\n\n[1] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy.\nIn International Conference on Learning Representations, 2021.\n\n[2] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 298–309, 2019.\n\n[3] Martin Abadi, et al. \"Deep learning with differential privacy.\" In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.\n"}, {"review_id": "tm9P55A696", "reviewer": "Reviewer_pfPa", "summary": "This paper introduces DP-HyPO, a framework for “adaptive” private hyperparameter optimization, aiming to bridge the gap between private and non-private hyperparameter optimization, that can allow practitioners to adapt to previous runs and focus on potentially superior hyperparameters. Besides, the arbitrary adaptive sampling distributions based on previous runs are allowed without any stability assumptions. The paper proposes experimental analysis to show the proposed methods' strengths. ", "questions": "1.  What is the purpose of Figure 1?  I want to know the details of experimental settings.  Maybe I have lost some important information.\n2.  What is the performance of other baselines? As the author states, some other baselines can be used for hyperparameter optimization.", "limitations": "The paper studies an important problem. However, the experimental section is unsatisfying and additional experimental analysis should be added. Besides, the author may want to clearly state the experimental settings.  Additionally, some non-adaptive methods should be compared such as Grid Search,  random search (RS), and Bayesian optimization (BO).", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses the problem of hyperparam optimization, which is an important problem. \n2. The paper proposes an interesting optimization framework, namely, DP-HyPO, which enables adaptive parameter selection under privacy constraints.\n3. The paper provides sharp DP guarantees for adaptive private hyperparameter optimization.", "weaknesses": "1. The experiments are not abundant, further evaluation should be listed.  There are only two sections related to the experiments which I do not think can reveal the strengths of the proposed method. Additional in-deep analysis should be conducted.\n2. In the experimental part, some related works are not compared. The author may want to add more related baselines listed in the Section of Related Works to show the efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for valuable feedback. While we respectfully acknowledge the input, we do have different viewpoints on certain aspects raised by the reviewer.\n\n**Empirical demonstration is important**: While our intention is to provide a rigorously theoretically-backed privacy accounting framework for HPO with DP consideration, we do believe a strong empirical demonstration is important. We acknowledge that the current experiment settings like MNIST are indeed overly simplistic, and think that could be the underlying cause why our experiments have not shown a significant gain. To address this, we conducted new experiments on CIFAR10 (a much more challenging task), and revealed a **substantial disparity** between our proposed approach and the baseline. Please refer to our \"general\" rebuttal for more detail.\n\n**Comparison to other related methods**: HPO with DP guarantee is an under-explored problem, and there are very limited related works.  The simple applications of methods like Grid Search and Random Search will result in the privacy cost growing linearly with the number of hyperparameter trials (proved in Liu & Talwar, 2019). Liu & Talwar (2019) and Papernot & Steinke (2021) proposed the uniform method (our baseline), and this is the only known algorithm whose DP guarantee is independent of the number of runs. Therefore, those methods (Grid search and Random search) are definitely undesirable when the hyperparameter space is non-trivial, which is the main focus of our paper.  This is the reason both us and the other two papers omit such comparison. We will make this more clear in the updated version.\n\n**The purpose of Figure 1**: Left panel of Figure 1 demonstrates the performance comparison of GP-instantiated DP-HyPO and the Uniform Method on MNIST; Right panel of Figure 1 demonstrates the same comparison on a real federated learning task with synthetically fitted loss landscape. We provided a detailed description in Appendix E of the original submission.\n\nReference:\n[1] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy.\nIn International Conference on Learning Representations, 2021.\n[2] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 298–309, 2019.\n[3] Shubhankar Mohapatra, et al. \"The role of adaptive optimizers for honest private hyperparameter selection.\" Proceedings of the aaai conference on artificial intelligence. Vol. 36. No. 7. 2022.\n\n"}, {"review_id": "rBwd4HAsUC", "reviewer": "Reviewer_o9LM", "summary": "This paper presents DP-HyPO, a pioneering framework for adaptive private hyperparameter optimization. Privacy risks are often neglected in private ML model training. DP-HyPO employs a comprehensive differential privacy analysis to bridge the gap between private and non-private optimization methods (non-adaptive HPO method and adaptive HPO method). The framework's effectiveness is demonstrated through empirical evaluations on a diverse range of real-world and synthetic datasets. DP-HyPO offers a promising solution for enhancing model performance while preserving privacy.", "questions": "Why a more challenging experimental setup was not used at the very beginning of the experiment? I don't think it would be difficult to find a more appropriate scenario to perform the evaluations.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is written to a high standard and is easy to understand. \n2. The availability of provided code facilitates reproducibility, making it a straightforward process.\n3. Adaptive hyperparameter optimization algorithms have an important place in practice. DP-HyPO permits the flexible use of non-DP adaptive hyperparameter methods, it is a very meaningful research problem. \n\n", "weaknesses": "I only have one concern regarding this paper, which pertains to the utilization of MNIST datasets that are deemed to be overly simplistic and small in scale. The performance improvement of GP compared to the uniform sample is far less than 1 percent as shown in Figure 1.\nAs mentioned in the conclusion, I would also recommend incorporating a more challenging dataset or a search space with greater complexity in future iterations of your work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback!\n\nWe totally agree that the current experiment settings like MNIST are indeed overly simplistic, and think that could be the underlying cause why our experiments have not shown a significant gain. To address this, we conducted new experiments on CIFAR10 (a much more challenging task), and revealed a **substantial disparity** between our proposed approach and the baseline. Please refer to our \"general\" rebuttal for more detail."}]

Author rebuttal:
We acknowledge that the current experiment settings like MNIST are indeed overly simplistic, and think that could be the underlying cause why our experiments have not shown a significant gain. To address this, we conducted new experiments on CIFAR10 (a much more challenging task), and revealed a substantial disparity (>2% performance improvement) between our proposed approach and the baseline. Please refer to our PDF for new experiment results.

Meta-review: Most studies so far about private-ML focused either on the training phase or the inference phase. This paper looks at hyper-parameters tuning and develops a differential private way to complete this task. By careful analysis, the authors bring us closer to being able to run ML pipelines while preserving privacy.
Decision: Accept (poster)