Optimal privacy guarantees for a relaxed threat model: Addressing sub-optimal adversaries in differentially private machine learning
Authors: Georgios Kaissis
Alexander Ziller
Stefan Kolek
Anneliese Riess
Daniel Rueckert
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Membership Inference Attack
Hypothesis Testing
Data Reconstruction Attack
Security

Abstract: Differentially private mechanisms restrict the membership inference capabilities of powerful (optimal) adversaries against machine learning models. Such adversaries are rarely encountered in practice. In this work, we examine a more realistic threat model relaxation, where (sub-optimal) adversaries lack access to the exact model training database, but may possess related or partial data. We then formally characterise and experimentally validate adversarial membership inference capabilities in this setting in terms of hypothesis testing errors. Our work helps users to interpret the privacy properties of sensitive data processing systems under realistic threat model relaxations and choose appropriate noise levels for their use-case.

Optimal privacy guarantees for a relaxed threat model: Addressing sub-optimal adversaries in differentially private machine learning
Georgios Kaissis Al in Medicine and Healthcare Technical University of Munich
Alexander Ziller
AI in Medicine and Healthcare Technical University of Munich Munich, Germany alex. wiw.er@tuum.dee de
Munich, Germany g kaississttum..... de
Stefan Kolek
Anneliese Riess
Mathematical Foundations of Al
Machine Learning in Biomedical Imaging
LMU Munich
Helmholtz Munich Neuherberg, Germany
Munich, Germany ko ek@math. lmu.de
anneliese enneliese.riesseeeeeeee hut.eeeerrroosscccemmmmotttnnnnh
Daniel Rueckert
AI in Medicine and Healthcare Technical University of Munich Munich, Germany daniel. rueckerrttrk de
Abstract
Differentially private mechanisms restrict the membership inference capabilities of powerful (optimal) adversaries against machine learning models. Such adversaries are rarely encountered practice. this work, we examine a more realistic threat model relaxation, where (sub-optimal) adversaries lack access to the exact model training database, but may possess related or partial data. We then formally charac- terise and experimentally validate adversarial membership inference capabilities in this setting in terms hypothesis testing errors. Our work helps users to interpret the privacy properties of sensitive data processing systems under realistic threat model relaxations and choose appropriate noise levels for their use-case.
Introduction
Machine learning (ML) offers powerful set of techniques for addressing complex problems across various fields, including fields where sensitive data is processed, c.g. medicine or finance. However, the use of sensitive data in ML comes with privacy challenges: It is known that ML models memorise their training data [T. and that some degree of memorisation may be necessary for the best model performance (2). When model memorises private information,
reveal this information when attacked by adversaries. A very important class of attack is Membership Inference (MI) (3), which aims to determine whether the data of specific individual was used to train machine learning model. MI can lead to the disclosure of highly sensitive information about the individual, e.g. that
"GK is also with the Institute of Machine Learning in Biomedical Imaging, Helmholtz Munich and the Department of Computing, Imperial College London.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

they are part of a database of cancer patients which was used to train predictive medical ML system. The importance of studying MI is furthermore derived from the fact that a successful MI attack signifies that the model is also vulnerable to all other attacks such as data reconstruction or attribute inference ("most significant bit" property (4)
Differential Privacy (DP) (5) is formal framework and collection of techniques to furnish objective privacy guarantees for ML model training.
natural counterpart MI, and it is possible to interpret DP entirely through the MI lens, which is known as the hypothesis testing interpretation of DP 7 Given database D and a database D' which differ in exactly one record, hypothesis testing DP quantifies the trade-offs between the Type-I and Type-1l II errors of an adversary using hypothesis test to determine whether a model was trained on D or on D'. This hypothesis test is considered to be optimal in the sense of the Neyman-Pearson (NP) lemma [8]. which makes the DP Threat Model (DPTM) very strong: It assumes that the adversary has full access to the training database, knowledge of the specifications of the DP mechanism and can even deeply manipulate the process of ML. model training itself to their advantage 99. Although this has the benefit that DP is a true "worst-case" guarantee and thus holds for all weaker adversaries, it may be unnecessarily conservative in practice. For instance, the assumption that the adversary has full access to the training data may be unrealistic in settings where this data is tightly access-restricted. As a consequence, previous works also considered threat models with weaker adversaries, i.e. Relaxed Threat Models (RTMs), and experimentally showed that the empirical protection against MI offered by DP mechanisms is much stronger than the upper bound predicted by the DP analysis g [I]. While such empirical investigations provide valuable initial insights, contend that additional formal analysis of specific, practically relevant RTMs can greatly benefit stakeholders in conducting a thorough privacy analysis of ML systems. For example, "privacy certificate" for ML model can include both (1) the MI risk under the DPTM (which holds when "all bets are off") but also (2) the more realistic MI risk under whichever RTM is applicable to the actual model training conditions.
In this work, we study MI in the context of a specific RTM with high practical relevance, in which the adversary has incomplete access to the model's 's training data. An example of this RTM is the training of a predictive ML model on medical data which is generated and stored at a single hospital and never released, whereas the model is shared with third parties. Here, an MI adversary must resort to leveraging auxiliary data from the same distribution as the hospital's target database. A similar attack (offlime M/) was studied in [12 13 14). and also does not use the full database for the attack (albeit for reasons of computational effciency). As MI is equivalent to a hypothesis testing problem, the aforementioned works demonstrate that the Type-I and Type-II errors (i.e. the false positive/false negative rates) of offline MI attacks are higher than MI attacks assuming the DPTM. In this work, we formally derive and validate exact bounds on the error rates of MI attacks against DP noise mechanisms in the aforementioned RTM (which we will refer to as "the RTM" from now on).
Contributions Our contributions as follows: (1) Since MI can be fully characterised using hypothesis testing, we begin by formalising the RTM as a hypothesis testing security game and show that the RTM adversary is strictly sub-optimal in terms of error rates compared the DPTM adversary: (2) Next, we formally derive the "best sub-optimal" hypothesis testing MI strategy in the RTM; (3) We then analyse the error rates associated with this strategy against common additive noise mechanisms used in DP under the RTM. (4) We express these error rates using trade-off functions, which parameterise all achievable Type-I/Type-II error combinations, similar to the approach taken by (7) in defining f-DP. (5) Additionally, we introduce a new metric, X-Detection Resilience (A-DR), which allows us to compare the hypothesis testing capabilities of the RTM and DPTM adversaries, despite their differing threat models. (6) We conclude our study by empirically auditing the proposed bounds and demonstrating accuracy advantages in the training of deep neural networks with DP-SGD.
2 Background
Related work Our work contributes to the ongoing research in three distinct, yet related areas of
privacy-presering ML. Firstly, we aim to augment empirical investigations which use MI to establish
lower bounds on the privacy guarantees of ML systems, with formal guarantees. For instance, (9]
experimentally evaluate several types of adversaries against DP ML workflows, [10] 11] present
empirical privacy analyses of DP-SGD [15), while (16) focus on federated learning. Such empirical
privacy auditing techniques have found their way into software tools such as ML-Doctor
[7 or ML

---

Privacy Meter (14). As mentioned above, our RTM considers an adversary performing MI without access to the (complete) model's training data. This type of MI attack has been studied in several prior works, most notably by Watson et al. [3]. Ye et al. [14) and Carlini et al. [12). who find the adversary's 's hypothesis testing capabilities to be substantially diminished compared to the DPTM. The second line of work related to our paper are formal analyses of MI in the DPTM, such as (T8), who consider a Bayesian adversary or [4]. who bypass the DP analysis and directly study the properties of the underlying distributions. Moreover, [19] and (20) are rooted in hypothesis testing theory like our work, but only consider threat models equivalent to the DPTM, while (2T] consider restricted adversaries, albeit not through the hypothesis testing lens. Lastly, we adopt the recent development of using functions (rather than numbers) to parameterise privacy guarantees, which is becoming common practice in the DPTM 7 22 23 but has not yet been used to study threat model relaxations. Our paper unifies these strands of work by introducing formal guarantee in the RTM, which allows for more nuanced analysis of the privacy risks associated with machine learning models.
Differential privacy DP (5) is stability condition on randomised mechanisms requiring that their outcomes should be approximately equally likely when the data of a single individual is added removed from the input database. Throughout this work, we will consider the scenario of ML model training, where DP is realised through an additive noise mechanism. We consider deterministic model training function q- The global sensitivity A O of q is defined A su D.D.DDD''' || (DD) - q(Dill where the sup is taken over all pairs of neighbouring databases D = D' which differ in a single record. P A is measured in some norm, which we will indicate by subscript wherever relevant (e.g. A1). An additive noise mechanism (or just mechanism) M maps databases and probability distributions to a (model) parameter space θ. Its outputs are of the form 0 = (X) + 2, 2 ~ 2, where Z is a noise distribution. Since q and the database are considered deterministic, 0 is random variable induced by the randomness of Z. Unless otherwise indicated, .M will be realised through distributions 2(14, E) supported on the real line which admit a density. We assume that & is fixed and public information and that 2 is shift invariant. In other words, M(D)= = (g(D) + E)) ~ 2(g(D),E) () and M(D) = (q(D') + 2(0,E)) ~ (()()),,
In the hypothesis testing interpretation of DP 6 7 24). the adversary attempts to determine whether 0 was trained on D or D' using a classicallfreequentiii hypothesis test. The adversary considers the hypotheses Ho 9 ~ M(D) vs. M1 B ~ MMD') and their reverse, i.e. Hu 8 ~ MM(D) vs. H2 8 ~ M(D). Ho and H. are called the null and alternative hypothesis, respectively. The aim of the hypothesis testing problem is to distinguish between MDD) and M(D') using pair of decision rules (tests). Let o, ø' be tests with Type-I error rate as = E (M) and Type-II error rate 3,p = 1- (0) (identical for Φ¹). The adversary's s goal will be to maximise their power 1- B at fixed level since the fundamental trade-off in hypothesis testing is that and 3 cannot be minimised simultaneously 225 All achievable a/ pairs for a given adversary/test combination expressed by pair of functions the unit square, called the trade-off functions T and T
T is defined through the test di M(D) vs. M(D') as (TM(().MM(') whereas 7-1 (M(( is defined using d'. The inf is taken over the set of tests which can be constructed in a given threat model, in this case the DPTM. For mechanisms with symmetric noise density, 7' = T T allowing us to consider only a single trade-off function. In general, one takes the symmetrisation/cce cwtissttiiiiooooeiffccttooooooon T' and 7-1 denoted 11 which creates a single, symmetric trade-off function. Since trade-off functions fully characterise the adversary's 's error rates, they can be used to compare the privacy guarantees of different mechanisms and/or different threat models. In particular, the closer the trade-off function's 's graph is the line 3(a) = 1 a, i.e. the off-diagona of the unit square, the stronger the implied privacy guarantee of the mechanism is. The notion of expressing DP guarantees based on comparison of C(T, T") with a "reference" trade-off function f is called f-DP 7
= inf (As : as S a).
Definition A mechanism M satisfies f-DP, if D ~ D' holds that C(T, ((T,T~")(a)) 2 fla)a& E [0, for reference trade-off function f (see Figure 2 of (7) for an example).
A pair of distributionss Z(μ1 E), Z(u2, E) is called a dominating pair (22 for M if. VD, D' D
D', (VT.T->)aa 2 C(T (( ((Z((z.)) 2(, [)aaaaaa E 1].
"In particular, we will assume databases are true sets and that D' is constructed from D by adding or removing a single record. The neighbouring relation is denoted x..
3

---

For example, the dominating pair for the Gaussian Mechanism (GM) is (N of), o²)) and for the Laplace Mechanism (LM), it (Lap(0, b), (. b)). The dominating pair distributions thus exhibit the greatest effect size (in this case 41/b or Az/n), allowing for the construction of the trade-off functions whose graphs are farthest from the off-diagonal of the unit square. In other words: the construction of the trade-off functions is determined by the hypothesis tests with the greatest power 1 - 3 under a specific threat model, evaluated at the dominating pair distributions.
In the DPTM, Ho and H, are both simple hypotheses of the form Ho 0 E Oo C vs. H1:0- E
O1 C è with ||@u]l || ||@:|| = 1 and Ou n = 0. The reason is that the distributions of M(D) and M(D') are fully specified because the adversary can evaluate q( () and (D)). The NP lemma (8] states that, for simple vs. simple hypothesis tests such as the ones in the DPTM, the uniformly most powerful (UMP) level a tests 6 and ø' (with the highest power 1 - B at a specified level a over the entire range of 0, in this case (D) or ((D)) can be constructed by thresholding the (log-)
Likelihood Ratio (LRs) A/A of the mechanism's 's outputs 0 under 1) and D':
L(0 MD)) (0) = log C(0) M(D)) cc and (0) = log C( M(D))) Sc.
L(O) M(D'))
where c E R is the critical value. The trade-off functions in the DPTM are then constructed from the distributions of A/A' evaluated at the dominating pairs under the respective Ho and Hi (also called privacy loss distributions (23)). Since the DPTM adversary enjoys the optimality properties of the NP lemma, will refer to this adversary ANP.
3 Hypothesis testing in the RTM
The trade-off function's ' form for a given threat model depends only on the test statistic's distributions under Ho and H1. Our strategy for the rest of the paper is thus: (1) Derive the optimal tests the adversary can construct in the RTM; (2) Specify the test statistic distributions for these tests, and (3) Construct the trade-off functions for given mechanism using these test statisties, which will allow us to tightly bound the adversary's 's error rates and compare them to the DPTM. We first recall a general result, specifying how trade-off functions are constructed from test statisties.
Definition 2 (Trade-off function construction). Let P. Q be the distributions of a test statistic under Ho and Hi respectively and let & P.QQ denote their cumulative distribution function (CDF), V P/Q their survival function (SF) and & P/Q' Le
P/Q their respective inverses (iCDF, iSF). Then, we define:
T(a) 22 V (a)) and (a) = p (a)).
(1)
For example, in experimental studies, empirical proxies of the test statistic distributions are evaluated by training shadow models 3). Then, the empirical trade-off functions are constructed, which
parameterise the error rates of the empirical adversary under a specific threat model [1] 12 [4]. We
will utilise this strategy later to validate our theoretical bounds empirically. For our formal analysis
on the other hand, we will derive exact expressions for and T
RTM security game For reasons which will soon become clear, we will refer to the adversary under our RTM as sub-optimal adversary (ASS0) and use a formal security game, similar to the one used to define the DPTM (see e.g. Section 3.1. of (4)), which proceeds between a neutral/trusted curator C and Ao
We consider single-round, non con-interacttve protocol.
Step I: The adversary ASO constructs a database D = (II,... In C DD decides on a training
function g. DP mechanism M and sends them to the curator C:
Step 2: C flips a bit If b = O, they fix X = D. If b = 1, they choose a singleton {x*} C D', where IB C D and D n D3 = {x*} and fix X = D U {x*). They then train a model 0 E θ on X using and M (6 may also be a gradient) and send 0 to A5,
Step 3: .4 decides if Ho : 0 ~ M(D) or H1 : ~ .MDD);
Step 4: If S5 is correct, the MI attack is successful, privacy is breached and the game is won.
The key difference between the RTM and the DPTM is step 2: As5 has no access to the point xx which may be added by C, and by extension, no knowledge of the exact value of (D)). In step 3, As can therefore only decide ~ M(D') by rejecting that 0 ~ M(D), but not by directly confirming that 0 ~~ M(D)).

---

The hypothesis testing capabilities of the RTM adversary are identical to those of an offline MI adversary. Offline MI attacks are used in previous works to audit the privacy of ML model training
13 14 and decide whether x² is part of the training data or not without actively training shadow models on databases containing
12
Equivalently, offline MI is MI by exclusion (i.e. inferring 0 ~ M(D') by rejecting Hg O ~ M(D)) In offline MI, this is done for reasons of practicality and computational efficiency [12), while in the RTM, it by design. Nonetheless, the resulting error rates are identical and our bounds thus can be used to characterise offline MI.
RTM: Formal analysis M is an additive noise mechanism based on the distribution 2, thus Ho 0 ~ M(D is equivalent Ho 0 ~ (.) Since (P) is computable by A through access to D, the likelihood [(0) 2 (q(( ()()),))))))))))) {)) is also computable and Ho is a simple hypothesis of the form
o, ||Oa|| 1, exactly like the DPTM. However, the likelihood [() 2(g(D"), E)) is not computable without access to D' and Ho is a composite hypothesis of the form 0 E θ Oo
with ||0 Goll > 1 because it depends on the unknown value of (D)). The following is direct consequence of the NP lemma, which holds only for simple vs. simple hypotheses [25]
Lemma 1. In the RTM, no UMP level a test exists for all possible values of (D'), Le. AA E @ \ 16- Thus, Ho vs. Hi (and Hi vs. Ha) are each not decidable by single test.
This implies that ASO is necessarily weaker than ANP, i.e, cannot achieve the same power - B at a given level a for all values of the parameter of interest; to thus establish the optimal tests in this sub-optimal setling, ASO must consider specific value ranges of (DD)) separately. In the following, we will call two tests equivalent if they have the same power at level a for all values of the tested parameter. Moreover, we will limit our description to Ho 0 ~ M(D) vs. Hi : 0 ~ M(D'), as Hi vs. Ho is handled identically.
Lemma 2. The composite LR test Ha 0 (() vs. H4 0 Z(g(D"), E) equivalent to letting O ~ 2(,, E) and simultaneously conducting two individual one-sided LR tests and r' with null hypothesis J = O and alternative hypotheses -À S μ < 0 r and 0 < p S A A r', where (DD) gDD and A is the global sensitivity of q.
Thus, _AS can leverage known facts about q and M to limit the value ranges for the alternative hypothesis, but, as (D') is unknown, must "split the problem" into two individual tests. The individual tests are then UMP level a under the following pre-condition.
Lemma 3. The individual LR tests T and r' are UMP level a if the noise distribution 2 has the monotone likelihood ratio property (MLRP). The Laplace Mechanism (LM), Gaussian Mechanism (GM) and the Chisson-Subsampler Gaussian Mechanism (SGM) all have the MLPR. Moreover, the power of both tests is maximised when |||||||||| = llg(D") DD)l = A.
This lemma intuitively states that, while there is an optimality condition associated with the tests that can be constructed in the RTM, it is not the same optimality condition as the NP lemma guarantees in the DPTM. In particular, although A4O can construct a pair of tests which are optimal (UMP level a). they are only optimal for specific parameter value ranges rather than for all possible parameter values. The lemma also states that it suffices to consider the tests μ 0 vs. | the trade-off functions, as these correspond to the highest effect size at fixed ç. In other words, dominating pairs remain dominating pairs in the RTM. Next, we provide two convenience lemmata, which allow A to conduct both tests simultaneously.
A when constructing
Lemma 4. If the density of Z is additionally symmetric about the location parameter, the simulta- neous individual LR tests and r' are equivalent to performing a single test using the magnitude of the observation as a test statistic, i.e. letting ||@] || ( {\]l and testing Ho ||pl| vs.
Hi : || > O. The power of this "combined" test is maximised at ||||= =
Lemma 5. For (not necessarily symmetric) Z the Generalised Likelihood Ratio Test (GLRT) using the test statistic log C10 ((p.E)) simultaneously conducting and r'. The GLRT's power is maximised al jt = A.
2 (0,,)) where ja the maximum likelihood estimate of μ is equivalent to
We stress that, while the two tests are UMP level a and can be "combined" into one test, the combined test is not UMP level a over the whole range (by Lemma 1). To construct both tra functions, the steps above are either repeated for Hi vs. Ho, or the trade-off function for Ho vs. Hi is inverted directly, i.c. in closed form numerically.
5

---

X-Detection resilience Next, we introduce a measure for A optimal achievable error rates under the RTM, inspired by f-DP: For each mechanism. we create pair of trade-off functions j and j These parameterise the error rates of the UMP level tests against the dominating pair distributions of a given mechanism M in the RTM. Next, we "unify" the functions by symmetrisation//onvexifff to obtain a single, symmetric trade-off function J - B, which expresses all optimal error rates of u against M. Finally, we compare J to a reference trade-off function If lies on or above X, A cannot achieve lower 3 for any a in the task of detecting the presence of x² in D' by observing and we say that M satisfies X-Detection Resilience (A-DR).
Definition 3. Let r E R be a test for M(D) vs. M(D') and r' E R be a test for M(D') vs. M(D), where L is the set of LR tests which computable in the RTM. To construct J. level o, then obtain j intrese aommetrriiaion/coovexeccttnn J C(j.J 1. We say that mechanism M satisfies X-DR, ifr some reference function X and VD, D' D = )), it holds that J(a 2 A(a) Va E [0,
Ot S a and j- j- inf,'est (3r : aOp" S a). Then compute the
We remark that computing the symmetristtion/onneeiicalll measure to circumvent the necessity work with both and j separately. The concrete algorithm for computing C for any trade-off function pair can be found in Definition E. of the Appendix to (7.
C(.j is only a convenience
Since A is weaker than AP,, expect the trade-off functions characterising their error rates to lie on or above the trade-off functions for the same mechanism under the DPTM (see Figure [
However, it is important to remark that X-DR is not DP guarantee, although the opposite holds true.
Lemma 6. If a mechanism satisfies f-DP, it also satisfies f'-DR, with f'(a) 2 f(a) Va E [0, [0.
Moreover, since X-DR defined conditional on a restriction of ASO's background knowledge, not resilient to post-processing through auxiliary information. However, weaker condition holds:
Lemma 7. mechanism satisfies f-DP and f'-DR with f 2 f, arbitrary post-processing can only deteriorate privacy up to the f-DP guarantee.
follows that X-DR is not closed under adaptive composition. In fact, no privacy relaxation assuming restricted background knowledge is closed under adaptive composition [26). However, mechanism- specific guarantees can be given for non non- adaptive composition, where the data/meehannim parameters fixed in advance and all intermediate models/gradients released .450, This covers the standard DP-SGD setting and studied below.
4 Mechanism-specifie analysis
Since precisely quantifying DR for a specific noise mechanism requires knowledge of the RTM trade-off functions, we now provide methods to compute j and j for various DP mechanisms. The construction of = C(j.j -1) independent of the specific form of j.j- . By definition for all j.j ((0) = j (() = -] 0 and [0, 1].
Laplace Mechanism The LM with scale b on function with global ( fi-sensitivity A outputs ((X) + Lap(O, b). The LM has a symmetric noise density, thus, the magnitude distributions can be used test statistics according to Lemma 4. Under Ho. the test statistic follows exponential distribution, while under H4, it follows the (uncommon) folded Laplace distribution [27]. Both distributions admit closed-fee formf expressions for their CDF, SF, iCDF and iSF, thus the trade-off functions can also be characterised in closed form.
Theorem 1. Let μl = As/b. The LM satisfies ((jaap(a) ( (a)) (D) with:
[ap { exp (-pi) sinh (log (a)), exp(-n)) otherwise,
(2)
{1 cosh (M1),
and
exp (m) + exp (2p1)+1' a < 1/221122expp2121 (-pi) a-1 cosh (
Jrap (a)
(3)
otherwise.

---

Gaussian Mechanism The GM with covariance matrix I²I on d-dimensional function q with global lg sensitivity A₂ outputs (X) + +V r2 Like the LM, it also has a symmetric noise density, thus the (squared) magnitude distributions can be used as a test statistic. Let x² of) be the chi-squared distribution with d degrees of freedom, i.e. the distribution of (IAV(,, o I. Let xa (13, o²) be the noncentral chi-squared distribution with d degrees of freedom and noncentrality parameter 1 = 43/0², i.e. the distribution of [[N(v, I2 with |||| A. As in Definition 2, Φ V, --1 and V denote the CDF, SF, iCDF and iSF of the subscripted distribution, respectively.
Theorem 2. Let μ12 22j0. The GM satisfies (LicM(a), ( with:
(I (Q)) and jeM xx3(0,0)) + (0)
(a)((a) 1b x2
These functions have no general analytic representation, but are easy to evaluate numerically. However, an analytic representation is available for j(x) at d = 1. We discuss the importance of d = below. Corollary 1. For d = 1, j(a) admits the following closed-form representation:
jama(a dd= 1) @v(0.1) (WNo.)) (0/2) - 122) - V.v(o.1) (wol,,1 (4/2) + 112)
(5)
Next, we study non-adaptive composition, where database and mechanism parameters are fixed ahead of time, and all intermediate results are released to ASo, This setting is often encountered, e.g. in standard DP-SGD.
Lemma 8. Ler GM,, GM,, be GMs with noise variances o² of on functions with sensitivities Aza, Agt, respectively. Then, the non-adaptively composed mechanism GMC has trade-ofy off functions:
jGMO(a) 1b x(()
(2)00,2)(00) (a)) and jaMc(a) xx3(0.0?)
( (x)))..0))()))
(6)
with Kr = (22 1/03 and of o o0/4
The GM moreover exhibits specific asymptotic behaviour when the query dimensionality d and/or the number of non-adaptive compositions increase.
Theorem (Blessing of dimensionality in the RTM). Consider a GM on a function with sensitivity
A and noise variance I²1 such that Anfo < 1. Let P2 Aafo. As d and/or the number of non-udaptive compositions N increase, JGM and JeM tend to the common form:
:-1
Th (a).))(a)
V2NH3
( (WNio.)(a) -
P2 2d
se 2N
(7)
2N
+ 2
2N +
As d increases for fixed N. Je and jot become symmetric and eventually both tend to (x(0,1) I (xlo.)(a)) - a, i.e. the Type-I and Type-II errors are equal and ASS's test is no better than random guessing. Intuitively, this can be understood by considering that the magnitude of (i.e. the test statistic) is influenced less by its individual components as dimensionality increases (28). Therefore, at d > 1, the GM provides progressively stronger X-DR guarantees than for scalar queries. However, as the adversary can leverage their knowledge of the model to design a database which influences only single coordinate of the weight/gradient vector, we mostly use d = 1 as a worst-case scenario below. In practice. such a worst-case database may be unrealistic, and the aforementioned result can thus be applied to obtain tighter bounds on MI success in specific scenarios. We note that, in the DPTM, the trade-off function of the GM is always independent
and has VNda/a. & denotes N-fold composition.
the form N Dx((o.) ( (a) - (o) - F
The similarity between faM and Equation 7 consequence of the central limit theorem-like phenomenon (7]. Despite the similarity between the functional forms, we stress that this does not mean that the asymptotic X-DR guarantee implies a GDP guarantee, although the converse holds.
We say that this mechanism satisties gaGaassian DP (GDP).
7

---

Poisson-Subsampled Gaussian Mechanism (SGM) The SGM is relevant in private deep learning [15). On a d-dimensional function q with global eg-sesiitiv A2, the SGM with diagonal covariance matrix rº1d samples a mask S ~ Ber(p)", where S E {0,1) 1) and Ber(p) denotes a Bernoulli
distribution with probability p and outputs (X) + S Z, Z ~ o2), where @ is the Hadamard product. The dominating pairs are (N(0, (1 D)A - pN ))) and
((1 pp) d²) + p0 , )) (22). Although we have shown in Lemma 3 that the SGM satisfies the MLRP, the test statistic distributions under My and H1 do not have tractable form. We thus proceed numerically: First, we instantiate jGM and JCM for the standard GM as shown above, then use the following general result to amplify the trade-off functions directly.
Lemma 9. Let T(A, (a) be a trude-off fanction between two general distributions A, B repre- senting mechanism outputs. The trade-off/ee functions for the sub-sampled mechunisms are given by T(A, - A + pB) (a) = (A, (a) + (1 (1 - o) and by its inverse.
We thus obtain the amplified functions jp and Jp from which we compute JSGM 3p It follows that the SGM satisfies -sR. This subsampling technique can also be applied to other mechanisms [2] 23 An example for the LM is shown in the Appendix. Composition of mechanisms other than the GM is also handled numerically through direct composition of the test statistics as described in 7 Definition 3.1. ff.
5 Experimental evaluation
RTM/DPTM trade-off function comparisons Figure shows trade-off functions for the LM, GM and SGM in low privacy (low noise) and high privacy (high noise) settings to compare the error rates in the RTM to the DPTM. The pair of asymmetric DPTM trade-off functions j.j is combined into a single symmetric function J CO.J (symmetrified) trade-off function f for the same mechanism under the DPTM for reference. All RTM curves G.j_l J) are closer to the off-diagonal than f. indicating that As has lower MI attack success than AbP, The "blessing of dimensionality" is shown in subfigure (f): at d = 30, stronger X-DR is preserved compared to 1. In the DPTM, the GM enjoys no such privacy amplification.
cyymmetrisation/onnexiiiiiiiii
We also plot the
1.0
1.0
1.0
frup
fux
fex
jax
Riap
Jush
Ju
Jue
Joa
0.5
m...5
m...5
0.0
0.0
0,3
0.0
0.5
0.0
0.5
0.0
1.
(a) LM, high privacy.
(b) LM,, low privacy
(c) GM,, high privacy
1.0
1.0
1.0
fox
Sou, 30
jeM
jr
Jav, d 1
Jay. d 30
Jus
Jaca
0.5-
0.5
0.5
0.0
0.3
0.0
0.5
1.0
0.0
0.5
1.0
1.0
01.5
1.0
(d) GM, low privacy
(c) SGM
(f) GM, high-dimensional
Figure 1: Exemplary trade-off functions for various mechanisms: (a) and (b): LM at 41/o 0.6 and
A1/b = 1.5, respectively. (c) and (d): GM at Aa/o = 0.6, = and A2/o = 1.5, d = 1, respectiivy,
(e): SGM at An/o- = 0.2, d 1, N = 30, p 0.4. (f): GM at As/o at d = 1 vs. d = 30.
8

---

Asymptotic behaviour and power function of the GM Figure 2a shows the asymptotic behaviour of a GM with Au/o = 1/5. d 300 and N 150. The computed trade-off functions become symmetric, approach the off-diagonal and match the plot of the analytic form in Equation 7 exactly, even a modest number of compositions. Figure 2b plots the power 1 - 3 of an MI adversary vs. 3 the Az/o-ratio at a fixed a = 10-3 for the GM and Figure 2c for the SGM assuming the worst case of a one-dimensional learning task and a sampling rate of 0.3. The curve for the DPTM in 2c was created using the formula from (29). As anticipated, the adversary has lower power throughout in the RTM compared to the DPTM, and the loss of power is amplified through subsampling.
1.0
10-2
JCM
10-1
RTM
RTM
JCM
DPTM
DPTM
Aualytic
0.0.5
10-
0.0
10
0.0
0.5
1.0
0.0
0.5
1.0
Aife
(a) GM: Asymptotic behaviour
(b) GM: Power vs.
Sa/n
(c) SGM: Power vs. Az/a
Figure 2: Asymptotic behaviour of the GM and power analyses of the GM/SGM.
MI attacks on DP ML. models To test the tightness of our theoretical bounds, we now perform an empirical audit using state-of-the-art offline MI attacks on ML models trained with DP. Recall that, despite the nominal difference the threat model, the offline MI adversary and the RTM adversary compute the same tests and thus have the same capabilities. Each auditing run produces a pair of empirical trade-off functions shown in green and blue. These are compared to the theoretical bound, shown in orange. If the empirical curves crossed below the theoretical one, this would indicate lack of tightness in our theoretical bounds. All results are shown as averages with standard deviation across 1024 runs for a single step of a one-dimensional synthetic binary classification task, since are interested in the worst-case scenario under the RTM. Figure 3a shows the results of the LiRa offline MI attack introduced in (1). where As trains shadow models on D and fits Gaussian likelihood to their confidence scores. At A2/a = 1, this logit space auditing technique already nearly perfectly matches the theoretical bound. A further improvement is achieved by implementing the very recent auditing technique presented in [1], also at 4a/a = 1. Here, a worst-case gradient with magnitude A ("Dirac canary") is inserted and the hypothesis test takes place in gradient space instead of logit space. As seen in Figure 3b the theoretical curve is matched exactly by the empirical one.
So far, we have assumed that A can leverage their knowledge of the model to design worst- case database which influences only a single coordinate of the gradient. This is useful for auditing purposes, but does not necessarily mirror real-life training. We therefore also repeat the gradient space attack against a linear neural network with a 50-dimensional latent space trained on the diabetes dataset (30]. Figure 3c shows that, when the adversary cannot reduce the effective dimensionality of the gradient, the hypothesis test loses substantial power compared to d d= (dashed line) at 42/a = 2 and the trfde-off functions become symmetric, exactly verifying Theorem 3.
Additional results for auditing the LM and SGM are shown in the Appendix.
Benefits for ML model training We next demonstrate that the tighter privacy bounds of the RTM translate to tangible improvements in terms of accuracy/privacy trade-offs in deep learning applications. We performed experiments on three classification tasks: CIFAR- 10 using ResNet-9, ImageNet using ResNet-18, and Stanford SNLI using a BERT transformer. In each case, we fixed final privacy guarantee (in terms of (c, 8(E)) or equivalently (a. 3))))) for the DPTM and then trained set of models up to this privacy guarantee. We then computed the DP-SGD noise scale corresponding to the same hypothesis testing privacy guarantee for the RTM, and re-trained the models for the same number of steps. For all datasets, the enhanced privacy guarantees of the RTM allowed us to obtain models with higher out-of-sample accuracy (e.g. up to 14% higher on CIFAR-10 at Re 1) for the nominally same membership inference guarantee by lowering the DP-SGD noise scale. These results are illustrated in Figure 4 and experimental details can be found in the Appendix.

---

1.0
1.0
1.3
Bound
Bound
Bound
va.
vs.
=1
D' vs D
D' vo. D
D vs. D
17 vs. D
0.0.3
0..55
0.0.5
0.0
0.0
0.31
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
(a) Logil space attack
(b) Grudient space attack
(c) High-dimensional latent space
Figure 3: Auditing our theoretical bounds using offline MI attacks.
0381
ILS
0.75
37
Tap-1 Aveuary
Top-1 Aceumeyy
0.
Top-1
0.5
0.00
0.4
0.00
250
200
100
Stero
Epoch
(a) CIFAR-10
(b) Stanford SNLI
(c) ImageNet
Figure 4: Deep learning with DP-SGD. Calibrating the noise scale to the RTM privacy guarantee results in substantially improved Top-1 validation set accuracy compared to calibrating to the DPTM guarantee. (a) CIFAR-10: 0.81 + 0.01 vs. 0.67 = 0.01 at (1,10-5 -DP (b) SNLI: 0.80 + 0.005 vs. 0.78 + 0.005 (1, 1.8 10-6) -D-D) (c) ImageNet: 0.48 0.46 at (10, 10 10-O)-DP. Error bars denote standard deviation across runs.
Improved bounds data reconstruction attacks As discussed above, successfully defending against MI attacks implies that all weaker attacks such as data reconstruction will also be unsuccessful. In the Appendix, we demonstrate that, in the RTM, data reconstruction adversaries also suffer diminished success rate compared to the DPTM, as measured in terms of Reconstruction Robustness which can be bounded directly through its relationship hypothesis testing 33
31 32
Conclusion
In this work, consider threat model relaxation of high practical relevance, where the adversary does not have access to the candidate record in question when performing an MI attack. Our results provide a complete characterisation of the adversary's optimal error rates under the restrictions of the RTM, including at fixed low Type-I error rate which is particularly meaningful for privacy- sensitive applications such as medical or financial data [12]. Moreover, they allow for fair and direct comparison between the privacy properties of noise mechanisms under different threat models. Our results thus guide individuals who train ML systems sensitive data in the selection of the appropriate noise magnitude to better balance model accuracy vs. privacy protection.
We acknowledge the following limitations. We focused on additive noise mechanisms and the global model of DP in this work. An extension of our results to local DP, mechanisms, mechanisms with discrete outputs and private selection mechanisms is natural next step. Moreover, our analysis considers the case of non-adaptive composition, which applies to some, but not all, relevant ML tasks. An investigation of adaptive composition scenarios (considering potential correlations between mechanism outputs) would be interest to expand the scope of our guarantees. Last but not least, we regard the analysis of adversaries who knowledge of the sensitivity, noise magnitude or noise type) as a promising avenue for future work.
more limited in their background knowledge (c.g.
10

---

Acknowledgements
This work was supported by Helmholtz Junior Research Group grant GK. This work has been funded by the German Federal Ministry of Education and Research and the Bavarian State Ministry for Science and the Arts through the Munich Centre for Machine Learning (MCML). The authors of this work take full responsibility for its content. This research was supported by the German Ministry of Education and Research (BMBF) under Grant Number 01ZZ2316C (PrivateAIM), This research was supported by the Konrad Zuse School of Excellence in Reliable Al (RelAI).
References
[1] Nicholas Carlini et al. "The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks." " In: USENIX Security Symposium. Vol. 267. 2019.
[2] Vitaly Feldman. "Does learning require memorization? short tale about a long tail". In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020,
pp. 954-959.
[3] Reza Shokri et al. "Membership inference attacks against machine learning models". In: 2017
IEEE symposium on security and privacy (S&P). IEEE. 2017, pp. 3-18.
[4] Saeed Mahloujifar et al. "Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms". In: arXiv preprini urXiv:2204 00444.0606666 (2022).
[5] Cynthia Dwork et al. "Calibrating noise sensitivity in private data analysis". In: Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer. 2006, pp. 265-284-
[6] Larry Wasserman and Shuheng Zhou. "A statistical framework for differential privacy". In: Journal of the American Statistical Association 105.489 (2010), pp. 375-389.
[7] Jinshuo Dong, Aaron Roth, and Weijie Su. "Gaussian Differential Privacy". In: Journal of the Royal Statistical Society (2021).
[8] Jerzy Neyman and Egon Sharpe Pearson. "IX. On the problem of the most efficient tests of statistical hypotheses". In: Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character 231 231.694-706 (1933), pp. 289-337.
[9] Milad Nasr et al. "Adversary instantiation: Lower bounds for differentially private machine learning". In: 2021 IEEE Symposium Security and Privacy (SP). IEFE. 2021, pp. 666-882.
[10] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. "Auditing differentially private machine learning: How private is private SGD?" In: Advances in Neural Information Processing Systems 33 (2020), pp. 22205-22216.
[11] Milad Nasr al. "Tight Auditing of Differentially Private Machine Learning". In: arXiv preprint ar32iv2300..000 07956 (2023).
[12] Nicholas Carlini al. "Membership inference attacks from first principles". In: 2022 IEEE Symposium on Security and Privacy (SP). IEEE. 2022, pp. 1897-1914.
[13] Lauren Watson et al. "On the importance of difficulty calibration in membership inference attacks". In: arXiv preprint arXiv:2111. 1..8440 (2021).
[14] Jiayuan et "Enhanced membership inference attacks against machine learning models". In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022, pp. 3093-3106.
[15] Martin Abadi et al. "Deep learning with differential privacy". In: Proceedings of the 2016
ACM SIGSAC conference on computer and communications security. 2016, pp. 308-318.
[16] Samuel Maddock, Alexandre Sablayrolles, and Pierre Stock. "CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learning". In: arXiv preprint arXivv2210.02911 (2022).
[17] Yugeng Liu et al. "(ML-Doctor): Holistic Risk Assessment of Inference Attacks Against Machine Learning Models", In: 31st USENIX Security Symposium (USENIX Security 22). 2022, pp. 4525
[18] Alexandre Sablayrolles et al. "White-box vs black-box: Bayes optimal strategies for member- ship inference". In: International Conference on Machine Learning. PMLR. 2019, pp. 5558- 5567.

---

[19] Zuxing Li. Tobias Oechtering, and Deniz Gündüz. "Privacy against a hypothesis testing ad-
versary". In: IEEE Transactions on Information Forensics and Security 14.6 (2018), pp. 1567- 1581.
[20]
Benedetta Tondi, Mauro Barni, and Neri Merhav. "Detection games with fully active attacker".
In: 2015 IEEE International Workshop on Information Forensics and Security (WIFS). IEEE
2015. pp. 1-6.
[21]
Kamalika Chaudhuri, Jacob Imola, and Ashwin Machanavajhalla "Capacity bounded differen- tial privacy". In: Advances in Neural Information Processing Systems 32 (2019).
[22] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. "Optimal accounting of differential pri- vacy via characteristic function". " In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 4782-4817.
[23] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. "Numerical composition of differential privacy". In: Advances in Neural Information Processing Systems 34 (2021), pp. 1 1631-11642
[24] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. "The composition theorem for differential privacy". In: International conference on machine learning. PMLR. 2015, pp. 1376-1385.
[25] E.L. Lehmann and Joseph P. Romano. Testing Statistical Hypotheses. 4th ed. Singapore: Springer Nature, 2022. ISBN: 978-3-030-705755
[26] Damien Desfontaines and Balázs Pejó. "Sok: differential privaciee.. In: Proceedings on privacy
enhancing technologies 2020.2 2 (2020), pp. 288-313,
[27] Yucui Liu and Tomasz J Kozubowski. "A folded Laplace distribution". In: Journal of Statistical
Distributions and Applicattoons 2.1 (2015), pp. 1-17.
[28] H. Urkowitz. "Energy detection of unknown deterministic signals". In: Proceedings of the IEEE 55.4 (1967). pp. 523-531.
[29] Zhiqi Bu et al. "Deep learning with gaussian differential privacy". In: Harvard data science review 2020.23 (2020), pp. 10-1162.
[30] Bradley Efron et al. "Least angle regression". In: The Annals of Statistics 32.2 (2004), pp. 407- 499.
[31] Borja Balle, Giovanni Cherubin, and Jamie Hayes. "Reconstructing training data with informed adversaries", In: 2022 IEEE Symposium on Security and Privacy (SP). IEEE. 2022, pp. 1138-
156.
[32] Jamie Hayes, Saeed Mahloujifar, and Borja Balle. "Bounding Training Data Reconstruction in DP-SGD". In: arXiv preprint S2kiv:2302.0222: (2023).
[33] Georgios Kaissis et al. "Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy". In: arXiv preprint #xXiv:2377.03928 (2023).
[34] Samuel Karlin and Herman Rubin. "The theory of decision procedures for distributions with monotone likelihood ratio". In: The Annals of Mathematical Statistics (1956), pp. 272 299.
[35] Antonio De Maio. Steven M Kay, and Alfonso Farina. "On the invariance, coincidence, and statistical equivalence of the GLRT, Rao test, and Wald test". In: IEEE Transactions on Signal Processing 58.4 (2009), pp. 1967-1979.
[36] Jess Marcum. "A statistical theory of target detection by pulsed radar". In: IRE Transactions on Information Theory 6.2 (1960), pp. 59-267.
[37] Helena Klause et al. "Differentially private training of residual networks with scale normalisa- tion". In: arXiv preprint 22X3v:2203.00322 (2022).
[38] Soham De et al. "Unlocking high- tigh-accuracy differentially private image classification through
scale". In: arXiv prepriní arXiv:2204. /3650 (2022).
[39] Jacob Devlin et al. "Bert: Pre-training of deep bidirectional transformers for language under- standing". In: arXiv preprint / /8000400 (2018).
[40] Alexey Kurakin et al. "Toward training at imagenet scale with differential privacy". In: arXiv preprint arXiv:2201.12322 (2022).
[41] Qinqing Zheng et al. "Sharp composition bounds for Gaussian differential privacy via Edge- worth expansion". In: International Conference on Machine Learning. PMLR. 2020, pp. 11420- 1 1435.
[42] Alexandre Lacoste et al. "Quantifying the Carbon Emissions of Machine Learning". In: arXiv preprint 17X.v:1900009700 (2019).
12

---

7 Supplementary Material
7.1 Additional results
Subsampling and auditing the Laplace Mechanism As mentioned in the section on the SGM, numerical subsampling also be applied mechanisms other than the GM. Figure Saauueeaassooon shows the trade-off function curves for the LM without subsampling in orange and the subsampled curve for A1/b = p, 0.3 blue. Similar to the GM, the MI error rates in the RTM (and thus the privacy guarantees) are amplified with sub-sampling.
Figure SggureSbccomin 5b the results empirical privacy auditing for the LM from the main manuscript. The gradient space auditing technique [IT] is again applied to mne-dimensional learning task as described in the main manuscript, however the LM is used instead of the GM. Once more, the empirical privacy audit (green and blue curves) exactly matches the theoretical bounds (shown in orange). As in the main manuscript, curves averages and standard deviations of 1024 repetitions.
1.0
1.0
Japp
Bound
D vs, D'
Jy Lap
D' vs. D
j Lop
JSLM
22 0.5
0n 0.5
0.0
0.0
0.0
0.5
1.0
0.5
1.0
(a) Subsampled LM (SLM)
(b) LM: Empirical auditing
Figure 5: Subsampled Laplace Mcchanism and auditing results.
Figure shows additional results on privacy auditing when the SGM is used. Here, single step of DP-SGD with Ax/o² 1.5 and 0.3 is audited using the gradient space auditing technique from [TI] as described above. Once more, the empirical privacy audit (green and blue curves) exactly matches the theoretical bounds (shown in orange). As in the main manuscript, curves are averages and standard deviations of 1024 repetitions.
Auditing the SGM
1.0
Bound
D vs. D
D' vs. D
02..5
0.0
0.0
0.5
1.0
Figure 6: Auditing results for the SGM.
13

---

Bounding data reconstruction As discussed in the main manuscript, successfully bounding MI implies an ability of the mechanism to also bound all weaker attacks. It thus possible translate our MI bounds into direct and tight bound the probability of successful data reconstruction attack by using the Reconstruction Robustness (ReRo) framework [ In brief, the goal of the ReRo adversary is to obtain successful reconstruction (from model weights//rradiets)) defined as reconstruction loss S. 17. for example mean squared error or perceptual loss. The ReRo framework models the adversary's s prior knowledge as the probability <(n) of successful reconstruction before/without observing the model weights/gradients. Satisfying ReRo then requires the probability of reconstruction after observing the model weights//raddietts to be I %. In summary, privacy mechanism satisfies (17 -eRRo against an adversary. if. given a prior probability *(n) of successful reconstruction (i.e. of reconstruction error I 17), the probability of reconstruction after sceing the mechanism's s outputs (e.g. model weights or gradients) is no larger than 7. In recent work, [33] show that, if the trade-off function of privacy mechanism is known, the probability of reconstruction y can be computed directly, allowing us to extend our theoretical membership inference guarantees to tight bounds the probability of success of reconstruction attacks. Concretely, it is shown that, if privacy mechanism's 's trade-off function f is known, then 7 = 1 - (+((1)). Since X-DR is expressed in terms of trade-off functions, the relaxed threat model we study extends naturally this type of attack. We conducted experiments under (highly) pessimistic assumptions about the adversary: We assume that the adversary has a prior probability of successful reconstruction x<n) 0.1 (a more optimistic baseline would be a uniform prior over the entire dataset, for example = 10 for ImageNet). Moreover, following the pessimistic assumption made above, i.c. that the adversary can design database which influences only a single entry in the weight/gradient vector, we assumed = for the construction of all trade-off functions in the experiments. We then analysed the DP-SGD applications mentioned above (CIFAR-10 10, ImageNet and Stanford SNL.), whereby we used the Edgeworth expansion technique introduced in (33) to estimate the ReRo upper bound. Even under these permissive assumptions, our findings, detailed in the Figure below, show that the relaxed threat model adversary has a substantially lower probability of success in reconstructing model inputs compared to the DP adversary. For details on the computation of e, see below.
3.8
08
0.5
Prob 1000. (1)
(7)
Prob. necus.
0.9
Prob.
0.4
0.4
02
DPTM RTM
DPTN RTM
DPTM
RTM
03
10
20
60
0.5
10
20
40
(8 100*1
(8 1.8- 10'*))
16
10
(a) CIFAR-10
(b) Stanford SNLI
(c) ImageNet
Figure 7: Application to data reconstruction attacks. Panels show the upper bound estimates on the probability of successful reconstruction attack on the architectures in Figure SI for increasing privacy budgets e. Under the assumptions of the RTM, the adversary has substantially lower probability of reconstruction compared to the DPTM.
7.2 Proofs
Lemma 1. In the RTM, no UMP level a test exists for all possible values of (D'), Lee. VO E θ \ Oo- Thus, Ho vs. Hi (and Hi vs. Ho) are each not decidable by single test.
Proof. The claim follows immediately from the Neyman-Pearson Lemma ment, we refer to Section 3.2. of 25
For a detailed treat-
Lemma 2. The composite LR test Ho : 0~ Z(g()) vs. Hi: 0 ~ Z(g(D"), E) is equivalent to
letting 0- ~ Z(n, 5) and simultaneously conducting two individual one-sided LR tests and r' with null hypothesis J = O and alternative hypotheses -A+ S p < 0 for r and 0 < p S A Afor where == (DD) (DD and A is the global sensitivity of
14

---

Proof. We will first show that testing No ((q( vs. H1 ((g(D)),E) is equivalent to testing 2 E) vs. -(q(D))-gl (D), g). We know that 2(4, {) is shift invariant probability measure which admits density. Thus, for any c. f E RR:
()) = (1,, c) + 2(u c,)) = (1, c).
(8)
The LR for (()()), vs. (gg(D)).E) is:
((q(D))
log Z ((((D),)(()
(9)
Since the LR may be evaluated at 0, we can evaluate it at 0 + ((D), since g(D) is known constant:
log ((q(D", () + (D)) log 2(q(D)- - (0), () + ((D)
- (D), loo 2(1(D)) (D)) (10)
()))
Therefore, we have shown that testing () vs. ((g(D'),E) {) is equivalent to testing (0, {) vs. ((q (D), as the LR for any 0 under both hypothesis testing problems will be the same. Now, let = g(D") (D). Since A does not know the value of gDD",, they can only deduct that ||^|| I A. Thus, the two cases μ > 0 and μ < 0 must be considered simultaneously and individually. The claim follows. Observe that the proof is identical for the reversed test Ho Z(g(D') -(D)) ()), vs. H₁ 200, E), i.e. with the null and alternative hypothesis switched.
Lemma 3. The individual LR tests r and r' are UMP level if the noise distribution Z has the monotone likelihood ratio property (MLRP). The Laplace Mechanism (LM), Gaussian Mechanism (GM) and the Poisson-Sude Juisson-Subsappled Gaussian Mechanism (SGM) all have the MLPR. Moreover, the power of both tests is maximised when |||||| (l' (D) A.
Proof. The existence of an UMP level a LR test for distributions with the MLRP is justified by the Karlin-Rubin Theorem (34), which states that, when the null hypothesis is simple, the alternative hypothesis is one-sided and the LR is a monotone function of the parameter of interest (MIRP),, the LR test is UMP level a 40 E θ \ On-
More precisely, the MLRP implies that the LR is non-decreasing non-increasing in the parameter of interest (in this case 0) of a test. We must consider the cases < 0 and μ > 0 individually for each mechanism. Throughout, let P = 2(0, {) and Q (1, E). We will replace the placeholder Z with the distribution of interest as required and consider both tests P vs. Q and Q vs. P.
For the Laplace Mechanism (LM), have:
P(0)
19-2l
10 pl|
10
log ((0) log e
and
(11)
b
log (()) log
19-2l
- 10 11|
+ 18
(12)
P(0)
P(0) For μa > 0, log Q()) is non-increasing in and for μ < it is non-decreasing in The opposite
holds for log P(e)
Q(0)
by symmetry.
For the Gaussian Mechanism (GM), we have:
log P(0) log Q(0)
1011 20
10-ull
||0
111
||011
20
and
(13)
20²
log ((0)
s 20
|10
11112 + |1011
log
2n2
(14)
P())
20
Q(6) non-increasing in and for μ < 0, non-decreasing in Again, the opposite holds for log P(Ø) by symmetry. Observe that the LRs are independent of dimensionality for the (S)GM, hence it suffices to consider the scalar case.
For μ > 0, log P(8)
Q(0)
15

---

Finally, for the Poisson-Suee Suisso--ubbamppedd Gaussian mechanism (SGM), we have:
log P(O)
+ (0 - 1x)
= log
and
(15)
((0) pe
(0-1)²
20²
(p - 1) C
log Q(0)
e2
10-212 20
log
pe
p +
(16)
P(0)
The computation here is slightly more involved. Taking the derivatives, we have:
d
P(0)
ppe
log
and
(17)
d0
Q(0)
o²
pea.*
pe
2
6² 10 (w-w)²
d
log Q(0)
ppe
20
(18)
d0
P(0)
r² pe
20
P p+1
Both numerators are positive when i positive and negative otherwise. For Q(0) it is negative. Thus, when denominator is negative when is positive, while for d log P(O)-
aB log P(0) the Q(0)
de
is positive, log P(0) is non-increasing in 0 and non-decreasing otherwise. Conversely, log P(0)
Q(0) is
Q(8)
non-decrasing with μ positive and -oniiccreasing otherwise.
So far, we have proven that (1) the LMM, GM and SGM have the MIRP and (2) thus, by Kublin-Rubin, there exists an UMP level a test for (00,E) <) vs. ((,, {) as well as for the reverse 2(u, vs. 2(0,E) for both r' (n. > 0) and (μ < 0). We note that the proof could have also been achieved by using the fact that the Laplace and Gaussian distributions with known scale are part of specific onepparameter exponential family, which has the MLRP property. Compare [25). Section 4.2. It remains to show that the power is maximised for A or μ A, i.e. that the power increases with the effect size, this case 4/E, with ç assumed fixed.
First, observe that we can reduce our workload by half as, by shift invariance, the tests r': 2 E) vs. 3(p, {) and 2(0,E) vs. Z(-H. {) as well their reverses are all equivalent. It remains to show that the power function (i.e. (1()) at fixed a:) is maximised at A. In fact, it suffices to show that the power function is strictly increasing as function of μr, since A is the largest value μ can take. The power function is a re-par parameterised version of the trade-off function for the one-sided UMP level a test (note that this is not the combined test but one of the individual component tests- the combined test is equivalent to performing the two component tests simultaneously and necessarily loses power as it represents multiple testing which increases the false discovery rate). Fix a level a.
For the LM, we have 7
e B(Tap(0, b), Lap(u, b) (a) = 6 h-/0/am
a a<e-%
e e-1///2 S $ 1/2,
(19)
c-
a),
a 1/2.
It is easily verified that ((La((O) b), Lap(u, a) is strietly increasing in μ Ya.
For the GM, we have 7
aa) 2 (a)
(20)
where Φ - are the CDF and and iSF, respectively. Recall that the function defined on [0, 1] x [0, 1]. Taking the derivative with respect to fı and observing that ---((r) = Φ- --1(1 (11 x) we obtain:
T @ (1 a) m//) = g ( - a) - -m/o) d
( (1 - a) w//),
(21)
dy
du
where y the PDF of the standard normal. The second term simplifies to:
(4- (1 a) m/6) -
(22)
du
16

---

Thus, we obtain:
① ( 1 a) - 9 (11 a) (1
-//o-
(23)
dp
Since is a positive constant and g(x) > 0 Vx, the derivative is negative for all values of μ. Thus, 3 (NV(0, (")0, N,,,,, a) is decreasing in μ and thus - B is increasing in μ as required.
Finally, for the SGM, we can invoke Lemma 9 below and re-use the proof for the GM. Fix 0 <p < 1.
Lemma 9, specialised the SGM, states:
3 (N(0, o o²) + (1- (0),)) |a) p (a) +1-))
(24)
The second term is independent of μr, thus the claim follows from the proof for the GM.
In conclusion, have shown that, in the RTM, the adversary must conduct two pairs of individual and simultaneous UMP level a LR tests whose power is maximised when μ = i.e. at the dominating pair distributions (22). This conforms to the intuition that the power of the test should increase when the distributions are "further apart", i.e. when the effect size increases. Moreover, identically to the DPTM, it allows
consider only the dominating pairs when constructing the trade-off functions, since no other test between the distributions of the mechanism on the two databases can have higher power the same level than the test(s) between the dominating pair(s). We have thus established that the optimal tests the sub-optimal adversary A can construct against the aforementioned noise mechanisms in the RTM are UMP level a tests. These tests are necessarily less powerful than the uniformly most powerful tests that ANN can construct because they are only optimal for subset of the values of q( (D) at a time, whereas the uniformly most powerful tests of A are optimal for all values of (DD) simultaneously.
Lemma 4. If the density of Z is additionally symmetric about the location parameter, the simulta- neous individual LR tests and r' are equivalent to performing a single test using the magnitude of the observation as test statistic, i.e. letting ||0] ~ || [p. and testing Ho || = 0 vs. H1 : ||||| O. The power of this "combined" test is maximised ||||| A.
Proof. Observe that Hi can be split up into two hypotheses: Hio 1 > 0 and His 1 < 0. Now, we can conduct two simultaneous tests F1 Ho vs. and Fg : Ho vs.H1b- The LRs are:
For El: Ai (0) = log H()
(in)
For Eg: (0) = log ((0)H..))
2(0)Ho)
The rejection region for these tests will be {A₁ > c1} and {A2 > c2). where C1, C2 are the critical values. The distributions for both A₁ and A2 under Ho are identical. It thus suffices to consider the numerator of the LR, which, from the MLRP, is monotone in 9. Cancelling the logarithms, we may thus simplify and consider A 0 and A2 -0. To maintain the same level for all tests, the critical values should be equal: c= c = é22 where the hat denotes the new critical values after simplification. We remark for completeness that this will render the tests unbiased. Since these tests are UMP and unbiased, they are also called UMP unbiased (i.c. the tests with the greatest power in the set of unbiased tests). For further details, we refer to (25). Section 4. For the combined test, the rejection region is thus: {Ai > } U (A2 > } = {0 > c) ( > c} = { > c). This proves the first claim. The claim that the power is maximised when || A follows from the previous observation and the proof to Lemma 3. For the reverse tests, the proof is identical.
Lemma 5. For a (not necessarily symmetric) Z the Generalised Likelihood Ratio Test (GLRT) using the test statistic log C(e ((0))().)) ((.))( where ja is the maximum likelihood estimate of is equivalent to simultaneously conducting and r'. The GLRT's power is maximised at P A.
Proof. For the concrete problem μ 0 vs |||] > 0, the GLRT test statistic can be written:
sup HeD ,., L(0) Z (v,, E)) [(0) E))
A(0) log
(25)
17

---

For single observation 8 (i.e. absent other information) the MLE for the mean ji is equal to the observed value of 9. Thus, the GLRT becomes:
((i,
A() = log (0))
(26)
Compare the GLRT to the two simultaneous tests:
The LR test statistic is A1 (0) log 2(0) for 14 0: ((0)2(00E))
r': The LR test statistic is A²(0) = log C( 2(n_)) for 11 0.
2(0 ((0
Observe that these are identical to A() when the restricted MLE is used, provided the same critical value is chosen. Thus, the tests are equivalent the same level The claim that the power is maximised when f = A then follows from the previous lemma. For the reverse tests, the proof is identical. We note for completeness that the same result could have been achieved using the Wald or Rao tests, which are derived differently, but are statistically equivalent to the GLRT (35).
Lemma 6. If mechanism satisfies f-DP, also satisfies DD,, with f'(a) 2 f(a) Va [0, 1].
Proof. The lemma is essentially a re-stating of Lemma in the language of f-DP. Since UMP level test does not exist for all values of (D'), any test that Ao constructs is less powerful for at least a subset of the parameter space, and thus the resulting trade-off function in the RTM will be on or above (dominating) the trade-off function in the DPTM. An alternative way to look at this through the post-processing guarantee of f-DP. As an example, consider using the test statistic |[]] as discussed above. As B is the output of a mechanism, we can consider a post-processing step on M'D For I-DP, it holds that [7]:
(M)) (roc(M((D)) > T(M(D).
(27)
for any trade-off function T. The claim follows by setting the LHS to f', which is the trade-off function constructed using the test statistic ||0]| in the RTM and the RHS f. which the trade-off function of the (NP) UMP level a test in the DPTM.
Lemma 7. If a mechanism satisfies f-DP and f'-DR with f 2 f, arbitrary post-processing can only deteriorate privacy up the f-DP guarantee.
Proof. This is essentially the contrapositive to Lemma 6. Since f-DP is resilient to post-processing, the worst deterioration of the A-DR-guarantes
never exceed the f-DP guarantee.
Before proceeding with the proofs about the closseifform/nnmmrriial expressions of the trade-off functions, we re-state Definition and provide a brief derivation.
Definition 2 (Trade-off function construction). Let P. Q be the distributions of a test statistic under Ho and Hi, respectively and let & p.QQ denote their cumulative distribution function (CDF), V Ppo their survival function (SF) and & -1 P/Q'' 4 P/Q
their respective inverses (iCDF, iSF). Then, we define:
T(a) (TF and (a) = (a)
Proof. The proof standard. We reproduce it here for the purpose being self-contained. Consider a one-tailed test for a parameter O. From basic hypothesis testing theory, given a test statistic A()) and a critical value c, a Pr(A(0) > e (H)) and B = Pr(A(0)= < cl H1). Letting be the distribution of the test statistic under Ho and Q its distribution under Ho. we have:
B(c) (c( and acc) (C).
(28)
Since the trade-off function is T + 3(a), we solve the RHS for e and have:
c= .ー (a) = T(a) क6 (TF
(29)
T-1 follows by inverting T. The same form manifests by considering T-1 the trade-off function for the test with the null and alternative hypotheses exchanged (the reverse test). The role of P and
Q will be played by the test statistics for the various mechanisms below. We note that, since the functions are inverses of each other, may arbitrarily designate one as T and the other as -1. D
18

---

Theorem 1. Ler μr = S1/b. The LM satisfies C(jLap (a). (a)) DR with:
{ exp (- sinh (log (a)), 2 exp (-11) otherwise,
[app(a)
{ cosh (1z),
and
a exp (fx + exp (2mr)+1* a < 1/2 (-H1)
Lap (a)
otherwise.
cosh (#:)
Proof. j(a) is the trade-off function corresponding to the test r Lap(O, b) vs. Lap(Ar, b) and (a) is the trade-off function for r' Lap( A1, Lap(O, b). Since the density of the Laplace distribution is symmetric, we can invoke Lemma 4 and use the absolute value of the observation as test statistic.
For r, under Ho. the test statistic ||O]| follows an exponential distribution with scale parameter Under H1, the test statistic ||@]] follows folded Laplace (FoldL) distribution (27) with mean A and scale parameter b. For r', the hypotheses and distributions are reversed. To construct the trade-off functions, require the CDF ④, and iCDF + --1 From these,
construct ((x) 1- - ((x)
and Vp (x) --1(1- æ)). All are available for both distributions in closed form. We have:
Ex)(()) (x) = 1 exp (-#/b),
1b Exp(U) (x) = -blog (1 x)
and
exp (-/ff) sinh (%)
0 < A A1.
(1))
exp (-z/b) cosh (A1/b),
blog (a exp (A1/b) / exp (201/b) + +1).
0 x S 1/2 e/2exp 1appp//p-/p--/-/pp0 (-2A1/b)
$ --1 FoldL(Aa, (or)
bog (cosb(a)/0/((1==))
1> x 2 (1/2 1/2 exp (-241/b)).
j and j- then follow by substitution in the expressions for the trade-off functions from Definition above:
j(a) +FooaL ( Exp()) (a)) and j j- (ax) = Exxp(() FAI (a)).
(30)
Theorem 2. Let μl D2fa. The GM satisfies C(jaM (c). (a) DD with:
(a) = 1b x3((0002) (w (v-1 (I (()) and (a) = xx((0,02) (
(4)
Proof. The proof is similar to Theorem 1. j(a) is the trade-off function corresponding to the test NO, g.). vs. NM42, o²) and j (a) corresponds to the test r' (N(A,, o²) (0, o?). The Gaussian density is also symmetric, hence we can appeal to Lemma and use the magnitude of 0 as the test statistic which does not change the monotonicity behaviour of the test statistics.
more. In fact, will use the squared magnitude for numerical reasons,
For r, under Ho, the test statistic |00|2 follows central chi-squared distribution with d degrees of freedom scaled by o², i.c. (2, o²). Under H,, the test statistic ||0||2 follows a noncentral chi chi-squared distribution with degrees of freedom and noncentrality parameter μr 22/0², i.e. x3 (xī, o²). For r', the hypotheses and distributions are reversed. To construct the trade-off functions, we require the CDF 4, and iCDF 4 From these, we can construct 4 (x) and (-'(x)) 0 I) as above. For the central chi-squared distribution, & has an analytic form, but - does not. For the non-central chi-squared distribution, c is expressed in terms of the Mareum Q-function (36). while --1 once again has no analytic form. However, high-precision numerical implementations of the aforementioned functions are widely available. We thus express j and j-1 in terms of these abstract functions and implement them numerically throughout. The concrete expressions follow directly from Definition 4. Moreover, for d = 1, a closed form is available for j. which is shown in the upcoming Corollary.
(xx)
19

---

Corollary 1. For d = 1, j() admits the following closed-form representation:
jam(a d 1) (
(WNo..) (0/2) - -12) - -VN(..1) (WNO.,) (2/2) + u2)
(5)
Proof. For this proof, it helps to picture Definition 2 with the role of the test statistic played once again by ||0]]. Thus, a = Pr[[10]22 > c² Ho) and 8 = Pr([|0]]2 < c² H1). We can take the square of the critical value since the magnitude is always non-negative and may choose the critical value arbitrarily; it will also simplify the computations below. Recall that because is now a scalar.
From the proof to Theorem 2, we have: a(c²)) v (x and 3(c²) T xx7(x2 (c²). -
x2) admits an analytical form:
V erf
ca
7 2 20²
20
V (+)=
=1
=1
(31)
V n
erfe
(32)
V2a
where 7 is the lower incomplete gamma function, I' the gamma function and erf, erfe are the error function and complementary error function of the Gaussian distribution, respectively, We can now exploit the following pattern:
11 = erfe
(33)
2
V2
so the term in Equation 31 can be written as 2 (0.1) (2). Since V V((..)) invertible, we have
that oB 110.1) oVW (2)
Similarly, & *x((x3002) (c²) admits closed-form representation. Recall that p1 = 43/0².
A3
1 Q
(34)
0
0²
A2 c
Qm1
(35)
where Qarg is the Marcum Q-function of order
2
(36].
Substituting the expression for from above, we obtain:
A2
v N
(a)
1- Qar!
(36)
σ
Qa!
A
1
(o)
(37)
((o.1))
The Mareum Q-function of order & also admits closed form:
1 2 erfe 0-aa V2
b b+a a
QM (a, 6)
+ erfe
(38)
v2
Using the pattern erfe * = v (k) as above, we rewrite Equation
v
38 as:
Qm (a, (b (b- a) + (a + b).
(39)
Finally, we substitute the arguments from Equation 37 and obtain:
Wwio.. (woto.) (0/2) A2
+ W.(o. (wxto.n (9/2) + 0 2²))= =
(40)
= 1 (woto.1 (0/2) - 122 V A((.)))
(Wolo,, (9/2) + (12) 122)
(41)
which is the desired form and completes the proof.
20

---

Lemma 8. Ler GM.. GM, be GMs with noise variances o on functions with sensitiviries 2za A2h, respectively. Then, the adapaiviy composed mechanism GMC has trade-of off functions:
jGMc(a) xx ox))))))
( (1 and JaMc(a) L2 xx3(0.03)
① -1 (x (a))
(6)
with Ks, = (Am+- /02 toß and of of +0.0
Proof. Let Pa. 0s E Rd be uncorrelated mechanism outputs two independent queries. Since A4 passively observes both outputs before testing, the test statistic becomes:
1 O0. 0,) Sc (()) = 110.12 = 122
(42)
Of note, the reason why the mean of the observations is the correct choice here follows from Lemma as the MLE of the mean of a normal distribution for > 1 observation is the sample average. By the additive properties of isotropic Gaussian noise, the distributions of the observations thus are:
Ho : O. ~ N (0.
02 oh 1d
VS.
(43)
4
Hi : 02 ~ N
Daa
+
2b
0
+
o
T
(44)
2
4
Under Ho, the test statistic is thus distributed as:
2 + 0,
o
X²
(45)
4
while under Hi is distributed as:
A
2
0a + oh
xx (14x. + A2)) o² + o
xa
2
? + of
(46)
From here, the proof continues identically the proof to Theorem 2 above, from which the claim fol- lows. The generalisation to > 2 compositions follows inductively. In particular, for N homogeneous compositions (i.e. with identical sensitivity A₂ and noise variance )²), the test statistic under Ho is distributed as:
xa
0, N
(47)
while under Hi is distributed as:
N
0²
x
(48)
N
which follows directly from the above. We will use this property in the following proof.
Theorem (Blessing of dimensionality in the RTM). Consider a GM on a function with sensitivity
Da and noise variance I² such that Anfo < 1. Let #22 Azfo. As d and/or the number of non-uduptive compositions N increase, JGM and JeM tend to the common form:
--1
V 1 (()
V2Nu3
W (Wxlo.nla) - NNV.
P2 2d
= PN
(7)
22
2N
+1
2dy
+1
Proof. To prove the claim, we will appeal to the central limit theorem (CLT). We will use the facts that the mean of the central chi-squared distribution with degrees of freedom is and its variance is 2d. The noncentral chi-squared distribution with d degrees of freedom and noncentrality has mean + k and variance 2d + 4k. Under the CLT, as + oo and/or as d + cc, we thus have convergence distribution as follows. Letting N = 5 (compare Equations (4 and 488
x² + NVdd, 28 d) and x² + .N(8(d + x). (2d + 4k)).
(49)
(50)
21

---

We now proceed as in the proof' above and consider the test statistic under the null and alternative hypotheses and critical value We have:
(c- dd
a<c) Vo(1.)))
cc= v
6d
(51)
2v
and
c (c- 8(d k)
3(c) @x((..1)
(52)
8v2d + 4k
For the trade-off function, we substitute obtain:
V (ato,1(aa6v + od 5d 8k
2N((..)
(53)
5/2d + 4x
Nío.11 Nio.1 (a) -
Px((o.))
(54)
8v2d + 4x
V 1o (a) - -Vau
(55)
V1
Substituting x t- NO3/0² a (i.e. the degrees of freedom, compare Equation 48 terms, we obtain:
and separating the
V2A3N
2 W (1)
(56)
dg
+1
2do²
243N do
Letting μ22 = Azfa, we obtain the form of the LHS of Equation
To obtain the RHS of Equation 7 we further massage Equation and Taylor expand the equation around ( = 0 to obtain:
55
Concretely, we lea ==
V (a) - (V (ooon((a)) + +O(C))
(57)
When d is large, O((2) vanishes and v dominates the term in the parentheses, yielnni
/ (v 2 ( - -c
(58)
Finally, recursively substituting Ç + w/d and x + NO3/0?, we get:
(110,1) (Wtt.n(a) N
(59)
2d
Letting 23/02 náz obtain the RHS of Equation The fact that the two trade-off functions become symmetrical follows this equation's 's functional form, which corresponds to the trade-off function between two Gaussians with the same variance, i.e. faM-
Lemma 9. Let T(A, ())) be trade-off function between two general distributions A, B repre- senting mechanism outputs. The trade-off functions functiioon for the sub-sampled mechanisms are given by T(A, (1 p) + (a) = (A, (a) + (1-p)) p1) a) and by its inverse.
Proof. Of note, this fact was first observed in 7 and also proved in (22). We provide a more concise proof here for the purpose of coff-contaisssssss. Let 4 and their inverses be defined for and B as above. By Definition 2, we have:
T(A, B) 13(4 (a)).
(60)
22

---

where T' is a generic trade-off function. in our case or j- We want to show that for mixture of distributions A and B, with mixture coefficient E (0,1):
()))) + (1 - p) T(A, (1 p)A + pB)(a) - Define the CDF of the mixture distribution C' as & = (1- p) A + pkn. Now, we have:
(61)
T(A, (a) -
=(1 p) ( A (a)) + (a))) =
=(1 - 2) (1 - a)) + p (a))= =
-1 p) - a) B),
The inverse T is not always easy to construct and, in practice, is usually computed numerically. We have thus shown that we can construct the trade-off functions of a sub-sampled mechanism directly from the trade-off functions of the original mechanism, even if none of them has an analytical form.
7.3 Experimental details
Privacy auditing experiments All experiments were conducted on a single workstation computer equipped with 64 GB of RAM and a 12-core Intel Xeon CPU with a Thermal Design Power of 105 W and implemented in the Python programming language. For the synthetic learning tasks, a dataset of 1025 samples with one feature each, split evenly across two classes, was generated using
's make_classseaas classif iiaiion method. Of these, 1024 samples were used for shadow model training and a single example (x*) was held out and its label flipped, similarly to the data poisoning technique of [12) to maximise the point's impact on the model's s confidence. This process was repeated for 1024 iterations, and shadow models were trained. No fixed random seed was used. Shadow models were trained in pytorch using full-batch DP gradient descent for the experiments in the main manuscript and Poisson sampling for the experiment in the Appendix, with sample-wise & norm bound of 1, a noise scale of 1 and implemented using single linear layer with a single unit. Models were trained to convergence on the training database, at which point the training loss was < 0.1. In every case, we considered single step of model training, i.c. disregarded all previous model updates. For the logit-space auditing, logits were transformed by applying the logistic sigmoid activation function, converted to confidence scores and Gaussian likelihood fitted as described in the Likelihood Ratio Attack Section IV.C of (12). For executing the offline MI attacks, we followed Algorithm I of [12] with the modifications described implement offline MI. In brief, likelihoods were fitted to the so-called IN models, i.e. the ones the adversary is assumed to have access in the RTM. The models' confidence was then measured on the unseen sample xx to determine its membership status by implementing the one-sided hypothesis test described in [12 for offline MI. To compute the trade-off functions, the test statistic was evaluated at 50 critical values using scikit-learn 's ROC functionality, as the ROC and the tradc-off function are complements of each other. Results are reported as averages and standard deviations over the 3 at each critical value a, whereby the critical values were chosen identically for each repetition. For the gradient space auditing, the gradients of the final training iteration, when norms were lowest, were used as a reference "database" (D). To these, a gradient with a magnitude of 22 i.e. equal to the clipping threshold was added to simulate the maximal effect of x", similar to the Dirae canary technique described in [1I. Noise was then added to all gradient samples. Then, the magnitude of the gradients was used as a test statistic as discussed in Appendix A.B. of [12), and as proven to correspond to the optimal hypothesis test under the RTM in Lemma 4. Similar to above, the test statistic was evaluated at 50 critical value settings and the ROCs were computed. For the high-dimensional experiment, we utilised the diabetes dataset [30]. 10-dimensional regression dataset with 442 samples. The same strategy was followed as in the gradient space auditing section above, but this time, a model with a latent space dimensionality of 50 was implemented. The noise multiplier was set to 0.5. Once again, a single Dirac canary gradient was added to the gradient "database" and the ROCs were computed as above. The experiments did not require graphics processing unit and required approximately 60 minutes of net computation time on a CPU. At an assumed carbon efficiency of 0.432 kg/kWh, the computation of these experiments caused approximately 0.04 kg of CO2 equivalent emissions.
Deep learning with DP-SGD CIFAR-10 was trained from scratch using the ResNet-9 architecture from 37) and subset of the techniques presented in (38) (2 augmentations per draw but no expo-
23

---

nential moving average on the weights) to (1, 10 10-10-0)).. D-D.P We used sampling rate of 4 096/50 000, noise scale of 10.5 and trained for 000 steps in total. For SNLI, we fine-tuned the final layers of a 105M-parameter pre-trained BERT Transformer (39) to (1, 1.8 10-6)-DP using a sampling rate of 4 1096/54 5549 361, noise scale of 1.15 and 405 steps. For ImageNet, we fine-tuned the final 12 layers of ResNet-18 architecture pre-trained on Places365 following the exact hyperparameters from (40) to (10, -DDP. For DP accounting, we used the Rényi-DP accountant from the Google Differential Privacy library, whereas for acounting for privacy loss in the RTM, computed the product distribu- tions of the test statistics as described in [7]. Definition 1. ff. using direct numerical integration to 50 digits of precision using the mpmath library. To determine the noise scale for training the models under the RTM, we adapted the technique described in (41). In brief, we determined the upper and lower noise scale values for which the RTM trade-off functions (A-functions) optimally "sandwich" the f-DP trade-off function and then chose the more pessimistic of the two noise scales to train the model, keeping all other hyperparameters constant. As point of comparison, if (hypothetically) one would convert the RTM noise scales to the DPTM in terms of e, this would result in g-values of 6.2.5 and 19 the same ō for CIFAR-10, SNLI and ImageNet, respectively. We remark that this conversion does not imply that these models satisfy DP for these s-values, just that hypothetical (c, -analogue of X-DR would achieve these e-values. The true worst-case (e, 6--DP guarantees remain the same in both cases. The experiments were performed on a GPU cluster using NVidia RTX A6000 GPUs and required a total of 212 GPU hours. At the carbon efficiency assumed above, the computation of these experiments caused approximately 27.5 kg of CO2 equivalent emissions. All emission computations were computed as described in 422
7.4 Ethics statement
Our study focuses on the relaxation of the differential privacy (DP) threat model and provides formal bounds on membership hypothesis testing error rates. We acknowledge that work has positive and potential negative ethical implications, and we strive to address these concerns as thoroughly as possible.
Positive implications of our study include the following:
1. Improved privacy guarantees and higher utility in machine learning models, which may encourage privacy sceptics to adopt DP.
2. Acknowledging that the standard DP threat model may not always be applicable in practice and providing a more realistic alternative.
3. Enhancing our understanding of privacy dynamics in systems by introducing relaxations incrementally, which can demonstrate how privacy guarantees improve as the adversary's power decreases.
4. Providing formal bounds, which offer more rigorous understanding of the sub-optimal adversary's 's membership inference capabilities in the relaxed threat model.
Despite these positive implications, we recognise potential drawbacks and have identified mitigations for each:
Our guarantees may not hold if the assumptions of the relaxed threat model are violated. To mitigate this, the relaxed threat model guarantee should only be reported alongside the full DP guarantee, which holds in the worst case.
2. If stakeholders or users misunderstand the circumstances under which the relaxed threat model's guarantees break down, they may come away with a false sense of security. To address this, we ensure comprehensive understanding of the threat model through formal characterisation and clear communication of the exact guarantees provided by the mechanism in the relaxed threat model, and the situations in which they don't hold, e.g. post-processing.
24


Reviews:
[{"review_id": "Y3MNhAeFQs", "reviewer": "Reviewer_WnyT", "summary": "The paper proposes a relaxation of the DP threat model in which the adversary's goal is to perform membership inference without access to the target example. The goal of this threat model is to reflect the offline setting explored in Carlini et al. 2022, Watson et al. 2021, and Ye et al 2022. It is possible to characterize the performance of the optimal adversary in this threat model, similar to the Neyman Pearson optimality in the full DP threat model. The paper computes these optimal performances for a variety of practical additive noise mechanisms for DP.", "questions": "The threat model seems more directly applicable to understanding the performance of reconstruction attacks rather than MI attacks, since reconstruction attacks also match your threat model's assumption that the target example is unknown to the adversary. Do you think your results could be applied to those attacks?", "limitations": "These are all well noted in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper approaches a well motivated goal - relaxing the DP threat model to understand the power of weaker, more realistic, adversaries.\n\nIn their threat model, they are able to derive the optimal attack for a number of mechanisms.\n\nTheir techniques allow a model trainer to \"fall back\" on the provable DPTM guarantees, even if an adversary is more powerful than the RTM guarantee would permit.\n\nThe paper is well written, and is careful about a lot of points, e.g. DR is not robust to postprocessing and does not compose. It is also very well cited.", "weaknesses": "I find the threat model difficult to motivate. At its core, the threat model is defined in a way where the adversary does not learn any private information from succeeding in the game. All it learns is that some example has been added, but no information about this example aside from membership.\n\nThe paper suggests a connection to offline MI attacks, but this doesn't seem right. In offline MI, the adversary still knows the example, they just are unable to fully compute the distribution of M(D'). The paper shows that in their threat model, the adversary can only use the magnitude of the noise, not the direction, as they don't know which direction the modification could have come from. However, in offline MI, the adversary *does* know the direction, because they know the example.\n\nThe experimental results are performed on very small datasets or small dimension synthetic data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments on our work and appreciate the opportunity to clarify the reviewer’s questions.\n\n> I find the threat model difficult to motivate (...)\n\nIt appears that there may be a misunderstanding about the implications of the adversary succeeding in the membership inference game. In brief, the membership inference security game involves an adversary attempting to determine if an individual's data was used to train a model, without being able to evaluate the likelihood on a challenge example directly. Therefore, success in the membership game does not mean that the adversary does not learn any private information (see step 4 of the game). On the contrary, the implications of the adversary winning the game are actually identical as in the DP threat model, i.e. a breach of membership privacy. The important difference to the DP threat model is the higher *difficulty* of succeeding in the game. This is because, in the relaxed threat model, no direct evaluation of the example’s likelihood is performed.\n\n> The paper suggests a connection to offline MI attacks, but this doesn't seem right (...)\n\nIndeed, in offline MI, the adversary knows the example but chooses not to compute the distribution (likelihood) of $\\mathcal{M}(D')$, usually to save computation. In the relaxed threat model we study, the adversary is unable to compute the distribution of $\\mathcal{M}(D')$ due to a lack of access to the point. The important similarity is that, *in both scenarios the distribution of $\\mathcal{M}(D')$ is not computed by the adversary*. In terms of a security game, we follow formal convention by defining the adversary as not having access to the point in question instead of stating that the adversary “chooses to not evaluate the distribution at this point”; the latter would be inconsistent with typical formal definitions of adversarial games as they are usually presented in security literature, where the adversary uses all available means to breach privacy. \n\nIn summary: (1) the relaxed threat model adversary aligns with the DP adversary in every aspect except the fact that they do not evaluate $\\mathcal{M}(D')$; (2) success in the membership inference game has the same implications as in the DP threat model; (2) an offline MI adversary does not evaluate $\\mathcal{M}(D')$ by choice, whereas the “formal” adversary does not evaluate $\\mathcal{M}(D')$ due to a lack of ability. However, the latter distinction is irrelevant in so far as the effect being identical. Therefore, our membership inference game and offline MI can be theoretically analysed in exactly the same way. \n\nWe are grateful for the reviewer's remarks on these point and will clarify the writing in the final version of the paper.\n\n> The experimental results are performed on very small datasets or small dimension synthetic data.\n\nWe recognise the reviewer’s interest in large dataset applications of our proposed method to obtain better privacy/accuracy trade-offs. Therefore, and also in response to comments from other reviewers, we have now conducted an additional set of experiments. These showcase the usefulness of our technique for improving privacy/accuracy trade-offs in deep learning for image recognition (CIFAR-10 and ImageNet) and natural language processing (Stanford SNLI). For instance, we show up to a 14% increase in accuracy on CIFAR-10 at $\\varepsilon=1$ by calibrating the DP-SGD noise scale to the guarantees of the relaxed threat model vs. the DP threat model. These additional experiments on large datasets provide a more comprehensive view of our method's applicability and advantages. Please refer to the “Global Reviewer Comment” and the attached PDF (Figure S1) with the results.\n\nRegarding the reviewer’s concern about the choice of small datasets in our study, it is important to point out that –for the auditing experiments in the manuscript– using small and low-dimensional datasets is preferable since large or high-dimensional datasets can lead to looseness in the empirical bounds due to the inherent difficulty of the attack in higher dimensions. Compare for example the paper by De et al. (Table 9), where, even in the DP threat model and on the relatively low-dimensional MNIST dataset, the empirical membership bounds are very loose. Therefore, large/high-dimensional datasets could hinder our ability to objectively test the tightness of our guarantees, which would be counterproductive for the purposes of the presented study.\n\n> The threat model seems more directly applicable to understanding the performance of reconstruction attacks (...)\n\nWe agree with the reviewer and are grateful for this suggestion. Indeed, reconstruction attacks are a promising target for our analysis and the reviewer’s intuition aligns with recent findings in the field. Specifically, works by Hayes et al., building on previous work by Balle et al., have demonstrated that DP mechanisms also bound reconstruction attacks through the concept of “Reconstruction Robustness”. Moreover, a recent work by Kaissis et al. establishes that the hypothesis testing interpretation can be used to formally and tightly bound the probability of a successful reconstruction attack when the trade-off function is known. Thus, our membership inference bounds can directly be translated into bounds on reconstruction attacks, which are (expectedly), much stronger, as reconstruction is a more difficult task. To address the reviewer’s concerns and suggestion, we have conducted additional experiments on bounding reconstruction attack probabilities for the aforementioned image recognition and natural language processing tasks, and show that the relaxed threat model reconstruction probabilities are much lower than those for the DP threat model. The results can be found in Figure S2 of the attached PDF and more details can be found in the “Global Reviewer Comment”.\n"}, {"review_id": "bO1FzgPl0P", "reviewer": "Reviewer_pkta", "summary": "The paper studies differentially private machine learning (DPML) against sub-optimal membership inferences attacks (MIAs), i.e., the attack cannot access the exact training data. Similar to DPML against the worst-case MIAs, the paper formally characterizes membership inference capabilities in terms of hypothesis testing errors and validates the hypothesis in synthetic datasets. ", "questions": "\nI do not have any serious comments on the motivation and theoretical results. My only concern is that the proposed DP mechanism is only evaluated on synthetic datasets and does not test in practical settings. Specifically, what are the results on the real-world dataset and applications that are commonly used in the existing DP literature? Whether it is possible to compare the proposed DP with other DP mechanisms against the worst-case adversary? \n\nCould the proposed DP be generalizable to defend against our privacy attacks such as model inversion/data reconstruction attacks? Any comments or thoughts? Regarding this, I would suggest the authors to clearly state \"membership inference adversaries\" in the title instead of \"adversaries\" in general. ", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper is well motivated and well-written \n+ Well-formed theoretical results ", "weaknesses": "- Only evaluations on synthetic datasets\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for these thoughtful remarks, and would like to address their concerns as follows.\n\n> My only concern is that the proposed DP mechanism is only evaluated on synthetic datasets and does not test in practical settings.\n\nWe are grateful for the reviewer’s suggestion to extend our proposed methods to real-world/large-scale datasets to demonstrate that the tighter privacy bounds of the relaxed threat model allow us to obtain better privacy/accuracy trade-offs. In response to interest from the reviewer and the other reviewers, we have thus now conducted additional experiments, which explore image (CIFAR-10 and ImageNet) and natural language (Stanford SNLI) modelling tasks using DP-SGD. These new results show that it is possible to train deep learning models with higher accuracy when considering the relaxed threat model compared to the DP threat model. For instance, we find that calibrating the DP-SGD noise scale to the guarantees of the relaxed threat model instead of the DP threat model results in up to 14% increased accuracy on CIFAR-10 at $\\varepsilon=1$. Further details on these results are provided in the attached PDF document (Figure S1) and the “Global Reviewer Comment”. \n\nThe reason behind our choice of relatively low-dimensional and synthetic datasets for the auditing experiments is that they are much easier to attack. This allows us to demonstrate the exact tightness of our bounds in a controlled environment, where the difficulty of the attack is not increased by reasons unrelated to the privacy mechanism (e.g. dimensionality of the dataset, sampling randomness in SGD etc.). Performing auditing on real-life datasets would have a high probability to fail to show the tightness of our bounds due to the natural difficulty of the task. Compare for example the work by De et al. (Table 9), where even auditing with MNIST in the DP threat model leads to very loose membership inference bounds. In this sense, performing the auditing experiments using low-dimensional/synthetic data has a higher probability of revealing a lack of tightness in our bounds, which is desirable in the current study.  \n\n> Could the proposed DP be generalizable to defend against our privacy attacks such as model inversion/data reconstruction attacks?\n\nThe reviewer’s insight into the potential application of our method to bounding model inversion/data reconstruction attacks is correct. Our approach is indeed applicable to bounding the success of reconstruction attacks thanks to the connection to the concept of “Reconstruction Robustness” which has been established in the recent works by Hayes et al. and Balle et al.. Moreover, Kaissis et al. have recently shown that the hypothesis testing interpretation allows one to directly bound the reconstruction attack success probability of an adversary when the trade-off function is known. Therefore, our membership inference bounds can be translated into bounds on reconstruction attacks. In response to the reviewer’s comment, we have now conducted additional experiments on this aspect. For both image recognition and natural language processing tasks, we show that the probability of a successful reconstruction attack is much lower for a relaxed threat model adversary compared to a DP threat model adversary. We refer to the attached PDF document (Figure S2) for the results, and to the “Global Reviewer Comment” for further details.\n\n> I would suggest the authors to clearly state \"membership inference adversaries\" in the title instead of \"adversaries\" in general.\n\nWe appreciate the reviewer’s suggestion regarding the title. However, since we now also include evidence that our threat model is applicable to bounding reconstruction attacks, we would propose keeping the title, but are open to feedback from the reviewer. \n"}, {"review_id": "GhhKzoMNxH", "reviewer": "Reviewer_5PdE", "summary": "In the context of membership inference attacks, the authors consider a relaxation of the differential privacy threat model (RTM) wherein the adversary lacks access to the targeted data record. By adopting the binary hypothesis testing formalism commonly employed in the DP literature, the authors prove that the RTM adversary is weaker than the standard DP adversary. Additionally, they prove that it is possible to design uniformly most powerful tests under the monotone likelihood ratio property. Since the Laplace, Gaussian, and Poisson-subsampled Gaussian mechanisms satisfy this property, the authors are able to find the optimal error rates for these three mechanisms under RTM. Finally, the authors include numerical illustrations using state-of-the-art membership inference attacks.", "questions": "While studying additive mechanisms serves as a valuable initial assessment, the emphasis on these mechanisms alone appears somewhat restricted in scope. To enhance the potential impact of the paper, it would be beneficial for the authors to analyze more complex privacy mechanisms. While conducting such an analysis analytically may present considerable challenges, it may be feasible to develop a principled approach that combines theoretical and empirical methods to address this objective.", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In order to incorporate privacy into real-life applications, it is necessary to calibrate privacy mechanisms against practical threats that relax the differential privacy assumptions. The present paper explores this research direction.", "weaknesses": "The problem addressed in this paper is of significant importance; however, the paper falls short in delivering substantial results as many of them appear to be straightforward and intuitive. While some proofs may be laborious, a significant portion of the results can be attributed to classical results in statistics. The introduction of the concept of \"lambda-Detection Resilience\" adds unnecessary complexity, and the results derived from this notion (Lemmas 6 and 7) lack depth. Furthermore, the provided illustrations are elementary and do not contribute significantly to the overall understanding. Collectively, both the theoretical and empirical contributions lack the desired impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their remarks and appreciate the critical feedback, as it provides an opportunity for us to clarify and strengthen our contributions. \n\n> (...) the paper falls short in delivering substantial results as many of them appear to be straightforward and intuitive (...)\n\nWe appreciate the reviewer's recognition of the significance of the problem at hand. Similar to previous works in the field (e.g. Dong et al., Gaussian DP), we leverage results from classical hypothesis testing to formulate our bounds. This is a conscious choice to retain the frame of reference of hypothesis testing DP and render our bounds comparable to $f$-DP. We would argue that the substance of our work lies in specialising the theory of sub-optimal hypothesis to sub-optimal adversaries to obtain closed-form trade-off curves for the class of privacy mechanisms most relevant to ML applications. The impact of our findings is thus both theoretical and practical: Our findings unlock the formal analysis of a class of sub-optimal adversaries which are of substantial interest in prior literature (Carlini et al., Ye et al., etc.) but have not yet been formally investigated. They are also general enough to be expanded upon to allow users to compute membership inference guarantees for other privacy mechanisms and compare them between the DP threat model and the relaxed threat model using the established tool of trade-off functions. \n\nFinally, the application of our paper’s results allows users to obtain more accurate machine learning models for the nominally same privacy guarantee. To strengthen our work’s contributions regarding this point, we have now undertaken a set of additional experiments on deep learning in complex image and language modelling applications, showing that our bounds translate into improved privacy/accuracy trade-offs. Moreover, to further strengthen our work’s impact in terms of the interplay between theoretical and practical methods, we have now also included additional results which demonstrate that our guarantees can be directly translated into stronger bounds on data reconstruction attacks, a point which was also of interest to other reviewers. These results can be found in the attached PDF (Figures S1 and S2) and details can be found in the “Global Reviewer Comment”.\n\n>  The introduction of the concept of \"lambda-Detection Resilience\" adds unnecessary complexity and (...) (Lemmas 6 and 7) lack depth.\n\nWhile we acknowledge that the concept of $\\lambda$-DR may at first glance seem complex, its introduction is important as it serves as a unified frame of comparison with $f$-DP by paralleling its definition. This is vital to accurately depict membership inference guarantees and to differentiate $\\lambda$-DR from $f$-DP—a crucial distinction, as a misinterpretation of our guarantees by users could lead to unintended consequences.\nLemmas 6 and 7 formally specify the relationship between $f$-DP and $\\lambda$-DR mechanisms concerning one of the most critical properties of privacy guarantees: post-processing resilience. They therefore allow readers to understand the relevant properties of our guarantee at a glance.\n\n> (...) the provided illustrations (...) do not contribute significantly to the overall understanding (...)\n\nWe appreciate the reviewer’s feedback concerning the illustrations, but would like to offer a slightly different perspective on their role and significance. Our paper is rich in mathematical formulas, and the expressions for the trade-off functions are even more complex than in the DP threat model (e.g. due to the appearance of hyperbolic trigonometric functions in the Laplace mechanism). Therefore, the illustrations are not merely supplementary but convey the actual form of the trade-off function’s graphs. Comparisons in function space are inherently comparisons between infinite-dimensional objects. Without these visual aids, understanding the relationships between trade-off functions in the DP threat model and the relaxed threat model would be very challenging for readers. Furthermore, the usage of trade-off function plots like the ones in our paper is established practice in literature. For example, the work by Dong et al. makes extensive use of trade-off function plots and the works of Carlini et al. and Ye et al. use trade-off function visualisations to compare attack success. We thus believe that the illustrations contribute to the overall understanding of our work while aligning with conventions of the field.\n\n> While studying additive mechanisms serves as a valuable initial assessment the emphasis on these mechanisms alone appears somewhat restricted in scope (...)\n\nWe thank the reviewer for the suggestion to extend our analysis to additional privacy mechanisms. While the term \"complex mechanisms\" may encompass a broad range of concepts, we understand the importance of extending our work to diverse applications. We have already taken steps in this direction by conducting the aforementioned additional experiments in more complex machine learning workflows and in bounding data reconstruction attacks. As noted in the manuscript, the theory we develop is general enough to analyse any privacy mechanism, provided the test statistics for the relaxed threat model are well-defined. Our current analysis is consciously centred on the class of additive noise mechanisms, since they are arguably the most important class of mechanisms for machine learning applications (especially the sampled Gaussian mechanism). This importance is illustrated by seminal work in the field, such as the paper by De et al. The reviewer is correct in observing that the analysis of additional privacy mechanisms is challenging, and we are actively working on overcoming these challenges in our ongoing research. As noted in the conclusion of our paper, we view these areas as fruitful targets for future exploration, aligning with our goal to bridge theoretical insights with real-world implementation.\n"}, {"review_id": "W0nUsDOgVe", "reviewer": "Reviewer_9uc5", "summary": "The paper proposes a notion of privacy called Detection Resilience, which quantifies success of a membership inference adversary in a relaxed threat model in which the adversary does not have access to the target example. This is in contrast to the standard strong adversary model in Differential Privacy that has this knowledge. The paper provides a series of theoretical results regarding the relaxed threat model, showing how to characterize the optimal adversary under the relaxation, which for common privacy mechanisms boils down to one-sided hypothesis testing. The trade-off curve of the most powerful test can be used to describe privacy similarly to f-privacy. Next, the paper provides expressions that enable to numerically compute the trade-off curves for Laplace, Gaussian, and Subsampled Gaussian mechanisms. Finally, using synthetic setups the paper visualizes the difference between the trade-off curves in the relaxed model and f-privacy, and shows that the trade-off curves of empirical membership inference attacks are close to those predicted by the theory.", "questions": "* Line 280 \"[In adaptive composition] a database and mechanism parameters are fixed ahead of time, and all intermediate results are released to $A_{SO}$, or –equivalently– the components the mechanism’s outcomes are independent of one another.\" Are these two settings well-known to be equivalent to adaptive composition? Is there a citation?\n* If I understand the former setting (\"all intermediate results are released to $A_{SO}$\"), the composition results are applicable to standard analyses of DP-SGD. Is this right, or are there fundamental barriers to computing the DR guarantees of DP-SGD using the proposed techniques?\n* How exactly is the membership inference attack in the experimental section set up? Does it use shadow models? How many? What are the error bars over in Figure 3?", "limitations": "- The paper's title reads as an overclaim. The content covers optimal guarantees to **one** particular relaxed threat model, thus \"Optimal privacy guarantees against sub-optimal adversaries\" is a stretch.\n- The paper does not describe what are the particular privacy harms that are protected in the strong adversary model of DP that are not protected by the relaxed notion.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**A great step towards useful provable privacy guarantees in DP.** The pessimistic nature of privacy guarantees afforded by DP has been a critical barrier to its deployment. The paper proposes a novel notion of privacy in a relaxation of the standard \"strong adversary\" model. Thus, it should enable to reduce the noise added during private training while keeping reasonable privacy guarantees, i.e. the guarantees within the relaxed model. *This is the first paper that provides such actionable relaxation* that I am aware of. The prior notions of privacy that incorporate background knowledge rely on assumptions about the data distribution, whereas the notion proposed in the paper does not.", "weaknesses": "- W1. **The threat model does not correspond to relevant privacy threats.** The proposed relaxation of the adversarial model in DP, although is a great step towards provable guarantees for realistic attack scenarios, does not model an actually practically relevant threat model. This is because it assumes the adversary does not know the challenge example. To the contrary, in many standard models of practical membership inference attacks the adversary starts with a challenge example they want to attack. For example, this is the case in the \"offline attack\" by Carlini et al. [12] that is cited as the motivation.\n\n  Instead of a realistic setting, I believe the proposed approach models something that is amenable to the analysis using the decision-theoretic tools in a natural extension of the hypothesis testing interpretation of DP (this is not to say this is something bad on its own).\n\n- W2. **No results with DP-SGD.** The paper seems to make most of the steps needed to evaluate privacy-guarantees under composition, e.g., DP-SGD yet does not quite go there. Without these experiments, it is impossible to gauge the utility gains of relaxing the threat model in most machine learning applications.\n\nNitpicks:\n- Clarity: \n  - The contributions paragraph could be interpreted as that the paper studies any relaxed threat models.\n  - The text does not provide sufficient context for Lemmas 1-3. It would be clearer to exactly define UMP in the context of any given Lemma.\n- DR is a rather confusing name\n- Line 92, 499, 508: Should be double bars to denote the norm?\n- Line 251: Unclear writing\n- Lines 103: The signature of the $\\mathcal{M}$ function in the definition of the hypotheses is inconsistent with the notation right above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We warmly thank the reviewer for the encouraging and insightful review of our paper. We are truly heartened by the recognition of our work as \"a great step towards useful provable privacy guarantees in DP\".\n\n> W1. The threat model does not correspond to relevant privacy threats.\n\nWe understand the reviewer’s concern that our proposed threat model does not correspond to an actual privacy threat, and would like to clarify this point.\n\nThe guarantees we derive are directly applicable to offline MI because in both our membership inference game and in offline MI, the adversary does not evaluate the likelihood at the challenge example. In our threat model, this is by design, whereas in offline MI it is usually by choice (e.g. to save computation). We chose to formulate our privacy game in this specific manner to align with common practices in formal security games. In such games, adversaries are typically designed to exploit all available means to breach security. It would be unconventional in terms of formal design for an adversary to \"choose not to do something\". We will clarify this point in the final manuscript and thank the reviewer for bringing this to our attention.\n\n> W2. No results with DP-SGD.\n\nWe appreciate this suggestion by the reviewer and have now conducted additional experiments which demonstrate the applicability of our threat model relaxation to the analysis of DP-SGD in both image recognition (CIFAR-10 and ImageNet) and natural language processing with transformers (SNLI). As the reviewer correctly assumed, analysing DP-SGD with the relaxed threat model allows us to obtain models with higher accuracy and/or lower privacy trade-offs (e.g. up to 14% higher accuracy in CIFAR-10). Moreover, in response to suggestions by other reviewers, we have also included an analysis of reconstruction attacks against models trained with DP-SGD, where we show that, in the relaxed threat model, the probability of a successful reconstruction attack is provably lower than in the DP threat model. These results can be found in the attached PDF (Figures S1/S2) and further comments can be found in the “Global Reviewer Comment”.\n\n> Nitpicks - Clarity\n\nWe thank the reviewer for calling these to our attention. We will make the requested clarifications in the contribution paragraph, define what a “uniformly most powerful test” is, and clarify the norm notation, the writing in line 251 and the signature of the functions in lines 101 ff.\n\nOn the topic of choosing the term “detection resilience”, we chose the term “detection” due to its connection to the notion of \"signal detection\" in hypothesis testing, which is a fundamental concept underlying our work. We are open to considering alternatives that may better convey the meaning of this concept.\n\n> Questions - adaptive composition in lines 280ff.\n\nWe acknowledge that the writing here may have been confusing, and will clarify it in the final manuscript. The settings referred to in lines 280 ff. are indeed consistent with the standard approach used when analysing DP-SGD. Specifically, the mechanism parameters are not chosen adaptively at each round but either kept fixed for all rounds or are set in advance. In other words, any changes made to the privacy parameters are determined ahead of time and not influenced by previous outcomes (this is what was meant by “the components of the mechanism outputs are independent of one another”, i.e. conditional independence of the noise draws). Moreover, it is assumed that no post-processing of the intermediate outcomes takes place. In this context, our result can indeed be applied to DP-SGD, and we provide results on deep learning applications with DP-SGD in the attached PDF (Figure S1). \n\n> Questions - experimental details in Figure 3\n\nWe thank the reviewer for their inquiry. The setup for the membership inference attack is described in Appendix 7.3, as it was too extensive to fit in the main manuscript. We utilised auditing techniques as described by Carlini et al. (employing shadow models without data poisoning) and by Nasr et al. (using shadow models with additional gradient poisoning). A total of 1024 shadow models were used in our experiments. The error bars in Figure 3 represent the standard deviation of the Type-II error over 1024 repetitions of the experiment (i.e., 1024 shadow models and 1024 repetitions). \n\n> Limitations - change of title\n\nWe thank the reviewer for this feedback and understand the concern that the original title may appear as an overclaim. In light of the reviewer’s suggestion, we would propose the following alternative title: \"Optimal Privacy Guarantees for a Relaxed Threat Model: Addressing Sub-Optimal Adversaries in Differentially Private Machine Learning\". We of course welcome alternative suggestions by the reviewer.\n\n> Limitations - privacy threats which are protected in the DP threat model vs. the relaxed threat model\n\nWe thank the reviewer for this remark. Both differential privacy and detection resilience formally protect against membership inference attacks and, by extension, against all weaker forms of attack, notably data reconstruction attacks (we demonstrate the improvement in reconstruction attack bounds in the new experiments – compare the attached PDF). The difference between the two is that the protection of differential privacy also holds against an adversary who can employ auxiliary information (in form of the challenge example) and/or post-process the mechanism output, whereas detection resilience does not. We will clarify this point in the final manuscript.\n"}]

Author rebuttal:
## Global Reviewer Comment

We would like to thank the reviewers for their thoughtful comments and suggestions for further experiments. In response to the feedback, we conducted additional experiments focusing on the two requested aspects: (1) obtaining improved accuracy/utility trade-offs in differentially private stochastic gradient descent (DP-SGD), and (2) applying our bounds to data reconstruction attacks. We outline the findings below and refer to the attached PDF for two additional figures which demonstrate the results.

### Large Datasets and DP-SGD Applications
Some reviewers pointed out the importance of large datasets and showcasing applications to DP-SGD to demonstrate the benefits of our approach. Accordingly, we investigated whether the tighter privacy bounds of the RTM could be utilised to train deep learning models with better accuracy/privacy trade-offs, which we found to be the case.

#### Methodology
We performed experiments on three classification tasks: CIFAR-10 using ResNet-9, ImageNet using ResNet-18, and Stanford SNLI using a BERT transformer. For CIFAR-10, we followed the state-of-the-art approach of De et al. and for ImageNet the approach by Kurakin et al., to obtain results comparable to current literature. In each experiment, we first fixed a final privacy guarantee for the DP threat model, and then trained the model to reach this privacy guarantee. Concretely, we selected an $(\varepsilon, \delta)$-DP guarantee for the final model (equivalently, a maximum allowed probability of a true positive membership attack at a pre-set level of Type-I error). We then computed the DP-SGD noise scale corresponding to the same final privacy guarantee for the relaxed threat model, and re-trained the model for the same number of steps.

#### Findings
For all datasets, the enhanced privacy guarantees of the RTM allowed us to obtain models with higher out-of-sample (validation set) accuracy (e.g. up to 14% higher on CIFAR-10 at $\varepsilon=1$) for the nominally same membership inference guarantee, since we were able to lower the DP-SGD noise scale. These results, illustrated in Figure S1, demonstrate how our theoretical bounds can be leveraged by practitioners to achieve improved privacy/accuracy trade-offs through our proposed threat model relaxation.

### Applicability to Data Reconstruction Attacks
Some reviewers also requested a discussion on whether it is possible to extend our membership inference bounds to data reconstruction attack bounds. In fact, it is possible to directly and tightly bound the probability of a successful data reconstruction attack with the Reconstruction Robustness (ReRo) framework (Balle et al.). In brief, the goal of the ReRo adversary is to obtain a successful reconstruction (from model weights/gradients), defined as a reconstruction loss $\leq \eta$, e.g. MSE or perceptual loss. The ReRo framework models the adversary’s prior knowledge as the probability $\kappa(\eta)$ of a successful reconstruction before/without observing the model weights/gradients. Satisfying ReRo then requires that the probability of reconstruction after observing the model weights/gradients to be $\leq \gamma$. In recent work, Kaissis et al. show that, if the trade-off function of a privacy mechanism is known, the probability of reconstruction $\gamma$ can be computed directly, allowing us to extend our theoretical membership inference guarantees to tight bounds on the probability of success of reconstruction attacks. Since Detection Resilience is expressed in terms of trade-off functions, the relaxed threat model we study extends naturally to this type of attack, as suggested by the reviewers. 

#### Findings
We conducted experiments under (highly) pessimistic assumptions about the adversary: We assume that the adversary has a prior probability of successful reconstruction $\kappa(\eta)=0.1$ (a more optimistic baseline would be a uniform prior over the entire dataset, i.e. $1/N \approx 10^{-6}$ for ImageNet). Moreover, following the pessimistic assumption made in lines 296ff. of our manuscript (i.e. that the adversary can design a database which influences only a single entry in the weight/gradient vector), we assumed $d=1$ for the construction of all trade-off functions in the experiments.
We then analysed the DP-SGD applications mentioned above (CIFAR-10, ImageNet and Stanford SNLI). Even under these permissive assumptions, our findings, detailed in Figure S2, show that the relaxed threat model adversary has a substantially lower probability of success in reconstructing model inputs compared to the DP adversary.

---

### References for all rebuttal comments below and the attached PDF

Hayes, J., Mahloujifar, S., & Balle, B. (2023). Bounding Training Data Reconstruction in DP-SGD. arXiv preprint arXiv:2302.07225.

Kurakin, A., Song, S., Chien, S., Geambasu, R., Terzis, A., & Thakurta, A. (2022). Toward training at imagenet scale with differential privacy. arXiv preprint arXiv:2201.12328.

De, S., Berrada, L., Hayes, J., Smith, S. L., & Balle, B. (2022). Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13650.

Kaissis, G., Hayes, J., Ziller, A., & Rueckert, D. (2023). Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy. arXiv preprint arXiv:2307.03928.

Balle, B., Cherubin, G., & Hayes, J. (2022, May). Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP) (pp. 1138-1156). IEEE.

Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2018). BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pp. 4171-4186. 2019.

Nasr, M., Hayes, J., Steinke, T., Balle, B., Tramèr, F., Jagielski, M., ... & Terzis, A. (2023). Tight Auditing of Differentially Private Machine Learning. arXiv preprint arXiv:2302.07956.


Meta-review: This paper proposes to study a weaker adversary than the one considered in standard differential privacy.
This is certainly an important and interesting goal, given that there seems to be a large gap between provable privacy guarantees and actual attacks on privacy.
Many of the reviewers were confused by the paper's threat model and claims, which seem to have been clarified with the rebuttal.
I encourage the authors to incorporate the feedback from the reviewers to better describe their main claims in the final version.
Decision: Accept (poster)