# provable_membership_inference_privacy__92b582c7.pdf

Published in Transactions on Machine Learning Research (04/2024)

Provable Membership Inference Privacy

Zachary Izzo zach@nec-labs.com NEC Labs America

Jinsung Yoon jinsungyoon@google.com Google Cloud AI

Sercan Ö. Arık soarik@google.com Google Cloud AI

James Zou jamesz@stanford.edu Department of Biomedical Data Science Stanford University

Reviewed on Open Review: https: // openreview. net/ forum? id= 3ludyx Pbb6

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.

1 Introduction

As the popularity and efficacy of 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 to regulatory or ethical concerns (Assefa et al., 2020; Office for Civil Rights, 2002). In 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 a 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 random output cannot change much depending on the presence or absence of an individual point in the database. These guarantees 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 prior knowledge or computational power, making DP an attractive method for guaranteeing privacy. However, DP s strong theoretical guarantees often come at the cost of a large drop in

Part of this project was done while the author was an intern at Google Cloud AI.

Published in Transactions on Machine Learning Research (04/2024)

Privacy Guarantees Noise Required Relevant Quantities DP Stronger Sometimes higher Probability laws/hypothesis testing MIP (Ours) Weaker Sometimes lower Subsampling and attacker performance

Table 1: A summary of the differences between differential privacy (DP) and membership inference privacy (MIP, our notion). DP comes with strong privacy guarantees, but these strong guarantees require large amounts of noise to be added to the algorithm. MIP is a 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 are difficult to interpret by non-experts. There is a precise definition for what it means for an 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), as a first step towards addressing these challenges. Membership inference measures privacy via a game played between the algorithm designer and an adversary or attacker. The adversary is presented with the algorithm s output and a target sample, which may or may not have been included in the algorithm s input set. The adversary s goal is to determine whether the target sample was included in the algorithm 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 a single bit; thus, provably protecting against membership inference provides a strong privacy guarantee. Furthermore, MIP may be easier for non-experts to interpret, as it is measured with respect to a simple quantity namely, the maximum success rate of an attacker on the membership inference task, which requires only a simple sampling scheme to 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 MIP, it 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 is given in Table 1.

We introduce a wrapper method for turning any base algorithm 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 a membership inference attack (Shokri et al., 2017), an attacker 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 in 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 is leaking information about its training data. Obscuring whether a given individual belongs to the private dataset is the core promise of private data sharing, and the

Published in Transactions on Machine Learning Research (04/2024)

main reason that we focus on membership inference as 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., 2021a), 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 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 measure 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 tries 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 a privacy violation (Bun et al., 2021; Jayaraman and Evans, 2022).

Differential Privacy (DP) DP (Dwork et al., 2014) and its variants (Mironov, 2017; Dwork and Rothblum, 2016) offer strong, information-theoretic 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 equivalently if D and D differ by replacing exactly one element. We say that the algorithm A is (ε, δ)-DP if P(A(D) S) eεP(A(D ) S) + δ

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 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 ε) 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 algorithm, and checking it empirically is generally computationally intractable (Gilbert and Mc Millan, 2018). The difficulty of checking DP has led to widespread implementation issues (and even errors due to finite machine precision), which invalidate the guarantees of DP (Jagielski et al., 2020).

While the basic definition of DP can be difficult to interpret, equivalent operational definitions have been developed (Wasserman and Zhou, 2010; Kairouz et al., 2015; Nasr et al., 2021). These works show that DP can equivalently be expressed in terms of the maximum success rate on an adversary which seeks to distinguish between two adjacent datasets D and D , given only the output of a 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 output in this larger space of possibilities. This is in contrast to the characterization of DP above, which only needs to distinguish between a single pair of datasets at any given time. Humphries et al. (2023) 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 a DP algorithm in a simplified membership inference setting where the whole training dataset except for the target record is known, effectively reducing the problem to the hypothesis testing 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 a fundamentally different use case. (Refer to Section 3.3 for more details.) The independent

Published in Transactions on Machine Learning Research (04/2024)

work of Thudi et al. (2022) 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 required 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 guarantees. Li et al. (2013) propose a 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 on 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 distinct 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.e., something akin to the ε parameter for DP or the η parameter for MIP, which we will introduce shortly). Long et 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 heuristic does not come with provable guarantees.

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 x D or x D to refer to a particular sample. Dtrain D refers to a size-k subset of D. We will assume the subset is selected randomly, so Dtrain is a random variable. The remaining data D \ Dtrain will be referred to as the holdout data. We denote by D the set of all size-k subsets of D (i.e., all possible training sets), and we will use D D to refer to a particular realization of the random variable Dtrain. Given a particular sample x D, Din (resp. Dout) will refer to sets D D for which x D (resp. x D). Lastly, we will use 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: if the population we are modeling is significantly different from the larger population, then if our algorithm s output contains any useful information whatsoever, it should be possible for an attacker to infer whether a 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 patient s blood pressure from several biomarkers, specifically for patients who suffer 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 linear regression model with coefficients ˆθ. Formally, we let x Rd denote the features (e.g. biomarker values), z R denote the patient s blood pressure, and y = 1{patient has the chronic disease in question}. In this case, the private dataset Dtrain contains only the patients with y = 1. Assume that in the general

Published in Transactions on Machine Learning Research (04/2024)

populace, patient features are drawn from a mixture model:

y Bernoulli(p), x N(0, I), z|x, y θ y x, θ0 = θ1.

In the membership inference attack scenario, an adversary observes a data point (x , z ) and the model ˆθ, and tries to determine whether (x , z ) Dtrain. If θ0 and θ1 are well-separated, then an adversary can train an effective classifier to determine the corresponding label 1{(x , z ) Dtrain} for (x , z ) by checking whether z ˆθ x . Since only data with y = 1 belong to Dtrain, this provides a signal to the adversary as to whether x could have belonged to Dtrain 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 = {xi}n i=1 be the private dataset and suppose that xi i.i.d. P for some probability distribution P. (Note: Here, x corresponds to the complete datapoint (x , z ) in the example above.) Let A be our (randomized) algorithm, and denote its output by θ = A(D). We generate a test point by first drawing y Bernoulli (1/2), then

x |y y Unif(Dtrain) + (1 y )P,

i.e. x is a fresh draw from P or a 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 output θ = A(Dtrain). 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(I(x , θ) = y ) 1/2 + η, (1)

where the probability is taken over the randomness in A and Dtrain, and ideally η 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 k n, let Dtrain D be a size-k subset chosen uniformly at random from the elements in D. For x D, let y = 1{x Dtrain}. An algorithm A is η-MIP with respect to D if for any identification algorithm I and for every x D, we have

P(I(x , A(Dtrain)) = y ) max k

Here, the probability is taken over the uniformly random size-k subset Dtrain D, as well as any randomness in A and I.

Definition 1 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 η better than always guessing the a priori more likely outcome. In the remainder of the paper, we will set k = n/2, so that A is η-MIP if an attacker cannot have average accuracy greater than (1/2 + η). This gives the largest a priori entropy for the attacker s classification task, which creates the highest ceiling on how much of an advantage an attacker can possibly gain from the algorithm 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.

We also remark that MIP guarantees specify that the adversary cannot distinguish between points in Dtrain and D \ Dtrain; however, this does not rule out the possibility that the adversary may be able to determine whether or not a point was in the base dataset D or not. Indeed, the leakage about membership information

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 private, only membership in Dtrain. This is a concrete consequence of the observation made in Section 3.2 that membership inference privacy must be measured 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 to consider all possible attack algorithms makes it difficult to work with technically. The following proposition shows that MIP is equivalent to a simpler definition which does not need to simultaneously consider all identification algorithms I. We state the theorem in terms of an algorithm with discrete output for simplicity, but the result readily generalizes to continuous output by replacing probability masses with densities.

Proposition 2. Let A = Range(A) and for simplicity assume that A is discrete. Let P(A(Dtrain) = A) denote the probability of a given output A A over the randomness in Dtrain and A. Then A is η-MIP if and only if

max P(x Dtrain | A(Dtrain) = A), P(x Dtrain | A(Dtrain) = A) P(A(Dtrain) = A) 1

Furthermore, the optimal adversary is given by

I(x , A) = 1{P(x Dtrain | A(Dtrain) = A) 1/2}.

Proposition 2 makes precise the intuition that the optimal attacker should guess the more likely of x Dtrain or x Dtrain conditional on the output of A. The optimal attacker s overall accuracy is then computed by marginalizing this conditional statement.

Finally, MIP also satisfies a post-processing inequality similar to the classical result in DP (Dwork et al., 2014). This states that any local functions of a MIP algorithm s output cannot degrade the privacy guarantee.

Theorem 3. Suppose that A is η-MIP, and let f be any (potentially randomized, with randomness independent of Dtrain) function. Then f A is also η-MIP.

Proof. Let If be any membership inference algorithm for f A. A membership inference attack against A can be any binary function of the attacked point x and the algorithm output A. In particular, If(x , f(A)) is such a function, so it is permissible to define IA(x , A) = If(x , f(A)). Since A is η-MIP, we have

1 2 + η P(IA(x , A(Dtrain)) = y ) = P(If(x , f(A(Dtrain))) = y ).

Thus, f A is η-MIP by Definition 1.

For example, Theorem 3 is important for the application of MIP to generative model training if we can guarantee that our generative model is η-MIP, then any output produced by it is η-MIP as well.

3.4 Relation to Differential Privacy

In this section, we make precise the relationship between MIP and the most common theoretical 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 as MIP.

Published in Transactions on Machine Learning Research (04/2024)

Theorem 4. Let A be (ε, δ)-DP. Then A is η-MIP with η = δ + 1 δ 1+e ε 1

2. Furthermore, this bound is tight, i.e. for any ε > 0 and 0 δ < 1, there exists an (ε, δ)-DP algorithm against which the optimal attacker has accuracy δ + 1 δ 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 D0 D1 be adjacent datasets, and let Y = A(D) where D {D0, D1}. We define the null and alternative hypotheses

H0 : D = D0, H1 : D = D1.

Hypothesis testing in this context reduces to defining a rejection set S: whenever A(D) S, we reject the null hypothesis, otherwise if A(D) S, we fail to reject. Kairouz et al. (2015) showed that A is (ε, δ)-DP if and only if for all adjacent datasets D0 and D1, and for any rejection set S, we have

P(A(D0) S) + eεP(A(D1) S) 1 δ,

eε P(A(D0) S) | {z } Type I error

+ P(A(D1) S) | {z } Type II error

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 as we have defined it is a more complicated setting than this hypothesis testing framework. Rather than simply being presented with two possible subsets D0 or D1 and asked to distinguish between only these possibilities, we must distinguish between two large collections of datasets: the n n/2 subsets which contain x , and the n n/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 Din and sets in Dout. For a complete proof, see Appendix B.

To help interpret this result, we remark that for ε 0, a Taylor expansion of 1/(1 + e ε) about ε = 0 shows that δ + (1 δ)/(1 + e ε) 1/2 δ/2 + (1 δ)ε/4.

