Provable Membership Inference Privacy
Authors: Zachary Izzo
Jinsung Yoon
Sercan O Arik
James Zou
Venue: Accepted by TMLR ()

Abstract: In applications involving sensitive data, such as finance and healthcare, the necessity for preserving data privacy can be a significant barrier to machine learning model development. Differential privacy (DP) has emerged as one canonical standard for provable privacy. However, DP’s strong theoretical guarantees often come at the cost of a large drop in its utility for machine learning; and DP guarantees themselves are difficult to interpret. In this work, we propose a novel privacy notion, membership inference privacy (MIP), as a step towards addressing these challenges. We give a precise characterization of the relationship between MIP and DP, and show that in some cases, MIP can be achieved using less amount of randomness compared to the amount required for guaranteeing DP, leading to smaller drop in utility. MIP guarantees are also easily interpretable in terms of the success rate of membership inference attacks in a simple random subsampling setting. As a proof of concept, we also provide a simple algorithm for guaranteeing MIP without needing to guarantee DP.

Published in Transactions on Machine Learning Research (04/2024)
Provable Membership Inference Privacy
Zachary Izzo* NEC Labs America
zach@nec-labss com
Jinsung Yoon Google Cloud Al
mhnsungyoon@google.com
Serean Ö. Arık Google Cloud Al
soorik@google.com com
James Zou
jameszüstanfores edu
Department of Biomedical Data Science Stanford University
Reviewed on OpenReview: https: // openreview. net/ forum? id= id=3ludyaPbbo
Abstract
In applications involving sensitive data, such as finance and healthcare, the necessity for preserving data privacy can be significant barrier to machine learning model development. Differential privacy (DP) has emerged
canonical standard for provable privacy. However, DP's strong theoretical guarantees often come at the cost, of large drop in its utility for machine learning; and DP guarantees themselves are difficult to interpret. In this work, we proposc a novel privacy notion, membership inference privacy (MIP), as a step towards addressing these challenges. We give a precise characterization of the relationship between MTP and DP, and show that some cases, MTP can be achieved using less amount of randomness compared to the amount required for guaranteeing DP, leading drop in utility. MIP guarantees membership inference attacks in simple random subsampling setting. As a proof of concept, we also provide simple algorithm for guarantecing MIP without needing to guarantee DP.
smaller
also easily interpretable in terms of the success rate of
1 Introduction
As the popularity and efficacy machine learning (ML) have increased, the number of domains in which ML is applied has also expanded greatly. Some of these domains, such as finance or healthcare, have ML on sensitive data which cannot be publicly shared due regulatory or ethical concerns (Assefa al. 2020 Office for Civil Rights 2002). Tn these instances, maintaining data privacy is of paramount importance and must be considered at every stage of the ML process, from model development to deployment. Even sharing data in-house while retaining the appropriate level of privacy can be a barrier to model development (Assefa et al. 2020). During deployment, the trained model itself can leak information about the training data if proper precautions are not taken (Shokri et al. 2017 Carlini et al. 2021a).
Differential privacy (DP) (Dwork et al.) 2014) has emerged as gold standard for provable privacy in the academic literature. Training methods for DP use randomized algorithms applied on databases of points, and DP stipulates that the algorithm's 's random output cannot change much depending the presence or absence of an individual point in the database. These guaranlees in turn give information theoretic protection against the maximum amount of information that an adversary can obtain about any particular sample in the dataset, regardless of that adversary's 's prior knowledge or computational power, making DP an attractive method for guarantceing privacy. However, DP's strong theoretical guarantecs often come at the cost of a large drop in
*Part. of this project was done while author was an intern Google Cloud AT.

---

Published in Transactions on Machine Learning Research (04/2024)
Privacy Guarantees
Noise Required
Relevant Quantities
DP
Stronger
Sometimes higher
Probability laws/hyypthesis testing
MIP (Ours)
Weaker
Sometimes lower
Subsampling and attacker performance
Table I: A summary of the differences between differential privacy (DP) and membership inference privacy (MTP, notion). DP comes with strong privacy guarantees, but these strong guarantees require large amounts of noise to be added to the algorithm. MIP is relaxed notion of privacy, providing weaker privacy guarantees but also potentially requiring less noise and allowing for greater utility. MIP guarantees are defined in terms of simple quantities, and therefore may be easier for non-experts to interpret.
utility for many algorithms Jayaraman and Evans, 2019). In addition, DP guarantees themselves difficult. to interpret by non-experts. There is precise definition for what it means for algorithm to satisfy DP with = 10, but it is not a priori clear what this definition guarantees in terms of practical questions that users could have, the most basic of which might be to ask whether an attacker can determine whether that user's information was included in the algorithm's input. These constitute challenges for adoption of DP in practice.
In this paper, we develop the theoretical underpinnings of a novel privacy notion, membership inference privacy (MIP), first step towards addressing these challenges. Membership inference measures privacy via game played between the algorithm designer and adversary or attacker. The adversary is presented with the algorithm's 's output and "target" sample, which may or may not have been included in the algorithm's 's input set. The adversary's 's goal is to determine whether the target sample was included in the algorithm's 's input. If the adversary can succeed with probability much higher than random guessing, the algorithm must be leaking information about its input.
Membership inference is one of the simplest possible privacy violations, as the attacker only needs to infer single bit; thus, provably protecting against membership inference provides strong privacy guarantee. Furthermore, MIP may be easier for non-experts to interpret, as it is measured with respect to a simple quantity-namele the maximum success rate of an attacker on the membership inference task, which requires only a simple sampling scheme lo implement. In summary, our contributions are as follows:
We propose a novel privacy notion, which we dub membership inference privacy (MIP), and study its properties.
We characterize the relationship between MIP and differential privacy (DP). In particular, we show that DP is sufficient to certify MIP and quantify the correspondence.
We demonstrate that in some cases, MIP can be certified using less randomness than that required for certifying DP. In other words, while DP is sufficient for certifying MTP, is not necessary. Thus, MIP is a weaker (but still powerful!) notion of privacy than DP, allowing for greater utility on the base task. A comparison of MIP and DP features given in Table
We introduce a "wrapper" method for turning any base algorithı with continuous outputs into an algorithm which satisfies MIP.
2
Related Work
Privacy Attacks in ML The study of privacy attacks has recently gained popularity in the machine learning community as the importance of data privacy has become more apparent. In membership inference altack (Shokri et al. 2017), an altacker is presented with a particular sample and the output of the algorithm to be attacked. The attacker's goal is to determine whether the presented sample was included the training data or not. If the attacker can determine the membership of the sample with a probability much greater than random guessing, this indicates that the algorithm leaking information about its training data. Obscuring whether given individual belongs to the private dataset is the core promise of private data sharing, and the
2

---

Published in Transactions on Machine Learning Research (04/2024)
main reason that we focus membership inference the privacy measure. Membership inference attacks against predictive models have been studied extensively (Shokri et al. 2017 Baluta et al. 2022 Hu et al.)
2022 Liu et al. 2022 He et al. 2022 Carlini et al. (021a), and recent works have also developed membership inference attacks against synthetic data (Stadler et al. 2022 Chen et al. 2020
In a reconstruction attack, the attacker is not presented with a real sample to classify as belonging to the training set or not, but rather has to create samples belonging to the training set based only on the algorithm's 's output. Reconstruction attacks have been successfully conducted against large language models (Carlini et al. 2021b). At present, these attacks require the attacker to have a great deal of auxiliary information to succeed. For our purposes, we are interested in privacy attacks to mcasure the privacy of an algorithm, and such a granular task may place too high burden on the attacker to accurately detect "small" amounts of privacy leakage.
In an attribute inference attack (Bun et al. 2021 Stadler et al., 2022), the attacker trics to infer a sensitive attribute from a particular sample, based on its non-sensitive attributes and the attacked algorithm outputs. It has been argued that attribute inference is the entire goal of statistical learning, and therefore should not be considered privacy violation (Bun et al. 2021
Jayaraman and Evans 2022
Differential Privacy (DP) DP (Dwork et al. 2014) and its variants MMironov 2017
Dwork and Rothblum
2016) offer strong, information--heorriic privacy guarantees. A DP (probabilistic) algorithm is one in which the probability law of its output does not change much if one sample in its input is changed. To be precise, given two datasets D and D', we say that these datasets are adjacent (denoted D ~ D") if (D) D' = D'' D =1 or cquivalently if D and D' differ by replacing exactly onc element. We say that the algorithm A is (E, (D
if
P(A(D) E S) S <FP(((DD)) E ES) +
for any subset S of the output space, and for any two adjacent datatsets D~ D'. DP has many desirable properties, such as the ability to compose DP methods or post-process the output without losing guarantees. Many simple "wrapper" methods are also available for certifying DP. Among the simplest, the Laplace mechanism, adds Laplace noise to the algorithm output. The noise level must generally depend on the sensitivity of the base algorithm, which measures how much a single input sample can change the algorithm's is output. The method we propose in this work is similar to the Laplace mechanism, but we show that the amount of noise needed can be reduced drastically. Enforcing DP with high levels of privacy (small s) often comes with sharp decreases in algorithm utility (Tao et al. 2021 Stadler et al.) 2022). DP is also difficult to audit; it must be proven mathematically for a given a algorithm, and checking it empirically is generally computationally intractable (Gilbert and McMillan 2018). The difficulty of checking DP has led to widespread implementation issues (and even errors due to finite machine precision), which invalidate the guarantecs of DP (Jagielski et al. )
While the basic definition of DP can be difficult to interpret, equivalent "operational" definitions have been developed (Wasserman and Zhou 2010: Kairouz al. 2015 Nasr et al., (022)). These works show that DP can equivalently be expressed in terms of the maximum success rate distinguish bet between two adjacent datasets D and D', given only the output of DP algorithm. While similar to the setting of membership inference considered in this paper at face value, there are subtle differences. In particular, in the case of membership inference, one must consider all datasets which could have contained the target record, and all datasets which do not contain the target record, and distinguish between the algorithm's 's output above, which only needs to distinguish between & single pair of datasets at any given time. [Humphiie et al. (023)) also studied membership inference attacks against DP-SGD in the presence of data dependencies, and they used the operational definitions to bound the success rate of a MIA against DP algorithm in a simplified membership inference setting where the whole training datasct except for the target record is known, effectively reducing the problem to the hypothesis lesting formulation of DP. Our methods also make use of subsampling, and therefore bear some resemblance to the DP literature on privacy amplification via subsampling (Balle et al. 2018). These results show that the privacy level of DP algorithms can be amplified if the input is first subsampled. In the present work, subsampling is instead used for privacy measurement, and thus constitutes fundamentally different use case. (Refer to Section 3.3 for more details.) The independent.
adversary which seeks to
this larger space of possibilities. This is in contrast to the characterization of DP
3

