Optimal Membership Inference Bounds for Adaptive Composition of Sampled Gaussian Mechanisms
Authors: Saeed Mahloujifar
Alexandre Sablayrolles
Graham Cormode
Somesh Jha
Venue: Submitted to ICLR 2023 (2023)
Keywords: Membership inference
DP-SGD
Gaussian Mechanism

Abstract: Given a trained model and a data sample, membership-inference (MI) attacks predict whether the sample was in the model’s training set. A common counter- measure against MI attacks is to utilize differential privacy (DP) during model training to mask the presence of individual examples. While this use of DP is a principled approach to limit the efficacy of MI attacks, there is a gap between the bounds provided by DP and the empirical performance of MI attacks. In this paper, we derive bounds for the advantage of an adversary mounting a MI attack, and demonstrate tightness for the widely-used Gaussian mechanism. Our analysis answers an open problem in the field of differential privacy, namely the fact that membership inference is not 100% successful even for relatively high budgets ($\epsilon> 10$). Finally, using our analysis, we provide MI metrics for models trained on CIFAR10 dataset. To the best of our knowledge, our analysis provides the state-of-the-art membership inference bounds.

Under review as a conference paper at ICLR 2023
OPTIMAL MEMBERSHIP INFERENCE BOUNDS FOR ADAPTIVE COMPOSITION OF SAMPLED GAUSSIAN MECHANISMS
Anonymous authors Paper under double-blind review
ABSTRACT
Given a trained model and a data sample, membershiip-infeeeeee (MI) attacks predict whether the sample was in the model's training set. A common counter- measure against MI attacks is to utilize differential privacy (DP) during model training mask the presence of individual examples. While this use of DP is principled approach to limit the efficacy of MI attacks, there is gap between the bounds provided by DP and the empirical performance of MI attacks. In this paper, we derive bounds for the advantage of an adversary mounting MI attack, and demonstrate tightness for the widely-used Gaussian mechanism. Our analysis answers an open problem in the field of differential privacy, namely the fact that membership inference is not 100% successful even for relatively high budgets provide MI metries for models trained
(e 10). Finally, using analysis, on CIFAR10 dataset. To the best of our knowledge, our analysis provides the state-of of-the-art membership inference bounds.
INTRODUCTION
The recent success of machine learning models makes them the go-to approach to solve a variety of problems, ranging from computer vision (Krizhevsky al. 2012) to NLP (Sutskever et al.] 2014), including applications to sensitive data such as health records or chatbots. Access to trained machine learning model, be white-box published model through a black-box API, can leak traces of information (Dwork et al., 2015) from the training data. Researchers have tried to measure this information leakage through metrics such as membership inference (Shokri et al.) 2017). Membership inference is the task of guessing, from a trained model, whether it includes given sample or not. This task interesting in its own right, as the participation of an individual in data collection can be sensitive information. Furthermore, it also serves as the "most significant bit" of information: if membership inference fails, attacks revealing more information such as reconstruction attacks (Fredrikson et al. 2014; Carlini et al. 2020) will also fail. In other words, defending against membership inference attacks also defends against more advanced attacks.
The standard approach to provably defeat these membership privacy attacks is differential pri- vacy (Dwork et al. 2006). The traditional variant of differential privacy defines a class of algorithms that apply on a database D and respect privacy budget and a probability of failure 4" These pa- rameters control the divergence between the distribution of outcome of the algorithm when applied on two "neighboring" databases that only differ in one location. In particular, our mechanism of interest, the Sampled Gaussian Mechanism (SGM), makes an arbitrary function f X + I2d differentially private by first sub-sampling a database of smaller size from the original database, using Poisson sam- pling, and then calculating f on the sub-sampled database, and finally adding Gaussian noise to the outcome. Increasing the amount of injected noise provides stronger privacy guarantees, and enables to trade off between privacy and utility of the trained model. To measure the privacy of a given algo- rithm, researchers have developed advanced mathematical tools and notions such as Renyi differential privacy (Mironov] 2017 Abadi et al. 2016) and advanced composition theorems (Dwork et al. 2010) Kairouz et al. 2015). These tools allow us to calculate (e, 6) values for carefully designed algorithms.
While intuitive, describing 5 the probability of failure mathematically inaccurate Meiser 2018

---

