Log-Concave and Multivariate Canonical Noise Distributions for Differential Privacy
Authors: Jordan Awan
Jinshuo Dong
Venue: NeurIPS 2022 Accept (2022)
Keywords: Gaussian differential privacy
tradeoff function
composition
group privacy

Abstract:  A canonical noise distribution (CND) is an additive mechanism designed to satisfy $f$-differential privacy ($f$-DP), without any wasted privacy budget. $f$-DP is a hypothesis testing-based formulation of privacy phrased in terms of tradeoff functions, which captures the difficulty of a hypothesis test. In this paper, we consider the existence and construction of both log-concave CNDs and multivariate CNDs. Log-concave distributions are important to ensure that higher outputs of the mechanism correspond to higher input values, whereas multivariate noise distributions are important to ensure that a joint release of multiple outputs has a tight privacy characterization. We show that the existence and construction of CNDs for both types of problems is related to whether the tradeoff function can be decomposed by functional composition (related to group privacy) or mechanism composition. In particular, we show that pure $\epsilon$-DP cannot be decomposed in either way and that there is neither a log-concave CND nor any multivariate CND for $\epsilon$-DP. On the other hand, we show that Gaussian-DP, $(0,\delta)$-DP, and Laplace-DP each have both log-concave and multivariate CNDs. 

