Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper develops tools for analyzing private algorithms in the framework of Gaussian Differential Privacy (GDP). GDP is a strengthening of approximate differential privacy, similar in spirit to concentrated differential privacy (CDP): both GDP and CDP capture the privacy guarantees of the Gaussian noise mechanism, but generalize them in different directions. GDP has a number of nice analytical properties but analyzing the GDP guarantees of an algorithm can be difficult, as it involves comparing two different functions on $[0,\infty)$. The paper proposes a method to reduce this problem to comparing a function against a fixed constant function, making numerical or analytical GDP analysis of a given algorithm easier.
main_review: GDP is an elegant framework for analyzing private algorithms, due to its nice composition properties. A wider application of the framework, however, would benefit from automated tools for deriving tight GDP guarantees for a given algorithm. The main strength of the paper is in giving one such tool, and showing how it can ease the privacy analysis of several algorithms. The visualizations of the privacy profiles transformed by GDPT in the paper provide some insight on the privacy guaranteed by several basic algorithm. The main weakness of the paper for me is in the strength of the applications mentioned at the end: 
* the analysis of the Laplace noise mechanism is simple, and probably not the best illustration of the power of the methods here; 
* the analysis of SGD is limited to giving guarantees for some constant $\varepsilon$ and $\delta$, in particular, a value of $\delta$ that is too high for deployment; the illustration that the partial order on $(\varepsilon, \delta)$ can help improve an algorithm's error analysis is interesting, however;
* I am not sure what the takeaway is from the analysis of subsampling?

So GDPT may end being a useful tool in a privacy toolbox built around GDP, but the paper does not quite manage to make a strong case for it. Because of this, I will be ok if the paper were accepted to ICLR, but I will not push for it.

