Attack-Aware Noise Calibration for Differential Privacy
Authors: Bogdan Kulynych
Juan Felipe Gomez
Georgios Kaissis
Flavio Calmon
Carmela Troncoso
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
DP-SGD
Primary area: privacy
TL;DR: Direct calibration of noise to attack risk increases utility of DP mechanisms at the same level of risk, compared to calibration of noise to a given level of epsilon.

Abstract: Differential privacy (DP) is a widely used approach for mitigating privacy risks when training machine learning models on sensitive data. DP mechanisms add noise during training to limit the risk of information leakage. The scale of the added noise is critical, as it determines the trade-off between privacy and utility. The standard practice is to select the noise scale to satisfy a given privacy budget ε. This privacy budget is in turn interpreted in terms of operational attack risks, such as accuracy, sensitivity, and specificity of inference attacks aimed to recover
information about the training data records. We show that first calibrating the noise scale to a privacy budget ε, and then translating ε to attack risk leads to overly conservative risk assessments and unnecessarily low utility. Instead, we propose methods to directly calibrate the noise scale to a desired attack risk level, bypassing the step of choosing ε. For a given notion of attack risk, our approach significantly
decreases noise scale, leading to increased utility at the same level of privacy. We empirically demonstrate that calibrating noise to attack sensitivity/specificity, rather than ε, when training privacy-preserving ML models substantially improves model accuracy for the same risk level. Our work provides a principled and practical way to improve the utility of privacy-preserving ML without compromising on privacy.