Log-Coneave and Multivariate Canonical Noise Distributions for Differential Privacy
Jordan A. Awan Department of Statistics Purdue University jawandpurdue. edu
Jinshuo Dong Department of Computer Science Northwestern University and IDEAL"
inshuo@northveettern. edu
Abstract
A canonical noise distribution (CND) is an additive mechanism designed to satisfy f f-differential privacy (f-DP), without any wasted privacy budget. f-DP is hy- pothesis testing-based formulation of privacy phrased in terms of tradeoff functions, which captures the difficulty of a hypothesis test. In this paper, we consider the existence and construction of both log-concave CNDs and multivariate CNDs. Log-concave distributions are important to ensure that higher outputs of the mecha- nism correspond to higher input values, whereas multivariate noise distributions are important to ensure that joint release of multiple outputs has a tight privacy characterization. We show that the existence and construction of CNDs for both types of problems is related to whether the tradeoff function can be decomposed by functional composition (related to group privacy) mechanism composition. In particular, we show that pure c-DP cannot be decomposed in either way and that there neither log-concave CND nor any multivariate CND for e-DP. On the other hand, we show that Gaussian-DP. (0, 6)-DP, and Laplace-DP each have both log-coneave and multivariate CNDs.
Introduction
Differential privacy (DP), proposed by Dwork et al. (006), is the state-of-the-art framework in formal privacy protection and is being implemented by tech companies, government agencies, and academic institutions. Over time, the DP community has developed many new DP mechanisms as well as new frameworks. Recently, f-DP (Dong al. [2022] was proposed generalization of DP. allowing for tight calculations of group privacy, composition, subsampling, and post- post-processing. It was shown in Dong et al. [2222] that f-D provably the tightest version of DP that respects the post-processing property of DP. In particular, f-DP can be losslessly converted to Rényi-DP (or any f-divergence version of DP) as well as (c, DDD,, but not vice-versa Dong al. 2022 Furthermore. f-DP is equivalent (can be losslessly converted back and forth) to the privacy profile [Bllle et al. 2018 2020) and the privacy loss random variables [Sommer et al. 2019 Zhu et al. 2022].
f-DP is defined terms of tradeoff function or receiver operator curve (ROC), which encapsulates T(P, Q) is the
the difficulty of conducting hypothesis test between two distributions. If
tradeoff function for testing between the distributions and Q, then a mechanism M satisfies f-DP, this means that given the output of M when run on one of two adjacent databases, it least as hard to determine which database was used, as it is to test between / and Q.
While f-DP has the many desirable theoretical properties listed above in its favor, there limited techniques for working with f-DP, and few constructive mechanisms for an arbitrary f-DP guarantee. A notable exception canonical noise distribution (CND) from the recent paper (waan paan and Vadhan
The Institute for Data, Econometrics, Algorithms, and Learning
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2021], which builds one mne-dimensional additive noise mechanism designed to exactly satisfy f-DP, with no wasted privacy budget. Along with the intuitive idea that a CND is optimal in that optimizes the privacy loss budget, Awan and Vadhan [202]] showed that CNDs are crucial to the construction of optimal DP hypothesis tests and free DP p-values. However, the CND construction given in Awan and Vadhan (02T] does not result in smooth distribution, and in particular is not log-concave. Log- concavity is a desirable property because it implies that the distribution has a monotone likelihood ratio: this means that higher observed values are always more likely to have come from higher input value than a lower one. Log-concavity thus makes the DP output much more interpretable, easily analyzed, and also has makes the calculation of the privacy cost simpler (Dong et al., 2021 Furthermore, the results of Awan and Vadhan [222 are limited to 1-dimensional distributions.
In this paper, we develop new properties of CNDs and f-DP, motivated by the following two questions,
1. Can we construct log-coneave CNDs? 2. Can we construct multivariate CNDs?
Our Contributions
The existence of both log-concave 1-dimensional CNDs and multivariate CNDs intricately linked with properties related to group privacy and mechanism composition. Two highly desirable properties of a tradeoff function are infinite divisibility and infinite decomposability. meaning that the tradeoff function can be exactly achieved by n-fold group privacy or n-fold mechanism composition, respectively. We prove that a tradeoff function has a log-concave CND if and only if the tradeoff function is infinitely divisible, and give a construction for the unique log-concave CND in this case. We also show that if tradeoff function is either infinitely divisible or decomposable, then we can construct multivariate CND.
Along with the positive results listed above, we also include impossibility results. In particular, (c, DD- is neither divisible nor decomposable, and in fact has neither a log-concave CND nor any multivariate CND. In contrast to (c, D)- two families that satisfy both infinite divisibility and infinite decomposability are μ-GDP and (0, 8)-DP. While (0, 8)DP has limited applicability due to its weak protection for events with small probability, p-GDP and related DP definitions (such as zero concentrated DP) have been gaining popularity. The results of this paper provide a new perspective supporting the adoption of GDP as the default privacy measure instead of (e, O)-DP
Organization In Section 2. review concepts in f-DP and canonical noise distributions. In Section B we study I-dimensional CNDs. In Section 3.I we prove that the Tulap distribution is the unique CND for (c, -D... In Section 3.2 propose the concept of infinite divisibility and prove that a tradeoff function has a log-concave CND if and only if it is infinitely divisible; we also give a construction to produce the log-concave CND from family of infinitely divisible tradeoff' functions. We prove that piece-wise linear tradeoff functions are generally not infinitely divisible in Section 3.3 and in particular O)DD and several related tradeoff functions do not have log-concave CNDs. In Section + we propose a multivariate extension of CND. We give two general constructions of multivariate CNDs in Section 4.1 depending on whether tradcoff function is decomposable or infinitely divisible. We give several examples of multivariate CNDs in Sections 4.2 4.5) for Gaussian DP. (0, DDP (c, (DDP, and Laplace-DPF In Section 4.6 we show that there no multivariate CND for (e, 0) DD, which implies that (c. 0)-DP is not decomposable. We conclude with discussion in Section Proofs and technical details are found in the Appendix.
Related Work While there are many complex DP mechanisms, many use the fundamental building block of additive mechanisms (e.g., functional mechanism (Zhang al., 2012), objective perturbation
(Chaudhuri et al., 2011,, Kifer et al. 2012), stochastic gradient descent [Abadi et al.) 2016). and the sparse vector technique Dwork et al.) 2009 Zhu and Wang 2020). to name few). T There have been many different additive mechanisms proposed in the literature, for different privacy purposes. We highlight the works that show some optimality property for the proposed noise distributions. This work is most directly building off of]Awan and Vadhan 202T]. who proposed the concept of canonical noise distributions as method of quantifying what it means to fully use the privacy budget. There are also other works, which derive optimal mechanisms with respect to other metrics. Ghosh et al. [2122] showed that discrete Laplace distribution the universal utility maximizer for a general class of utility functions in pure-DP. Geng and Viswanath (2055)) proposed the staircase mechanism which they showed optimizes the E, or l2 error for pure-DP. DP. For (e, 6)-DP, Geng and Viswanath (2015a] showed that either the staircase or uniform distribution can achieve the optimal rate in terms of f and &g error, (Steinke and Ullman| (016) showed that the -mehhnniss is rate optimal when measuring utility in terms of L.x emror. Awan and Slavkovid 2020 derive optimal mechanisms
2

---

among the class of K-Nomm Mechanisms, proposed by Hardt and Talwar 2010 in terms of various scale-independent measures, for fixed statistic and sample size.
2 Differential privacy basics
Differential privacy ensures that given the output of a private mechanism, it difficult for an adversary to determine whether individual is present in the database or not. To satisfy DP, privacy expert employs a mechanism M, which is a set of probability distributions MD on a common space V, indexed by possible databases D E 9. Let d( (D,, D') be an integer-valuee metric on the space of databases 2, which represents the number of entries that D and D' differ in. We call D and D' adjacent if dd D*) S While there are now many variants of DP, they all center around the idea that given a randomized algorithm M, for any two adjacent databases D, D', the distributions of M (D) and (D') should be "similar." While many DP variants measure similarity in terms of divergences, f-DP formalizes similarity in terms of hypothesis tests. Intuitively, for two adjacent databases D and D', mechanism M satisfies f-DP if given the output of M, it is difficult to determine whether the original database was D or D'. This is formalized in terms tradeoff functions.
For two distributions P and Q. the tradeoff function (or ROC) between P and Q is T(P, Q) [0, 1] + [0, 1], where ((P, ()(a) = inf Eqo (o( 2 1 - a.. where the infinimum is over all measurable tests o. The tradcoff function returns the optimal type II error for testing Ho P versus H1 = Q at specificity (one minus type I error) o, and captures the difficulty of distinguishing between P and Q. A A function f: [0, 1] - [0. is tradeoff function if and only if f is convex, continuous, non-decreasing, and f(x) I x for all x E [o. 1] (Dong et al. 2022. Proposition 2.2]. We say that a tradeoff function f is nontrivial if faa
a for some a E (0, I).
Definition 2.1 (S-DP: Dong et al. 2022). Let be a tradeoff function. A mechanism M satisfies f-DP if (MM (D))) 2 f. for all D, D' E 9 which satisfy D') S 1.
Intuitively, mechanism satisfies S-DP, where ʃ - T(P, Q), if testing Ho MMD) versus H1 (DD) is at least as hard as testing Ho : P versus H1 : Q. Without loss of generality we can assume that ff is symmettic,, meaning that if f T(P, Q). then f T(Q, This is due to the fact that adjacency of databases is a symmetric relation [Dong et al. 2022 Proposition 2.4]. So, we limit the focus of this paper on symmetric tradeoff functions.
key property of differential privacy is that it also implies privacy guarantees for groups. Dong et al. 2022, Theorem 2.14] showed that if mechanism is f-DP, then it satisfies fDP-DP, when the adjacency measure changed to allow for a difference in entries (where foh means the functional composition of f with itself, k times). We call this group privacy, which is a central topic in differential privacy. Note that the bound for not necessarily the tightest privacy guarantee for a particular mechanism.
Mechanism Composition quantifies the cumulative privacy cost of the output of mechanisms. To express the tradeoff function resulting from composition, Dong et al. 2022 proposed the tensor product of tradeoff functions: if f = T(P.Q) and g (P.Q) Q') then f x g T(P x P', P.Q x Q'), which they show is well defined, commutative, and associative. They prove that if we have mechanisms MI...., Mg, which each satisfy fi fi-DP,
DD respectively, then the composition (MI.... Ms) satisfies fi @ ... & fx- (see Dong et al. 2022 Theorem 3.2] for more precise statement).
The traditional framework of (e, 6)- is a subclass of f-DP: Let e 2 0 and 8 E [0. A mechanism e exp(ee) -
satisfies (c, DD if it satisfies fe,s-DP, where fa) = max(0, 1-5 5-e e +
An important special case is (e, DD,,, which was the original definition of DP.
Another popular subclass is Gaussian-DP (GDP): For μ 2 0, a mechanism satisfies μ-GDP if it. satisfies G,, where G,, T(N N(,, 1)). Gaussian-DP was proposed in Dong et al. [002] and has several desirable properties, such as being closed under group privacy and closed under composition. Dong et al. [202 also established a central limit theorem for tradeoff functions as the number of compositions approaches infinity, showing that under general assumptions the tradeoff function of the composed mechanisms approaches G₁, for some
In Dong et al. 2022], the tradeoff function was originally defined as a function of type I error. Our choice to flip the tradeoff function along the a-a is for mathematical convenience. The ROC function is usually defined the power (one minus type II error) function of type I error.
3

---

2.1 Canonical noise distributions
To satisfy DP, additive mechanisms must introduce noise proportional the sensitivity of the statistic of interest. Let ||-|| be a norm on R A statistic S 9 + R has I-ll--ensittiviyy A > 0 if []S(D) - - I for all d(D, D') S 1. When d 1, we use . the default norm. Any additive mechanism, which releases S(D) + AN,, satisfies f-DP if T(N, N +w) > for all || < 1. The concept canonical noise distribution (CND) was proposed by Awan and Vadhan 2021 to capture when an additive mechanism satisfies f-DP, and "fully uses the privacy budget."
Definition 2.2 (Canonical noise distribution: Awan and Vadhan (2021), D. Let f be a symmetric
tradeoff function. A continuous random variable N with cumulative distribution function (edf) F is canonical noise distribution (CND) for f if
1. For any m [0, 1], T(N, N + m) 2 f.
2. f(a) (N,, N ()) for all (0,
3. T(N,N N () F(F-1(a) - 11 for all E (0, 1),
4. F(x)
F for all R; that is, N is symmetric about zero.
In Definition 2.2 property ensures that the additive mechanism using a CND satisfies f-DP, property 2 ensures that the privacy guarantee is tight, property 3 gives closed form for the tradeoff function in terms of the CND's cdf, which is equivalent to enforcing a monotone likelihood ratio property, and property 4 imposes symmetry which is mostly for convenience.
important property CNDs that they satisfy the following recurrence relation:
Lemma 2.3 (Awan and Vadhan (202T). Let be symmetric nontrivial tradeoff function and let F be a CND for f. Then F(x) = f(1 F(x - 1)) when F(x - 1) >> O and F F(x) = f(F(x+
when F(x + 1) 1.
In Awan and Vadhan [021]. they showed that the above recurrence relation can be used to construct CND for any nontrivial symmetric tradeoff function.
Proposition 2.4 (CND construction: Awan and Vadhan 202
Let f be symmetric nontrivial
tradeoff function, and let e [0, be the solution to f(1
c. We define Ff R - as
[[Ff(x +))
<< <1122
Fy(x)=
c(1/2- (1- (1-((-F((=-1))
-1/2 S 1/2
1/2.
Then N Fy a canonical noise distribution for f.
While Proposition 2.4 gives a general construction of CND for an arbitrary f. the resulting distribution is generally not smooth or log-concave, /Awan and Vadhan [021] showed that in the case of G,,, this construction does not recover the Gaussian distribution, which is the log-concave CND,
3 One-dimensional CNDs
In this section, we expand on the results of Awan and Vadhan (202] by producing new results for one-dimensional CNDs. In Section 3.1 we show that the Tulap distribution is the unique CND for (e, DD... In Section 3.2 we propose the concept of an infinitely divisible tradeoff function and show that a tradeoff function has a log-concave CND if and only if it is infinitely divisible. We also give a construction to produce the unique log- log-concave CND for an infinitely divisible family of tradeoff functions. In Section 3.33 we determine when piece-wise linear tradcoff function is divisible, and show that fe.o and related tradeoff functions are not infinitely divisible, and hence do not have log-concave CNDs.
CNDs for (c, O)DP 3.1
In Awan and Vadhan 202T], was shown that in general, the CND not unique, but was not clear whether there existed alternative CNDs for feo or fe,s We begin this section by showing that

---

the Tulap distribution, which was shown to be CND for fe,s by Awan and Vadhan [202]] is in fact the unique CND for fc.. The Tulap distribution was proposed by Awan and Slavković 2018 for the purpose of designing uniformly most powerful hypothesis tests for Bernoulli data. In the case of (c, O)-D, the Tulap distribution coincides with one of the staircase mechanisms [Geng and Viswanath, 2015b]. It is also closely related to the discrete Laplace distribution (also known as the geometric mechanism), which is optimal for a wide range of utility functions in Ghosh et al. 2012
Proposition 3.1. Let c > 0. The distribution Tolap(O, exp(-c), 0) is the unique CND for fe.0-
Sketch. By Lemma 2.3 the only choice CND is on 1-1/2, 1/2] If the density is non- constant on 1/2], wC show that the likelihood ratio is not bounded by e", violating e-D.. L
Proposition 1 is surprising result in that may expect more natural CND than the Tulap distribution, which has a discontinuous density. However, we now know that there are no other CNDs for (c, O). In particular, there is log-concave CND, which is the topic of the next subsection.
3.2 Infinite divisibility and log-concavity
It has been shown in Dong et al. 2022 and Dong et al. [002 that tradeoff functions built from location family log-concave distributions have very nice properties for f-DP. Log-concave distribu- tions are have a monotone likelihood ratio property which gives simple closed form expression for the tradcoff function in terms of the edf of the log-concave distribution. is easily observed that a tradeoff function with a log-concave CND satsifies a property that we call infinite divisibility. We prove that in fact tradeoff function has a log-concave CND if and only it is infinitely divisble. Our proof also results in construction to produce the unique log- log-concave CND.
continuous random variable X is log-concave if its density can be written as gx 9x(x) exp(C(a:).
where C' is a concave function. We call a (symmetric) tradeoff function f log-concave if there exists log-concave CND) N for f. Recall that if N ~ F is CND for f, then f(a) F(F-1((F) (a) 1). If
N is also log-concave then fe(o)) == (a) t) is a tradeoff function for every E [0, oo), and the family {f t [0, ] is a monoid satisfying the assumptions of Definition 3.2
Definition 3.2. A tradeoff function is infinitely divisible if there exists monoid, under the operation of functional composition, {fe E 3 2 0} containing f such that
1. f. o fa = fets for all s, t 220 0,
2. fe is nontrivial for all > and
3. f. fo Id as 4
The discussion above established that log-concave CNDs are infinitely divisible. The key result of this section is that tradeoff function is log-concave and only if it is infinitely divisible. We saw that it is easy construct the infinitely divisible family given a log-concave CND. Surprisingly, give a construction to derive the log- log-concave CND from the infinitely divisible family as well. This result shows intimate relationship between properties of a tradcoff function and the possible CNDs for that tradeoff function. We will see in Section 4.1 that the property of infinite divisibility shows up again in the construction of multivariate CNDs.
Theorem 3.3. A nontrivial tradeoff function f E F is log-concave if and only if it is infinitely divisible. In particular,
1. If f is log-concave with log-concave CND N F, then (fe 1 2 0} defined by ft F(F ((FF((a)= t) satisfies the assumptions of Definition 3.2
2. Let f be infinitely divisible. with monoid {ft E I 1t 0}, as defined in Definition 3.2
such that f= fr. Let F. be any CND for fo (such as constructed Proposition 2.4 Then the following limit exists (*(t)= == lim lim Ft() and N ~ F is the unique concccevvee CND for f. Furthermore, F* (st) is the unique log-concave CND for for all >
Proof Sketch. It is easy to verify property For property 2, we consider a subsequence 8, 1/n! and observe that (nlt) is CND for ff at every n, but that as increases, the number of points
5

---

NW
Figure 1: An illustration of Theorem 3.3 when applied to G1 T(N 1), (), From left to right, we have the density corresponding to Fag-n (2"t) for n = 0,3.
at which the CND is uniquely determined also increases, by Lemma 2.3 In the limit, this sequence converges to a unique cdf, which we show has the properties log-concave CND.
Example 3.4. We will illustrate the limit of Theorem 3.3 on G1- Let Fc,-. be the constructed edf from Proposition 2.4 for n = 0, 2, The density functions corresponding to Fc,-. (2*t) are plotted in Figure We that n increases, the pdfs approach that of standard normal, which know is the log-concave CND for f G1.
When the construction of Theorem 3.3 is applied to fe,o. the edf F* converges to Laplace edf. This seems to reflect the fact that under the limit of group privacy, (e, O)DD converges Laplace-DP
Dong al. 2022 Proposition 2.15].
Finally, we illustrate why properties 2 and of Definition 3.2 are necessary for Theorem 3.3
Example 3.5 (Non examples for Theorem 3.3). First consider why it is necessary to have f. + Id. Set [a) = ((a 1) for all > Note that fs ft fstts but that the construction of Theorem 3.3 results in point mass at zero, which is not CND as it is not continuous.
Next, suppose that all of the tradeoff functions are trivial, then fa(a) a for all >> 0, and f. o fi = fstt- However, there are no CNDs in this case.
3.3 Piece-wise linear tradeoff functions generally not infinitely divisible
We showed in Theorem 3.3 that if a tradeoff function is infinitely divisible, then we can construct log-concave CND. However, is not always obvious whether tradeoff function is infinitely divisible or not. We show that in the case of piece-wise linear tradeoff functions, we can upper bound the number of possible divisions terms of the number break points. In particular, the piece-wise linear tradeoff functions considered in this section are not infinitely divisible.
We characterize the piece-wise linear convex functions in terms of the 2nd derivative behavior: A convex function is piece-wise linear if and only if its 2nd derivative is defined everywhere except for finitely many points, and is zero whenever it is defined.
Part 1 of Proposition 3.6 shows that a piece-wise linear tradeoff function f. which satisfies f(x) = implies = 0, can be sub-divided only a finite number of times. A consequence of this is that fe, and several related tradeoff functions are not infinitely divisible and hence not have log-concave CNDs. In fact, not only is fe.o not infinitely divisible, but there is in fact no division fe,0 f o g into symmetric tradcoff functions, except where either f or g is the identity!
Proposition 3.6.
Let be a nontrivial piece-wise linear tradeoff function with 2 1 breakpoints and such that f(x) = 0 implies that x 0. Then there is tradeoff function such that (k+++) f-
2. Let There does not exist nontrivial symmetric tradeoff functions f1 and f2 such that fe.0 = f f2.
3. Let [ be the tradeoff function obtained by arbitrary sequence of mechanism compositions, functional compositions, or subsampling (without replacement) of Sc.o (could be different values for each). Then is not infinitely divisible and does not have log- concave CND.

---

Proof Sketch. We show in Lemma A.12 that divisions of piece-wise linear tradeoff function are themselves piece-wise linear, and that the functional composition of piece-wise linear tradeoff functions increases the number of breakpoints. This then limits the number of divisions piece- linear tradeoff function can have in terms of the number of its breakpoints.
Example 3.7 (fo.s s is log-concave). What if f(x) O does not imply that 0? The tradeoff functions fo.s fit within this setting, and the results of Proposition [36 do not apply here. In fact, fo.s is infinitely divisible with log-coneave CND U(-1/(20), (2 That is ʃo.s T(U U + +) where ~ U (-(1/22 1/2). While fe.5 for > 0 also does not satisfy the assumption that (x) implies 0, it is not clear at this time whether fc,8 is log-concave or not.
4 Multivariate CNDs
In this section, we generalize the definition of CND to dimensions greater than one. While in the univariate case, sensitivity is measured using the absolute distance between two statistic values, in R there are many choices of norms which can be used to measure the sensitivity [Awan and Slavković 2020]. So, will specify the sensitivity norm when talking about multivariate CND. In Definition we define a multivariate CND to be a natural generalization of properties 1-4 of Definition 2.2
Definition 4.1. Let be symmetric tradeoff function, and let ||-|| be norm on Rd A continuous random vector N with density is a canonical noise distribution (CND) for f. with respect to ||-|], if
1. For all v E Fd such that |||||| s 1 we have that T(N,N +)
2. there exists ||=0|| || < 1 such that T(N, N 0" (a) f()) for all 10,
3. for all n" which satisfy property 2, and all w E IRd, we have that the likelihood ratio g(w w + tv" - =")/((w to") is non-decreasing function of E R
4. N is symmetric about zero: g(z) g(=z) for all Rd.
When restricted
1, Definition 4. recovers Definition This is clear for properties 1, and 4. Property 3 of Definition 2.2 can be interpreted as requiring that optimal rejection set for T(N, N + 1) is of the [r, 30) for some x. By the Neyman Pearson Lemma, we know that this holds if and only if the likelihood ratio F'xx= 1)/F'(x)) is non-decreasing in ar. We see that when d = 1, property 3 of Definition 4.1 is equivalent to property 3 of Definition 2.2 We can interpret Property of Definition 4.1 as enforcing a monotone likelihood ratio in directions parallel to v*.
4.1 Constructions of multivariate CNDs
Composition gives simple method construct a multivariate CND whenever a tradeoff function can be decomposed into the composition of k tradeoff functions:
Proposition 4.2. Suppose that f fi & f2 1 ... & fo all be nontrivial and symmetric tradeoff functions, and let F1, F2,..., P&g be CNDs for f1,..., S'k respectively. Let N = (N1...., N₂) be the random vector where N₂ ~ F, are independent. Then N is CND for f with respect 11-1l
Interestingly, when a tradeoff function is infinitely divisible and hence has a log-concave CND by Theorem A.8 we can create multivariate CND with respect to Il-lla-sesiitivity
Theorem 4.3. Let ff be a nontrivial and symmetric log- tog-concave fraceoffuunctio function with log-concave CND F. Let N = (N1,...,Np N&) be the random vector where N, ~ F are independent. Then N is (log-concave) CND f with respect to 11-112--
Proof Sketch. Since the noise added is i.i.d., product of the individual tradeoff functions. We apply Theorem A.2 which lower bounds the tensor product of tradeoff functions with the functional composition.
rephrase the tradeoff function as the tensor
Theorem 3 was inspired by the i.i.d. Laplace mechanism. In Section 4.5
we show that the i.i.d. Laplace mechanism is special case of Theorem 4.3 and gives multivariate CND for Laplace-DP.
Note that Theorem results in a log-concave multivariate CND, and if each of Ni...., N₁ are log-concave in Proposition 2
then that constructed multivariate CND is log-concave as well. Dong

---

et a.. 2021 showed that log-concan concave distributions have many nice properties in multivariate settings as well. We leave future work to investigate when multivariate log-coneave CNDs exist.
4.2
Multivariate CND for GDP
Recall that if N [N, I) is d-dimensional Gaussian random vector, and v R any vector, then T(N.N NN + v) = TN (0, 1), .N (11el22 1)) [Dong et al. 2022, Proposition D.1(5).. This previous result implies that N (O, I) was multivariate CND for GDP under ||- |l-lle-sensittvity, In fact, we show in Proposition 4.4 that for GDP, any multivariate Gaussian is a CND with respect to any norm.
Proposition 4.4. Let be a d d positive definite matrix. Let v² argmax 1//1/22 Then (0, Σ) is a d-dimensional CND for ||X-1/2 -DDP with respect to the norm ||-I|-
Remark 4.5. While a multivariate Gaussian is always a multivariate CND for GDP, there is still possibly room for improvement. For Definition 4.1 we only need single vector to satisfy property 2. However, we could potentially ask that the bound is achieved at all u such that ||w|| = 1. Note that if ||||| is elliptical norm, then we do get this stronger property for the multivariate Gaussian, when we choose Σ to align with the sensitivity norm.
4.3 Multivariate CND for (0,8)-DP
First let's review a few facts about (0, d)-DP, also known as SD.. First, note that U -1 L) is
36 26
a (log-concave) CND for fo,s. So, we can write fo,s - TU, U + +0) where U U(- U(-1/2,1, 1/2). Because of this, we have that fa,5 is infinitely divisible, and fo.s, o f0.5 = f0.min(6r+ba.. Further- more, fu,6, @ fo.62 fo.1-(1-6))(--
as observed in Dong al. [2022]. This means that fo,5 also infinitely decomposable, a property that we had only seen for GDP before. This decomposability implies, by Proposition 4.2 that we can build multivariate CND for fo.s under selllc--ensstivityy In fact, this construction is multivariate CND for any sensitivity norm.
Proposition 4.6. Let
s d 2 1, and ||-|| be a norm on Rd. Call E arg min [
|
5) and A = IT --==1 (1 1)). Then U( 1 1 )² is a CND for fo.1-A under sellssennittiityy In 26
the special case of ||-I1 = |1- this simplifies to A = (1 - 5)5.
4.4 Multivariate CND for fe,s when 8 >
Let > () and 8 E (0, 1]. Recall that fe,6 = Sc,a @ Jo.5 Dong et al. 2022]
Since fo,s is infinitely
decomposable, we can write fes = fa. @ fu.o, Proposition 4.2 we construct multivariate CND for fe, with respect to -sensitiivyy by using
fu. where II (1 8.). By
(u, exp( exp(-e),0) 0) in one coordinate, and the uniform distributions U (-1 1 in the other k coordinates.
25, 25,
4.5 Two multivariate CNDs for Laplace-DP
Many mechanisms designed to satisfy (c, D)- actually satisfy the stronger privacy guarantee of Laplace-DD DP, In particular, variations the Laplace mechanism very common additive mecha- nisms used to achieve (e, DDP In this section, we show that two multivariate versions of the Laplace mechanism, the E and fo mechanisms, are multivariate CNDs for Laplace-DP.
The Laplace distribution, denoted Laplace(m, m, s) is a distribution on E with density 1 exp |x ml). We say mechanism satisfies e-Laplace-DP it satisfies D.P, where L. == T[N, N + and N Laplace 1). is easily seen that Laplace 1/e) is a log-concave CND for e-Laplace-DP.
2y
i.i.d. Laplace Mechanism The i.idd Laplace mechanism is defined as follows: Let c > 0 be given. 1 -enssitivvyy of A, then the i.i.d. Laplace mechanism releases T(X) + AN,
I 22' - R has
where N = (Ni...., .N)) ) is the random vector with i.i.d. entries N; ~ Laplace 1/c). It is well known that the i.i.d. Laplace mechanism satisfies fr.o-DP [Dwork et al. 2014 Theorem 3.6). Since N₁ is log-concave CND for L,, Theorem 4.3 shows that N is CND for Lt, with respect to [l-I]: -elsiiientt As T.e 2 Se.o and Ta) > (a))(a)) for some values of a, we can more precisely capture the privacy cost of the i.idd. Laplace mechanism using tradeoff functions rather than c-DP.
8

---

-oo-Mchhanism The -eechnnism proposed in Steinke and Ullman 2016 is special case of the K-norm mechanisms [Hardt and Talwar 2010 with density proportional to exp(-<l|==]>>) Steinke and Ullman 2016) showed that the to mechanism can improve the sample complexity of answering multiple queries, when accuracy is measured by foo-n [Awan and Slavković [2020] showed that the &or mechanism is near optimal in certain applications of private linear and logistic regression. It is well known that when using lo -sensitivity, the eo-- -eecannsm satisfies e-DP. In this section, we show that the &oo -mech is CND for Le, with respect to & -senitivity.
Proposition 4.7. Let 6 > O, and d 2 1. Let X be d-dimensional random vector with density expl -ellarl [mm) Then X is CND for the tradeoff function L. with respect to Il-Iloo-
g(x)
Proof Sketch. First show that with the shift of o*' (1, ... 1), the privacy loss random variable coincides with that of Le. Then, we show that v² = (1, 1, 1) is the worst case of any shift to minimize the tradcoff functions. To deal with the case that some of the entries of v are zero, we
establish convergence theorem for tradeoff functions in Theorem A.8 of the Appendix.
4.6
No multivariate CND for Se,0
By the construction of Proposition 2.4 we know that a one-dimensional CND exists for any nontrivial tradeoff function. It turns
that the same cannot be said for the multivariate setting. In Theorem we show that there is no multivariate CND for Se.o with respecl to any norm. In fact, we prove the stronger result that it is not even possible to satisfy properties I and of Definition 4.1
4.8
Theorem 4.8. Let d 2 2 and les ||-|| be any norm on I&d Then for any e > O, there is no random vector satisfying properties I and 2 of Definition 4.1 for fe,0 with respect to the norm [|- In particular, there is no multivariate CND for Je.0-
Proof Sketch. Suppose to the contrary. then (e, O)- imposes strict bounds on the likelihood ratio of the distribution. These bounds allow us to find an arbitrarily long sequence of points, sufficiently far apart, where the density is bounded below. This ultimately shows that the density is not integrable. I
Combining Theorem 4.8 with Proposition 4.2 we infer in Corollary 4.9 that fe. cannot be written as the tensor product of any nontrivial tradeoff functions. This means that if we want to design two independent mechanisms such that the joint release exactly satisfics (e, O)-D. then one of the mechanisms must be perfectly private.
Corollary 4.9. Let 0 be given. There does not exist nontrivial symmetric tradeoff functions fi and f2 such that fe,o = fi 8 fz.
Remark 4.10. Theorem 4.8 along with Theorem gives an alternative argument that fe, is not log-concave/infniitly decomposable.
5 Discussion
Motivated by the goals of constructing log-concave CNDs and multivariate CNDs, we found some fundamental connections between these constructions and the operations of mechanism composition and functional composition of the tradeoff functions. Surprisingly, the constructions for both log- concave and multivariate CNDs relied on whether tradeoff function could decomposed either according to functional composition, or according to mechanism composition. An interesting result of our work was that for (e, D) there is a unique I-dimensional CND and no multidimensional CNDs, which implies that fe.o can neither be decomposed according functional composition or mechanism composition. This highlights the limitations of pure-DP as privacy definition. On the other hand, Da Laplace-DP, and (0, 6D- were seen to have much better properties.
While the framework of GDP and related notions (e.g.. cero-concentrated DP) have many desirable properties, including those developed in this paper, there are still many reasons why one may be interested in other DP frameworks. In some applications, having stronger notion DP needed to protect events with small probability, such as pure-DP or Laplace-DP, in this case, our work shows that I Laplace-DP is a much better behaved notion of privacy than pure-DP. One may also propose other alternative DP definitions based on family of tradeoff functions, and our research gives some

---

fundamental insights on what properties that family must have in order for log-concave or multivariate CNDs be constructed.
We showed that a multivariate extension of CND can capture the same properties as in the 1- dimensional case. [Awan and Vadhan [201]] showed that in one dimension, CNDS can be used to obtain DP hypothesis tests with optimal properties. An open question is whether our definition of a multivariate CND has any connections to optimal hypothesis testing.
Most of the constructions of multivariate CNDs presented in this paper are product distributions. Even the multivariate CNDs for GDP are linear transformation of ii.d random variables. The so ---ehhannism is the exception, providing a truly nontrivial CND for Laplace-DR It is worth exploring whether there are general techniques to produce nontrivial multivariate CNDs like the me--hhcaasssm, as well as exploring the merits of such CNDs.
While many of the multivariate CNDs constructed for tradeoff functions, only held for specific sensitivity norms, a more general question would be on the existence and construction of multivariate CNDs for arbitrary tradeoff/norm pair.
Acknowledgments
This work was supported in part by NSF SES 2150615, awarded to Purdue University.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
Jordan Awan and Aleksandra Slavković. Differentially private uniformly most powerful tests for binomial data. Advances in Neural Information Processing Systems, 31, 2018.
Jordan Awan and Aleksandra Slavković. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, pages 1-20, 2020.
Jordan Awan and Salil Vadhan. Canonical noise distributions and private hypothesis tests. arXiv preprint 2 108. 04303, 2021.
Jordan Awan, Ana Kenney, Matthew Reimherr, and Aleksandra Slavković. Benefits and pitfalls of the exponential mechanism with applications Hilbert spaces and functional pca. In International Conference on Machine Learning, pages 374-384. PMLR, 2019.
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.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020.
Kamalika Chaudhuri, Claire Monteleoni, and Anand Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Jinshuo Dong, Weijie Su, and Linjun Zhang. A central limit theorem for differentially private query answering. Advances in Neural Information Processing Systems, 34, 2021.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B, 08 2022. doi: 10.1 l.ssss.......555 arXiv:1905.02385.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-fist annual ACM symposium on Theory of computing, pages 381-390, 2009.
10

---

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., 9(-44):21-400 2014.
Quan Geng and Pramod Viswanath. Optimal noise adding mechanisms for approximate differential privacy. IEEE Transactions on Information Theory, 62(2):952-966 2015a.
Quan Geng and Pramod Viswanath. The optimal noise-adding mechanism in differential privacy.
IEEE Transactions on Information Theory, 62(2)925-951, 2015b.
Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally malitt-maxiiizing privacy mechanisms. SIAM Journal on Computing, 41(6):1733-1993 2012.
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy, In Proceedings of the forty-second ACM symposium Theory of computing, pages 705-714, 2010.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
David M Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem differential privacy. Proceedings on privacy enhancing technologies, 2019(2): 245-269, 2019.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2):3 22, 2016.
Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winsleu.. Functional mechanism: Regression analysis under differential privacy. Proceedings of the VLDB Endowment, 5(11), 2012.
Yuqing Zhu and Yu-Xiang Wang. Improving sparse vector technique with renyi differential privacy. Advances in Neural Information Processing Systems, 33:20249-20258, 2020.
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.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Section S we discuss directions for future work.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section A. in the Appendix
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Included in the Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A] No experiments
were run, the results are justified by theory.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'l you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "yKOthk4FUVU", "reviewer": "Reviewer_yTW3", "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. \n\nOne 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. ", "questions": "I find the subsampling part of the following statement a bit unexpected (Proposition 3.6) :\n\"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.\"\n\nWhy is that statement included, what is its value? \n\nOn 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?\n\n\nComment: 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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- 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.\n\n- 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. \n\nWeaknesses:\n\n- 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.\n\n- Still I think quite limited contribution. This is a strong theory paper and DP community needs this ground work \n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ISJiVzVA5Z6", "reviewer": "Reviewer_B1pt", "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).", "questions": "In general I liked the paper and I think it has solid contributions.\n\nOne 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.\n\nSmall typos:\nabstract: Gaussian-DP. -> Gaussian-DP,\nline 140: |S(D)-S(D') | -> ||S(D)-S(D') ||", "limitations": "No apparent potential negative societal impact. Some technical limitations have been sufficiently discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.\n- 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.\n\nWeaknesses:\n- 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.\n- 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.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CYQRzA5_pOK", "reviewer": "Reviewer_RBrs", "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.", "questions": "Minor questions\n- What is $G_1$ in line 227?\n", "limitations": "Limitations and negative impact are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Understanding the optimal noise adding strategy is a fundamental theoretical problem for differential privacy. CND satisfies\n- This work extends previous work by showing the existence of log-concave CND in 1 dimension and give an equivalent condition (infinite divisibility)\n- 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.\n- Under the framework of $f$-DP, CNDs for various existing privacy notions are derived. The results draw connection to many existing DP mechanisms.\n- The writing is clear and well structured.\n\nWeakness\n- 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?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept