Private Hyperparameter Tuning with Ex-Post Guarantee
Authors: Badih Ghazi
Pritish Kamath
Alexander Knop
Ravi Kumar
Pasin Manurangsi
Chiyuan Zhang
Venue: NeurIPS 2025 spotlight ()
Keywords: differential privacy
hyperparameter tuning
ex-post differential privacy
Renyi differential privacy
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: The paper generalizes the utility-first approach in differential privacy to any sequence of private estimators, incurring at most a doubling of the privacy budget and allowing for hyperparameter tuning without additional privacy cost.

Abstract: The conventional approach in differential privacy (DP) literature formulates the privacy-utility tradeoff with a "privacy-first" perspective: 
for a predetermined level of privacy, a certain utility is achievable. 
However, practitioners often operate under a "utility-first" paradigm, prioritizing a desired level of utility and then determining 
the corresponding privacy cost.
        
Wu et al. [2019] initiated a formal study of this ``utility-first'' perspective by introducing ex-post DP. 
They demonstrated that by adding correlated Laplace noise and progressively reducing it on demand, a sequence of increasingly
accurate estimates of a private parameter can be generated, with the privacy cost attributed only to the least noisy iterate released. 
This led to a Laplace mechanism variant that achieves a specified utility with minimal privacy loss.
However, their work, and similar findings by Whitehouse et al. [2023], are primarily limited to simple mechanisms based
on Laplace or Gaussian noise. 
        
In this paper, we significantly generalize these results.  In particular, we extend the findings of Wu et al. [2019] and Liu and Talwar [2019] 
to support any sequence of private estimators, incurring at most a doubling of the original privacy budget. 
Furthermore, we demonstrate that hyperparameter tuning for these estimators, including the selection of an optimal privacy budget, 
can be performed without additional privacy cost. 
Finally, we extend our results to  ex-post R\'{e}nyi DP, further broadening the applicability of utility-first privacy mechanisms.

