Bounding Membership Inference
Authors: Anvith Thudi
I Shumailov
Franziska Boenisch
Nicolas Papernot
Venue: ICLR 2022 Submitted (2022)
Keywords: differential privacy
membership inference

Abstract: Differential Privacy (DP) is the de facto standard for reasoning about the privacy guarantees of a training algorithm. Despite the empirical observation that DP reduces the vulnerability of models to existing membership inference (MI) attacks, a theoretical underpinning as to why this is the case is largely missing in the literature. In practice, this means that models need to be trained with differential privacy guarantees that greatly decrease their accuracy. In this paper, we provide a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides  $\epsilon$-DP. Our bound informs the design of a novel privacy amplification scheme, where an effective training set is sub-sampled from a larger set prior to the beginning of training, to greatly reduce the bound on MI accuracy. As a result, our scheme enables $\epsilon$-DP users to employ looser differential privacy guarantees when training their model to limit the success of any MI adversary; this, in turn, ensures that the model's accuracy is less impacted by the privacy guarantee. Finally, we discuss the implications of our MI bound on machine unlearning.

Under review as a conference paper at ICLR 2022
BOUNDING MEMBERSHIP INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Differential Privacy (DP) is the de facto standard for reasoning about the privacy guarantees of a training algorithm. Despite the empirical observation that DP re- duces the vulnerability of models to existing membership inference (MI) attacks, theoretical underpinning erature. In practice, this means that models need to be trained with differential privacy guarantees that greatly decrease their accuracy. In this paper we provide a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides e-DP. Our bound informs the design of novel privacy amplification scheme, where an effective training set is sub-sampled from a larger set prior to the beginning of training, to greatly reduce the bound on MI accuracy. As result, our scheme enables c-DP users to employ looser differential privacy guarantees when training their model to limit the success of any MI adversary; this in turn ensures that the model's ' accuracy is less impacted by the privacy guarantee. Finally, we discuss implications of our MI bound on machine unlearning.
to why this is the case is largely missing in the lit-
INTRODUCTION
Differential Privacy (DP) (Dwork 2006) is employed extensively reason about privacy guarantees in a variety of different settings (Dwork) 2008). Recently, DP started being used to give privacy guarantees for the training data of deep neural networks (DNNs) learned through stochastic gradient descent (Abadi et al. 2016). However, even though DP gives privacy guarantees and bounds the worst case privacy leakage, is not immediately clear how these guarantees bound the accuracy of known existing forms of privacy infringement attacks.
At the time of writing, the most practical attack on the privacy of DNNs is Membership Inference (MI) (Shokri et al.) 2017). where an attacker predicts whether not model used particular data point for training (note that this is quite similar to the hypothetical adversary at the core of the game instantiated in the definition of DP); membership inference attacks saw a strong interest by the community, and several improvements and renditions were proposed since its inception (Sablay- rolles al. [2019] Choquette- Choo al.] [021 Maini et al. 2021 Hu et al. [021)) Having privacy guarantees would desirably defend against MI, and in fact current literature highlights that DP does
indeed give an upper bound the performance of MI adversaries (Yeom et al. 2018 Brlingsson
it al. 2019 Sablayrolles et al. 2019 Jayaraman et al. 2020).
In this paper, we first propose a tighter bound on MI accuracy for training algorithms that provide e-DP. Our approach uses a lemma about an equivalence of certain sets of datasets. Furthermore, in obtaining our bound, we also show how this bound can benefit from a form of privacy amplification where the training dataset itself is sub-sampled from larger dataset. Amplification is a technique pervasively found in work improving the analysis of DP learners like DP-SGD (Abadi et al.) 2016), and we observe the effect of our amplification on lowering MI accuracy is significantly stronger than the effect of batch sampling, a common privacy amplification scheme for training DNNs.
Our bound also has consequences for the problem of unlearning (or data forgetting in ML) intro- duced Cao & Yang (0155). In particular the MI accuracy on the point to be unlearned is a popular measure for how well model has unlearned (Baumhauer et al., 2020 Graves et al. 2020 Golatkar et al. 2020b a). However empirical verification of the MI accuracy can be open ended, as it is sub- jective to the attack employed. Theoretical bounds all MI attacks, such as the one proposed in this work, circumvent this issue; bound on the accuracy of MI attacks, in particular the probability data point used in the training dataset, indicates limitation for any entity to discern if the

---