Thus in the regime where strong privacy guarantees are required (η 0), we will need δ 0. Substituting δ 0 into the equation above then yields η ε/4.

In fact, DP is strictly stronger than MIP, which we make precise with the following theorem.

Theorem 5. For any η > 0, there exists an algorithm A which is η-MIP but not (ε, δ)-DP for any ε < and δ < 1.

In order to better understand the difference between DP and MIP, let us again examine Proposition 2. Recall that this proposition showed that marginally over the output of A, the conditional probability that x Dtrain given the algorithm output should not differ too much from the unconditional probability that x Dtrain. The following proposition shows that (pure) DP requires this condition to hold for every output of A(Dtrain).

Proposition 6. If A is an (ε, 0)-DP algorithm, then for any x , we have

P(x Dtrain | A(Dtrain)) P(x Dtrain | A(Dtrain)) eε P(x Dtrain)

P(x Dtrain).

Proposition 6 can be thought of as an extension of the Bayesian interpretation of DP explained by Jordon et al. (2022). Namely, the definition of DP immediately implies that, for any two adjacent sets D and D ,

P(Dtrain = D | A(Dtrain)) P(Dtrain = D | A(Dtrain)) eε P(Dtrain = D)

P(Dtrain = D ).

We remark that the proof of Proposition 6 indicates that converting between the case of distinguishing between two adjacent datasets (as in the inequality above, and as done in (Wasserman and Zhou, 2010;

Published in Transactions on Machine Learning Research (04/2024)

Kairouz et al., 2015; Nasr et al., 2021)) vs. 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 .

Aside from (approximate) differential privacy, there are other privacy notions such as f-DP or Gaussian DP (GDP) (Dong et al., 2019), Renyi DP (RDP) (Mironov, 2017), concentrated DP (CDP) (Dwork and Rothblum, 2016), and truncated CDP (t CDP) (Bun et al., 2018). The following theorem shows that MIP is distinct from each of these notions as well.

Theorem 7. For any η > 0, there exists an algorithm A and a dataset D such that A is η-MIP with respect to D, but A is not (nontrivially) RDP, CDP, t CDP, 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:

1. 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 either notion.

2. 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 a successful membership inference attack. Thus, MIP guarantees are a relaxed form of privacy as compared to DP.

(a) Theorem 4 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 5 and 7 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 et al. (2021a), in some cases it 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 an adversary cannot identify most individuals but can confidently infer that a small number of individuals belong to the private dataset, which would still constitute a 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 is the content of Theorem 8.

Theorem 8. Suppose that A is η-MIP. Then for any adversary I and any target record x , we have that

P(I(x , A(Dtrain)) = 1 | x Dtrain) P(I(x , A(Dtrain)) = 1 | x Dtrain) + η.

In other words, any adversary must have TPR FPR + η.

Theorem 8 shows that MIP guarantees translate into an additive bound on the TPR. Thus, while MIP is defined in terms of average membership inference accuracy, it still provides a meaningful measurement and bound of privacy leakage 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 terms of the attacker s accuracy was shown by Yeom et al. (2018). However, while the form of our bounds is the same, note that Theorem 8 does not follow from Yeom et al. (2018) because 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.)

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 θ Rd. For instance, A may compute a simple statistical query on D, such as mean estimation, but our results apply equally well in the case that e.g. A(D) are the weights of a neural network trained on D. If θ are the weights of a generative model, then if we can guarantee MIP for θ, then by the data processing inequality (Theorem 3), this guarantees privacy for any output 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 θ. The question is, what is the smallest amount of noise we can add to θ which will guarantee MIP? If we add noise on the order of max D D D A(D) A(D ) , then we can adapt the standard proof for guaranteeing DP in 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 a 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 θ should be sufficient for a marginal guarantee. Theorem 9 shows that this intuition is correct. Theorem 9. Let be any norm, and let σM E θ Eθ M be an upper bound on the M-th central moment of θ with respect to this norm over the randomness in Dtrain and A. Let X be a random variable with density proportional to exp( 1

cσ X ) with c = (7.5/η)1+ 2

M . Finally, let ˆθ = θ + X. Then ˆθ is η-MIP, i.e., for any adversary I, P(I(x , ˆθ) = y ) 1/2 + η.

At first glance, Theorem 9 may appear to be adding noise of equal magnitude to all of the coordinates of θ, regardless of how much each contributes to the central moment σ. However, by carefully selecting the norm , we can add non-isotropic noise to θ such that the marginal noise level reflects the variability of each specific coordinate of θ. This is the content of Corollary 10. (Gen Normal(µ, α, β) refers to the probability distribution with density proportional to exp( (|x µ|/α)β).)

Corollary 10. Let M 2, σM i E|θi Eθi|M, and define x σ,M = Pd i=1 |xi|M

vector x = (x1, . . . , xd) . Generate Yi Gen Normal(0, σi, M), U = Y/ Y σ,M and draw r Laplace (6.16/η)1+2/M . Finally, set X = r U and return ˆθ = θ + X. Then ˆθ is η-MIP.