---

Published in Transactions on Machine Learning Research (04/2024)
work of Thudi et al. (002)) specifically applies DP to bound membership inference rates, and our results in Section 3.4 complement theirs on the relationship between membership inference and DP. However, our results show that DP is not reguired to prevent membership inference; it is merely one option, and we give alternative methods for defending against membership inference.
Membership Inference as a Measure of Privacy Previous works have also sought to understand privacy guarantees via membership inference. Lee and Clifton (2012) propose a privacy notion they call differential identifiability in order to address the difficulty of interpreting DP guarantocs. Li et al. (2013) propose notion called membership privacy. Both of these notions rely on bounding the change between an attacker's prior and posterior belief on the membership of target records, conditional observing the output of the private algorithm. As we will discuss in detail in Section 3.4 because these notions require conditional, rather than marginal, bounds on the posterior, they are also distinct from (and generally stronger than) MIP. Nasr et al. (2018) also introduce a notion of membership privacy (which is technically distinet from Li et al. (2013)), which they enforce via a min-max optimization problem. While they do provide theoretical results, these guarantees hold only assuming that the optimal membership inference adversary can be computed exactly; in practice, this must. be approximated (e.g- with a neural network). Furthermore, their notion of membership privacy does not allow the user to specify the desired privacy level (i.c., something akin to the parameter for DP or the v parameter for MIP, which will introduce shorlly). Long el al. (2017) propose an empirical measure of privacy loss based on membership inference. Experiments confirm that their notion correlates closely with empirical privacy loss, but their hcuristic does not come with provable guarantecs.
3 Membership Inference Privacy
In this section, we will motivate and define membership inference privacy and derive several theoretical results pertaining to it. Full proofs and/or proof sketches of all propositions and theorems can be found the Appendix.
3.1 Notation
We make use of the following notation. We will use D to refer to our entire dataset, which consists of n samples all of which must remain private. We will use E 'D or x* E D to refer to particular sample. Dtrain C DD refers to a size-k subset of D. We will assume the subset is selected randomily, so Derain is a random variable. The remaining data D Dirain will be referred to as the holdout data. We denote by D the set of all sizc-l subscts of 'D (i.c., all possible training sets), and we will use D to refer to a particular realization of the random variable Durain. Given particular sample x* E D, D (resp. Do"")) will refer sets D E Do for which x" D (resp. x" & D). Lastly, we will the notation D D' to denote that the datasets D and D' are adjacent, that is, they differ in exactly one element.
3.2 Theoretical Motivation
The implicit assumption behind the public release of any statistical algorithm be it a generative or predictive ML model, or even the release of simple population statistics is that it is acceptable for statistical information about the modelled data to be released publicly. In the context of membership inference, this poses a potential problem: the population we are modcling significantly different from the "larger" population, then our algorithm's 's output contains any useful information whatsoever, should be possible for an attacker to infer whether given record could have plausibly come from our training data or not.
We illustrate this concept with an example. Suppose the goal is to publish an ML model which predicts a palient's 's blood pressure from several biomarkers, specifically for patients who suller from a particular chronic disease. To do this, we collect a dataset of individuals with confirmed cases of the disease, and use this data to train a lincar regression model with coefficients å. Formally, we let x E Rd denote the features (e.g. biomarker values), denote the patient's blood pressure, and y = 1 [ppttinn has the chronic discase in question). In this case, the private dataset Dirain contains only the patients with y 1. Assume that in the general
4

---

