Differential privacy (DP), proposed by Dwork et al. [2006], 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 et al. [2022] was proposed as a generalization of DP, allowing for tight calculations of group privacy, composition, subsampling, and post-processing. It was shown in Dong et al. [2022] that f -DP is 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 (✏, )-DP, but not vice-versa [Dong et al., 2022]. Furthermore, f -DP is equivalent (can be losslessly converted back and forth) to the privacy profile [Balle et al., 2018[Balle et al., , 2020] ] and the privacy loss random variables [Sommer et al., 2019, Zhu et al., 2022].
f -DP is defined in terms of a tradeoff function or receiver operator curve (ROC), which encapsulates the difficulty of conducting a hypothesis test between two distributions. If f = T (P, Q) is the tradeoff function for testing between the distributions P and Q, then if a mechanism M satisfies f -DP, this means that given the output of M when run on one of two adjacent databases, it is at least as hard to determine which database was used, as it is to test between P and Q.
While f -DP has the many desirable theoretical properties listed above in its favor, there are limited techniques for working with f -DP, and few constructive mechanisms for an arbitrary f -DP guarantee. A notable exception is a canonical noise distribution (CND) from the recent paper Awan and Vadhan [2021], which builds a one-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 it optimizes the privacy loss budget, Awan and Vadhan [2021] 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 [2021] does not result in a smooth distribution, and in particular is not log-concave. Logconcavity 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 a 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 [2021] 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-concave CNDs?
2. Can we construct multivariate CNDs?
Our Contributions The existence of both log-concave 1-dimensional CNDs and multivariate CNDs are 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 a tradeoff function is either infinitely divisible or decomposable, then we can construct a multivariate CND.
Along with the positive results listed above, we also include impossibility results. In particular, (✏, 0)-DP is neither divisible nor decomposable, and in fact has neither a log-concave CND nor any multivariate CND. In contrast to (✏, 0)-DP, two families that satisfy both infinite divisibility and infinite decomposability are µ-GDP and (0, )-DP. While (0, )-DP has limited applicability due to its weak protection for events with small probability, µ-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 (✏, 0)-DP.
Organization In Section 2, we review concepts in f -DP and canonical noise distributions. In Section 3, we study 1-dimensional CNDs. In Section 3.1, we prove that the Tulap distribution is the unique CND for (✏, 0)-DP. In Section 3.2, we 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 a 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 (✏, 0)-DP and several related tradeoff functions do not have log-concave CNDs.
In Section 4, we propose a multivariate extension of CND. We give two general constructions of multivariate CNDs in Section 4.1 depending on whether a tradeoff function is decomposable or infinitely divisible. We give several examples of multivariate CNDs in Sections 4.2-4.5 for Gaussian DP, (0, )-DP, (✏, )-DP, and Laplace-DP. In Section 4.6, we show that there is no multivariate CND for (✏, 0)-DP, which implies that (✏, 0)-DP is not decomposable. We conclude with discussion in Section 5. 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 et 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 andWang, 2020], to name a few). 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 [2021], who proposed the concept of canonical noise distributions as a 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. [2012] showed that a discrete Laplace distribution is the universal utility maximizer for a general class of utility functions in pure-DP. Geng and Viswanath [2015b] proposed the staircase mechanism which they showed optimizes the `1 or `2 error for pure-DP. For (✏, )-DP, Geng and Viswanath [2015a] showed that either the staircase or a uniform distribution can achieve the optimal rate in terms of `1 and `2 error. Steinke and Ullman [2016] showed that the `1-mechanisms is rate optimal when measuring utility in terms of `1 error. Awan and Slavković [2020] derive optimal mechanisms among the class of K-Norm Mechanisms, proposed by Hardt and Talwar [2010], in terms of various scale-independent measures, for a fixed statistic and sample size.
Differential privacy ensures that given the output of a private mechanism, it is difficult for an adversary to determine whether an individual is present in the database or not. To satisfy DP, a privacy expert employs a mechanism M , which is a set of probability distributions M D on a common space Y , indexed by possible databases D 2 D. Let d(D, D 0 ) be an integer-valued metric on the space of databases D, which represents the number of entries that D and D 0 differ in. We call D and D 0 adjacent if d(D, D 0 ) 1. 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 0 , the distributions of M (D) and M (D 0 ) 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 0 , a mechanism M satisfies f -DP if given the output of M , it is difficult to determine whether the original database was D or D 0 . This is formalized in terms tradeoff functions.
For two distributions P and Q, the tradeoff function (or ROC) between P and
Intuitively, a mechanism satisfies f -DP, where
. 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.
A key property of differential privacy is that it also implies privacy guarantees for groups. Dong et al. [2022, Theorem 2.14] showed that if a mechanism is f -DP, then it satisfies f k -DP, when the adjacency measure is changed to allow for a difference in k entries (where f k 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 f k is not necessarily the tightest privacy guarantee for a particular mechanism.
Mechanism Composition quantifies the cumulative privacy cost of the output of k 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 0 , Q 0 ), then f ⌦ g := T (P ⇥ P 0 , Q ⇥ Q 0 ), which they show is well defined, commutative, and associative. They prove that if we have Dong et al. [2022, Theorem 3.2] for a more precise statement).
The traditional framework of (✏, )-DP is a subclass of f -DP: Let ✏ 0 and 2
An important special case is (✏, 0)-DP, which was the original definition of DP.
Another popular subclass is Gaussian-DP (GDP): For µ 0, a mechanism satisfies µ-GDP if it satisfies G µ -DP, where G µ = T (N (0, 1), N(µ, 1)). Gaussian-DP was proposed in Dong et al. [2022] and has several desirable properties, such as being closed under group privacy and closed under composition. Dong et al. [2022] 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 µ.
To satisfy DP, additive mechanisms must introduce noise proportional to the sensitivity of the statistic of
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]). Let f be a symmetric tradeoff function. A continuous random variable
In Definition 2.2, property 1 ensures that the additive mechanism using a CND satisfies f -DP, property 2 ensures that the privacy guarantee is tight, property 3 gives a 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.
An important property of CNDs is that they satisfy the following recurrence relation: (Awan and Vadhan [2021]). Let f be a symmetric nontrivial tradeoff function and let F be a CND for f . Then
In Awan and Vadhan [2021], they showed that the above recurrence relation can be used to construct a CND for any nontrivial symmetric tradeoff function.
Proposition 2.4 (CND construction: Awan and Vadhan [2021]). Let f be a symmetric nontrivial tradeoff function, and let c 2 [0, 1] be the solution to f (1 c) = c. We define F f : R ! R as
x > 1/2.
Then N ⇠ F f is a canonical noise distribution for f . While Proposition 2.4 gives a general construction of a CND for an arbitrary f , the resulting distribution is generally not smooth or log-concave. Awan and Vadhan [2021] showed that in the case of G µ , this construction does not recover the Gaussian distribution, which is the log-concave CND.
In this section, we expand on the results of Awan and Vadhan [2021], by producing new results for one-dimensional CNDs. In Section 3.1, we show that the Tulap distribution is the unique CND for (✏, 0)-DP. 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-concave CND for an infinitely divisible family of tradeoff functions. In Section 3.3, we determine when a piece-wise linear tradeoff function is divisible, and show that f ✏,0 and related tradeoff functions are not infinitely divisible, and hence do not have log-concave CNDs.
In Awan and Vadhan [2021], it was shown that in general, the CND is not unique, but it was not clear whether there existed alternative CNDs for f ✏,0 or f ✏, . We begin this section by showing that the Tulap distribution, which was shown to be a CND for f ✏, by Awan and Vadhan [2021] is in fact the unique CND for f ✏,0 . 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 (✏, 0)-DP, 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 ✏ > 0. The distribution Tulap(0, exp( ✏), 0) is the unique CND for f ✏,0 .
Proof Sketch. By Lemma 2.3, the only choice in a CND is on [ 1/2, 1/2]. If the density is nonconstant on [ 1/2, 1/2], we show that the likelihood ratio is not bounded by e ✏ , violating ✏-DP.
Proposition 3.1 is a surprising result in that one may expect a more natural CND than the Tulap distribution, which has a discontinuous density. However, we now know that there are no other CNDs for (✏, 0)-DP. In particular, there is no log-concave CND, which is the topic of the next subsection.
It has been shown in Dong et al. [2022] and Dong et al. [2021] that tradeoff functions built from location family log-concave distributions have very nice properties for f -DP. Log-concave distributions are have a monotone likelihood ratio property which gives a simple closed form expression for the tradeoff function in terms of the cdf of the log-concave distribution. It 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 a tradeoff function has a log-concave CND if and only if it is infinitely divisble.
Our proof also results in a construction to produce the unique log-concave CND.
A continuous random variable X is log-concave if its density can be written as g X (x) / exp(C(x)), where C is a concave function. We call a (symmetric) tradeoff function f log-concave if there exists a log-concave CND N for f . Recall that if
) is a tradeoff function for every t 2 [0, 1), and the family {f t | t 2 [0, 1)} is a monoid satisfying the assumptions of Definition 3.2.
Definition 3.2. A tradeoff function f is infinitely divisible if there exists a monoid, under the operation of functional composition, {f t 2 F | t 0} containing f such that 1. f t f s = f t+s for all s, t 0, 2. f s is nontrivial for all s > 0, and 3. f s ! f 0 = Id as s # 0.
The discussion above established that log-concave CNDs are infinitely divisible. The key result of this section is that a tradeoff function is log-concave if and only if it is infinitely divisible. We saw that it is easy to construct the infinitely divisible family given a log-concave CND. Surprisingly, we give a construction to derive the log-concave CND from the infinitely divisible family as well. This result shows an intimate relationship between properties of a tradeoff 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 2 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 {f t | t 0} defined by f t = F (F 1 (↵) t) satisfies the assumptions of Definition 3.2.
2. Let f be infinitely divisible, with monoid {f t 2 F | t 0}, as defined in Definition 3.2, such that f = f 1 . Let F s be any CND for f s (such as constructed in Proposition 2.4). Then the following limit exists F ⇤ (t) := lim s!0 F s ( 1 s t) and N ⇠ F ⇤ is the unique log-concave CND for f . Furthermore, F ⇤ (st) is the unique log-concave CND for f s , for all s > 0.
Proof Sketch. It is easy to verify property 1. For property 2, we consider a subsequence s n = 1/n! and observe that F 1/n! (n!t) is a CND for f at every n, but that as n increases, the number of points From left to right, we have the density corresponding to F G 2 n (2 n t) for n = 0, 1, 2, 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 of a log-concave CND.
Example 3.4. We will illustrate the limit of Theorem 3.3 on G 1 . Let F G 2 n be the constructed cdf from Proposition 2.4 for n = 0, 1, 2, 3. The density functions corresponding to F G 2 n (2 n t) are plotted in Figure 1. We see that as n increases, the pdfs approach that of a standard normal, which we know is the log-concave CND for f = G 1 .
When the construction of Theorem 3.3 is applied to f ✏,0 , the cdf F ⇤ converges to a Laplace cdf. This seems to reflect the fact that under the limit of group privacy, (✏, 0)-DP converges to Laplace-DP Dong et al. [2022, Proposition 2.15].
Finally, we illustrate why properties 2 and 3 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 s ! Id. Set f s (↵) = I(↵ = 1) for all s > 0. Note that f s f t = f s+t , but that the construction of Theorem 3.3 results in a point mass at zero, which is not a CND as it is not continuous.
Next, suppose that all of the tradeoff functions are trivial, then f s (↵) = ↵ for all s > 0, and f s f t = f s+t . However, there are no CNDs in this case.
We showed in Theorem 3.3 that if a tradeoff function is infinitely divisible, then we can construct a log-concave CND. However, it is not always obvious whether a 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 in terms of the number of break points. In particular, the piece-wise linear tradeoff functions considered in this section are not infinitely divisible.
We can 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) = 0 implies x = 0, can be sub-divided only a finite number of times. A consequence of this is that f ✏,0 and several related tradeoff functions are not infinitely divisible and hence do not have log-concave CNDs. In fact, not only is f ✏,0 not infinitely divisible, but there is in fact no division f ✏,0 = f g into symmetric tradeoff functions, except where either f or g is the identity! Proposition 3.6.
1. Let f be a nontrivial piece-wise linear tradeoff function with k 1 breakpoints and such that f (x) = 0 implies that x = 0. Then there is no tradeoff function g such that g (k+1) = f . 2. Let ✏ > 0. There does not exist nontrivial symmetric tradeoff functions f 1 and f 2 such that f ✏,0 = f 1 f 2 .
3. Let f be the tradeoff function obtained by an arbitrary sequence of mechanism compositions, functional compositions, or subsampling (without replacement) of f ✏,0 (could be different ✏ values for each). Then f is not infinitely divisible and so does not have a log-concave CND.
Proof Sketch. We show in Lemma A.12 that divisions of a 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 a piece-wise linear tradeoff function can have in terms of the number of its breakpoints.
Example 3.7 (f 0, is log-concave). What if f (x) = 0 does not imply that x = 0? The tradeoff functions f 0, fit within this setting, and the results of Proposition 3.6 do not apply here. In fact, f 0, is infinitely divisible with log-concave CND U ( 1/(2 ), 1/(2 )). That is f 0, = T (U, U + ) where U ⇠ U ( 1/2, 1/2). While f ✏, for > 0 also does not satisfy the assumption that f ✏, (x) implies x = 0, it is not clear at this time whether f ✏, is log-concave or not.
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 d , there are many choices of norms which can be used to measure the sensitivity [Awan and Slavković, 2020]. So, we will specify the sensitivity norm when talking about a multivariate CND. In Definition 4.1 we define a multivariate CND to be a natural generalization of properties 1-4 of Definition 2.2.
Definition 4.1. Let f be a symmetric tradeoff function, and let k•k be a norm on R d . A continuous random vector N with density g is a canonical noise distribution (CND) for f , with respect to k
3. for all v ⇤ which satisfy property 2, and all w 2 R d , we have that the likelihood ratio g(w
When restricted to d = 1, Definition 4.1 recovers Definition 2.2. This is clear for properties 1, 2, and 4. Property 3 of Definition 2.2 can be interpreted as requiring that an optimal rejection set for T (N, N + 1) is of the [x, 1) for some x. By the Neyman Pearson Lemma, we know that this holds if and only if the likelihood ratio F 0 (x 1)/F 0 (x) is non-decreasing in x. 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 3 of Definition 4.1 as enforcing a monotone likelihood ratio in directions parallel to v ⇤ .
Composition gives a simple method to construct a multivariate CND whenever a tradeoff function can be decomposed into the composition of k tradeoff functions:
all be nontrivial and symmetric tradeoff functions, and let F 1 , F 2 , . . . , F k be CNDs for f 1 , . . . , f k respectively. Let N = (N 1 , . . . , N k ) be the random vector where
Interestingly, when a tradeoff function is infinitely divisible and hence has a log-concave CND by Theorem A.8, we can create a multivariate CND with respect to k•k 1 -sensitivity.
Theorem 4.3. Let f be a nontrivial and symmetric log-concave tradeoff function with log-concave CND F . Let N = (N 1 , . . . , N k ) be the random vector where N i ⇠ F are independent. Then N is a (log-concave) CND for f with respect to k•k 1 .
Proof Sketch. Since the noise added is i.i.d., we can rephrase the tradeoff function as the tensor product of the individual tradeoff functions. We apply Theorem A.2 which lower bounds the tensor product of tradeoff functions with the functional composition.
Theorem 4.3 was inspired by the i.i.d. Laplace mechanism. In Section 4.5, we show that the i.i.d. Laplace mechanism is a special case of Theorem 4.3 and gives a multivariate CND for Laplace-DP.
Note that Theorem 4.3 results in a log-concave multivariate CND, and if each of N 1 , . . . , N k are log-concave in Proposition 4.2, then that constructed multivariate CND is log-concave as well. Dong et al. [2021] showed that log-concave distributions have many nice properties in multivariate settings as well. We leave it to future work to investigate when multivariate log-concave CNDs exist.
Recall that if N ⇠ N (0, I) is a d-dimensional Gaussian random vector, and v 2 R d is any vector, then T (N, N + v) = T (N (0, 1), N(kvk 2 , 1)) [Dong et al., 2022, Proposition D.1(5)]. This previous result implies that N (0, I) was a multivariate CND for GDP under k•k 2 -sensitivity. 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 ⇤ 2 argmax kuk1 k⌃ 1/2 uk 2 . Then N (0, ⌃) is a d-dimensional CND for k⌃ 1/2 v ⇤ k 2 -GDP with respect to the norm k•k.
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 a single vector to satisfy property 2. However, we could potentially ask that the bound is achieved at all u such that kuk = 1. Note that if k•k is an 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, )-DP First let's review a few facts about (0, )-DP, also known as f 0, -DP. First, note that U ( 1 2 , 1 2 ) is a (log-concave) CND for f 0, . So, we can write f 0, = T (U, U + ) where U ⇠ U ( 1/2, 1/2). Because of this, we have that f 0, is infinitely divisible, and f 0, Dong et al. [2022]. This means that f 0, is also infinitely decomposable, a property that we had only seen for GDP before. This decomposability implies, by Proposition 4.2 that we can build a multivariate CND for f 0, under k•k 1 -sensitivity. In fact, this construction is a multivariate CND for any sensitivity norm.
4.4 Multivariate CND for f ✏, when > 0
Let ✏ > 0 and 2 (0, 1]. Recall that f ✏, = f ✏,0 ⌦ f 0, [Dong et al., 2022]. Since f 0, is infinitely decomposable, we can write
. By Proposition 4.2 we construct a multivariate CND for f ✏, with respect to k•k 1 -sensitivity by using Tulap(0, exp( ✏), 0) in one coordinate, and the uniform distributions U ( 1 2 i , 1 2 i ) in the other k coordinates.
Many mechanisms designed to satisfy (✏, 0)-DP actually satisfy the stronger privacy guarantee of Laplace-DP. In particular, variations on the Laplace mechanism are very common additive mechanisms used to achieve (✏, 0)-DP. In this section, we show that two multivariate versions of the Laplace mechanism, the `1 and `1 mechanisms, are multivariate CNDs for Laplace-DP.
The Laplace distribution, denoted Laplace(m, s) is a distribution on R with density 1 2s exp( 1 s |x m|). We say a mechanism satisfies ✏-Laplace-DP if it satisfies L ✏ -DP, where L ✏ := T (N, N + ✏) and N ⇠ Laplace(0, 1). It is easily seen that Laplace(0, 1/✏) is a log-concave CND for ✏-Laplace-DP. i.i.d. Laplace Mechanism The i.i.d. Laplace mechanism is defined as follows: Let ✏ > 0 be given. If T : X ! R k has k•k 1 -sensitivity of , then the i.i.d. Laplace mechanism releases T (X) + N , where N = (N 1 , . . . , N k ) is the random vector with i.i.d. entries N i ⇠ Laplace(0, 1/✏). It is well known that the i.i.d. Laplace mechanism satisfies f ✏,0 -DP [Dwork et al., 2014, Theorem 3.6]. Since N 1 is a log-concave CND for L ✏ , Theorem 4.3 shows that N is a CND for L ✏ , with respect to k•k 1 -sensitivity. As L ✏ f ✏,0 and L ✏ (↵) > f ✏,0 (↵) for some values of ↵, we can more precisely capture the privacy cost of the i.i.d. Laplace mechanism using tradeoff functions rather than ✏-DP.
`1-Mechanism The `1-mechanism, proposed in Steinke and Ullman [2016] is a special case of the K-norm mechanisms [Hardt and Talwar, 2010], with density proportional to exp( ✏kxk 1 ). Steinke and Ullman [2016] showed that the `1 mechanism can improve the sample complexity of answering multiple queries, when accuracy is measured by `1-norm. Awan and Slavković [2020] showed that the `1 mechanism is near optimal in certain applications of private linear and logistic regression. It is well known that when using `1-sensitivity, the `1-mechanism satisfies ✏-DP. In this section, we show that the `1-mech is a CND for L ✏ , with respect to `1-sensitivity. Proposition 4.7. Let ✏ > 0, and d 1. Let X be a d-dimensional random vector with density
. Then X is a CND for the tradeoff function L ✏ with respect to k•k 1 .
Proof Sketch. First we show that with the shift of v ⇤ = (1, 1, . . . , 1), the privacy loss random variable coincides with that of L ✏ . Then, we show that v ⇤ = (1, 1, . . . , 1) > is the worst case of any shift v to minimize the tradeoff functions. To deal with the case that some of the entries of v are zero, we establish a convergence theorem for tradeoff functions in Theorem A.8 of the Appendix. . Then for any ✏ > 0, there is no random vector satisfying properties 1 and 2 of Definition 4.1 for f ✏,0 with respect to the norm k•k. In particular, there is no multivariate CND for f ✏,0 .
Proof Sketch. Suppose to the contrary, then (✏, 0)-DP 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.
Combining Theorem 4.8 with Proposition 4.2, we infer in Corollary 4.9 that f ✏,0 cannot be written as the tensor product of any two nontrivial tradeoff functions. This means that if we want to design two independent mechanisms such that the joint release exactly satisfies (✏, 0)-DP, then one of the mechanisms must be perfectly private.
Corollary 4.9. Let ✏ > 0 be given. There does not exist nontrivial symmetric tradeoff functions f 1 and f 2 such that f ✏,0 = f 1 ⌦ f 2 . Remark 4.10. Theorem 4.8 along with Theorem 4.3 gives an alternative argument that f ✏,0 is not log-concave/infinitely decomposable.
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 logconcave and multivariate CNDs relied on whether a tradeoff function could be decomposed either according to functional composition, or according to mechanism composition. An interesting result of our work was that for (✏, 0)-DP there is a unique 1-dimensional CND and no multidimensional CNDs, which implies that f ✏,0 can neither be decomposed according to functional composition or mechanism composition. This highlights the limitations of pure-DP as a privacy definition. On the other hand, Gaussian-DP, Laplace-DP, and (0, )-DP were seen to have much better properties.
While the framework of GDP and related notions (e.g., zero-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 a stronger notion of DP is needed to protect events with small probability, such as pure-DP or Laplace-DP; in this case, our work shows that Laplace-DP is a much better behaved notion of privacy than pure-DP. One may also propose other alternative DP definitions based on a 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 to be constructed.
We showed that a multivariate extension of CND can capture the same properties as in the 1dimensional case. Awan and Vadhan [2021] 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 a linear transformation of i.i.d. random variables. The `1-mechanism is the exception, providing a truly nontrivial CND for Laplace-DP. It is worth exploring whether there are general techniques to produce nontrivial multivariate CNDs like the `1-mechansism, 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 be on the existence and construction of multivariate CNDs for an arbitrary tradeoff/norm pair.
InDong 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 x-axis is for mathematical convenience. The ROC function is usually defined as the power (one minus type II error) as a function of type I error.