It may be the case that the σi are not known or an analytic upper bound cannot be easily derived. In such cases, an approximate or asymptotic form of MIP can be employed by estimating the σi from data. We implement this intuition and devise an approximate method for applying MIP in Algorithm 1. The algorithm has two important caveats. First, we remark briefly that the estimator for σj used in Algorithm 1 is not unbiased, but it is consistent (i.e., the bias approaches 0 as B ). 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. Second, the conditions of Theorem 9 and Corollary 10 require that σ or σi 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 as B (or if B = n n/2 and all possible subsets Dtrain are tested, so that σ is computed deterministically and exactly), for finite B, it cannot be guaranteed that the estimated σ is an upper bound on the central moment, therefore the results of Theorem 9 or Corollary 10 cannot be guaranteed to hold. If strict theoretical enforcement of MIP is required, σ must be guaranteed to be an upper bound on the central moment, via analytical arguments (as is done in Proposition 11, for instance) or other means. While this is not ideal, we believe it is still an improvement over the sensitivity bound needed for many DP algorithms (e.g., the Laplace mechanism), since σ may be consistently estimated from data, but there is no consistent estimator of the sensitivity. The σ estimation heuristic can be viewed as similar to the folklore statement in the DP literature that ϵ 1 is needed for theory, but ϵ 10 is fine in practice (Ponomareva et al., 2023). It is also conceivable that the effects of a finite σ estimation budget B can be taken into account in the resulting MIP parameter η, but we leave this for future work.

Published in Transactions on Machine Learning Research (04/2024)

Algorithm 1 MIP via noise addition Require: Private dataset D, σ estimation budget B, MIP parameter η

Dtrain Random Split(D, 1/2)

# Estimate σ if an a priori bound is not known for i = 1, . . . , B do

D(i) train Random Split(Dtrain, 1/2) θ(i) A(D(i) train) end for for j = 1, . . . , d do

B PB i=1 θ(i) j

σj 1 B PB i=1(θ(i) j θj)M 1/M

# Add appropriate noise to the base algorithm s output U Unif({u Rd : u σ,M = 1})

r Laplace 6.16

return A(Dtrain) + X

When Does MIP Require Less Noise Than DP? By Theorem 4, 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) is much smaller than its sensitivity , which is defined as the maximum change in the algorithm s output when evaluated on two datasets which differ in only one element. For instance, applying the Laplace mechanism from DP requires a noise which scales like /ϵ to guarantee ε-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.

Proposition 11. For any finite D R, define A(D) = 1 P

x D x. Given a dataset D of size n, define

D = {D D : |D| = n/2 }, and define

σ2 = Var(A(D)), = max D D D |A(D) A(D )|.

Here the variance is taken over D Unif(D). Then for all n, there exists a dataset D with |D| = n such that σ2 = O(1) but = Ω(2n/3).

In Appendix D, we show that the dataset

D = {2i : i = 0, . . . , n 2}

satisfies the conditions of Proposition 11. To illustrate this result, we plot the noise level needed to guarantee MIP vs. the corresponding level of DP (with the correspondence given by Theorem 4) for this construction in Fig. 1

Refer to Fig. 1. Dotted lines refer to DP, while the solid line is for MIP with M = 2. The x-axis gives the best possible bound on the attacker s improvement in accuracy over random guessing i.e., the parameter η

Published in Transactions on Machine Learning Research (04/2024)

Figure 1: Noise level vs. privacy guarantee for MIP and DP for the construction used to prove Proposition 11 (lower is better). For datasets with at least n = 36 points and for almost all values of η, MIP allows us to add much less noise than what would be required by naively applying DP, i.e., by first enforcing ε-DP by bounding the algorithm sensitivity and applying the Laplace mechanism, then using the tight DP/MIP correspondence from Theorem 4. For n > 48, the amount of noise required by DP is so large that it will not appear on the plot.

for an η-MIP method according to that method s guarantees. For DP, the value along the x-axis is given by the (tight) correspondence in Theorem 4, namely η = 1 1+e ε 1

2. η = 0 corresponds to perfect privacy (the attacker cannot do any better than random guessing), while η = 1

2 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 output, as measured by the scale parameter of the Laplace noise that must be added (lower is better). For MIP, by Theorem 9, this is (6.16/η)2σ where σ is an upper bound on the variance of the base algorithm over random subsets, and for DP this is log 1+2η

1 2η . (This comes from solving

η = 1 1+e ε 1

2 for ε, then using the fact that Laplace( /ε) noise must be added to guarantee ε-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 is only one line.

The results show that for even small datasets (n 36) and for η 0.01, direct noise accounting for MIP gives a large advantage over guaranteeing MIP via DP. In practice, such small datasets are uncommon. For n in the range typical for a 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. The noise required for DP grows exponentially in n, while it remains constant in n for MIP.)

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 a smaller amount of noise to guarantee as compared to DP, allowing for greater utility on the base task. We proposed a simple wrapper method for guaranteeing MIP, which can be implemented with a 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 notions such as MIP may be appropriate. For instance, in recommender systems or online advertising placement, user data is less sensitive than patient data in a healthcare setting or client data in finance. The decision of what level of privacy to enforce should be made with the help of domain experts on a case-by-case basis, and MIP expands the range of available options.

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 probability) non-private outputs, but which still satisfy MIP. Thus, algorithms which satisfy 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 respect to a holdout set still drawn from D, an adversary may be able to determine with high probability whether a given sample was contained in D, rather than just in Dtrain, 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 attacker can successfully reconstruct the training data, then a simple membership inference attack is to reconstruct the training data first and check whether or not the attacked record is contained in the reconstruction. If membership inference is impossible by enforcing MIP, then this attack cannot succeed with high probability, so reconstruction cannot succeed with high probability either. On the other hand, for some versions of linkage attacks, MIP may not provide protection. For instance, in a standard version of a 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 MIP will not apply to this scenario.

Future Work Theorem 4 suggests that DP implies MIP in general. However, Theorem 9 shows that a finer-grained analysis of a standard DP mechanism (the Laplace mechanism) is possible, showing that we can guarantee MIP with less noise. It seems 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 as 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 3, we showed that MIP obeys a post-processing inequality, 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.

Samuel A Assefa, Danial Dervovic, Mahmoud Mahfouz, Robert E Tillman, Prashant Reddy, and Manuela Veloso. Generating synthetic data in finance: opportunities, challenges and pitfalls. In Proceedings of the First ACM International Conference on AI 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, S Hitarth, Shruti Tople, and Prateek Saxena. Membership inference attacks and generalization: A causal perspective. ACM SIGSAC Conference on Computer and Communications 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 Ullman, and Salil Vadhan. Statistical inference is

Published in Transactions on Machine Learning Research (04/2024)

not a privacy violation. Differential Privacy.org, 06 2021. https://differentialprivacy.org/ inference-is-not-a-privacy-violation/.

Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. ar Xiv preprint ar Xiv:2112.03570, 2021a.

Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar 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-leaks: A taxonomy of membership inference attacks against generative models. In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 343 362, 2020.

Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. ar Xiv preprint ar Xiv:1905.02383, 2019.

Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. ar Xiv preprint ar Xiv:1603.01887, 2016.

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends R in Theoretical Computer Science, 9(3 4):211 407, 2014.

Inna Gerlovina and Alan E Hubbard. Computer algebra and algorithms for unbiased moment estimation of arbitrary order. Cogent mathematics & statistics, 6(1):1701917, 2019.

Anna C Gilbert and Audra Mc Millan. Property testing for differential privacy. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 249 258. IEEE, 2018.

Xinlei He, Zheng Li, Weilin Xu, Cory Cornelius, and Yang Zhang. Membership-doctor: Comprehensive assessment of membership inference against machine learning models. ar Xiv preprint ar Xiv:2208.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, Ian 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. IEEE, 2023.

Matthew Jagielski, Jonathan Ullman, 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 Houssiau, Mirko Bottarelli, Giovanni Cherubin, Carsten Maple, Samuel N Cohen, and Adrian Weller. Synthetic data what, why and how? ar Xiv preprint ar Xiv:2205.03257, 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.

Jaewoo 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.

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. ar Xiv preprint ar Xiv:1712.09136, 2017.

Ilya 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 instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on security and privacy (SP), pages 866 882. IEEE, 2021.

HHS Office for Civil Rights. Standards for privacy of individually identifiable health information. final rule. Federal register, 67(157):53181 53273, 2002.

Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan Mc Mahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 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 Oprisanu, and Carmela Troncoso. Synthetic data anonymisation groundhog day. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, 2022.

Yuchao Tao, Ryan Mc Kenna, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Benchmarking differentially private synthetic data generation algorithms. ar Xiv preprint ar Xiv:2112.09238, 2021.

Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot. Bounding membership inference. ar Xiv preprint ar Xiv:2202.12232, 2022.

Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375 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 security foundations symposium (CSF), pages 268 282. IEEE, 2018.

A Proofs for Section 3.3

Proposition 2. Let A = Range(A) and for simplicity assume that A is discrete. Let P(A(Dtrain) = A) denote the probability of a given output A A over the randomness in Dtrain and A. Then A is η-MIP if and only if

max P(x Dtrain | A(Dtrain) = A), P(x Dtrain | A(Dtrain) = A) P(A(Dtrain) = A) 1

Furthermore, the optimal adversary is given by

I(x , A) = 1{P(x Dtrain | A(Dtrain) = A) 1/2}.

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 a 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(Dtrain = D) = n k 1 be the constant probability that Dtrain is equal to any particular training set D D. We have

P(I(x , A(Dtrain)) = y ) = X

D D P(Dtrain = D) X

A A P(A(D) = A) P(I(x , A) = 1{x D})

D Din P(A(D) = A) P(I(x , A) = 1) + X

D Dout P(A(D) = A) (1 P(I(x , A) = 1))

D Din P(A(D) = A) X

D Dout P(A(D) = A)

P(I(x , A) = 1) + X

D Dout P(A(D) = A)

The choice of algorithm I just specifies the value of P(I(x , A) = 1) for each sample x and each A A. We see that the maximum membership inference probability is obtained when

P(I(x , A) = 1) = 1

D Din P(A(D) = A) X

D Dout P(A(D) = A) 0

Observe that

P(x Dtrain | A(Dtrain) = A)

D Din P(Dtrain = D) P(A(D) = A) P D Din P(Dtrain = D) P(A(D) = A) + P D Dout P(Dtrain = D) P(A(D) = A)

D Din P(A(D) = A) P

D Din P(A(D) = A) + P

D Dout P(A(D) = A). (4)

We note that (4) is at least 1/2 if and only if P

D Din P(A(D) = A) P

D Dout 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(Dtrain = D), we have