Attack-Aware Noise Calibration for Differential Privacy
Bogdan Kulynych"
Juan Felipe Gomez"
Lausanne University Hospital (CHUV)
Harvard University
Georgios Kaissis
Flavio du Pin Calmon Harvard University
Carmela Troncoso EPFL
Technical University Munich
Abstract
Differential privacy (DP) is widely used approach for mitigating privacy risks when training machine learning models on sensitive data. DP mechanisms add noise during training to limit the risk of information leakage. The scale of the added noise is critical, as it determines the trade-off between privacy and utility. The standard practice to select the noise scale to satisfy a given privacy budget e. This privacy budget is in turn interpreted in terms of operational attack risks, such as accuracy, sensitivity, and specificity of inference attacks aimed recover information about the training data records. We show that first calibrating the noise scale to a privacy budget E, and then translating & to attack risk leads overly conservative risk assessments and unnecessarily low utility. Instead, we propose methods directly calibrate the noise scale to desired attack risk level, bypassing the step of choosing For given notion of attack risk, our approach significantly decreases noise scale, leading to increased utility at the same level privacy. We empirically demonstrate that calibrating noise attack sensitivity/speecfiiity. rather than E, when training accuracy for the same risk level. Our work provides principled and practical way to improve the utility of privacy-preserving ML without compromising on privacy.
ML models substantially improves model
Introduction
Machine learning and statistical models can leak information about individuals in their training data, which can recovered by membership inference, attribute inference, and reconstruction attacks (Fredrikson et al., 2015; Shokri et al., 2017: Yeom et al., 2018; Balle et al., 2022). The most common defenses against these attacks are based on differential privacy (DP) (Dwork et al., 2014). Differential privacy introduces noise to either the data, the training algorithm, or the model parameters (Chaudhuri et al., 2011). This noise provably limits the adversary's ability to run successful attacks at the cost of reducing the utility of the model.
In DP, the parameters and ó control the privacy-utility trade-off. These parameters determine the scale (e.g., variance) of the noise added during training: Smaller values of these parameters correspond larger noise. Larger noise provides stronger privacy guarantees but reduces the utility of the trained model. Typically, is set to a small fixed value (usually between 10 88 and 10 10-5), leaving the primary tunable parameter. Without additional analyses, the values of parameters (c, ö) alone do not provide a tangible and intuitive operational notion of privacy risk (Nanayakkara al., 2023). This begs the question: how should practitioners, regulators, and data subjects decide on acceptable values of and and calibrate the noise scale to achieve desired level of protection?
"Contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Standard Calibration
Our Method
DP Parameters
Noise
Attack Risk
Attack (TPR), o (FPR)
Noise Scale
(TPP)), (PPR)
Direct calibration of noise to attack risk increases utility compared to the standard calibration at the same level risk:
GPT-2 SST-2 (lext sentiment classificatior)
0.05
Altack riak (TPR,
Method
Standard cslibration Attack risk calibration
01.3
0.2
0.00
accuracy
CNN CIFAR diassttication)
1.0
ABtakk (884 (TPR
Method
Attack risk calibration
Task accuracy
Test accuracy (X-axis) of privately finetuned GPT-2 SST-2 text sentiment classification dataset (top) and a convolutional neural network on CIFAR-10 image classification dataset (bottom). The DP noise calibrated to guarantee most certain level of privacy attack sensitivity (y-axis) three possible attack false-positive rates E {0.01, 0.05, 0.1 See Section 4 for details.
Figure 1:
A standard way of assigning operational meaning to DP parameters is mapping them to attack risks. One common approach is computing attacker's posterior belief (or equivalently, accuracy or advantage) of membership inference attacks, that concrete values of (z, 6) allow (Wood et al., 2018). An alternative is to compute the trade-off between sensitivity and specificity of feasible membership inference attacks (Wasserman and Zhou, 2010; Kairouz al., 2015; Dong et al., 2022), which was recently shown to also be directly related to success of record reconstruction attacks (Hayes et al., 2024; Kaissis al., 2023a). Such approaches map (c, 8) to quantifiable level of risk for individuals whose data is present in the dataset. Studies have shown that such risk-based measures are the most useful way interpret the guarantees afforded by DP for practitioners and data subjects (Cummings et al., 2021; ; Franzen et al., 2022: Nanayakkara et al., 2023).
In this work, we show that directly calibrating the level of noise satisfy a given level of attack risk, as opposed to satisfying a certain E, enables a significant increase in utility (see Figure 1). We enable this direct calibration to attack risk by working under f-D (Dong et al., 2022), hypothesis testing interpretation of DP. In particular, we extend the tight privacy analysis method by Doroshenko al. (2022) to directly estimate operational privacy risk notions in f-DP. Then, use extended algorithm to directly calibrate the level of noise to satisfy given level of attack risk. Concretely, our contributions
1. We provide efficient methods for calibrating noise to (a) maximum accuracy (equivalently, advantage), (b) sensitivity and specificity of membership inference attacks, in any DP mechanism, including DP-SGD (Abadi al., 2016) with arbitrarily many steps.
2. We empirically show that calibration methods reduce the required noise scale for given level of privacy risk, up to 2 as compared to standard methods for choosing DP parameters. In private language modeling task with GPT-2 (Radford et al., 2019), we demonstrate that the decrease in noise can translate to 18 p.p. gain in classification accuracy.
3. We demonstrate that relying membership inference accuracy as an interpretation of privacy risk, as common practice, can increase attack power in privacy-critical regimes, and that calibration for sensitivity and specificity does not suffer from this drawback.

---

4. We provide Python package which implements our algorithms for analyzing DP mecha- nisms terms of the interpretable f-PP guarantees, and calibrating operational risks:
Ultimately, we advocate for practitioners to calibrate the noise level in learning algorithms sensitivity and specificity constraint under /-DP as outlined in Section 3.2.
machine
Related Work. Prior work has studied methods for communicating the privacy guarantees afforded by differential privacy (Nanayakkara et al., 2023, 2022; Franzen et al., 2022; Mehner et al., 2021; Wood et al., 2018), and introduced various principled methods for choosing the privacy parameters (Abowd and Schmutte, 2015; Nissim et al., 2014; Hsu et al., 2014). Unlike assume that the mechanisms are calibrated to a given e privacy budget parameter, and do not aim to directly set the privacy guarantees in terms of operational notions of privacy risk.
approach, these works
Cherubin et al. (2024); Ghazi and Issa (2023); Izzo et al. (2024); Mahloujifar et al. (2022) use variants of DP that directly limit the advantage of membership inference attacks. We show that calibrating noise to a given level of advantage can increase privacy risk in security-critical regimes and provide methods that mitigate this issue. Leemann et al. (2024) provide methods for evaluating the success of membership inference attacks under a weaker threat model than in DP. Unlike their work, we preserve the standard strong threat model in differential privacy but set and report the privacy guarantees in terms of an operational notion of risk under f-DP as opposed to the & parameter.
Problem Statement
2.1 Preliminaries
Setup and notation. Let ID" denote the set of all datasets of size n over a space D, and let S ~ S denote neighboring relation, e.g. S, that differ by one datapoint. We study randomized algorithms (mechanisms) (S) that take as input a dataset 5 E 2D, and output the result a computation, e.g.. statistical queries or ML. model. We denote the output domain of the mechanism by O. For ease of presentation, we mainly consider randomized mechanisms that are parameterized by a single noise parameter w E S2 but our results extend mechanisms with multiple parameters. For example, in the Gaussian mechanism (Dwork et al., 2014), (5)) = ((S) + Z. where Z ~ (0, o²) and ((S) is non-private statistical algorithm, the parameter is w a with Ω R22 We denote a parameterized mechanism by (S). We summarize the notation in Table in the Appendix.
Differential Privacy. For any 7 0, define the hockey-stick divergence from distribution P to Q over a domain O by
D, Q) A sup Q(E) PPEE
E
where the supremum is taken over all measurable sets E' C O. We define differential privacy (DP) (Dwork al., 2006) as follows:
Definition 2.1. A mechanism (-) satisfies ()P iff sup De (M(S) M())) 88
Lower values of & and mean more privacy which in turn requires more noise, and vice versa. In the rest of the paper assume that a larger value of the parameter w E Ω for Ω C R, e.g., standard deviation of Gaussian noise w = a in the Gaussian mechanism, means that the mechanism (.) is more noisy, which translates into higher level of privacy (smaller e, 8), but lower utility.
Most DP algorithms satisfy a collection of (e, 8D-DP guarantees. We define the privacy profile (Balle and Wang, 2018), or privacy curve (Gopi et al., 2021; Alghamdi et al., 2023) of mechanism as:
Definition 2.2. A parameterized mechanism Ma (-) has a privacy profile en [0, 1] + R if for every 5 E [0. 1], (.) is (#(6), DD-
We refer to the function (E), defined analogously, also as the privacy profile.
DP-SGD. A common algorithm for training neural networks with DP guarantees is DP-SGD (Abadi et al., 2016). The basic building block of DP-SGD is the subsumpled Gaussian mechanism, defined as (S) (PooissonSample, S) + Z, where Z ~ NN(0, A3 o² Iz), and PoissonSample, is procedure which subsamples dataset such that every record has the same probability p E (0,1) 1) to be in the subsample. SGD, parameterized by p, a, and T > 1, is repeated application of the
3

---

.... (S), where (.) is a single step of gradient descent with per-record gradient clipping to Ag Euclidean norm. In line with standard practice (Ponomareva et al., 2023), we regard all parameters but as fixed, thus w a.
subsampled Gaussian mechanism: M()) a M
Privacy profiles for mechanisms such DP-SGD are computed via numerical algorithms called accountants (see, c.g., Abadi et al., 2016; Gopi et al., 2021; Doroshenko et al., 2022; Alghamdi al., 2023). These algorithms compute the achievable privacy profile to accuracy nearly matching the lower bound of privacy audit where the adversary is freee to choose the entire (pathological or realistic) training dataset (Nasr et al., 2021, 2023). Given these results, we regard the analyses of these accountants as tight, and use them for calibration to a particular (E, 6)-DP constraint.
Standard Calibration. The procedure of choosing the parameter w E Ω to satisfy given level of privacy is called calibration. In standard calibration, one chooses w given a target DP guarantee e* and an accountant that supplies privacy profile (6) for any noise parameter 92 ensure that Ms(s) satisfies (e", 6
min w s.t. 6w())) E6, WE
with 5* set by convention to 8 = 1/e.,, where n is the dataset size, and c > (see, e.g., Ponomareva et al., 2023; Near et al., 2023). The parameter e* is also commonly chosen by convention between 2 and 10 for crivacy-perevveriie Eq. (2) and the rest the paper we denote by" the target value of privacy risk.
ML algorithms with practical utility (Ponomareva et al., 2023). In
After calibration, the (e, parameters are often mapped some operational notation of privacy attack risk for interpretability. In the next section, we introduce the hypothesis testing framework of DP. f-DP, and the notions of risk that (e, parameters are often mapped to. In contrast standard calibration, in Section 2.3, we calibrate w to directly minimize these privacy risks.
2.2 Operational Privacy Risks
We can interpret differential privacy through the lens of membership inference attacks (MIAs) in the so-called
model (see, e.g., Nasr et al., 2021). In this framework, the adversary aims to determine whether a given output 0 θ came from (S) some target example & E D. The adversary has access to the mechanism M(). the dataset S, and the target example E ID. Such an attack is equivalent to a binary hypothesis test (Wasserman and Zhou, 2010; Kairouz et al., 2015; Dong et al., 2022):
MS'),, where S' = S U {2} for
Ho ~ (S), H1 : M(S).
where the MIA is modelled as a test Φ θ + [0, 1] that maps a given mechanism output 0 to the probability of the null hypothesis Hg being rejected. We can analyze this hypothesis test through the trade-off between the achievable false positive rate (FPR) as - (s) [o] and false negative rate (FNR) 3g - 1 1- [or(s)) where the expectations are taken over the coin flips in the mechanism. 3 Dong et al. (2022) formalize the trade-off function and define f-DP as follows:
Definition 2.3. A trade-off function funnciooo T'M (S), (S'))) : [0, 1] + [0, 1] outputs the FNR of the most powerful attack at any given level E [0;
inf de e-100.]
{3o ass S a}
See Figure 5 in the Appendix for an illustration.
Definition 2.4. A mechanism (-) satisfies f-DP, where f is the trade-off curve for some other mechanism, if for all a E [0, 1J. we have infs=s/ (S), (S)) f(a).
Next, we state the equivalence between (), guarantees and f-DP guarantees. Proposition 2.1 (Dong et al. (2022)). Ifa mechanism M() is (e, 6)DDP, then is J-DP with [(a) max (0, 8 - Ea, e = (1 - 8 -a)}.
(5)
Moreover, a mechanism M(-) satisfies (E(8), for all 8 E [0, 1] isf it is J-DP with
f(a)= = sup max (0, 1 1 (() a, e =()) (1 8 - a)))
(6)
6E[U.1]
Wee use add relation in this exposition, i.c., S ~ S' S' = S SU (z), but our results hold for any relation.
Note that sensitivity (IPR) is 1 3 and specificity (TNR) is a.

---

We overview three particular notions of attack risk: udvantage/accuracy of MIAs, FPR/FNR of MIAs, and reconstruction robustness. These risks can be thought of summary statisties of the f curve.
Advantage/Accuracy Wood et al. (2018) proposed to measure the attack risk as the maximum achievable attack accuracy. To avoid confusion with task accuracy, we use advantage over random guessing, which is the difference between the attack TPR 1 Ss and FNR otg
sup sup S-S1 Φ: (-1
B. as.
The advantage 77 is linear transformation of the maximum attack accuracy sup 1/2- (1- BB) + 1/2- (1 - as)), where supremum is over S = S' and o e + [o, 1]. Moreover, yj can be obtained from a fixed point a² = faa) of the f curve as 1 2a', and it bounded given an (e, 6DD guarantee:
Proposition 2.2 (Kairouz et al. (2015)). If mechanism M(-) is (c,6)-DP, then we have:
e- 2
n - +1+1
(8)
FPR/ENR Risk. Recent work (Carlini et al., 2022; Rezaei and Liu, 2021) has argued that MIAs a relevant threat only when the attack true positive rate 1 33 is high at low enough ogg- As concrete notion of risk, we thus consider minimum level of attack FNR 3 within an FPR region [0, a"), where a" a low value. This approach is similar the statistically significant p-values often used in the sciences, Following the scientific standards and Carlini et al. (2022), we consider a* E {0.01, 0.05, 0.1).
Reconstruction Robustness. Another privacy threat is the reconstruction of training data records (see, e.g., Balle et al., 2022). Denoting by R(0; z) attack that aims reconstruct 2, its success probability can be formalized as p é Pr[e[2, R(0; z)) I 7 over ~ (SU())) 2 ~ i for some loss function 8: ID2 + R and prior æ. Kaissis et al. (2023a) showed that MIA error rates bound reconstruction success as p < ((s,) for an appropriate choice of Ky. Therefore, the FPR/ENR trade-off curve also be thought notion of robustness to reconstruction attacks.
2.3 Our Objective: Attack-Aware Noise Calibration
The standard practice DP is to calibrate the noise scale w mechanism (-) to some target
(s+ "D*DD guarantee with s* from a recommended range, e.g., e* E [2, 10). and 6* fixed to 6* < 1/n, as in Eq. (2). Then, the privacy guarantees provided by the chosen (=*.8*) are obtained by mapping these values to bounds sensitivity and specificity (by Proposition 2.1) or advantage (by Proposition 2.2) of membership inference attacks. In this work, we show that the goal is to provide operational and interpretable guarantee such attack advantage FPR/ENR, this approach leads to unnecessarily pessimistic noise requirements and a deterioration in utility due to the intermediate step of setting (=*;"*). We show it is possible to skip this intermediate step by using the hypothesis-testing interpretation of DP to directly calibrate noise to operational notions of privacy risk. In practice, this means replacing the constraint in Eq. (2) with an operational notion of risk:
min w s.t. risk. S threshold".
WEQ
Solving this optimization problem requires two components. First, way to optimize w given method to compute risk.. As we assume that risk is monotonic in w, Eq. (9) can be solved via binary search (see, c.g., Paszke et al., 2019) using calls to the risk, function to an arbitrary precision. Second, we need way to compute risk. for any value w. In the next section, we provide efficient methods for doing so for general DP mechanisms, including composed mechanisms such as DP-SGD, by extending the tight privacy analysis from Doroshenko et al. (2022) to computing f-DP. Having these methods, we instantiate Eq. (9) for the notions of risks introduced Section 2.2.
3 Numeric Calibration to Attack Risks
In this section, we provide methods for calibrating DP mechanisms to the notions of privacy risk in Section 2.2. As first step, we introduce the core technical building blocks of our calibration method: methods for evaluating advantage The and the trade-off curve (ax for a given value of w.
Wood et al. (2018) used posterior belief. which is equivalent accuracy under uniform prior.
5

---

Dominating Pairs and PLRVs. We make use of two concepts, originally developed in the context of computing tight privacy profiles under composition: dominating pairs (Zhu al., 2022a) and privacy loss random variables (PLRV) (Dwork and Rothblum, 2016).
Definition 3.1. We say that a pair of distributions (P, Q) is a dominating pair for a mechanism M.) if for every E IR, we have sups=s' De (M()) M(S")) Der (P Q).
Importantly, a dominating pair also provides a lower bound on the trade-oft off curve of a mechanism: Proposition 3.1. If (P. Q) is dominating pair for a mechanism M, then for a E [0, 1),
inf T(M(S). (() 2 ()). S-
(10)
The proofs of this and all the following statements are in Appendix E. Proposition 3.1 implics that mechanism M-) is f-DP with f = T(P, Q). Next, we introduce privacy loss random variables, which provide a natural parameterization of the curve T(P: Q)-
Definition 3.2. Suppose that mechanism (-)) has a discrete-valued dominating pair (P, Q). Then, we define the privacy loss random variables (PLRVs) (X,Y) Y) as Y - log ((o)/P(o), with ~ Q, and log Q Q(o)) ((oo)) with of ~ P.
X f
We can now state the result which serves as a main building block for our calibration algorithms, and forms the main theoretical contribution of our work.
Theorem 3.3 (Accounting for advantage and f-DP with PLRVs). Suppose that a mechanism M() has discrete-valued dominating pair (P, Q) with associated PLRVs (X,Y) Y). The attack advantage n, for this mechanism is bounded:
11 S Pr[y > Prppr(X oj.
(11)
Moreover, for any T E R U foo, )c) and y [0, 1). define
(T,7) Pr[y <| Pr|Y T].
(12)
For any level [0. 1). choosing (1 a) -quantile of X and --Pr[X>r] P
guarantees that
To show this, at level a in terms the threshold I on the Seyman-Pearse test statistic and the probability y of guessing when the test statistic exactly equals the threshold. See Appendix E.2 for the detailed proof.
the Neyman Pearssn lemma explicitly parameterize the most powerful attack
We remark that similar results for the trade-off curve appear in (Zhu et al., 2022a) without the y terms, as Zhu et al. assume continuous PLRVs (X, Y). In our work, we rely on the technique due to Doroshenko al. (2022), summarized in Appendix D, which discretizes continuous mechanisms such as the subsampled Gaussian in DP-SGD, and provides dominating pair that is discrete and finitely supported over an evenly spaced grid. As the dominating pairs are discrete, the y terms are non-zero, thus are necessary to fully reconstruct the trade-off curve.
3.1 Calibration to Advantage
First, we show how to instantiate Eq. (9) to calibrate noise to a target advantage 1y" [0, 1]. Let ma denote the advantage of the mechanism (.) as defined in Eq. (7):
min w WEit
s.t. Th Sn"
(13)
Given the PLRVs (X_,, Y=), we can obtain a substantially tighter bound than converting (c, 5) guarantees using Proposition 2.2 under standard calibration. Specifically, Theorem 3.3 provides the following way to solve the problem:
min w s.t. Pr[Y.. > 0J Pr[X 0, S 17" well
(14)
We call this approach advantage calibration, and show how to practically implement it in Algorithms and 4 in the Appendix. Given method for obtaining valid PLRVs X.,, Y., for any such as the one by Doroshenko et al. (2022), advantage calibration is guaranteed to ensure bounded advantage, which follows by combining Proposition 3.1 and Theorem 3.3:

---

Method Standard calibaaiion
Method
Standard celibration
Noise scale, e
Advantage caliratton
Advantage calibration
Attack FNR,
0.5
10F
0.00
11.15
11.20
0.5
Attack advantage.
Atlack FPR,
(a) Calibrating noise to attack advantage signifi- cantly reduces the required noise scale compared to the standard approach. y axis is logarithmic.
(b) Optimal calibration for advantage comes with a pitfall: it allows for A,3 higher attack power in the low FPR regime compared standard calibration.
Figure 2: Benefits and pitfalls of advantage calibration.
Proposition 3.2.
Given PLRVs (Xwi Yw) of discrete-valued dominating pair of a mechanism (t), choosing w" using Eq. (14) ensures nh- =1
Utility Benefits. We demonstrate how calibration for a given level of attack advantage can increase utility. As mechanism to calibrate, we consider DP-SGD with p 0.001 subsampling rate, T' = 10,000 iterations, and assume that 8* = 10 Our goal is to compare the noise scale o obtained via advantage calibration to the standard approach.
As a baseline, we choose a using standard calibration in Eq. (2), and convert the resulting (s, 6) guarantees to advantage using Proposition 2.2. We detail this procedure in Algorithm 2 in the Appendix. We consider target values of advantage 17" E [0.01, 0.25]. As we show in Figure 2a, our direct calibration procedure enables to reduce the noise scale by up to 3.5x.
Pitfalls of Calibrating for Advantage. Calibration to a given level of membership advantage is compelling idea due to the decrease in noise required to achieve better utility at the same level of risk as with the standard approach. Despite this increase in utility, we caution that this approach comes with a deterioration of privacy guarantees other than maximum advantage compared to standard calibration. Concretely, it allows for increased altack TPR in the privacy-critical regime of low attack FPR (see Section 2.2). The next result quantifies this pitfall:
Proposition 3.3 (Cost of advantage calibration). Fix dataset size 1, and a target level of attack advantage 17" (5*, 1), where 8* //en for some >> 1. For any 0
-n there exists
DP mechanism for which the gap in FNR fstandard(()) (a:) obtained with standard calibration for E* that ensures 1) S 17,, and FNR (a) obtained with advantage calibration is lower bounded:
AB(a)= fstandard (ad 2 n² 8 + 2a
(15)
17"
For example, if we aim to calibrate a mechanism to most 17" 0.5 (or, 75% attack accuracy), we could potentially increase attack sensitivity by (B(aa) = 30 p.p. at FPR a = 0.1 compared to standard calibration with 8* 10-3 3 (see the illustration in Figure 2b). Note that the difference AB in Proposition 3.3 is an overestimate in practice: the increase in attack sensitivity can be significantly lower for mechanisms such as the Gaussian mechanism (see Figure 6 in the Appendix).
3.2 Safer Choice: Calibration to FNR within Given FPR Region
In this section, we show how to calibrate the noise in any practical DP mechanism to a given minimum
level of attack FNR 8* within an FPR region E [0, a*), which enables to avoid the pitfalls of advantage calibration. We base this notion of risk off the previous work (Carlini et al., 2022: Rezaei and Liu, 2021) which argued that MIAs are a relevant threat only when the achievable TPR 1 8 high at low FPR a. We instantiate the calibration problem Eq. (9) as follows, assuming M. (-) satisfies fo (a)-DP:
min w s.t. inf
(a) 2 8 OSaSa"
(16)
we
To solve Eq. (16), we begin by showing that such calibration is in fact equivalent to requiring a given level of attack FNR 3* and FPR a*
7

---

Algorithm 1 Construct the trade-off curve using discrete privacy loss random variables (X, Y)
Require: PMF Pr X x. over grid {I1, "2,-,
-00..------00 26 with #1 < x2 < ... <, 3h
Require: PMF Pr[y, = y, over grid {3i, .2..... 30 with y1 < 92 < <
I: procedure COMPUTEBETA(W: a Xws Yw)
2: 8 + min E {0.1..... k} Pr[X > xi. S ) where xo _ 00
3: Y a" D'-Pr[Xu30]]
4: return fa(a*) = Pr|Y, S x 7 Pr[Y = 2z1
Proposition 3.4. For any o² 2 0, 3 2 such that a* + 3" S 1, and any f-DP mechanism M()::
inf f(a) 2 3r iff f(aa((()))))))))))) 3 0SaSa*
(17)
This follows directly by monotonicity of the trade-off function f (Dong 2022). The optimization problem becomes:
min w s.t. (a 2 6**
(18)
WE
Unlike advantage calibration to 17",, the approach in Eq. (18) limits the adversary's 's capabilities without increasing the risk in the privacy-crine critccclritical low-FPR regime, as we can explicitly control the acceptable attack sensitivity for a given low FPR.
To obtain (a), we use the PLRVs Xw,, Y., along with Theorem 3.3 to compute f = Q)) (see Algorithm 1), and solve Eq. (18) using binary search over Ω. We provide the precise procedure in Algorithm 6 in the Appendix. This approach guarantees the desired level of risk:
Proposition 3.5. Given PLRVs (Xw; Yw) of a discrete-valued dominating pair of a mechanism M.).), choosing w' using Eq. (18) and Algorithm I to compute fa() ensures fw- (a*) 8*.
3.3 Other Approaches to Trade-Off Curve Accounting
In this section, we first contextualize the proposed method within existing work. Then, we discuss settings in which alternatives to PLRV-based procedures could be more suitable.
Benefits of PLRV-based Trade-Off Curve Accounting. Computational efficiency is important when estimating (a), the calibration problem requires evaluating this function multiple times for different values of w as part of binary search. Algorithm computes fw for single w in R 500ms, enabling fast calibration, e.g., in minute for DP-SGD with T 10,000 steps on commodity hardware (see Appendix H). Existing methods for estimating (a on the contrary, either provide weaker guarantees than Proposition 3.5 or substantially less efficient. In particular, Dong et al. (2022) introduced fdGDP, an asymptotic expression for (a) as T - 00, that overestimates privacy (Gopi al., 2021), and thus leads to mechanisms that do not satisfy the desired level of attack resilience when calibrating to it. Nasr et al. (2023); Zheng et al. (2020) introduced a discretization- based approach approximate (a: (discussed next) that can be orders of magnitude less efficient than the direct estimation in Algorithm 1, c.g., 1-6 minutes (ss 100-700x slower) for single evaluation of f (a) in the same setting as before, depending on the coarseness of discretization.
Calibration using Black-Box Accountants. Most DP mechanisms are accompanied by (c, 8DDDP accountants, i.e., methods compute their privacy profile (.) (e). Black-box access to these accountants enables to estimate nu and fa) In particular, Proposition 2.2 tells us that (0, 6)-DP mechanisms bound advantage as 77 I 6. Thus, advantage calibration
also be performed with
any & accountant by calibrating noise to ensure e (17") = 0. Estimating fa (a). as mentioned previously, is less straightforward. Existing numeric approaches (Nasr al., 2023; Zheng et al., 2020) are equivalent to approximating Eq. (6) on a discrete grid over 5 E -,,,,..,,,, 5.). This requires
calls to the accountant s (6), thus quickly becomes inefficient for estimating (a) to high precision. We provide a detailed discussion of such black-box box approaches in Appendix A.
Calibration of Mechanisms with Known Trade-Ofr Curves. An important feature of our calibration methods is that they enable calibration of mechanisms whose privacy profile is unknown
'I practice, we need to additionally symmetrize the trade-off curve due to the implementation details of the add/remove neighborhood relation in the Doroshenko al. (2022) accountant. See Appendix F.
8

---

Attack FPR, 0.01
Attack FPR, 0.05
Attack FPR, 0.1
1.0
No scale.
0.5
Method
Standard calibration FPP/FPR calirraiion
0.0
0.4
0.1
0.3 Attack TPR.
0.2
3.4
0.5
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.5
01.
Attack TPR.
Atlack TPR.
Figure 3: Calibration to attack TPR (i.e., 1-FNR) significantly reduces the noise scale in low FPR
regimes. Unlike calibration for attack advantage, this approach does not come with deterioration of privacy for low FPR, as it directly targets this regime.
1.0
accuracy
accuracy
accuracy -
18.
Attack FNR
Method
(6. SP
0.6
Ours (Algorithm 1)
0.0
0.2
11.4
0.5 0.5
1.000
0.2
0L4
01.5
1,00.0
01.2
0.44
11.55
Attack FPR, or
Attack FPR,
Attack FPR.
Figure 4: Trade-off curves obtained via our method in Algorithm provide significantly tighter analysis of the attack risks, compared to the standard method of interpreting the privacy risk for given (e, 8) with fixed 5 < 1/m via Eq. (5). The trade-off curves are shown for three runs of DP-SGD with different noise multipliers in the language modeling experiment with GPT-2. The dotted line shows the trade-off curve which corresponds to perfect privacy.
in the exact form, e.g., DP-SGD for T 1. Simpler mechanisms, such as the Gaussian mechanism, which are used for simpler statistical analyses, e.g., private mean estimation, admit exact analytical solutions to the calibration problems Eqs. (13) and (18). Appendix G. we provide such solutions for the standard Gaussian mechanism, which enable efficient calibration without needing Algorithm 1.
4 Experiments
In this section, empirically evaluate the utility improvement of calibration method traditional approaches. We do so in simulations as well as in realistic applications of DP-SGD, In Appendix H, we also evaluate the utility gain when performing simpler statistical analyses.
First, we demonstrate the noise reduction when calibrating the DP-SGD algorithm for given error rates using the setup in Section 3.1. We fix three low FPR values: a* f0.01, 0.05, 0.1). and vary maximum attack sensitivity 1- 8" from 0.1 to 0.5 in each FPR regime. We show the results in Figure 3. We observe significant decrease in the noise scale for all values. Although the decrease is smaller than with calibration for advantage (see Figure 2a), calibrating directly for risk in the low FPR regime avoids the pitfall of advantage calibration: inadvertently increasing risk in this regime.
Simulations.
Language Modeling and Image Classification. We showed that FPR/FNR calibration enables to significantly reduce the noise scale. Next, study how much of this reduction in noise translates into actual utility improvement in downstream applications. We evaluate our method for calibrating noise in private deep learning two tasks: text sentiment classification using the SST-2 dataset (Socher et al., 2013), and image classification using the CIFAR-10 dataset (Krizhevsky et al., 2009).
For sentiment classification, we fine-tune GPT-2 (small) (Radford et al., 2019) using DP version of LoRA (Yu et al., 2021). For image classification, we follow the approach of Tramer and Boneh (2021) of training convolutional neural network on top of ScatterNet features (Oyallon and Mallat, 2015) with DP-SGD (Abadi al., 2016). See additional details in Appendix H. For each setting, by varying the noise scale, obtain several models at different levels of privacy. For each of the models

---

we compute the guarantees in terms of TPR 1 1-3 3 at three fixed levels of FPR a* E {0.01, 0.05, 0.1} that would be obtained under standard calibration, and using our Algorithm 1.
Figure shows that FPR/ENR calibration significantly increases task accuracy (a notion of utility; not to confuse with attack accuracy, notion of privacy risk) at the same level of a". For instance, for GPT-2, we see the accuracy increase of 18.3 p.p. at the same level of privacy risk (top leftmost plot). To illustrate the reasons behind such large difference between the methods, in Figure 4, we show the trade-off' curves obtained with our Algorithm I, and with the standard method of deriving the FPR/ENR curve from a single (e, 8) pair for a fixed 1/n via Eq. (5). We can see that the latter approach drastically overestimates the attack risks, which translates to significantly higher noise and lower task accuracy when calibrating with standard calibration.
for all values of
5 Concluding Remarks
In this work, we proposed novel methods for calibrating noise in differentially private learning targeting given level of operational privacy risk: advantage and FPR/FNR of membership infer- ence attacks. We introduced an accounting algorithm which directly and tightly estimates privacy guarantees in terms of f-DP, which characterizes these operational risks. Using simulations and end-to-end experiments on common use cases, we showed that our attack-aware noise calibration significantly decreases the required level of noise compared to the standard approach at the same level of operational risk. In the case of calibration for advantage, we also showed that the noise decrease could be harmful as it could allow for increased attack success in the low FPR regime compared to the standard approach, whereas calibration for a given level of FPR/ENR mitigates this issue. Next, we discuss limitations and possible directions for future work.
Choice of Target FPR/ENR. We leave open the question on how to choose the target FPR a² and FNR 8*, e.g.. whether standard significance levels in sciences such as a = 0.05 are compatible with data protection regulation and norms. Further work is needed to develop concrete guidance on the choice of target FPR and FNR informed by legal and practical constraints.
Catastrophic Failures. It is possible to construct pathological DP mechanisms which admit catastrophic failures (see, e.g., Ponomareva et al., 2023), i.e., mechanisms which allow non-trivial attack TPR FPR a = 0 so that their trade-off curve is such that (S), (0) < for some S ~ S". A classical example in the context of private data release is a mechanism that releases a data record the clear with probability 8 > 0, in which case we have (M M (O) = 1 8. See the proof of Proposition 3.3 in Appendix E for concrete construction. In the case that such a pathological mechanism used in practice, one should use standard calibration to (c, with 5 < 1/2 to directly limit the chance of catastrophic failures. Fortunately, practical mechanisms such as DP-SGD do not admit catastrophic failures, as they ensure T(M M (O)) = 1.
Tight Bounds for Privacy Auditing. Multiple prior works on auditing the privacy properties of ML algorithms (Nasr al., 2021; Liu et al., 2021: Jayaraman and Evans, 2019; Erlingsson al., 2019) used conversions between (s, 5) and operational risks like in Proposition 2.1. which we have shown to significantly overestimate the actual risks. Beyond calibrating noise, our methods provide bounds on attack success rates for audits in a more precise and computationally efficient way than a recent similar approach by Nasr et al. (2023).
Accounting in the Relaxed Threat Models. Although we have focused on DP, our methods apply to any notion of privacy that is also formalized hypothesis test. In particular, our method can be used as is to compute privacy guarantees of DP-SGD in a relaxed threat model (RTM) proposed by Kaissis et al. (2023b). Previously, there was no efficient method for accounting in the RTM.
Applications Beyond Privacy. Our method can be applied to ensure provable generalization guarantees in deep learning. Indeed, prior work has shown that advantage 7) bounds generalization gaps of ML models (Kulynych et al., 2022a,b). Thus, even though advantage calibration can exacerbate certain risks, it can be useful tool for ensuring a desired level of generalization in models that usually do not come with non-vacuous generalization guarantees, e.g., deep neural networks.
Acknowledgements
The authors would like to thank Priyanka Nanayakkara for the helpful suggestions.
10

---

References
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016.
John M Abowd and lan M Schmutte. Revisiting the economics of privacy: Population statistics and confidentiality protection public goods. Economics, (1/20), 2015.
Wael Alghamdi, Juan Felipe Gomez, Shahab Asoodeh, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. The saddle-point method differential privacy. In International Conference on Machine Learning, pages 508-528. PMLR, 2023.
Borja Balle and Yu- Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International Conference on Machine Learning. PMLR, 2018.
Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022.
Barry Becker and Ronny Kohavi. Adult.
UCI Machine
Learning Repository, 1996. DOL:
http:///bbooog//0224442///X111
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), 2022.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 2011.
Giovanni Cherubin, Boris Köpf, Andrew Paverd, Shruti Tople, Lukas Wutschitz, and Santiago Zanella Béguelin. Closed-form bounds for DP-SGD against record-level inference. In 33rd USENIX Security Symposium (USENIX Security 2024), 2024.
Rachel Cummings, Gabriel Kaptchuk, and Elissa M Redmiles. need a better description"" An investigation into user expectations for differential privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2022.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 2022.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Theory of Cryptography Conference, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which we call private. arXiv preprint arxiv: 03566, 2019.
Daniel Franzen, Saskia Nuñez von Voigt, Peter Sörries, Florian Tschorsch, and Claudia Müller-Birn. Ami private and if so, how many? communicating privacy guarantees of differential privacy with risk communication formats. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the ACM SIGSAC conference on computer and communications security, 2015.

---

Marco Gaboardi, Michael Hay, and Salil Vadhan. Manuscript, May. 2020.
A programming framework for OpenDP.
Elena Ghazi and Ibrahim Issa. Total variation with differential privacy: Tighter composition and asymptotic bounds. In IEEE International Symposium on Information Theory (ISIT), 2023,
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchan Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 2020.
Jamie Hayes, Borja Balle, and Saced Mahloujifar. Bounding training data reconstruction in DP-SGD. Advances in Neural Information Processing Systems, 2024.
Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In 2014 IEEE 27th Computer Security Foundations Symposium, 2014.
Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2021.
Zachary Izzo, Jinsung Yoon, Sercan O Arik, and James Zou. Provable membership inference privacy. Transactions on Machine Learning Research, 2024.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), 2019.
Bargav Jayaraman, Lingxiao Wang, Katherine Knipmeyer, Quanquan Gu, and David Evans. Re- visiting membership inference under realistic assumptions. Proceedings on Privacy Enhancing Technologies, 2021.
Richeng Jin, Zhonggen Su, Caijun Zhong, Zhaoyang Zhang, Tony Quek, and Huaiyu Dai. Breaking the communication-privaee privacy-accuracy tradeoff with f-differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 2023.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning. PMLR, 2015.
Georgios Kaissis, Jamie Hayes, Alexander Ziller, and Daniel Rueckert. Bounding data recon- struction attacks with the hypothesis testing interpretation of differential privacy. arXiv preprint arXiv:2307.03928, 2023a.
Georgios Kaissis, Alexander Ziller, Stefan Kolek, Anneliese Riess, and Daniel Rueckert. Optimal privacy guarantees for a relaxed threat model: Addressing sub-optimal adversaries in differentially private machine learning. Advances in Neural Information Processing Systems (NeurlPS), 2023b.
Thomas Kluyver, Benjamin Ragan-Kelley, Fernando Pérez, Brian Granger, Matthias Bussonnier, Jonathan Frederic, Kyle Kelley, Jessica Hamrick, Jason Grout, Sylvain Corlay, Paul Ivanov, Damián Avila, Safaa Abdalla, Carol Willing, and Jupyter development team. Jupyter notebooks a publishing format for reproducible computational workflows. In Positioning and Power in Academic Publishing: Players, Agents and Agendas. IOS Press, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Bogdan Kulynych, Mohammad Yaghini, Giovanni Cherubin, Michael Veale, and Carmela Troncoso. Disparate vulnerability to membership inference attacks. Proceedings on Privacy Enhancing Technologies, 2022a.
12