Published in Transactions on Machine Learning Research (04/2024)
populace, patient features drawn from mixture model:
y Bernoullip),
x x~ ~~,,0, I),
z|x,y~ ~ 0jx, Oo + 01.
In the membership inference attack scenario, an adversary observes a data point (x*, 2²) and the model 0 and tries to determine whether (x*,²*) E Dersin. If 6b and 81 are well-separated, then an adversary can train an effective classifier determine the corresponding label II [[(x", =²) ) E Perain) for (x*,²*) ) by checking whether x" = x'x". Since only data with = belong to Derain this provides a signal to the adversary as to whether x* could have belonged to Dirain or not. The point is that in this setting, this outcome is unavoidable if is to provide any utility whatsoever. In other words:
In order to preserve utility, membership inference privacy must be measured with respect to the distribution from which the private data are drawn.
The example above motivates the following theoretical ideal for our membership inference setting. Let D {x+]== be the private dataset and suppose that Xi 1i.d. P for some probability distribution P. (Note: Here, x" corresponds to the complete datapoint (x",2") in the example above.) Let A be our (randomized) algorithm, and denote its output by 0 = A(D). We generate a test point by first drawing y" ~ Bernoulli (1/2), then
x x"w ~ ~ Unit((eera))))) + 11--y") )P:
i.c. x' is fresh draw from P random element of the private training data with equal probability. Let I denote any membership inference algorithm which takes as input x* and the algorithm's 's oulput 0 = A(Drrain). The notion of privacy we wish to enforce is that I cannot do much better to ascertain the membership of x* than guessing randomly:
P(Z(x" 0) y²) 1122+
(1)
where the probability is taken over the randomness in AA and Derain, and idcally n < 1/2.
3.3 Approximation via the Empirical Distribution
In reality, we do not have access to the underlying distribution P. Instead, we propose to use samples from a suitable empirical distribution to approximate fresh draws from P.
Definition 1 (Membership Inference Privacy (MIP)). Given fixed ls n, let Durin C be size-k subset chosen uniformly at random from the elements in 'D. For x" E ED, let v² [xx E DDrrai). An algorithm A is M-MIP with respect to D if for any identification algorithm I and for every x* E DD, we have
{ k -
A(Dtminn) = y")
)==)))))) S max
( +
Here, the probability is taken over the uniformly random size-k subset Deruin S D, as well as any rondomness in A and I.
Definition D states that given the output of A, an adversary cannot determine whether a given point was in the holdout set or training set with probability more than v) better than always guessing the a priori more likely outcome. In the remainder of the paper, we will set k: = n/2, so that is 7-MIP if an attacker camnol. have average accuracy greater than (1/2+ This gives the largest priori entropy for the attacker's classification task, which creates the highest ceiling on how much of an advantage gain from the algorithm's 's output, and consequently the most accurate measurement of privacy leakage. The choice k = n/2 also keeps us as close as possible to the theoretical motivation in the previous subsection. We note that analogues of all of our results apply for general k.
attacker can possibly
We also remark that MIP guarantces specify that the adversary cannot distinguish between points D Drrain and D \ Diraini however, this does not rule out the possibility that the adversary may be able determine whether or not point was in the "base" dataset. D or not. Indeed, the leakage about membership information
5

---

Published in Transactions on Machine Learning Research (04/2024)
in D can be arbitrarily high. Consider, for instance, the following "algorithm": A(D) 1(D D). The output of this algorithm gives the adversary no information about whether or not a given x" was in Dtrain for any random subset of D, and it therefore clearly satisfies MIP. However, the output very clearly reveals information about membership in D. For this reason, in order for MIP to apply, membership in the "overall population" 'D should not be considered privale, only membership in Dirain This concrete consequence of the observation made Section 3.2 that membership inference privacy must be mcasured with respect to the distribution of the private data if we are to preserve any utility. Knowledge of membership in 'D is essentially knowledge that the target x" was drawn from the private data distribution.
The definition of MIP is phrased with respect to any classifier (whose randomness is independent of the randomness in A; if the adversary knows the algorithm and the random seed, we have no hope of enforcing privacy). While this definition is compelling in that it shows a bound on what any attacker can hope to accomplish, the need consider all possible attack algorithms makes it difficult to work with technically. The following proposition shows that MIP equivalent to a simpler definition which does not need simultaneously consider all identification algorithms I. We state the theorem in terms of algorithm with discrete output for simplicity, but the result readily generalizes to continuous output by replacing probability masses with densitics.
Let A (A)ge(A) and for simplicity assume that & is discrete. Let P(A(Dtrain) AA denote the probability of given output A E ls over the randomness in Dwain and A. Then A is 7-MIP if and only if
Proposition
1
Σ max (P(x* E Derain A((rra)))) = A), & Dtrain A(Derain) = A)} P(A(D = -4) $ + AEA
Purthermore, the optimal adversary is given by
I(x", A) = 11P(x* E Dirain A(Dtrain) = A) 2 1/2].
Proposition 2 makes precise the intuition that the optimal attacker should guess the more likely of x* E Drrain or x* & Derain conditional on the output of A. The optimal attacker's 's overall accuracy is then computed by marginalizing this conditional statement.
Finally, MTP also satisfies a post-processing inequality similar to the classical result in DP (Dwork et al., 2014). This states that any local functions of MIP algorithm's output cannot degrade the privacy guarantee.
Thcorem 3. Suppose that A is M-MIP and let f be any (potentially randomized, with randomness independent of Durain) function. Then J a is also n -MMIP
Proof. Let I be any membership inference algorithm for fo A. A membership inference attack against, A can be any binary function of the attacked point x* and the algorithm output A. In particular, Ix(x', (x() is such a function, so is permissible to define IA(x", A) I, f(A)). Since A is M-IP we have
1 2 P(IA(X ( y²) PX ((A(D (A((erain)) train) ))) = y²).
Thus, fo A is MIP by Definition
For example, Theorem 3 is important for the application of MIP to generative model training if we can guarantee that our generative model is 7-MIP, then any output produced by it is M/PIP as well.
3.4 Relation to Differential Privacy
In this section, we make precise the relationship between MIP and the most common thcoretical formulation of privacy: differential privacy (DP). Proofs of our results can be found in the Appendix. Our first theorem shows that DP is at least as strong MIP.

---

Published in Transactions on Machine Learning Research (04/2024)
Theorem 4. Let A be (E, ().P.. Then A is n-MIP with 1 6+ --=2- 2. Furthermore, this bound is tight, i.e. for any >> 0 and 0 v ā < 1, there exists on (s, 6)DP algorithm against which the optimal ollacker has accuracy + 1-6 T4
1+e-
The proof makes use of the hypothesis testing interpretation of DP introduced by Kairouz et al. 2015 which we restate here for convenience. Let Do ~ D1 be adjacent datasets, and let Y = A(D) where E (Do: D1}. We define the null and alternative hypotheses
Ho D= Do: :
Hypothesis testing in this context reduces to defining rejection set S: whenever A(D) E S, we reject the null hypothesis, otherwise if A(D) & S, we fail to reject. Kairouz et al. (2015) showed that A is (e, (e, if and only if for all adjacent datasets Du and D1, and for any rejection set S, we have
P(A(Do) S) e(((A(D)) & 55 6, e ((A(D)) ES)+ P(A(D)) $ 2 1 5.
Type
Type
These inequalities give an upper bound on any adversary's accuracy on the task of distinguishing between any two adjacent datasets. We remark that the membership inference problem more complicated setting than this hypothesis testing framework. Rather than simply being presented with two possible subsets Do or Dj and asked to distinguish between only these possibilities, we must distinguish between two large collections of datasets: the (//2) subsets which contain x", and the (x/2) subsets which do not. We emphasize this point because it is nontrivial to show that distinguishing between any two datasets at once also allows one to distinguish between two collections of datasets: moving from the simpler "one versus one" to the more complicated " "many versus many" setting requires establishing a correspondence between sets in D and sets in Dout, For a complete proof, see Appendix B
have defined it is
To help interpret this result, we remark that for 0, a Taylor expansion of 1/(1 + e about & 0 shows that
8 (1 - (1-8)/(1+ 5) 1/2 6/2 0/2+ 8)=/4.
Thus in the regime where strong privacy guarantocs are required (17 z 0), we will need z 0. Substituting into the equation above then yields 1j R e/4.
In fact, DP is strictly stronger than MIP, which we make precise with the following theorem. Theorem 5. For any n > 0, there erists an algorithm A which is n-MIP but not (E. for any e oc and 8 1
In order to better understand the difference between DP and MIP, let us again examine Proposition 2 Recall that this proposition showed that maryinally over the output of A, the conditional probability that
x" E Derain given the algorithm output should not differ too much from the unconditional probability that x" E Derain The following proposition shows that (purc) DP requires this condition to hold for every output of A(Dussuu)
Proposition 6. If A is an O)-DP algorithm, then for any x", we have
PP(x* $ Derain A(Derain) )
P(x" @ Dirain)
P(x* E D Derain A(Derain))
P(x Dirain)
Proposition t can be thought of as an extension of the Bayesian interpretation of DP explained by [Joddon ct al. 2022 Namely, the definition of DP immediately implics that, for any two adjacent sets D and D',
P(Derain D A(Dtrain)) S et P(Derain D)
P Duaann D' A(Derain))
P(Dersin D")
We remark that the proof of Proposition indicates that converting between the case of distinguishing between two adjacent datasets (as in the inequality above, and done in (Wasserman and Zhou 2010
7

---

Theorem 8, Suppose that A is MIPI Then for ony adversary I and any target recond x", have that Published in Transactions on Machine Learning Research (04/2024)
the case of membership inference is non-trivial: both our proof and a similar one by Thudi et al. (2022 require the construction of a injective function between sets which do/do not contain x
Kairouz al, 2015 Nasr et al. 2021
Aside from (approximate) differential privacy, there are other privacy notions such as f-DP or Gaussian DP (GDP) (ong et al., 2019), Renyi DP (RDP) (Mironov) 2017), concentrated DP (CDP) (Dwork and Rothblum 2016), and truncated CDP (tCDP) (Bun et al. 2018). The following theorem shows that MIP is distinct from each of these notions as well.
Theorem 7. For any >>>>0 O, there erists an algorithm A and a dalaset such that A is n-MIP with respect to D, but A not (nontrivially) RDP, CDP, tCDP, or f-DP.
Summary The results of this section elucidate the differences and similarities between MIP and DP. For clarity, we summarize them as follows:
Both DP and MIP are theoretically principled notions of privacy, with provable limitations on the private information that an adversary can obtain given the output of an algorithm which satisfies cither notion.
DP implies general bounds on the outcome of any privacy attack, while MIP guarantees apply specifically to membership inference attacks and, by extension, any privacy attack which would imply successful membership inference attack. Thus, MIP guarantees are relored form of privacy compared to DP.
(a) Theorem shows that DP is at least as strong as MIP by showing that DP implies MIP, and gives the best correspondence possible between the DP and MIP privacy parameters.
(b) Theorems] and show that MIP is strictly weaker than existing forms of DP.
3.5 MIP in the Low False Positive Rate Regime
As presented, MIP measures and bounds privacy loss in terms of an adversary's average accuracy advantage over random guess. However, as argued by Carlini al. (2021a), in some cases may be more relevant. to consider the adversary's true positive rate (TPR) at a low false positive rate (FPR). This corresponds to scenarios in which adversary cannot identify most individuals but can confidently infer that small number of individuals belong to the private dataset, which would still constitute privacy violation even though the average accuracy is low. While MIP is not explicitly defined to address this scenario, MIP actually implies strong results for the low FPR regime as well. This the content of Theorem
(TDix'AADurain)) = |x t E Derain) S ,(([i"",AADraaiii) A(Drrain)) = ||x" R Derain) + m..
In other words, any adversary must have TPR +
Theorem shows that MIP guarantees translate into additive bound on the TPR. Thus, while MIP is defined in terms of average membership inference accuracy, it still provides meaningful measurement and bound of privacy Icakage in the low FPR regime. The connection between the attacker's accuracy and the TPR/FPR gap is not specific to MIP, and indeed the same bound on this gap in lerms of the atlacker's accuracy was shown by Yeom et al. (2018). However, while the form of our bounds is the same, note that Theorem
X docs not follow from Yeom et al. (2018) bocause the membership inference setting considered in their work is different from ours. (In particular, they focused on membership inference in the presence of i.i.d. data.)
8

---

Published in Transactions on Machine Learning Research (04/2024)
4 Guaranteeing MIP via Noise Addition
In this section, we show that a small modification to standard training procedures can be used to guarantee MIP. Suppose that A takes as input a data set D and produces output 0 E R For instance, A may compute a simple statistical query on D, such as mean estimation, but our results apply equally well the case that. e.g, A(D) are the weights of neural network trained on D. If 0 are the weights of a generative model, then if we can guarantee MIP for 8, then by the data processing inequality (Theorem this guarantees privacy for any oulput of the generative model.
The distribution over training data (in our case, the uniform distribution over size n/2 subsets of our complete dataset D) induces a distribution over the output O. The question is, what is the smallest amount of noise we can add to 0 which will guarantee MIP? If we add noise on the order of maxp=D'EP [|A(D) - A(D)Il, then we can adapt the standard proof for guaranteeing DP terms of algorithm sensitivity to show that a restricted version of DP (only with respect subsets of D) holds in this case, which in turn guarantees MIP. However, recall that by Propositions 2 and 6 MIP is only asking for marginal guarantee on the change in the posterior probability of D given A, whereas DP is asking for a conditional guarantee on the posterior. So while max seems necessary for a conditional guarantee, the moments of 0 should be sufficient for a marginal guarantee. Theorem 9 shows that this intuition is correct.
Theorem 9. Let - be any norm, and let gM 2 EB10 EOll PJ be an upper bound on the M-th central moment of 0 with respect to this norm over the randomness in Durain and A. Let X be a random variable with density proportional to exp(- [X]] with c (7.5/n) ft. Finally, let 0 = 0 + X. Then @ is n-MIP,
i.e., for any adversary I,
P(Z(xx, 0) - y²) S 1/22+
At first glance, Theorem g may appear to be adding noise of equal magnitude to all of the coordinates of 8 regardless of how much each contributes to the central moment a. However, by carefully selecting the norm Il I], we can add non-isotropic noise to 0 such that the marginal noise level reflects the variability of each specific coordinate of 0. This is the content of Corollary 10. (GenNormal(j,, a, 33 refers to the probability distribution with density proportional to exp(-(Iz - ()))
Corollary 10. Let M 2 2, o. 2 R[00 - RM, and define || = (Ei 1e. 1/M do vector x = (II....,za)) IT) Generate Y, ~ GonNormal(O,a,, os, U = Y/I|Y|lo.M and drow r ~ Laplace ((6.16/n) Finally, set X = rU and return 0 = 8 Then O is n-MIP
for any
It may be the case that the o; are not known or an analytic upper bound cannot be casily derived. In such cases, an approximale or asymptotic form of MIP can be employed by estimating the o, from daía. We implement this intuition and devise approximate method for applying MIP in Algorithm [ The algorithm has two important caveats. First, remark briefly that the estimator for Jj used in Algorithm I is not unbiased, but it is consistent (i.e., the bias approaches 0 as B + 00). When M = 2, there is a well-known unbiased estimate for the variance which replace 1/B with 1/(B- 1), and one can make similar corrections for general M (Gerlovina and Hubbard 2019). These corrections generally yield very small differences and the naive estimator presented in the algorithm should suffice. Sccond, the conditions of Theorem g and Corollary [0 require that a or 03 are upper bounds on the central moments of the appropriate model parameters. While our estimation procedure for is consistent and guaranteed to give the correct value o0 (or if B = (n122) and all possible subsets Derain are tested, so that a is computed deterministically and exactly), for finite B, it camnot be guaranteed that the estimated a is an upper bound on the contral moment, therefore the results of Theorem g or Corollary [0 cannot be guaranteed to hold. If strict theoretical enforcement of MIP is required, must be guaranteed to be upper bound on the central moment, via other means. While this is not ideal, we believe it is still an improvement over the scnsitivity bound necded for many DP algorithms (c.g., the Laplace mechanism),, since a may be consistently estimated from data, but there is no consistent estimator of the sensitivity. The a estimation heuristic can be viewed as similar to the "folklore" statement in the DP literature that c < is needed for theory, but c < 10 is fine practice (Ponomareva et al. 2023). It also conceivable that the effects of a finite a estimation budget B can be taken into account in the resulting MIP parameter n, but we leave this for future work.
analytical arguments (as is done in Proposition [1 for instance)
9

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm MIP via noise addition
Require: Private dataset D, a estimation budget B, MIP parameter 1
Dirain RANDOMSPLIT(D,1/2
# Estimate if an priori bound is not known
for i= , do
train + RANDOMSPLII(Pusan 1/2) (( f A(D
D (
end for
for j 1, ..... d do
0 + B 1
1 ())
m) 1/M
1 (0, -
end for
Add oppropriate noise the base algorithm's 's output
U + Unif((u Rd ||u]la,
1})
(( (5.10)
1+2/M
+- Laplace
t rU
return A(Duriu)) X
When Does MIP Require Less Noise Than DP? By Theorem any DP algorithm gives rise to a MIP algorithm, so we never need to add more noise than the amount required to guarantee DP, in order to guarantee MIP. However, Theorem 9 shows that MIP affords an advantage over DP when the variance of our algorithm's output (over subsets of size n/2) much smaller than its sensitivity A, which is defined the maximum change in the algorithm's output when evaluated element. For instance, applying the Laplace mechanism from DP requires noise which scales like A/c to guarantee e-DP. It is easy to construct examples where the variance is much smaller than the sensitivity if the output of our "algorithm" is allowed to be completely arbitrary as a function of the input. However, it is more interesting to ask if there are any natural settings in which this occurs. Proposition 11 answers this question in the affirmative by demonstrating an estimation procedure where MIP can require arbitrarily smaller noise than that required by DP.
two datasets which differ in only
Proposition 11. For any finite D S R, define A(D)
Given dataset of size n, define
Σ
BB DDCD [D] [n/2]}, and define
o² Var(A(D)),
max D-D'ED
A(D)
Here the variance is taken over D Uni Then for all n, there exists a dataset with [D] = n such that 2 = 0(1) but A -3)2/33).
In Appendix D we show that the dataset
1/2
# -
= (2
i .n... 2}u
n
2
n/2
==0
I To illustrate this result, we plot the noise level needed to guarantee MTP vs. the corresponding level of DP (with the correspondence given by Theorem 4 for this construction in Fig.
satisfies the conditions of Proposition
Refer to Fig. Dotted lines refer DP, while the solid line for MIP with M The a-axis gives the best possible bound the attacker's improvement in accuracy over random guessing iie., the parameter n
10

---

Published in Transactions on Machine Learning Research (04/2024)
1.0 1e6
0.8
Noise level
MIP (all
0.6
DP (n-366 36)
DP (n=40)
DP (n-44)
0.4
DP (n=48)
0.2
0.0
0.1
0.2
0.5
Attacker advantage over random (n)
Figure 1: Noise level vs. privacy guarantee for MIP and DP for the construction used to prove Proposition (lower better). For datasets with at. least n = 36 points and for almost all values of y, MIP allows us add much less noise than what would be required by naively applying DP, i.e, by first enforcing e-DP by bounding the algorithm scnsitivity and applying the Laplace mechanism, then using the tight DP/MIP correspondence from Theorem 4 For 48, the amount of noise required by DP is so large that it will not appear on the plot.
for an M-PIP method according to that method's guarantees. For DP, the value along the æ-axis is given by 1
the (tight) correspondence in Theorem namely 17 = I+e- 2-2 rj corresponds to perfect privacy (the attacker cannot do any better than random guessing), while 1, = corresponds to no privacy (the attacker can determine membership with perfect accuracy). The y-axis denotes the amount of noise that must be added to the non-private algorithm's 's output, as measured by the scale parameter of the Laplace noise that must be added (lower better). For MIP, by Theorem 9 this is (6.16/n)²o where is an upper bound on the variance of the base algorithm over random subsets, and for DP this log 1-2T- T-27
(This comes from solving = Ite - for E, then using the fact that Laplace(A/s) noise must be added to guarantee E-DP.) For DP, the amount of noise necessary changes with the size n of the private dataset. For MIP, the amount of noise does not change, so there only one line.
The results show that for even small datasets (n 2 36) and for n 2 0.01, direct noise accounting for MIP guarantceing MIP via DP. In practice, such small datasets uncommon. For in the range typical for ML dataset (10,000+), the noise required for DP is many orders of magnitude larger than that required for MIP, and is not even visible on the plot. (Refer to Proposition 11 required for DP grows exponentially in n, while it remains constant in n for MIP.)
gives large advantage
The noise
5 Conclusion
In this work, we proposed a novel privacy property, membership inference privacy (MIP) and explained its properties and relationship with differential privacy (DP). The MIP property is more readily interpretable than the guarantees offered by (DP). In some cases, MIP also requires smaller amount of noise to guarantee compared to DP, allowing for greater utility the base task. We proposed simple "wrapper" method for guaranteeing MIP, which can be implemented with minor modification both to simple statistical queries or more complicated tasks such as the training procedure for parametric machine learning models. In many "low stakes" scenarios where privacy is nevertheless desired, weaker privacy nolions such as MIP may be appropriate. For instance, in recommender systems or online advertising placement, user data less sensitive than patient data in healtheare setting or client data in finance. The decision of what level of privacy enforce should be made with the help of domain experts on a case- raso-by-case basis, and MIP expands the range of available options.
11

---

Published in Transactions on Machine Learning Research (04/2024)
Limitations As the example used to prove Theorem 5 shows, there are cases where algorithms may have certain (low probabilitt) non-private outputs, but which still satisfy MIP. Thus, algorithms which satisly MIP may require post-processing to ensure that the output is not one of the low-probability events in which data privacy is leaked. In addition, because MIP is determined with respoct to a holdout set still drawn from D, an adversary may be able to determine with high probability whether a given sample was contained D, rather than just in Derain, if 'D is sufficiently different from the rest of the population.
Another limitation of MIP is that it does not necessarily protect against all possible privacy attacks. MIP protects against any privacy attack which would imply a successful membership inference attack. One instance of this is reconstruction attacks (discussed in the Section 2), where the adversary seeks to reconstruct training data "ex nihilo" rather than being supplied with potentially included data. If an at can successfully reconstruct the training data, then a simple membership inference attack to reconstruct the training data first and check whether or not the attacked record is contained the reconstruction. Tf membership inference is impossible by enforcing MIP, then this attack cannot succoed with high probability, so roconstruction cannot, succeed with high probability eir. On the other hand, for some versions of linkage altacks, MIP may not provide protection. For instance, in standard version of linkage attack, the adversary already knows that a specific individual was contained in the training dataset, just not which specific record belongs to that individual. Such an attacker has already passed the "line of defense" enforced by MIP (namely, the membership of an individual in the training data), so MTP will not apply to this scenario.
Future Work Theorem suggests that DP implies MIP in general. However, Theorem 9 shows that a finer-grained analysis of a standard DP mechanism (the Laplace mechanism) possible, showing that we can guarantce MIP with less noisc. It scems plausible that a similar analysis can be undertaken for other DP mechanisms. In addition to these "wrapper" type methods which can be applied on top of existing algorithms, bespoke algorithms for guaranteeing MIP in particular applications (such synthetic data generation) are also of interest. Noise addition is a simple and effective way to enforce privacy, but other classes of mechanisms may also be possible. For instance, it would be interesting to study whether or not it is possible to directly regularize a probabilistic model using Proposition 2
In Theorem g we showed that MIP obeys a post- post-processing incquality, a feature shared by DP. Besides post-processing, DP also has well-studied group privacy and composition properties, and DP guarantees can be amplified by subsampling. An important direction for future work is to establish to what extent similar properties exist for MIP.
Lastly, this paper focused on developing on the theoretical principles and guarantees of MIP. Taking advantage of the relaxed requirements of MIP to develop practical algorithms, and systematic empirical evaluation of these algorithms, is an important direction for future work.
References
Samuel A Assefa, Danial Dervovic, Mahmoud Mahfouz, Robert E Tillman, Prashant Reddy, and Manuela Veloso. Generating synthetic data in finance: opportunities, challenges and pit/falss. In Proceedings of the First ACM International Conference on Al in Finance, pages 1 8, 2020.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
Teodora Baluta, Shiqi Shen, Hitarth, Shruti Tople, and Prateck Saxena. Membership inference attacks and generalization: causal perspective. ACM SIGSAC Conference on Computer and Comsnunicutions Security, 2022.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74 86, 2018.
Mark Bun, Damien Desfontaines, Cynthia Dwork, Moni Naor, Kobbi Nissim, Aaron Roth, Adam Smith, Thomas Steinke, Jonathan Ullaa,, and Salil Vadhan. Statistical inference is
12

---

Published in Transactions on Machine Learning Research (04/2024)
not privacy violation.
DifferentialPrivaey.org 06 2021.
httpe://Ahffferrnniaapprrvvyyyrr
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. arXic preprint 2XN 2021a.
Nicholas Carlini, Florian Tramer, Eric Wallaco, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulaar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633 2650, 2021b.
Dingfan Chen, Ning Yu, Yang Zhang, and Mario Fritz. Gan-lcaks: A taxonomy of membership inference attacks against generative models. In Proceedings of the 2020 ACM SIGSAC conference computer and commanicalions securily, pages 343 362,, 2020.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint 14M5::9905023350 2019.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 1rXi::1609.01880 2016.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3
2014.
Inna Gerlovina and Alan E Hubbard. Computer algebra and algorithms for unbiased moment estimation of arbitrary order. Cogent mathemalics & slatistics, 6(1):1701917, 2019.
Anna C Gilbert and Audra McMillan, Property testing for differential privacy. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 249 258.. TEFE, 2018.
Xinlei He, Zheng Li, Weilin Xu, Cory Cornelius, and Yang Zhang. Membership-doctor: Comprehensive assessment of membership inference against machine learning models. arXiv preprint arXie:2208.10/ 10445, 2022.
Pingyi Hu, Zihan Wang, Ruoxi Sun, Hu Wang, and Minhui Xue. M 4i: Multi-modal models membership inference. Advances in Neural Information Processing Systems, 2022.
Thomas Humphries, Simon Oya, Lindsey Tulloch, Matthew Rafuse, lan Goldberg, Urs Hengartner, and Florian Kerschbaum. Investigating membership inference attacks under data dependencies. In 2023 IEEE 36th Computer Security Foundations Symposium (CSF), pages 473-488. IEFF, 2023.
Matthew Jagielski, Jonathan Ulman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33:22205 22216, 2020.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pages 1895 1912, 2019.
Bargav Jayaraman and David Evans. Are attribute inference attacks just imputation? ACM SIGSAC
Conference on Computer and Communications Security, 2022.
James Jordon, Lukasz Szpruch, Florimond Houssian, Mirko Bottarelli, Giovanni Cherubin, Carsten Maple, Samuel N Cohen, and Adrian Weller. Synthetic data-what why and how? arXiv preprint XrXiv:2205.088 2022.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
Jacwoo Lee and Chris Clifton. Differential identifiability. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1041-1049, 2012.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Ninghui Li, Wahbeh Qardaji, Dong Su, Yi Wu, and Weining Yang. Membership privacy: A unifying framework for privacy definitions. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 889 900, 2013.
Yiyong Liu, Zhengyu Zhao, Michael Backes, and Yang Zhang. Membership inference attacks by exploiting loss trajectory. ACM SIGSAC Conference on Computer and Communications Security, 2022.
Yunhui Long, Vincent Bindschaedler, and Carl A Gunter. Towards measuring membership privacy. arXiv preprint arxi (Tf:::772209136, 2017.
llya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF),
pages 263-275. IEEE, 2017.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Machine learning with membership privacy using adversarial regularization. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 634-646, 2018.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlin. Adversary instanti- alion: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium securily and pricacy (SP), pages 866- 882. IEFE, 2021.
HHS Office for Civil Rights. Standards for privacy of individually identifiable health information. final rule. Federal register, (7(17)):53181 53273, 2002.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113 1201, 2023.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
Theresa Stadler, Bristen Oprisamu, and Carmela Troncoso. Synthetic data - anonymisation groundhog day. 31st USENIX Security Synposium (USENIX Security 22). USENIX Association, 2022.
Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajihala, and Gerome Miklau. Benchmarking differentially private synthetic data generation algorithms. arXiv preprint arXiv:2112.00 09238, 2021.
Anvith Thudi, Ilia Shumailov, Franziska Bocnisch, and Nicolas Papernot. Bounding membership inference. arXiv preprinl arxi:2220 12232, 2022.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375 375-3397 389, 2010.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st computer securily foundalions symposium (CSF), pages 268 282. IEEE, 2018.
A Proofs for Section 3.3
Proposition 2. Let A Range(A) and for simplicity assume that & is discrete. Let P(A(Dtrain) AA) denote the probability of given output A E l over the randomness in Derain and A. Then A is M-MIP if and only if
Σ max (P(x'= E Deruin A(Derain) = PXx & Dirain A(Derain) = A)} P(A(Derrn)) = -A) S 2 AEA
+ m.
Furthermore, the optimal adversary is given by
I(x", A) 1 (P((x E D A((train)) = A) 1/2).
14

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. To avoid measure theoretic complications, we will show the result for the case where the output space A of A is discrete. The results extend in straightforward way to continuous output, with probability masses replaced with densities and sums replaced with integrals.
We will show that the membership inference attack specified in the theorem is optimal, then compute the resulting probability of membership inference. Let C = P(Derain D) = (x) be the constant probability that Drain is equal to any particular training set D D. We have
P(I(x", A(Dirain) = =y) = Σ
P(Derain D) Σ P(A(D) = A) P(I(X A) 11x" E D))
DED
AEA
= =C =c Σ AEA DEDIS
Σ P(A(D) = A) P(I(X", =) +) Σ P(A(D) = - -1- .A) = 1))
DED
= E AEA
Σ P(A(D) = A) Σ P(A(D) = A) =A)
P(I(x",A)=1) 1)+
E P(A(D) = A) (2)
DEDIS
DED
DEDous
The choice of algorithm just specifies the value of PII(xx" AA for each sample x* and each A E A. We see that the maximum membership inference probability is obtained when
P(I(x', (A) 1) =1 =1 Σ
P(A(D) A) E P(A(D)= =))
(3)
DED
DED
Observe that
P(x* E D Derain A(Dtrain) A)
Enerio (D = D)- ((((D) AA
EDED P(Durinn D) PPA(D) A) EDEDON P(Derain D)-1P(((D) A)
EDED P(((D) A) EDEDI P(A(D) A) + EDeDou P(A(D) = A)
(4)
We note that 4 is least 1/2 if and only if ED P(A(D) - A) 2 Degonw P(A(D) A), establishing the equivalence between 3 and the stated optimal adversary.
Next, we use the optimal adversary from 3 to upper bound the accuracy of any adversary. Plugging the optimal adversary into 2 and recalling that C = P((rraiin -D,, we have
P(I(x*, , .((Drrain) vn)
P(Derain = D))(((()) = =A) }
Σ
Σ
P(Ptrain D)PP(A(D) A), Σ DEDout
max
AEA
DED
Σ max [P(x" E Duran A A(Dirain) = P(x" 4 Drraiu A A(Drraia) = AA}
AEA
P(x' Dirain A A(Drrai)) = A) P(x" & D A A(Drrain) = A) P(A(Drrain) A)
Σ
max
P((A(Derai)) = A)
P(A(Drrain) A)
AEA
Σ max P(x" e Dtrain A((train)) = A), P(x" & Derain |A(Drrain) = A) | (P((((rriin)) = A). (5)
AEA
The expression in
is precisely the formulation of MIP given in Proposition 2
This completes the proof.
15

---

Published in Transactions on Machine Learning Research (04/2024)
B Proofs for Section 3.4
In what follows, we will assume without loss of gencrality that n/2. The proofs in the case n/2 are almost identical and can be obtained by simply swapping Mhi ++ .yout and k k.
Lemma 12. Fix x" E D and let Tyi" = {D E D x E D) and D {D E x If 2 n/2 then there is an injective function f Dout + D such that D F(D) for all Dout,
Proof. We define a bipartite graph G on nodes D and Dow. There is an edge between D Min and Dout E Mou if Dout can be obtained from D by removing x" from Dim and replacing it with another element, ie. if Din ~ Dout, To prove the lemma, it suffices to show that there is matching on G which covers Doue, We will show this via Hall's marriage theorem.
First, observe that G is a (ki, n bibbeggll graph. Each Din E I has n - neighbors which are obtained from D by selecting which of the remaining n elements to replace x* with; each Dout E Dout has k neighbors which are obtained by selecting which of the & elements in Dout to replace with x*.
Let W C Nout and let N(W) Dia denote the neighborhood of W. We have the following:
Epante 1{Dout ~ D
IN(W)]=
Σ DW)
E Donee 11 [ Din]
E Dont gw 1 1(Dont Din)
Dost Erout 1 Dout Dim
DI")N(W)
Σ
11Dour ~ Din}
(6)
n1 K
Doul DImEN(W)
k
W/.
(7)
k
Equation O holds since each Din has degree - k and by exchanging the order of summation. Similarly, holds since each Dout has degree k. When & 2 n/2, we thus have [N()] 2 [W] for every W C Ioou and the result follows by Hall's marriage theorem.
7
Thcorem 4. Let A be (c, 0)-D.. Then A is M-MIP with = 8 1-5 1te- Furthermore, this bound is tight, i.e. for any > and < < 1, there erists an (e, O)P algoriliim against which the oplimal allacker has accuracy + 1-8
146-6-
Proof. Note that any identification algorithm I(x*"A(Dxx)) A(Dtrain)) specified by a "rejection region" S for each x*. That is, with x" fixed, there subset S of the range of such that predicts x" & Dirain iff A(D E S.
Let Do Dj with x* e Do and x* & Dr. By Theorem 2.1 of Kairouz et al. 2015 have that
P(A(Do) E +) & 5) 2 -
< +(A(() $5) 2 1-8 88
Summing these inequalities, we have that
P(A(D)) SS +))+P((AD))) $ 2(1 8)
(8)
1
16

---

Published in Transactions on Machine Learning Research (04/2024)
We now use this to lower bound the probability that the adversary is incorrect:
P(adversary is incorrect) =
Σ
P(D - (D))(((D()) E S)
DOE
+
Σ
P(D = D.)IP(((D)) & S)
DDeDo
Σ DoEDin
(S) & S))
(9)
n1/2)
2 2 n/22
n1
n2/2/
71
2(1 -6
+ e
= 1 + c
1
(10)
Here inequality (9 critically uses the fact that f is a bijection. Since Do ~ ,(Do), we can apply inequality to obtain 10 Thus, the adversary's accuracy is at most
1 1-6 1+e 1te
1-8
8
as desirod.
To that the bound is tight, consider the following scenario. We take D (0,1) and define
0
w.p. 5
w.p.
A(1O))
w.p.
1-6 Io-- 1-8
A((1))
w.p. 1-
1-8
w.p.
w.p.
I-
Note that the algorithm is is (e, DP.. Suppose WLOG that x 0. By the formula from Proposition 2
when Dtrain {0), the optimal adversary correctly predicts x" E Derain when A((0)) 0 or *. When Dirain [1}, the optimal adversary correctly predicts x* & Derain when A((1)) = or t. This gives total accuracy
1-8
1 1-5
8
2
1
2
1
1
P
A((0))=0 A(10))=
(1)
A([1))=1
A(U))=
which matches the upper bound in the theorem.
Theorem 5. For any n > 0, there crists an algorithm A which is M-MIP but not (E, for ony < and 8 < 1.
Proof sketch. Let be an even, positive integer, let D == A(Derain) 1 = Dr}. Clearly, A is not (E for any å < 1 (it is a deterministic algorithm with non-constant output). However, the output of A only lets the adversary determine whether Durain = Dr. As n gets large, marginally over Derain, the advantage over random guessing goes to
D' [m] [m] = 21, nJ, and set D = [n/2]. Define
Proposition 6. If an (c, D)- algorithm, then for any x", we have
P(x" &f Derain A(Derain)) c P(x" & Dieain)
P(x* E Derain A( A(Derain)
P(x E Dirain)
Proof. We have
P(x" & D Derain
A A)
EDE P(A(D) A)
( x E Derain A(D A)
EDEDIO P(A(D) = A)
De min (PA('D)) = A)
EDER P(A(D) A)
17

---

Published in Transactions on Machine Learning Research (04/2024)
We now analyze this latter expression. We refer again to the biregular graph G defined in Lemma 12 For D E moue, (() C D refers to the neighbors of D in G, and recall that IN(D) = k for all D e Ioour Note that since each D' E mi has n - k neighbors, we have
Σ E P(A(D) - (n- Σ PPA(D)) A). DIEDm
DEDoet D'EN(D)
Using this equality, we have
EneDow Din D''D P(A(D) = A)
EDeD minD'EN(D) P(A(D) = A)
EDEDIO P(A()) A)
Σ Σ
P(A(D)= A)
K
DEDout D'EN(D)
2 P(A(D))=A)
n1
h:
Since Px(x & Duraiu) = ("²))/(2 and P(x* Dirain) (K=1)/(W), we have completes the proof.
Pix" @Drniul F(x EDraial
m=k. This
Theorem 7. For any 1j 0, there erists an algorithm A and dataset such that A is 1-MIP with respect to D, but A is not (nontrivially) RDP, CDP, tCDP, f-DP.
Proof skelch. The counterexample provided in the proof of Theorem also works for each of these other notions privacy.
C Proofs for Section 3.5
Theorem 8. Suppose that A is n-MIP. Then for ony adversary and any larget record x", we have that
P(I(X", A(Durai)) = x E Durain) S P[I(x" (ATT(x""A(ADAAT A(Diraim)) = 1 xx o D Derain) + 17.
In other words, any adversary must have TPRSFPR+* +
Proof. We will prove the contrapositive statement. Suppose that I is an adversary that achieves TPR FPR + against some algorithm A. By definition, this means that
Σ
P(Drrain = D) P((((("AA(D)) = 1)>
Σ
P(Dtrain D) P(I(x" (.I(((",A(DD) = +1
DE
Deloo
Σ
P(Dtrain D) PII(x", A(D)) 0)) +
Deloo
Σ
P(D D) P(Z(x", A(D))) 0)
2
DeB
Rearranging this inequality yields that
Σ P(Drrain D) DD- P(I(x" ((D)) 1)
Σ
IP(trriin = D) P(I(x" A(D)) 0) > 7,
2
D
DeDon
which is precisely the statement that P(I(x', A(D =y²) > 1/2 7, i.e., that A is not MIP.
7
18

---

Published in Transactions on Machine Learning Research (04/2024)
D Proofs for Section 4
In the proof of Theorem
make use of generalized Chebyshev inequality.
Lemma 13 (Chebysher's Inequality). (eequalterssInnequuttt)))) Let ||-Il be any norm and a random vector with MIX--EXX] < o Then for any > O, we have
P( - EX| > 1o) 1110"
Proof. This follows almost directly from Markov's inequality:
P(I - [X > to) P(IXX EXI > o²* E| - EX
O S 11/t".
Theorem 9. Let ||- be any norm, and let aM 2 E110 EOjiar be upper bound on the M-th central moment of 0 with respect to this norm over the randomness in Drrain and A. Let X be random variable with density proportional to exp(- (X))) with = ( a. Pinally, let = 0 + X. Then is M-MIP, i.e., for any adversary I,
P(I(x* 0) v²) 1/2
Before proceeding to the full proof, we provide sketch.
Proof sketch. The proof proceeds by bounding the posterior likelihood ratio F(x @Drain 10) from above and E(x 10)
below for all i in a large || ||-ball. This in turn yields an upper bound on the max in the integrand in Proposition 2 with high probability over A(Derain) The central moment allows to apply generalized
Chebyshev incquality (Lemma 13 to establish these bounds.
]
We now proceed to the full technical proof.
Proof. We will assume that h n/2 is an integer. Let N DD'| [Dout), and let D = (Di,.... Dw) and Nout (D,..., }. Define a; = A(D)) for D, E Din and b, A(D)) for D' E Dout, Let Z be random variable which is uniformly distributed on {b,}. We may assume without loss of generality that EZ = 0. In what follows, e, a, 3, and 7 are constants which we will choose later to optimize our bounds. We also make repeated use of the inequalities 1 x I ex for all o; + 2 1- 1-- x for all x 2 0; and e" S 11+ 2x and (1 (1=x)(1 - y) 2 1 likelihood ratio is given by
y for 0 < N, < 1. Let X have density proportional to exp( 1 [III)) The posterior
f(0) def P(Duriin E Din 0) Σn exp( 1 110 a.
P(Drrain E Mout
0) Σj=1 exp( 3 110 byll)
We claim that for all Ô with ||ه|| s yoeloge, 1- s f()) < (1 - -)- First, suppose that ||0]| S doo Then have:
Σ Elaillse expl (1|@ + ||a. ID]
5(0) >
N
(1 pana
2 NN e -00
- 4c min(Ma.1-a)
(1I)
19

---

Published in Transactions on Machine Learning Research (04/2024)
Otherwise, ||0| 2 o. We now have the following chain of inequalities:
Σ11b, I|by ISsuud 6- (100 1b,11) Emaillsse e de +1011+
f(0) 2
10000 - + Σ |0.11210111
+ |1
E|Kas|Se c I
Elbb,1ssns eco 11, + Σ [xllbbb eir 11byll + Σ 11:11211011 6 [21101 ||bb,|
N(1 ctaa )
N goa-1
2 +
e |101|
+
20
e 110)
claa
10
C )e m-
2 e2 logg
cur e² loge
2 1 2c -M ca-1 20a11 46 4aa
(12)
2 1 9c aaall))
Combining this with
11 shows that ((0) 2 1 - - min(I for all ||²|| S voclog c.
Next, we must measure the probability of ||Â]| I cacloge. We can lower bound this probability by first conditioning on the value of Drrain:
PP[|0||| S 7ocloge)
P[[0) S rocloge Dirain D)
D
DEE
Σ
P[| & roclog c [|A(D))))
DD
|A(D)lIseo
1
yoclog
1- exp
cM
C
|
1
(1
(1-90
e
cMl
2
2 21- M
Note that the exact same logic (reversing the roles of the at's and by's) shows that f(0) s (1
9c- Ma-2)-- with probability least c M -e- as well.
Finally, we can invoke the result of Proposition Let 9c min(1-a. and note that
1 A- f(0) (11-A)" A)-
max P(xx* E Dirain 0), P(x" $ Dirain 18) 2 2
+ A
20

---

Published in Transactions on Machine Learning Research (04/2024)
Thus we have
max P(xx E Dtrain 10),P(x* Dirain 10)} dP(())
+
P(f(0) E1- ( -
2
2
1
9
min I (a, + 2c M + -c
+
2
2
1
+
+
c -min(l-a. + 2
(13)
2
1
$ 2 +
7.5c M12
where the last inequality follows by setting 7 = a- 1 Ma 7 and solving, yielding 7 M/(M + 2). Solving for nj 7.5c æFzz, find that (T, (T,5) suffices. This completes the proof.
Corollary Let M 2 2, of E0 R0 and define ||o||a, = (Ei 12.1 1/M da,"
for any Y/I|Y|lo.M and draw r
vector x = (II,.... Ia) Generate Y, ~ GenNormallO, 02. M), Laplace ((G.166n))+2///0 Finally set X = =r and return 0 = + X. Then is n-MIP.
Proof skelch. Let || 11 1l, It can be shown that the density X has the proper form. Furthermore, The corollary follows directly from Theorem 9 The
by definition of the ot, we have 0-10-E0]1 improvement in the numerical constant (from 7.5 to 6.16) comes from numerically optimizing some of the bounds in Theorem g and these optimizations are valid for M 2 2.
Corollary 14. When M 2 2, laking c (6.16/1) guaranlees 11MIP.
Proof. The constant improves as M increases, it suffices consider M 2. Let M and 7 1/2, and refer to the proof of Theorem Equation 112 be improved to
2c Ma
ca-1 (e 1)ea=1 4 (4+ e 2c 2c- 10--1/2c--11 1/2
using the inequality e" 11+ (e-
(1+1111)a 1)x for 0 < x < instead of cx < 11 which was used to prove Theorem g
With A = (4 + + 2c 2-12212)) 1/2)c 1/2
13
becomes
1
+
4 + e + 2c 1/2 1/2
+e 1c-2c=32 c c11/2
(14)
2
2
Observe that since 7/ S 1/2, when we set c == (6.16/m) we always have c 2 (2.6,1)), in which case
4 4 + 2c 2c 1/2
e 2c 3/2 3/2 6.1597.
2
Thus, with c = (6.16/n)2, we have
1
14
+ 6.1597
< m.
6.16 2
This completes the proof.
Corollary 10. Let M 2 2, o.M 2 E00; M, and define || = (Σ
Izzl
M
1/M
for any
da!
vector x (I1,...,za) Generate Y, ~ GenNormal(O. o, M), U = Y/J and draw
Laplace ((6.16/1)442/M). Finally, set. X rU and relurn 0 = 0 X. Then Ô is M-MI.
21

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. We with to apply the result of Theorem 9 with ||||| = || lla..M To do this, must bound the resulting M and show that the density of X has the correct form. First, observe that
d
0. E0,
d 2a= =1
M B110 BOIaa
do M
It remains to show that the density has the correct form, i.c. depends on X only through || This will be the case if the marginal density of U is uniform. Let p(U) be the density of U. Observe that, for any ||u]| = ||ulls,M = 1, we have that Y + a iff Y = su for some > 0. Thus
(sun/o)) + +.. (ama/aas)
p(u)=
e
ds
-h d||ull
ds
==0 Md
e
ds.
s=0
The last inequality holds because ||u|| = is constant. Thus, the density is independent of and we directly apply Theorem
Proposition 11. For any finite D S R, define A(D)
1 Engn= x"
Given dataset D of size define
D = (D [D = [n/2]}, and define
o² = Var(A(D)),
A max D~D'EE
IA(D) - A(D').
Here the variance is taken over D ~ Unif(D). Then for all n, there exists dataset D with [D] such that o² = 0(1) but A 0(2n/3).
3 Proof. Assume n is even for simplicity. Let = (n/2) (n/22) and A = vp- - 2:. Take
D (2' i= 0 ,....,,.. 2) (A).
We claim that this datasct satisfics the conditions the proposition.
First, we bound 0², Let D {20 ..... - 2, Note that A(D*)= = p-1 1/2 and this oceurs with probability p. For all other subsets D' * D*, 0 S- A(D') 1. From this, it can seen that S [[A(D)] 2. The lower bound is trivial since A(D) for all D. For the upper bound, we have that
B[A(D)) = p A(D*)+
Σ A-D')
D'4D"
1/1/2+ + (
1/22 -1 p
1/2 +
< 2,
where the equality in the second to last step holds by definition p. We can now use this to bound o². Since A(D') for all D' + D*, we have (A(D") - E[[(()))) < for all D' + D follows that
8² = (A(D") E[A(D)))2 + Σ p. p. (A((D) - E[A(D)))
D'
Sp. 1p-11222211 -02 + ((1)) - -1) p
-1+4-4p
< 5.
22

---

Published in Transactions on Machine Learning Research (04/2024)
Thus o² (1) desired. It remains to lower bound A. Let D' = 120 12.,,...2 and note that D ~ D Observe that
IA(D*) A(D)) 2 1/2 -1
1/2
2 2"
-1
(15)
2n/3
for large enough, where we have used Stirling's approximation for factorials in equation (15) and means that asymptotically the ratio of the two expressions approaches This completes the proof.
23


Reviews:
[{"review_id": "08hDdPdJJu", "reviewer": "Reviewer_h3cw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1) The authors relate the proposed MIP to DP, which is currently the best-understood formal privacy definition.\n\n2) Showing that several MIA bounds are achievable without DP under the weaker MIP notion is interesting.\n\n3) The proposed MIP might allow for improved privacy-utility trade-off compared to DP, at least in some cases.\n\n\n### Weaknesses\n\n1) I do not buy the argument that MIP guarantees are much easier to interpret that DP: DP can be equivalently stated as a guarantee against MIA in iid setting (following Yeom et al. 2018), which allows for a roughly correct interpretation without using $(\\epsilon,\\delta)$. \nAlso, as DP, MIP is not fully characterised by a single number (e.g. it assumes some underlying larger dataset, and a sampling scheme that produces the actual training data from this underlying population), so stating the guarantee in a readily readable manner requires sweeping this complexity out of sight. I find the reasoning of MIP as relaxed form of DP much more appealing irrespective of how easily one can describe the guarantees to an outsider.\n\n2) Related to the previous point, while the paper explicitly connects MIP to DP, this discussion should be continued and expanded: several results have obvious connections to MI bounds derived under DP, but this is not usually even mentioned. This seems like a wasted opportunity, as deriving the same bound under MIP shows that DP is not strictly required for that bound (see Required changes for details). Also, whether or not MIP has analogues of some major DP properties, namely, composition and group privacy, is not mentioned at all.\n\n3) All the experiments use only synthetic data, there are no results e.g. using known becnhmark datasets or models.\n\n4) The paper seems generally a bit rushed and unfinished: several proofs seem to end while leaving several steps as an exercise for the reader, the notation could be better, and the experiments need some fixing (see Required changes for details).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes membership inference privacy (MIP), a formal definition of (training data) privacy based on membership inference attacks (MIA). The authors show that MIP is related to differential privacy (DP), but weaker in the sense that DP implies MIP, but the reverse is not true. The authors provide some theoretical and empirical evidence that MIP can improve the privacy-utility trade-off compared to DP while guaranteeing protection against MIAs. In summary, while I find the proposed definition interesting, I also find that the paper requires some fixes and more work before it provides sufficient evidence for the claims presented.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the following questions/suggested changes:\n\n1) Fix the privacy leakage issue in the experiment in Sec 5.2: you cannot choose the clipping threshold for DP based on private information like the actual gradient magnitudes without implementing some additional privacy mechanism to control that leakage. Using the actual median was an error in the original Abadi et al. paper, that has been fixed in the later versions e.g. on arXiv.\n\n2) Please clarify: does estimating $\\sigma$ from data weaken the resulting MIP guarantee: how does the estimation budget $B$ in Alg 1 affect MIP? Do inaccuracies in estimating $\\sigma$ affect the MIP guarantees?\n\n3) Prop2: the proof should be written out more clearly, for example: jumping from Eq4 to the claim seem to skip plenty of work, I am not sure I understand what you mean by writing $\\mathcal P (\\mathcal A (D))$ vs ) $\\mathcal P (\\mathcal A_{\\mathcal A} (D))$ vs $\\mathcal P (\\mathcal A_{\\mathcal A, D} (D))$), the result is for continuous values while the proof uses discrete sums.\n\n4) Thm 4: The stated bound for the attackers accuracy is exactly the bound shown previously by Humpries et al. 2023 (please also add Humpries et al. to the Related work; see Thudi et al. 2022 for a discussion on the existing bounds). Also, Thm 4 proof should also explicitly argue that the bound is tight as claimed in the Thm statement. This seems unclear without further argument as the proof relies on several inequalities (we know this is tight under DP up to tightness of the DP guarantees as shown by Thudi et al.2022).\n\n5) Thm 8: should also mention that corresponding result is known for DP already from Yeom et al. 2018.\n\n6) Mention adjancency explicitly in defining DP and MIP, or mention if MIP is agnostic w.r.t. adjacency same as DP. At least proof of Lemma 12 in the Appendix and all the experiments use replace adjacency.\n\n7) Discuss or at least mention if MIP provides group MIP and composition: these are fundamental properties of DP, and it would be important to know if these hold for MIP.\n\n\n8) Add $M=2$ line in Fig 2a; feel free to use separate zoom plots or simply limit the y-axis to keep the other resultsd readable, but dropping MIP lines in case they are bad seems like cherry picking the results somewhat.\n\n9) Please clarify: p3 in defining DP: \"While similar to the setting of membership inference at face value, there are subtle differences. In particular, in the case of membership inference, one must consider all datasets which could have contained the target record, and all datasets which do not contain the target record, and distinguish between the algorithm’s output in this larger space of possibilities. This is in contrast to the characterization of DP above, which only needs to distinguish between two datasets.\" I do not understand the claim: DP def requires the bound to hold for all possible adjacent data sets. How is this different from MI?\n\n\n### Typos and other minor changes\n\ni) Fix Appendix A, proof of Prop2 lines leading to and including Eq (3): should imply an upper bound for the original prob., not for diff in sums? Eq (4) x should be xˆ*? \n\nii) Prop 6 proof beginning: missing A from the divisor. Next line dividend should be mathcal A(D'), not mathcal A(D), and the same in the rest of the proof (also in the divisor for consistency)?\n\niii) Thm 8 should have \\leq instead of strict ineq\n\niv) Mention what are $x_i$ in Cor 10\n\n\n#### References (beyond those in the paper):\n\nHumpries et al. 2023: Investigating Membership Inference Attacks under Data Dependencies.", "broader_impact_concerns": "I have no broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cAYiUwBtqz", "reviewer": "Reviewer_zNTL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- MIP provides a different kind of privacy interpretability than DP that demonstrates the probabilistic strength of the adversary to identify membership of a target (unlike DP) which might be easier to interpret in the context of MIAs.\n- The noise required (as shown in Algorithm 1 and Figure 1) for MIP is considerably lower and can be non-isotropic and thus tailored to each dimension.\n- The paper demonstrates a simple relationship between MIP and differential privacy with appropriate proofs and counter-examples.\n- Experiments (in Figure 2) show the advantage of MIP over DP for the privacy-utility trade-off.\n\n\n### Weaknesses:\n\n- Figure 1 is quite confusing. It is unclear what algorithm naive DP refers to. Furthermore, it is unclear why the noise level increases with the number of samples (and not the data dimensions). Normally higher samples should provide better utility-privacy tradeoff. Could the exact naive DP algorithm be added to the paper? Also what composition theorems have been used to compute the privacy of DP in Figure 1? Without comparisons between MIP and composed DP (say with advanced composition) it is hard to know the exact/true benefit extracted from MIP.\n- In Figure 2, is MIP compared to the same naive DP algorithm and does such an algorithm have noise scaled with ’n’? It might be more appropriate to compare MIP against DP, DP with advanced composition, and maybe even DP with subsampling-based privacy amplification.\n- The data-dependent approach of MIP is an advantage as it then requires lower noise levels. However, such non-private computations can leak private data. Furthermore, can the privacy leakage due to such a data-dependent noise mechanism be quantified or simply compared to regular DP (even for simple toy datasets)?\n- Although MIP guarantees privacy in the adversary algorithm setting, do the same benefits extend to other attacks such as linkage attacks (like regular DP)? More generally, can MIP be particularly vulnerable to other privacy attacks due to its data-dependent approach or due to adding lower amounts of noise?\n- MIP might be incompatible with local privacy setups or federated setups.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents Membership Inference Privacy (MIP) as an alternative privacy definition (to Differential Privacy) that focuses on designing a weaker, but more practical and interpretable privacy technique in the context of Membership Inference Attacks. By designing a privacy mechanism around MIAs the authors claim that significantly lower and non-isotropic noise can used to obtain strong privacy guarantees. Here, the privacy strength is measured as the probability advantage of the adversary in determining the membership of a given target sample given access to only the private algorithm’s output and the target sample.\n\nThe paper further discusses the theoretical guarantees of MIP, its practical implications, and the connection between Differential Privacy (DP) and MIP.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My primary concerns and questions have been presented in the weakness section. Below, I have included additional considerations/questions for the authors,\n\n- Can a simple comparison over the privacy-utility trade-off be made with MIP and vanilla DP (say with advanced composition and/or with subsampling) for a DP-SGD pipeline (by appropriately replacing DP with MIP) for a real dataset like MNIST? Furthermore, can simple MIAs be carried out on such a pipeline?\n- Finally, is there a way to get sub-sampling-based privacy amplification with MIP?", "broader_impact_concerns": "The authors do include a limitations section and I have inquired about a few more weaknesses above. Otherwise, the paper does not seem to have other broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h3au84xio7", "reviewer": "Reviewer_VuDy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper describes a notion of privacy that makes it easier to understand and audit privacy measures especially empirically.\n- The work is interesting and mostly sound.\n- The experiments show that MIP improves on DP in terms of percentage of error.\n\nWeakness:\n- The MIP notion of privacy has better accuracy, but this is not surprising since the privacy guarantee is weaker and the randomness added is lower. It seems like there is a need for better comparison with DP with respect to privacy breach as well to have a fairer comparison.\n- It is not very clear to me how useful this privacy notion is and where it would make sense to allow for a $much$ more lenient privacy for the sake of better accuracy when releasing a model or when releasing data.\n- The sentence in section 2, \"In particular, in the case of membership inference, one must consider $all$ datasets...\" - this seems to imply that MIP is stronger than DP, while this is not the case.\n- In theorem 3, it seems like the result is found by defining $I_A(x^*,A(D_{train}))=I_f(x^*,f(A(D_{train})))$, but why is this statement true?\n- In many theorems and theorem proofs, it seems that some relations or expansions are used which are not specified to help in understanding the work. For example, the remark after Theorem 4, that when $\\epsilon\\approx 0$, we have $\\delta+(1-\\delta)/(1+e^{-\\epsilon})-1/2\\approx\\delta/2+(1-\\delta)(\\epsilon/4)$ -- getting to $(1-\\delta)\\epsilon/4$ is unclear. Same with the next statement when $\\delta\\approx 0$.\n- In Theorem 8, \"must have $TPR< FPR+\\eta$\", should this be $\\leq$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper defines a new privacy notion, which is the membership inference privacy (MIP). MIP is a notion of privacy where an adversary is not able to infer membership of a data point in the used dataset with better confidence than random guessing. \nMIP is then compared to differential privacy (DP) and a relationship between the two is established and quantified. The required randomness for an algorithm to be MIP is then studied and it is shown that in some cases this randomness is less than what is required for DP.\nThe paper then proposes a method to make an algorithm with continuous outputs satisfy MIP.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The issues stated in the weaknesses section need to be clarified, and those are critical to recommend acceptance of the paper. \n- At this point I am not very convinced with the usefulness of this privacy notion. Moreover, the statements, theorems and proofs need to be clarified. Stronger examples showing the significance of this notion would be very important in motivating this problem better.\n- More experiments would benefit this paper greatly, especially in terms of privacy leaks as compared to DP. One experiment that could be useful is assessing privacy leakage with a DP algorithm and a MIP algorithm for the same accuracy (or for the same $\\epsilon$ ($\\eta$)). This would help to see how it compares with DP and how much sacrifice in terms of privacy one needs to make.\n- Many statements are not very clear in the text, so proofreading is necessary to help in the understanding of the readers.", "broader_impact_concerns": "No concerns of ethical implications detected.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In general the paper is in a good shape. However, I would like the authors to clarify and fix the following points.
- The proof for Proposition 11 needs further clarification. From the current presentation it is difficult to see if the claims on $\sigma^2$ and $\Delta$ hold. Please make the proof connect explicitly to the claim.
- I guess the data set you consider for Fig. 1 is the same that was used in the proof of Prop. 11? If not, please clarify which data set was used, and what was the sensitivity.
- In the discussion after Thm 4, you could mention that it holds for $(\epsilon, \delta)$-DP algorithms $\mathcal{A}$
- Just before Corollary 10, I guess the $x - \mu$ should be in absolute value?
Decision: Accept (poster)