Some further minor comments:
* DP definition has a typo - missing less than or equal to sign.
* Concentrated DP was first proposed by Dwork and Rothblum (https://arxiv.org/abs/1603.01887).
* The references for DP SGD should contain Bassily, Smith, Thakurta, FOCS 2014
* Is $\mu_{\text{GDP}}(x,y)$ well-defined: what about existence and uniqueness of $\mu$?
summary_of_the_review: The paper makes a contribution to automating the privacy analysis of algorithms within the elegant GDP framework, but doesn’t manage to make a strong case for the usefulness and applicability of the new tool it develops.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors propose the Gaussian Differential Privacy Transformation to identify which algorithms fall under the framework of of GDP.
main_review: This paper attempts to identify a class of DP algorithms they call GDP algorithms. It is largely unclear what is the motive of the paper and what is the application. I will list down some of the issues below:

1. The theorems in section 3 are either results of previous works or are at best trivial facts. 

2. The theorems in section 4 are just basic algebraic manipulations. This paper thus lacks technical novelty.

3. The purpose of the introduction of the transform is unclear to me. There is no formal result showing the improvement in utility for a class of algorithms. The abstract claims their technique refines the utility, but this is illustrated using only 1 example and some basic calculations.

4. The abstract claims they study the effect of subsampling on the GDPT, but the only thing mentioned about subsampling is that it doesn't give any amplification.

Largely, I don't see any applicability of the transformation introduced in this paper.
summary_of_the_review: The paper lacks technical novelty and makes no real contribution/improvement to support the new transformation for characterizing introduced. Thus, I think it is not good enough for publication.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work is an investigation into the newly proposed Gaussian Differential privacy (GDP) in the context of existing formulations of epsilon, delta differential privacy (DP). Authors propose a novel framework for GDP transformation (GDPT) that analyses the properties of GDP and contrasts it to DP through the lens of the adversarial (head/tail composition) analysis, showing both theoretically and empirically that it results in better algorithmic utility. Authors provide a list of applications for GDPT and outline the benefits of this approach (primarily through tighter privacy bounds).

main_review: The work presents a comprehensive overview of the GDP in the context of privacy profiling, that is attempting to reduce the detrimental effects of DP on the results of algorithmic training. 

There are many interesting insights presented based on the results of a closer analysis of GDP in regards to its behaviour around the head/tail composition of the function through the lens of the novel formulation of GDPT (including experimentally shown tighter privacy analysis, resulting in better utility of the algorithm).

The motivation is very clear to me, as the existing formulations of DP are notoriously difficult to interpret by a non-specialist, require multiple parameters that are not easily defined in practise and provide guarantees that can be difficult to put into perspective. In addition, DP is known to be detrimental to the utility of the trained model, which a more carefully selected formulation (such as GDP) can partially mitigate. Therefore, I believe that this work is a needed step towards democratisation of privacy-preserving ML and a timely investigation into mitigations of DP’s detrimental effects to algorithmic training performance.

Major comments:

While the motivation behind the analysis of GDP is clear, the potential applications of the work (in general) are too, the take-home message of the findings is not. Is the key message of the paper that GDP gives tighter guarantees? Or that existing DP formulations are pessimistic and detrimental to utility? It is very difficult to assess the impact of the work, when there is no clear message on how and why it needs to be integrated into the existing workflows. To alleviate some of these issues I would suggest being much more explicit in the conclusion and contributions: in my eyes GDPT on its own is difficult to put into practical context. I do, however, acknowledge that Section 5 introduces how GDPT can be applied to existing notions, but in my opinion, this comes very late and the conclusions are very ad-hoc. There is no clear direction of how the insights from this work are meant to be interpreted and what the main message of the manuscript is.

In terms of content, my main concern here is the overall novelty of the work and the insights presented. There exists a similar line of work on the interpretation of GDP by Asoodeh et al. [1], that was published in March 2021 and presents an argument about the properties of GDP along with its relation to DP, and the associated effects on the privacy-utility trade-off. This work, however, was not cited or addressed in this manuscript. Similar things can be said about Bu et al.[2], which considers the application of GDP in the context of deep learning. Many of the insights seen in this work (e.g. the interpretation of GDP and its relation to DP in general) have already been presented in these two works and are thus hardly novel. While the goals of this work and [1] are tangential, and GDPT being based on DP analysis through the head/tail behaviour and not on a reinterpretation of other DP formulations and authors here consider Laplace mechanism rather than Gaussian, the conclusions these works present are very similar. 
I would like, therefore, to request that reviewers compare their contributions to the work by [1] and specify the novel conclusions that can be drawn from their work in comparison to the prior work. I am open to changing my review should the authors present a sound argument that their work derives additional insights when compared to the literature I linked and particularly, their implications for the wider scientific community.

[1] - Asoodeh, Shahab, et al. "Three variants of differential privacy: Lossless conversion and applications." IEEE Journal on Selected Areas in Information Theory 2.1 (2021): 208-222.
[2] - Bu, Zhiqi, et al. "Deep learning with Gaussian differential privacy." Harvard data science review 2020.23 (2020).

Another concern I have is a lack of any discussion on the Gaussian mechanism. As this paper is positioned to be applicable for ML practitioners, I find the scope of these findings rather limiting (especially if we were to consider deep learning) if only the Laplacian mechanism is considered due to its unfavourable composition properties. Moreover, I am unsure if it is enough to only assess Laplacian in the work that considers Gaussian DP and completely disregard the Gaussian mechanism. In general, I would like to see justification on why Laplace is the suitable choice here, as otherwise I am struggling to see the broader impact of this work and would, therefore, encourage authors to include some concrete applications of their work.

On this note, I would have expected a more detailed discussion on the applications of this work (or of DP in general) in the domain of ML specifically. I would encourage authors to expand their Section 5 and provide explicit applications of their work in this domain. 

The experimental results (Figure 1) could be explained better. The results are relatively straightforward, but the subsection comes unannounced and following the method of obtaining these was not straightforward.

Minor comments:
The actual novelty of the paper is not very clearly presented, the abstract contains a lot of information about GDPT’s details, so the actual contributions are diluted (and the same thing can be said about the introduction).  As a result, it is very difficult to determine the actual novel contributions that the work contains. I would suggest trimming the technical details down to make the contributions of the paper more convincing. 

Multiple issues with Definition 1.1:
 missing a less than or equals sign.
 does not specify the condition of ‘differ’: is this an add/remove a record or is it a replace a record?

summary_of_the_review: Overall, while I do believe that this paper tries to address a very important problem and is formally sound, I am not fully convinced that there is enough novelty in the existing manuscript to justify the acceptance and therefore I believe that this paper is just below the bar of acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: ## Summary of Contributions

This paper considers Gaussian differential privacy (GDP) notion which is an extension of $(\epsilon, \delta)$-differential privacy (DP). Roughly speaking, an algorithm is $\mu$-GDP if it is "at least as private as Gaussian mechanism with noise multiplier $1/\mu$". The main advantages of GDP are that (i) it has a simple and sharper composition theorem than $(\epsilon, \delta)$-DP and (ii) it has only a single parameter $\mu$ leading to simpler/more efficient computation compared to other DP notions that provide good composition (e.g. $f$-DP or Privacy Loss Distribution (PLD)).

This paper develops tools that can help understand/deploy GDP more easily. Specifically:
- They propose Gaussian Differential Privacy Transformation (GDPT) which roughly speaking is the curve $\mu: \mathbb{R} \to \mathbb{R}$ where $\mu(\epsilon)$ is the smallest $\epsilon$ for which the algorithm is at least as private as Gaussian mechanism of noise multiplier $1/\mu(\epsilon)$ at this particular value of $\epsilon$.
- With the above notion, they derive (in Theorems 4.3, 4.4) the condition for an algorithm to be $\mu$-GDP for some finite $\mu$: it must be $(\epsilon, \delta(\epsilon))$-DP where $\limsup \frac{\epsilon^2}{-\log \delta(\epsilon)}$ is finite.
- They then show how to approximately check whether an algorithm is GDP. Specifically, they show that it suffices to check a certain condition on a finite number of points (corresponding to an upper staircase in Figure 2 right). They show that if this condition holds the algorithm is $(\epsilon_h, \mu)$-head GDP, roughly meaning that it is "GDP" for all $\epsilon < \epsilon_h$.
- They argue that in practice taking $\epsilon_h$ to be sufficiently large should be enough. But they also give a "clip and noise" procedure to turn an $(\epsilon_h, \mu)$-head GDP algorithm into one which is actually $\mu$-GDP. 


Along the way, the paper also shows a new implication between $(\epsilon, \delta)$-DP and $(\epsilon', \delta')$-DP. Previously, it was known that the former implies the latter if $\epsilon' \geq \epsilon$ and $\delta' \geq \delta$. In Theorem 3.1 of this paper, the authors show that the implication may even hold when $\epsilon > \epsilon'$ but $\delta'$ also has to be larger than $\delta$ by a certain amount (depending on $\delta, \epsilon, \epsilon'$). The authors give some example in Section 5 where this relation gives non-trivial implications for some known algorithms.
main_review: ## Strengths
- This paper proposes a transformation and several auxiliary lemmas that may help make GDP more practical and more widely applicable.
- The non-trivial relationship between $(\epsilon, \delta)$-DP's is interesting.

## Weaknesses
- I do not believe that GDPT yields significant insight that cannot be drawn from the privacy profile curve itself. Specifically, almost all the applications can be derived via the latter as well. (More details are presented below in "Detailed Comments for Authors".)
- Although the paper claims to provide "engineering tools" for GDP, no evaluation is given. On this front, I think it is important to show e.g. how tight & how efficient GDP tools presented here are compared to other methods in literature such as Privacy Loss Distributions [Sommer et al., PETS 2019].
- The "utility improvement" from the non-trivial relationship between $(\epsilon, \delta)$-DP's does not seem that appealing. Specifically, the examples in the paper uses very high $\delta$ (all of them larger than $0.05$) which is not a value used anywhere in practice. (I have not seen any practical application where $\delta > 10^{-4}$.) Indeed, this does not seem like a coincidence: the new relation only seem useful for $\epsilon, \epsilon_0$ relatively close and $\delta, \delta_0$ relatively large (otherwise the additive term in $\delta_0$ would be too large).
- The non-trivial relationship between $(\epsilon, \delta)$-DP's also seems to be implicit in previous work. As an example, the paper "Optimal Accounting of Differential Privacy via Characteristic Function" by Zhu et al. has a characterization that says that the privacy curve must be convex (Lemma 11) when the x-axis is changed from $\epsilon$ to $e^{\epsilon}$. Using this convexity on $0, \epsilon_0, \epsilon$ also yields this characterization. I think this is a minor weakness since it is good for the statement to be written down in a more explicit form as is done here anyway.

## Detailed Comments for Authors
- *Regarding GDPT:*
  - Theorem 4.4 can be easily derived from Lemma A.1 by setting up $f(\epsilon) \leq \delta_\mu(\epsilon)$ for some $\mu$.
  - For Theorem 4.6, the staircase functions taken are equivalent to rounding up or down $\delta(\epsilon)$ in the privacy profile for all $\epsilon \in [x_i, x_{i + 1}]$ in each $i$. So the entire proof of Theorem 4.6 can also be derived as easily via the privacy profile curve as well.
  - Overall, I think it'd be better if you show an application of GDPT that would be much harder to derive under the privacy profile notion. Otherwise, I'm not sure why we should define yet another privacy curve in addition to the already many curves.

### Other More Minor Comments:
- Definition 1.1: missing $\leq$ in the equation.
- Page 2, paragraph before Section 1.1: $\sigma$ is not yet defined?
- Page 3, second example: isn't the Gaussian mechanism itself also an example of such a tradeoff?
- Page 3, third example: the ICEA algorithm of Ghazi et al. (2019) was actually proposed much earlier by Ishai et al. [FOCS 2006] in the paper " Cryptography from anonymity". See also the papers "Private Aggregation from Fewer Anonymous Messages" by Ghazi et al. [EUROCRYPT 2020] and "Private Summation in the Multi-Message Shuffle Model" by Balle et al. [CCS 2021] which give better analysis of ICEA compared to Ghazi et al. (2019).
- Page 3, third example: m in the ICEA algorithm is *not* maximum error but the number of messages (i.e. additive shares) per user.
- Page 5 Definition 3.2: it doesn't seem like the tail condition is used in a meaningful way (at least in the main body)? If so, then maybe there is no need to define it (at least in the main body).
- Page 6 before Theorem 4.1: "... the following theorems *formalizes* ..." -> "... the following theorems *formalize* ..."
summary_of_the_review: ## Recommendation

Overall, although I think this paper advances the understanding of GDP, I am unconvinced that GDPT yields significant novel insight that cannot be achieved otherwise and more empirical evaluations have to be made in order to determine the practicality of the tools proposed here. Due to this, I recommend rejection.
review_title: null

Meta-review: We thank the authors for their response. The reviewers agree that this paper provides contributions in automating privacy analyses under the Gaussian differential privacy (GDP) framework. The reviewers also pointed out several drawbacks of the paper. Most importantly, the reviewers do not find the presented applications to be convincing. In particular, the presented result can be much strengthened if the proposed method can lead to improved privacy analysis for more sophisticated algorithms such as DP-SGD across a wide regime of epsilon and delta. (In general, the privacy guarantee is very weak with delta bigger than 1/n.) Overall, the paper does not seem to provide enough evidence to showcase the usefulness of their proposed method.
Decision: Reject