---

Bogdan Kulynych, Yao- Yuan Yang, Yaodong Yu, Jaroslaw Blasiok, and Preetum Nakkiran. What you see is what you get: Principled deep learning via distributional generalization. Advances in Neural Information Processing Systems (NeurIPS), 2022b.
Tobias Leemann, Martin Pawelczyk, and Gjergji Kasneci. Gaussian membership inference privacy, Advances in Neural Information Processing Systems, 36, 2024.
Erich L Lehmann and Joseph P Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
Jiaxiang Liu, Simon Oya, and Florian Kerschbaum. Generalization techniques empirically outperform differential privacy against membership inference. arXiv preprint arXiv:2110.05524, 2021.
Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint 1xXiv:2204.06106 2022.
Luise Mehner, Saskia Nuñez Voigt, and Florian Tschorsch. Towards explaining epsilon: A worst-case study of differential privacy risks. In 2021 IEEE European Symposium on Security and Privacy Workshops (FuroS&PW), 2021.
Priyanka Nanayakkara, Johes Bater, Xi He, Jessica Hullman, and Jennie Rogers. Visualizing privacy-utility trade-offs in differentially private data releases. Proceedings on Privacy Enhancing Technologies. 2:601-618, 2022.
Priyanka Nanayakkara, Mary Anne Smart, Rachel Cummings, Gabriel Kaptchuk, and Elissa M Redmiles. What are the chances? explaining the epsilon parameter in differential privacy. In 32nd USENIX Security Symposium (USENIX Security 23), 2023.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In IEEE Symposium
security and privacy (SP), 2021.
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), 2023.
Joseph P Near, David Darais, Naomi Lefkovitz, Gary Howarth, et al. Guidelines for evaluating differential privacy guarantees. National Institute of Standards and Technology, Tech. Rep, 2023.
Kobbi Nissim, Salil Vadhan, and David Xiao. Redrawing the boundaries on purchasing data from privacy-sensiteee individuals. In Proceedings of the conference on Innovations in theoretical computer science, 2014.
Edouard Oyallon and Stéphane Mallat. Deep roto-translation scattering for object classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015.
The pandas development team. pandas-dev/pandaa. Pandas, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 2019.
Shahbaz Rezaei and Xin Liu. On the difficulty of membership inference attacks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2021.
13

