From Differential Privacy to Bounds on Membership Inference: Less can be More
Authors: Anvith Thudi
Ilia Shumailov
Franziska Boenisch
Nicolas Papernot
Venue: Accepted by TMLR ()

Abstract: Differential Privacy (DP) is the de facto standard for reasoning about the privacy of a training algorithm. Yet, learning with DP often yields poor performance unless one trains on a large dataset. In this paper, we instead outline how training on less data can be beneficial when we are only interested in defending against specific attacks; we take the canonical example of defending against membership inference. To arrive at this result, we first derive (tight) bounds on the success of all membership inference attacks. These bounds do not replace DP, rather they introduce a complementary interpretation of a DP algorithm's ability to defend against membership inference specifically. Because our bound more tightly captures the effect of how training data was selected, we can show that decreasing the sampling rate when constructing the training dataset has a disparate effect on the bound when compared to strengthening the DP guarantee. Thus, when the privacy protection we care about is defending against membership inference, training on less data can yield more advantageous trade-offs between preventing membership inference and utility than strengthening the DP guarantee. We empirically illustrate this on MNIST, CIFAR10 and SVHN-extended.

Published in Transactions on Machine Learning Research (03/2024)
From Differential Privacy to Bounds on Membership Infer- ence: Less can be More
Anvith Thudi
anwith. Seludd@@mmll.utooooooo
University of Toronto and Vector Institute
Ilia Shumailov University of Toronto and Vector Institute
Wio..Shummaloov@@dcccomcccm ackuk
Franziska Boenisch
franziska. htwp://ww.eeeesccccccttttttttttn
University of Toronto and Vector Institute
Nicolas Papernot
nicolas. pocollaspppeeroot@@tttooo..ooo.
University of Toronto and Vector Instiitte
Reviewed on OpenReview: https: openrevee....... net/ forun? id- daXqjb6dVE
Abstract
Differential Privacy (DP) the de facto standard for reasoning about the privacy of a Iraining algorithum Yet, learning with DP oflen yields poor performance unless one trains on a large dataset. In this paper, we instead outline how training on less data can be beneficial when are only interested in defending against specific attacks; canonical example of defending against membership inference. To arrive at this result, we first derive (tight) bounds on the success of all membership inference attacks. These bounds do not replace DP, rather they introduce complementary interpretation of a DP algorithm's 's ability to defend against membership inference specifically. Because our bound more tightly captures the effect of how training data was selected, we can show that decreasing the sampling rate when constructing the training dataset has disparate effect on the bound when compared to strengthening the DP guarantec. Thus, when the privacy protection care about is defending against membership inference, training less data can yield more advantageous trade-offs between preventing membership inference and utility than strengthening the DP guarantee. We empirically illustrate this on MNIST, CIFAR10 and extenex..
take the
1 Introduction
Differential Privacy (DP) is employed extensively to reason about privacy guarantees (Dwork et al. 2006
Dwork 2008). Recently, DP started being used to give privacy guarantees for the training data of deep neural networks (DNNs) learned through a noisy stochastic gradient descent (SGD) (Abadi et al. 2016
However training DNNs with DP has come at a cost to performance. The emerging paradigm this tension between performance and privacy to get access more private data and/or do pretraining public data, i.e., data whose privacy need not protect (Tramèr & Boneh 2020 De et al. 2022 Mehta ct al. 2022). Here, we take different direction. Perhaps surprisingly, we show that training on less data can be beneficial to the privacy vs. performance trade-off when one cares about defending against a specific class of privacy attacks. In particular, constrained to a fixed privacy guarantee we obtain models that become more accurate by training on a smaller subset of the available training data.
resolve
This is because differential privacy provides guarantees that hold for many attacks, yet our primary concern may only be preventing subset. of those attacks. Put simply, DP often leads characterization of

---

Published in Transactions on Machine Learning Research (03/2024)
privacy that is too conservative. We show that defender interested in preventing only certain forms of privacy leakage, i.e., certain attacks, is well served by deriving bounds tailored to these specific attacks. Such bounds can surface new variables undermining the success of those specific privacy attacks, and hence new rigorous defonse mechanisms for those attacks.
We take the canonical example of a membership inference (MT) attack. This is the most practical attack devised against the privacy of training data to this date, as evidenced by the line of work initiated by [Shokri et al. (017). The goal of the MI adversary is to predict whether not model used a particular datapoint for training. Defending against membership inference is common goal in prior work. Approaches either fall into the category of obtaining differential privacy (in way that is agnostic to the threat of membership inference) or deploying heuristics that forgo differential privacy to mitigate known membership inference attacks (Jia et al. 2019 Nasr et al.) 2018). The former introduces a large cost in peformance because the guarantce is too conservative as outlined above. The latter has typically better performance but is not rigorous and thus introduces an arms race between attackers and defenders.
We propose a change in paradigm: inference adversary that more tightly capture non-DP factors. That is, unlike past bounds that exclusively study the connection between DP and MI, we ask how other factors underlie the success of attacks when one has trained with DP. However, unlike heuristic defenses to membership inference, we provide guarantees that bound the success of any membership inference adversary; our bound does not introduce an arms race between attackers and defenders. In other words, we obtain the best of both classes of approaches considered thus far.
derive bounds
the success of any membership
Our first contribution is to derive bound on the success of any membership inference adversary when the model was obtained with differentially private training algorithu. Specifically, we bound the positive accuracy (f.e. precision) of any membership inference: when the adversary predicts point is a member of the dataset, how likely is it that they are correct? The key novel insight for our bound is that a membership inference adversary only ever has a finite set of points they suspect were used during training. This allows us to apply a counting lemma. We show that our bound is tight up to the looseness of the DP guarantee provided by the training algorithm. This means our bound cannot be improved further without improving the DP guarantee itself or replacing it by another guarantec.
Our second contribution is to observe that our bound surfaces dominant factor in the success of mem- bership inference attacks: how the training set was sampled. This factor has an even larger effect on the bound than the strength of the DP guarantee the model was obtained with. It suggests a new paradigm to alleviate the previously observed tension between defending against membership inference (MT) by training with DP and training performative models. Concretely, as our bound better descríbes the effect of different regimes of sampling training data, we are able to demonstrate the effectiveness of subsampling training data form of privacy amplification specific to defending against MI. By subsampling the training data, we are able to obtain increased privacy in the form of increased robustness to MT that outweighs the degradation in performance that results from training on smaller dataset. As a result, we surprisingly find that training on less data can yield more advantageuus trade-offs between privacy and performance whhen one is primarily concerned about limiting the success of membership inference.
We illustrate this phenomenon on MNIST, CIFAR10 and SVHN-extended. Notably, we confirm that this theoretical outweighed benefit. of subsampling empirically translates to increased robustness state-of-the- art membership inference attacks (Carlini et all 2022a As predicted by inspecting our bound, also confirm experimentally that training with less data can result in a more accurate model when one is given a fixed target bound (i.e., a maximal MI precision they can tolerate). We attach our code in the supplementary material and will open-source it upon publication.
2

---

Published in Transactions on Machine Learning Research (03/2024)
2 Background
2.1 Differential Privacy
Differential privacy (DP) @work al.) 2006) bounds how different the outputs of function on adjacent inputs can be in order to provide privacy guarantees for the imputs. More formally, function F is e-DP if for all adjacent inputs x and x' (i.e. inputs with Hamming distance of 1) we have for all sets S in the output space:
P(F(2) E S) S P(F(((()) S).
(1)
There also is the more relaxed notion of (c, 6)-DP which is defined for the same setup as above, but introduces a paramcter E (0, such that P(F(x)) E S) I (T(((=))) +)+ Notably, (e, 8eP is used for functions where it more natural to work with lg metrics on the input space, having 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 is calibrated to the maximal &2 or & difference between all possible outputs of the function on adjacent datasets (also called sensitivily). Significant progress was achieved on minimizing the amount of noise needed
for given sensitivity (Balle & Wang 2018
Dwork et al. 2010 Kairouz et al. 2015
Song et al. (2013): Bassily et al. (2014): Abadi et al. (2016) demonstrated method to make the final model returned by mini-batch SGD (c, O)PD) with respect to its training dataset. This is done by bounding the sensitivity of gradient updates during mini-batch SGD and introducing Gaussian noise to each update. Despile being the de facio approach to learning with DP, the adoption of DP-SGD is still greatly limited because of an observed trade-off between privacy guarantees and model performance As discussed in the introduction, a common approach to address this tradc-off is to soek access to additional data that is public (Tramer & Boneh 2020 De el al. 2022). We remark now that there are other DP notions used to analyze DP-SGD that provide tighter analysis, such as Rényi DP Mironov (2017) and f-DP Dong et al. (2019), and leave it future work to study optimal membership inference bounds under those definitions.
2.2 Membership Inference
Membership inference (MT) asks, given a model and datapoint, can the adversary infer if the given datapoint was used in the training set? [hhkki et al.) (2017) introduced an MI attack against deep neural networks (DNNs), which leveraged shadow models (models with the same architecture as the target model) trained on similar data. Given these shadow models, they then trained a classifier which, given the outputs of a model on a data point, predicts if the model was trained on that point or not. Since the introduction of this initial attack, the community has proposed several improved variations of the original MI attack (Yeom)
et al. 2018
(Salem al., 2018 (Sablayrolles al.] 2019 Truex et al.) 2019 Jayaraman et al.) 2020 Maini Choquette-Chor al. 2021 These privacy attacks are currently the most practical attacks an adversary can implement against a machine learning model.
et al.
2021
2.3 Previous Bounds
We are interested in providing bounds on the success of MI attacks against algorithms that provide DP. Initially, prior efforts (Yeo et al., 2018 Erlingsson et al., 2019 Humphries et al., 2020 Mahloujifar et al. 2022) only considered the restricted case where candidate for MI (i.c., point that may or may not have been used to train the model) always has a prior 50% probability of being a training dalapoint. [Sablayrolles et al. (2019) were the first to introduce the prior probability Px- (1) of the datapoint being sampled into the training datasct as factor of their analysis. They bounded the probability datapoint x" was in fact used to train the model (i.e. Pxxx E Dtrain(S) which we will refer to as "positive accuracy" in Section 3) by xxx (1) + G- However this bound (a) assumes that the algorithm is eDDP, i.e. , requires = O, and (b) only loosely describes the impact of x (1). We address both of these limitations in our paper.
Indeed, our first step will be to give a bound that more tightly captures the effect of Px (1): a non-DP factor affecting the bound. We point this out key observation of our work will be that varying this sampling
3

---

Published in Transactions on Machine Learning Research (03/2024)
probability has disparate effect on MI (compared to strengthening the DP guarantee). Furthermore, changing the sampling rate is in fact in the model trainer's 's control, and so this will also allow us to propose practical mechanisms a defender can use to boost their ability to defeat MI.
We lastly point out that concurrent work by Mahloujifar et al. (022) improves the bound by Sablayrolles et al. (2019) to Ite- This however comes at the expense of reintroducing the assumption that T'x
1=
U.5 (i.e. the prior probability of the datapoint being sampled into the training dataset is 50%) and an additional assumption that all other data is fixed. Our bound will match theirs at this sampling rate (1) 0.5, but notably generalizes to having multiple variable datapoints all with different sampling rates. This generalization is crucial for making subsampling mechanism a defender can usd A more detailed discussion comparing the different aforementioned bounds and their proof techniques in light of the advances made in our paper is deferred to Appendix B
3 Bounding Membership Inference
As highlighted in Section 2.3 past bounds are largely agnostic to, or do not tightly capture, factors influencing membership inference beyond the DP guarantee of the algorithm. We proceed to derive a more general membership inference bound that better incorporates the prior likelihood (before observing the final model) of whether datapoint was sampled into the training set. The bound obtain constitutes this paper's first principal result. It is from this improved bound that we later describe how controlling the sampling rate of data into the training set can constitute an effective and desirable defense against membership inference.
3.1 Definition of Membership Inference and Notation
We first introduce some notation. In the rest of the paper we assume the training dataset D is a random variable over subsets of a set {x1,-.., xyJ, and use x* E D to denote the event that D contains a particular datapoint v"; formally D E Dx- where xx- denotes subsets containing x*. Later Section 3.2 we specily the distribution of D: a product distribution of i.i.d Bernoulli random variables associated to each datapoint x (x1,".. xx} for some N, where let P1) denote the probability the bernoulli random variable associated to x is 1 (representing being sampled into D). We also use H to denote the training function, which takes as imput the training dataset D.
The objective of an MI adversary is to predict if the event x" E D occured given only the ouputs of training on D, Le., a function MI(x", H()) E 10, More specifically, to every MI adversary, we can associate a set of models (or generally, algorithm outputs) for which it predicts the datapoint x" was in the training dataset D (i.e., a member). Let us call this set S. In fact, the set S completely characterizes the adversary; on S the adversary predicts x" was member, and on S the adversary predicts not a member. Hence, now just working with the set S, we can abstract what an MT adversary is and state an equivalent definition of membership inference in terms of conditionals. Specifically, we have the following definition of the adversary's 's "positive accuracy', f.e. accuracy when predicting x* is in the training set (also called precision or positive predictive value in the literature]). p. For brevity we use P(x* e DJS) to denote PP(x E DJMT(x", M(D) = 1) = PPxx E (D) E S), ie., the conditioning on denotes conditioning on the MI attack predicting x" is a member given H(D).
Definition 3.1 (MI positive accuracy). The positive accuracy of a MI adversary, associated to the set i, is P(x" DJS). Similarly, the negative accuracy is P(x" DIS) = - Pxx" E DJS),
For notational simplicity, will often use P(x*|S) (S) to denote P(x* e DIS). We explain more about where the randomness is introduced (in particular the probability involved in obtaining a training dataset which the hypothesis test for membership inference acts on) in Section 3.2
AA defender would most likely want preserve the privacy of multiple datapoints simultancously.
We stick away from using the terms precision and positive predictive value in the literature they are specific to the "adversary" interpretation of the definition, while seems this abstraction in terms of 5 may be of more general interest.
4