Private Hyperparameter Tuning with Ex-Post Guarantee
Badih Ghazi Google Research badihghazi@gmail com
Pritish Kamath
Alexander Knop Google Research
Google Research
pritishealum.nin edu
alexanderznop@googleecoo com
Ravi Kumar Google Research
Pasin Manurangsi Google Research pasinggoogle.co com
Chiyuan Zhang
Google Research chiyuan@google.com com
ravi www.ikk33mmml....m com
Abstract
The conventional approach in differential privacy (DP) literature formulates the privacy-utility tradeoff with "privacy-first" perspective: for predetermined level privacy, certain utility achievable. However, practitioners often operate under "utility-first" paradigm, prioritizing desired level of utility and then determining the corresponding privacy cost.
Wu et al. [2019] initiated a formal study of this "utility-first" perspective by intro- ducing ex-post DP. They demonstrated that by adding correlated Laplace noise and progressively reducing it on demand, sequence of increasingly accurate estimates of a private parameter can be generated, with the privacy cost attributed only to the least noisy iterate released. This led to a Laplace mechanism variant that achieves specified utility with minimal privacy loss. However, their work, and similar findings by Whitehouse et al. [2022], are primarily limited to simple mechanisms based on Laplace Gaussian noise.
this paper, we significantly generalize these results. In particular, we extend the work of Wu et al. [2019] and Liu and Talwar [2019] to support any sequence private estimators, incurring at most a doubling the original privacy budget. Furthermore, demonstrate that hyperparameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost. Finally, we extend our results to ex-post Rényi DP, further broadening the applicability of utility-first privacy mechanisms.
Introduction
Many applications of machine learning and statistics involve computation on sensitive data, necessitat- ing hriwacy-preeerving techniques. recent years, differential privacy (DP) [Dwork al., 2016] has become one of the most rigorous formalization of privacy, with many practical applications [Abadi al., 2016, Yu al., 2024, Mehta al., 2023, Tang et al., 2025, US Census Bureau, 2023, Hod and Canetti, 2025, Wilson al., 2020]. Recall that algorithm is DP if the output distributions on two neighboring inputs are close, where the closeness is determined by the privacy budget' e:
Definition 1 (Pure Differentially Privacy, [Dwork al., 2016]). For imput fromt D and output from O is e-differentially private (or simply, e-DP) iff Pr[M(D) = of S e (r') for all E O and neighboring datasets D. D' ED.
0, a mechanism M with
'Our work also applies to approximate-DD DP with parameter; see Section for the definition.
We also assume for simplicity that O is finite; it is simple to extend the results to the infinite case.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

For reasons that will become clear soon, we refer to the classic DP definition above as ex-ante DP.
Utility-First DP Mechanisms. One of the main challenges in deploying DP is ensure that the output remains useful. In particular, real-world deployments are often constrained by utility requirements. For example, in ML training, one may wish ensure that the model accuracy meets a certain threshold. Similarly, in statistical applications, one may wish to guarantee that the relative error of the estimated population is small (e.g., [Ghazi et al., 2022J). Such desiderata may not be compatible with the ex- ex-ante DP (Definition 1) since it priori specifies a fixed privacy budget E. This motivated Wu et al. [2019] to propose the notion of ex-post DP, where the privacy budget E can depend on the output of the mechanism, as formalized below.
Definition (Ex-post (Pure-) DP, [Wu al., 2019]). For a function È O + *R20, a mechanism M with input from D and oulput from O is ex-post é-DP i/ PrPM)()() of ell) Pr(M(D') = =], for all o E O and neighboring datasets D, D' E D.
Observe that any ex ex-post E-DP mechanism is ex-ante D-DP where max.co E(o). Furthermore, ex ex-post DP can also be used as a privacy filter to guarantee ex-ante DP [Rogers et al., 2023, Lebensold et al., 2024]. Roughly speaking, given total privacy budget for ex-ante DP, run multiple ex ex-post algorithms where we subtract the realized privacy budget E(O) from E until the latter is exhausted.
Thus, the main question in ex-post DP becomes: What is the smallest privacy budget needed to produce an output that passes the desired utility bar? As pointed out in [Wu et al., 2019], a simple algorithm here is the "doubling" method where we start from small privacy budget, run the "base" (ex-ante DP) algorithm with this budget, and continue until we find an acceptable output'. While simple, this doubling method can result in the privacy budget as large as four times* the optimal budget. Although there has been no improvement to this for general mechanisms, Wu et al. [2019] and later Whitchouse et al. [2022], building on earlier work by Koufogiannis et al. [2016], gave an elegant improvement for the simple Laplace and Gaussian mechanisms that allows for a finer control of privacy budget increment than doubling and also just pays for the final privacy budget, instead of the total privacy budget (via composition). Alas, their method does not apply to more complex mechanisms, such the seminal DP-SGD algorithm [Abadi et al., 2016] that is ubiquitous in private ML applications.
Hyperparameter Tuning with DP. A related challenge in private ML deployments is hyperpa- rameter tuning. A naive solution here is to run any standard hyperparameter tuning algorithm and compute the total budget via composition theorems. However, this results in a prohibitive blow-up in the privacy budget, depending on the number of times the base algorithm is invoked. Liu and Talwar [2019] devised simple algorithm but with surprising guarantee. Their algorithm performs hyperparameter tuning on any ex-ante c-DP by running it possibly multiple times (based on a carefully chosen distribution) and outputting the best found parameter. Even though the algorithm may be run many times, they show that the privacy budget incurred is only 3e. Furthermore, they show that, any "weakly useful" ex-ante DP hyperparameter tuning algorithm must incur privacy budget at least (roughly) 2s. A follow-up work by Papernot and Steinke [2022] closed this gap by giving an algorithm with privacy budget arbitrarily close to 2z, and further generalized this to work with Rényi DP [Mironov, 2017]. Although the task of optimizing the privacy budget in ex-post DP framework seems similar to hyperparameter tuming where is a parameter, none of the aforementioned works [Liu and Talwar, 2019, Papernot and Steinke, 2022] applies to this setting since they require the base mechanism to have a fixed value of in the ex-ante DP framework.
1.1 Our Contributions
In this work, we present the first hyperparameter tuning algorithm with ex-post DP guarantees. Our algorithm can take in multiple base mechanisms My.... ......, MM where M, is ex-ante D,- It then runs these mechanisms (possibly multiple times, based on carefully crafted distributions) and select the "best" output. The ex-post DP guarantee is that, if the output comes from the base mechanism M;, then the privacy budget spent is only (roughly) 25,- We consider this counterintuitive and highly surprising given that other base mechanisms Mj with higher budget (i.e., Ej E,) might be run en
Checking whether an output passes a utility bar must also done with DP. " factor of two due to having to apply the composition theorem to sums up all the budget, and another factor of two from the potential misalignment between the doubling exponential grid and the optimal budget.

---

route and their output considered as part of the selection, nevertheless, our algorithm does not have to pay for this higher privacy budget E We are unaware of similar phenomenon in DP.
While our algorithm (which works for multiple mechanisms with different 6; 'S) is a significant generalization of those of Liu and Talwar [2019], Papernot and Steinke [2022] (which only work for a single mechanism in the ex-ante setting), our privacy analysis is arguably simpler than theirs. In particular, the proof of our main privacy theorem (Theorem 8) draws inspiration from that of the Sparse Vector Technique [Dwork et al., 2009] and is elementary. We hope that the resulting simplicity will help further elucidate the underlining principles behind DP hyperparameter tuning. We note that our hyperparameter tuning is well suited for the task of optimizing the privacy budget given the privacy bar ex-ante DP, since we can set the "score" in the selection step to be based on the privacy budget and whether the privacy bar is passed.
Finally, we introduce a notion of ex-post Rényi DP and show that hyperparameter tuning with Rényi DP is also possible (Theorem 10). In addition, we prove a connection between ex-post Rényi DP and ex-post approximate-DP and construct a privacy filter that allows composing together a sequence of ex-post Rényi DP mechanism into an ex-ante Rényi DP guarantee (which could allow using this algorithm in practical systems that want to provide ex-ante guarantees). Our technique, which applies to any mechanism including the aforementioned DP-SGD, is far more general than those in [Wu et al., 2019, Whitehouse et al., 2022], which only applies to Laplace or Gaussian mechanisms. To demonstrate this, we provide experiments that empirically show that our algorithm outperforms those in [Wu et al., 2019, Whitehouse et al., 2022] for linear regression (using the conversion from ex-post Rényi DP to ex-post approximate-DP).
2 Preliminaries
Let D be set of datasets. We write D ~ D' as a shorthand for pair of neighboring input datasets (in D). Let O be any set; for simplicity, we assume that is discrete. We say that a function M mapping De E D to distribution over O is mechanism with input from D and output from O.
While have defined (ex-ante) pure-DP in Definition 1, it will be useful to recall other variants of DP. We start with approximate-DD DP, which allows an additional additive error ò in the difference in the two probabilities, as defined below. When 6 = O, this coincides with Definition 1. Definition (Differential Privacy, [Dwork et al., 2016)). For e, 2 O, a mechanism M with input from D and output from O is ex-ante (E, dddifferrentt private for simply, (E.8)-DP) iff Pr[M(D) E S] S E PriM(D') E S] + 6, for all S S O and all D D'.
Ex-Ante DP.
Modern private learning is largely based on DP-SGD [Abadi et al., 2016],The The privacy analysis of such a mechanism, which involves both subsampling and composition, is often done through Rényi DP [Mironov, 2017], which we recall here.
Let a > 1. and P and Q be two distributions on O. Let D (P 11) denote the Rényi divergence of P from Q i.e., D. (P Q) - log ((o)) (Q(o))
Definition 4 (Rényi DP, [Mironov, 2017)). For a > 1, E 2 0, a mechanism M with input from 'D and output from O is ex-ante (a, R)-Rényi DP (or simply, (a, (a,e) RDDP) D (M(D) M(D') S for all D D'.
Ex-Post DP. We also need approximate and Rényi variants of ex-post DP. We start with the former since it is defined in the literature before this paper.
and 5 > O, mechanism M with input from DD and output from O is ex-post (E, 8)-DP if for all S S O and all ~ D',
Definition 5 (Ex-post DP, [Wu et al., 2019]). For function é O - T
Pri(M(D) = o) S OES
((0) Pr(M(DD)= = o) + 8.
OES
Again, when 8 = 0. this coincides with Definition 2. Next, we introduce ex-post Rényi DP.
Definition 6 (Ex-post RDP). For a function s O + R220 and a: > mechanism M with input from D and output from O is ex- ex-post (a, E) RDP iff for all D ~ D',
(Pr(M(D) o))²
Σ OEO
(ec(o) Pr[MMDD) = ol) < 1.
3

---

We note that if É is a constant function, ex ex-ante and ex ex-post are equivalent for all DP notions stated.
In the case of ex-ante DP, it is known that ex-ante pure-DP is stronger notion than ex-ante RDP, which in turn is stronger than ex-ante approximate-DD [Mironov, 2017]. We can show here that a similar result holds for their ex-post variants, as stated below. The proof, which follows its ex-ante counterpart, is deferred to the Supplementary Material.
Lemma 7. Let & O -+ R2200 be a function and > 1, [0, 1] be constants.
*I is ex-post E-DP, then M is ex-post (a, ERDPP.
If M is ex-post (ar, (DDP,, then M is ex-post ,6,D),,, where (0) =( log 1/5 a-1
DP Selection Problem. The main focus of our paper is on the DP selection problem, which can be defined as follows. There are mechanisms , .M. - O where M, is ex-ante DP (or ex-ante RDP). Following [Papernot and Steinke, 2022]. assume that O is totally ordered set. The goal is to, after running Mi..... possibly multiple times, output (o, i) where e [d] and E O is an output from of the runs of M,. Occasionally, also allow output 1 to indicate that no good output was found.
A classic application of DP selection is in DP hyperparameter tuning of ML mechanisms. Here, each M, can represent the mechanism with different configuration of parameters (including the privacy budgets) and the output M)(D) is the private ML model together with the accuracy score on the test set. Our setting also generalizes the widely-used exponential mechanism in which case M, can be thought of as outputting the DP score of the ith candidate [McSherry and Talwar, 2007].
Probability Notation. For a distribution P. let supp(P) denote its support. For i E supp(P), let P()) denote the probability mass (resp., density) at i. For a subset T, let PPT) = Eier P(i) (resp.. J, P(i)di). Let Ber(y) denote the Bernoulli distribution with parameter p. i.e., the distribution on {0. such that the probability of 1 equals p. Lett Geom, denote the geometric distribution with failure probability p E [0, 1]. i.e., the distribution on Zo0 such that Gcom, Throughout this work, we will use the following property of the Geometric distribution in our proofs:
(1 - p)p².
(u) S pp=" Geomp(r)
Vu, E Z such that S
Note that the above inequality is in fact an equality for u 2 O.
Finally, let Exp, denote the exponential distribution with parameter À > 0, i.e., the distribution on Ry0 such that (x) -xz
3 Ex-Post Hyperparameter Tuning
In this section present new algorithm for hyperparameter tuning with ex-post DP guarantees (Algorithm 1). The main idea random dropping, where we only include an output from each M; to the candidate set S with certain probability. While this bears some similarity with the random stopping technique of Liu and Talwar [2019], our main innovation is the use correlated randomness k that is sampled at the beginning of the algorithm and determines the dropping probabilities of all the mechanisms. This idea is inspired by the Sparse Vector Technique (SVT) [Dwork et al., 2009], in which threshold is noised at the beginning of the algorithm. Indeed, the high-level structure of our proof follows that of SVT: we couple & with k + 1 in the two neighboring datasets, and bound the ratio of the output probabilities in the two cases. This is formalized in the proofs below. Furthermore, in Appendix A, we describe SVT (specifically, the AboveThreshie algorithm) and its connections to our method in more detail.
For convenience, we extend the order on O to (O x [d]) U {1}, where 1 is the minimum element, and elements in O x [d] are ordered lexicographically.
3.1 Pure-DP
Our privacy guarantee for pure-DP for Algorithm is stated below. It says that, if the final output from M,, then the privacy budget we pay is only 2c; + e', where e' is a parameter of the distribution
'If' the test set is considered sensitive, then we add noise to achieve DP with respect to the test set.

---

Algorithm 1 Hyperparameter Tuning Mechanism with Random Dropping.
Parameters: Distribution &, Mechanisms M; D + O and budget parameters for i [d]
Input: Dataset D.
S < {1) Sample k _
for ,,...,d, do Sample y/4 ~ Ber(e if y/+ then + M,(D;)
[random drop)
S SU (()
return maximum element in S
{as per the total order on (O [d] U ((1))
& = Geom, This e' can be arbitrarily small, although setting it too small results in a larger drop probability. The latter can mitigated by repeating each mechanism M, multiple times in the input, which allows us to set that the desired expected number of times that each mechanism is run.
Theorem 8 (Ex-post Pure-DP). Let g' > O and let each M; be EP-DP. Define function é such that E(o, i) 25, + e' and E(L) Then, Algorithm I with Goom,-e' ex-post č-DP.
Proof. Consider neighboring datasets D ~ D'. Let A, A' be the output distributions of Algorithm 1 on D, respectively and let 2i, D be the output distributions of M; on D, D', respectively.
First, the probability that Algorithm 1 outputs T. is independent of input dataset and so A(L)
A'L Next, consider any output (o, i) E O x [d]. For each j E [d] {i), let U == fo' E O
(d.j) > (o,1)}- Since M, is DD, it holds that (U 2 e 53 Similarly, we have
(o( S e (o(). Finally, (1) yields Geom, (k) c² Geom 2 (k: + 1). Thus, we have
A(o, i)
Geom, . (k) e c:k O.(0)
II II (1-0-st,((i))
jæi
Geom.- (e' Geom (k (k+1)) E (()) II [I(1 11- 11-e-sh (1 ((0g)()))))
jfi
8 6 20/t'
Geom.-r (1(+1) (((tt)))))))))) (((0) II (1- (--- ((1t))
##
S 2e i'
The state-of-the-art (ex-ante) pure-DP hyperparameter tuning from [Papernot and Steinke, 2022, Corollary 3] can only take in single mechanism Q that is e-D.. To compare this with our mechanism, consider the case where Mi up to the difference in the distribution of the number of times Q is executed. Figure compares the standard deviation versus the mean of these two distributions. While our distribution has a larger variance, emphasize its several advantages: more general as works for different mechanisms with different e values.
MM = Q. In this setting, the two mechanisms are equivalent
proof is completely elementary and our algorithm
In addition, such repetition trick allows us to prove utility lower bound that achieves "boosting" effect. To set stage of the formal statement, note that we will give a relatively weak assumption that at least one of the mechanisms Mj- outputs "good" candidate with small probability a. The theorem below states that, by repeating each mechanism M, a certain number of times T,, we can ensure that Algorithm I outputs "good" candidate with probability at least 1 - B (where B is small number). We formalize this below, where "good" candidates are those that are at least o*. Note also that T; is upper bound on the number of times the mechanism M, is run."
'In ML settings, the score itself is computed as measure of performance on test set, as proxy for the measure of performance the population distribution. When running more mechanisms, would need
5

---

200
Theorem [Papernot and Steinke, 2022]
Standard Deviation
150
100
50
0
0
20
40
60
100
120
Expectation
Figure A plot of the standard deviation vs expectation of the number invocations of mechanism by the algorithms from Corollary 3 in [Papernot and Steinke, 2022] for v = e'/e and Theorem 8 for Geom for 0.1 and g 0.01.
) In [n3)
sa/e'
Theorem 9. Let a, 3 E 10 and let T:
1 a
Consider Algorithm I with
= Geom o where, for all E [d]. we repeat M,, T; times in the input parameter sequence.
If there exists Of E O and it E [d] such that Pr[M, (D) 2 o²1 a, then Algorithm 1 outputs element that is larger than (o", with probability at least 1 B.
Proof. If the final output is smaller than (o", i*), then in all runs of M,,, it either has be dropped or the output is less than o* (or both). For fixed value of k. this happens with probability at most (1
ck a)T I exp (-e S-r a T²-). Due our choice of T.., this is at most 3/2 for ls < In (2/B) /e'. Thus, the probability that the final output is smaller than (o", ,i' is at most 3/2 Pr Pr
In (2/3) /e"] < B.
Finally, we remark that, even in the ex-ante setting with all e's being equal. Liu and Talwar [2019] showed that the additional factor of 2 in the privacy budget is necessary even under very weak assumption on the utility. This gives strong evidence that our algorithm (in its generic form) requires such a factor of 2 blow-up as well.
3.2 Rényi DP
In this section, we consider the setting where each M; satisfies Rényi DP (RDP) instead of pure-DP. As alluded to earlier, many popular DP machine learning algorithms, including DP-SGD [Abadi al., 2016], do not satisfy pure-DP but are amenable to privacy analysis using RDP. By changing the distribution of & from the Geometric distribution (in the pure-DP case) to the Exponential distribution, we can show version Theorem 8 for RDP.
Theorem 10 (Ex-post RDP). Let li...,, 2 0 and us assume that each M; (a, RDD with the output set O x R. Let T; be the expected number of times M; is executed in Algorithm 1 (note that it is independent of the dataset); and let T =E=
Define a function such that ē(o, (2+ l,); + (1 4))= + 1gg(++1)-E,a (y0+
and
a-1
E(L) a-1
log(r+1) Then, Algorithm with Exp_ (a, RDDP.
larger test set in order get good generalization. This is orthogonal to Theorem 9, which in this setting would refer to o the performance the population distribution.

---

we can ensure that We defer the proof of Theorem 10 to Appendix B, and provide a high-level overview here.
Recall that in the above proof of Theorem 8 we use the inequality (1 (1-e) (1-e-sht,(U?) QU(U))) -
(1 (1- (1-
which follows from the assumption that Mh is E The main challenge in proving an RDP bound is that such an inequality fails since the assumption that M, is (, -RDP is weaker. To tackle this, we change the coupling: instead of coupling k with k + 1, we couple & with k + 1+ 4. Note that, since we allow l to be non-integer (e.g., a value below one), this step necessitates the use of the Exponential distribution instead of the Geometric distribution. This new coupling allows us to instead compare (1- (1-e-s) (U()) with (1- (1-=
Alas, the former still not necessarily smaller than the latter. Nevertheless, via a careful argu- ment, we can bound the ratio of these two quantities. Such a bound then ends up as the last term 1 - (1-ae))
our RDP guarantee in Theorem 10.
We note that, unlike Theorem 8, ((L) in Theorem 10, i.e., we pay privacy budget even when we fail to output anything meaningful. Again, this can be mitigated by repeating each mechanism multiple times in the input decrease the probability of outputting J. to be arbitrarily small.
When the e 's are different, it might be beneficial to pick E to different as well. On the other hand, if we only consider the simple setting when ěι
Ed = E and we wish to choose ,
to all be equal to f. Then, it is not hard to verify that by setting = O log
Eieege (1++ae)) 1. With this setting of parameters and assuming e' s O()), we thus have the RDP bound of E = 22 + E' + O log d
Note that this is similar to the bound from state-of-the (ex-ante) RDP hyperparameter tuning from [Papernot and Steinke, 2022, Theorem 2), which gives an RDP bound of (2 :7)5 + O (logd) where 1) is the parameter of the negative binomial distribution (and assuming ? E (0. 1) a constant and - X, E =).
Alternatively, one may notice that E(o, doesn't depend on &j for j * i; hence, for each i it is possible to choose & value minimizing é(o, i).
Fully-Adaptive Composition with Ex-Post Rényi DP
Real-life applications of DP mechanism are often highly interactive: i.e., the analyst queries private data and based on the results of these queries decides what to query next. Moreover, often it is important to be able to choose further privacy parameters based on previous responses. Following Rogers al. [2016], we express this interactivity in form of a "game" between an adversary A and some system Fa.s In this interaction there is an unknown bit that the adversary wishes to learn; on
each step the adversary (based on previous responses) chooses two datasets D and D a privacy loss function é,, and a mechanism M, that is (a, RRDP: the system decides if such request could
be answered; and if the system allows proceed, the result (D(((") is given to the adversary. Our privacy filter is simple: Start with total RDP budget e, subtract from it the ex-post RDP bound after each request is answered, and only allow the next request to be answered if the remaining budget is at least the maximum possible ex ex-post RDP bound of the mechanism. See Algorithm 2 for the details.
Algorithm 2 Privacy filter for ex-post RDP.
Parameters: Order & > 1, privacy budget > 0, number of steps n. Input: Adversary A. private bit b {0, 1}.
for i from (o n do
D D
(1) E,, M; + A(or, ... 0.-1)
if -ー == ēo(0,) + sup, E((o) > = then
return O1...., 0
0 + (, return 01, 01, On
7

---

Our privacy filter allows us to use ex-post RDP algorithms in interactive manners while ensuring final ex-ante RDP bound. This result extends the results Lécuyer [2021], Feldman and Zmic [2021] to allow adversary to issue mechanisms with ex-post guarantees. We note that such connection between ex-post DP and ex-ante DP via a privacy filter has been made before, e-g., for pure-DP and approximate-DD DP [Rogers et al., 2016, Lebensold et al., 2024], and for specific RDP mechanisms like Brownian Noise Reduction [Rogers et al., 2023]. We believe our work is the first to generalize this filter to the full, arbitrary class of ex-post RDP mechanisms, although the proof of our filter follows simply from the aforementioned previous work. We defer the full proof to Appendix C.
Theorem 11. For any adversary A, a
D. (IT (. A) || (Faei S E,
where IT (Fo A) is the output of Algorithm 2.
Experiments
We present two sets of experiments: In the first, we evaluate the performance of our algorithm on analytical tasks and in the second, we focus on the performance a machine learning problem.
5.1 Analytical Problem
Informally the problem is as follows [Rogers et al., 2023]: given a message board, the goal is to estimate the number of unique per thread, each with relative error 10%; estimates possible. Here, user could contribute to any of the threads. We consider two datasets.
many
Synthetic: The synthetic datasets
generated
follows:
N
18000,1600,, 16000, 32000, 64000, 128000} samples are obtained from the power-law distribu- tion with support to 0.75 and is otherwise). We assume that each x corresponds to a thread and the number of samples with this value is the number of users. Hence, convert these samples into histogram 300 values with their counts.
330] (i.c., the distribution such that for x E [300]. the density is proportional
Reddit:
We use the webis/tldr-11 dataset [Völske et al., 2017] that contains authors of posts and subreddits where the post was posted. The histogram consists of subreddits (i.e., threads) and the number of unique users who posted in the subreddit.
We consider two types of algorithms: where pure-DP guarantee is available and another where we eventually have an approximate-DP guarantee. However, in both cases, we can check whether the current estimate v is good (i.e., expect it to be with less than 10% error) by checking that (ú + a - a)| E [0.9, 1.1] and j0] 2 a, where a is the standard deviation of the noise used to obtain the estimate.
For pure-DP, we follow [Rogers et al., 2023] and allow mechanisms to compute each estimate with privacy budget = 0.001 (V2)* for some i, with a total budget of 10. The comparison includes the doubling mechanism with Laplace noise (the algorithm that attempts one after another and pays for them via composition) [Wu et al., 2019], noise reduction method with Laplace noise from [Wu et al., 2019], and Algorithm with Laplace mechanism and E' 0.001. The detailed results can be in Table 1. Note that in terms of number of produced answers, our algorithm outperforms all other solutions and in terms of precision (percentage of outputs that were indeed with 10% relative error) is similar to the doubling estimator and within reasonable bounds.
For approximate-DD. we allow mechanisms to compute each estimate with privacy budget 0.001 - (v2)* for some i, with total budget of (10, 10 10-6). We compare the doubling mechanism with Gaussian noise and zCDP budgeting [Bun and Steinke, 2016), Brownian Motion algorithm with zCDP budgeting [Whitehouse et al., 2022], and Algorithm with Gaussian mechanism and RDP budgeting. The results can be seen in Table 2. this case, our algorithm underperforms, which not too surprising since the Gaussian mechanism with zCDP budgeting is tailored for tasks of this nature.

---

Table 2: Comparison between approximate- DP mechanisms on synthetic data; the column 'Produced Answers' contains the average and standard deviation of the number of threads that the algorithm was able to estimate before the budget got exhausted and the column 'Precision' contains the average and standard deviation of the fraction of threads that were estimated with less than 10% relative error among the estimated columns. cell value a = means is the average and b the standard deviation. The dataset name SN means synthetic dataset made of N samples.
Brownian Motion
Doubling
Algorithm w/ Gaussian
Mechanism
Mechanism
Dataset
Produced Answers
Produced Answers
Produced Answers
Precision
Precision
Precision
S8000
0.974 +
28.63 = 0.74
0.969
17.20
0.57
0.970 + 0.09
6.694
S16000
0.973 + 0.02
50.44 + 0.89
0,971 + 0.0
30.75
# 0.65
0.972 + 0.s
11.97 0,33
S32000
0.974
0.02
88.58 + 1.01
0.973 ouz
54.74
0.971 + 004
20.61
S64000
0,975
+ 0.01
154.8
= 1.29
0.974 0.00
96.95 1.01
0.973 + o.
33.84 0.63
$128000
0.977 n.t
269.7 = 1.50
0.980 + 0.1
173.6 1:23
0.970 + am
52.33 1.17
Table 1: Comparison between pure-DP mechanisms; the column 'Produced Answers' contains the average and standard deviation of the number of threads that the algorithm was able to estimate before the budget got exhausted and the column 'Precision' contains the average and standard deviation of the fraction of threads that were estimated with less than 10% relative error among the estimated columns. A cell value a means is the average and b is the standard deviation. The dataset name SN means synthetic dataset made of N samples.
Doubling
Noise Reduction
Algorithm w/ Laplace
Mechanism
Mechanism
Dataset
Produced Answers
Produced Answers
Produced Answers
Precision
Precision
Precision
S8000
0 + 0.07
14.77 + 0.47
0.999 + 0.02
2.22 + 1.45
0,912
0.06
20.37 + 0.52
$16000
0.912
+ 0.05
22.47
0.999
4.47
# 2.22
0.911
30.63 + 0.57
S32000
0.910 # 0.05
33.96
+ 0.56
0.998 + 0.12
8.12
+ 3:29
0.905
0.04
45.74 +: 0.63
$64000
0.909 = 0.04
50.90
+
0.998 = 15.14
5:2
0.911
0.03
68.39 + 0.7
S128000
0.909 = 0.05
76.09
+ 0.74
0.997 = n.01
27.68 9.15
0.912
0.03
102. + 0.8
Reddit
0.911 = 0.02
279.7 1.10
0.992 6.01
207.2
421
0.922
327.5 + 13.9
5.2 Machine Learning
We perform the following experiments related to an ML task.
1. In the first set of experiments we follow the setup from [Wu et al., 2019, Whitehouse et al., 2022] and train linear regression model dataset of timeseries generated by Twitter usage ['The AMA Team at Laboratoire d' Informatique de Grenoble] (subsampled to 100000 data-points) and search for model with at most 0.05 MSE. We compare the following mechanisms.
(a) Brownian motion with the AboveThreshole mechanism using sufficient statistics perturba- tion [Vu and Slavkovic, 2009], sequence 0.1, 0.2. of values of for Brownian motion, and 0.01 for AboveThreshold on the MSE of the model.
(b) Algorithm 1 with the DP-SGD [Abadi et al., 2016] mechanism, learning linear models with e' 0.01, possible values of E in {0.1, 0.2, ... 1}. learning rate in (0.01, 13. epochs in {1, 5, 10}. batch sizes in (32, 64, 128, 256, 512, 1000). and clipping norms in {0.1, 1, 10).
(c) Doubling mechanism Wu et al. [2019] running DP-SGD tuned according to Papernot and Steinke [2022] with identical hyperparameters to those used by Algorithm 1.
In the second set, we train a classifier for the MNIST dataset [LeCun et al., 2010] and search for the minimal & such that the model has least 0.6 accuracy. We compare the following mechanisms.

---

Table Comparison of the values used by the Brownian Motion mechanism, doubling mechanism, and Algorithm when applied to machine learning tasks. The numbers represent the average ex ex-post (e, 10 JDD guarantees over 100 trials.
Dataset
Brownian Motion
Doubling Mechanism
Algorithm
Twitter
0.77
0.55
0.28
MNIST 0.62
0.38
0.32
Gisette 0.33
0.54
0.23
(a) Brownian motion with the AhoveThreshold mechanism using output perturbation [Vu and Slavkovic, 2009], a sequence 0.1, 0.2.... of values of e for Brownian motion, and 0.01 for AboveThreshold accuracy of the model.
(b) Algorithm with DP-SGD mechanisms learning CNN models (for the architecture Basic MNIST Example) with e' = 0.01, possible values of in {0.1, 0.2, 1). learning rate in {0.01, 0.1, 1). epochs in {1, 10), batch sizes in (32, 64, 128, 256, 512, 1000), and clipping norms in (0.1, 10}.
(c) Doubling mechanism Wu et al. [2019] running DP-SGD tuned according to Papernot and Steinke [2022] with identical hyperparameters those used by Algorithm
In the third set, train classifier for the Gisette [Guyon et al., 2004] dataset and search for the minimal & such that the model has at least 0.4 accuracy. We compare the following mechanisms.
(a) Brownian motion with the Slavkovic, 2009], sequence 0.1, 0.2, ... 1 of values of for Brownian motion, and 0.01 for AboveThreshold on accuracy of the model.
mechanism using output perturbation [Vu and
(b) Algorithm with DP-SGD mechanisms learning a linear model with s' = 0.01, possible values of in {0.1, 0.2, 1). learning rate in {0.01, 0.1, 1}. epochs 5,, 103, batch sizes in {32, 64, 128, 256, 512, 1000}, and clipping norms in 10.1, 10).
(c) Doubling mechanism Wu et al. [2019] running DP-SGD tuned according to Papernot and Steinke [2022] with identical hyperparameters to those used by Algorithm
(In both cases
Opacus [Yousefpour et al., 2021] for training DP-SGD.)
The results of comparison can be seen Table Our algorithm significantly outperforms the previous Brownian motion algorithms and doubling mechanism. This can be explained by the fact that DP-SGD vastly outperforms the simpler models in these settings (Yu et al., 2020] and the fact that doubling requires running tuning which (in order to keep the budget small) needs high a. Our algorithm also consistently outperforms the doubling mechanism. This superior performance can be attributed to the doubling mechanism's 's privacy loss being approximately two times greater than that of the tuning mechanism which in-turn about two times greater than the underlying procedure.
Conclusion and Open Problems
In this work, we give simple yet general algorithm for DP hyperparameter tuning that works even for ex-post DP and RDP. Despite its generality, our experiments show that it achieves significant advantage over previous algorithms for MI. applications. Two immediate questions remain. First, is it possible to get rid of the f's in Theorem 10? Second, and somewhat related, is the question of proving zCDP version of the result, which would improve the analysis in the case of analytics workloads since the Gaussian mechanism is typically used in those cases.
10

---

Acknowledgments
We thank the anonymous reviewers for their valuable feedback. We also thank Ryan Rogers for helpful discussion and for clarifying the connection between their work on privacy filters [Rogers al., 2023] and the ex-post RDP framework presented in this paper.
References
M. Abadi, A. Chu, I. J. Goodfellow, H. B. McMahan, Mironov, K. Talwar, and Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016.
Basic MNIST Example.
URL https://github. mitt..
httpp//orcc//xmmplsseeeeeee The example of MNIST writ-
ten using PyTorch.
M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In TCC, pages 635-658. 2016.
Z. Ding, Y. Wang, Y. Xiao, G. Wang, D. Zhang, and D. Kifer. Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms. VLDB J., 32(1):23 48, 2023.
C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381-390, 2009.
C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. JPC, 7(3):17-51, 2016.
V. Feldman and T. Zrnic. Individual privacy accounting via a Rényi filter. In NeurlPS, pages 28080-28091, 2021.
B. Ghazi, B. Kreuter, R. Kumar, P. Manurangsi, Peng. Skvortsov, Y. Wang, and C. Wright. Multiparty reach and frequency histogram: Private, secure, and practical. PETS, 2022(1):373-33) 2022.
I. Guyon, S. Gunn, A. Ben-Hur, and G. Dror. Gisette. UCI Machine Learning Repository, 2004.
Hod and R. Canetti. Differentially private release of Israel's national registry live births. In & P, pages 101-101, 2025.
Koufogiannis, S. Han, and G. J. Pappas. Gradual release of sensitive data under differential privacy. JPC, 7(2), 2016.
J. Lebensold, D. Precup, and B. Balle. On the privacy of selection mechanisms with Gaussian noise. In AISTATS, pages 1495-1503, 2024.
Y. LeCun, C. Cortes, and C. Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: htp::/yann.lecum. http:///www.......o////////////a www//e/d/////iss....ommmmomm 2, 2010.
M. Lécuyer. Practical privacy filters and odometers with Rényi differential privacy and applications to differentially private deep learning. arXiv:2/03.01379, 2021.
J. Liu and K. Talwar. Private selection from private candidates. In STOC, pages 198-309,40 2019.
F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94-103, 2007.
H. Mehta, A. G. Thakurta, A. Kurakin, and A. Cutkosky. Towards large scale transfer learning for differentially private image classification. TMLR, 2023.
I. Mironov. Rényi differential privacy. In CSF, pages 263-275, 2017.
N. Papernot and T. Steinke. Hyperparameter tuning with Rényi differential privacy. In ICLR, 2022.

---

R. M. Rogers, S. P. Vadhan, A. Roth, and J. R. Ullman. Privacy odometers and filters: Pay-as- you-go composition. In NIPS, pages 1921-1929, 2016.
R. M. Rogers, G. Samorodnitsky, Z. S. Wu, and A. Ramdas. Adaptive privacy composition for accuracy-first mechanisms. In NeurIPS, 2023,
X. Tang, A. Panda, M. Nasr, S. Mahloujifar, and P. Mittal. Private fine-tuning of large language models with zeroth-order optimization. TMLR, 2025.
The AMA Team at Laboratoire I'Informatiuue de Grenoble, 2017. Buzz prediction in online social media.
US Census Bureau, Decennial census of population and housing disclosure avoidance, 2023.
URL https: //www//www////////////////// census gow/programs- seavveysddeeenial... www.e/eennnnneeeeeeeeeeeeeeeeeee www.a/aeatettppoeeeeeeeeeeeeeeee /oocsssessscccssseueeeeeee avvodaacce .ttml.
M. Völske, M. Potthast, S. Syed, and B. Stein. TL;DR: Mining Reddit to learn automatic summariza- tion. In Proc. Workshop on New Frontiers in Summarization, 2017.
D. Vu and A. B. Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In ICDM Workshops, pages 138-143, 2009.
J. Whitehouse, A. Ramdas, Z. S. Wu, and R. M. Rogers. Brownian noise reduction: Maximizing privacy subject to accuracy constraints. NeurIPS, 2022.
R. J. Wilson, C. Y. Zhang, W. Lam, D. Desfontaines, D. Simmons-Marengo and Gipson. Differ- entially private SQL with bounded user contribution. PETS, 2020(2):200-250, 2020.
Z. S. Wu, A. Roth, K. Ligett, B. Waggoner, and S. Neel. Accuracy first: Selecting differential privacy level for accuracy-constraneed ERM. JPC, 9(2), 2019.
A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj. J. Zhao, G. Cormode, and I. Mironov. Opacus: User-friendly differential privacy library in PyTorch. urXiv:2109.12298 2021.
D. Yu, H. Zhang, W. Chen, J. Yin, and T. Liu. Gradient perturbation is underrated for differentially private convex optimization. In IJCAI, pages 3117-3123, 2020.
D. Yu, S. Naik, Backurs, S. Gopi, H. Inan, G. Kamath, J. Kulkarni, Y. Lee, Manoel,
L. Wutschitz, et al. Differentially private fine-tuning of language models. JPC, 14, 2024.
12

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The abstract and introduction only mentions the statements proven in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected generalize to other settings.
It fine to include aspirational goals as motivation as long clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, the paper explicitly states the limitations of the results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e-g., the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Ye]]
Justification:
The paper proves all theoretical results.
Guidelines:
13

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper describes the algorithms and datasets used in the paper; moreover, all the experiments using standard algorithms with the sole exception of the main contribution of the paper since is a new algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a way to access this model for reproducing the results or a way to reproduce the model (c.g.. with open-source dataset instructions for how construct the dataset).
model (c.g., large language model), then there should either be
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers to have some path to reproducing verifying the results.
the case of
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The dataset used in the paper are standard and the paper has the code in the supplemental materials.
14

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines http:s::///ips.cccppplee guides/ Saltes/Cooeeubmiiee cttpsubmissioooooiiicooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed duce the results. See the NeurIPS code and data submission guidelines (https: : / /sw..npp....oo cc/ cc/ public/ wawicc/ggii///Cee /goides/Codeuummn www.ibmissssoPooooooooo sssinnolicyyy ply) for more details.
repro-
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ys]]
Justification: The choice of train-test data splits and optimizers used in the experiments are not significant for the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
Yes, the paper explains the significance of the important experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state that they have 96% CI, the hypothesis of Normality of errors is not verified.
15

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
all the experiments are performed on personal laptop within 10 minutes each.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each the individual experimen- tal runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips. cc/public httpppplllcuhiceeeeeeeeeppp Etthicauueeeeeees
Answer: [Yes]
Justification:
The paper conforms ethic guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The paper is mostly theoretical without direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point out. For example, is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
16

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper doesn't 't release any models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
No assets other than datasets are used in the paper, the datasets are cited
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. ctt/datameeeeeeeeeeeecc datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No assets are introduced in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
17

---

Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing are performed.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
experiments on human subject are performed part of the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
The paper doesn't 't use LLM as a component research.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httppp/////aoeere.ecoooooootaree http////ooeeeeecce////////////// for what should should not described.
18

---

A Warm-Up: Ex-Post AboveThreshold Mechanisms
Before we present our full ex-post DP Hyperparameter Tuning algorithm, would be helpful recall the Sparse Vector Technique [Dwork et al., 2009]. In particular, our ex-post DP Hyperparameter Tuning algorithm derives inspiration from the so-called Thoeshhheeholld mechanism.
A.1 Classic Above AboveThreshold Mechanism
To state the Above'Threshee mechanism, recall that the sensitivity of a function DD - is defined A(f) max maxD~>' D' If(D) {(D"),, where the maximum is taken over all neighboring input datasets D ~ D The setting here is that we are given sensitivity-1 fu fa and the goal output the first index such that fi( least zero." ? The mechanism works by first sampling a Geometric noise k to be its noisy threshold; then, for each fi we add an independent Geometric noise ys to it and check if it exceeds the threshold. If it does, we output and terminate. It turns out that, in addition to i, we can get an estimate of f; (via (D) + k) for free without any additional privacy cost [Ding et al., 2023]. full description is given in Algorithm 3.
Algorithm 3 AboveThreshold Mechanism
Parameters: Sensitivity-1 functions D + Z and budget parameters e, for i [d], and additional privacy budget > 0.
Input: Dataset D.
Sample k ~ Geom.ee"
(threshold noise) }
for i 1, 11...,, do
Sample ~ Geom. if (D) Yi 2 then
{query noise }
return (D) + yi k, i) and terminate
return
This algorithm generalizes the standard ex-ante DP ThoveThresholdd mechanism since we allow the noise for each f; to have different privacy budget parameter Eq. Indeed, with this mechanism, show that the ex- ex-post privacy budget spent for releasing fi is only 22, + E', as stated below.
Theorem 12 (Ex-post AboveThreshold), Define function such that i(o,i) 2s, E' for all o E Eza, E [d] and É(L) = e'. Then, Algorithm 3 is ex-post ě-DP.
Our proof closely mirrors the proof for the analogous ex-ante AboveThreshold Namely, for neighboring datasets D. D' and output (o, i), we can couple the Geometric noises such that k' + v/ = yi + + 1+ (D) - f((D)) and all other noises remain the same. It not hard see that, if the algorithm returns (o, i) on D, it returns (o, on D' as well. Furthermore, due to property (1) of the Geometric distribution, the probability decreases by at most e2ctte' factor. This idea is formalized the proof given below.
Proof of Theorem 12. Consider neighboring datasets D D'. Let A, A' be the output distributions of Algorithm 3 on D, D', respectively. Below, we write Geomp < x) as shorthand for Geom,(12)
1, x .....) }) Ey= (e)
First, consider any output (o, i). This output happens exactly when yi o + k Si(D) and Vj (D) for j < Thus, we have
A(o, = Σ Geom. -er (o II Geom -=(<<k (2)
Since A(fi) S we have o + 5 wotk++++++110 fi(')): applying (1) then yields
Goom.-r:(o+he ((DD) S (((()(())))) Geom, (0 k ++1- 1 (o fa(D))
< 25, Geom, c, (o + + -
(3)
We can easily handle non-zero threshold r by considering fi instead.
19

---

where the second inequality again uses (ff) - 1.
Furthermore, ((J)) & implies Geom - (< k - [D() & Geom (eomg-s,(< k + (D)))
Moreover, (1) implies Ge (k) S e Geom,-. 1). Plugging these two inequalities and (3) into (2) yields
i(),
Σ
Geom (k 1) 2 (o
II j=1
Geom - (t
K=U
Geom +
II j=1
Geom e 1
k=U
S 25-0 io,
Next, consider the output 1. This output happens when yj k I2(D) for all j E [d]. Thus, we have
A(L)
Ge
II jE|d]
Gcom,
k=0
Geom. (k) II
Geom
k=
jEld
8
Geom, a (k 1). II
Geom ((<++1-f((D))
JE(d]
Geom d' (k +))
II
Geom (ck+1-fs(D))
k=0
JE(4]
6 A'(L),
where again (f) s in the first inequality and (1) in the subsequent inequality.
A.2 Optimized Noise via Monotonicity
Let 2 denote any total order on D. We say that a function f is monotone (with respect to 2, ~) iff the following holds: I(D) 2 f(D') for all D ~ D' such that D Z D'. An example of this is when denotes an add-remove neighboring notion, i.e., D D' iff results from adding or removing a user from D'; in this case, we may let ł be based on the size of the dataset, and f is monotone iff adding a user does not decrease the function value. Such a property holds when f is counting the number of users satisfying certain criteria, which is example used in our experiment in Section 5.
For monotone /, the same algorithm (Algorithm 3) yields better ex-post guarantee, where do not need to pay the factor of 2 in front of E,, as stated below. Note that this is similar to saving seen in the ex-ante setting Ding al. [2023].
Theorem 13 (Ex-po Monotone Threshhls.... Define function È such that E(I) = E, + E' and E(L) = e'. If f is monotone, then Algoritium 3 is ex-post E-DP.
The proof proceeds similarly to before except that, in the monotone case, either (i) f((D)) 2 f((D) in which case the difference y ys is already at most (instead of two before), or (ii) fa(D") < (D) in which case we can instead couple with k' V. = yi + f(D - fD
resulting in 1/ yı < again.
Proof of Theorem 13. We use similar notations as in the proof of Theorem 12. The case of .L output is exactly the same in that proof. For the output (o,i), we consider the following two subcases, based on whether D' > D. First, let us consider the case D' > D. In this case, the proof is exactly the same as before except that, since fx(D') Z J:(D), in (3), instead get
Geom.- k f(()) < 55 (1-)(
Geom,-r, (o + - f((D'))
20

---

S ef ( -
Following the same line of reasoning as before, we then get A(o, i) 2 ggite' A i) as desired. Finally, let consider the case D ž D'. In this case, since fj(D) 2 (j()'), we have
DC A(o, = --Eeeee Geom k
1-1
II
Geoma-r, (ck==
k=0
Goom (k) (o
II j=l
Geoma-s (<k-
km0
Since + k fi(D) 1o+k--i(D)) we can apply (1) to arrive at Geom, 4 k- --kk-(())) S e.-((((D--((('')
(0 fil'))
E (o k f(D')),
where the second inequality follows from A(fi) 1. Combining the above two inequalities then gives
A(o, 1) - Geom (o- fi())) II
Geom -- (< - f<
k=
j=1
$
Geom - (k) - ctt Geom,-r, f((D') II
Geom -2z (< - fy('))
S cite (o,
which concludes our proof.
A.3 Generalized AboveThreshold Mechanism via Random Dropping
generalized algorithm for AboveThreshold with ex-post DP guarantees (Algorithm 4). We consider the following general setting: We have mechanisms Mi.... M2 D O and the goal is to output the first mechanism such that M, is at least certain threshold T E O. Our main idea is random dropping, where, instead of always comparing MD() with т, only compare with certain probability; otherwise, we drop MD( completely. While this bears some similarity with the random stopping technique of Liu and Talwar [2019], our main innovation is the of correlated randomness that is sampled at the beginning of the algorithm and determines the dropping probabilities of all the mechanisms. This idea is inspired by the above analysis of the AboveThreshold mechanism. Indeed, the high-level structure of our proof follows that we couple & with & + 1 in the two neighboring datasets, and bound the ratio of the output probabilities in the cases. This is formalized in the proof below.
Next, present
of
Algorithm 4 Generalized AboveThreshold Mechanism with Random Dropping.
Parameters: Distribution &, EDD mechanisms M; D - O, additional privacy budget e' > and threshold E O
Input: Dataset D.
Sample h ~ Geom,
for i 1,...,d do
Sample ~ Ber(e-sshh
(random drop)
if y then < MD, if o 2 then return (o),
return
21

---

Our privacy guarantee for Algorithm 4 is stated below. It says that, if the final output is from Ms, then the privacy budget we pay is only 22, + E'. The value of e' can be arbitrarily small, although setting it too small results in a larger drop probability. The latter can be mitigated by repeating each mechanism M; multiple times in the input, which allows us to set that the desired expected number of times that each mechanism is run.
Theorem 14 (Ex-post Generalized T Define a function È such that ē(o, = 22, + and E {(L) E'. Then, Algorithm 4 ex-post E-DP.
Proof of Theorem 14. Consider neighboring datasets D ~ D'. Let A, A' be the output distributions of Algorithm on D', respectively and let Q,, 2 be the output distributions of M, on D, D', respectively. Furthermore, let Ozr == {o' E O o' 2 r).
Consider any output (o, i) O x [d]. Note that, o < r. then A(o, i) = A'(o, Otherwise, 2 T, then the algorithm outputs (o, iff y Thus, we have
oj < for all j and yı = 1 and
A(o,
Σ Geom (k)) e k=
cckk 2.(0)
II (1- 11--00A,, JCL
Since My is EDDP, it holds that 2,(02r) 2 e (0(22)) 20 Similarly, we have 21(0) I E {(()))
Finally, (1) implies that Geom, . (k) S se' -Geom e (k + 1). Plugging these into the above gives
A(o,t) S
Goom / (k (1+1)) . c (c=2 II e (002)(()))))) j$i
8 Geom (k El(t+1) (() II
22,+s
(1- (
S 2 i),
Finally, consider the output 1. For the algorithm to output 1, we must have y, = 0 or 0g < T for all j E [d]. Similar to above, we thus have
A(L) = Σ Geom_-r (k)
II (1 c 0,(00)))
0=
.E [4]
c -comm--
II (1 - - (e ((02)))))))
k=0
jEId
(kom,-r(k+])
II SE[d]
1 (k+ (
k=0
A'L...
Theorem 14 can be viewed as a generalization of Liu and Talwar [2019] who prove similar statement stress that our mechanism is based different technique. As
for ex-ante DP. Nevertheless, demonstrated in the next section, our technique is more robust as it generalizes to hyperparameter tuning (without known threshold) with similar privacy guarantee, whereas Liu and Talwar [2019] have to pay a factor of 3 instead of 2 in that setting.
B Missing proofs for Ex-post Rényi DP
To prove Theorem 10, we start by collecting some useful facts. The first the following inequality which is sometimes called the "reverse Hölder's 's inequality";; we provide the proof for completeness.
Lemma 15. Let X be a random variable and f. be any functions on X. Then, for any a > 1, we have
< 9(x))
22

---

Proof. By Hölder's inequality, we have
xl - 2 E[S(X)).
Rearranging this yields the claimed inequality.
Lemma 16. For all > 0, a > 1, a E (0, 1) are such that a at S ella-1), then, for all t>0, 0,
a) (1-c 1 I exp (e=c(lta)))
Proof. From + x S e for all x E R, the LHS is at most exp((a - 1)e -e000 oa). It is thus sufficient to bound (a (1+00 aa.
To do this, observe that the condition a ba 6a S ecla-1) implies
a z boc
Thus, we may bound the desired term as follows.
(a - 1)e 1ee-=)(le - aa
(4)
1 (a- 1)e 1)e- -5(1+0 - a.c a e baT
e -
(a= - 1)e -abatr)
a a-1
(
a-1
(a-1)e-st (aa-1)et-abat)) a-1 .o.
bob
a-1
(a - ()e ol abaut
+ (a- 1) - b...
a
a
aa 1)e -e
1
2a-1
(((+a))
a
I (l+ta))
where we use the weighted AM-GM inequality for (+).
Proof of Theorem 10. We will use the same notations as in the proof of Theorem 8.
First, let rearrange the term we wish to bound;
Σ -
aEOX(dU(L)
( (a--)())
Σ ((((,))
1)8(o.a)
OEO,iE[1]
(A(o, (
(5)
T+1 oEO,iE[4]
We will now bound each term (A(o, (A'(o,, i) -a above. We have
1-a
i(, = EXWEXDS
0,() II 1-
jEld (i)
=Q,(o) Egn-EXp''
e E.
(1 e 2 2,(U8
jE[d]<(1)
23

---

and
i0
ExnExpp
0 (0) II (1-6 --
jEld/(()
.fe e'e-s'a, (0=5:00((0))
x
II (1-6-6 (((05)) do
jEId]-(1)
2 1 ge .e (0-=001000
II jE
2) (U,,)) dr
1444
-ettiileeteen ((()) | E'e e
II (1 5y(++(1 155 dx
jE(ds(()
=e-0ttaltte O(()) Expe
e Gp
II (1 ((tt) JE|4&(
(4)
where the integrals due to exponential random variables
Combining these two inequalities together with Lemma 15, we get that (A(o, (A'(o,) l-a S ((o=1)(+t))ettt) +o)) (Q(()))
-EEwExp
eex
II (1- -0,))) -1(16)) e ((2))) (E
To bound the inner term, first consider post-processing of mechanism My where, after running, only output whether the score is greater than st. Since this is post-processing of Mj. this mechanism is also (a, )-D.-DDPP.... As such, we have (Q,(U2)) (Q) ()) s ee>(a-1), Thus, we may apply Lemma 16 to conclude that
e 2 Q
- sillte) - ((U,))) S exp (e-sslttati).
Plugging this into the above, we arrive at
(A((.)))
exp
(1+tal)
E EnwExp -e- 5
fEld
(00 exp
(1++a8)
Ti
jEId
7+1 (00
where in the last inequality we use our choice of & and E(o, i).
Combining with (5), thus get
Σ
(1))
GEOx|d-[11
(2i()))
(a- 1)s.
++1
iE|d
DEO
(O)(
To
(a- 1)c;
1+1
(1(0))=-T
OEO
24

---

+
T;
6
(a-la-1)i
(a-
7+1
7+1 1
iE|d
T:
T+1
:E|d
C Fully-Adaptive Composition with Ex-Post Rényi DP
Proof of Theorem 11. Without loss of generality, we can assume that the adversary is always issuing queries such that E + sup, (o,)) I E for all E [n]. Let us denote the query issued by
the adversary after seeing O1...., 0i-1 as D 11-1 Do Eo and Mor....--- Let us also denote the distribution of Mot.... D ).......__) by p(l) Poi......... Note that
(ra || (Fa.(Fa)))))
(p()) (01) P (02) ... p(()
On- (0n))
Σ
(o1) (02) P (1)
0n-1 (0n) )a-1
01,02
(01 P (02) p!
Po....., a (On
(Pll) (on))
Σ
11) (o1) p! (02) p(l
(On-1)) ja1
(P on (0x))
01,02
Further, note that M Mo is (a, E Eo RDP and hence,
(Pot....__I(nn)) (on))
11. 1.
(e (oppunan- (0x) (1]
On (0n aa-1
(ot (0z) p(0)
, (0x)}
Let (() (o2) (o2) (oz)...e oo ((1) pofi..o (ou))
Then
(aa (a-I)D. (For)))) (Fo,))))
c(a-1)e
(P(O) (or) (o2) (0)
(02)
Pr...... on (0n))
cla-1)e
(P1) Po! (oz) P P (0n) )--1
01.02....0n
(P(0) (01 P!!! (02) ... or an (0n))
0n On (eE(or) p(1) (0z) p(l) (02)
on (0n) p(])
p (0n))a-1
Σ
on)
(Po (0m))
Σ
Loo On-1)
Σ
Eo (on) p(1)
0n-1 )an)
Σ
0n-1)
01
(0 ( (0a-1) (()) p
Σ
0p-2))
Σ
On (On- 1) a-
On
L(01) & 1, which implies that D. (IT
IT (Faeii Se.
01
25


Reviews:
[{"review_id": "zoQu5cXdIN", "reviewer": "Reviewer_Rabk", "summary": "The paper presents a general algorithm for hyperparameter tuning under ex-post differential privacy, compatible with both pure DP and Rényi DP. It privately selects among multiple candidate mechanisms, incurring privacy cost only for the selected one. The method supports complex workflows like DP-SGD and introduces an ex-post RDP filter to enable interactive composition. Empirical results demonstrate improved privacy-utility tradeoffs compared to prior approaches.", "questions": "1. Would the expression above line 178 be more accurately written as $\\tilde{\\varepsilon}(o, i)$?\n\n2. Can the authors provide more intuition on why the final ex-post DP guarantee depends only on the selected mechanism?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**:\n\nThis work presents a novel result in private hyperparameter tuning, with potential for practical applications. The algorithm’s design is elegant, and the accompanying proof is communicated with clarity. The author also derives a corresponding privacy filter, which appears to be of additional interest.\n\n\n**Weakness**:\n\nPlease refer to the question section", "was_revised": true, "final_justification": "This is a good paper. I will keep my positive score.", "rebuttal": "Thank you for your detailed review and suggestions.\n\n\n# Response to Questions\n\n\n1. We thank the reviewer for pointing this out. Indeed this is a typo and should be changed to $e^{\\\\epsilon_i + \\\\epsilon'} \\\\cdot \\\\mathcal{A}'(o, i)$. We have rechecked the proof and can confirm that, apart from this typo, the proof is correct.\n\n2. We find this surprising as well! Our rough intuition is that, since we randomly decide if each mechanism’s result is included in the final computation, this allows mitigating the leak of each individual mechanism. However, as can be seen in our paper (and previous works of Liu–Talwar and Papernot–Steinke), this requires a very careful strategy of how each mechanism is probabilistically included, together with a subtle privacy proof."}, {"review_id": "FLzTRruZ9m", "reviewer": "Reviewer_gugu", "summary": "This work introduces a hyperparameter tuning algorithm that provides ex-post DP guarantees, allowing a utility-first approach to DP selection. They propose a privacy filter that allows using their ex-post Rényi DP algorithm interactively ensuring a ex-ante guarantee. The authors demonstrate that they can achieve stricter privacy guarantees than prior work for ML applications.", "questions": "Some clarification is needed for Theorem 11—for example, the notation $IT^0$ and $IT^1$ is used without definition.\n\nMinor suggestions and comments:\n- shortly mention the definition of privacy filter \n- briefly discuss what having a larger variance implies (Figure 1)\n- Definition 6: is there a reason why you use $\\epsilon$ instead of $\\tilde{\\epsilon}$ here?\n- Line 93: missing brackets (Theorem 10) \n- for better reproducibility, mention the CNN model architecture (in 5.2 second experiment)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is well-motivated and addresses a relevant problem within the field. The authors provide a thorough theoretical treatment of their novel algorithm (hyperparameter tuning via random dropping) proving that it guarantees pure DP and Rényi DP respectively. They also evaluate their algorithm empirically, confirming its practical benefits (and limitations) on two types of problems (analytical and ML).", "was_revised": true, "final_justification": "I believe the paper is technically solid and, while not being groundbreaking, addresses a relevant problem in the field. The authors have also adequately addressed the reviewers' comments.", "rebuttal": "Thank you for your detailed review and suggestions.\n\n\n# Response to Questions\n\n\nAs alluded to in the paragraph starting at line 92, privacy filter is the typical way to build a system where an adversary is allowed to run ex-ante private subroutines interactively and the filter halts the computation if a target ex-ante privacy guarantee would be violated by request. \n\n\nHowever, our paper considers a generalization of this concept to a setting where the subroutines are allowed to be *ex-post* private. In other words, the filter we consider allows converting ex-post guarantee into the standard ex-ante guarantee. Here one would have a target ex-ante privacy budget (denoted by $\\\\epsilon$ in Algorithm 2) and the privacy filter allows us to run multiple ex-post DP subroutines. At the end, the guarantee of the entire algorithm is *ex-ante*. In other words, this can be thought of as a “composition theorem” for privacy, except that it allows ex-post DP subroutines and yet yields the more traditional final ex-ante DP. Finally, we note that we focus on RDP in Section 4 since a natural privacy filter for,  e.g., pure-DP is already known (Lebensold et al., 2024).\n\n\nAs for $IT^0$ and $ IT^1$, we define them to be the output of Algorithm 2 for $b = 0$ and $b = 1$, respectively. ($IT$ here stands for “interactive transcript”.)  We will make sure to include the definition more clearly in the main body in the revised version. Thank you for pointing this out.\n\n\n# Response to Comments\n\n\nRe variance and Figure 1: Larger variance in the number of invocation of the mechanisms also implies a larger variance in the running time and a larger “variance” in the utility guarantee. This is because the number of invocations of the Papernot–Steinke mechanism is more well concentrated around the expectation, so their running time and utility are also more well concentrated. (This is perhaps the price we pay for the generality of our algorithm–which works for mechanisms with different DP guarantees–compared to their algorithm.)\n\n\nRe CNN architecture:\nWe didn’t optimize the architecture for MNIST (since it was already outperforming linear models) and used the one from Opacus tutorial: it has two convolution layers and two linear layers with max-pooling (with kernel 2 and stride 1) and ReLU after convolution layers and ReLU after linear layers. \n1. The first convolution layer has out channel 16, kernel 8, and stride 2.\n2. The second convolution layer has out channel 32, kernel 4, and stride 2.\n3. The first linear layer has 32 output features.\n4. The second linear layer has 10 output features for each class.\n\nWe will make sure to add the architecture to the final text too.\n\n\nThank you so much as well for pointing out the other typos."}, {"review_id": "qLHKYTIWGS", "reviewer": "Reviewer_ULcx", "summary": "Wu et al. 2019 proposed the framework of Ex-post DP, which aims to search for the smallest privacy budget that passes  a specified  utility.  Despite practical relevance, literature on Ex-post is limited and existing methods do not apply to DP-SGD.\n \nAuthor’s contribution starts by extending ex-post DP to ex-post RDP. Their main contribution is a new algorithm and a bound (inspired from the proof of SVT) for DP selection problem under ex-post DP/RDP.  The DP selection problem has applications in hyperparameter tuning/model selection process.\n \nA major limitation of seminal results from Liu and Talwar 2019 and Papernot and Steinke 2022 for (ex-ante) DP-aware hyperparameter tuning (model selection) is that they assume the same privacy cost for all base mechanisms. This means one can tune the batch size, DP noise scales or number of epochs for a fixed epsilon, but not the base epsilon itself.\n \nTake-away from their bound: Among several candidate ex-ante DP mechanisms with (possibly) heterogeneous ex-ante $\\epsilon$’s, if the ith mechanism produces the best result, then the total ex-post budget of the entire exploration is only $2\\epsilon_i$. The factor of 2 seems unavoidable.\n\nThey also propose a privacy filter to adaptively compose several ex-post RDP mechanisms to obtain the final ex-ante guarantee.", "questions": "1)\tAlgorithm 1 does not include the step for checking whether output passes the utility threshold for each $M_i$. Can you please clarify? \n\n2)\tThe line 138 seems to suggest that 'M_1,...,M_d' can be executed multiple times. However, there is no outer loop in Algorithm 1. So, it seems the number of distinct mechanisms need to be much lower than d to have each mechanism run multiple times. If my understanding is correct, please mention this explicitly.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1)\tYou only incur the privacy cost of  the best mechanism which may have much smaller budget than the suboptimal mechanisms with higher budgets. This effect is quite surprising.\n2)\tThe bound places no restrictions on the mechanisms used, and also applies to DP-SGD which is the main the main beneficiary of hyperparameter tuning methods.  \n\nWeakness:\n1)\tThe runtime of this method has higher variance than Papernot & Steinke for the same expectation. But authors already mention this. \n2)\tThe final ex-post epsilon can vary a lot, e.g., when the accuracy gap between the best and second-best mechanism is tiny but their base epsilons differ a lot.    \n3)\tThe bound introduces several new hyperparameters ($\\ell_i’s $). These can be set equal, and upper bounded, but it’s not clear how to choose these in general.", "was_revised": true, "final_justification": "My issues have been resolved. \n\nUpon acceptance, authors should consider including their responses for my questions above. \nThis is a strong paper and meets NeurlPS bar, IMO.", "rebuttal": "Thank you for your detailed review and suggestions.\n\n\n# Response to Weaknesses\n\n\nNote that $\\\\ell_i$’s are *not* data dependent so they can be set entirely based on the $\\\\epsilon_i$’s values; i.e., one may choose $\\\\ell_i$ that minimizes $(2 + \\\\ell_i) \\\\epsilon_i + (1 + \\\\ell_i) \\epsilon’ + \\\\frac{\\\\sum_{j \\neq i} e^{-\\\\epsilon_j (1 + \\\\alpha  \\\\ell_i)}}{\\alpha - 1}$ (note that it doesn’t depend on $\\\\ell_j$ for $j \\\\neq i$ or the dataset).\n\n\n# Response to Questions\n\n\n1. Indeed, one of the strengths of our algorithm is that it does not need an a priori threshold since it simply outputs the best response with the highest “score” (based on the ordering of $\\\\mathcal{O}$ that we can choose). However, if one insists on using a threshold, then our algorithm can be easily adapted: We can assign every output below the threshold with “score” of $-\\\\infty$ (and every output above the threshold a positive score)  and add another 0-DP mechanism $\\\\mathcal{M}_{d + 1}$ that always output a dummy output with score 0. In this way, we ensure that we only output an element that exceeds the threshold.\n2. We apologize for the confusing phrases that we used. You are correct that in our Algorithm 1 description each mechanism is run exactly once. However, as explained in the subsequent paragraphs (Line 178-192), we can run each mechanism more than once by a simple “repetition trick” where we duplicate each mechanism multiple times in the input sequence. Note that, in terms of privacy, there is no cost to such repetition trick since the guarantee in Theorem 8 does *not* depend on the sequence length."}, {"review_id": "CVWPHiGAIT", "reviewer": "Reviewer_AAhR", "summary": "The paper presents a novel framework for hyperparameter tuning in differential privacy (DP) with a utility-first perspective, building on the ex-post DP concept introduced by Wu et al. (2019). It proposes a general algorithm that supports any sequence of private estimators, achieving ex-post DP and Rényi DP guarantees with at most a doubling of the privacy budget. The algorithm extends to complex mechanisms like DP-SGD, unlike prior work limited to Laplace or Gaussian noise. Additionally, the paper introduces a privacy filter for fully adaptive composition in ex-post Rényi DP and provides empirical evidence of superior performance in machine learning tasks, such as linear regression on Twitter data and classification on MNIST.", "questions": "1. Can the authors clarify or correct the inconsistency between Definition 2 and Definition 5 regarding the summation over the output set? \n2. Could the authors add a note near Algorithm 1 or in its description to highlight the unconventional use of the probability of failurefor the geometric distribution? This would prevent implementation errors and could improve the Clarity score to 3.\n3. Can the authors discuss the implications of the uniform $\\varepsilon' $ term in Theorem 8, which reduces the output-specific flexibility of ex-post DP? \n4. In Theorem 10, are the parameters $l_1, \\dots, l_d $ arbitrary, or do they require optimization? If optimization is not needed, would swapping the quantifier order improve clarity? \n5. Can the authors provide a better introduction or motivation for Section 4 to connect it to the paper’s main narrative?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The algorithm significantly generalizes prior work by Wu et al. (2019) and Liu and Talwar (2019), extending ex-post DP to arbitrary private estimators, including DP-SGD. \n- The proof of Theorem 8, which establishes ex-post pure-DP guarantees, is notably simple and leverages the Sparse Vector Technique. Its elementary nature enhances its accessibility and strengthens the theoretical contribution.\n- The experimental results in Section 5.2 demonstrate substantial improvements in machine learning tasks. \n\nWeaknesses\n- There is an inconsistency between Definition 2 (ex-post pure-DP) and Definition 5 (ex-post approximate-DP), as Definition 5 includes a summation over the output set, absent in Definition 2. \n- The parametrization of the geometric distribution in Algorithm 1, using the probability of failure instead of the conventional probability of success, is unconventional and not highlighted. Without reading the “Probability Notation” section, readers might implement the algorithm incorrectly.\n- Theorem 8 introduces a uniform additive term across all indices, which partially undermines the output-specific flexibility of ex-post DP, aligning it closer to ex-ante DP. This trade-off is not sufficiently discussed.\n- A typo in the proof of Theorem 8 (final line) omits the $\\varepsilon$-term and incorrectly uses $\\mathcal{A} $ instead of $\\mathcal{A}' $, which could compromise the proof’s integrity.\n- Section 4 is poorly introduced and feels disconnected from the rest of the paper, lacking a clear transition or motivation.\n- The general writing could be improved, with occasional unclear phrasing and lack of coherence in some sections, particularly Section 4.", "was_revised": true, "final_justification": "After reading the author’s response, I’ve decided to keep my positive rating of the article.", "rebuttal": "Thank you for your detailed review and suggestions.\n\n\n# Response to Weaknesses\n\n\n* Regarding the last expression of the proof of Theorem 8: We thank the reviewer for pointing this out. Indeed this is a typo and should be changed to $e^{\\\\epsilon_i + \\\\epsilon'} \\\\cdot \\\\mathcal{A}'(o, i)$. We have rechecked the proof and can confirm that, apart from this typo, the proof is correct.\n\n\n# Response to Questions\n\n\n1. We wish to remark that the two versions (with and without the sum) of the definitions are equivalent for pure-DP  (i.e., $\\\\delta = 0$). One direction (with the sum to without the sum) is obvious by taking $\\\\mathcal{O} = \\\\{o\\\\}$. The other direction can be seen by taking the sum of the inequality over all $o \\\\in \\\\mathcal{O}$. We also note that both versions are standard in DP literature; indeed the original DP paper (Dwork et al., 2006) has the definition of pure-DP without the sum, in a similar manner as our Definition 2.\n\n\n2. Thank you for pointing this out. We will make sure to change this and use $p$ as the success probability in the revised version.\n\n\n3. This term is actually not a problem since we can choose $\\\\epsilon’$ to be arbitrarily small, and thus the privacy overhead from this additive term can be made negligible. Note that, to retain similar utility after decreasing $\\\\epsilon’$, we can simply duplicate the mechanisms so that each mechanism is run multiple times (see Line 178-191); this would result in the same utility and lower privacy at the expense of computational cost. (Note that a similar tradeoff also occurs in ex-ante DP hyperparameter tuning algorithm of Papernot–Steinke; see their Corollary 3.)\n\n\n4. Note that $\\\\ell_i$’s are *not* data dependent so they can be set entirely based on the $\\\\epsilon_i$’s values; i.e., one may choose $\\\\ell_i$ that minimizes $(2 + \\\\ell_i) \\\\epsilon_i + (1 + \\\\ell_i) \\epsilon’ + \\\\frac{\\\\sum_{j \\neq i} e^{-\\\\epsilon_j (1 + \\\\alpha  \\\\ell_i)}}{\\alpha - 1}$ (note that it doesn’t depend on $\\\\ell_j$ for $j \\\\neq i$ or the dataset).\n\n\n5. As alluded to in the paragraph starting at line 92, privacy filter is the typical approach to convert ex-post guarantee into the standard ex-ante guarantee. Here one would have a target ex-ante privacy budget (denoted by $\\\\epsilon$ in Algorithm 2) and the privacy filter allows us to run multiple ex-post DP subroutines. At the end, the guarantee of the entire algorithm is *ex-ante*. In other words, this can be thought of as a “composition theorem” for privacy, except that it allows ex-post DP subroutines and yet yields the more traditional final ex-ante DP. Finally, we note that we focus on RDP in Section 4 since a natural privacy filter for e.g. pure-DP is already known (Lebensold et al., 2024)."}]

Author rebuttal:

Meta-review: The reviews agree that this is an interesting, useful and well-executed paper, and would be a useful addition to NeurIPS. Please revisit the discussion with the reviewers while preparing the camera ready version, and try to incorporate the promised changes (especially for the sections where the writing needs to be improved).
Decision: Accept (spotlight)