Under review as a conference paper at ICLR 2022
model had trained the data point. In the case when this is sufficiently low (where sufficiently is defined apriori), one can then claim to have unlearned by achieving a model sufficiently likely to have not come from training with the data point. Our analysis shows that, if dataset subsampling is used, one can unlearn under this definition by training with relatively large e (and thus have less cost to performance).
To summarize, our contributions are:
We present tighter general bound on MI accuracy for e-DP;
We further demonstrate how to lower this bound using a novel privacy amplification scheme built on dataset subsampling;
We discuss the benefits of such bounds to Machine Unlearning rigorous way MI as a metric for unlearning.
2 BACKGROUND
2.1 DIFFERENTIAL PRIVACY
Differential privacy (DP) (Dwork 2006) bounds how different the outputs of function on adjacent inputs can be in order to give privacy guarantees for the inputs. More formally function F is e-DP for all adjacent inputs x and (i.e. inputs with hamming distance 1) we have for all sets S in the output space:
P(F(x) E 9) <EP(F(E)) S)
(1)
We also have more relaxed notion of (c, DD where in the same setup above, but with parameter 8 E (0, 1}, we have P (()(2) E S) S eFP(((()) S) + d. Notably, (c, 6DP is used for functions where it is more natural to work with l metrics on the input space, which has to do with how DP guarantees are obtained.
To achieve DP guarantees one usually introduces noise to the output of the function F. The amount of noise calibrated to the maximal &a or É, difference between possible outputs of the function on adjacent datasets (also called sensitivity). Significant progress was achieved minimizing the amount noise needed for a given sensitivity (Balle & Wang 2018), and on how DP guarantees scale when composing multiple DP functions (Dwork al. 2010 Kairouz et al. 2015).
Abadi al. 2016) demonstrated a method to make the final model returned by mini-batch SGD (c with respect to its training dataset by bounding the sensitivity of gradient updates during mini-batch SGD and introducing Gaussian noise to each update. This approach became the da-facto standard for DP guarantees in DNNs. However, the adoption still greatly limited because of observed trade-off between privacy guarantees and model utility. At the time of writing there is still no feasible ways to learn with low e and high accuracy, and past work (Jagielski et al. 2020 have suggested that Dn-anllysis may be too loose and provides more privacy than is expected.
However, more recently Nasr al. (2021) showed (using statistical tests and stronger MI adver- saries) that the current state of the art approaches to achieving (c, 8DP bounds for deep learning are tight, in contrast Jagielski et al. (2020) results suggesting that they were loose. That there not much more improvement to be gained by studying how to improve the (e, 0)-P bound from a given amount of noise or improving composition rules. Facing this, future improvements in DP training would lie in understanding the guarantees that DP bounds provide against the performance of relevant privacy attacks. This would allow us to be more informed about the guarantees required during training defeat practical attacks and enable the use of looser guarantees if one is only interested in defending against a specific set of attacks.
It is worth noting that Nasr et al. 2021) showed that current analytic upper bounds on DP guarantees are tight, measuring them empirically with various strong privacy adversaries. Although results do suggest that hounds match, the paper did not investigate how DP guarantees limit performance of the adversary.
2

---

Under review as a conference paper at ICLR 2022
2.2 MEMBERSHIP INFERENCE
Shokri et al. (017) introduced MI attack against DNNs, which leveraged shadow models (models with the same architecture as the target model) trained on similar data in order to train a classifier which, given the outputs of model a data point, predicts if the model was trained that data point or not. Since the introduction of this initial attack, the community has proposed several improved and variations of the original MI attack ( (Yeom et al. 2018 (allm et al. [201 [Sablayrolles eet al. 2019 Truex et al. 2019 Jayaraman et al. al.] 20200 Maini et al. (0021). such as an attack that
only look at predicted labels of the target model (Choquette- Choo et al.] 2021).
MI attacks are currently the main practical threat to the privacy of a user's data used to train DNNs. Especially in the context of DP DNN learning, it would be beneficial know how DP bounds translate to bounds on the accuracy of MI attacks. This would provide an understanding on what sort of DP guarantees an entity requires to ensure a sufficiently low maximum accuracy of an adversary trying to discern their training data from their deployed model. The bounds would hence help in guiding decisions regarding setting these parameters and their corresponding guarantees.
In our paper we will work with the following (abstract) notion of MI in giving our bounds. In particular we define our MI adversary as function f which takes set of models S and a data point x" to deterministically output either 1 or O, corresponding to whether x was in the dataset D used to obtain the models in or not respectively. Note the generality of this adversary, as we do not consider how the adversary obtains the function, i.e. it can have arbitrary strength. Any such adversary will then satisfy the upper and lower bounds we derive later in the paper.
With that definition of our adversary, have the following definition of positive and negative MI accuracy (which is what we focus on in this paper); note that here D is the training dataset and P(x" E D)S is the probability data point x" was in the training dataset used obtain the models in the set S (i.e. this is a probability over datasets). We explain more about where the randomness introduced (in particular the probability involved in obtaining a training dataset) in Section 3.1
Definition 1 (MI accuracy). The positive accuracy of f(x', SS) the accuracy if f outputs I which E D)S) and the negative accuracy, the accuracy if outputs O which we define as A(f(x", = 0), is P(x" & DJS) = - P(x" E DIS))
define A(f(x, 5)=1), is P(x"
2.3 PREVIOUS BOUNDS
Before giving bounds on MI accuracy, we have to formally define the attack setting. Two of the main bounds (Yeom et al. 2018 Erlingsson et al., 2019) focused on an experimental setup first introduced by Yeom et al. (0018). To summarize the experiment, and in particular the situation the adversary is operating in, an adversary f is given a datapoint x" that is 50% likely to have been used to train model S or not. The adversary then either predicts 1 if they think it was used, or 0 otherwise. Let b = 1 or 0 indicate if the datapoint was or was not used for training respectively. We say the adversary was correct if their prediction matches b. We then define the adversary's ' advantage as improvement in accuracy over the 50% bascline of random guessing, or more specifically 2(A(f)- 0.5) where A(f) the accuracy of f.
For such an adversary operating in scenario where data is equally likely to be included or not in the training dataset, Yeom et al. (2018) showed that they could bound the advantage of the adversary by e - 1 when training with e- DP. In other words, they showed that they could bound the accuracy of the MI adversary by e /2. Their proof used the fact that the true positive rate (TPR) and false positive rate (FPR) of their adversary could be represented as expectations over the different data points a dataset, and from that introduced the DP condition to obtain their MI bound, noting that MI advantage is equivalent to TPR FPR.
Erlingsson et al. (2019) improved on the bound developed by Yeom et al. (2018) for an adversary operating under the same condition by utilizing proposition given by Hall et al. (2013) on the relation between TPR and FPR for an (c, 5)DP function. Using these facts, Erlingsson et al. (2019) bounded the membership advantage by 1 +5e which is equivalent to bounding the accuracy of the adversary by 1 - e e/2 when 5 = (i.e. in e-DP). This is, to the best of our knowledge, the previous state-of-the-are bound for high
3

---

Under review as a conference paper at ICLR 2022
Other work have considered more general setups where the probability of sampling datapoint in the dataset can vary, similar to what we consider in Section 3.I For c-DP, Sablayrolless et al. (2019) bounded the probability of a datapoint x" being used in the trainigg set of model (i.c., the accuracy of an attacker who predicted the datapoint was in the dataset of the model) by Pxx (1) + where
Px (1) is the probability of the datapoint being in the dataset. This is, to the best of our knowledge, the previous state-of-the- bound for low (when reduced to case of Yeom et al. (2018) by setting Fx (1) 0.5 as compare with Erlingsson et al. (2019)).
Finally, Jayaraman et al. 2020) bounded the positive predictive value of an attacker (i.e. its preci- sion) on a model trained with (c, 6)-D when the FPR is fixed. It is worth noting that although the considered setup is similar to works covered above, it assumes an unbalanced sampling procedure. Similarly, Jayaraman et al. further bounded membership advantage under the experiment described by Yeom et al. (2018) for fixed FPR. EEringsson et al. (2019) followed a similar argument for their bound but were also able to remove the need for an explicit knowledge of the FPR.
2.4 UNLEARNING
Having bounds membership inference is partieularly relevant to machine unlearning for DNNs. Machine unlearning was first introduced by Cao & Yang (2013), who described a setting where important for the model to be able forget certain training data points and focused on the cases where there were efficient analytic solutions. It was then extended to DNNs by [Boutoollc al. (209)) with the definition that model has unlearned a data point if after the unlearning, the distribution of models returned is identical to the one that would result from not training with the data point at all. This definition was also stated earlier by Ginart et al.. (2019) for other classes of machine learning models.
Given that unlearning is interested in removing the impact a data point had on the model, further work employed MI accuracy on the data point to be unlearned as a metric for how well the model had forgotten it after using some proposed unlearning method (Baumhauer et al.] 2020 Graves et al.) 2020 Golatkar et al.) 2020b a). Yet, empirical estimates on the membership status of datapoint are subjective to the concrete MI attacks employed - indeed it may be possible that there exists a stronger practical attack.
Analytic bounds to MI attacks, on the other hand, resolve the subjectivity issue of MI as a metric for unlearning they bound the success of any adversary. In particular one could give the following definition of an unlearning guarantee from a formal MI positive accuracy bound:
Definition 2 (B-MI Unlearning Guarantee). An algorithm is B-MI unlearnt for x" if P(x* é DIS) 2 B, i.e. the probability xf not being in the training dataset is greater than B.
Therefore, our result bounding positive MI accuracy has direct consequences on the field of machine unlearning, which we further elaborate in Section
THE BOUND
3.1 THE SCENARIO
We now proceed to formalize the scenario under which our adversary operates. Here, our scenario is more general than the one introduced by Yeom al. (2018) and, as we note later, a specific instance of it can be reduced to their setup. In particular we formalize how an entity samples data into the training dataset, and proceed with our analysis from there.
Our intuition here is that one can imagine the existence of some large data superset containing all the data points an entity could have in their training dataset. Yet, any one of these datapoints only has some probability of being sampled into the training dataset. For example, this larger dataset could consist of all the users that gave an entity access to their data, and the probability comes from the entity randomly sampling the data to use in their training dataset. This randomness can be black-box such that not even the entity knows what data was used to train. In essence, this is the scenario Jayaraman et al. (2020) considers, though in their case, the larger dataset is implicit and takes the form of a distribution. We can then imagine that the adversary (or perhaps an arbitrator in an unlearning setup) knows the larger dataset and tries infer whether particular data point was
4

---

Under review as a conference paper at ICLR 2022
used in the training dataset. The particular MI attack that analyze and bound is based on this scenario.
Specifically, let the individual training datasets D be constructed by sampling from finite count- able set where all datapoints are unique and sampled independently, i.e. from some larger set {xI,... XN) ). That is if D (x1, X2, '.. ,,,,,,,,,, then the probability of sampling D is P(D) Px, (1)P xx (1) ... (1)P (0) .......... .x (0), where Px, (1) is probability of drawing x; into the dataset and (0) is the probability of not.
We define D as the set of all datasets. Let now Dx- be the set of all datasets that contain a particular point x" E {x1,-.. XNJ. that is Dx- {D s. x* D}. Similarly let xx-' be the set of all datasets that do not contain x', i.e. Xx- = {D' s, x' of D'}. Note D = Dx U xx by the
simple logic that any dataset has or does not have x" in We then have the following lemma (see
Appendix A for the proof).
Lemma 1. Dx and x' are in bijective correspondence with P(D) P. (0) (T)
PPD)) for D DED Dx
and D' E Dx-' that map to each other under the bijective correspondence.
Once some dataset D is obtained. we call H the training function which takes in D and outputs a model M as set of weights in the form of a real vector. Recall that H c-DP if for all adjacent datasets D and D' and any set of model(s) S in the output space of H (i.e. some weights) we have: (DH(D) S) z (DD() E S). It should be noted that from now on we assume that the set S has non-zero probability membership inference attacks on sets of models that have probability to come from training; note also if (D) E 5) O, then (DH(D') S) 0 for all adjacent D' O (P( S) s (D((HD) S) = 0, and thus the probability is O for all countable datasets as we can construct any dataset by removing and adding data point (which does not change the probability if it initially 0) countably many times.
be produced by H. This is sensible we not interested in
3.2
MAIN RESULT
We now proceed to use Lemma D to bound the positive and negative accuracy of MI, as stated in Definition!! I for a training function H that is e-DP under the data-sampling scenario defined carlier. Our approach differs from those we discussed in Section 2.3 in that now focus the definition of the conditional probability Pxx* e DIS) as a quotient; finding a bound then reduces to finding a way simplify the quotient with the c-DP definition, which achieve using Lemma] T
What follows are the technical results, with Section and disscussin the main consequences of the bound.
Theorem (DP bounds MI positive accuracy). If is a MI attack applied to a set of models and it predicts x" was in the datasets used to obtain them, and the training process H is DP with its accuracy is upper-bounded by (1+ --Tx-(0) -1
and lower bounded by (1 e'Pxx(() -1 Fx- (1) the probability of drawing x" into the dataset.
,where
(2)
(2)
See Appendix for the proof.
By the definition of negative accuracy of we have the following corollary:
Corollary (DP bounds MI negative accuracy). If f an MI attack applied to a set of models S and it predicts x" R is not in it, and the training process H is DP with then the accuracy is
upper-bounded by (1+ e "Pp
and lower-bounded by (1
c'Px. -1
where Ppx (1) is
(x)
Px
the probability of drawing x" into the dataset.
See Appendix A for the proof.
Note that in the case Px- (1) = Px- (0) = 0.5, the bounds given by Theorem and Corollary are identical. Therefore, f(x" S) must output either 0 or 1, have more general claim that the attack accuracy (maximum of positive or negative accuracy) is always bounded by the same values given by Theorem
5

---

Under review as a conference paper at ICLR 2022
4 THE EFFECT OF Px- (1)
We now focus on the effect of (1) which we discuss in two subsections below. The first ex- plains how the privacy amplification, i.e. lowering of our MI positive accuracy bound, we observe from decreasing Px- (1) is fundamentally different than the privacy amplification on MI from batch sampling. The second subsection outlines the practical consequences of this for defender.
4.1 NEW PRIVACY AMPLIFICATION FOR MI
Our bound given by Theorem 1 can be reduced by decreasing Px- (1) or Furthermore, have batch sampling, which the probability for data point to be used in the batch for a given training step, reduces MI positive accuracy as it reduces sampling both decrease our bound, and we term their effect "privacy amplification" (for MI) as they decrease privacy infringement (analogous how "privacy amplification" for DP refers methods that reduce privacy loss). We now ask the question, is the effect of dataset sub-sampling and batch sampling different?
So dataset sub-sampling (Px-(1) and batch
Before proceeding, it is useful to get a sense of the impact Px. (1) has on our bound. We plot Fxx(1) against our positive MI accuracy bound given by Theorem in Figure 3 for different (see Appendix B). Notably, for a specific case when Px- (1) is small, we get that the positive accuracy is bounded by 6.9% for e = 2 and 1xx (1) = 0.01 (i.e. 1%).
We now turn to comparing the effect of batch sampling to the effect of (1) (note (x-(0)/xx = (1 (1)) (1)). First it is worth noting that the two amplification methods mostly independent, i.e. decreasing (0)/P)))P /IP (1) mostly places restriction on the sam- pling rate for batch sizes (with some exception) for the time being as we are interested in their independent mathematical behaviours. Including q for DP batch privacy amplification, we can compare its impact to Px. (1) by looking at the term e xx) (0)/Px (1) in the bound given by Theorem [] the goal is to maximize this to make the upper bound as small as possible. In particular, we see that decreasing y increases this term by ( where decreasing xxx (1) increases this term by O((1 t)/t), which is slower than O(e up to a point, then faster (do note that we are looking at the order as the variable & decreases). Figure [ plots this relation, however note that the specific values are subject to change with differing con- stant. Nevertheless what does not change with the constants are the asymptotic behaviours, and in particular we see lim;-0o ((11 - t)/t) oo where as lim;-+0 (
Nevertheless we can ignore this restriction
constant.
Thus we can conclude the effects of data sampling and batch sampling are different to our bound, and hence data sampling presents a new privacy amplification scheme for MI positive accuracy. As a last remark, note these same comparison holds more generally when comparing the effect of c and Px- (1);
Comparisan of Privacy Ampliiication
Amplricatoon Ampilication
Figure I: Comparing the DP amplification observed by decreasing batch probability (given by e-) to the amplification we observe from decreasing Px (1) (given by (1 (1-1)) t)/
We say "mostly" as this is true upto point. In particular we have the expectation of the training dataset size decreases with smaller dataset sampling probabilities, and thus the lowest possible batch sampling rate 1/n, where in the training size, increases in expectation

---

Under review as a conference paper at ICLR 2022
4.2 USEFULNESS FOR DEFENDER
We now explain one course of action a defender can take in light of this new privacy amplification for MI. In partieular note that an upper bound on x (1) translates an upper bound the relation found in Theorem (as the bound is monotonically increasing with x (1)); hence one can, in practice, focus on giving smaller upper-bounds on Fxx (1) to decrease MI positive accuracy.
A possible approach to this is as follows. Say a user (the defender) is given some sample D C (xI.-... X drawn with some unknown distribution. In particular they do not know the individual probabilites for the points being in D. However say that from D they obtain D' by sampling any point from D with probability T. Then the probability for any point x" E (xI, .XN J being in D' is bounded by T as the true probability is the probability x" E D (which is S 1) times T. Hence the user trains with D' they will have P xx (1) S T and thus can use our bound to give guarantees on how low the MI positive accuracy is.
This does come with some drawbacks. In general one wants to train with more data, but by further sampling with probability 7 we reduce our expected training dataset size. Thus user will have to make the decision between how low they can make T (in conjunction with the parameter they choose) compared to how small dataset they are willing to train on. We leave this type of decision making for future work.
5 DISCUSSION
5.1 OUR BOUND IS TIGHTER THAN EARLIER RESULTS
We first compare our main technical result, the bound on MI adversary's success, with the two key baselines we identified earlier (Sablayrolles et al. 2019 Erlingsson et al. (219). The setup described in Section 3.1 is equivalent to the MI experiment defined by Yeom et al. (2018) when (1) = 0.5 Vx;- E x1,- xx}. J. That is. if the training dataset was constructed by sampling data points from a larger dataset by a coin flip, then when the adversary is given any data point from the larger dataset to test there is a 50% chance it was in the training set or not. Furthermore, recall that when xxx (1) = 0.5, then Theorem reduces to bounds on the overall accuracy of any MI attack f (as the bounds on positive and negative accuracy are the same). We can thus compare the upper-bound on MI accuracy that we achieved with the current tightest bounds given by Erlinnssson eet al. (2019) and (Sablayrolles et al. (2019) for e-DP; we stated these bounds carlier in Section 2.3 where for the latter bound we also set x (1 = 0.5.
Our bound, and these two previous bounds, are depicted in Figure 2 where see the bound given in Theorem [ is always tighter than both of the previous bounds. In particular, we see that it is introduced by [Sablayrolles et al.) for small and closer to the one defined by
closer to the Erlingsson et al.] for large e. Notably, for = 1, we bound the accuracy of an MI attack by 73.1% whereas Erlingsson al. bound it by 81.6%, and [Sablayrolles et al. by 75%. For 2, we bound MI accuracy by 88% whereas Erlingsson et al. bound it by 95% and Sablayrolles et al. by 100%.
5.2 ANALYSIS OF ID LOGISTIC REGRESSION
We now motivate future work on MI bounds by illustrating how our approach of bounding the positive accuracy (defined (xx (S) of a MI adversary for c-DP does not immediately extend to (c, DD-D. Such an extension would be desirable so one can capture the success of MI adversaries against training algorithms that only provide relaxed guarantees of DP, as opposed to the D-DP guarantees we studied. In particular, we give a practical counter-example that shows for a specific (c, -DP logistic regression that there is no bound on the positive accuracy of the adversary, unlike what follows from our bound for e-DP. Nevertheless, we demonstrate how one can still tailor bounds on general MI accuracy for this specific attack and remark how this bound much tighter than what our theorem states for any MI adversary in the tighter c-DP conditions.
MI attack
5.2.1 POSITIVE ACCURACY IS NOT BOUNDED
Consider a set of two (scalar) points {21, which are drawn into the training set D with P.,, (1) = 1 and Par. (1) = 0.5; that is æ1 is always in the training set, and 22 has 50% chance of being in
7

---

Under review as a conference paper at ICLR 2022
the training set. Let model M be single dimensional logistic regression without bias defined as (x) = we initialized such that for cross-entropy loss L. VL z 0 (i.e. set I1 = {(10%, 1)} and the weights w 10 that (z) = 10"x and thus the softmax output of the model is approximately 1 on I1 and thus gradient is approximately 0). Conversely set 22 such that the gradient it is less than -1 (i.e., for the above setup set 22 = ((10%, 0))).
Now, train the model to (1, 10-P) following Abadi et al. 2016) with 1 = 1, sampling rate of 100%, maximum gradient norm of for one step. Note these are just parameters which we are allowed to change under the DP analysis, and we found the noise we would need for (1, DDDP 4.0412. Then consider running a MI attack on the above setup where if for some threshold the final weights W are s.t if W < a one classifies those weights as having come from the dataset with I2, otherwise not. Do note that here we use W for the final weights as opposed to w to emphasize that we are now talking about a random variable. The intuition for this attack is that if the dataset only contain 21 then the weights do not change, but the dataset contains 22 we know the resulting gradient is negative (by construction) and thus decreases the weights (before noise).
By the earlier setup on how training datasets are constructed note that = { or D= x2)). and we will denote these D2 and D2 respectively. Note that if M trained on D₃ following the sug- gested data points and initial weights, we have the distribution of final weight WD, = N(10%,0)
[ 4.0412) where denotes the noise needed for (1, 10 --DD as stated earlier. Similarly WD, = N(10 - 1, 4.0412), since the maximum gradient norm is set to 1.
For the above MI attack we can then bound the positive accuracy as function of by: P(( D2 S a) P(D2)
P(D2 W a)
P(W D. S + P(D2) + P(W D.
6 (W D., a) 0.5
Φ W D1. a) 0.5 + Φ0 ( p2 * 0.5
where of (WW, o:) is the (Gaussian) cumulative function of random variable W upto a.
We plot this in Figure 4a| and unlike Theorem 1 note how it is not bounded by anything less than and goes to 1 as the threshold a decreases (i.e. Vm E [0, 1) 3x s.t S = (-o0, ai) yields positive accuracy greater than m))
5.2.2 MI ACCURACY IS BOUNDED
The previous section showed that for (e, 6DP the positive accuracy of our adversary is not bounded. However, as we will show in this section, this does not mean the overall accuracy is not bounded. Specifically, for the same attack and setup as in Section 5.2.1 note that we have a bound on the general accuracy of this specific attack given by: F(D1/W 2 aW* 2 PPD W S aP & (1
0.)5
(4)
We illustrate this in Figure 4b and observe that is bounded by 54.9% for a = 10t 0.5. Do note that 54.9% is significantly less than 73.1% which is what our bound gives for 1-DP, and 1- DP is tighter DP condition than (c = 1,5 = 10-9)-DP which is what is depicted in Figure 4b This illustrates how the bound can be further tightened with better understanding of the (worst case scenario) weight distribution and the nature of the attack. We leave this to future work.
5.3 MI ADVANTAGE
Previous work, particularly Yeom al. (2018) and Erlingsson et al. (2019), focused on membership advantage, which is essentially an improvement in accuracy of f over the random guess of 50% of drawing point in the training dataset. More specifically, if we let A(f) denote the accuracy of f. then membership advantage is computed as (AA()) 0.5). We can generalize this to ask what the membership advantage of the positive accuracy of f compared to the baseline Px- (1) is.
Theorem D gives us upper bound on the positive accuracy and thus an upper bound on the positive advantage of f denoted as Ad(f):
(1-- Px (0) -1
Ad(ʃ) = (A ;S= = -x- 52
- -Px
(5)
Px (1)
8

---

Under review as a conference paper at ICLR 2022
We plotted this advantage function of Px (1) for different fixed in Figure (see Appendix B We observe that the advantage clearly depends on Px- (1), and in fact for different e, the x (1) resulting in the maximum advantage changes. In particular, Px- (1) 0.5 is not close to the advan- tage for large 6, which shows how the fixed experiment proposed by Yeom et al. (2018) does not necessarily give the maximum advantage adversary could have.
However, it should be noted that higher advantage here does not mean a higher upper bound on accuracy; as we already saw in Figure the upper bound on accuracy increases monotonically with Fxx (1), in contrast to the bump observed with membership advantage. This serves to contrast the study of advantage and the study of accuracy for future work.
IMPORTANCE TO DATA DELETION
The ability for an entity to decrease the ability for an arbitrator to attribute a data point to model also has consequences for machine unlearning and data deletion requests as mentioned in Section 2.4
In particular if P(x" E DIS) is sufficiently low, that is the likelihood of S coming from x" is low, then an entity could claim that they do not need to delete the users data since their model is most likely independent of that data point as it most likely came from a model without it: i.e. leading to plausible deniability. Note we defined this type of unlearning Section 2.4 as B-MI unlearn- ing guarantee. This is similar to the logic presented by (Sekhari et al. (2021) where unlearning is presented probablistically in terms of (c, (c.8)-unlaame) unleammin...
We also observe analogous result to Sckhari et al. (2021) where we can only handle maximum number of deletion requests before no longer having sufficiently low probability. To be exact, let us say do not need undergo any unlearning process given set of data deletion request x* if P(x" & DIS)= 2 B for some (i.e. we are working with probability of not having that set of data in our training set which we want to be high). Note that we sampled data independently, thus if x* = (x], X5. ",,,,,
J. then P(x* & DJS) P(x & DIS) ..................... P(x" & DJS).
Now, for simplicity, assume the probability of drawing all points into the datasets the same, so that for all x we have the same bound given by Corollary 1 that is IP(;; & DJS) > T, for some S Then we have P(x" & DIS) 2 L and an entity does not need to unlearn if L B, lm1/B i.e. if m S II/ = In
I This gives a bound on how many deletion requests the entity can avoid in
terms of the lower bound given in Corollary
In particular, note that if {x1 [N3 is the larger set of data points an entity is sampling from, and Px(1) = c/N Vx E -x....X. then the lower bound given by Corollary is (1+ (1+
Sekhari et al. (20T)) showed that with typical DP the deletion requests grow linearly with the size of the training (in the above case represents the expected training set size). We thus compare linear line w.r.t to c to in Lie; (where L is given in the earlier expression for the bound from Corollary I in Figure (see Appendix B to observe their respective magnitude: we fix B = 0.8.N = 10000 and e as we are interested in general trends. We observe that our deletion capacity significantly higher for low expected training set sizes and is marginally lower than linear trend for larger training set sizes.
B
CONCLUSION
In this work, we provide tighter bound on MI accuracy against ML models trained with c-P.. Our bound highlights that intricacies of dataset construction are of great importance for model vulnera- bility to MI attacks. Indeed, based our findings, we develop privacy amplification scheme that just requires one to sub-sample their training dataset from larger pool of possible data points.
Based on our results, entities training their ML models with DP can employ looser privacy guar- antees (and thereby preserve their models' accuracy better) while still limiting the success of MI attacks. Finally, our bound, and more generally bounds positive MI accuracy, can also be applied to handle unlearning requests when doing machine unlcarning if unlearning is defined by achieving model with low probability of having come that data point.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Borja Balle and Yu- Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Ana- lytical calibration and optimal denoising. In International Conference on Machine Learning, pp- 394 403. PMLR, 2018.
Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer. Machine unlearning: Linear filtra- tion for logit-based classifiers. arXiv preprint arXiv:2002.027300 2020.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chor Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. arXiv preprint arXiv:1912.038/77 2019.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. 2015 IEEE Symposium on Security and Privacy, pp. 463-480. IEEE, 2015.
Christopher A Choquette- Choo,, Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label-only membership inference attacks. In International Conference on Machine Learning, pp. 1964-1974. PMLR, 2021.
Cynthia Dwork. Differential privacy. International Colloquium on Automata, Languages, and Programming, pp. 1-12. Springer, 2006.
Cynthia Dwork. Differential privacy: A survey of results. In International conference theory and applications of models of computation, pp. 1-19. Springer, 2008
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp- 51-60. IEEE, 2010.
Ülfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which we call private. arXiv preprint arXiv:1908. 005566, 2019.
Antonio Ginart, Melody Y Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. arXiv preprint 197.50090..00//2 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 9304-9312, 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision, pp. 383-398. Springer, 2020b.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. arXiv preprint arXiv:2010.1 10981, 2020.
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and func- tional data. The Journal of Machine Learning Research, 14(1):703-727, 2013. 2013.
Hongsheng Hu, Zoran Salcie, Gillian Dobbie, and Xuyun Zhang. Membership inference attacks on machine learning: A survey, arXiv preprint arXiv:2 100.00833..... 2021.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? arXiv preprint arXiv:2006.07709 2020."
Bargav Jayaraman, Lingxiao Wang, Katherine Knipmeyer, Quanquan Gu, and David Evans. Revis- iting membership inference under realistic assumptions. arXiv preprint arXiv:2005. 10881, 2020.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning, pp. 1376-1385. PMLR, 2015.
10

---

Under review as a conference paper at ICLR 2022
Pratyush Maini, Mohammad Yaghini, and Nicolas Papernot. Dataset inference: Ownership resolu- tion in machine learning. arXiv preprint arXiv:2104.10700 10706, 2021.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adver- sary instantiation: Lower bounds for differentially private machine learning. arXiv preprint arXiv:2101.04533, 2021.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. In International Confer- ence on Machine Learning, pp. 5558-5561 PMLR, 2019.
Ahmed Salem, Yang Zhang, Mathias Humbert, Pascal Berrang, Mario Fritz, and Michael Backes. MI-lcaks: Model and data independent membership inference attacks and defenses machine learning models. arXiv preprint 1rXiv:1806.01240 2018.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. arXiv preprint arXiv:2103.03279 2021.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference tacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Stacey Truex Ling Liu, Mehmet Emre Gursoy, Lei Yu, and Wenqi Wei. Demystifying membership inference attacks in machine learning as a service. IEEE Transactions on Services Computing, 2019.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learn- ing: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pp. 268-282. IEEE, 2018.
A PROOFS
Lemma 1 Note that for given D = {xi, ... ",,...""" Dx., D/x E Dx. is unique (i.e. the map by removing x* injective) and similarly for given D' Dx. (i.e. the map by adding x" is injective). Thus, we have injective maps running both ways which are the inverses of each other. As a consequence, we have Dx- and xx- are in bijective correspondence.
D' x unique
... xxv] letting D = fx1 ... ..-,-11 } Ux* and D' = {x] ... Xn- be any pair of datasets that map each other by the above bijective map, then note P(D) = Px, (1 IP (1) .....,...... P, (1)Txx (1)... .P).......... xx (0) ......P ....PPx x, (0) and P(D')
Now if the larger set of datapoints is (x) - 1,'',,'' x", Xn,
Fx, (1)Ps, ... Px___ P(D').
P1) ( (0) ... Px.., (0) Pxx (0). In particular we have PPD) Fx
(2)
Theorem The positive accuracy is:
= EDED,, P(H(D) S)P(D) EDED P(H(D) E S)P(D)
(6)
By the observation 2 = Dx. Dx'' we have that the denominator can be split into EDER,- PDH(D) S)P(D) EDees P(H(D') S)).
By Lemma I we can replace the D' E D'. in the second sum by D E 2x- and replace
F(D') by P(D)
(I) For PHH(D') E S) note by H being eDDP we have PHH(D' E S) > e PDH(( E S) and so with the previous replacements we have that the denominator greater
(0)
than (1 PP.. EDER,- P(H(D) E S)P(D).
(1)
Thus, the accuracy of i
(i.e. the upper bound).
14 1
11

---

Under review as a conference paper at ICLR 2022
Different MI Bounds
1.9
0.8
0.7
0.0
Eriipsson Bound
Sabtayrolles Bound
0.5
Epslion
Figure 2: Comparing the upper bound to MI performance achieved to that given by Erlingsson et al. (2019) and Sablayrolles et al. 2019) (note xpx (1) = 0.5 here). In particular note we are tighter for all 6.
If instead we used the fact that (D') E E) c(H(H E S), we would find that the accuracy of f is
1+ 20 (i.e. the lower bound).
(1)
Corollary 1 Immediately follows from Theorem and Defintion as if A(f(x" 5) = 1) -
1 10) then A(f(x", S) 0) =1 A(f(x", .) 1) 1
Fo- (0)
Similarly, we get A(J(x" 5) 0) = A(S(x* ; 11
P--
B FIGURES
Positive Accuracy Bound Probability
1.0
0.8
0.6
0.4
Bound Bound Ace Bounst
Probability of drowing x*
Figure 3: Our upper bound on MI positive accuracy function of Px- (1)
C
TABLES
Paper
Analytic Form e2/2 1 1-e-t/2 Px- +1)
Type General General
Yeom al. 2018
Erlingsson et al. 2019
Sablayrolles et al. 20199
Positive Accuracy
(1+ - -1
Our Work
Positive Accuracy
(1-(1)
Table Bounds found in prior work.
12

---

Under review as a conference paper at ICLR 2022
Positive Accuracy
Accuracy
1.0
0.3
0.9
0.54
0.8
Aecuray
0.53
0.7
0.52
0.6
0.1
Positive accuracy function of the threshold
(b) Accuracy function of the threshold
Figure 4: Impact of threshold on positive accuracy and accuracy.
Sablayrollas Accuracy Bound Probability
1.0
0.6
0.4
Accuraty
Our Sound: c 0.1
Acturacy Bound: c 1.0
Acturacy
Our Sound: - 2.0
6.0
0.4
1.0
Probability of drawing x"
Figure 5: Sablayrolles et al. (2019) upper bound MI positive accuracy function of Px (1)
compared to our bound. Note that we are still tighter for all probabilities.
MI Advantage Probabiiity
1.75
Mi Anvertage
AlAovantage =
1.25
MiAovantage c-
Apannagg
1.00
0.50
Probubility drawinn
Figure 6: MI advantage
13

---

Under review as a conference paper at ICLR 2022
Delection Capacity Expected Training Set
12000
Our Trend
Sekhan
10000
Dalaton Capacky
2000
0-
25
50
75
100
125
150
175
200
Expocted Training Set
Figure 7: Comparing our deletion capacity trend the trend Sekhari (2021) describes. In particular our number of deletions degrades with training size while theirs increasing.
14


Reviews:
[{"review_id": "p7ZNxkZr75F", "reviewer": "Reviewer_JCNw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strengths of the paper are the following: \n1) The authors provide a tighter bound of membership inference accuracy than existing literature. This is very consequential in privacy preserving machine learning. \n2) The bounds provided by this paper are able to handle situations where the inclusion probability of samples is not 0.5 by providing separate bounds for positive and negative accuracy. \n3) The authors demonstrate a benefit of their bound by connecting it to machine unlearning in a rigorous way. \n4) The authors highlight the limitations of their approach by demonstrating that their bounds don't readily extend to approximate DP. \n\nThe main weaknesses of the paper are the following: \n1) The background needs to substantially expanded upon. I would like to at least see the following improvements: i) a formal definition of membership inference, ii) a formal definition of machine unlearning (as used in the context of this paper). \n2) I found section 4 quite difficult to follow. I believe this could be improved by presenting some background on privacy amplification by subsampling. \n", "summary_of_the_paper": "The paper provides a tighter bound for accuracy of membership inference attacks for (pure) differentially private machine learning models. To account for inclusion probability of samples being different from 0.5, the authors separately bound positive and negative accuracy. Moreover, the authors also demonstrate the benefits of their bound on machine unlearning.", "summary_of_the_review": "While the paper presents an important and novel technical contribution, it has some writing issues. In particular, the background section needs to be somewhat expanded and a particular section would benefit from more clear writing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "iC-TgDgP1MX", "reviewer": "Reviewer_rQvh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presentation count be improved.  There are some parts that could be reworded to be made more clear.  Specifically, on page 1, it states “we observe the affect of our amplification on MI accuracy is significantly stronger than batch sampling”, but does this mean that batch sampling is used to amplify MI accuracy?  As far as I know, sampling is used to decrease privacy loss parameters in DP, which should reduce MI accuracy.  It is also not clear how batch sampling is different from training data that is sub-sampled.  I also do not understand the second contribution listed.  The tighter MI accuracy bound benefits in what way with subsampling?  Do you mean the bound is tighter?\n\nNasr et al. “Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning” argues that MI is not a good attack to evaluate DP.  Do you see that increasing the privacy loss parameter with DP leads to an improved MI attack empirically, not just with theoretical bounds? As I understood it, MI was a pretty weak attack for DP, so not sure how much tightening theoretical bounds really helps here.  \n\nIn the Amplification Effect section, there should be a little more care in the amplification term that is plotted.  In particular, the amplification by subsampling converts eps -> O(q eps) and the constants might matter in the plots.  This section seems a bit hand wavy in what it is trying to say.  At a high level, I understand this section to mean that subsampling amplifies DP and reducing the probability of drawing x_i in the dataset leads to an improved MI accuracy bound.  Are there two types of subsampling going on: one for subsampling the dataset and one for batch sampling.  If they are considered the same type of sampling, can you take advantage of the DP amplification, getting O(q epsilon) privacy loss, and the dataset subsample in the MI bound?\n\n### UPDATE ###\nThe author feedback has addressed my concerns, so I will increase my score.", "summary_of_the_paper": "This work studies membership inference attacks and how differential privacy can help mitigate such attacks.  Although the connection between membership inference and differential privacy has been known, this work provides a tighter connection.  It is important for the future development of private ML to better understand the connection between DP and specific attacks as small privacy loss parameters are not practical in many settings", "summary_of_the_review": "This work provides a slightly stronger bound connecting Membership Inference attacks with differential privacy, however, the presentation could be improved and some parts are a little hand wavy.  I would also like to see more discussion on whether MIA are the right attack to consider with DP, as some recent works have shown the attack to be weak.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SdeN61XhNzS", "reviewer": "Reviewer_rm9k", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proves a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides $\\epsilon$-DP. Specifically, The bound is given in terms of $\\mathbb{P}_{\\mathbf{x}^*} (1)$, which indicates the probability of drawing \n$x^*$ into the dataset from a larger set of candidates.I have verified the proofs and they are correct. \n\nThe authors further compare the amplification effects of $\\mathbb{P}_{\\mathbf{x}^*} (1)$ with those in DP. Besides, the author also gives the connection between the bound and data deletion in machine unlearning. Overall, the whole paper is well-written and clearly organized, and the bound provided in the paper is interesting.\n\nMy biggest question is how to use the bound to the defender in practice.  Usually, the defender does not have the prior knowledge $\\mathbb{P}_{\\mathbf{x}^*} (1)$, which is completely controlled by the attack. Could you please elaborate more on how to use the information of the bound when the defender who wants to to know the limit of MI accuracy when the probability of drawing \n$x^*$ into the dataset is unknown to the user and how it improves from the Erlingsson et al. (2019) and Sablayrolles et al. (2019)?\n\nMinor:\n\nBesides, in Figure 2, is $\\mathbb{P}_{\\mathbf{x}^*} (1)=0.5$? \n\nIf  $\\mathbb{P}_{\\mathbf{x}^*} (1)\\neq0.5$, does the tightness of the bound still hold? In order to do so,  I suggest the author should provide the analytical form of previous bounds of MI in the appendix.\n", "summary_of_the_paper": "The paper provides a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides $\\epsilon$-DP. The authors also analyze their bound from the perspectives of privacy amplification schemes and its connection to machine unlearning.", "summary_of_the_review": "1. The paper is well written and the bound is insightful.\n2. The paper still needs to elaborate on the bound from the perspective of the defender.\n3. More detailed comparison about the bounds of MI are needed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bpmi_KvxXr", "reviewer": "Reviewer_gi1v", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Edit: I have bumped my score by a point after the authors' response.\n\nUpdate: on further digging into the prior work, and having discussions with other reviewers and the area chair for this paper, I have decided to downgrade my review, unfortunately. Apologies for the last minute change, but I feel like the improvements made here, which were the main focus of this paper, are a little incremental. Unless the authors’ response to the Area Chair’s comments are satisfactory, I will commit to this evaluation.\n\nStrengths:\n\n--The bounds for membership inference attacks are fairly novel.\n\n--Their experiments suggest better privacy amplification as opposed to the prior work.\n\n--The application to machine unlearning is interesting.\n\nWeaknesses:\n\n--This is not really a well-written paper. Sometimes there are vague blocks of texts like Lemma 1 and Definition 1. The latter, in particular, seems counter-intuitive based on what the text before that described. Also, what the probability is over isn't mentioned either. The role of $f$ in the accuracy statement isn't clear exactly.\n\n--Nitpick, but the definition of pure DP is stated twice in the paper (Equations 1 and 2). I don't know why this could not have been done just once.\n\n--The technical contributions don't seem that strong. The proofs don't seem to require that much depth.\n\n--Also, their bounds on the membership inference attacks don't appear super tight. Evaluating some known attacks to compare their accuracy with their own bounds could have been some kind of an evaluation.", "summary_of_the_paper": "This paper presents a tighter analysis for membership inference attacks on algorithms that satisfy $\\varepsilon$-differential privacy. It also talks about a better form of privacy amplification based on that. Finally, it discusses the role of membership inference in the task of machine unlearning.", "summary_of_the_review": "Based on the comments above, this paper doesn't strike me as a great paper. The ideas are respectable, but the execution could have been better, and more depth would have been appreciated.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: As the public post indicates, significant deliberation went into this decision. However, the core criticism remains: the primary contribution of this paper, Theorem 1, is somewhat incremental. It is acknowledged that MI is an important problem and understanding its intricacies is worthwhile, but the present paper's contributions in this space remains narrow. A more thorough exploration of the points brought up in the latest discussion and author response might help strengthen the paper. ​In particular, more careful discussion and systematic discussion and exploration of relationships between various MI attack efficacy measures (accuracy vs positive accuracy) and privacy notions (pure vs approx DP -- it wasn't totally clear how broad the result in Section 5.2.1 is without a precise theorem statement) would strengthen the paper. Additionally, while it indeed seems that the positive accuracy bound given also suffices to protect against the type of attack mentioned (where 1% of the datapoints are highly vulnerable), it is unclear if this is necessary. This feeds into the previous point: it would be valuable to get a more systematic understanding of the various MI efficacy measures and how they interact with DP. Finally, it is now appreciated that the Sablayrolles et al (2019) result worked under an unusual model restriction, though deficiencies of their result does not necessarily make this result stronger (as an aside, I believe their restriction is so that they can get a tight understanding of behavior in other settings, and DP protections were somewhat of an afterthought). The authors are encouraged to further build on this work, potentially in the directions suggested, to get a more thorough understanding of the relationships between DP and MI attacks
Decision: Reject