---

Published in Transactions on Machine Learning Research (03/2024)
3.2 The Setting
We now proceed to formalize how entity samples data into the training dataset, i.e., our prior on whether datapoint x* was used to train a model before observing a specific set of models. The intuition for our formalization is the existence of some finite data superset containing all the data points that 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 a black-box such that not even the entity knows what data was used to train. We can then imagine that the adversary knows the larger dataset and tries to infer whether particular point was used in the training datasct. This sctting defines the prior will assume for the MI allacks we bound, and we now explain the lerminology and facts regarding this setup that we will use.
Specifically, let the individual training datasets D be constructed by sampling from a finite count- able set where all datapoints are unique and sampled independently, i.e. from some larger set (XI,"",,
That. is if D = (2,,X,,... ; }n} then the probability of sampling D is P(D) = Px, (1)Pxx(1) .x.
.............................. Px, (1) (O)...PP (0), where Px (1) is probability of drawing x, into the dataset and Px, (0) is the probability of not.
We define D the set of all datasets. Let now xx be the set of all datasets that contain a particular point x" [x1,-.. xN), that is Dx- (D x" E D). Similarly let xx be the set of all datascts that do not contain x", i.e. Dx.' (D's : x & D'). Note D = xx U U by the simple logic that any dataset has or does not have x² in it. We then have the following lemma.
Lemma 3.2. xx- and Dx''' are in bijective correspondence with P(D) (0) (0) D' E xx' that map to each other under the bijective correspondence.
(1) P(D') for E Dx and
Proof. Note that for given D = (xi..... xn) Dx D' Dz= = D/x E Dx-' is unique (t. the map by removing x" is injective) and similarly for given D' DD''D' 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 Dx.'' are in bijective correspondence.
D= D'Ux' is unique (i.e. the map by adding
Now if the larger set of datapoints is {x1 (x1.-xXn-1 1, x", Xn ... .xN} letting = fxi ..... xx---x U x" and D' = {x1.... ....Xx-1} be any pair of datasets that map to each other by the above bi- jective map, then note PPD) Fx (1) (1) (1)...PP ....P..., (1)Px (I)....PP..,, (0). ..)...P... Px (0) and P(D")
Px (1)P (1).... ... Px P..., (1)P (O)....Px...................
... Px..1 (0)... .... Pxx (0). In particular we have P(D)
P.. (0)
P P(D)).
Once some dataset D is obtained, we call H the training function which takes in D and outputs a model M represented by a real vector. Recall that H is (PP if for all adjacent datasets D and D' and any set of models S in the output space of H (i.e some weights) we have: (P) E S) I (PH((( E S) +
3.3
The Bound
We now proceed to use Lemma 3.2 to bound the positive and negative accuracy of MI, as stated in Definition This will be done for a training function H that is (c, d)DP, under the data-sampling setting defined earlier.
3.1
From now on we assume that the set S has non-zero probability be produced by H given x* in the training set (or not in the training set in the case of negative accuracy bounds). This is sensible we are not interested in MI positive negative accuracy for adversaries that never predict positively or negatively respectively.
Theorem 3.3. For any MT altack on datapoint x" (i.e. with any associated set S), given the training process H is (E, 8)DP, we have its positive accuracy is upper- soper-bouuded by (Sx*(S) < (1+ (0)) be- (U)
)
Fx) P[S
5

---

Published in Transactions on Machine Learning Research (03/2024)
long the right-hand side is positive. Similarly we have the negative accuracy is bounded by P(x' DDS)
(1 +
(1)
de de-(P.(())
(0) FD)
Proof. The positive accuracy of an adversary f associated to any set S is: P((x1S)) = Enes F(H(D))S)P())
EDER P(M())ES)P()))) DD'esy D'est. R(H(D)))))(()))
Now using that P(H(D)) 8) e (PH( E ()- =6 and P(D') P(D) (x) -- (0) (H)H E S) Se ED'ED' P(D)).
have the denominator
(1)
is 2 EDED,. (1+
(1)
Note that de E>EEE P(D') = S -ErEE P(D') EDED P(I())S))(L)
LIED. P(H(D)ES)P()) So now cancelling the EDED,. (DH(D) S))(D) in the numerator and denominator, and noting EDeo, P(H(D) S)P(D)
P(S]x*) and Eneo P(D)) xx (0), we have PSx S (1 Txt Te
(1) F(Sxx) )- Note this is only
true if the right-hand side of the bound is positive, the fact a/b a/c if c (which we used) is only true if c is positive when and b is positive.
Note that a completely analogous proof proves the negative accuracy bound.
Remark on P(S)x*). Implicit. in Theorem 3.3 is the fact we must. accept. a probability of failing to mean- ingfully bound positive accuracy when * O, i.e. we need to assume a lower- on PPS[x*) when of O. Otherwisc the expression in Theorem 3.3 can approach oo P(S[x*) - 0. Our failure bound positive accuracy as IPS)x")) + is in fact "necessary" for any bound on positive accuracy, as without a lower bound (P(S(x*) allow adversaries whose positive accuracy can be arbitrarily close to even when training with (c, DP; an example of class of adversaries whose positive accuracy approaches 1 as allow P(S]x") + 0 is given in Appendix A.1 One can interpret this mode of failure as accepting "we may fail for adversaries that would predict positively infrequently if we did train with x*
Remark on tightness of the bounds. The bounds in Theorem 3.3 are tight if all the differential privacy inequalities we use (specifically P(H(D)) E 8) 2 E=(P(((()) E 8 ) E xxx) are tight. This is due to those differential privacy inequalities being the only inequalities appearing in the proof. Hence, any future improvement would have to go beyond the DP condition and incorporate the looseness of the DP guarantee on different datasots. This means that our bound is optimal when no such knowledge provided.
3.4 Comparing Px- (1) to the privacy budget
The bound given by Theorem 3.3 can be reduced by decreasing Px- (1) the privacy budget E. Reducing (1) corresponds to "dataset subsampling", i.e. downsampling the original training set to a new smaller training set. However, the privacy budget E can also be reduced by a sampling strategy: reducing the mini- batch sampling rate during DP-SGD is known to reduce the overall & by "batch sampling" amplification. So we have that both dataset subsampling and batch sampling provide privacy amplification (for MI) as they decrease our bound. However, is the effect of these two sampling strategies on our bound quantitatively different? As batch sampling acts on our bound by decreasing E, we will compare the impact on our bound vary Px- (1). In the following, take 8 = 0 for simplicity.
To first get a sense of the impact Pxx (1) has our bound, we plot Px (1) against the positive MI accuracy bound from Theorem 3.3 in Figure [ for different e. The trend we see is that the bound decreases to 0 as Px (1) goes to O, and for large this drop happens sharply. However, by decreasing e we have the bound converges to Px-(1) which need not be 0.
We now quantitatively compare the effect of to the effect of Px (1), where the latter appears in our bound (0) (1) = (1 Pxx (1))/Px (1). We can compare the impact of to the of Px-(1) by looking
6

---

Published in Transactions on Machine Learning Research (03/2024)
at the term (=)x(())Px in the bound given by Theorem 3.3 the goal is to maximize this to make the see that decreasing e increases this term by O(e
upper bound as small as possible. In particular, whereas decreasing Fxx (1) increases this term by O((1t)/t) which is weaker than O(e up to a point, then stronger: we are looking at the order as the variable decreases. Figure 2 plots this relation, however, the specific values are subject to change with differing constants. Nevertheless what does not change with the constants are the asymptotic behaviours, and particular we see lim O(11 - t)/t) oc where as lim;-00 O(e=))= = constant.
Thus, we conclude from bound that the effects of data sampling and (which encompasses batch sampling) are different. In other words, data sampling presents non-DP method to reduce MI positive accuracy.
Bound Probability
0.6
0.4
6.2
Bound
Poz Acc
Acc Bound: 6-
0.0
Poz Acc Boundi c-
0.0
0.2
0.4
0.6
0.5
Probabilkt of drawing x
Figure Upper bound on MI positive accuracy from Theorem
3.3
setting 0, as a function of Txx (1)
4 The MI Sampling Mechanism
We now focus what will be the key benefit of the bound we derived in Theorem 3.3
the effect of Pxx (1) on the success of MI attacks. As we just observed in Section 3.4 the Px- (1) dependence of our bound dominates its E dependence. This means that decreasing Pxx (1) will impact the bound more than strengthening the differential privacy guarantee (i.e., lowering e).
We now describe in Section 4.1 how this gives a new mechanism a defender can use to prevent membership inference, which we call the "MT sampling mechanism". Following this, we show in Section 4.2 one can empirically observe the disparate effect of this mechanism in the current state-of-the-art membership inference attack (Carlini et al. 2022a).
This will have explained the usefulness of subsampling the training set for entities that can afford using small sampling rates xx (1), e.g,, have more data than they can train on. However in Section 4.3 we empirically show a favorable trade-off between low sampling rates and performance on MNIST, CIFAR10 and SVHN- extended. That is, we will show training on less data can be beneficial for the privacy vs. performance trade-off on benchmark datascts so long as the entity training the model interested in only defending against MI attacks.
4.1
Usefulness for Defender
We now explain one course of action defender can take in light of the privacy amplification for MI given by Px (1). Note that upper bound on Px- (1) translates to upper bound the relation found in Theorem This is as the bound is increasing with (x) Hence one can, in practice, focus on giving smaller
3.3
upper-bounds on Px- (1) to decrease MI positive accuracy.
A possible approach to this is as follows: assume a user (the defender) is given some sample D C [xi,... x drawn with some unknown distribution. In particular, the user does not know the individual probabilities for the points being in D and whether these points were drawn independently. However, assume that the user obtains from D the training dataset Dtrain by sampling any point from D independently with
7

---

Published in Transactions on Machine Learning Research (03/2024)
Comparison Privecy Amplification
5
DP Ampliiction
Our Ampification
Anvo Andultn
0.0
0.2
0.4
0.6
3.8
1.0
Figure 2: Comparing the DP amplification observed by decreasing batch probability (given by ((e-9) to the amplification we observe from decreasing (1) (given by O((1- ((I)) in Theorem 3.3 setting
probability T. Our bound then bounds the conditional probability PP D) with (1) = T. Note that [Sx*|S) S P(x*|S D) x* D, so our upper-bound also bounds P(x* [S). That is, one can use our bound to give upper-bounds for points sampled from unknown (not necessarily i.i.d) distributions if independent sampling (i.e. as needed for Lemmna 1) is applied after drawing from this unknown distribution.
To give real-world example of this procedure, assume D is obtained by scraping Wikipedia articles, following some protocol that may be deterministic. In this case, without exact knowledge of the sampling probabilitics of points, and a guarantee they were independent, we cannot use our bound. However, given D, now consider sampling from specific sentences (i.e., inputs) independently, where each sentence has probability T of being included into the new dataset Dtrain. We then train our model using DP with Derein. We then can apply Theorem 3.3 to bound the positive accuracy any adversary (that makes deterministic decisions given the models returned during training) can have by setting P., (1) = T in the Theorem (explained in more detail in the second paragraph of 4.1).
4.2 Empirical Attack Case Study
To study the empirical effect (1) on MI positive accuracy, we will observe the positive accuracy of the current state-of-theeart membership inference attack, LiRA (Carlini et al., 2022a), as we vary Px- (1). We also train with different (c, 6D-DP guarantecs. In the original paper, the attack was not evaluated against DP trained models, we reimplement the attack ourselves on MNIST, CIFAR10, and SVHN-extended. In particular, we follow Algorithm in Carlini et al. (2022a) but now the training function is DP-SGD, varying with fixed 8 = 10-5, and using the hyperpaprameteers and models of Tramèr & Boneh 2020) for training " We train 20 shadow models for each E sctting (i.e. rouse the same shadow models for all the points we test), sampling their training sets uniformly with 50% probability from the original training set. Our larget models use the same training function as the shadow models, but we now vary the P.. (1) to capture the effectiveness of the attack on target models with different sampling rates.
We evaluate the attack by computing the scores that Algorithm 1 in Carlini et al (2022a) outputs for the first 1000 training points of MNIST, CIFAR10, and SVHN-cxtended respectively. In each sctting, we consider different thresholds for acceptance according to quantile based approach: we consider accepting the top i 2.5% quantile scores for every i E [40], and report the best precision (positive accuracy) out of all these different thresholds (i.e. select the highest precision threshold) []]
Figure 3 plots the average positive accuracy (from 5 repeated trials) of the LiRA attack for different e function of the (x)(1) used for the target model. We further plot the positive accuracy of the baseline attack of always predicting a datapoint is in the training dataset. As we see, the LiRA attack consistently outperforms the bascline, but importantly, we see that the sampling is the dominant factor dictating
IIn the of Sytteexxedded, take the CIFAR1O hyperparametcrs and model architecture
4 4Due to numerical instability (e.g. the handling of the density value in the tails of the Gaussian), the score at times these cases, our attack predicts the point was not training point.
8

---

Published in Transactions on Machine Learning Research (03/2024)
eps
1.0
Positive Accuracy
1.0
Positive Accuracy
3.0
eps 3.0
eps 5.0
eps 5.0
7.0
eps 7.0
eps 7.0
9.0
Postive
0.4
eps 9.0
eps 9.0
0.4
eps 12.0
eps
eps 15.0
0.2
baseline
baseline
baseline
0.4 Sampling Probability (1)
Sampling Probability P2-(3)
Sampling Probability Px)(1)
(a) MNIST
(b) CIFAR10
(c) SVHN-extended
Figure 3: Membership inference positive accuracy of the state-of-the-at LiRA attack (Carlini et al. 2022a on MNIST (left), CIFAR10 (middle), and SVHN extended (right) as a function of the probability Fx of point being sampled into the training set. The LiRA attack is conducted against models trained with differential privacy. Different curves are obtained by varying the privacy budget æ used by the differentially private training algorithm (DP-SGD of Abadi et al. (2016)). Observe how sampling is the dominant factor dictating how much the LiRA attack outperforms the baseline atlack (i.e. predicting point is always member).
0.07
Average Improvermen Over
Improvement Baseline
Average Improvement
Over Baseline
0.05
0.06
0.04
0.04
0.03
0.02
0.02
0.02
Sampling Probabilty Ps-(1)
Sampling Probability (2)
Sampling Probabilty Pz-(1)
(a) MNIST
(b) CIFAR10
(c) SVHN-extended
Figure Relative improvement of membership inference positive accuracy for the LiRA allack over the baseline attack on MNIST, CIFAR10, and SVHN-extended. This improvement plotted as function of the probability Px (1) of point being sampled into the training set. We include the 95% confidence interval (over the 7 values of æ from Figure 3 and 5 trials). Observe how low sampling probabilities Px- (1) disproportionately mitigate the improvement. in membership inference brought by the LiRA attack.

---

Published in Transactions on Machine Learning Research (03/2024)
100
80
80
40
Accuracy
Best Accuracy
Best Accuracy
60
60
30
20:
40
Bound
20
Bound 0.881
0.881
Bound 0.881
Bound 0.731
Bound 0.731
Bound 0.731
0
Sampling Probability (1)
Sampling Probability (x-(2)
Sampling Probability P2-(1)
(a) MNIST
(b) CIFAR10
(c) SVHN-extended
Figure 5: Best accuracy for MNIST (left), CIFARIO (middle) and SVHN-extended (right) as a function of the sampling probability Px (1). The plots are obtained by fixing a target positive accuracy bound and using Theorem 3.3 to interpolate across the values of Px-(1) and & achieving the bound. The bounds are computed assuming P(S[x*) 2 1% in Theorem 3.3 We report the best test accuracy from 100 epochs of training. Observe how there is preference for smaller sampling rates, which is more distinct for smaller fixed positive accuracy bounds. We include the 95% confidence interval over 5 trials.
100
40
80
80
Bound
Accuracy
Final Accuracy
30
Bound 0.731
Enal Accuracy
660
60
20:
Bound
Bound
10
20
Bound 0.881
Bound 0.881
Bound 0.731
Bound 0.731
0.8
Sampling Probability (1)
Sampling Probability (1)
Sampling Probability Px-(1)
(a) MNIST
(b) CIFAR10
(c) SVHNN-xxtended
Figure 6: Final accuracy for MNIST (left), CIFAR10 (middle) and SVHN-cxtended (right) as a function of the sampling probability Px-(1). The plots are obtained by fixing a larget positive accuracy bound and using Theorem 3.3 to interpolate across the values of Px-(1) and & achieving the bound. The bounds are computed assuming P(S[x*)= 2 1% in Theorem 3.3 We report the final accuracy from 100 epochs of training, Observe how there is preference for smaller sampling rates, which is more distinct for smaller fixed positive accuracy bounds. We include the 95% confidence interval over 5 trials.
10

---

Published in Transactions on Machine Learning Research (03/2024)
how much we outperform the baseline. That is, this state-of-the-art attack can be made less effective by applying our MI subsampling mechanism-an as predicted by our bound.
To further illustrate this outweighed effect of sampling over e; Figure 4 plots the average improvement (over the E values from Figure 8 and 5 trials) against the baseline attack. What we see is that both low and high sampling rates see less an improvement over the baseline than medium sampling rates. In particular, this shows low sampling disproportionately mitigates membership inference. This behaviour is consistent with what we expect from our bounds (see Figure 1
4.3 Performance vs. Sampling
We now study the trade-off between sampling to prevent MI and model performance on MNIST, CIFARIO, and SVHN-extended. That is, we fix a target MI bound and vary Px- (1) as we vary according to the formula given in Theorem 3.3 assuming P(SIx*) 2 1%. That is, bounding only adversarics that predict positively at least 1% of the time when actually training with x² This is shown in Figures 5 and 6 where the final accuracy is the accuracy after training for 100 epochs and best accuracy is the highest achieved accuracy during the training run. The fixed target bounds were chosen to be those achieved when setting (1)(1) = 0.5 and taking & = 2, 1 with = 10-5. In training, we used the models from Tramèr & Bonch (2020g with the training hyperparameters being those reported to perform the best for e 3 by Tramer &
Bonch p020
We observe that MNIST often finds optimal accuracy with (x- 0.5, though for the tightest bound observe there is preference for smaller (1). CIFAR10 suffers more disproportionately from having smaller epsilons than having smaller datascts, tending to have an optimal accuracy with Px (1) = 0.3. This is even more apparent when looking at the final accuracy for CIFARIO, where Px- (1) = 0.1 often performs best. We conclude that CIFARIO performance benefits from low sampling (with some fixed target MI bound). SVHN-oxtended follows similar trends as CIFAR10, with stronger preference of low Px- (1) when considering smaller fixed MI bounds (c.g., the bound when using 1 with (1) = 0.5).
So to conclude, for MNIST, CIEAR1O, and SVHN-extended we empirically observe that lower sampling, i.e., training with less data, is beneficial for performance.
5 Why Bound Membership Inference?
So far have motivated the usefulness of studying membership inference by the fact membership inference is currently the most practical attack against DNNs. In this section, further connect the pursuit of bounding membership inference to other privacy attacks and topics of general interest to the MI. community.
5.1 Importance to Data Deletion
The ability to decrease MI positive accuracy, f.e. the ability for arbitrator to attribute data point to model, has consequences for machine unlearning and data deletion. Cao & Yang) (2015) were the first to describe a setting where it is important for the model to be able to "forget" certain training points. The authors focused on the cases where there exist efficient analytic solutions to this problem. The topic of machine unlearning was then extended to DNNs by Bourtoule et al. (2019) with the definition that a 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 carlier by Ginart al. (2019) for other classes of machine learning models.
Given that unlearning is interested in removing the impact a data point had the model, further work employed MI accuracy on the data point to be unlearned as a metric for how well the model had unlearned it after using some proposed unlearning method (Baunhauer et al., 2020 Graves el al. 2020 Golatkar el al., 2020b a). Yet, empirical estimates on the membership status of a datapoint are subjective to the concrete MI attacks employed. Indoed may be possible that there exists a stronger attack. The issue of empirical MI for measuring unlearning was recently illustrated by Thudi al. (2021) and [arlini et al. (202bb) where they highlighted undesirable disconnects between it and other measures of unlearning.
11

---

Published in Transactions on Machine Learning Research (03/2024)
Applying our result to unlearning. Analytic bounds to MI attacks, on the other hand, resolve the subjectivity issue of specific MT attack as a metric for unlearning as they bound the success of any adversary. In particular one could give the following definition of an unlearning guarantee from formal MI positive accuracy bound:
Definition 5.1 (B-MI Unlearning Guarantee). An algorithm is B-MI unlearnt for x* P( & DIS) > B, iee the probability of x" 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 unlearn- ing. In particular if P(xx E D)S) 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 it most likely came from a model without it: iee leading to plausible deniability. This where unlearning is presented probablistically in
is similar to the logic presented by Sekhari et al. (2021) terms of (e, Jullearnnn
We also observe an analogous result to Sekhari et al. 2021 where we can only handle a maximum number of deletion requests before no longer having sufficiently low probability. To be exact, let us say we do not need to undergo any unlearning process given set of data deletion request x* if P(x* & DIS) 2 B for some B. Now, for simplicity, assume the probability of drawing all points into the datasets are the same and, so that for all x we have the same bound given by Theorem 3.3. that is P(x; & DIS) > L for some L S 1 Then we have PPX* & DIS) > L as if x- = Xi,
X then P(X* & DIS) P(xi & DIS) .((; $ o D) but this conditioning on the other datapoints not being sampled does not 1n in
DJS, {x] x5. .............................. -1) xx, } change our lower-bound 6 Hence, an entily does not need to unlearn if L. > B, i.e. m S
In In
This gives a bound on how many deletion requests the entity can avoid in terms of the lower bound on
negative accuracy implied by the upper-bound on positive accuracy given in Theorem 3.3 In particular, if
(x1...Xx) is the larger set of data points an entity is sampling from, and Px(1) = o/ Vx E (x1 (x)).
XN):
then the lower bound (taking d = 0) is (1+ =-
I-
Corollary 5.2 (B-MI Unlearning Capacity). If (x1 1x11...0 x is the larger set of data points entity is sam-
In B pling from, and Px(1) = c/N Vx E (x1 .xxN,, then one can delete m S In I[e) and satisfy B-MI unlearning.
with L(c) = (1 (1+ a 11+1-g))
1-
Sekhari et al. (2021) showed that with typical DP the deletion requests grow linearly with the size of the training (in the above case e represents the expected training set size). We thus compare lincar line w.r.t to L(e] and == as we are interested in asymptotics. We observe that our deletion capacity is significantly higher for low expected training dataset sizes and is marginally lower than lincar trend for larger training set sizes.
In B (given by Corollary 5.2h in Figure to observe their respective magnitude: we fix B = 0.8, N = 10000
5.2 Applying to Data Reconstruction
An interesting question is how training with DP impacts the effectiveness of data reconstruction attacks. The goal of a data reconstruction attack is, given model (and/or the sequence of models used to obtain it), to have an algorithm that outputs a training point: more realistically, a point close to training point. In this sense, the attack "reconstructed" a training datapoint. An immediate consequence of our MI positive accuracy bounds is a statement that data reconstruction attacks are not trustworthy; even when they reconstruct an image close to a possible datapoint, the probability of the datapoint actually being a training datapoint is bounded.
Corollary 5.3 (Data Reconstruction not Trustworthy). Consider a deterministid] "data reconstruction" algorithm R that takes a model (or the training sequence of models) M and outputs datapoint. We say it
SThis L is given by 1 minus the upper bound on positive accuracy Itt changes the larger set of possible data, but the bound is agnostic what this set is and only depends on the individual sampling probability ? "One could consider random algorithms, but fixing the random seed the bound will apply. As the bound applies for every random seed, also applies in expectation.
12

---

Published in Transactions on Machine Learning Research (03/2024)
Capacity Expected Training
12000
Dur Trend
Sekhari Trund
10000
Delesion Capacity
4000
2000
0
25
50
100
125
150
175
200
Expected Trairing Set Size
Figure 7: Comparing our deletion capacity trend to the trend Sekhari al. (202)) describes. In particular, our deletion capacity grows as the expected training size decreases.
"reconstructs" training datapoint out of the set of possible datapoints D == fx,,... xx.] if for some metric d, d(R(M), x,) < e for some 2 0. For any Xs, consider the sel S = (M d(R(M), z }} of models it
claims to have trained on X1- By Theorem 3.9. when training with (e,6)-DP, the probability x; was actually
used train models in S is (S) s (1 (1)
(0) 6E 5F -0)
P(S
Proof. Just an application of Theorem
3.3
However, we believe a more interesting question is if, considering specific class of reconstruction algorithms R, we can lower bound the reconstruction error (with high probability). We believe this should possible, but currently are not sure what an appropriate class of is. A naive idea is that d(R(M), x) S e iff E D, that is, the algorithm can only reconstruct datapoints used the training set. However, the above corollary states no such attacks can exist when training with e-DP. So it stands this characterization might, be too powerful. We leave finding fruitful classes of reconstruction attacks to study for future work.
5.3 We can Bound Generalization Error
In this subsection highlight connection between bounds MI adversaries and generalization error. Yeom et al. (2018) studied MI adversaries in the Px (1) 0.5 setting, f.e. 50% probability of being sampled,, that took advantage of a generalization gap Rg between training and non-training datapoints. Specifically, they described an adversary whose accuracy is (R,/ /B/1//2, where B is an upper- upper-bound on the loss (Theorem in Yeom et al. (2018)). However, note that this accuracy is upper and lower-bounder by Theorem 3.3 as the theorem bounds the accuracy of all adversaries when Pxx = 0.5. The lower-bound because the upper-bound on negative accuracy gives a bower-bound on positive accuracy, and similarly the upper-bound on positive accuracy gives a lower-bound on negative accuracy. Thus we have the following corollary.
Corollary 5.4 (MI bounds Generalization Error). For loss function upper-bounded by B and an s-DP training algorithm, (Definition 3 in Yeom et al. 2018), where their D is our larger set, and their S is the specific training set sampled from the larger set).
have (1+ee) -1+ < (Rg/ B + 1)/2 < (1 + e where Rg is the generolization gop
This tells us how well the Px- (1) = 0.5 sampled dataset generalizes to the entire larger set. We believe this general procedure using specific adversaries with accuracies dependent on values of interest (e.g. the generalization gap here) and applying more general bounds to get a range for those values of interest is somothing future work can expand on.
6 Conclusion
The current paradigm for boosting performance when obtaining private models train on more, often public, data. In contrast to this, showed how training on less data be beneficial for the privacy vs.
13

---

Published in Transactions on Machine Learning Research (03/2024)
performance trade-off. This was done by first obtaining new membership inference bound that more tightly captures the effect of small training set sampling. In Appendix B we give more details on how our bound relates to prior bounds. This allowed us to describe a new privacy amplification mechanism that a defender can reasonably take advantage of, and we showed that the disparate effect of this mechanism can be seen empirically the current stale-of-the-art membership inference attack. Studying the effect of this sampling mechanism on performance, we showed that what we gained in performance by being able to use weaker DP guarantees outweighs what lost by training on less data. Ultimately, smaller training sampling rates can lead to performance gains while retaining specific privacy guarantees.
Broader Impact
Our results show that under specific threat models and metrics of privacy leakage, we can have alternative ways of protecting privacy when using machine learning complementary differential privacy, leading new "sweet spots' for model performance. In particular, we have shown that when ent wants to claim datapoint, such as for unlearning, modifying their sampling rate of training
deniability of training points is one method to do so which allows them to train with weaker DP guaranatees. We believe this result motivates further consideration of the different real-world threat models and the methods to ensure "privacy" in those threat models, such as the role of priors (i.e., sampling rates) and what the attack can use (i.e., deterministic given the models returned in training).
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Dyy Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and commanications security, pp. 308-318, 2016.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394-403. PMLR, 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient al- gorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464 473. IEEE, 2014.
Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer. Machine unlearning: Linear filtration for logit-based classifiers. arXiv preprint wwXi:2002.007990 2020.
Lucas Bourtoule, Varum Chandrasekaran, Christopher A Choquette-Choo Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. arXiv preprint 1918:1111,.08817, 2019.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Prinacy, pp. 463-480 TEFE, 2015.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1917-1914. IEEE, 2022a.
Nicholas Carlini, Matthew Jagielski, Nicolas Papernot, Andreas Terzis, Florian Tramer, and Chiyuan Zhang, The privacy onion effect: Memorization is relative. arXiv preprint arXiv:2206.1000 10469, 2022b.
Christopher A Choquetto-Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot Label-only mem- bership inference attacks. In International Conference on Machine Learning, pp. 1964 1974. PMLR, 2021.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arxiv preprint arxiv:2204. 13650, 2022.
14

---

Published in Transactions on Machine Learning Research (03/2024)
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. arXiv preprint 023883 2019.
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and appli- cations of models of computation, pp. 1-19. Springer, 2008.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to scnsitivity in private data analysis. In Theory of cryplograhyy conference, pp. 265 284. Springer, 2006.
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. IEFE, 2010.
Ülfar Erlingsson, Nlya Mironov, Ananth Raghunathan, and Shuang Song. That which call private. arXiv preprinl Xiv: 03566, 2019.
Antonio Ginart, Melody Y Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. XrXiv preprint 15:::1997000111 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVE 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 obscrvations. In European Conference Computer Vision, pp. 383 398. Springer, 2020b.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. arXiv:2010. 10981, 2020.
Amnesiac machine learning. ar preprint
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. The Journal of Machine Learning Research, 14(1):703 727, 2013.
Thomas Humphries, Matthew Rafuse, Lindsey Tulloch, Simon Oya, Ian Goldberg, Urs Hengartner, and Florian Kerschbaum. Differentially private learning does not bound membership inference. arXiv preprint arXiv:2010.122 1211000.1111..111 2020.
Bargav Jayaraman, Lingxiao Wang, Katherine Knipmeyer, Quanquan Gu, and David Evans. Revisiting membership inference under realistic assumptions. arXiv preprint orXiv:2005.1088) 2020.
Jinyuan Jia, Ahmed Salem, Michael Backes, Yang Zhang, and Neil Zhenqiang Gong, Memguard: Defending against black-box membership inference attacks via adversarial examples. In Proceedings of the 2019 ACM SIGSAC conference on computer and communicttions security, pp. 259 274, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. International conference on machine learning, pp. 1376-1385. PMLR, 2015.
Saced Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership infer- ence bounds for adaptive composition of sampled gaussian mechanisms. arXiv preprint 2xXi::2204.06166, 2022.
Pratyush Maini, Mohammad Yaghini, and Nicolas Papernot. Dataset inference: Ownership resolution in machine learning. arXiv preprint arXiv:2104. 10706, 2021.
Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky, Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.0 029000 2022.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. IEFE, 2017.
15

---

Published in Transactions on Machine Learning Research (03/2024)
Milad Nasr, Reza. Shokri, and Amir Houmansadr. Machine learning with membership privacy using adversar- ial regularization. In Proceedings of the 2018 ACM SIGSAC conference. on computer and communications security, pp. 634 646, 2018.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White-box black-box: Bayes optimal strategies for membership inference. In International Conference on Machine Learning, pp. 5558 5567. 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 on machine learning models, arXiv preprint Xrxi::1806 800.00146,,, 2018.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithuss for machine unlearning, arXiv preprint arXiv:2103.03272 2021.
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), pp. 3 18. IEEE, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pp. 248-248. TEFE, 2013.
Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. Unrolling sgd: Understanding factors influencing machine unlearning, arXiv preprint arXiv:2109. 1333::9009,,398,, 2021.
Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint Xrx:2:2011, 11660, 2020.
Stacey Truex, Ling Liu, Mehmet Emre Gursoy, Lei Yu, and Wenqi Wei. Demystifying membership inference
atlacks in machine learning service. IEEE Transactions on Services Compuling, 2019.
Larry Wasscrman and Shuheng Zhou, A statistical framework for differential privacy. Journal of the American Slatislical Associalion, 105(489):375 389, 2010.
Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 5093-3106, 2022.
Samuel Yeom, Trene Giacomelli, Matt Fredríkson, and Somesh Jha. Privacy risk in machine learning: Analyz- ing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pp. 268-282. IEEE, 2018
A Further Discussion on The Bound
A.1 Positive Accuracy is not always bounded
Here we present why the failure mode in PP(S(=)) is necessary.
Consider a set of two (scalar) points (21, which are drawn into the training set D with Pa, (1) = and Pz, (1) = 0.5; that is xi is always in the training set, and 22 has a 50% chance of being in the training set. Let model M be single dimensional logistic regression without bias defined (x)) we initialized such that for cross-cntropy loss L, VL ~ 0 (f.e. set 41 = {(10%, 1)} and the weights w 106, so that M(x) = 10 and thus the softmax output of the model is approximately 1 on Ij and thus gradient is approximately 0). Conversely set D2 such that the gradient on it is less than -1 (i.e. for the above setting set x2 = ((109.0) O))).
Now, train the model to (1, 10 DDP following Abadi et al. (2016) with r = 1, sampling rate of 100%, a maximum gradient norm of 1, for one step. Note these are just parameters which we are allowed to change under the DP analysis, and found the noise we would need for (1, 10-DDDP is 4.0412. Then consider
16

---

Published in Transactions on Machine Learning Research (03/2024)
Positive Accuracy Threshold
1.0
0.9
0.8
0.7
6.6
0.5
1000
-75
-50
0
25
75
1.0
Threshold
+166
(a) Positive accuracy function of the thresh-
old
Accuracy vs
0.55
0.51
0.50
-10.0
-7.5
-5.0
-2.
0.0
2,5
5.0
7.5
10.0
Threshold
+1u5
(b) Accuracy function of the threshold
Figure 8: Impact of threshold on positive accuracy and accuracy,
running MI attack on the above setup where if for some threshold a the final weights W are s.t if W S a one classifies those weights as having come from the dataset with T2, otherwise not. Do note that here we use W for the final weights opposed to to emphasize that are now talking about random variable. The intuition for this attack is that if the dataset only contain then the weights do not change, but if the dataset contains 22 we know the resulting gradient is negative (by construction) and thus decreases the weights (before noise).
By the earlier setting on how training datasets are constructed note that D (a1) or = (-1 22), and we will denote these Dj and D2 respectively. Note that if M trained on D2 following the suggested data points and initial weights, denotes the noise needed for (1, (0.10-5--00 maximum gradient norm is set to 1.
have the distribution of final weight WD, WD, N(10 .) N N(10%, 4..412)) where a
stated earlier. Similarly WD, N 1, 4.0441)) since the
For the above MI attack we can then explicitly compute the posilive accuracy as a function of a by:
PPD2IW aa)
P(W D3 S a) P(D22) P(W D. S a) P( D2) P(Ww, aa) P(D,)
W a..aa) 0.5
W Wi a) 0.5 oi (W 0z) 0.5
Note o( ((W a)) is the (Gaussian) cumulative function of random variable W upto a. We plot this in Figure 8al and note how not bounded by anything less than and goes to 1 as the threshold a decreases (i.e. Vm E [0, 1) 3o s.t. S (-00, af yields positive accuracy greater than m).
17

---

Published in Transactions on Machine Learning Research (03/2024)
B Previous Bounds Compared to Our Bounds
In our work we are interested providing bounds on MI that better describe non-DP influences on the effectiveness of an attack. However, to situate our work, we first describe the context prior work derived MI bounds in. Two of the main bounds (Yoo et al. 2018: Erlingsson et al., 2019) focused on an experimental setup first introduced by Yeom et al. (2018). 1. In this setting, an adversary f is given datapoint x' that is 50% likely to have been used to train a model or not. The adversary then either predicts 1 if they think it was used, or O otherwise. Let b 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% baseline of random guessing, or more specifically 2(A(f) - 0.5) where A(f is the accuracy of f.
For such an adversary operating in a setting 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 - when training with e-DP. 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 in a dataset, and from that introduced the DP condition to obtain their MI bound.
Erlingsson et al. (0199) improved on the bound developed by Yeom et al. (0018) h for an adversary operating under the same condition by utilizing a proposition given by Hall al. (2013) on the relation between TPR and FPR for an (EP function. Based on these insights, Erlingsson et al. (2019) bounded the membership advantage by 1 - e= + Se-=. Finally, improving on Erlingsson et al. 2019 by using propositions given by Kairouz et al. 20155), Humphries et al. (2020) bounded the membership advantage by 5"-1+26 This
e++1
translates to an accuracy bound of 426 which is the tightest MI accuracy bound we are aware of. 2(c*+1)
Other work has considered variable sampling rates. For e-DP, Sablayrolles et al. (019)) bounded the proba- bility of a datapoint x" being used in the training set of a model (i.e, , P(x" E Dirain|S) which we will refer to as "positive accuracy") ') by Px- (1)+ + á where Px- (1) is the probability of the datapoint being sampled into the training dataset.
We now discuss how the bounds obtained in this line of work compare to our bound, obtained in Theorem 3.3 For simplicity, let us take ō = 0. Note that the setting described in Section 3.2 is equivalent to the MI
experiment defined by Yeom et al. (2018) when Px, (1) = 0.5 Vx, E {x). ; .xx) J. Moreover, note the
positive accuracy bound in Theorem 3.3 also bounds MI accuracy for (1) = 0.5. This is as setting d = O, Theorem 3.3 gives a bound for cDP algorithms. Note then that by taking Px- (1) = (0) = 0.5, the posilive and negalive accuracy bounds are equal in Theorem 3.3 Therefore, as an adversary must output either a positive or a negative prediction, we have MI accuracy (not positive accuracy or negative accuracy) is bounded by Theorem 3.3 when P (1) = 0.5.
Note the bound we obtain is (1+e = which matches the MI accuracy bound given by Humphries et al. (2020), the previous tightest bound on MI accuracy (see Figure g One of the contributions of our proof is it explicitly demonstrates where the looseness in this bound comes from, i.e. looseness of the DP inequality over all DD) pairs.
Do note our positive accuracy bounds extend to the setting with a biased sampler. We compare our bound with the positive accuracy bound derived by Sablayrolles et al. (2019) in Figure 10 which demonstrates that our bound is indeed tighter.
Concurrent work by Mahloujifar et al. 2022) improved the bound on positive accuracy by Sablayrolles et al. 2019) (also called precision or positive predictive value "when referring specifically to an adversary") to Ite in the case of Fxx (1) = 0.5 and all other data, is fixed. Note eur bound on positive accuracy generalizes to a more general setting than the one Mahloujifar et al. (202) is limited to.
We note that Jayaraman al. 2020 bounded the positive predictive value (cquivalent to precision and positive accuracy) of attacker model trained with (e,6) when the FPR is fixed. Note, that both our work and the previously mentioned bounds are independent FPR. In particular Erlingsson et 2019 followed similar technique to Jayaraman et al. 2020 but were able to drop the FPR term using proposition relating TPR FPR (Hall et 2013).
18

---

Published in Transactions on Machine Learning Research (03/2024)
Different MI Accuracy Bounds
0.9
Accuracy Bound
0.-
0.7
Our Humphries Bound
Erilgsson
Sablayrolles Bound
0.5
0
Easilon
Figure 9: Comparing the upper bound to MI performance we achieved matching Humphries et al. (2020) to
that given by Erlingsson et al. (2019) and Sablayrolles et al. 2019 (note Pxx (1) = 0.5 here). In particular, note we are tighter for all e.
Sablayrolles Pos Accuracy Bound Probability
1.0
0.8
0.6
0.4
Accuracy
Bound: c 0.1
Accuracy Bound: c 1.0
Bound: =
Accuracy
Our Sound: - 2.0
0.0
0.0
0.2
0.4
0.6
6.8
1.0
Probability af drawing
Figure 10: Sablayrolles et al. (2099) upper bound on MI positive accuracy as function of Px (1) compared to our bound. Note that still tighter for all probabilities.
In particular, we now describe how our analysis yields a more relevant (and stronger) approach bounding failure rates when using (c, DD than the (1 11-0) 5) approach used by Mahloujifar et al. (2022)_ Following Eq. 15 in Mahloujilar et al. (2022) which stales the e-DP conditions holds for any fixed (D, D') pair with probability (I (), the bounds in Theorem 3.3 (setting 8 = 0) trivially apply to (E,8)-DP with probability
(1- (1- where N is the number of (D, pairs appearing from the random sampling. Note this N could be quite large, i.e. if n is the number of datapoints in the larger set, N = Σm= ("z") if every point is being randomly sampled. The scenario studied by Mahloujifar al. (2022) bypassos the N dependence by only considering one (D, D') pair, f.e. all the other points in the dataset are fixed and only the datapoint in question is being randomly sampled. This assumption made by Mahloujifa et al. (002)) is not applicable in practice as we do not know which datapoints the adversary is going to test: hence, we would have to resort to randomly sampling all them. Instead, our failure analysis in Section 3.3 (particularly Theorem 3.3) conveniently bypasses this problem by telling us low probability states are what lead to failures (removing the N dependence in the failure rate).
As last remark of how the work of Mahloujifar et al. (022 recall our bound is tight upto the looseness of the DP inequalities holding all adjacent datasets. Hence, any future improvement would have to beyond the DP condition and incorporate the looseness of the DP guarantee on different datasets. This means that our bound is optimal when no such knowledge is provided. Mahloujifar et al. (202)) does just that by studying MI accuracy bounds given by a privacy mechanism, beyond just the (c, 8D- guarantees yields. However it should be noted that MI accuracy, which is what Mahloujifar al. (2022) primarily studies, and MI positive accuracy (what we study) have divergent analyses
be viewed in the context of our result,
in the case of (e, 0) DDP due to failure mode described above (which is not present for accuracy).
19

---

Published in Transactions on Machine Learning Research (03/2024)
C
Additional Figures
20

---

Published in Transactions on Machine Learning Research (03/2024)
cifar10 with == 3.0
cifar10 with == 5.0
cifar10 with = 7.0
1.0
1.0
1.0
0.1
0.1
0.1
Pastive Rate
0.8
0.3
True Positive Rate
0.8
0.3
True Posiivve Rate
0.8
0.3
0.5
0.5
0.5
0.7
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
10
10-2
10-1
10
10
10
10
10
10
10-2
10
10a
Falice Pocciie Rale
Falce Prxitiuu Rabe
Falon Positiue Rate
(a) CIFARIO with 3.0
(b)
CIFARIO with 5.0
(c) CIFAR10 with 7.0
mnist with 3.0
mnist with 5.0
mnist with 7.0
1.0
0.1
1.0
0.1
1.0
0.1
True Positive Rate
0.3
True Positive Rata
0.3
True Positive Rate
0.8
0.3
0.5
0.5
0.5
0.6
0.7
0.6
0,7
0.6
0.7
0.9
0.9
0.9
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
10
10
10
109
10:
10
10
10
10
10
10
109
Falce
Falen
(d) MNIST with 3.0
(e) MNIST with 5.0
(f) MNIST with 7.0
Figure 11: Viewing privacy hypothesis testing Wasserman & Zhou (010)), we present TPR vs. FPR for LiRA attack against MNIST and CIFAR10 for = 3.0, 5.0, 7.0 and 8 10-5, with the dashed line representing TPR = FPR. For each setting, we plotted the attack against target models with sampling rates Px- = 0.1, 0.3, 0.5, see marginal strength low false positive rates.
0.7, 0.9. The results are the average over 5 trials with a 95% confidence interval. We
cifar10 with No DP
mnist with No DP
0.8
Positive Accuracy
0.8
0.6
0.6
Positive
0.2
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Sampling Probability Ps-(1)
Sampling Probability Px-(2)
(a) CIFAR10
(b) MNIST
Figure 12: Positive accuracy the LiRA attack against MNIST and CIFAR10 when training with no privacy guarantees (normal SGD). For each setting, we plotted the attack against target models with sampling rates Px- 0.1, 0.5, 0.9. The results are the average over 5 trials with 95% confidence interval, and the baseline (always predicting positive) is given by the dashed line. We observe that the improvement over the bascline depends on the sampling rate Px.
21

---

Published in Transactions on Machine Learning Research (03/2024)
cifar10 with 3.0
mnist with 3.0
1.0
Sampling 0.1
Sampling 0.1
Positive Accurocy
Sampling 0.3
Positive Accuracy
0.8
Sampling 0.3
Sampling 0.5
Sampling 0.5
Sampling
Sampling
Sampling
Sampling
0.4
baseline
0.4
line
0.2
0.2
0.4
Sampling Probability Pz-(1)
Sampling Probability (x)
(a) CIFAR10
(b) MNIST
Figure 13: Positive accuracy of the LiRA attack against MNIST and CIFAR10 when training with (e 3.0, = 10-P. For each setting, we plotted the attack against target models with sampling rates Px 0.1, 01,,0.0..5,44 0.7, 0.9 when using shadow models trained with varying sampling rales. The results are the average over trials with a 95% confidence interval, and the baseline (always predicting positive) is given by the dashed line. We observe that there is significant difference between the sampling rates, though Px- (1) = 0.5 is average best.
Attack on cifar10
Attack P on mnist
= 1.0
= ==000
== 3.0
Positive Accuracy
==3.0 3.0
0.6 5,0 0.4
g 5.0
Positive
0.4
baseline
baseline
0.2
0.2
0.4
0.6 Sampling Probability P2)
Sampling Probability Px-(1)
(a) CIFAR10
(b) MNIST
Figure 14: Positive accuracy of Attack in Yo et al. 2022) against MNIST and CIFAR10 when training with e 1.0, 3.0, 5.0, 7.0, 9.0, 15.0 and 10-)). We implemented Allack P by using 1000 test points (non training points) to the threshold on the loss ensure FPR of 0.1. For each privacy setting, we plotted the attack against target models with sampling rates Px- 0.3, 0.5, 0.9. The results are the average over 5 trials with 95% confidence interval, and the baseline (always predicting positive) is given by the dashed line. We observe no significant improvement over the baseline with respect to Px*
22

---

Published in Transactions on Machine Learning Research (03/2024)
Attack R cifar10
Attack R on mnist
1.100
Positive Accuracy
0.8
Posttive Accuracy
0.8
=:0.0
= 9.0
c=1.0
2-15.0
baseline
0.4
0.4
0.2
baseline
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Sampling Probability Ps-(1)
Sampling Probability Px-(3)
(a) CIFAR10
(b) MNIST
Figure 15: Positive accuracy of Attack R in Ye et al. (2022) against MNIST and CIFAR10 when training with = 1.0, 3.0, 5.0, 7.0, 9.0, 15.0 and 10-)). We implemented Attack by training 20 shadow models sampling training datapoints with probability 50%, and computing the loss among the shadow models that did sample datapoint to pick a datapoint dependent threshold for the loos ensure a FPR of 0.1. For each privacy selting, plotted the allack against target models with sampling rates Px 0.1, 0.3, 0.5, 0.7, 0.9. The results the average over trials with 95% confidence interval, and the baseline (always predicting positive) is given by the dashed line. We observe significant improvement over the baseline with respect to Px..
23

---

Published in Transactions on Machine Learning Research (03/2024)
Attack cifar10 with Alpha 0.05
Attack cifar10 with Alpha 0.2
Attack R cifar10 with Alpha 0.3
1.0
1.0
1.0
Accuracy
0.8
3.0.0
Positive Accuracy
0.8
3.0
Posiive Accuracy
0.8
=
= 9.0
e 9.0 = 15.0
9.0
= 15.0
0.6
E 15.0
baseline
baseline
baseline
0.4
0.4
0.4
0.2
0.2
0.6
0.8
0.2
0.4
0.8
0.2
0.8
Sampling Probability (3)
Sampling Probability (x)(1)
Sampling Probability Px1(1)
(a) CIFAR10: FPR 0.05
(b) CIFAR10: FPR 0.2
(c) CIFAR10: FPR 0.3
Attack cifar10 with Alpha 0.5
Attack mnist with Alpha 0.05
Attack mnist with Alpha
1.0
3.0
Positive Accuracy
0.8
e= 3.0
Positive Accuracy
0.8
3.0
9.0
9.0 0.4
9.0
0.6
== 15.0
<= 15.0
<= 15.0
Positive
baseline
baseline
0.4
baseline
0.2
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Sampling Probability
Sampling Probability
Sampling Probability
(d) CIFAR10: FPR 0.05
(e) MNIST: FPR 0.05
(I) MNIST: FPR 0.2
Attack on mnist with Alpha 0.3
Attack on mnist with Alpha 0.5
6.100
=-
1.0
Positive Accuracy
Positive Accuracy
0.6
15.0
15.0
0.4
baseline
baseline
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Sampling Probability P.-(1)
Sampling Probability Py-(2)
(g) MNIST: FPR 0.3
(hh MNIST: FPR 0.5
Positive accuracy of Attack R in Ye al. (2022) against MNIST and CIFAR10 following the setup of Figure 15 but with different FPR constraints among the shadow models to pick the threshold. We again see now significant improvement over the baseline.
Figure 16:
Attack on cifar10 with Alpha
Attack on mnist with Alpha 0.1
Positive Accuracy
0.8
7.0
Positive Accuracy
0.8
7.0
baseline
baseline
0.6
0.6
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Sampling Probabiiity (1)
Sampling Probability (2)(3)
(a) CIFAR10
(b) MNIST
Figure 17: Positive accuracy of Attack R in Ye et al. (2022)
against MNIST and CIFAR10 when training
with e = 3.0, 7.0 and d = 10-5), following the setup of Figure 15 except the shadow models sample data at
the same rate as the target model. We observe no significant improvement over the baseline with respect to Px
24


Reviews:
[{"review_id": "eoO4BNum2a", "reviewer": "Reviewer_vVhg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of improving the DP bound by considering non-DP factors is interesting. Although the analysis focuses primarily on some specific form of attacks, membership inference can be considered a basic form of privacy attacks, so such analysis is of general interest in the privacy community. \n\nHowever, I still have some concerns.\n\ni) From Figure 3 I cannot observe what the author has claimed \"Sampling is dominant factor dictating how much the LiRA attack outperforms the baseline attack\". All the lines appear parallel to the line of the baseline.\n\niii) From Figure 5 and 6, networks basically collapse for high sampling probability. Does this also suggests the derived bound is still very loose?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work derives a bound on the success rate of membership inference attack. The derived bound is claimed to be tighter than the DP bound due to capturing non-DP factors. Additionally, analysis suggests that training on less data can yield more advantageous trade-offs between privacy and utility.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can the authors discuss why their analysis and experiment rely on DP? Especially, it is important to know whether the improvement only exists for DP networks.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vcusPJckzr", "reviewer": "Reviewer_KveU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nStudying how prior knowledge of samples inclusion in the training data set affects membership inference attacks is certainly an interesting one from both theoretical and practical aspects of private machine learning. \n\nThe main result of the paper seems to be, that if you subsample your data set prior to the training then the models learned under DP are less susceptible to MI attacks the smaller this subsampling fraction is. Authors demonstrate that this effect is stronger than the MIA reducing effect of DP. This result is highly intuitive, as if a sample is never even used in training, then obviously it should not be susceptible to membership inference. \n\nWhat is really interesting in this paper is the empirical result that the models performance (i.e. accuracy) is not negatively affected by the smaller training data set. The experiments seem to suggest that there is a \"sweet spot\" in training set subsampling that for a bounded MIA performance and models accuracy, and that this sweet spot is clearly below 1 (the standard practice of using the entire training data set in training).\n\n## Weaknesses\nThe term $\\mathbb{P}(S \\mid x^*)$ in Thm 3.3. is not clear to me. First, I would imagine this term is affected by the privacy guarantee because DP obviously has an effect on the learning methods output distribution. Second, how have you estimated this term in the bounds of Fig 1? I tried looking at the code in the supplementary material but didn't find the script to produce these plots.\n\nI find the positive accuracy, used as a metric throughout the paper, a bit misleading or at least bit incomplete metric. I do understand that small positive accuracy does imply low MI success, however when it is used to diagnose the MI performance with varying $P_{x^*}(1)$ it might have some shortcomings. For example, consider Figure 3. This figure demonstrates that with low sample rate ($P_{x^*}(1)$ is small), the positive accuracy becomes small. More importantly, the change in $P_{x^*}(1)$ has a significantly larger to the positive accuracy than the privacy level $\\epsilon$ of DP has. However, this metric is now highly dependent on the strength of the LiRA attack. If the LiRA classifier is unable to learn to distinguish the in/out settings, then the probability of LiRA score exceeding a certain threshold is independent of the in/out status. Now, this means that the number of samples LiRA labels as positive is approximately $N \\Pr(s_i > \\gamma)$, where $s_i$ is the score for sample $i$ and $\\gamma$ is the decision threshold, and if the classifier does not distinguish in/out then $\\Pr(s_i > \\gamma) = \\Pr(s_i > \\gamma \\mid x_i \\in D) = \\Pr(s_i > \\gamma \\mid x_i \\notin D)$. Similarly we have that the number of true positives is approximately $N_{pos} \\Pr(s_i > \\gamma)$, and since $N_{pos} = N P_{x^*}(1)$, we have that true positives / predicted positives is $TP/PP = P_{x^*}(1)$. While it seems that the LiRA classifier used in Fig. 3 is not quite a random classifier (it is somewhat above the diagonal line), it would be really interesting and important to see how powerful this classifier actually is in order to evaluate the difference the $P_{x^*}(1)$ makes. For example in Carlini et al. 2022, the LiRA attack applied on DP models behaved almost like a random classifier even with very moderate noise levels. One interesting question is how would the training data subsampling perform in MIA attacks against non-private models, for which the MIA actually has a high performance.\n\nI would also be quite curious to see how the number of samples used in training affects the MIA performance. In training of shadow models, you have used 50% in/out sets similar to Carlini et al. 2022. However, in your target model, you use training set that might differ in size quite significantly. Would this then affect the MIA performance as the target models could come from quite different distribution compared to the shadow models? \n\nFor now, I will set the Claims and Evidence to \"No\" because of my concerns relating to the positive accuracy as a metric. However, I'm happy to change this if authors can provide include further metrics on the performance of MIA. \n\nReferences:\nNicholas Carlini, et al., Membership inference attacks from first principles, 2022\n\n## Minor comments/suggestions\n- I believe your supplement material is missing some of the plotting scripts, e.g. the one responsible for Fig 1. Moreover, it seems that the plotting script for Fig 3 is bit different to the one actually used in paper (the labels are lower case in attached .py file whereas in the paper the labels are title-case).\n- Lemma 3.2: I think you need to assume that D and D' are adjacent (which is done in the proof). Or are you saying that _any_ bijective corresponcence between $D$ and $D'$ would be enough?\n- In the proof for Thm 3.3, immediately after \" we have the denominator is\", are you missing $\\Pr(H(D) \\in S)$ from the first summand?\n- \"This will have explained\", a typo?\n- In Def 3.1., you have used $\\mathbb{P}(x^* \\in D \\mid S)$ do denote the positive prob, but afterwards you use $\\mathbb{P}(x^* \\mid S)$. I just want to verify that these are the same. If so, it might make sense to add a brief statement after the definition that you will use this notation for the rest of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the membership inference attacks (MIA) against machine learning models, where the training data has been subsampled prior to the training. The main discovery of the paper is that this procedure can significantly lower the MIAs success probability compared to the case where we use all the training data. Moreover, authors present theoretical bounds for the MIA success probability, and show that differential privacy (DP) has smaller effect to these bounds than the subsampling (or equivalently the prior knowledge on target datapoints inclusion in the training data set). Empirical results demonstrate that the positive accuracy of MIA, i.e. probability that MIA correctly classifies target as a member based learned results, decreases significantly when the training data set is subsampled to a smaller set prior to training. \n\nAuthors also connect their theoretical results to machine unlearning. The idea is that for a machine unlearning task, curator needs to remove samples from the training data and re-train the model in order to avoid sample being distinguished from the learning outcome. Authors connect this to the probabilistic upper bound for MIAs success. From this bound, authors can derive an upper bound for number of samples the curator can avoid \"unlearning\" from the model if using the subsampled training data to begin with.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Better diagnostics of the MIA performance. For example, you could add a FPR vs. TPR plots on several different levels of $P_{x^*}(1)$\n2. Test how the sampling ratio affects the shadow models. For example you could train a set of shadow models with 10% in 90% out, and see if it has any effect on MIA performance when testing against the $P_{x^*}=0.1$ setting.\n3. Explain how $\\mathbb{P}(S \\mid x^*)$ is computed.\n\n#### After rebuttal\nI'm happy with the changes provided by the authors, and have now changed \"Claims and Evidence\" to \"Yes\".", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AZrM5bVFCP", "reviewer": "Reviewer_yek7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-motivated, aiming at a very important question in ML privacy research today. \n- The proposed bound reveals the relationship between DP and MI accuracy, which is novel and significant to understand the connection between these two concepts. \n- The discovery that subsampling can amplify privacy is very interesting and surprising finding, and experiments on various datasets have validated this idea for the LiRA MI attack.\n- There is a very excellent, theoretically grounded connection to deletion, reconstruction, and generalization in Section 5.\n\n Weaknesses:\n- The second paragraph of Section 4.1 is a bit confusing to me. I hope the authors could explain the approach a bit further in this paragraph. What is the relationship between $D$ and $D_{\\mathrm{train}}$ in this context? Is $T$ a independent or dependent with $x$? \n- It is unclear what \"model utility\" means in this article.\n- There lack experiments on more recent SOTA MI attacks such as \"Enhanced membership inference attacks against machine learning models\" by J. Ye et al, etc.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This article presents an upper bound on the MI accuracy when the model is DP-trained. \n- This article discovers that sabsampling the training set can amplify the privacy and reduce MI accuracies. \n- This article draws connections between the proposed bound and a few other important concepts including data deletion, reconstruction, and generalization bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Refine the writing in Section 4.1 and make it easier to understand.\n- Make clear definition of what \"model utility\" means. \n- Experiment with more recent MI attacks and conclude if the same phenomenon can be observed.", "broader_impact_concerns": "It would be nice to have a short discussion on what people should take care of when they use MI attacks in practice (for example, to obey legal restrictions or to go to court) given the discovery of this article.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: ## Mathematical Notations:

1. There should be a section about the mathematical notations being used.  This is especially important because some of the notations are not clear and unconventional.  For example, in Definition 3.1 the notation of $\mathbb{P}(x^*\in D | S)$ is used. This typically means a conditional distribution given the event S, where x^* is the random variable.  But to my understanding, in Section 3.1 it means something very different --- it means the probability of an unspecified randomized learning algorithm outputting a model inside S, where S is the set of models determined by a fixed deterministic MI attacker, a fixed dataset $D$ and a fixed target $x^*$.    Specifically, my understanding is that $S = \{ model | MI(x^*, model) = 1 \}$.  For that reason, the standard notation for the MI positive accuracy would be $\mathbb{P}(M([D,x^*]) \in S)$ for a randomized training algorithm M.  Or more directly $\mathbb{P}(MI(x^*, M([D,x^*])) = 1)$ and then specifies that the randomness is only over the randomness of M.


2. It is a bit unclear whether Definition 3.1 is stated for a fixed D or needs to be a bound that applies for any D that includes $x^*$... in the Comment 1 above, I assumed a fixed D that does not include $x^*$ and constructed a particular neighbor dataset $[D,x^*]$.



3. Similarly, the $\mathbb{P}\_{x^*}(0)$ and $\mathbb{P}\_{x^*}(1)$ notations are also a bit awkward too.  The subscript usually denotes the probability distribution and inside the brackets, it is usually the Event.  It is unclear whether it is the probability mass function or the distribution function these notations are about. 




## About the first claim:

4. The authors discussed the connection TPR-FPR tradeoff function by citing Kairouz, Oh and Viswanath. It is perhaps better to also cite the origin of this idea Wasserman and Zhou https://arxiv.org/abs/0811.2501, as well as how the mechanism-specific variant known as f-DP from Dong, Roth and Su https://arxiv.org/abs/1905.02383 could be used to improve the bounds.  Specifically, the authors used generic DP definition for their analysis, but DP-SGD satisfies RDP and f-DP, which implies stronger protection against membership inference.


5. The authors should verify that their Theorem 3.3 is not already implied by Theorem 4.2 and Corollary 4.3 from Dong, Roth and Su https://arxiv.org/abs/1905.02383.   Note that Type I error = 1 - Positive accuracy  and Type II error =  1- Negative accuracy.



## Now about the second claim:

6. So there are two sampling procedures in this paper. The first, is the poisson sampling of the minibatches within DP-SGD. The second is another poisson sampling (deccribed in the lasts paragraph of Section 3.2 before Lemma 3.2 that happens before the data is passed into DP-SGD.  I am curious that in the experiments (e.g., the $\epsilon$ in the legends of Figure 1 and Figure 3), has the reported DP parameter \epsilon taken advantage of the amplification by sampling that happened at the beginning?

7. In Figure 1 for example, it makes sense to alsso include the Pos Acc bound directly implied by the DP guarantee of the mechanism.
Decision: Accept (poster)