Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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:

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

* 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?

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

* The analysis works only for a single, very specific algorithm.
clarity,_quality,_novelty_and_reproducibility: A membership inference (MI) attack is a hypothesis test between the null hypothesis H_0 (the person is not in the dataset) and the alternative hypothesis H_1 (the person is in the dataset. A complete understanding of what an MI attack can do is given by the tradeoff between type I error (or false positive rate) and type II error (false negative rate). Let $T(\alpha)$ be the minimum type II error of any attack that has type I error at most $\alpha$. The TV distance between the two hypotheses, which is the advantage measure studied in the paper under review, is then simply $\max_{\alpha \in [0,1]} 1 - \alpha - T(\alpha)$. Thus, the tradeoff curve $T$ allows computing the TV distance, but also gives more fine grained information about false positive vs false negative tradeoffs.

The paper of Dong, Roth, and Su mentioned above has a detailed study of this tradeoff curve. They show how to bound a tradeoff curve of any adaptive composition of mechanisms by the tradeoff curve of a non-adaptive composition: see Theorem 4 in the DRS paper. Applying Theorem 4 from DRS to DP-SGD immediately yields Theorem 7 from the paper under review, and, more strongly, it yields a complete tradeoff curve between type I and type II error. Moreover, Theorem 10 from the DRS paper already gives this analysis of DP-SGD. So, as far as I understand, the theoretical results in this paper are subsumed by the DRS results. 

It may be also worth noting that the TV_a quantity is commonly known as the hockey-stick divergence, and Lemma 5 is also known: see the results in the ICML 2018 paper by Balle and Wang.

Finally, the notation in the paper is unclear in some places. What is, for example, $1_T$ in (6)? What is $0^T$ in Theorem 7? 
summary_of_the_review: The paper studies an important topic but the results follow from prior work, and have some considerable limitations.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:
1. This paper studies a relevant problem.
2. 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.

Weaknesses:
1. 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:
 *  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.
* 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.
* 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.
2. 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.
3. For Theorem 6, while I agree with the statement, reading the proof is more confusing than just trying to reason about the statement.
4. 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.
clarity,_quality,_novelty_and_reproducibility: The paper is quite poorly and hastily written.
The idea of directly reasoning about the Total Variation distance when reasoning about the advantage is novel.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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).
strength_and_weaknesses: 
Pros:

- the paper improves the TV bounds by Humphries et al. (2020) for the subsampled Gaussian mechanism considerably.

- The paper is very well written, easy to follow.

Cons:

- There is not much novelty, the contribution remains small (see comments below).
clarity,_quality,_novelty_and_reproducibility: My main criticism is regarding the novelty: I would claim that using existing tools, it is already possible to bound the TV distance tightly for the subsampled Gaussian mechanism (and many more), using the results of [3] and also using the numerical method of [2]. Namely, the way you define TV, i.e. $\mathrm{TV}(X,Y) = \sup_A \mathbb{P}(X \in A) - \mathbb{P}(Y \in A)$, we see that this is just the hockey-stick divergence for $\varepsilon=0$ i.e. the $\alpha$-divergence for $\alpha=1$ (see e.g. [1]). The methods of [2] and [3] can be used to compute this for the subsampled Gaussian mechanism with arbitrary precision. When writing the hockey-stick divergence using the privacy loss distribution, we just need to compute an integral from $\varepsilon$ to $\infty$ and having $\varepsilon=0$ does not affect the method at all. It is of course nice if there are analytical formulas for doing it, however these computational methods are very efficient and thus I think this reduces the novelty of this paper a lot.

You seem to define $\mathrm{TV}(X,Y)$ without the absolute value, however it would not change anything as for $(\varepsilon,\delta)$ we take maximum of $H_\alpha(X,Y)$ and $H_\alpha(Y,X)$, where $H_\alpha$ denotes the $\alpha$-divergence.


I think that the TV-results for the Gaussian mechanism and the simple formula for the subsampling amplification for TV are nice contributions, but I don't think they are sufficient for a publication.

[1] Balle, B., Barthe, G., & Gaboardi, M. (2018). Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31.

[2] Gopi, S., Lee, Y. T., & Wutschitz, L. (2021). Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34, 11631-11642.

[3] Zhu, Y., Dong, J., & Wang, Y. X. (2022, May). Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics (pp. 4782-4817). PMLR.

summary_of_the_review: Doe to these aforementioned reasons (lack of novelty, lack of content), I am leaning towards rejecting the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

strength_and_weaknesses: ### Update after the discussions:

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

### Strengths:

1) The results presented in the paper seem exiting, and solve an important open problem in privacy-preserving machine learning.

2) The paper is mostly enjoyable to read.

### Weaknesses:

With 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:

1) 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?

2) 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.

3) 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.."?

4) Fig.4: synced oscillations look really weird, please check again that this is not an artifact of the experiment.


#### Even smaller comments:

i) Thm.7: Thm statement is overlapping with the proof.

ii) 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.

iii) 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.

iv) Note that delta in approximate DP is not a probability (see e.g. Meiser 2018).

v) 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.


#### References: 

Meiser 2018: Approximate and probabilistic DP definitions.

Nasr et al. 2021: Adversary instantiation.

Song et al. 2013: SGD with DP updates.

clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and very nice to read, although some points woiuld benefit from clarifications. 
As far as I know, the results are novel and seem very interesting. It should be possible to replicate the main findings of the paper given the information provided.

summary_of_the_review: A very nice paper (partly) solving an open problem in privacy-preserving machine learning.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies membership inference attacks against DP-SGD algorithm. In particular, the authors analyze the total variation (TV) distance between two executions of this algorithm on two neighboring datasets. 

Understanding membership inference attacks is an important goal, however, the paper has several shortcomings. The general consensus among the reviewers is that there is little novelty in this work. In particular, several results in the paper follows from a prior work ([Dong et al. 2019]) as pointed out by one of the reviewers. Moreover, the results are based on analyzing a very specific instantiation of one algorithm and under specific assumptions on the adversary's knowledge, which limit their applicability. 


justification_for_why_not_higher_score: The work is of little novelty. The main results mostly follow as special cases of a previous work.
Decision: Reject