Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies distributions that can be used as additive noise mechanisms, which tightly/exactly satisfy f-differential privacy but also enjoy nice properties such as being log-concave or multivariate. Such tight distributions are called canonical noise distributions (CDNs) for f-DP. First, the paper gives a sufficient and necessary set of conditions on f for the existence of log-concave CNDs for f-DP and on the one hand proves that a CND for any piece-wise linear f as well as the unique CND for f_(epsilon,0) (pure DP) is not log-concave and on the other hand observes that f_(0,delta) is log-concave. Secondly, the paper extends the definition to multivariate CNDs and gives examples of CNDs for the special cases of f that corresponds to pure-, approximate-, (0,delta)-, Gaussian-, and Laplace-DP for different sensitivity norms (ell-1,2,infinity).
strengths_and_weaknesses: Strengths:
- f-DP is a general definition that can be translated to several DP definitions that see extended use. Given this generality, I think that the pursuit of optimal additive noise distributions (CNDs) (in the sense that they satisfy exactly the f-DP definition for some worst-case set of datasets) is useful and interesting.
- This paper gives concrete extensions over the first paper in this area, which defined CNDs and focused on univariate noise distributions. The extensions are two-fold. First, in studying for which types of f we can have log-concave CNDs for f-DP and providing examples and an impossibility result for pure DP. Second, in extending the definition to multivariate noise distributions. Both (log-concave and multivariate) are desirable properties of noise distributions used for DP, and especially the latter seems like an interesting direction for future work.

Weaknesses:
- The results on log-concave distributions seem more complete/conclusive but this is not the case for multivariate CNDs, which I think is the more interesting contribution, especially for DP high-dimensional statistics. However, I do think the examples provided are a good start and given that this paper is the first to extend the definition to the multivariate case and the log-concave conditions are fully characterized, this is a solid contribution as is.
- The paper builds directly on recent work and in a somewhat niche area. I think this along with the space constraints make for a quite dense paper that seems targeted to a rather small audience. I liked some choices in terms of the presentation (I appreciated the proof sketches and illustration) but in general it is easy to loose the big picture in the text. I think this is a minor issue.
questions: In general I liked the paper and I think it has solid contributions.

One suggestion I have for the presentation is to present the contributions more clearly in the introduction of the main paper, instead of mentioning them all in parallel with the organization. I think it would be clearer to break them down into the log-concave and multivariate results, and make some of the intuition about group privacy/composition, which is mentioned more vaguely before that, more clear.

Small typos:
abstract: Gaussian-DP. -> Gaussian-DP,
line 140: |S(D)-S(D') | -> ||S(D)-S(D') ||
limitations: No apparent potential negative societal impact. Some technical limitations have been sufficiently discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers f-DP and canonical noise distributions. f-DP is based on the concept of tradeoff functions which give an order for the distinguishability of pairs of random variables (Dong et al.) and is in a sense stronger notion than (eps,delta)-DP (is in a sense equivalent to privacy loss random variables and so called pairs of dominating distributions, however). Canonical noise distributions 'fill' a given f-DP profile by giving a noise adding mechanism which has exactly the f-DP distinguishability for pairs of additive-noise outputs (with given distance) (canonical noise distributions: Awan and Vadhan). The distributions of Awan and Vadhan are 'ugly', they can be e.g. discontinuous. Dong et al. show that 'nice' mechanisms are those where the noise has a log concave distribution. It is a natural question to ask, which f-DP profiles exhibit log concave canonical distributions and how do canonical noise distributions look for multivariate distributions. 

One of the weaknesses of DP is that it is hard to interpret and also a very hard topic for non-experts. GDP (and f-DP in general) is good in a sense that it is easy to understand (which one is more distinguishable) and easy to calculate with (simply add up the mu's). While accurate DP accountants and analyses are important, it is important to make DP as easily understand ( on a rigorous grounding) as possible. So in this perspective this line of work is really important. 
strengths_and_weaknesses: Strengths:

- Strong theory paper which continues this important line of work on f-DP. The math seems all correct and the writing is on a high level.

- Interesting connection between group privacy and compositions that has to hold (similar property holds particularly for GDP) for a tradeoff function f to have log concave canonical distributions. 

Weaknesses:

- The most practical looking results concern Gaussian DP and their novelty does not seem that big (e.g. covariance matrix Sigma in multivariate Gaussian noise corresponds to scaling the sensitivity appropriately). So I am not entirely sure whether the characterisations given by the paper will have that much practical value.

- Still I think quite limited contribution. This is a strong theory paper and DP community needs this ground work 


questions: I find the subsampling part of the following statement a bit unexpected (Proposition 3.6) :
"Let f be the tradeoff function obtained by an arbitrary sequence of mechanism compositions, functional compositions, or subsampling (without replacement) of $f_{\varepsilon,0}$ (could be different values for each). Then f is not infinitely divisible and so does not have a log-concave CND."

Why is that statement included, what is its value? 

On a related note, I was hoping to see some statements about subsampling. Can you comment: is there a way to characterise the subsampled versions of log concave trade off functions? The composition results would be then some CLT - based results as in case of GDP, right?


Comment: Typo, line 169: "In Section 3.1 that the Tulap distribution is the unique CND...."
limitations: From the applicability perspective the work is quite limited: as far as I see only the GDP related results are directly practical. However this is basic research so I don't see that as a big deficit.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work investigates canonical noise distributions (CND) of $f$-DP, a generalization of $(\epsilon, \delta) $-DP which characterizes the level of privacy by the hardness of hypothesis tests. CND is a family of distributions that satisfies $f$-DP with no loss in privacy budget. The authors prove the existence and infinite divisibility of log-concave CND and extend the notion of CND to high dimensions. Relations to other notions of DP, such as $(\epsilon, \delta) $-DP, Gaussian DP are also discussed.
strengths_and_weaknesses: Strengths
- Understanding the optimal noise adding strategy is a fundamental theoretical problem for differential privacy. CND satisfies
- This work extends previous work by showing the existence of log-concave CND in 1 dimension and give an equivalent condition (infinite divisibility)
- The authors provide a generalization of CND in higher dimensions and shows that CND can be easily constructed when the tradeoff function can be decomposed into $k$ components.
- Under the framework of $f$-DP, CNDs for various existing privacy notions are derived. The results draw connection to many existing DP mechanisms.
- The writing is clear and well structured.

Weakness
- For $(\epsilon, \delta)$-DP with $\delta > 0$, $\ell_2$ sensitivity is also used frequently. Can we say something about CND for $(\epsilon, \delta)$-DP with respect to $\ell_2$ sensitivity?
questions: Minor questions
- What is $G_1$ in line 227?

limitations: Limitations and negative impact are adequately addressed.
review_title: null

Meta-review: metareview: This paper provides conditions for the existence of log-concave multivariate distributions to satisfy f-differential privacy constraints. The results of the paper have the potential to be broadly applicable.  
confidence: Certain
Decision: Accept