P(I(x , A(Dtrain) = y )

D Din P(Dtrain = D)P(A(D) = A), X

D Dout P(Dtrain = D)P(A(D) = A)

A A max {P(x Dtrain A(Dtrain) = A), P(x Dtrain A(Dtrain) = A)}

A A max P(x Dtrain A(Dtrain) = A)

P(A(Dtrain) = A) , P(x Dtrain A(Dtrain) = A)

P(A(Dtrain) = A)

P(A(Dtrain) = A)

A A max P(x Dtrain | A(Dtrain) = A), P(x Dtrain | A(Dtrain) = A) P(A(Dtrain) = A). (5)

The expression in (5) is precisely the formulation of MIP given in Proposition 2. This completes the proof.

Published in Transactions on Machine Learning Research (04/2024)

B Proofs for Section 3.4

In what follows, we will assume without loss of generality that k n/2. The proofs in the case k < n/2 are almost identical and can be obtained by simply swapping Din Dout and k n k.

Lemma 12. Fix x D and let Din = {D D | x D} and Dout = {D D | x D}. If k n/2 then there is an injective function f : Dout Din such that D f(D) for all D Dout.

Proof. We define a bipartite graph G on nodes Din and Dout. There is an edge between Din Din and Dout Dout if Dout can be obtained from Din by removing x from Din and replacing it with another element, i.e. if Din Dout. To prove the lemma, it suffices to show that there is a matching on G which covers Dout. We will show this via Hall s marriage theorem.

First, observe that G is a (k, n k)-biregular graph. Each Din Din has n k neighbors which are obtained from Din by selecting which of the remaining n k elements to replace x with; each Dout Dout has k neighbors which are obtained by selecting which of the k elements in Dout to replace with x .

Let W Dout and let N(W) Din denote the neighborhood of W. We have the following:

Dout W 1{Dout Din} P

Dout W 1{Dout Din}

Dout W 1{Dout Din} P

Dout Dout 1{Dout Din}

Din N(W ) 1{Dout Din} (6)

= k n k |W|. (7)

Equation (6) holds since each Din has degree n k and by exchanging the order of summation. Similarly, (7) holds since each Dout has degree k. When k n/2, we thus have |N(W)| |W| for every W Dout and the result follows by Hall s marriage theorem.

Theorem 4. Let A be (ε, δ)-DP. Then A is η-MIP with η = δ + 1 δ 1+e ε 1

2. Furthermore, this bound is tight, i.e. for any ε > 0 and 0 δ < 1, there exists an (ε, δ)-DP algorithm against which the optimal attacker has accuracy δ + 1 δ 1+e ε .

Proof. Note that any identification algorithm I(x , A(Dtrain)) is specified by a rejection region S for each x . That is, with x fixed, there is a subset S of the range of A such that I predicts x Dtrain iff A(Dtrain) S.

Let D0 D1 with x D0 and x D1. By Theorem 2.1 of Kairouz et al. (2015), we have that

P(A(D0) S) + eεP(A(D1) S) 1 δ,

eεP(A(D0) S) + P(A(D1) S) 1 δ.

Summing these inequalities, we have that

P(A(D0) S) + P(A(D1) S) 2(1 δ)

1 + eε . (8)

Published in Transactions on Machine Learning Research (04/2024)

We can now use this to lower bound the probability that the adversary is incorrect:

P(adversary is incorrect) = X

D0 Din P(Dtrain = D0)P(A(D0) S)

D1 Dout P(Dtrain = D1)P(A(D1) S)

1 (P(A(D0) S) + P(A(f(D0)) S)) (9)

1 + eε = 1 δ

1 + eε . (10)

Here inequality (9) critically uses the fact that f is a bijection. Since D0 f(D0), we can apply inequality (8) to obtain (10). Thus, the adversary s accuracy is at most

1 + eε = δ + 1 δ 1 + e ε

as desired.

To see that the bound is tight, consider the following scenario. We take D = {0, 1} and define

0 w.p. δ w.p. 1 δ 1+e ε w.p. 1 δ 1+eε

1 w.p. δ w.p. 1 δ 1+eε w.p. 1 δ 1+e ε

Note that the algorithm A is (ε, δ)-DP. Suppose WLOG that x = 0. By the formula from Proposition 2, when Dtrain = {0}, the optimal adversary correctly predicts x Dtrain when A({0}) = 0 or . When Dtrain = {1}, the optimal adversary correctly predicts x Dtrain when A({1}) = 1 or . This gives total accuracy

1 2 |{z} Dtrain={0}

δ |{z} A({0})=0

+ 1 δ 1 + e ε | {z } A({0})=

+ 1 2 |{z} Dtrain={1}

δ |{z} A({1})=1

+ 1 δ 1 + e ε | {z } A({1})=

= δ + 1 δ 1 + e e ,

which matches the upper bound in the theorem.

Theorem 5. For any η > 0, there exists an algorithm A which is η-MIP but not (ε, δ)-DP for any ε < and δ < 1.

Proof sketch. Let n be an even, positive integer, let D = [n] = {1, 2, . . . , n}, and set D = [n/2]. Define A(Dtrain) = 1{Dtrain = D }. Clearly, A is not (ε, δ)-DP for any δ < 1 (it is a deterministic algorithm with non-constant output). However, the output of A only lets the adversary determine whether Dtrain = D . As n gets large, marginally over Dtrain, the advantage over random guessing goes to 0.

Proposition 6. If A is an (ε, 0)-DP algorithm, then for any x , we have

P(x Dtrain | A(Dtrain)) P(x Dtrain | A(Dtrain)) eε P(x Dtrain)

P(x Dtrain).

Proof. We have

P(x Dtrain | A(Dtrain) = A) P(x Dtrain | A(Dtrain) = A) = P

D Dout P(A(D) = A) P D Din P(A(D) = A)

D Dout min D Din,D D P(A(D ) = A) P

D Din P(A(D) = A) .

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 Dout, N(D) Din refers to the neighbors of D in G, and recall that |N(D)| = k for all D Dout. Note that since each D Din has n k neighbors, we have

D N(D) P(A(D ) = A) = (n k) X

D Din P(A(D ) = A).

Using this equality, we have

D Dout min D Din,D D P(A(D ) = A) P

D Din P(A(D) = A) = P

D Dout min D N(D) P(A(D ) = A) 1 n k

D N(D) P(A(D ) = A)

| {z } k min D N(D) P(A(D )=A)

Since P(x Dtrain) = n 1 k / n k and P(x Dtrain) = n 1 k 1 / n k , we have P(x Dtrain) P(x Dtrain) = n k

k . This completes the proof.

Theorem 7. For any η > 0, there exists an algorithm A and a dataset D such that A is η-MIP with respect to D, but A is not (nontrivially) RDP, CDP, t CDP, or f-DP.

Proof sketch. The counterexample provided in the proof of Theorem 5 also works for each of these other notions of privacy.

C Proofs for Section 3.5

Theorem 8. Suppose that A is η-MIP. Then for any adversary I and any target record x , we have that

P(I(x , A(Dtrain)) = 1 | x Dtrain) P(I(x , A(Dtrain)) = 1 | x Dtrain) + η.

In other words, any adversary must have TPR FPR + η.

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

D Din P(Dtrain = D) P(I(x , A(D)) = 1) > X

D Dout P(Dtrain = D) P(I(x , A(D)) = 1) + η

D Dout P(Dtrain = D) (1 P(I(x , A(D)) = 0)) + η

D Dout P(Dtrain = D) P(I(x , A(D)) = 0) + η.

Rearranging this inequality yields that

D Din P(Dtrain = D) P(I(x , A(D)) = 1) + X

D Dout P(Dtrain = D) P(I(x , A(D)) = 0) > 1

which is precisely the statement that P(I(x , A(Dtrain)) = y ) > 1/2 + η, i.e., that A is not η-MIP.

Published in Transactions on Machine Learning Research (04/2024)

D Proofs for Section 4

In the proof of Theorem 9, we make use of a generalized Chebyshev inequality.

Lemma 13 (Chebyshev s Inequality). Let be any norm and X be a random vector with E X EX 2 σk. Then for any t > 0, we have P( X EX > tσ) 1/tk.

Proof. This follows almost directly from Markov s inequality:

P( X EX > tσ) = P( X EX k > tkσk) E X EX k

Theorem 9. Let be any norm, and let σM E θ Eθ M be an upper bound on the M-th central moment of θ with respect to this norm over the randomness in Dtrain and A. Let X be a random variable with density proportional to exp( 1

cσ X ) with c = (7.5/η)1+ 2

M . Finally, let ˆθ = θ + X. Then ˆθ is η-MIP, i.e., for any adversary I, P(I(x , ˆθ) = y ) 1/2 + η.

Before proceeding to the full proof, we provide a sketch.

Proof sketch. The proof proceeds by bounding the posterior likelihood ratio P(x Dtrain | ˆθ)

P(x Dtrain | ˆθ) from above and

below for all ˆθ 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(Dtrain). The central moment σ allows us to apply a generalized Chebyshev inequality (Lemma 13) to establish these bounds.

We now proceed to the full technical proof.

Proof. We will assume that k = n/2 is an integer. Let N = |Din| = |Dout|, and let Din = {D1, . . . , DN} and Dout = {D 1, . . . , D N}. Define ai = A(Di) for Di Din and bj = A(D j) for D j Dout. Let Z be a random variable which is uniformly distributed on {ai} {bj}. We may assume without loss of generality that EZ = 0. In what follows, c, α, β, and γ are constants which we will choose later to optimize our bounds. We also make repeated use of the inequalities 1 + x ex for all x; 1 1+x 1 x for all x 0; and ex 1 + 2x and (1 x)(1 y) 1 x y for 0 x, y 1. Let X have density proportional to exp( 1

cσ X ). The posterior likelihood ratio is given by

f(ˆθ) def = P(Dtrain Din | ˆθ)

P(Dtrain Dout | ˆθ) = PN i=1 exp( 1

cσ ˆθ ai ) PN j=1 exp( 1

cσ ˆθ bj ) .

We claim that for all ˆθ with ˆθ γσc log c, 1 η

2 f(ˆθ) (1 η

2) 1. First, suppose that ˆθ cασ. Then we have:

ai cασ exp[ 1

cσ( ˆθ + ai )]

(1 2 c Mα )N e 2cα 1

1 4c min(Mα,1 α). (11)

Published in Transactions on Machine Learning Research (04/2024)

Otherwise, ˆθ cασ. We now have the following chain of inequalities:

cσ ( ˆθ + ai ) P

cσ ( ˆθ bj ) + P

cασ< bi < ˆθ e 1

cσ ( ˆθ bj ) + P

cσ ( bi ˆθ )

bj cασ e 1 cσ bj + P

cασ< bi < ˆθ e 1 cσ bj + P

bi ˆθ e 1 cσ (2 ˆθ bi )

N(1 2 c Mα )e cα 1

N ecα 1 + 2 c Mα e 1 cσ ˆθ + 2σM

ˆθ M e 1 cσ ˆθ

(1 2 c Mα)e cα 1

ecα 1 + 2 c Mα eγ log c + 2 c Mα eγ log c

1 2c Mα cα 1 2cα 1 4cγ Mα (12)

1 9c min(1 α,Mα 2γ).

Combining this with (11) shows that f(ˆθ) 1 9c min(1 α,Mα γ) for all ˆθ γσc log c.

Next, we must measure the probability of ˆθ γσc log c. We can lower bound this probability by first conditioning on the value of Dtrain:

P( ˆθ γσc log c) = 1

D D P( ˆθ γσc log c | Dtrain = D)

A(D) cσ P( X γσc log c A(D) )

2 exp γσc log c cσ

Note that the exact same logic (reversing the roles of the ai s and bj s) shows that f(ˆθ) (1 9c min(1 α,Mα 2γ)) 1 with probability at least 1 c M e

2c γ as well.

Finally, we can invoke the result of Proposition 2. Let = 9c min(1 α,Mα γ) and note that

1 f(ˆθ) (1 ) 1 = max n P(x Dtrain | ˆθ), P(x Dtrain | ˆθ) o 1

Published in Transactions on Machine Learning Research (04/2024)

Thus we have Z max n P(x Dtrain | ˆθ), P(x Dtrain | ˆθ) o d P(ˆθ)

P(f(ˆθ) [1 , (1 ) 1]) + P(f(ˆθ) [1 , (1 ) 1])

2c min(1 α,Mα γ) + 2c M + ec γ

2 + e c min(1 α,Mα γ,γ) + 2c M (13)

2 + 7.5c M M+2

where the last inequality follows by setting γ = 1 α = Mα γ and solving, yielding γ = M/(M + 2). Solving for η = 7.5c M M+2 , we find that c = ( 7.5

η )1+2/M suffices. This completes the proof.

Corollary 10. Let M 2, σM i E|θi Eθi|M, and define x σ,M = Pd i=1 |xi|M

vector x = (x1, . . . , xd) . Generate Yi Gen Normal(0, σi, M), U = Y/ Y σ,M and draw r Laplace (6.16/η)1+2/M . Finally, set X = r U and return ˆθ = θ + X. Then ˆθ is η-MIP.

Proof sketch. Let = σ,M. It can be shown that the density of X has the proper form. Furthermore, by definition of the σi, we have E θ Eθ M 1. The corollary follows directly from Theorem 9. The improvement in the numerical constant (from 7.5 to 6.16) comes from numerically optimizing some of the bounds in Theorem 9, and these optimizations are valid for M 2.

Corollary 14. When M 2, taking c = (6.16/η)1+2/M guarantees η-MIP.

Proof. The constant improves as M increases, so it suffices to consider M = 2. Let M = 2 and α = γ = 1/2, and refer to the proof of Theorem 9. Equation (12) can be improved to

1 2c Mα cα 1 (e 1)cα 1 4cγ Mα = 1 (4 + e + 2c 1/2)c 1/2

using the inequality ex 1+(e 1)x for 0 x 1 instead of ex 1+2x, which was used to prove Theorem 9. With = (4 + e + 2c 1/2)c 1/2, (13) becomes

1 2 + 4 + e + 2c 1/2

2 + e + 2c 3/2 c 1/2. (14)

Observe that since η 1/2, when we set c = (6.16/η)2, we always have c (2 6.16)2, in which case

4 + e + 2c 1/2

2 + e + 2c 3/2 6.1597.

Thus, with c = (6.16/η)2, we have

2 + 6.1597 η 6.16 1

This completes the proof.

Corollary 10. Let M 2, σM i E|θi Eθi|M, and define x σ,M = Pd i=1 |xi|M

vector x = (x1, . . . , xd) . Generate Yi Gen Normal(0, σi, M), U = Y/ Y σ,M and draw r Laplace (6.16/η)1+2/M . Finally, set X = r U and return ˆθ = θ + X. Then ˆθ is η-MIP.

Published in Transactions on Machine Learning Research (04/2024)

Proof. We with to apply the result of Theorem 9 with = σ,M. To do this, we must bound the resulting σM and show that the density of X has the correct form. First, observe that

σM = E θ Eθ M =

i=1 E|θi Eθi|M

It remains to show that the density has the correct form, i.e. depends on X only through X . 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 = u s,M = 1, we have that Y 7 u iffY = su for some s > 0. Thus

1 σ2 1 (su1/σ1)M+ +(sud/σd)M ds

s=0 e s Md u 2 ds

s=0 e s Md ds.

The last inequality holds because u = 1 is constant. Thus, the density is independent of u and we can directly apply Theorem 9.

Proposition 11. For any finite D R, define A(D) = 1 P

x D x. Given a dataset D of size n, define

D = {D D : |D| = n/2 }, and define

σ2 = Var(A(D)), = max D D D |A(D) A(D )|.

Here the variance is taken over D Unif(D). Then for all n, there exists a dataset D with |D| = n such that σ2 = O(1) but = Ω(2n/3).

Proof. Assume n is even for simplicity. Let p = n n/2 1 and A = p P n

2 2 i=0 2i. Take

D = {2i : i = 0, . . . , n 2} {A}.

We claim that this dataset satisfies the conditions of the proposition.

First, we bound σ2. Let D = {20, . . . , 2 n 2 2, A}. Note that A(D ) = p 1/2, and this occurs with probability p. For all other subsets D = D , 0 A(D ) 1. From this, it can be seen that 0 E[A(D)] 2. The lower bound is trivial since A(D) 0 for all D. For the upper bound, we have that

E[A(D)] = p A(D ) + X

D =D p A(D )

p1/2 + n n/2

= p1/2 + 1 p

where the equality in the second to last step holds by definition of p. We can now use this to bound σ2. Since 0 A(D ) 1 for all D = D , we have (A(D ) E[A(D)])2 4 for all D = D . It follows that

σ2 = p (A(D ) E[A(D)])2 + X

D =D p (A(D ) E[A(D)])2

p (p 1/2 0)2 + n n/2

Published in Transactions on Machine Learning Research (04/2024)

Thus σ2 = O(1) as desired.

It remains to lower bound . Let D = {20, . . . , 2 n 2 1} and note that D D . Observe that

|A(D ) A(D )| p 1/2 1

2 πn 2n !1/2

for n 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 1. This completes the proof.