Under review as a conference paper at ICLR 2023
29.93
6.97
3.92
1:13
0.68
3.10
0.98
0.74
0.45
0.37
1.0
1,0
Humph
Hunghrins ei
Ours (Pirskrt
Ours (Hisker)
0.8
Emplriica
0.6
Empllical
Dur bound
Our bound
0.6
0.6
0.4
0.4-
0.0
0.0
EM 5
<M
(a) Without subsampling (q = 1)
(b) With subsampling (g = 0.01)
Our spoet bound ucppr bound
0.0004
0,0003
TiV pi0atir
2.6
Tie pooliive
0.0002
0.001
Our upper bound BP upper hound
0.000
00
02
0.1
066
0.7
0.9
L0
Ealoe
Fafor pootiiu
10-3
(c) False positive vs true positive rate
(d) FP v.s. TP for small FP rates
Comparison of advantage bounds in a Gaussian setup. We run the sampled Gaussian Mechanism in one dimension with 50 epochs, and either no subsampling (a) or subsampling with q 0.01 (b). Our attack compares likelihood of the observations under both hypothesis, and chooses the most likely (see Appendix [.T for details). We compute the empirical advantage by measuring the percentage of time p the adversary guesses membership correctly, and report 2p 1. In two bottom figures (c and d) we compare upper bounds for true positive rate obtained from differential privacy analysis versus our direct analysis (Details are provided in Appendix
Figure 1:
Previous work has shown that any differentially private algorithm will provably bound the accuracy of any membership inference adversary. Specifically. Yeom et al. (2018). Humphries et al. (2020), and Thudi et al. (2022) prove that any model trained with (c, 8) differential privacy will induce an upper bound on the accuracy of membership inference. These upper bounds help practitioners calibrate the privacy budget e to defeat the adversary. As can be seen in Figure [ there is a large gap between the best existing upper bound and the performance of empirical attacks. In this work, we use new proof technique to bypass DP analysis and directly bound the advantage of MI attacks, and close the gap between theoretical guarantees and empirical performance.
The most widely-used DP algorithm in machine learning applications is DP-SGD: it is small change of the classical stochastic gradient descent algorithm that only requires clip per-sample gradients, average them and add Gaussian noise. Each iteration of DP-SGD is an instance of the sampled Gaussian mechanism, which chooses fraction g of dataset and outputs noisy sum of the desired quantity. DP-SGD has been shown to be more accurate than other differentially private training algorithms in the case of linear and convex models (van der Maaten and Hannun 2020). Our analysis mirrors the recent shift in the field of empirical membership inference, from advantage (or accuracy) metrics (Shokri et al. 2017 Yeom et al.. 2018, Sablayrolles et a 2019) to precision/recall (true positive/false positive) measures (Watson et al. 2022] Carlini al. (020). Our result shows that no single parameter (either e or membership inference advantage) can explain the performance of adversaries in different settings. in other words, the same value for can lead to significantly different membership inference advantages and vice versa. As shown in Figure 1.c and l.d, this phenomenon holds for the entire precision/recall curve; the precision of adversary all given recall values cannot be explained only with a or advantage parameter.
Our contributions in this work are as follows:
2

---

Under review as a conference paper at ICLR 2023
Our main theorem in Section 4 bounds the membership inference advantage of any adversary for the composition am arbitrary set of sampled Gaussian mechanisms that could adaptively depend each other. This bound is optimal as it reflects the membership inference advantage for real adversary on a particular series of Gaussian mechanisms, Additionally, extend bounds the where the prior knowledge of adversary is non-uniform (Appendix J. We also provide upper bounds on the true positive rate for any given false positive rate (Appendix A
We propose numerical way to calculate the total variation distance (and generalization of it) between mixtures of Gaussians (Section 4.T). Our algorithm is computationally tractable, works in linear time with respect to the number of mechanisms and is independent from the dimension. We use our numerical approach obtain concrete bounds for Gaussian mechanisms and compare our bounds to that of Humphries et al. (2020). We also use this algorithm to calculate upper bounds on true positive rate of adversary.
Finally, to understand the practical implication of our bound for mainstream datasets, we use DP-SGD to train models on CIFAR 10 and MNIST and calculate the membership inference bounds using our techniques. Our approach allows to achieve state-of-the-art provable membership inference privacy for any given accuracy.
BACKGROUND
In this section, we briefly recall the main properties of KL divergence and total variation (TV), as well as differential privacy and membership inference.
2.1 TOTAL VARIATION, KL DIVERGENCE, AND PINSKER INEQUALITY
We consider random variable X (resp. Y) with probability distribution (resp. 1/) over measurable space 12. With a slight abuse of notation, consider quantities as function of either the random variables X, Y or their probability distributions μ, v. Here we recall the definition of total variation (TV) distance and Kullback-Leibhe (KL) divergence:
dp dv
(V(X, = sup Pr[X E A]
Pr(Y E A), XL(XIYY) log
du.
(1)
Post-processing.
Given a function g applying g to X and Y can only decrease TV.
(V(g(X). - TV.
In particular, if is bijective transform, we have (V TV(
Pinsker's Inequality. For any two random variables and Y. Pinsker 1964 inequality states
TV(X,Y) < KL(X | Y)
2
2.2 DIFFERENTIAL PRIVACY AND THE GAUSSIAN MECHANISM
Differential privacy. A randomized algorithm M satisfies (c, 6) -iifferreni privacy if, for any two datasets 1 and D' that differ in most sample, and any subset R of the output space, we have:
Pr(M(D) R) S exp(e) Pr(M(D') e R) +
(3)
While the probability of failure is often chosen to be inversely proportional to the number of samples, there no clear consensus the literature over desirable values
2 After submission of this work we realized (thanks to Anonymous reviewers of ICLR 3) that Theorem 4.2 in Dong et al. (2019) and its refinements in 7hu al. (2022) implies our Theorem 6 However, since our proof technique different, and perhaps simpler, still keep our proof in the paper.
3

---

Under review as a conference paper at ICLR 2023
DP-SGD with the subsampled Gaussian mechanism. DP-SGD ( Song al. 2013) is a modifi- cation of Stochastic Gradient Descent that makes it differentially private. The core mechanism behind it is the subsampled Gaussian mechanism. Given a function 6 that operates sets S with sensitivity 1 (i.e. ([x(5)) ((S')l2 I 1), the subsampled Gaussian mechanism selects sets S at random and adds noise the output of Φ Note that the mechanism is differentially private if all intermediate steps of the training process are revealed.
2.3 MEMBERSHIP INFERENCE ATTACKS
Membership Inference is the task of predicting whether a given sample was in the training set of a given model. Homer et al. (2008) showed the first proof of concept, and(Sh al. (2017) showed that a wide variety of machine learning models are vulnerable to such attacks. (Shokri et al. (2017) train neural networks attack machine learning models, and measure the success of the attack by the percentage of correctly predicted (train/test) samples, equivalently the advantage Yeom et al. 2018). Later work showed that simple heuristics such as the loss (Yeom et al.] 2018 Sablayrolles et al. 2019 Choquette-Chai
et al. (02TT) provide more accurate and robust measure of membership inference. Membership inference attacks have also been used as an evaluation mechanism for
differentially private mechanisms (Jayaraman et al.
2020
Jayaraman and Evans 2019).
Recent works (Watson al., 2022 Carlimi al.) 2021 Rezaei and Liu 2021 have proposed to evaluate membership inference by the precision/recal trade-off (Watson et al. 2022) or the precision at low levels of recall (Carlini et al. (02T). In particular, such works show that some setups which were thought to be private because the membership accuracy is significantly less than 100% can actually reveal membership of a small group of samples with very high precision. There is also a line of work developed to design algorithms to specifically defend against membership inference attacks (Nasr et al. 2018 Jia et al. 2019] Tang et al., (202). While these works offer no theoretical guarantees against attackers, the empirical defenses achieve better utility at the same membership advantage than their differentially private equivalents. Finally, membership inference has been studied in the context of differential identifiability (Bernau et 2021] Lee and Clifton 2012) (see Appendix F.I for Gaussian experiments that correspond to differential identifiability techniques).
3
MEMBERSHIP INFERENCE AND TOTAL VARIATION
In this section, we define our security game for membership inference and show its connection to the notion of total variation distance (or statistical distance) between probability distributions.
3.1 SECURITY GAME
We adopt the classical assumptions of membership inference (Yeom et al. 2018 Sablayrolles et al., 2019 Humphries et al. 2020). In particular, we assume that the datasets differ by adding/removing one element. We define a security game between an Adversary (who wants to guess training set membership) and Challenger (who wants to hide training set membership).
1. Adversary picks datasets D {.,,..,, } and data point z'
2. Challenger samples bit b uniformly random and creates
D' D'= { (
if
D
if 0
3. Challenger runs the learning algorithm L on D' train a model and sends a transcript of training to the adversary
4. Adversary observes 0 and guesses a bit 8'. Adversary wins if b' b.
We define the advantage of adversary on learning algorithm I as Adv (L, A) = = 2- Pr(bb b'] We also use Adv(L) s Adv(A,L) to denote the advantage of the worst-case adversary against L.
"The transcript only include the final model more information like the intermediate steps of training.
4

---

Under review as a conference paper at ICLR 2023
Remark 1 (Comparing with security game of Yeom al. (0188). The security game of Yeom et al. (2018) for membership inference attacks (See Appendix H is slightly weaker than ours. This means that the upper bounds we prove in this work also apply the security game of Yeom et al. (2018). A curious reader might question if our security game is too strong; the worsl-case advantage of adversary might be lower in the security game of Yeom et al. (2018). In Appendix ( answer this question negatively. Through experiments, we show that we cannot prove better upper bounds in the alternative security game of Yeom al. (2018), even if we assume the adversary does not control the neig neighboring datasets and only sees the final model (and not the intermediate steps). This shows that our bounds in Section Mare tight even the weaker security games.
Remark 2 (Non-uniform prior). One can define a similar security game where the selection of the bit b is non-uniform. This security game captures settings that the adversary has some prior knowledge about the inclusion of the example in the training set. This setting
studied by (Thudi et al. (2022) who provide some upper bounds for the advantage of the adversary in such a security game. In Appendix we show that we can extend our analysis to this setting and provide optimal bounds.
Comparison to existing bounds. In the reminder of the paper we bound the membership inference advantage for DP-SGD. We first recall the best existing upper bound that is proved and improved in prior work (Jayarmann et al.) 2020 layaraman and Evans 2019 Humphries et al. 2020: Yeom et al.
2018 Thudi et al. al.a] (022))
Theorem 3 (Humphries et al. (220 ). For any (c, 6D algorithm L we have Adv(L)
e" e'- 1-+26
e1+1
Note that Theorem B applies to any DP algorithm and hence covers DP-SGD as well. Because of its generality, the bound is loose for DP-SGD (see Figure ((a)). To improve on this bound, we perform a direct analysis of the advantage instead of using the DP tools and then converting to advantage.
Advantage. Let us first mathematically characterize the notion of advantage for a general learning algorithm. For fixed learning algorithm and fixed neighboring datasets, let us define X := 0 (b = 0) and Y := 0 | (b 1) to be the distributions of the output of the learning algorithm for two cases of the security game.
deterministic adversary defines a region A and predicts that is sampled from if A E A and from v if 0 A. We use μ(A) and v(A) to denote Pr[X E A] and Pr|Y E A]. For such an adversary we have
Adv(L. A) Pr[X E A Prly E A
-((A -(A).
Note that with a simple averaging argument we can show that the best adversarial strategy in membership security game is a deterministic strategy. Therefore, the advantage for the learning algorithm I. is then defined as
Adv(L) sup ((A) =(A)
A
where TV is the total variation distance. Total variation distance thus gives us an upper bound on the advantage of any adversary. Since we do not know the exact density function for X and Y it is not clear how to calculate or approximate the total variation distance in general. In the next subscction we discuss how Pinsker's inequality upper bounds total variation distance.
3.2 BOUNDING MEMBERSHIP INFERENCE USING PINSKER'S INEQUALITY
Using Equation 44) and directly applying Pinsker's 's inequality 2 we have:
Adv(T)) < TV) KL(X IlY lim
Dx Y)
(5)
where D. is the Rényi divergence at a. This bound enables to use Rényi divergence, which is rou- tinely calculated DP-SGD (Mironov) (017)) to obtain numerical upper bounds on the membership inference advantage of any adversary against adaptive composition of sampled Gaussian mechanisms.
To this end, we use RDP accounting to calculate the D. for an a > 1. We know that for any a > 1, D& Y) is greater than KL(X || Y) because Da is increasing in This means that for any > 1 D2 will be a valid upper bound on the membership inference ad advantage and the bound becomes better as we decrease o.
5

---

Under review as a conference paper at ICLR 2023
In our evaluation (see Figures 3(a) and | use this formulation to caleulate numerical upper bounds for membership inference for DP-SGD using typical parameters. We refer to this bound as the Pinsker bound. The figure shows that it obtains better numerical values compared to the bound of Humphries eet al. (2020). However, there are two main limitations with Pinsker's bound: 1) The bound is not tight. 2) It is vacuous in cases where KL((X || Y) > 2. In next section, we will optimally bound the membership inference for composition of adaptive and sampled Gaussian mechanisms.
4 OPTIMAL BOUNDS FOR COMPOSITION OF SAMPLED GAUSSIAN MECHANISMS
In this section, we show a tighter upper-bound for the adversary's 's advantage. In particular, we will upper-bound the total variation between the transcripts of the (subsampled) Gaussian mechanism, specifically the noisy gradients produced by the DP-SGD algorithm (Theorem[o)
As the first step of calculating our optimal bounds, we show that the adaptivity of Gaussian mecha- nisms does not increase the membership advantage. In other words, for clipping threshold DP-SGD with clipping threshold r. the entire process of DP-SGD can be replaced by a process where each step replaced by either (00 o²) or N or), for the basic Gaussian mechanism, and replaced by either (00, o²) or (1 - (0, o²) + qN(r,o* for the sampled Gaussian mechanism, without decreasing the total variation distance. Our analysis relies on modified version of TV, that denote by TV..
Definition 4. For a > define TV TVa(X, = Sq (u(x) a v(x)(dz dz where and v are the probability density functions for X and Y respectively.
While we do not know an explicit form of the TV, divergence between Gaussians, we can still prove that it increases with ||uj u2l12, as formalized in the following lemma.
Lemma 5. Let X _Niu,, o². Ia) and Y = NN(u,, o² Ia). Then, for any R TV, Y) is only a function of [|u u2lle and o². Moreover this function is monotonically increasing with respect to |Iu u2lle That is, for any a 2 ||u] 22ll2 we have
TVo(X, Y) S TVo(N(0, (O)
The proof involves some careful but standard gradient calculations and is deferred to Appendix
Now we focus on stating upper bound on the membership inference advantage of an adversary on composition of Gaussian mechanisms. But before that, we state some useful notations. Notation. We use 0 = (#1..... ,T) ) to denote the transcript of the learning algorithm L that consists of T adaptive steps. We use $ce to denote the first steps of the transcript of the random process. We use S, to denote the union of the support set of the ith step of the mechanism M on all possible datasets. That is S; = {& 3D, 8 E Supp M )-))) We also define Sey S1 x K..,,,, S₁. We use B()) to denote Bernoulli random variable that is equal to 1 with probability 9 and 0 with probability Or (or 17) to denote the vector of dimension I' that is 0 (or 1) in each coordinate. We use B(g)" to denote an n dimensional random variable where each coordinate is independent and distributed as B(q). For r E R. we use r B(g)" to denote the random variable that is sampled by the following process: first sample from B(q)" "h and then multiply by r. We also use ((rr "(g"(""" "a""""""" o²) to denote an dimensional random variable that is distributed according to a mixture of Gaussians which all have standard deviation a and centers are chosen at random from r B(g)".
q. We use
Theorem 6 (Gaussian Composition with sub- -ub-sampling). Let Mi...., MM be series of adaptive Gaussian Mechanisms with L2 sensitivity r and Gaussian noise with standard deviation a and sub-sampling rate q. The membership inference risk of the composition of M; 's is at most
TV ,a))
(g))"o²²)
Proof sketch. We first prove the proof for the case that there is no sub-sampling. Let MD) be the mechanism that works on D (resp. D') and consists of i Gaussians (0, o2) (resp. o2),a")) steps followed by T - steps of SGM applied to (resp. D').
Specifically, the mechanism M corresponds SGM, and MT to pure Gaussians. We will show in this proof that
TV (V' M' < (D),
(6)
*This notion is also used by the name of Hockey stick divergence Balle al. 2018).

---

Under review as a conference paper at ICLR 2023
and hence
TV(X,) TV(M(D) M) & (D)) (T oI
To this end, we will first argue that the very final step of the mechanism M' can be replaced with Gaussian step without increasing the total variation distance. Then we can move this noise to the start of the process without affecting the result, obtaining M
Let us fix a step and let s = ($1..... $1) be a transcript. Denoting X ~ (D) and Y ~ M (D)), have (In the following, use Σ instead of integral for better clarity and the steps be replace with integral.)
(DV(M
Σ sCrESeT
Pr[X sgr] Pr|Y sgrll
Σ
Σ
Pr[X = =8r] - Pr(y = sgTll
E #7
Σ
Σ
Pr ST 185T-1] -ii-i--Pr(X-0 Pr|XsT-111 SST-1]
8gT-1E5 E7
-Pr[Yr = ST $ | SgT-
E
1 = 8gr-1 Σ
Pr[XT = 8T 8gT-1)
8ST-1ESeT-1
*rEST
Pr|YT = ST 1 Pr|Yer-1=
(7)
Pr(XgT-1=88
We know that the last (h" step of (D) (resp. (D)) has two isotropic Gaussian distributions centered around two points #1 and u2 such that ||u] - S r and with standard deviation a. These centers could be chosen adaptively according to the history of the mechanism. We use a($gT-1) to
denote P=1 -=( By Lemma we have
Σ
Pr[X7 ST [8gT-1] Pr[Yr = ST (IsT-1J((SSTD)))
ex ET
2TV (l0
Denoting by A the mechanism that coincides with M for the first T steps and replaced by Gaussian at the last (T"t step, we thus have, by following Equation in the reverse direction 2TV (D),
2TV (D)).
Given that the last step of N does depend on the first steps, we can permute to put it in first position.
Now, we focus on the proof of the case we have sub-sampling. We defer the full proof of Theorem to the Appendix E However, we provide a high level idea behind the proof based on the proof of the case where there is no sub-sampling. The first step is to characterize the TV,, for sub-sampled mechanisms and relate it to the TV, for the case without sab-sampling.
Lemma 7. Let X' (1 q) Y q- X. Then we have TV (X', (X',) Y) = TV atg (X,Y).
The proof of this lemma is provided in Appendix L Now we use Lemma 7 to convert TV, of the sub-sampled Gaussians TV, of Gaussians and Lemma 5 upper bound them with TV. of independent Gaussians. Then we use Lemma 7 Jggain to convert the independent Gaussians to independent sub-sampled Gaussians.
Optimality of our bound. We note that the bound of Theorem is optimal. This is because the bound equal to the advantage of an adversary defined on sequence of independent Gaussian mechanisms. However, one might wonder if our bound is tight in the context of classification with DP-SGD. Appendix H we consider this question and show a learning problem for which our bound is tight. We empiricllly verify that advantage the adversary Additionally, we show that for this learning task, an adversary who only observe the final model can also get very close upper bounds.
get close to our upper bounds.
7

---

Under review as a conference paper at ICLR 2023
Varying noise levels Theorem could be simply extended to composition of Gaussian mechanisms with varying noise levels, assuming the noise levels are not selected adaptively. We leave the composition of Gaussians with adaptive noise selection open question.
Extending to other monotone mechanisms. Although Theorem is stated only for Gaussian mechanism, the theorem extends to any mechanism that satisfies monotonicity under TV, according to some notion of sensitivity. For example, if one can show that TV (C00, σ), [(u, σ)) is monotoni- cally increasing with respect to some norm of u, then Theorem 6 extends to composition of Laplace mechanisms with bounded sensitivity according to that norm.
4.1
MONTE CARLO COMPUTATION
In order to numerically approximate the upper- bound, we write the total variation as
TV(X, Y) = Ja (du(t) du(()) (du(t) s du(())
(9)
= / (1-
(1-du(() (1-du(t) du(t)
) (du(t) S dp(t)) du(t)
(10)
du(l)
= Enmp (11- --((((t) du(t)) (dv(t) - du(t))
(11)
The expectation is over the distribution 14, so we can sample a dataset from f and approximate this expectation using empirical averaging (or Monte-Carke sampling):
TV(XY))
ap(tt) 1 (dv(t)) S dp(t)),
dolta))
(12)
where f; Midd μ.. The Monte-Care estimation of this quantity is very accurate, as it is bounded between 0 and Figures ((a) and show the upper bound using this Monte-Carle simulation for typical settings in DP-SGD. We also provide a detailed algorithm on how we this in Appendix D Following we provide proposition on the accuracy of our Monte Carlo approximation which directly follows by applying the Chernoff Hoeffdng bound.
Proposition 8. Our Monte Carlo simulation (Algorithm ① in Appendix D returns a value that with high probability close to the optimal membership inference bound 1j of Theorem 6 namely Priin n7' 2 8) S em.68//3
EVALUATION
In this section we perform experiments to calculate the concrete trade-off between accuracy and membership inference on mainstream datasets. For our experiments, we use DP-SGD (Algorithm to train models and use Algorithm to caleulate the corresponding membership inference bounds.
Experiments on the MNIST and CIFAR datasets. We use the MNIST (LeCun) and CI- FAR (Krizhevsky et al. 2009) datasets perform experiments with DP-SGI. Figures 2(a) and 2(b) shows the result of our experiments. For MNIST, we used 3-layer convolutional neural networks (CNN) and train for 10 epochs with sampling rate q 0.001 and learning rate 0.1 using the cross-entropy loss function. We also choose the gradient clipping threshold to be 1.0 and change the noise scale between [0.5, 1.5). For the CIFAR-10 experiments, we use 5-layer CNNs and trained them for 50 epochs with sampling rate 0.02 and learning rate 0.5 using the cross- cross-entropy loss. We the gradient clipping threshold to 10.0 and the noise scale changed between [0.5, 2]. Our experiments show that differentially private training using DP-SGD can obtain a significantly better trade-off between accuracy and membership inference advantage than was previously thought. For instance, on the MNIST dataset obtain membership inference bounds that are close to 0.01 while maintaining accuracy at around 93%.
Study of the role of noise scale and sampling rate. To understand the role of sub-sampling membership inference advantage we perform experiments with varying sub-sampling rates. In Figure 5 we show the results of our experiments where change the sampling rate between [0, 1] at three different values of noise scale. Our experiments are done for 5 epochs of training. Note that although the number of epochs fixed, the number of iterations are different for different sampling
8

---

Durx (T
Hamphties
Dura (Hiikker)
0.
0.5
Bur llumphnee et Our Ifirsker
0.300
modol
(a) Membership Inference v.s. Accuracy on CIFARIO. (h) Membership inference v.s. Accuracy on MNIST.
Figure 2: Empirical results on membership advantage
30
(a) 0.5
(b) 1.0
(c) 1.5
Figure 3: Effect of sub-sampling rate at various noise scales with epochs.
rates. One interesting observation is that our optimal bound less dependent on very small sampling rate. For instance at noise scale a = 0.5, both the Pinsker and Humphries et al. (2020) bounds become vacuous abruptly as the sampling rate grows but our optimal membership inference bound remains meaningful. Another interesting phenomenon is the oscillations that happens at certain locations for the optimal and Pinsker bounds. These oscillations happen independently for both the Pinsker and optimal bound. As these two bounds calculated using completely different techniques, we believe this phenomenon is not due to numerical issues.
Monte Carlo error for the experiments. In experiments for optimal membership bounds use Monte Carlo simulation (see Section and in Algorithm T. with m = 5e5 samples. Via Propo- sition & we guarantee that with probability at least 99.9 99.999% that the bound has error less than 0.01.
6 CONCLUSION
In this paper, we directly analyzed membership inference bounds for adaptive composition of sampled Gaussian mechanisms. Our analysis enables us obtain bounds that are better than bounds from prior analyses of differential privacy. Our analysis shows that although differential privacy guarantees might sometimes lead to large/vacuous membership inference guarantees, the mechanisms that obtain differential privacy can be in fact much more secure against membership inference attacks. Previously, this phenomenon was observed for DP-SGD and here, for the first time, we prove it.
Our analysis is the first to directly analyze membership inference bounds. We limited our study to membership inference attacks against sampled Gaussian mechanisms as DP-SGD, the most widely used differentially private learning algorithm. Direct study of membership inference could be potentially done for other mechanisms and algorithms as well. We leave this for future work.
We also note that the hyper-parameters for DP-SGD that achieve optimal membership privacy versus utility might be different than that of differential privacy. Our new analysis opens up the possibility of a systematic search for the
and architectures (using recent advancements in hyperparameter tuning and architecture search (Papernot et al. 2020 Papernot and Steinke 2021 Chaudhuri and Vinterbo 2013)) that obtain optimal utility for given upper bound on membership inference.
Last, while our paper closes the gap between theoretical and empirical measures of an adversary's advantage, the bounds apply to the subsampled Gaussian mechanism. We leave the tightness of advantage measure other mechanisms for future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Dlya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. CCS, 2016.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
Daniel Bernau, Günther Eibl, Philip W Grassal. Hannah Keller, and Florian Kerschbaum. Quanti- fying identifiability to choose and audit e in differentially private deep learning. arXiv preprint 1oXiv:2003.02913. 2021.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, al. Extracting training data from large language models. arXiv preprint arXiv:2012.07805, 2020.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. arXiv preprint a2.:5:21 2021.
Kamalika Chaudhuri and Staal A Vinterbo, A stability- validation procedure for differentially private machine learning. Advances in Neural Information Processing Systems, 26, 2013.
Christopher A Choquette-Chon Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label- only membership inference attacks. In International Conference on Machine Learning, pages 1974-1974. PMLR, 2021.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv:1905.02383 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-28:4 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, pages 51 51-60. IEEE, 2010.
Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust trace- ability from trace amounts. In 2015 JEEE 56th Annual Symposium on Foundations of Computer Science, pages 650-669. IEEE, 2015.
Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An end-to-end case study personalized warfarin dosing. In 23rd USENIX Security Symposium, pages 17 17-32, 2014.
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS genetics, :e 1000167,, 2008.
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.12112. 2020.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pages 1895-1912, 2019.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Revisiting membership inference under realistic assumptions. arXiv:2005. 10881, 2020.
Jinyuan Jia, Ahmed Salem, Michael Backes, Yang Zhang, and Neil Zhenqiang Gong. Memguard: De- fending against black-box membership inference attacks via adversarial examples. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pages 259-274, 2019.
10

---

Under review as a conference paper at ICLR 2023
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Internationaa conference on machine learning, pages 1376-1388 1385. PMLR, 2015.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist/.
Jaewoo Lee and Chris Clifton. Differential identifiability. In Proceedings of the 18th ACM SIGKDD international conference Knowledge discovery and data mining, pages 1041-1049, 2012.
Sebastian Meiser. Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive, 2018.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Machine learning with membership privacy using adversarial regularization. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages
2018.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 666-882. IEEE, 2021.
Opacus. Opacus PyTorch library. Available from opacos.u
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. arXiv preprint arXiv:2 10.00:6000 2021.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ulfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint arXiv:2007. 14191, page 10, 2020.
Mark S Pinsker. Information and information stability of random variables and processes. Holden- Day, 1964.
Shahbaz Rezaei and Xin Liu. On the difficulty of membership inference attacks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7892-7900, 2021.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. International Conference on Machine Learning, pages $558-5567 PMLR, 2019.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposiun on Security and Privacy (SP), pages 3-18. IEFF, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE global conference on signal and information processing. pages 245-245 IEEE, 2013.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Xinyu Tang, Saeed Mahloujifar, Liwei Song, Virat Shejwalkar, Milad Nasr, Amir Houmansadr, and Prateek Mittal. Mitigating membership inference attacks by self-distillation through a novel ensemble architecture. arXiv preprint 4rX1v:2110.08324, 2021.
Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot. Bounding membership inference. arXiv preprint 2xXiv:2202./2232 2022.

---

Under review as a conference paper at ICLR 2023
Laurens der Maaten and Awni Hannun. The trade-offs of private prediction. arXiv preprint arXiv:2007.05089, 2020.
Lauren Watson, Chuan Guo, Graham Cormode, and Alexandre Sablayrolles. On the importance of difficulty calibration in membership inference attacks. International Conference on Learning
Representations, 2022.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection overfitting In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pages 268-282. IEEE, 2018.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 4782 4817. PMLR, 2022.
12

---

Under review as a conference paper at ICLR 2023
A BOUNDING TRUE POSITIVE RATE
As argued in introduction, membership inference alone should not be used as single measure of privacy. Here we first show how one can use TV. draw the false positive. Let X, Y be two distributions and consider a set Sa = {z; Pr[Y = x] > P=(X==]}.
Proposition For all sets with Pr[X E S) S Pr[x S.] we have Pr(Y E ES] S Pr(Y E S.).
Proof. We have
Pr(V E S.) Pr|y E Pr(V E S2 \S| Pr(Y \ Sa)
We also have,
Pr[Y = x]] Pr[X x
Pr[X E S Sal
Pr[Y E { = E
1(x E 1 (.)]
and
Pr|Y x] Pr[X x
Pr[X E S₂ S
Pr[Y E S. \ =|== Ex-
[ So 15)
a
By the condition of the proposition we have
Pr[X E S.] = Pr|X E S. SPr(X E S,US) > Pr[X S\Sx E S,US] = Pr[X e S]
Therefore we know that Pr[X E S. \ Pr|E|X E S S.I which finishes the proof.
Proposition 10. We have
2TV (X,Y) + 2Pr[X Sal +
Pr|Y E S.)
2a
Proof.
/
2TV (VVaXX,Y).
|du adv)
(adv du))(addv > dp) + Pr Sal --P22P e Sa 1 a.
Propositions 9 and 10 give us way to argue about the true positive rates at any given false positive rate as follows.
Corollary 11. Let X and be the distribution induced by applying composition of subsam- pled Gaussian mechanisms given an output decides whether the output was sampled from X or Y. Let FP and TP be the false positive and true positive rates of this adversary, i.e. FP Pr[A(X) 1] and
neighboring datasets. Also let A be adversary that
TP = Pr(A(Y) = 1]. Let a be such that Pr, <- X[Pr(Y = x] Pr(X==] FP Then we
2F 2FP42TV.. ,a) B az )1)a-a-11
have TPS
2a
Proof. This directly follows from Theorem 0 and Propositions and 10
B PROOF OF LEMMA 5
Proof. The first part follows by the symmetry of isotropic Gaussian. For the second part (monotonic- ity) we use the definition of TV Without loss of generality we can assume E [0, 1] as otherwise work with TV. (P, Q)/a derivative of the integral always positive. In the following calculations, we use C₁ C22 C3 and ca to denote positive constants that are independent r.
TV (V, P). Let ||u uzll2- We show that the
13

---

Under review as a conference paper at ICLR 2023
First note that x² -22 In(a) is middle point where 2-2 negative as x increases. By our assumption that a E [0, 1], we have that x > 0. Recalling that erf(2) - So exp(-t?)dt, and that erf(oc) can write
=2
(a-ej² 2o goes from positive to
that (by symmetry) 2
/ s exp(-t? (ep(-t?)ed 1,
TVa(P,Q) = C1 (ʃ=
e 20
ae
dæ
By breaking the integral in an intermediate point we have
(
-1
ae
20
ue
20
By replacing the integrals with the CDF of Gaussian distribution we have (x (=//V20)
=a (1 ++ett erf
(r)(((=
(a(1 erf ((=--r)/V20)
orf (x" 2V//22)
= 02 orf (T² [2=In((a)0? + +1 aerf (-r² In(a) ( -a).
2//20r
2/2or
(1 (==_n(() and (2(r) -aerf
(- In(o)r
Now, let (r) = erf
2v/2or
222or
2v/2r
Taking the derivative with
respect to r we have
0fi
In(a)
(
(12-000))22 2wZer
C3
Ör
22
2/2r2
0f2
In(a)o
(nin)()) 24/
cza
Òr
2v
2v2r2
-nn_)n 2/2or
Now note that we have
202er
2/2 .
Therefore, we have
112-000)) ?
OTV
1+ Va
In(a) (Va -Va-1)o
20
dr =e
20
2v2r²
Now since a E [0, 1.. we have ln(a) < and vā-1 < 0, which means the term positive. This implies that the whole gradient is positive.
1+ 1+va lnfa)(vā-1jo
2.2o
2/2r²
C ESTIMATING KL WITH RÉNYI DIVERGENCE
For two probability distributions y and v, the Rényí divergence of order a >
1
Da (u v) 1 log E
dp du (t)
(13)
Rényi divergence is non-decreasing in a, and lim Do (P =LP
RDP accounting for DP-SGD. Abbad al. 2016 Mironov 2017) propose methods to account for RDP for the Gaussian mechanism. Implementations of DPDSGD such Opacus make use of these accounting procedures. This is important as we use these accounting methods to calculate the bound in Equation 13 Specifically, calculate the Da for 1 + for very small using the Opacus implementation of Rényi accounting.
D ALGORIHTM
14

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Optimal MI
Require: sample rate vector q, number of iterations T, learning rate vector 17 noise scale vector a, gradient norm clip vector r, sample size m
1: for all [ma] do
2: f 0
3: for i E [T] do
4: for [m]] do
2-1,/--11-11 [i) II) 5: sample ti, o(0, 2
6:
11 < M1j +In In (1+g/i](e 20/1/2
-1))
7:
7 0
8: for j E [m] do
9:
fij max(1;; 0).
10: 17 17 1-e"1
11: return 1
Algorithm 2 DP-SGD (Abadi et al.) 2016)
Require: training dataset D, sample rate vector q. number of iterations learning rate
vector 7), noise scale vector a, gradient norm clip vector loss function L Initiate randomly
2: for E {T) do
3: B; +- -ample batch via Poisson sampling with rate g[i]
4: Vit] +
5:
for all (ar, y) B, do
6:
(2.w) <- gradient of L(x, y) (V(..))
7:
V (z.8) + r|t] max([[]).[VV
8:
V f
V
(a.y)
9:
V
< V i + WO [(
10:
0
11:
return 0
E PROOF OF THEOREM 6
Proof of Lemmal
We have
2TV (X = / dp' - advl = Iqdμ - (g + a - 1)dvl
=9 9 ( dp (g du
TV -لا (X,Y).
Proof of Theorem
The proof steps are similar there is no sub-sampling. First, we have
(TV(X,Y) =
Σ
SET 18
Pr sT1 = SCT-I]|
Σ Pr|Xr = ST
= ST | Pr[X sgT-1)
2
Σ
D=X TVatr))) S Yr 8gr-1).
BCT-1E8c7-1
15

---

Under review as a conference paper at ICLR 2023
But since XT and Y7 are subsampled Gaussian mechanisms we have XT = (1 Y + q.Y. where and X' are mixtures of Gaussians. Therefore, by Lemma and Lemma we have
TV(X,))
T = ScT-1]9TV al stegr-1)to- (X 88T-1, Yr SgT-1) "CT -
Σ
|
(By Lemma
Σ
= - (By Lemma
P1(X = (00
esT -
=
(By Lemma
-
Σ
-57-1E55T-1
Therefore, we can replace XT with mixture of two Gaussians centered and and Yr with single Gaussian centered at O. Now we can use the same technique used in the proof of the case without sub-sampling and move Xr and Yr to the first round and repeat this process. is replaced by n--dimnssiona Gaussian centered at 0 and standard deviation a, and X by a mixture of Gaussians with center randomly selected according to a n-dimensional Bernoulli distribution with probability That is, the advantage is bounded by
the end, Y
TV(((0", (()(O")))
F EXPERIMENTAL DETAILS
F.1 GAUSSIAN EXPERIMENT
The simple Gaussian experiment is aimed at stripping away parts of the machine learning pipeline that can interfere with privacy / membership inference, such as the particularities of neural networks or optimization algorithms.
In this setup. D = {0, O.. 0} and D' = DUDDU f1}. The (clean) summed gradient, before noise addition, is therefore either (on D or on D' if the batch does not contain 1) or (if the batch contains 1). The adversary observes the noisy sums and infers whether they come from D or D'. Given that the adversary knows the distribution either A/0. o²) or (1 (0, o²) + gN(11 2²). they can perform a simple likelihood test to determine whether the noisy sums come from D or D'. and predict the more likely dataset. We report the advantage of this adversary in the "empirical" curve of Figure
G MEMBERSHIP INFERENCE PRECISION
In this section, we refine the analysis of Sablayrolles et al. 2019) for the accuracy of a membership attack.
Upper-bound on precision. Let us first derive bound on the precision of membership inference. We assume that there are two datasets D and D' and that differentially-pritn private mechanism M trains model represented by 0.
With probability (1 - 8) over the choice of we have:
Pr(M(D)= = 0) Pr(M(D') 8)
S
log
S
(14)
Given that there is balanced prior Pr(D) Pr(D'), using Bayes rule, we have:
0))
Pr(D 10 Pr(M P) Pr(D))
(15)
16

---

Under review as a conference paper at ICLR 2023
(D) -)
(16)
Pr(M(D) - 0) P = 8)
<00 log Pr(M = 0)
(17)
Pr(M(D')>= = 0)
with (u) 1/(1 + exp(-u)) the sigmoid function.
Hence the precision Pr(D 0) is bounded between o(-)) and ((c), as o()) is non decreasing.
Upper-bound on attack accuracy. The accuracy of the Bayes classifier
Acc max(Pr(D) 0), Pr(D) 0)),
(18)
and thus
Acc S max( a
(19)
(20)
This means that the attack accuracy is bounded by o(c) with probability - 5. Empirically, we see that the sigmoid function closely matches the bound given by HHumphries al. (2020). Simply stated, this derivation shows that the bound proven by Humphries et al. (2020) actually holds with probability - instead on average.
Ace
2 (Pr(X A
2 (Pr(X E #) E A))
(1 + Adv)
H COMPARING SECURITY GAMES
In what follows, we write multiple variants of security games specifically defined for DP-SGD. Then we proceed compare the security games based on an example. We perform experiments on this examples by running an attack and show that our upper bounds are tight even for the weaker security games.
H.1 OUR SECURITY GAME WITH ALL INTERMEDIATE GRADIENTS (OIG)
1. Adversary picks datasets D {.1.... 2n and pair of data points z 21.
2. Challenger samples a bit b uniformly at random and creates
D i (2) ifb=0
D' D'=
3. Challenger runs DP-SGD on D' train a model and sends transcript of training, including all intermediate gradients, (The transcript could only include the final model or more information like the intermediate steps of training) to the adversary.
4. Adversary observes 0 and and guesses a bit b' Adversary wins if b.
Remark 12. this paper we are interested in analyzing the membership inference advantage for algorithms that could be stated as adaptive composition of sampled Gaussian mechanisms. DP-SGD (Algorithm 2 is a widely used example of such algorithm. Note that we assume that the output of DP-SGD includes all the intermediate gradients that are used to train the model. In other words, the parameter in the security game contains all the intermediate gradients (not only the final model). However, in what follows the final model. We define these more restricted security game so as to experimentally compare with security game.
still define the security game for the case that the adversary only sees
17

---

Under review as a conference paper at ICLR 2023
Remark 13 (Replacing vs addition/removal). We also note that in this section define the notion of advantage for neighboring datasets where one dataset replaces a single example with another example (i.e. the replacement game). The reason for this choice is that the security game of Yeom et. al. is based on replacement and we want to make fair comparison.
In the main body, use the addition/removal definition of neighboring datasets because it is stronger. Namely, we can convert an upper bound on addition/removal security game to an upper bound for the replacement security game.
Remark 14 (Alternative notion of inference in Humphries et al. (2020)) Humphries et al. (2020)
propose new definition for inference attacks. This definition (They call "Experiment with Data Dependencies", .) is distinct from the previously known notions of membership inference and deals with the ability of an adversary in distinguishing samples from two different distributions. As this notion is model of distributional inference, the power of adversary in this model is not bounded by differential privacy. The only way to bound this notion of privacy with DP is to pay the cost of group privacy for groups that almost the same size as of the entire dataset. Hence, do not study this model in this work.
H.2 OUR SECURITY GAME WITH FINAL MODEL (OFM)
1. Adversary picks datasets D {=1- -....... . 2n)
and pair of data points 21-
2. Challenger samples a bit b uniformly at random and creates
D' D'= 2 b i
3. Challenger runs DP-SGD on D' to train a model and sends the final model 0 (The transcript could only include the final model or more information like the intermediate steps of training) to the adversary.
4. Adversary observes & and and guesses a bit b/ Adversary wins if 6' = b.
H.3 YOEM ET. AL'S SECURITY GAME WITH FINAL MODEL (YFM)
1. Challenger samples a dataset {21, ......... 1 } from distribution D.
2. Challenger runs DP-SGD on D to train model and sends the final model A to the adversary.
3. Challenger samples a bit uniformly random and creates
D if D
2
if =0 0
4. Adversary observes (0, and and guesses bit V' Adversary wins if D'
H.4 YOEM ET. AL'S SECURITY GAME WITH ALL INTERTEDIATE GRADIENTS (YIG)
1. Challenger samples a dataset D = (=1, 11+1 } from distribution D.
2. Challenger runs DP-SGD on D to train a model and sends a transcript of training 0, including all intermediate gradients, the adversary.
3. Challenger samples a bit b uniformly at random and creates
z - D
i = b-
-
D
4. Adversary observes (0, and and guesses bit b' Adversary wins if b' b.
Notation. For a security model 7' we use T(L, n, D) to denote the advantage of strongest adversary in that threat model with learning algorithm I., dataset size n and data distribution D (our threat models do not use this parameter but we include it for symmetry).
Proposition 15. For any learning algorithm L, any n E N and data distribution D we have OFM(L, n, D) < OIG(L, n, D) and YFM n, YTG(L, D).
18

---

Under review as a conference paper at ICLR 2023
Proposition 16 (Proved in Humphries al. (0200). ). For any learning algorithm L, any N and data distribution D we have YIG(L, n, D) S OIG(L, D) and (FM(L, n, D) S YIG n, D). Corollary 17. Any upper bound on the advantage of udversaries in security game OIG is also an upper bound on the udvantage of adversaries in the security games YIG, YFM and OFM.
Our analysis above shows that upper bounds for our security model are valid upper bounds for the security game of Yoem et al and Shokri et as well. Now, to analyze the tightness of our upper bound we perform experiments with attacks in these threat models. We argue that one cannot get a better upper bound on membership inference, unless they make extra assumptions on the data distribution. In what follows, we experimentally verify this.
I EXPERIMENTS ON THE OPTIMALITY OF OUR BOUND
In this section, we construct a data distribution and study logistic regression on this distribution.
Definition 18. We define Ha be the uniform distribution over the hamming ball of radius I and
centered at zero. Thus, the samples from Ha have the form. (O..... 0, 1, O,....... .., .) with only one of the coordinates being and other being O. For an arbitrary Boolean function J: {- - {0. 1} we also define Hi be the distribution of samples from H that are labled w.r.t. f, namely, H2 (Ha, ((Ha)).
Experiment setup: We run experiments for membership inference on DP-SGD when trying to learn Hy using logistic regression, and for an arbitrary function f. We set the learning rate to 0.001, the clipping threshold to .1 and vary the sub-sampling rate and noise multiplier. We run the models for either 5 or 50 epochs.
Attacks. We implement a simple attack that only looks at the final model. This adversary looks at the final model 0 and the target instance in hand which is equal to 1 in coordinate i and zero everywhere else. If the ith coordinate of larger than Tge/2 + mTqe/d d (T the number of iterations, is sub-sampling rate, is the number of examples in the training set, and is the clipping threshold) then the attack predicts = otherwise it predicts V/ = 0. We call this attack the "final model attack" (FMA). We also implement another attack that looks at all the intermediate models. This attack basically performs the FMA attack at each iteration and takes majority vote at the end. We call this attack the "Intermediate models attack" (TMA).
Evaluation.
We evaluate our FMA attack in the threat models of Yoem et al. and Shokri et al. in the setting where the adversary only sees the final model. We also evaluate this attack in our threat model, in the setting that the adversary only sees the final model. We also report the accuracy of the stronger TMA attack.
1.1 RESULTS
We now summarize our findings in our experiments
Increasing d reduces the gap between threat models. We instantiate our data distribution Hi with random function f and select the dimension from {2000, 10000, 10000]. We set the sample size to 1000, set the sub-sampling rate to and vary the noise multiplier to obtain the attack curve. We the models for epochs and report the attack in various threat models. Our results in Figure shoow that by increasing the dimension, the gap between the performance of all attacks and our upper bound shrinks almost 0. This verifies the optimality of our bound. It also shows that there is no fundamental gap between the threat models and we cannot hope to achieve stronger upper bounds in the weaker threat models, unless we make further assumptions.
Small sub-sampling rate results in small gap between the performance of FMA and IMA.
We instantiate our data distribution Hd with random function and set dimension to 2000 while keeping the number of instances at 1000. We set the sub-sampling rate to .01 and the number of epochs to 50. We vary the noise multiplier to obtain the attack curve. Our results in Figure 1.1 show
show
19

---

Under review as a conference paper at ICLR 2023
1.0
Our bound
al.]
0.9
Humphries et al. bound
success al.]
Attack success [All intermidiate models] success (Only the model]
0.8
Advantage
0.6
0.5
0.4
0.3
0.75
1.00
125
1.50
1.75
2.00
2.25
2.50
Noise multiplier
(a) d = 2000
1.0
Our bound
Attack
al.]
0.9
Humphries at al. bound
success [Shokri
Attack success [All intermidiate models]
0.0
[only
Advantage
0.7
0.6
0.5
0.4
0.3
0.75
1.00
1.5
1.50
1.75
2.00
2.25
2.50
Noise multiplerr
(b) d = 10000
1.0
Our bound
success [Yoem et al.]
0.9
Humphrics et al. bound
[Shokri
Attack success [All intermidiate models]
0.8
Attack success [Only the last model]
Advantage
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
multiplier
(c) d 100000
Figure 4: Decreasing results smaller gap between all threat models and the upper bound. This shows the optimality of our bound in all threat models.
20

---

Under review as a conference paper at ICLR 2023
bound
Advantage
Attack success (ooem el.]
0.6
Humphries bound
Attack success [Shokri et al.]
Attack [All intermidiate models)
0.4
Attack success [Only the last model)
0.2
0.75
1.00
1.25
1.50
1.75
2,00
2.25
2.50
Noise multiplier
Figure 5: Small sampling rate can produce a gap between FMA and IMA, but this gap tightens as we increase the noise.
that small sub-sampling shrinks as we increase the noise multiplier.
create a gap between the performance of two attacks. This gap
Remark 19. Our experiments in this section verification of the observation made in Nasr et al. (2027) that an adversary with enough capabilities (e.g. poisoning the datasel and observing the models in different iterations) can achieve high membership inference advantage. Our result in this section show that if we allow the adversary to pick the classification problem (the data distribution and the architecture), can achieve high advantages that are close theoretical upper bounds, even without seeing the intermediate models or poisoning the data.
J SECURITY GAME WITH NON-UNIFORM PRIOR
Here, we extend our result to the setting where the prior distribution for the bit in the security game for membership inference is non-uniform. This setting is recently studied in the work of.
Definition (Non-uniform membership inference.). We define security game between an Adver- sary (who wants to guess training set membership) and Challenger (who wants to hide training set membership).
1. Adversary picks datasets D = (21 Zn. and a data point z!
2. Challenger samples bit b from bernouli distribution with probability p and creates
DU (2'}
ifb= -
D'
3. Challenger runs the learning algorithm I. on D' to train model and sends a transcript of training 0 (The transcript could only include the final model or more information like the intermediate steps of training) to the adversary.
4. Adversary observes 0 and guesses bit b'. Adversary wins if b.
We define the advantage of adversary A on learning algorithm L as Ad = P.Pb B'] max(p, 1 p)- We also use Adv(T.,p) supA Adv(A, I.,p) denote the advantage of any adversary against T.
Note that similar to the uniform setting, with simple averaging argument best adversarial strategy in the non-uniform membership security game is deterministic strategy. Therefore, assuming 0.5, the advantage for the learning algorithm L is then defined
show that the
Adv(L.p)
sup ((A) (P (1- (1- (1-
(21)
2
21

---

Under review as a conference paper at ICLR 2023
((A) p
sup p)
1-p ((A)
(22)
= sup p)
((AA) 1 p p(l)
p
- -(1 -11-77
(M(A)
- p u(A)
P
(23)
A
+ (1 - p) (((A) p
- (((A)
(24)
Adv(L,
2(1 p) TV - (X,Y) + (1 22p
(25)
2
Therefore we have
Adv(L,p) - 2(1 - P)
2p
(26)
Now using this, can prove the following Theorem.
Theorem 21 (Non-uniform gaussian Composition with sub-sampling). Let MI....; Mr be series of adaptive Gaussian Mechanisms with L2 sensitivity r and Gaussian noise with standard deviation and sub- sub-samplin rate q. The non-uniform membership inference risk of the composition of M; 's is at most
2(1 p)TV + (NrO .o).N(r BBg)) +1
where p < 0.5 is the probability of sampling of the additional example in the non-uniform security game.
The proof is similar to the proof of Theorem 6 exceept that we use Equation 26 instead of Equation
Proof.
22


Reviews:
[{"review_id": "x6HbteaiqJ", "reviewer": "Reviewer_eNLu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies upper bounds on the performance of membership inference (MI) attacks on models trained with the subsampled Gaussian mechanism to ensure differential privacy. In this paper, the authors derive bounds on the advantage of an adversary mounting the MI attack.They also perform some experiments to illustrate the values of the calculated upper bounds on CIFAR and MNIST datasets.", "summary_of_the_review": "All in all, the paper is not very well written and makes it hard to understand. In light of the weaknesses mentioned above, I recommend this paper for rejection.", "strength_and_weaknesses": "Strengths:\n1. This paper studies a relevant problem.\n2. The paper makes headway in the right direction by trying to bound the advantage directly using the divergences which are intimately tied to DP guarantees rather than incurring the additional loss incurred by DP guarantees by converting them to divergence based guarantees.\n\nWeaknesses:\n1. The paper is poorly and hastily written; many statements are imprecise and its unclear what they mean. I will list down a few below, and would be interested to know what the authors mean by them:\n *  On page 2, \"Our analysis explains, from a theoretical point of view, why the precision and recall of membership inference attacks is stronger than the accuracy.\" --- What is accuracy here? How does your analysis explain this? There is no mention of precision/recall after the related work, its unclear what the paper is claiming.\n* Notation of r is used before defining in section 4, page 5 when giving an overview of the section. There are also other such instances.  While this by itself doesn't make a paper rejection worthy, it creates quite an unpleasant experience.\n* Throughout the paper, there has been reference to Theorem 18, when the real reference is to something else. This again, makes reading and trying to understand the contributions really hard.\n2. The equation following Lemma 5 doesn't show a monotonically increasing function, while maybe not wrong, the equation is quite vacuous. Also, the proof is quite standard.\n3. For Theorem 6, while I agree with the statement, reading the proof is more confusing than just trying to reason about the statement.\n4. The optimality claim is very vague, there is no rigorous sense in which optimality is defined and shown. If it is provably optimal, one doesn't need to empirically show tightness; if it is not, it is not optimal.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "msvLZ8t8_j", "reviewer": "Reviewer_919G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper focuses on finding bounds on the success of membership inference (MI) attacks, i.e., attacks that predict if a given sample has been used in training a model or not, when the privacy is protected by (subsampled) Gaussian mechanism from the differential privacy (DP) literature. MI attacks have an intimate connection with DP, since DP definitions direcly give worst-case bounds for MI. The current paper establishes optimal bounds for the adversary advantage for the subsampled Gaussian mechanism using the add/remove neighbourhood granularity. The authors experimentally show that their bounds are tighter than the existing bounds in the literature, and that the optimal bound matches the experimental results.\n", "summary_of_the_review": "A very nice paper (partly) solving an open problem in privacy-preserving machine learning.\n", "strength_and_weaknesses": "### Update after the discussions:\n\nAs pointed out by the other reviews, many of the main results in the paper can be derived by existing methods. I am therefore lowering my score. I still think that this can make a nice paper once the authors have more time to rewrite it and change the focus to emphasize the more novel aspects. Hopefully, the more critical reviewers can also give good feedback on what they think would be the possible novelty.\n\n### Strengths:\n\n1) The results presented in the paper seem exiting, and solve an important open problem in privacy-preserving machine learning.\n\n2) The paper is mostly enjoyable to read.\n\n### Weaknesses:\n\nWith superficial checking of the proofs (due to tight reviewing schedule), I have no major problems with this paper. The following are minor comments and some questions for the authors:\n\n1) Considering Remark 1 about the weaker security game: how does this relate to Nasr et al. 2021 results with DP, which shows that to achieve the theoretical DP bounds the adversary needs the full power allowed by the DP definitions, in particular the power to poison the data on each iteration and to see the output from all iterations, not only the final model?\n\n2) Add some more steps to proof of Lemma 5 to make it easier to follow; by quick checking there also might be some typos in the proof, please check this again.\n\n3) Thm.6: Please clarify the proof: does the transcript of the learning algorithm need to be discrete (e.g. Eq.8)? What do you mean by saying that M^i(D) \"works on D and consists of i Gaussians N(0,sigma^2) steps..\"?\n\n4) Fig.4: synced oscillations look really weird, please check again that this is not an artifact of the experiment.\n\n\n#### Even smaller comments:\n\ni) Thm.7: Thm statement is overlapping with the proof.\n\nii) p.4: denote by Adv(L) \"advantage of any adversary\". Should this be advantage of worst-case adversary? It looks like there might be adversaries which have worse advantage, since this is sup over A.\n\niii) What is Thm.18 in Appendix D? The notation is a bit confusing: in Lemma 8 X' is a mixture of X and Y, but in the proof of Thm18 X is mixture of X' and Y.\n\niv) Note that delta in approximate DP is not a probability (see e.g. Meiser 2018).\n\nv) p.3: DP-SGD was proposed by Song et al. 2013, while the main contribution by Abadi et al. 2016 was the new accounting technique.\n\n\n#### References: \n\nMeiser 2018: Approximate and probabilistic DP definitions.\n\nNasr et al. 2021: Adversary instantiation.\n\nSong et al. 2013: SGD with DP updates.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bdpCs6oBMBi", "reviewer": "Reviewer_H7BJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Motivated by membership inference attacks against differentially private stochastic gradient descent (DP-SGD), the paper bounds the total variation (TV) distance between two runs of DP-SGD on two neighboring data sets. DP-SGD amounts to subsampling and adding Gaussian noise to adaptively chosen vectors. The main result of the paper is that the TV distance between these two sequences of random vectors can be bounded by a sequence where the vectors are fixed rather than adaptively chosen, or, equivalently, by the TV distance between two Gaussian distributions with equal variance and random means chosen from a binomial distribution. The result then implies bounds on the advantage over random guessing of a membership inference attacks against DP-SGD, assuming that the attacker sees the full sequence of noisy gradient steps.", "summary_of_the_review": "The paper studies an important topic but the results follow from prior work, and have some considerable limitations.", "strength_and_weaknesses": "A detailed understanding of membership inference attacks is an important research agenda. This paper studies a widely used differentially private algorithm, and gives tight bounds on the advantage over random guessing allowed by this algorithm. There are, however, some shortcomings to this work:\n\n* The theoretical results are special cases of the much more general results of Dong, Roth, and Su (\"Gaussian Differential Privacy\", Journal of Royal Statistical Society, Series B). In particular, the DRS results hold for a wider range of algorithms, and allow a more fine grained understanding of the tradeoff between true and false positives in an inference membership attack. I elaborate on this below.\n\n* The advantage over random measure is a crude way to measure the power of an attack. The authors themselves acknowledge that precision and recall are better measures in evaluating attacks. But then what is the value of bounding advantage for a particular algorithm?\n\n* The model where the whole history of noisy gradient updates is available to to an attacker is not justified, and not always realistic. It may make sense in some federated learning settings, but the authors need to justify their model.\n\n* The analysis works only for a single, very specific algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RQTfXINnd5", "reviewer": "Reviewer_8xNP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper gives formulas for evaluating the total variation distance for the outputs of the Gaussian mechanism and its subsampled variant (i.e. for outputs originating from neighbouring datasets). The need for doing this is motivated by membership inference security game where an adversary tries to guess whether a given sample is in the data or not. The 'advantage' of the adverary can be bounded using the total variation distance. This has been considered previously for general $(\\varepsilon,\\delta)$-DP mechanisms by Humphries et al. (2020).", "summary_of_the_review": "Doe to these aforementioned reasons (lack of novelty, lack of content), I am leaning towards rejecting the paper.", "strength_and_weaknesses": "\nPros:\n\n- the paper improves the TV bounds by Humphries et al. (2020) for the subsampled Gaussian mechanism considerably.\n\n- The paper is very well written, easy to follow.\n\nCons:\n\n- There is not much novelty, the contribution remains small (see comments below).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject