Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies membership inference attacks and how differential privacy can help mitigate such attacks.  Although the connection between membership inference and differential privacy has been known, this work provides a tighter connection.  It is important for the future development of private ML to better understand the connection between DP and specific attacks as small privacy loss parameters are not practical in many settings
main_review: The presentation count be improved.  There are some parts that could be reworded to be made more clear.  Specifically, on page 1, it states “we observe the affect of our amplification on MI accuracy is significantly stronger than batch sampling”, but does this mean that batch sampling is used to amplify MI accuracy?  As far as I know, sampling is used to decrease privacy loss parameters in DP, which should reduce MI accuracy.  It is also not clear how batch sampling is different from training data that is sub-sampled.  I also do not understand the second contribution listed.  The tighter MI accuracy bound benefits in what way with subsampling?  Do you mean the bound is tighter?

Nasr et al. “Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning” argues that MI is not a good attack to evaluate DP.  Do you see that increasing the privacy loss parameter with DP leads to an improved MI attack empirically, not just with theoretical bounds? As I understood it, MI was a pretty weak attack for DP, so not sure how much tightening theoretical bounds really helps here.  

In the Amplification Effect section, there should be a little more care in the amplification term that is plotted.  In particular, the amplification by subsampling converts eps -> O(q eps) and the constants might matter in the plots.  This section seems a bit hand wavy in what it is trying to say.  At a high level, I understand this section to mean that subsampling amplifies DP and reducing the probability of drawing x_i in the dataset leads to an improved MI accuracy bound.  Are there two types of subsampling going on: one for subsampling the dataset and one for batch sampling.  If they are considered the same type of sampling, can you take advantage of the DP amplification, getting O(q epsilon) privacy loss, and the dataset subsample in the MI bound?

### UPDATE ###
The author feedback has addressed my concerns, so I will increase my score.
summary_of_the_review: This work provides a slightly stronger bound connecting Membership Inference attacks with differential privacy, however, the presentation could be improved and some parts are a little hand wavy.  I would also like to see more discussion on whether MIA are the right attack to consider with DP, as some recent works have shown the attack to be weak.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a tighter bound for accuracy of membership inference attacks for (pure) differentially private machine learning models. To account for inclusion probability of samples being different from 0.5, the authors separately bound positive and negative accuracy. Moreover, the authors also demonstrate the benefits of their bound on machine unlearning.
main_review: The main strengths of the paper are the following: 
1) The authors provide a tighter bound of membership inference accuracy than existing literature. This is very consequential in privacy preserving machine learning. 
2) The bounds provided by this paper are able to handle situations where the inclusion probability of samples is not 0.5 by providing separate bounds for positive and negative accuracy. 
3) The authors demonstrate a benefit of their bound by connecting it to machine unlearning in a rigorous way. 
4) The authors highlight the limitations of their approach by demonstrating that their bounds don't readily extend to approximate DP. 

The main weaknesses of the paper are the following: 
1) The background needs to substantially expanded upon. I would like to at least see the following improvements: i) a formal definition of membership inference, ii) a formal definition of machine unlearning (as used in the context of this paper). 
2) I found section 4 quite difficult to follow. I believe this could be improved by presenting some background on privacy amplification by subsampling. 

summary_of_the_review: While the paper presents an important and novel technical contribution, it has some writing issues. In particular, the background section needs to be somewhat expanded and a particular section would benefit from more clear writing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides $\epsilon$-DP. The authors also analyze their bound from the perspectives of privacy amplification schemes and its connection to machine unlearning.
main_review: The paper proves a tighter bound on the accuracy of any membership inference adversary when a training algorithm provides $\epsilon$-DP. Specifically, The bound is given in terms of $\mathbb{P}_{\mathbf{x}^*} (1)$, which indicates the probability of drawing 
$x^*$ into the dataset from a larger set of candidates.I have verified the proofs and they are correct. 

The authors further compare the amplification effects of $\mathbb{P}_{\mathbf{x}^*} (1)$ with those in DP. Besides, the author also gives the connection between the bound and data deletion in machine unlearning. Overall, the whole paper is well-written and clearly organized, and the bound provided in the paper is interesting.

My biggest question is how to use the bound to the defender in practice.  Usually, the defender does not have the prior knowledge $\mathbb{P}_{\mathbf{x}^*} (1)$, which is completely controlled by the attack. Could you please elaborate more on how to use the information of the bound when the defender who wants to to know the limit of MI accuracy when the probability of drawing 
$x^*$ into the dataset is unknown to the user and how it improves from the Erlingsson et al. (2019) and Sablayrolles et al. (2019)?

Minor:

Besides, in Figure 2, is $\mathbb{P}_{\mathbf{x}^*} (1)=0.5$? 

If  $\mathbb{P}_{\mathbf{x}^*} (1)\neq0.5$, does the tightness of the bound still hold? In order to do so,  I suggest the author should provide the analytical form of previous bounds of MI in the appendix.

summary_of_the_review: 1. The paper is well written and the bound is insightful.
2. The paper still needs to elaborate on the bound from the perspective of the defender.
3. More detailed comparison about the bounds of MI are needed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a tighter analysis for membership inference attacks on algorithms that satisfy $\varepsilon$-differential privacy. It also talks about a better form of privacy amplification based on that. Finally, it discusses the role of membership inference in the task of machine unlearning.
main_review: Edit: I have bumped my score by a point after the authors' response.

Update: on further digging into the prior work, and having discussions with other reviewers and the area chair for this paper, I have decided to downgrade my review, unfortunately. Apologies for the last minute change, but I feel like the improvements made here, which were the main focus of this paper, are a little incremental. Unless the authors’ response to the Area Chair’s comments are satisfactory, I will commit to this evaluation.

Strengths:

--The bounds for membership inference attacks are fairly novel.

--Their experiments suggest better privacy amplification as opposed to the prior work.

--The application to machine unlearning is interesting.

Weaknesses:

--This is not really a well-written paper. Sometimes there are vague blocks of texts like Lemma 1 and Definition 1. The latter, in particular, seems counter-intuitive based on what the text before that described. Also, what the probability is over isn't mentioned either. The role of $f$ in the accuracy statement isn't clear exactly.

--Nitpick, but the definition of pure DP is stated twice in the paper (Equations 1 and 2). I don't know why this could not have been done just once.

--The technical contributions don't seem that strong. The proofs don't seem to require that much depth.

--Also, their bounds on the membership inference attacks don't appear super tight. Evaluating some known attacks to compare their accuracy with their own bounds could have been some kind of an evaluation.
summary_of_the_review: Based on the comments above, this paper doesn't strike me as a great paper. The ideas are respectable, but the execution could have been better, and more depth would have been appreciated.
review_title: null

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