---

Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE symposium on security and privacy (SP). IEEE, 2017.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2013.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2021.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Coumaaeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Ker,, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 2020.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, 2018.
Michael L. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, 6(60), 2021. doi: 10.21105/ 03021. URL https: /ttp::///oooo////////// 21105/josss joss. 03021.
Larry Wasserman and Shuheng Zhou, A statistical framework for differential privacy. Journal of the
American Statistical Association, 2010.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi,
Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transformers: State-of-the-art natural language processing. arXiv preprint arXiv: 2019.
Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, James Honaker, Kobbi Nissim, David R O' O'Brien, Thomas Steinke, and Salil Vadhan. Differential privacy: A primer for a non-technical audience. Vand. J. Ent. Tech. L., 2018.
Lukas Wutschitz, Huseyin A. Inan, and Andre Manoel. dp-transformers: Training transformer models with differential privacy. https://wwi microsoft. com/en- ws/research/prooeecee dp-trannffrmeen August 2022.
Samuel Yeom, Irene Giacomeli,, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF). IEEE, 2018
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109, 0ttp9./2299/0 12298, 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2021.
Qinqing Zheng, Jinshuo Dong, Qi Long, and Weijie Su. Sharp composition bounds for gaussian differential privacy via Edgeworth expansion. In International Conference on Machine Learning. PMLR, 2020.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via char- acteristic function. In Proceedings of The 25th International Conference on Artificial Intelligence and Statisties, 2022a.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics. PMLR, 2022b.
14

---

Table 1: Notation summary
Symbol
Description
Reference
2
Data record
5 E 2D
Dataset of records
22 5"
Adjacency relation of neighboring datasets
:2: +
rivacy-preserving mechanism
w E
Noise parameter of mechanism M(S)
D,(M(5) (S
Hockeystick divergence
Eq. (1)
(0) 00.1
Privacy parameters differential privacy Privacy profile curve (6) Privacy profilc
Def.
Def. 2.2
6. [0
(x)
Def. 2.2
0:6 00
Membership inference hypothesis test
False positive rate (FPR) of attack ((f)
8 0.1]
False negutive rate (FNR) of attack 6(0)
0,
Maximal advantage across attacks against mechanism (S)
Eq. (7)
((M))
-0.
Tradc-off curve between FPR and FNR of optimal attacks A lower bound on the trade-off curve for all neighboring datasets
Def. 2.3
- [0.1]
Def. 2.4
P.Q X,Y
A dominating pair distributions for given mechanism (SS) Privacy loss random variables for a given dominating pair P, Q
Def. 3.1
Def. 3.2
A Attack-Aware Noise Calibration with Black-box DP Accountants
Advantage Calibration. Proposition 2.2 implies that (0,6)-DP mechanisms ensure bounded advantage 1) S 8. Therefore, given access to black-box accountant (6) or (c) we can calibrate to given level of advantage v/* by ensuring (0, DDD:
min w s.t. (n)) wes
or (0) = =
(19)
This is more generic way to perform advantage calibration using an arbitrary black-box accountant. is equivalent our procedure Section 3.1 when using Doroshenko et al. (2022) accountant.
EPR/ERR Calibration with Grid Search. Given a black-bor box DP accountant, i.e., a method which computes the privacy profile (6) of mechanism M-),), we can approximate (a) by discretizing the range of E [0, and solving Eq. (6) as:
fa
sup be....b.....bbt
max (0, 1- 1 - (1-
(20)
where 0 < 61 < 82 < <.... < 6n < 1. It is possible to perform analogous discretization using (e) and Proposition 2.1, which case we have to additionally choose a bounded subspace [Emin Emax] R. Equivalent procedures to Eq. (20) have previously appeared in Nasr et al. (2023); Zheng et al. (2020).
Plugging in Eq. (20) into the problem in Eq. (18), we can calibrate mechanisms to given a*, 9 using binary search (see Section 2.3) in a space (Wmin; Wmaxl Ω to additive error war > Denoting by V/:
Wmax
Wmin
(21)
Wer
the calibration requires [log2 v1 evaluations of (6). For instance, single evaluation of the bound in Eq. (20) takes approximately one minute with u = 100, and six minutes with u = 1,000 for DP-SGD with T 10,000 using Gopi et al. (2021) accountant as instantiation of (6) on commodity hardware (see Appendix H). In contrast, evaluating (-) using Algorithm in the same settings takes approximately 500ms the default discretization level A 10 (see Appendix D).
Although this approach is substantially less computationally efficient than our direct procedure in Section 3.2, its strength is that it can be used to calibrate noise in any DP algorithm which provides way to compute its (E, 8) guarantees.
B Detailed Calibration Algorithms
Advantage calibration. The standard advantage calibration first finds s* for given 8* < 1/n which provides the desired advantage guarantee via Eq. (8), then calibrates noise the derived (8 JDP guarantee using the privacy profile e. (8) function:
15

---

Algorithm 2 Standard advantage calibration
Require: ,""0", 0 where 8* 1 privacy profile e. (0). n.
1: Find s* by solving Eq. (8) for with fixed d = 8 and 1) = 17*
2: Find noise parameter w c.g., using binary search:
w argmin s.t. (w E* WER
3: return w
For direct calibration to advantage, we first show how practically use the expression in Theorem 3.3 to evaluate advantage using PLRVs:
Algorithm 3 Compute advantage using PLRVs (X,Y)
Require: PMF Pr Xw r] over grid {21, F2, ................................ F&k with 21 < 22 ... < 2k
Require: PMF Pr Pr rj over grid {31, 92. ................................ 81 with y1 y2 < ... < 1/1
1: procedure COMPUTEADV(w; Xw,, Y.)
2: Lx f- min [k] 04 > 0}, by f min(i E [ y/ > 0}
3: return Σ by Pr[y. Vil Dinty Pr[X =z,]
Given Algorithm 3, direct calibration advantage amounts e.g., binary search:
Algorithm 4 Direct advantage calibration using PLRVs (X,Y)
Require: n7,, PLRVs X Y. (see Algorithm 3 for more detailed specification) 1: Find noise parameter w", c.g., using binary search:
argmin s.t. COMPUTEADY(w:: Xw, Y.) S 11*
wEB
2: return w
FPR/ENR Calibration. The standard approach to FPR/ENR calibration proceeds analogously to advantage calibration. First, the algorithm solves Eq. (5) to obtain the value of s* which ensures that a mechanism satisfies faa* = f*. Then, the algorithm calibrates the noise to the obtained (E",5*) pair using the privacy profile function (8):
Algorithm 5 Standard FPR/ENR calibration
Require: 8²
"",6"" 6"' where 8* n privacy profile (5).
I: Find s* by solving Eq. (5) for with fixed 5 = 8* and f(a*) = 3*
2: Find noise parameter w", e.g., using binary search:
w argmin s.t. (w') e* weft
3: return w
Direct calibration to FPR/ENR amounts to, e.g., binary search, using calls Algorithm 1:
Algorithm 6 Direct FPR/ENR calibration using PLRVs (X,Y)
Require: a*, B* PLRVs Xw, Yu (see Algorithm I for detailed specification) 1: Find noise parameter w", e.g., using binary search:
wn f argmin s.t. COMPUTEBETA X Xu) 8* wEB
2: return w
16

---

Attack risk measure
Symbol
Derived 8
Advantage
" acc*
1 a 17'
Accuracy
2(a acc*)
Positive predictive value precision
ppv
(a 1)ppp
Table Some supported risk measures for calibration with fixed level of FPR a", with the derivation of the corresponding level of FNR 8*. Given a* and the derived 3*, we can calibrate noise using the procedure in Section 3.2.
C Calibration to Other Risk Notions
Noise calibration for given FPR/ENR level can be seen as a basic building block calibrate for other operational measures of risk that are functions of FPR a and FNR B.
For instance, Rezaci and Liu (2021) propose to measure the risks of membership inference attacks in
terms of accuracy acc and FPR a, where: acc(a, 3) & 1/2 ((1 a) (1 3)) We can calibrate
for given level of accuracy acc* and FPR a* using the method in Section 3.2 by solving the expression for accuracy for a given 3*.
Jayaraman et al. (2021) propose to measure positive predictive value, precision, of attacks:
3) - 1-
(22)
1-
Although precision alone is not sufficient to determine the level of privacy, like with accuracy, calibrate for given level of precision ppv" and FPR a* by deriving the corresponding 3
We provide the exact conversions in Table 2. These enable practitioners to use the calibration method in Section 3.2 while reporting technically equivalent but potentially more interpretable measures, c.g., attack accuracy at a given FPR.
Although throughout the paper have assumed that the hypotheses H. and 1/ both have probability 1/2, our results and conversions can be easily extended to settings where the hypotheses are not equiprobable, as proposed by Jayaraman al. (2021).
D Dominating Pairs
D.1 Constructing Discrete Dominating Pairs and their PLRVs
We summarize the technique from Doroshenko et al. (2022) to construct dominating pair from composed mechanism M(S) (1 o (2) o... (S). This models the common case in privacy-preserving MI where a simple mechanism, such as the subsampled Gaussian in DP-SGD, is applicd T times. We assume that each uub-mechanism (1) E [T'. has a known privacy curve 6.()). Given input discretization parameter A, size k. and a starting E (Doroshenko et al., 2022) creates a grid fei, E1 + A,..., + AA}. Then, they compute the privacy curve on this grid (81) 5e(E1 + A)................. 6E1 + k.)). and append the values of o( -o) = 0 and 5(cc). The dominating pair for the th mechanism is constructed using Algorithm 7. Note that Algorithm is identical Algorithm 1 in Doroshenko et al. (2022), with the notation modified be consistent with the notation in this paper.
This process is repeated for every mechanism. As long as the discretization parameter A is the same for all T mechanisms, the resulting collection of PLRVs can can be composed via the Fast Fourier Transform. The dominating pair for the composed mechanism M is simply the distribution X7, Y Y..... Xr).
of (X₃ + X2...
We remark that the discretization parameter A is user-defined, and the choice for the size k and starting ε for each grid is mechanism-spert speciffcc.. For further implementation details, we point the reader to the code documentation file and the code itself, which can be found in the dp accountin ing Python library.. In particular, we note that while the PLRVs X, Y have the same support except for atoms at too, the support of the composed PLRV X1 + X₂ ... + Xxr need not be the same as the the support of Y1 + Y2... + Yr. This because the convolution part of the implementation of Doroshenko et al. (2022), the code discards any tail probabilities smaller than some truncation
17

---

Algorithm 7 (Doroshenko et al., 2022) Construct a dominating pair
Require: Grid: E1.., Sk:
x)).
Require: Privacy curve on a grid: (., 8(Ex),
1: P(oo)= =0
2: for i = k L...., do
3:
P(s:) f exple:) exp(F.-1)
-(=+))
4: P(-oo) +1 -1-Ejek 2j P(ey)
5: Q(-00) 0
6: for pari=l,.... -,....,k -...,,--10
7: ((e:) eep((:))((e)
8: Q(x0) = =((0))
9: return (P,Q)
parameter. This is why we allow for X and Y to have different support in Algorithm 1, and why we make no assumptions on the distributions of (P, Q) or of (X,Y) in the proof for Theorem 3.3.
D.2 Some Properties of the Trade-Off Curves of Discrete Dominating Pairs
In this section, we provide several observations on the trade-off curve of discrete dominating pairs. In particular, these observations hold for the trade-off curve described Theorem 3.3.
Connecting the Dots. From the proof of Theorem 3.3 (see Appendix E.2). we know that when the level happens to equal point in the reverse CDF of X, i.c. when Pr[X > x.} for some i, that the corresponding FNR T(P, (a)) ) is simply the CDF of Y evaluated at the same point, i.c. T(P, (a) Pr(Y S xz]- Since the reverse CDF of X can take on k values, it follows that there are k + 1 values a where the trade-off curve is fully characterized by the CDF of the PLRVs.
Next, we observe a special structure of the trade-off curve on the points outside of these k + values. For fixed т, Eq. (34) implies a (T("7) increasing linearly in 7 and Eq. (37) implies (T, is decreasing linearly in 7. This implies that the trade-off curve "in between" the k + 1 points that correspond the CDFs of the PLRVs is linear interpolation, where one "connects the dots". Hence, the trade-off curve is piece-wiss linear, continuous everywhere, and not differentiable at the lc + 1 points where a happens to be on the reverse CDF of X.
This observation provides an interesting connection to Doroshenko et al. (2022), who showed that "connecting the dots" between finite points on the privacy profile 8(c5) yields a valid pessimistic estimate to the privacy profile. Could "connecting the dots" in trade-off curve space also yield valid pessimistic estimate? The answer is clearly no: "connecting the dots" on finite samples from a trade- off curve corresponds to an optimistic bound on the trade-off curve. Nevertheless, it is interesting to note that the class of discrete and finitely supported privacy loss random variables simultaneously achieve pessimistic bound in privacy profile space and an optimistic bound in trade-off curve space. Further exploration of this phenomena, specifically in the context of constructing optimal optimistic privacy estimates, is left as future work.
Behavior the Edges. The trade-off curve of discrete dominating (P,Q) in general does not satisfy T(P. (0) = 1. Indeed, the point = O corresponds to - Fmmx and = 0. in which case T(P. (0) = Pr(Y < =maax]= 1 Pr[Y Fmax] Whether or not this equals 1 depends on the details of the PLRV Y, though we note that in our experiments, T(P. (0) is usually I to within a
margin of 10-10, Moreover, we have that T(P, (a) for any a E [Pr[X -oo), 1]. Indeed,
for any E [Pr[X > oo). 1). we have that -00 meaning that 8 (T,7) Pr(y & -o0 = 0 for any choice of 7-
The observation that T(P. (0) * 1. that T(P, Q) is piece-wise linear, and that T(P, (a) 0 for any sufficiently large a, are all consistent with the findings of Jin al. (2023), who characterized the trade-off curves of discrete-valued mechanisms.
The linear interpolation must be done in e space, in this grid the privacy profile 8(e") is convex.
18

---

E
Omitted Proofs
E.1
Omitted Proofs in Section 3
First, let define the notion of the convex conjugate that we use in the proofs. For given function f: [0, 1] - [0, 1], its convex conjugate f* is:
f") sup yr f(x),
(23)
05251
Next, we can show the omitted proofs.
Proposition 3.1. (P; Q) is dominating pair for a mechanism M, then for a E [0, 1].
inf
M(5))) 2 ((P.
(10)
S=8"
Proof. The proof follows from taking the convex conjugate of both sides of the following result from Zhu al. (2022b):
Proposition E.1 (Lemma 20 from Zhu et al. (2022b) restated in our notation). If a mechanism is (P || -))-DP, then is f-DP for f such that the following holds:
De (P Q) = =1 (-
Taking the convex conjugate of the equation above reveals that follows exactly the structure of the trade-off curve implied by the Neyman-Pearson optimal test, which is exactly T(P, Q). See Appendix E.2.2 for more details on the Neyman-Pearson lemma.
Proposition 3.3 (Cost advantage calibration). Fix dataset size n > 1, and a target level of attack advantage 17" E (8*, 1), where 8* = for some c > 1. For any < a < L there exists a DP mechanism for which the gap in FNR (standard(a)) obtained with standard calibration for E* that ensures 1) E 17,, and FNR (ad)(a)) obtained with advantage calibration is lower bounded:
17
(aaa) fstandard - fadu(a) 2 17¹t - -5" 2a rj"
(15)
Proof. us fix a pair of datasets S = S", Suppose that we have mechanism M 2D + {0, 1,,3)
which satisfies (e, DD- Further, assume that for the specific fixed pair S, it is defined as follows:
(SM(S) 0) =
P(M(S') = 0)
P(M(S) 1) (1 -)
P(M(S') 1) (1 8)
(24)
P(M(S) = 2) = (1
P(M(S") = 2) = 8)
P(M(S)- = =3)- 5
P(M(S") =3)- =0
The defining feature of this mechanism is that its trade-off curve T(M(S), ((S)) for S, exactly matches the f(-) curve for generie (s, -DP mechanisms in Eq. (5) (Kairouz et al., 2015). Thus, for this mechanism we can use f and T(M (S), M (S')) interchangeably. In the rest of the proof, we assume that we are calibrating this mechanism.
We want to derive (1) fstandard under standard calibration with d* = 1/e-n and E* chosen such that we have 7 I 17th' (2) fadv under advantage calibration for ensuring 17", and find their difference.
For this, we first solve Eq. (8) for e to derive the corresponding 8* that would satisfy the required level of ry" under standard calibration with 8*
28
1
log
(25)
11"
As we are interested in the low a regime, let us only consider the following form of the DP trade-off curve from Proposition 2.1:
f(a) 1 - 8 c
(26)
19

---

It is easy to verify that this this form holds for 0 S a S 1-6 In the case of (=*,8*)-DD with e* ltfe.
defined by Eq. (25), simple computation shows that this holds for a S -
To get /standard. we plug (s", ,")) into the form in Eq. (26). Recall that by Eq. (8) advantage calibration for generic DP mechanisms is equivalent calibrating noise to (0, 17" JDD. Thus, get (adv(a), plug into 0, = 17" to Eq. (26). Subtracting the two, we get:
8*
A 11" 5t + 2a 1 1
(27)
from which we get the sought form.
Proposition 3.5. Given PLRVs (Xw: Yw) of discrete-valued dominating pair of a mechanism (.), choosing w" using Eq. (18) and Algorithm I to compute fa) ensures fw- (a*) ) 2 28"
Proof. Observe that Algorithm computes the intermediate values of T and & considered in the four cases of a values in the proof of Theorem 3.3 given in Appendix E.2, and thus computes the valid trade-off curve [PP, (a) defined Eq. (12). By Proposition 3.1, (.).) satisfies f-DP with = T(P.)).
E.2 Proof of Theorem 3.3
Theorem 3.3 (Accounting for advantage and f-DP with PLRVs). Suppose that a mechanism M()) has a discrete-valued dominating pair (P, Q) with associated PLRVs (X, Y). The altack advantage n for this mechanism is bounded:
1 S Pr[Y > Pr|x 0j.
(11)
Moreover, for any E CR -0) and y [0, define
(T, = Pr[Y -| Pr(YY T].
(12)
For any level a E [0, 11. choosing (1 a) -quantile of X and 7 a-Pr(X>r]
guarantees that PTX==
3
Eq. (11) is an implication of a result by Gopi et al. (2021), which states:
8(E) Pr[Y E] - e Pr[X e].
(28)
We get Eq. (11) by observing that O)D bounds S from Proposition 2.2.
In the remainder of the proof, show Eq. (12) and why choosing the threshold and coin flip prob- ability y in the way specified in the theorem guarantees T(P. ()(a = B(T, 7). In Appendix E.2.1, establish the notation necessary for the remainder of the proof along with all the assumptions made. In Appendix E,2.2, we introduce the Neyman-Pearson lemma and use it to construct Eq. (12). Finally, in Appendix E.2.3, we prove the final statement of the theorem.
E.2.1 Setup, Notation, and Assumptions
Let the domain of (P, Q) ) be O, which we assume to be countable. We refer to the probability mass function of P as P(-) and similarly for Q. We allow for multiple atoms where P(o) 0 and Q()) = 0, and also multiple atoms where Q(o") > 0 and P(o') = 0. We make no further assumptions on (P, Q).
Since (P, Q) dominate the mechanism M()), we know from Proposition 3.1 that the hypothesis test:
Ho 10:0<< P. H :1:0~0 Q
(29)
easier (the trade-off curve less than or equal to) that the standard DP hypothesis test:
Ho A ~ M(S), H 11:00 ~ M(S)
(30)
for all S S" In Appendix E.2.2, we use the Neyman-Pearson Lemma to tightly characterize the
trade-off curve implied by (29). The notion of privacy loss random variables (PLRVs) (X, Y), which were defined Def. 3.2 as Y A log Q(oi/ P(o) with o Q, and X A log Q(o') with d' P.
appear naturally and play central role in the proof.
20

---

As such, we establish more notation on them. Let T denote the finite values that the PLRVs can take We let the support of X be
T flog Q(0)/(())
o O, P(o) 0, Q(0) > 00--
U-OOTUT X [-T usup {sup
if sup T E ET otherwise.
and we set Pr[X = sup 7] 0 if we manually append sup 7 of X well-defined all countable domains. Moreover, let T'mx sup X sup T. We will often refer to elements in the support of X via (-00, I1, #2. , Fmax
do this to make quantile
E.2.2 Applying the Neyman-Pearson Lemma
According the Sayman-Pearson Lemma (see, e.g., Lehmann and Romano., 2006; Dong et al., 2022), the most powerful attack at level for the hypothesis test (29) threshold test o O - [0, parameterized by two numbers RU 0o), [0. 1].
if Q(o) > e² P(o)
o (0)
if Q(o = e² P(o)
(31)
((0) < eT
which we can equivalently write as:
1 if log Plol
Q(o)
6 (0)
if log P(o) =T
Q(o)
(32)
0 if log P(a)
Qlo
<T.
This threshold test works by flipping a coin and rejecting the null hypothesis (equivalently, guessing that came from Q) with probability ",,,())) (o). Here, log Ploj is the Neyman-Pearson test statistic, and is the threshold for this test statistic. If the test statistic less (greater) than the threshold, the rejected (Ø',- 0) when the null hypothesis is true (o P), and has the following form:
Q(o)
test always rejects (accepts) the null hypothesis, and if the test statistic equals the threshold, the test flips coin with probability 7 to reject the null hypothesis.
The false positive rate or,y, which we denote by a, is the probability that the null hypothesis is
a (T,77)
A
E 10 (0,,, (0)
(33)
owP
= =
7] + Pr([(X
(34)
Similarly, the false negative rate of o;,,, which we denote 3, is the probability that the null hypothesis is accepted (1 oi, > 0) when the null hypothesis is false (o ~ Q), and has the following form:
B (T,7)
E Q~Q
(6)
(35)
1 (Pr( Pr|Y =]]
(36)
Pr|Y < - =]]
(37)
We have thus shown the correctness of the construction of Eq. (12). In Appendix E.2.3, we prove the final statement in Theorem 3.3.
E.2.3 Construction of the Trade-Off Curve of Dominating Pair
The goal of this section is to prove the following statement made in Theorem 3.3:
For any level E [0, 1), choosing
(1 -q--unie of X and a-Pr <-Pr(X>>r guarantees that: P[[
T(P.Q)(a)=
where T(P, (a) outputs the false negative rate of the most powerful attack at level a. From Appendix E.2.2, know that the most powerful attack takes the form oi,y defined in Eq. (32).
21

---

One should think of the level a as a constraint on the attack 0. In particular, the constraint a" a"(T, 7) (where a' is the false positive rate of oz and is defined in Eq. (33)) yields family of possible tests that all achieve the level a. If (P, Q) were continuous distributions, the constraint a" (T) = would uniquely determine the optimal test. This does not hold in the discrete case, and hence we must identify the most powerful test within this family.
Below, we list out 4 different regimes for the value of the level a, identify the family of possible tests in each regime and the most powerful test, and finally give the false negative rate of the respective most powerful test.
1 Case a 1: Recall that X has a finite probability of being -o, meaning that the only way to have a² (T, 7) = 1 is to set 7 -x and 7 1. The corresponding false negative rate is given by (-
= Pr[Y S -0] Pr[Y - _x] =
2 Case a = O: If we choose the threshold T = max and the coin flip probability 7 = 0, then we have that the false positive rate of this test is:
a (T Fmax 7 = 0) Pr(X > Fmax) + Pr Fmaa
(38)
0.
(39)
Morcover, any test with >> Tmax has a (T, 7) O. However, increasing the threshold above
Tmax can never decrease 33" Moreover, a test with a threshold T < Tmax cannot achieve a = 0.
follows that choosing (T Tmax, 7 = 0) yields the most powerful test, which has false negative rate 3 (Imux, 0) = Pr[Y I J-
3 Case = Pr[X > xe) for some probability 7 = 0, then we have that the false positive rate of this test
X: If we choose the threshold T and coin flip
a = Ft. = 0) = Pr(X x4) + 0
(40)
(41)
Moreover, the test &% and any test with 7 E (Ze, 21+1) has a (T.7) a. It straightforward
see that all these tests are equivalent outputting if log 2(0) 2g and 0 otherwise, making them all equivalent to o .0- Note that no other test can achieve the level a, since decreasing the threshold below I; or above Z++1 makes it impossible
achieve level a. For fixed threshold T = I2 (I only a coin flip probability o = 0(1) achieves level a. We conclude that all the tests that achieve level have false negative rate of 3 Pr|Y s zz).
4 Otherwise: If we choose the threshold
T = inf E X a 2 Pr[X > x|}
(42)
and choose the coin flip probability to exactly satisfy the constraint that a² (T,7)) = ar, i.e.,
PP[[X > xx) Pr[X xx]
(43)
then this test achieves false positive rate of a. easy to see that this is the only test that achieves level a, and has a false negative rate of 3 = PriY < x1 Pr(Y zz).
Note that in all regimes, there is one unique test that achieves a level and is the most powerful test. However, in some regimes of a E [0, 1]. namely regime 3, there are many different parameterizations for the same test. In these cases, are free to choose any parameterization. For each regime, the very first test we list is the parameterization we choose. To summarize, we have the following most powerful tests:
when a = 1, choose 7 = -00, 7 =
when a = 0, choose T = Fmuxx 7 = 0
3 when = Pr[X > 2t). choose T = Ltt, ? = 0
4 else, choose via Eq. (42), and 7 a P-Pr[[>T]]
PP[X=T]
22

---

It is clear from the list above that for distributions with finite support. the most powerful test can be concisely written as:
T inf E E
a a Pr(X > x]}
(44)
7 = a - -rrrX T]
(45)
Pr(X -
where we recognize T as the (1 a)- -qqantile of X.
Note that for distributions with countably infinite support, Eq. (45) does not capture Case 2, since Pr[X- Xmax] = O. So. we define 7 whenever = 0, and y Eq. (45) otherwise. Since this work focuses on using PLRVs from Doroshenko et al. (2022), which are always finitely supported, we report Eq. (44) and Eq. (45) without this edge case in the main body.
We remark that similar results regarding the trade-off curve between two discrete mechanisms can be found in Jin et al. (2023). We differ from this work by parameterizing the trade-off curve using PLRVs, in contrast Jin et al., who parameterized the trade-off curve in terms of the discrete distributions P and Q. Our parameterization lends itself more naturally to composition, as the PLRVs sum under composition.
F Practical Considerations
The algorithm of Doroshenko et al. (2022), which is implemented in the dp_ accounting Python library," ** handles Poisson subsampling under composition (i.e. accounting for DP-SGD) by analyzing the removal and add relations separately. This approach, to the authors knowledge, was first advocated for by Zhu et al. (2022b) (see the discussion in their Appendix).
In particular, instead of the algorithm outputting a dominating pair (P,Q) that dominates for the symmetric add/remove relation under composition, outputs one dominating pair for the asymmetric remove relation (P (Premuves Qremove) ) and one for the asymmetric add relation (Pada, Qusa). This means that naively applying Theorem 3.3 to, for example, (Padd Qudu), will return a trade-off curve that is only valid for DP-SGD under the asymmetric add relation.
To handle the case when Theorem 3.3 is applied PLRVS (X, Y)) that only dominate a mechanism under an asymmetric neighboring relation, a more sophisticated technique is needed to map ((P, Q) the target symmetric neighboring relation. In particular, a result from (Dong et al., 2022) explains how to handle this case:
dominating pair (P, Q) (equivalently, the
Proposition F.1 (Proposition F.2 from Dong et al. (2022)). Let f [0, [o, 1] be a convex, continuous, non-increasing function with ((x 1 x x E [0. 1]. Suppose mechanism M (E, + (" for all E 2 O, then is Symm(f)-DP with the synmetrization operator Symm(J) defined as:
if f()). if f(7), f
Symm(f)(x)
(46)
where = = in [0.1] |: -1 0f(z))) and
[f(z). [()). < S()),
S
(47)
(x).
if > f(ā).
Though not explicitly stated, the proposition does assume the mechanism M(.) has a symmetric neighboring relation. By letting f be unspecified however, the proposition allows for the input function f to correspond to asymmetric neighboring relation. In this case, the proposition returns a trade-off curve that holds for the symmetric neighboring relation.
We can hence apply this proposition to the problem at hand by recalling that given a dominating pair (P, Q). we have that the mechanism is (c, De: (P || QDP Moreover, Theorem 3.3 outputs the trade-
off function f = T(P, Q), which is exactly the function f such that D. (P || Q) = 1 1 f- We can thus restate Proposition F.I more familiar form as:
23

---

Proposition F.2 (Proposition F.2 from Dong et al. (2022) restated). Suppose that (P, Q) is domi- nating pair for a mechanism (-) under either the add or remove relation. Then, the mechanism Symm(T (P, Q))-DP with respect to the add/remove relation.
Proposition F.2 allows us to, for example, use a dominating pair for the asymmetric add relation to ob- tain trade-off curve for the symmetric add/remove relation. Moreover, the operator Symm (T(, Q)) implement practice.
turns out to straightforward
Appendix E.2.3 details how to explicitly construct T(P, Q). It is well known that T(Q, P))a) = T(P, (()()))(a,, ((),, hence the order of (P, Q) can be easily swapped in Appendix E.2.3 to get the inverse function T(P, Q) The only obstacle remaining is in determining ε = inf E [0, 1. : E (z))). Due the structure of T(P Q), namely that is piece-wise linear function parameterized by Eq. (34) and Eq. (37), it turns out that the subdifferential (z) are of the form {er ). where T are the allowable thresholds the proof laid out in Appendix F.2.3. As an example, a unique threshold of -00 at = 1 implies that the derivative of T(P: Q) at a = O, meaning the trade-off curve is flat there.
the Seyman--Pearoon lemma level identified in each of the cases of
follows that the constraint ă = inf (I E [0, [ -1 0x())) implies that & is the smallest level where the threshold switches signs, i.e. aT 7, -Pr[X > 0] and f(æ) 3 (T 0, 7 0) = Pr[y I Oj. This gives us all the information needed to implement the Symm operator.
G Calibrating Gaussian Mechanism
In the case where the trade-off curve of the mechanism has closed form, we can solve the calibration problems in Eqs. (13) and (18) exactly without resorting to the numerical procedures in Sections 3.1 and 3.2.
Definition G.1. For given non-private algorithm q: 2D Rd. Gaussian mechanism (GM) is defined as MS)) = (S) + E, where & ~ (0 A2 0². Ia) and D2 & sups-s [[((S) g( )| is
the sensitivity of (S))
For the Gaussian mechanism, we can exactly compute the relevant adversary's ' error rates:
Proposition G.1 (Balle and Wang (2018); Dong et al. (2022)). Suppose that Ma (S) is GM with sensitivity 22 and noise variance o². Denote by = A2fa and by ((t) the CDF of the standard Gaussian distribution N (0, 1). Then,
* The mechanism satisfies (c, 8)-DP if the following holds:
E
(-
8 = 1
(48)
1
2
It satisfies f-DP with:
((a) + ( ax)
(49)
With these closed-form expressions, we can solve the calibration problems exactly:
Corollary G.2 (Advantage calibration for GM). For a GM (S) and target 17" > 0. choosing o
0
(50)
2Φ
ensures that adversary's 's advantage is upper bounded by n²
Proof of Corollary G.2. It is sufficient to ensure (0, 11" J-D.. Plugging in é = 0 and 5 = ')* into
Eq. (48), we have:
11
11
17t ④
24
1,
(51)
2
from which we can derive μ
Az 2 -1 n n'+1
2
By solving Eq. (49) for a, we also have exact expression for calibrating to given level of a', a',8":
24

---

Corollary G.3 (FPR/FNR calibration for GM), For a Gaussian mechanism Mo and target a
f 2 0 such that a* 8 S choosing a as:
A
(52)
T ax') + (B*)
ensures that adversary's FNR and FPR rates are lower bounded by a* and B3,, respectively.
Note that using the exact expressions above to calibrate Gaussian mechanism offer only computational advantages compared the method the main body. terms of resulting noise scale o, the results the same as with generic PLRV-based calibration up to numerical approximation error.
H
Additional Experiments, Details, and Figures
H.1 Computing Resources
We use commodity machine with AMD Ryzen 5 2600 six-core CPU, 16GB of RAM, and an Nvidia GeForce RTX 4070 GPU with 16GB VRAM run our experiments. All experiments with deep learning take up to four hours to finish.
H.2 Experimental Setup
In all our experimental results, the neighborhood relation 5 = S' is the add-remove relation, i.e., = S' ifT is A S = which is the standard relation used by modern DP-SGD accountants, See more on implementation details related to the neighborhood relation in Appendix F.
Text Sentiment Classification. We follow Yu et al. (2021) to finetune a GPT-2 (small) (Radford et al., 2019) using LoRA (Hu et al., 2021) with DP-SGD on the SST-2 sentiment classification task (Socher et al., 2013) from the GLUE benchmark (Wang et al., 2018). We use the Poisson subsampling probability p xe 0.004 corresponding to expected batch size of 256, gradient clipping norm of A2 1.0, and finetune for three epochs with LoRA of dimension 4 and scaling factor of 32. We vary the noise multiplier E (0.5715, 0.6072, 0.6366, 0.6945, 0.7498) approximately corresponding to {3.95, 3.2, 3.2, 1.9, 1.45). respectively, SST-2 dataset containing 67, 344348 examples for finetuning, and the default validation split containing 872 examples test set.
10 We the default training split of the
Image Classification. We follow Tramer and Boneh (2021) to train a convolutional neural net- work (Tramer and Boneh, 2021, Table 9, Appendix) Mallat, 2015) on the CIFAR-10 (Krizhevsky et al., 2009) image classification dataset. We use the Poisson subsampling probability of Ra 0.16 corresponding learning rate of 4, Nesterov momentum 0.9, and gradient clipping norm A = 0.1. We train for up 100 epochs. We vary the gradient noise multiplier a/22 [4, 5, 6, 8, 10). corresponding to E (5. 3.86, 3.15, 2.31, 1.63), respectively, at 10-5 We use the default 50K/10K train/test split of CIFAR-10.
the ScatterNet features (Oyallon and
expected batch size of 8192,
H.3 Additional Experiments with Histogram Release
Histogram release is simple but common usage of DP, appearing as a building block, e.g. in private query interfaces (Gaboardi et al., 2020). To evaluate attack-aware noise calibration for histogram release, we use the well-known ADULT dataset (Becker and Kohavi, 1996) comprising small set of US Census data. We simulate the release of the histogram of the 'Education' attribute (with 16 distinct values, e.g., "High school", "Bachelor's", etc.) using the standard Gaussian mechanism with post-processing to ensure that the counts are positive integers. To measure utility, we use the L₁ distance (error) between the original histogram and the released private histogram.
Figure shows the increase utility we calibrate the noise of the mechanism using the direct calibration algorithm to given level of FPR a* and FNR 3* vs. standard calibration over 100 simulated releases with different random seeds. In certain cases, e.g., for a = 0.1 and 3* = 0.75, approach decreases the error by approx. 3x from three erroneous counts average to one.
25

---

H.4 Software
We use the following key open-source software:
Py PyTorch (Paszke et al., 2019) for implementing neural networks.
huggingface (Wolf et al., 2019) suite of packages for training language models.
opacus (Yousefpour et al., 2021) for training PyTorch neural networks with DP-SGD.
dp-transformers (Wutschitz et al., 2022) for differentially private finetuning of language models.
numpy (Harris et al., 2020), seipy (Virtanen et al., 2020), pandas (pandas development team, 2020), and jupyter (Kluyver et al., 2016) for numeric analyses.
scaborn (Waskom, 2021) for visualizations.
26

---

Feasible region by DP
Exact feasible region
Attack FNR. 3
0.5
1-46 14e7
1-6
0.5
1
14
Attack FPR.
Figure 5: Trade-off curves of Gaussian mechanism that satisfies (c, 8)-DP. Each curve shows boundary of the feasible region (greyed out) of possible membership inference attack FPR (a) and FNR (3) pairs. The solid curve shows the limit of the feasible region guaranteed by DP via Eq. (5), which is a conservative overestimate of attack success rates compared to the exact trade-off curve (dotted). The maximum advantage 1) is achieved with FPR and FNR at the point closest to the origin.
Standard calibration (SC)
Exact SC trade-off curve
Advantage calibration (AC)
Attack FNR, 3
Exact AC waad-oof curve
0.5
Attack FPR,
Figure 6: The increase in attack sensitivity due to calibration for advantage is less drastic for Gaussian mechanism than for generic (c, 6DP mechanism.
o 0.01
o 0.05
= 0.1
Method
Standaadd us calibration celloration
Attack TPR.
3
Attack TPR,
Attack TPR.
Figure 7: Direct calibration attack FNR/FPR reduces average Ln error in histogram release with Gaussian mechanism. The confidence bands are 95% CI over 100 simulated releases.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims in the abstract/intro succinctly represent the claims in the main body.
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 to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 3.1 discusses detail the limitations of advantage calibration. Sec- tion 5 discusses limitations and future work for the whole paper.
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 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., if 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 in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in 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: [Yes]
28

---

Justification:
The theoretical results are within the standard setup of differential privacy detailed in Section 2.1.
Guidelines:
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 provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to 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)?
Question:
Answer: [Yes]
Justification: We provide the detailed information on reproducing the experimental results in Appendix H. Moreover, we link the code along with the instructions for reproducing.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary 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 to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We common openly available benchmark datasets. We have published the code on the Github platform.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
heellic/guies//eee CowedeeeCooSuuuissiiic.. stteesuubbisiiiooocoyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: wtw.eessuumssssooooolooooo
/ //npps.c////cc htabbii/guiiee////eeeeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only 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/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the information on the machine learning details in the main body well as in Appendix H.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: In our setting, we can directly approximate the theoretical quantities of interest (i.e., the level of privacy) without the need for empirical statistical methods and the corresponding uncertainty estimation. For the empirically evaluated model accuracy values, only one seed in the main suite of experiments for computational reasons. In the additional experiments in Appendix H, we provide 95% confidence bands.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

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 a 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 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out 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 or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments only require commodity hardware. We detail the requirements in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :/tp::://////uu// http///eerrrrureeee/ee htcp/p/licc/thhicccttteeee.eeeee
Answer: [Yes]
Justification: Neither the research process itself nor the outcomes of the research carry significant potential for harm.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: The topic of our paper is concerned with social issue of privacy in machine learning and statistical analyses, and our work aims to improve the state of the art in the area. Although our work is mostly technical, we take broader look in Sections and 5.
31

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it 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, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
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.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no 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 or 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
Are the creators or 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?
Question:
Answer: [Yes]
Justification: We cite the dataset sources well the sources for the key pieces of software used for the experimental evaluations and analyses in the main body and Appendix H.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
32

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 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: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or 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 of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. 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: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
33

---

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 not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "6zYMvSA07M", "reviewer": "Reviewer_JyJW", "summary": "Differential privacy (DP) mitigates privacy risks in machine learning by adding noise during training, balancing privacy and utility. Traditionally, the noise scale is set using a privacy budget parameter ε, which is then translated to attack risk. This two-step method often results in conservative risk assessments and reduced utility. The proposed approach directly calibrates noise to a desired attack risk, bypassing ε, thus decreasing the noise scale and enhancing utility while maintaining privacy. Empirical evidence shows that this method improves model accuracy for the same privacy level, offering a practical way to enhance privacy-preserving machine learning.", "questions": "1.\tIn the experiment section, how about the results of other low FPR regimes?", "limitations": "1. In Section 3.1, please include inference for ensuring advantage calibration in the appendix.\n2. The two figures at the top of page 7 lack figure names. It appears they should be labeled as Figure 2.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed framework successfully addresses technical challenges, providing compelling insights.\n2. The experimental results are robust and strongly support the framework's effectiveness.", "weaknesses": "1.\tThe paper includes numerous definitions and symbols, which can be confusing for readers. Creating a table to summarize these terms and explain their meanings would greatly enhance clarity and help readers follow along more easily.\n2.\tIn Section 2, the problem statement is not clearly articulated, making it difficult to discern the main goal and the specific problem being addressed. Highlighting the main goal and explicitly defining the problem would make this section more readable and comprehensible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and the suggestions! We respond to the comments and questions next. Note that we also address some of them in the general response, and we refer to it when relevant.\n\n> The paper includes numerous definitions and symbols, which can be confusing for readers. Creating a table to summarize these terms and explain their meanings would greatly enhance clarity and help readers follow along more easily.\n\nSee the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz) for the notation table.\n\n> In Section 2, the problem statement is not clearly articulated, making it difficult to discern the main goal and the specific problem being addressed. Highlighting the main goal and explicitly defining the problem would make this section more readable and comprehensible.\n\nThe problem statement appears in the discussion of Section 2.3. We will highlight this more clearly in the final version, and change the title of Section 2.3 to “Our Objective: Attack-Aware Noise Calibration” to clearly signal that the problem statement is there. To be clear, our problem is to solve the calibration problem $\\min \\omega \\text{ s.t. } risk_\\omega \\leq threshold$, in particular, by providing a method to efficiently compute $risk_\\omega$ for standard notions of operational attack risk in DP.\n\n**Questions**\n\n> In the experiment section, how about the results of other low FPR regimes?\n\nSee the attached PDF in the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz) for the trade-off curves for all five models in the language modeling experiment. Using these curves, one can glean the behavior in terms of FPR/FNR trade-off for different levels of noise scale/task accuracy and for all $\\alpha \\in [0, 1]$ as opposed to $\\alpha \\in \\{{0.01, 0.05, 0.1\\}}$. We will add these plots in the Appendix in the final version.\n\n**Limitations**\n\n> In Section 3.1, please include reference for ensuring advantage calibration in the appendix.\n\nEq. 13 in Section 3.1 shows (1) the optimization problem corresponding to advantage calibration and (2) how we compute advantage given dominating PLRVs $(X_\\omega, Y_\\omega)$. Moreover, in Appendix E we explain how to obtain $X_\\omega, Y_\\omega$ from an arbitrary mechanism given its privacy curve, and in Section 2.3 we explain how we solve an optimization problem in the form of Eq 13. In the final version, we will consolidate all this information into one algorithm in the Appendix, as showed in the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz). \n\n> The two figures at the top of page 7 lack figure names. It appears they should be labeled as Figure 2.\n\nThank you for spotting this issue! Indeed, this Figure is missing a caption. We will fix this in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ow1ZigYGkT", "reviewer": "Reviewer_Bdkd", "summary": "This paper introduces a new method for improving  the utility of privacy-preserving machine learning without sacrificing privacy protection. The authors develop efficient algorithms to calculate the trade-off curve between attack FPR and FNR using f-differential privacy (f-DP). They then show how to use this information to fine-tune the amount of noise added, allowing for precise control over privacy risks. This approach offers a more refined way to balance data usefulness and privacy in machine learning, addressing a key challenge in the field.", "questions": "see in weaknesses", "limitations": "see in weaknesses", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The authors show that their direct calibration methods can significantly reduce the required noise scale compared to the standard approach, leading to an increase in utility (e.g., 18 percentage points higher accuracy) for the same level of privacy risk. They also demonstrate that calibrating for attack advantage (attack accuracy) can increase attack power in the low FPR regime, and show that calibrating for a desired FPR and FNR level mitigates this issue. By this method, the noise of DPSGD can be reduced tighter once we are aware of the privacy risk.", "weaknesses": "The notation in this paper is heavy, could you provide notation tables?\n\n\nCould you provide a more detailed algorithm in the appendix about how to use $\\epsilon$ , $\\delta$, and q to generate Advantage Calibration’s Xω , Yω.  Its quite hard to follow in Section 3’s demonstration. I think authors need an algorithm to demonstrate how they did the experiment from the supplement's code.\n\nI am willing to increase my score if the above questions can be answered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and suggestions. We address some of points raised directly below, but they are also partially covered in our general response, to which we refer when relevant.\n\n> The notation in this paper is heavy, could you provide notation tables?\n\nWe agree. See the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz) for the notation table.\n\n> Could you provide a more detailed algorithm in the appendix about how to use $\\epsilon$, $\\delta$ , and $q$ to generate Advantage Calibration’s $X_\\omega$ , $Y_\\omega$. It’s quite hard to follow in Section 3’s demonstration. I think authors need an algorithm to demonstrate how they did the experiment from the supplement's code.\n\nIn Section 3, following Theorem 3.4, we point to Appendix E for how we construct $X_\\omega$, $Y_\\omega$ for a general mechanism given its privacy curve. We will clarify in L226 as follows:\n\n“Given a method for obtaining valid PLRVs $X_\\omega$ , $Y_\\omega$ for any $\\omega$, **such as the one provided by Doroshenko et al. 2022 (see Appendix E),** …”\n\nWe want to emphasize to the reviewer that Appendix E is a summary of the algorithm proposed by Doroshenko et al. 2022, which we used in all of our experiments. Moreover, this algorithm uses the entire privacy curve and mechanism-specific functions such as $q$ to construct $X_\\omega$, $Y_\\omega$, not just a single $(\\epsilon, \\delta)$ pair. \n\nAdditionally, we provide a more detailed description of the steps involved in the calibration algorithms in the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mlAyMxEmDM", "reviewer": "Reviewer_pcXQ", "summary": "This paper proposes new methods for calibrating noise in differentially private learning to achieve a given level of operational privacy risk, specifically focusing on the advantage and FNR/FPR of membership inference attacks. The methods reduce the noise scale compared to the standard two-step procedure (first converting to a privacy budget, then converting to a privacy assessment).", "questions": "1. Will choosing a discrete-valued dominating pair of the mechanism be a sub-optimal choice for advantage calibration?\n\n2. How is the discretized PLRV typically obtained for a general mechanism?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses an important practical problem in the privacy regime with significant theoretical contributions.\n\n2. It is well-organized and easy to follow.", "weaknesses": "1. I suggest the authors include more downstream tasks and utility metrics to further demonstrate the effectiveness of the theoretical results.\n\n2. High-level intuitions for different variables in Theorem 3.4, such as $\\alpha(\\tau, \\gamma)$ and $\\beta(\\tau, \\gamma)$, would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and suggestions!\n\n**Weaknesses**\n\n> I suggest the authors include more downstream tasks and utility metrics to further demonstrate the effectiveness of the theoretical results.\n\nWe have added a new experiment on a common use case of DP – private histogram release – which shows that attack-aware noise calibration also enables to significantly reduce the error when privately releasing histograms. See the [general response](https://openreview.net/forum?id=hOcsUrOY0D&noteId=4H6Ec2IhLz) and the attached PDF for details. \n\n> High-level intuitions for different variables in Theorem 3.4, such as $\\alpha(\\tau, \\gamma)$ and \n$\\beta(\\tau, \\gamma)$, would be beneficial.\n\nWe will add the following lines after Theorem 3.4:\n\n“The proof for Eq. (12) works by using the Neyman-Pearson lemma to explicitly construct the optimal most powerful attack at level $\\alpha$. We parameterize the optimal attack in terms of intermediate parameters $\\tau$ and $\\gamma$, where $\\tau$ is the threshold for the Neyman-Pearson test statistic and $\\gamma$ is the probability of guessing in case the test statistic exactly equals the threshold.”\n\n\n**Questions**\n> Will choosing a discrete-valued dominating pair of the mechanism be a sub-optimal choice for advantage calibration?\n\nAny dominating pair, whether discrete or continuous, suffices for advantage calibration. Moreover, the results of Doroshenko et al. 2022 imply that a carefully-crafted discrete-valued dominating pair can provide arbitrarily tight privacy bounds to a continuous mechanism. Since we use the algorithm proposed by Doroshenko et al., the answer to this question is no: a discrete-valued dominating pair is not sub-optimal for advantage calibration. \n\n> How is the discretized PLRV typically obtained for a general mechanism?\n\nIn Appendix E, we detail the technique from Doroshenko et al. for constructing PLRVs for a general mechanism given its privacy curve. The technique discretizes the privacy profile curve, and builds pmfs of the dominating pair $P$, $Q$ using the discretized values. The distributions of the PLRVs can then computed using the pmfs of $P$, $Q$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kwvmicO8hW", "reviewer": "Reviewer_tsqL", "summary": "The paper proposes calibrating the noise in privacy mechanisms directly to MIA success metrics like advantage or TPR at low FPR instead of calibrating to a given $(\\epsilon, \\delta)$-bound and converting that to bounds on MIA success. The paper develops an algorithms for direct calibration for various MIA success metrics, most importantly TPR at low FPR. The algorithms use a discrete privacy loss random variable that is output by an existing privacy accountant. The paper compares the calibration methods by comparing the noise variances, and finds that calibrating directly significantly reduces the amount of noise required. The paper also does a small experiment showing that the reduction in noise translates to improved accuracy for machine learning.", "questions": "Issues with Theorem 3.4:\n- In the reasoning around lines 673-675, why is it not possible that $\\alpha$ just happens to be one of the $k+1$ possible values of Eq. (42)? On line 659, it is said that this reasoning should work for all $\\alpha$. This case is considered explicitly later, but only after this line of reasoning is concluded.\n- Doesn't the conclusion that there can be multiple ways values of $\\gamma$ and $\\tau$ that satisfy the constraint on line 695 imply that the choice of the optimal test $\\phi_{\\tau,\\gamma}$ is not unique, though the FPR and FNR are unique?\n- Why is the test that is found on lines 690-698 optimal?\n- It is not clear whether Theorem 3.4 claims \"for all $\\tau$ and $\\gamma$\" or \"for some $\\tau$ and $\\gamma$\".\n\nMinor points:\n- I don't think Algorithm 1, line 2 works with $\\alpha = 1$, the strict inequality is never satisfied. Though this should be easy to fix.\n- Line 164: should this have $\\alpha^\\star$ instead of $\\alpha$?\n- Are $P$ and $Q$ the correct way around in Eq. (1)? They seem to be the other way around in Gopi et al. [2021].\n- Should the support of $Y$ in line 666 be $y_1, \\dotsc, y_{l+1}$ instead of $x_1, \\dotsc, x_{l+1}$?\n- Are the image classification results in Figure 1 comparable between standard and attack risk calibrations, since you had to use RDP due to data augmentations with the standard accountant?\n- What type of subsampling (Poisson, sampling with/without replacement) and which neighbourhood relation did you use in the DP-SGD experiments? The fixed batch sizes suggest sampling without replacement, in which case the issues that Lebeda et al. (2024) have recently raised with privacy accounting for sampling without replacement might affect your results.\n\nReference:\n- Lebeda et al. \"Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition\" (2024) arXiv:2405.20769", "limitations": "The paper discusses limitations adequately.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is mostly easy to read and understand, given the amount of theory. The case for calibrating directly to membership inference success metrics is made very well, and the algorithm for the calibration seems very practical.", "weaknesses": "Some parts of the proof of Theorem 3.4, the main theorem of the work, are not fully clear, and could be missing details needed to make them fully correct. I've collected these points in the Questions section. I think the issues can be fixed, and the theorem is likely true, but these should be addressed before the paper is accepted.\n\nFigure 5 shows that the $\\delta'$ corresponding to the attack TPR/FPR calibration is very large compared to the standard $\\delta$. The standard $\\delta$ is chosen to be small, since the mechanism that randomly outputs one individual's data is $(0, 1/n)$-DP with $n$ datapoints. I think the paper should discuss how this mechanism behaves with the TPR/FPR calibration. My quick calculation suggests that with the optimal attack for this mechanism, $FNR = (1 - 1/n) \\cdot (1 - FPR)$, which would give a large FNR at small FPR, suggesting that the mechanism is very private, even though it obviously isn't. Requiring the FNR bound to be large to fix this could reduce the apparent advantage that the paper's results suggest, since the paper always considers smaller FNR bounds.\n\nMinor points:\n- Line 97: the domain and range of $\\epsilon_\\omega$ are the wrong way around.\n- The neighbourhood relation is inconsistent: Section 2.1 describes substitute neighbourhood, while Section 2.2 describes add/remove neighbourhood.\n- TPR does not necessarily need to be high for a MIA to be a relevant threat. For example, if TPR = 1% at FPR = 0.01%, the attack can very accurately identify the presence of a small number of individuals, which violates the privacy of those individuals.\n- The results in Figure 1 could have uncertainty estimates.\n- Restating the theorems before their proofs and having the proofs in the same order as the main text would make the proofs much easier to read. \n- Line 649: $\\phi$ outputs the probability that the sample came from $Q$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for such a detailed reading of our work, and especially the proof! We appreciate it.\n\n## Theorem 3.4\n\n> **Q1.** In the reasoning around lines 673-675, why is it not possible that $\\alpha$ just happens to be one of the possible values of Eq. (42)? On line 659, it is said that this reasoning should work for all $\\alpha$. This case is considered explicitly later, but only after this line of reasoning is concluded.\n\nWe agree that this line of reasoning appeared too early in the proof. We will move it to the part of the proof where we only consider $\\alpha$ that are not one of the possible values of the reverse CDF of $X$ in Eq. (42).\n\n> **Q2.** Doesn't the conclusion that there can be multiple ways values of $\\gamma$ and $\\tau$ that satisfy the constraint on line 695 imply that the choice of the optimal test is not unique, though the FPR and FNR are unique?\n\nNot necessarily! What we are saying in line 695 is that the optimal test, which is unique, can have two different _parameterizations:_ $(\\tau_1 = x_t, \\gamma_1 = 0)$ and $(\\tau_2 = x_{t+1}, \\gamma_2 = 1)$. That these two parameterizations yield the same test follows by observing that $\\phi^*_{\\tau_1, \\gamma_1}(o)$ outputs 1 if $\\log \\frac{Q(o)}{P(o)} > x_t$ and 0 otherwise, while $\\phi^*_{\\tau_2, \\gamma_2}(o)$ outputs 1 if $\\log \\frac{Q(o)}{P(o)} \\geq x_{t+1}$ and 0 otherwise. Since the test statistic $\\log \\frac{Q(o)}{P(o)}$ lives on a discrete grid and cannot take on values between $x_t$ and $x_{t+1}$, it follows that $\\phi^*_{\\tau_1, \\gamma_1}$ and $ \\phi^*_{\\tau_2, \\gamma_2}$ will classify each observation $o$ identically.\n\n> **Q3.** Why is the test that is found on lines 690-698 optimal?\n\nOur response to Question 2 should address this concern as well. Lines 690-698 do NOT identify two distinct tests and choose one as the optimal without proof. Instead, lines 690-698 identify two different parameterizations for the unique and optimal test. One is free to choose either parameterization (or any other!) for implementation. In our implementation, we choose $(\\tau_1 = x_t, \\gamma_1 = 0)$. We will make this distinction between different parameterizations and different tests clear in the final version of the proof (see next).\n\n> **Q4.** It is not clear if Theorem 3.4 claims \"for all\" or \"for some\" $\\gamma$ and $\\tau$.\n\nTheorem 3.4 indeed holds **for all** $\\tau \\in \\mathbb{R}$ and $\\gamma \\in [0,1]$, and we will make this clear by specifying the “for all” quantifier. To clarify this in the proof, in each of the three studied regions of $\\alpha$, we will specify (i) the optimal test and (ii) all possible parameterizations $(\\tau, \\gamma)$ for the optimal test, as described next.\n\nIn the case when $\\alpha = 1$, we have only one possible parameterization for the optimal test: $(\\tau = -\\infty, \\gamma = 0)$. When $\\alpha$ is one of the $k+1$ values in Eq. 42, we have the two parameterizations in Question 2 along with a continuum $\\{ (\\tau, \\gamma) \\mid \\tau \\in (x_t, x_{t+1}), \\gamma \\in [0,1] \\}$ if $t<k$, and $\\{ (\\tau, \\gamma) \\mid \\tau \\in (x_k, \\infty), \\gamma \\in [0,1]\\}$ if $t = k$. Finally, when $\\alpha$ does not fall into any of the remaining categories, we have one unique parameterization $(\\tau = x_t, \\gamma = \\text{Eq (49)})$ for all $t$.\n\nThis covers all $\\tau \\in \\mathbb{R}, \\gamma \\in [0,1]$, and shows that Theorem 3.4 claims holds \"for all'' parameter values.\n\n## Catastrophic Failures\n\n> Figure 5 shows that the $\\delta'$ corresponding to the attack TPR/FPR calibration is very large compared to the standard $\\delta$. The standard $\\delta$ is chosen to be small, as the mechanism that randomly outputs one individual's data is $(0, 1/n)$-DP with $n$ datapoints. I think the paper should discuss how this mechanism behaves with the TPR/FPR calibration. \n\nThis is a great point that we thought about a lot, although a detailed discussion didn't make the final cut in this submission (it will be added to the revised version). The reviewer correctly notes that the standard convention of computing $\\varepsilon$ for $\\delta \\ll \\frac{1}{n}$ is based on the _existence_ of an $(\\varepsilon, \\delta)$-DP mechanism allowing catastrophic failures with probability $\\delta$. Given our calibration in Figure 5 allows for $\\delta > \\frac{1}{n}$, there exists a mechanism achieving our target TPR/FPR with a high probability of catastrophic failure, and the reviewer provided an example of such mechanism.\nHowever, we introduce our calibration approach in the context of choosing a noise scale $\\omega$ for a _given parameterized mechanism_ $M_\\omega$. Most if not all practical mechanisms, including those we investigated (DP-SGD), do not admit catastrophic failures (see, e.g., this [post](https://differentialprivacy.org/flavoursofdelta/)). We argue that the _existence_ of a mechanism achieving our TPR/FPR calibration with a high probability of catastrophic failure is irrelevant when calibrating the noise parameter $\\omega$ of a _specific mechanism_ that we know does not admit failures. Consequently, our methods should only be used for mechanisms without catastrophic failures. We will clarify this in the final version by adding the following paragraph in the Concluding Remarks:\n\n“Our calibration algorithms are supposed to be used with mechanisms that do not admit catastrophic failures, i.e., those that ensure attack TPR of zero when FPR is also zero, or, equivalently, mechanisms whose trade-off curve is such that $T(M(S), M(S’))(0) = 1$ and $T(M(S), M(S’))(1) = 0$ for all $S \\simeq S’$. Although practical mechanisms such as DP-SGD have this property, one can in principle construct mechanisms which do admit catastrophic failures (e.g., a “name-and-shame” mechanism which outputs one of the records in the clear [see, e.g., [Aerni et al. 2024](https://arxiv.org/abs/2404.17399)]). In such pathological cases, standard calibration should be used to ensure $\\delta \\ll \\frac{1}{n}$.”\n\n---\nWe respond to the minor points in the next comment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and feedback. We are glad the reviews found that our framework addresses an important technical problem (pcXQ), provides significant theoretical contributions (pcXQ), and compelling insights (JyJW). We are also glad that the reviews appreciated the practicality of our algorithms (tsqL), the increased utility that our approach enables (Bdkd), the robustness of the experimental results (JyJW), as well as pointed out that the paper is easy to follow (pcXQ, tsqL) and builds a strong case for attack-aware noise calibration (tsqL).

We noticed some general trends in the reviewers' suggestions, addressed next.

**Notation table.** Reviewers JyJW and Bdkd remarked that the paper is notation heavy, and asked for a table summarizing the different terms and their meanings. We agree and will add the notation table in the final version (see below).

**Algorithms for standard and direct advantage calibration.** Reviewers JyJW and Bdkd both asked for a single algorithm detailing how we ensure advantage calibration. We acknowledge that the exact steps for calibration are spread across Sections 2 and 3, and we will consolidate them in the final version. Specifically, we will detail the exact steps as follows:

_Standard calibration._ Inputs: privacy parameters $\eta^\star, \delta^\star < \frac{1}{n}$, privacy profile $\varepsilon_\omega(\delta)$.

1. Find $\varepsilon^\star$ which ensures $\eta = \eta^\star$ for a given $\delta^\star$, i.e., solve Eq. 8 for $\varepsilon$ for fixed $\delta = \delta^\star$ and $\eta = \eta^\star$.
2. Find noise parameter $\omega$ that ensures $(\varepsilon^\star, \delta^\star)$-DP using binary search as described in Sec. 2.3:

	$\min_\omega \text{ s.t. } \varepsilon_\omega(\delta^\star) \geq \varepsilon^\star$.

	This step is exactly Eq. 2.

_Direct advantage calibration (ours)._ Inputs: privacy parameter $\eta^\star$, PLRVs $X_\omega, Y_\omega$.

Find noise parameter $\omega$ that ensures $\eta^\star$ advantage using binary search as described in Sec. 2.3, and using Eq. 11 in Theorem 3.4 to instantiate the $risk_\omega = \eta_\omega = P[Y_\omega > 0] - P[X_\omega > 0]$ function:

$\min_\omega \text{ s.t. } P[Y_\omega > 0] - P[X_\omega > 0] \leq \eta^\star.$

This step is exactly Eq. 13.

**Additional plots and experiments.** Moreover, we attach a PDF with additional results:

1. Trade-off curves for the language modeling experiments, showing a more complete picture of attainable $(\alpha, \beta)$ values in addition to $\alpha \in \{{0.01, 0.05, 0.1\}}$ in the submission (following a question by JyJW).

2. A version of Figure 1 for the image classification experiments with a tight reanalysis of the method by Tramer and Boneh, 2021, using the Doroshenko et al. accountant instead of the RDP accountant to ensure fair comparisons (following a comment by tsqL).

3. Following a suggestion by pcXQ, we added a new experimental setting in which we use attack-aware noise calibration for releasing a single _differentially private histogram_. This is a simple but common usage of DP, appearing as a building block, e.g., in private query interfaces. To make it concrete, we use the well-known ADULT dataset comprising a small set of US Census data, and simulate the release of the histogram of the 'Education' attribute (with 16 distinct values, e.g., “High school”, “Bachelor’s”, etc.). To measure utility, we use the $L_1$ distance (error) between the original histogram and the released private histogram. The plot shows the increase in utility if we calibrate the noise of the Gaussian mechanism (with post-processing to ensure the counts are positive integers) using the direct calibration algorithm to a given level of FPR $\alpha^\star$ and FNR $\beta^\star$ vs. standard calibration over 100 simulated releases with different random seeds. In certain cases, e.g., for $\alpha^\star = 0.1$ and $\beta^\star = 0.75$, our approach decreases the $L_1$ error by 3x from three erroneous counts on average to one.

We address the other comments in individual responses.

---

| Symbol | Description | Reference |
|-|-|-|
| $z \in \mathbb{D}$ | Data record |       	|
| $S \in 2^{\mathbb{D}}$ | Dataset of records   	|
| $S \simeq S'$ | Adjacency relation of neighboring datasets that differ by one record |       	|
| $M_\omega: 2^{\mathbb{D}} \rightarrow \Theta$  | Privacy-preserving mechanism                                     	|       	|
| $\omega \in \Omega$                        	| Noise parameter of a given mechanism $M(S)$                      	|       	|
| $D_\gamma(M(S) \| M(S')) \geq 0,\ \gamma \geq 0$         	| Hockeystick divergence                                           	| Eq. 1 	|
| $\varepsilon \in (0, \infty), \delta \in [0, 1]$	| Privacy parameters in differential privacy                       	| Def 2.1   |
| $\varepsilon: \mathbb{R} \rightarrow [0, 1]$ | Privacy profile curve                                            	| Def 2.2   |
| $\phi: \Theta \rightarrow [0, 1]$ | Membership inference hypothesis test                    	|       	|
| $\alpha_\phi \in [0, 1]$  | False positive rate (FPR) of attack $\phi(\theta)$               	|       	|
| $\beta_\phi \in [0, 1]$  | False negative rate (FNR) of attack $\phi(\theta)$               	|       	|
| $\eta \in [0, 1]$   | Maximal advantage across attacks against mechanism $M(S)$        	| Eq. 7 	|
| $T(M(S), M(S')): [0, 1] \rightarrow [0, 1]$ | Trade-off curve between FPR and FNR of optimal attacks           	| Def. 2.3  |
| $f: [0, 1] \rightarrow [0, 1]$  | A lower bound on the trade-off curve for all neighboring datasets   | Def. 2.4  |
| $P, Q$  | A dominating pair of distributions for a given mechanism $M(S)$  	| Def 3.1   |
| $X, Y$  | Privacy loss random variables for a given dominating pair $P, Q$ 	| Def 3.2   |

Meta-review: The paper presents a novel one-step for procedure for determining the noise level needed to prevent inference attacks on private data, in contrast to the usual two-step procedure that is routed through a DP guarantee. All reviewers agreed that the paper should be accepted.
Decision: Accept (poster)