We introduce Concentrated Differential Privacy, a relaxation of Differential Privacy enjoying better accuracy than both pure differential privacy and its popular "(ε, δ)" relaxation without compromising on cumulative privacy loss over multiple computations. The Fundamental Law of Information Recovery states, informally, that "overly accurate" estimates of "too many" statistics completely destroys privacy ([DN03] et sequelae). Differential privacy is a mathematically rigorous definition of privacy tailored to analysis of large datasets and equipped with a formal measure of privacy loss [DMNS06, Dwo06] . Moreover, differentially private algorithms take as input a parameter, typically called ε, that caps the permitted privacy loss in any execution of the algorithm and offers a concrete privacy/utility tradeoff. One of the strengths of differential privacy is the ability to reason about cumulative privacy loss over multiple analyses, given the values of ε used in each individual analysis. By appropriate choice of ε it is possible to stay within the bounds of the Fundamental Law while releasing any given number of estimated statistics; however, before this work the bounds were not tight. Roughly speaking, differential privacy ensures that the outcome of any anlysis on a database x is distributed very similarly to the outcome on any neighboring database y that differs from x in just one row (Definition 2.3). That is, differentially private algorithms are randomized, and in particular the max divergence between these two distributions (a sort maximum log odds ratio for any event; see Definition 2.2 below) is bounded by the privacy parameter ε. This absolute guarantee on the maximum privacy loss is now sometimes referred to as "pure" differential privacy. A popular relaxation, (ε, δ)-differential privacy (Definition 2.4) [DKM + 06], guarantees that with probability at most 1 − δ the privacy loss does not exceed ε. 1 Typically δ is taken to be "cryptographically" small, that is, smaller than the inverse of any polynomial in the size of the dataset, and pure differential privacy is simply the special case in which δ = 0. The relaxation frequently permits asymptotically better accuracy than pure differential privacy for the same value of ε, even when δ is very small. What happens in the case of multiple analyses? While the composition of k (ε, 0)-differentially privacy algorithms is at worst (kε, 0)-differentially private, it is also simultaneously ( 2k ln(1/δ)ε+ kε(e ε − 1), δ)-differentially private for every δ [DRV10]. Let us deconstruct the statement of this result. First, privacy loss is a random variable that captures differences in the probability distributions obtained when a randomized algorithm M is run on x as opposed to neighboring database y (see Section 2.1). In general, if the max divergence between two distributions is bounded by ε 1 Note that the probability is over the coins of the algorithm performing the analysis. The above formulation is not immediate from the definition of (ε, δ)-differential privacy, this was proved in the full version of [DRV10] . 1 then their KL-divergence (Definition 2.1) is bounded by ε(e ε − 1). This means that the expected privacy loss for a single (ε, 0)-differentially private computation is bounded by ε(e ε − 1). By linearity of expectation, the expected loss over k (ε, 0)-differentially private algorithms is bounded by kε(e ε − 1). The statement therefore says that the cumulative privacy loss random variable over k computations is tightly concentrated about its mean: the probability of privacy loss exceeding its expectation by t √ kε falls exponentially in t 2 /2 for all t ≥ 0. We will return to this formulation presently. More generally, we prove the following Advanced Composition theorem, which improves on the composition theorem of Dwork, Rothblum, and Vadhan [DRV10] by exactly halving the bound on expected privacy loss of (ε, 0)-differentially privacy mechanisms (the proof is otherwise identical). Details for the sharper bound appear in Section 3.2. Theorem 1.1. For all ε, δ, δ ′ ≥ 0, the class of (ε, δ ′ )-differentially private mechanisms satisfies ( 2k ln(1/δ)ε + kε(e ε − 1)/2, kδ ′ + δ)-differential privacy under k-fold adaptive composition. As the theorem shows (recall that δ ′ is usually taken to be "sub-polynomially small"), the pure and relaxed forms of differential privacy behave quite similarly under composition. For the all-important class of counting queries ("How many people in the dataset satisfy property P ?") Theorem 1.1 leads to accuracy bounds that differ from the bounds imposed by (one instantiation of) the Fundamental Law by a factor of roughly 2 log(1/δ). 2 Recently, tight bounds on the composition of (ε, δ)-differentially private algorithms have been given in [KOV15, MV16](see below). A New Relaxation. In this work we introduce a different relaxation, Concentrated Differential Privacy (CDP), incomparable to (ε, δ)-differential privacy but again having the same behavior under composition. Concentrated differential privacy is closer to the "every δ" property in the statement of Theorem 1.1: An algorithm offers (µ, τ )-concentrated differential privacy if the privacy loss random variable has mean µ and if, after subtracting off this mean, the resulting (centered) random variable, ξ, is subgaussian with standard τ . 3 In consequence (see, e.g., [BK00] Lemma 1.3), ∀x > 0: Thus, concentrated differential privacy ensures that the expected privacy loss is µ and the probability of loss exceeding its mean by x = tτ is bounded by e −t 2 /2 , echoing the form of the guarantee offered by the Advanced Composition Theorem (Theorem 1.1). Consider the case in which τ = ε. On the one hand, (µ, ε)-concentrated differential privacy is clearly weaker than (ε, δ)-differential privacy, because even if the expected loss µ is very small, the probability of privacy loss exceeding ε in the former can be constant in the former but is only δ, which is tiny, in the latter. On the other hand, in (ε, δ)-differential privacy there is no bound on the expected privacy loss, since with probability δ all bets are off and the loss can be infinite. Concentrated differential privacy enjoys two advantages over (ε, δ)-differential privacy.  • Improved Accuracy. Concentrated differential privacy is tailored to the (realistic!) case of large numbers of computations. Traditionally, to ensure small cumulative loss with high probability, the permitted loss for each individual query is set very low, say ε ′ = ε (log 1/δ)/k, even though a privacy loss of, say, ε/10 or even ε itself may not be of great concern for any single query. This is precisely the flexibility we give in concentrated differential privacy: much less concern about single-query loss, but high probability bounds for cumulative loss. The composition of k (µ, τ )-concentrated differential privacy mechanisms is (kµ, √ kτ )-concentrated differential privacy (Theorem 3.4). Setting τ = ε we get an expected privacy loss of kµ and, for all t simultaneously, the probability of privacy loss exceeding its epectation by t √ kε falls exponentially in t 2 /2, just as we obtained in the composition for the other variants of differential privacy in Theorem 1.1 above. However, we get better accuracy. For example, to handle n counting queries using the Gaussian mechanism, we can add independent random noise drawn from N (0, n/ε 2 ) to each query, achieving (ε(e ε − 1)/2, ε)-concentrated differential privacy (Theorem 3.2) 4 . When ε = Θ(1) the noise is scaled to O( √ n); the Fundamental Law says noise o( √ n) is disastrous. • Group Privacy Group privacy bounds the privacy loss even for pairs of databases that differ in the data of a small group of individuals; for example, in a health survey one may wish not only to know that one's own health information remains private but also that the information of one's family as a whole is strongly protected. Any (ε, 0)-differentially private algorithm automatically ensures (sε, 0)-differential privacy for all groups of size s [DMNS06], with the expected privacy loss growing by a factor of about s 2 . The situation for (ε, δ)-differential privacy is not quite so elegant: the literature shows (sε, se s−1 δ)-differential privacy for groups of size s, a troubling exponential increase in the failure probability (the se s−1 δ term). The situation for concentrated differential privacy is much better: for all known natural mechanisms with concentrated differential privacy we get tight bounds. For (hypothetical) arbitrary algorithms offering subgaussian privacy loss, Theorem 4.1 shows bounds that are asymptotically nearly-tight (tight up to low-order terms). We suspect that the tight bounds should hold for arbitrary mechanisms, and it would be interesting to close the gap. 1. Under certain conditions, satisfied by all pure differential privacy mechanisms 5 , and the addition of Gaussian noise, any (µ, τ )-concentrated differential privacy mechanism satisfies (s 2 ·µ, s·τ )-concentrated differential privacy for groups of size s, which is optimal. 2. Every ( (1))-concentrated differential privacy for groups of size s. The bound holds so long as s · τ is small enough (roughly, (1/τ ) should remain quasi-linear in s). See Theorem 4.1 for the formal statement. We also assume here that µ ≤ τ 2 2 . 6 Remark 1.2. Consider any mechanism built by composing a collection of "good" mechanisms, each satisfying the conditions in Item 1 above. To prove that the composed mechanism has the good group privacy bounds we can first apply the group privacy bounds for the underlying "good" mechanisms, and then apply composition. It is interesting that these two operations commute. 4 To achieve (ε, δ)-differential privacy one adds noise drawn from N (0, 2 ln(1/δ)), increasing the typical distortion by a factor of ln(1/δ). 5 Every (ε, 0)-differentially private mechanism yields (ε(e ε −1)/2, ε)-concentrated differential privacy (Theorem 3.5). 6 Up to low-order terms, this relationship holds for all mechanisms we know. For other mechanisms, it is possible to derive a less elegant general bound, or τ can be "artificially inflated" until this condition holds. Tight Bounds on Expected Loss. As noted above, we improve by a factor of two the known upper bound on expected privacy loss of any (ε, 0)-differentially private mechanism, closing a gap open since 2010 [DRV10]. This immediately translates to an improvement by a factor of √ 2 on the utility/privacy tradeoff in any application of the Advanced Composition Theorem. The new bound, which is tight, is obtained by first proving the result for special pairs of probablity distributions that we call antipodal (privacy loss for any outcome is in {−ε, 0, ε}), and then showing a reduction, in which an arbitrary pair of distributions with max divergence bounded by ε -such as the distributions on outcomes of a differentially private mechanism when run on databases x and y differing in a single row -can be "replaced" by a antipodal pair with no change in max divergence and no decrease in KL-divergence. Remark 1.3. If all (ε, 0)-differentially private algorithms enjoy concentrated differential privacy, as well as the Gaussian mechanism, which (ε, δ)-differentially private algorithms are ruled out? All (ε, δ)-differentially private algorithms in which there is some probability δ ′ ≤ δ of infinite privacy loss. This includes many (but not all!) algorithms in the "Propose-Test-Release" framework [DL09], in which a differentially private test is first performed to check that the dataset satisfies some "safety" conditions and, if so, an operation is carried out that only ensures privacy if the conditions are met. There could be a small probability of failure in the first step, meaning that the test reports that the safety conditions are met, but in fact they are not, in which case privacy could be compromised in the second step. Tightness. Optimality in privacy loss is a suprisingly subtle and difficult question under composition. Results of Kairouz, Oh and Viswanath [KOV15] obtain tight bounds under composition of arbitrary (ǫ, δ)-mechanisms, when all mechanisms share the same values of ǫ and δ. That is, they find the optimal ǫ ′ , δ ′ such that the composition of k mechanisms, each of which is (ǫ 0 , δ 0 )-differentially private, is (ǫ ′ , δ ′ )-differentially private. The nonhomogeneous case, in which the ith mechanism is (ǫ i , δ i )-differentially private, has been analyzed by Murtagh and Vadhan [MV16], where it is shown that determining the bounds of the optimal composition is hard for #P. Both these papers use an analysis similar to that found in our Lemma 3.8, which we obtained prior to the publication of those works. Optimal bounds on the composition of arbitrary mechanisms are very interesting, but we are also interested in bounds on the specific mechanisms that we have in hand and wish to use and analyze. To this end, we obtain a complete characterization of the privacy loss of the Gaussian mechanism. We show that the privacy loss of the composition of multiple application of the Gaussian mechanism, possibly with different individual parameters, is itself a Gaussian random variable, and we give exact bounds for its mean and variance. This characterization is not possible using the framework of (ǫ, δ)-differential privacy, the previous prevailing view of the Gaussian mechanism. Subsequent Work. Motivated by our work, Bun and Steinke [BS15] suggest a relaxation of concentrated differential privacy. Instead of framing the privacy loss as a subgaussian random variable as we do here, they instead frame the question in terms of Renyi entropy, obtaining a relaxation of concentrated differential privacy that also supports a similar composition theorem. Their notion also provides privacy guarantees for groups. The bounds we get using concentrated 4 differential privacy (Theorem 4.1) are tighter; we do not know whether this is inherent in the definitions. Divergence. We will need several different notions of divergence between distributions. We will also introduce a new notion, subgaussian divergence in Section 3. Definition 2.1 (KL-Divergence). The KL-Divergence, or Relative entropy, between two random variables Y and Z is defined as: where if the support of Y is not equal to the support of Z, then D KL (Y ||Z) is not defined. Definition 2.2 (Max Divergence). The Max Divergence between two random variables Y and Z is defined to be: where if the support of Y is not equal to the support of Z, then D ∞ (Y ||Z) is not defined. The δ-approximate divergence between Y and Z is defined to be: For a given database d, a (randomized) non-interactive database access mechanism M computes an output M(x) that can later be used to reconstruct information about d. We will be concerned with mechanisms M that are private according to various privacy notions described below. We think of a database x as a multiset of rows, each from a data universe U . Intuitively, each row contains the data of a single individual. We will often view a database of size n as a tuple x ∈ U n for some n ∈ N (the number of individuals whose data is in the database). We treat n as public information throughout. We say databases x, y are adjacent if they differ only in one row, meaning that we can obtain one from the other by deleting one row and adding another. I.e. databases are adjacent if they are of the same size and their edit distance is 1. To handle worst case pairs of databases, our probabilities will be over the random choices made by the privacy mechanism.  where the probabilities are over algorithm M's coins. Or alternatively: . A randomized algorithm M gives (ε, δ)-differential privacy if for all pairs of adjacent databases x and y and all S ⊆ Range(M) where the probabilities are over the coin flips of the algorithm M. Or alternatively: Privacy Loss as a Random Variable. Consider running an algorithm M on a pair of databases x, y. For an outcome o, the privacy loss on o is the log-ratio of its probability when M is run on each database: Concentrated differential privacy delves more deeply into the privacy loss random variable: this real-valued random variable measures the privacy loss ensuing when algorithm M is run on x (as opposed to y). It is sampled by taking y ∼ M(x) and outputting L (o) (M(x)||M(y)) . This random variable can take positive or negative values. For (ε, 0)-differentially private algorithms, its magnitude is always bounded by ε. For (ε, δ)-differentially private algorithms, with all but δ probability the magnitude is bounded by ε. Subgaussian random variables were introduced by Kahane [Kah60]. A subgaussian random variable is one for which there is a positive real number τ > 0 s.t. the moment generating function is always smaller than the moment generating function of a Gaussian with standard deviation τ and expectation 0. In this section we briefly review the definition and basic lemmata from the literature.  We say that X is subgaussian if there exists τ ≥ 0 s.t. X is τ -subgaussian. For a subgaussian random variable X, the subgaussian standard of X is: Remarks. An immediate consequence of Definition 2.5 is that an τ -subgaussian random variable has expectation 0, and variance bounded by τ 2 (see Fact 2.1). Note also that the gaussian distribution with expectation 0 and standard deviation σ is σ-subgaussian. There are also known bounds on the higher moments of subgaussian random variables (see Fact 2.2). See [BK00] and [Riv12] for further discussion. Lemma 2.1 (Subgaussian Concentration). If X is τ -subgaussian for τ > 0, then: Proof. For every λ > 0 and t > 0: where the first equality is obtained by raking an exponential of all arguments, the second (in)equality is by Markov, and the this is by the properties of the subgaussian random variable X. The righthand side is minimized when λ = t/τ , and thus we get that: The proof that Pr[X ≤ −t · τ ] ≤ e −t 2 /2 is similar.  For any τ -subgaussian random variable Y , and integer k, the k-th moment is bounded by: Lemma 2.2 (Sum of Subgaussians). Let X 1 , . . . , X k be (jointly distributed) real-valued random variables such that for every i ∈ [k], and for every (x 1 , . . . , x i−1 ) ∈ Supp(X 1 , . . . , X k−1 ), it holds that the random variable ( Proof. The proof is by induction over k. The base case k = 1 is immediate. For k > 1, for any λ ∈ R, we have: where the last inequality is by the induction hypothesis. The following technical Lemma about the products of (jointly distributed) random variables, one of which is exponential in a subgaussian, will be used extensively in proving group privacy: 7 Lemma 2.3 (Expected Product with Exponential in Subgaussian). Let X and Y be jointly distributed random variables, where Y is τ -Subgaussian for τ ≤ 1/3. Then: Proof. Taking the Taylor expansion of e Y we have: By the Cauchy-Schwartz inequality: where the last inequality uses the fact that for a τ -subgaussian RV Y , Var (Y ) ≤ τ 2 (Fact 2.1), and that To bound the last summand in Inequality 2, we use linearity of the expectation and Cauchy-Schwartz: Using the fact that for any τ -subgaussian distribution Y , the 2k-th moment E[Y 2k ] is bounded by 2), we conclude from the above that for τ < 1: Putting together Inequalities (2), (3), (4), we conclude that for τ ≤ 1/2: where the next-to-last inequality holds whenever τ ≤ 1/3, and the last inequality is because 3 Concentrated Differential Privacy: Definition and Properties If the supports of Y and Z aren't equal, then the privacy loss random variable is not defined. We study the privacy loss random variable, focusing on the case where this random variable is tightly concentrated around its expectation. In particular, we will be interested in the case where the privacy loss (shifted by its expectation) is subgaussian.  ) is defined and subgaussian, and its subgaussian parameter is at most τ . If we have both D subG (Y ||Z) (µ, τ ) and D subG (Z||Y ) (µ, τ ), then we say that the pair of random variables X and Y are (µ, τ )-subgaussian-indistinguishable.  Proof. Follows from Definition 3.3 and the concentration properties of subgaussian random variables (Lemma 2.1). Guassian Mechanism Revisited. We revisit the Gaussian noise mechanism of [DMNS06], giving a tight characterization of the privacy loss random variable. Then the Gaussian mechanism with noise magnitude σ is (τ 2 /2, τ )-CDP, where τ = ∆(f )/σ. Later, we will prove (Theorem 3.5) that every pure differentially private mechanism also enjoys concentrated differential privacy. The Gaussian mechanism is different, as it only ensures (ε, δ)-differential privacy for δ > 0. of Theorem 3.2. Let M be the Gaussian mechanism with noise magnitude σ. Let d, d ′ be adjacent databases, and suppose w.l.o.g that f (d) = f (d ′ ) + ∆f . We examine the privacy loss random variable obtained by drawing a noise magnitude x ∼ N (0, σ 2 ) and outputting: Since x ∼ N (0, σ 2 ), we conclude that the distribution of the privacy loss random variable L (U ||V ) is also Gaussian, with expectation (∆f /σ) 2 /2, and standard deviation ∆f /σ. Taking τ = ∆f /σ, As noted in the Introduction, it is a consequence of Theorem 3.2 that we can achieve (ε(e ε − 1)/2, ε)-concentrated differential privacy by adding independent random noise drawn from N (0, n/ε 2 ) to each query. If we further relax to (ε, √ ε)-cdp, we can add even smaller noise, of magnitude ( 1/ε). This would make sense in settings where we expect further composition, and so we can focus on the expected privacy loss (bounding it by ε) and allow more slackness in the standard deviation. For small ε, this gives another order of magnitude improvement in the amount of distortion introduced to protect privacy. Finally, we observe that the bounds for group concentrated differential privacy of the Gaussian mechanism follow immediately from from Theorem 3.2, noting that for a group of size s the group sensitivity of a function f is at most s · ∆f . Corollary 3.3 (Group CDP for the Gaussian Mechanism). The Gaussian mechanism with noise magnitude σ satisfies ((s∆f /σ) 2 /2, s∆f )-concentrated differential privacy. Concentrated Differential Privacy composes "as well as" standard differential privacy. Indeed, a primary advantage of CDP is that it permits greater accuracy and smaller noise, with essentially no loss in privacy under composition. In this section we prove these composition properties. We follow the formalization in [DRV10] in modeling composition. Composition covers both repeated use of (various) CDP algorithms on the same database, which allows modular construction of CDP algorithms, and repeated use of (various) CDP algorithms on different databases that might contain information pertaining to the same individual. In both of these scenarios, the improved accuracy of CDP algorithms can provide greater utility for the same "privacy budget". Composition of k CDP mechanisms (over the same database, or different databases) is formalized by a sequence of pairs of random variables (U, V ) = ((U (1) , V (1) ), . . . , (U (k) , V (k) )). The random variables are the outcomes of adversarially and adaptively chosen CDP mechanisms M 1 , . . . , M k . In the U sequence (reality), the random variable U (i) is sampled by running mechanism M i on a database (of the adversary's choice) containing an individual's, say Bob's, data. In the V sequence (alternative reality), the random variable V (i) is sampled by running mechanism M i on the same database, but where Bob's data are replaced by (adversarially chosen) data belonging to a different individual, Alice. The requirement is that even for adaptively and adversarially chosen mechanisms and database-pairs, the outcome of U (Bob-reality) and V (Alice-reality) are "very close", and in particular the privacy loss L (U ||V ) is subgaussian. In more detail, and following [DRV10], we define a game in which a dealer flips a fair coin to choose between symbols U and V , and an adversary adaptively chooses a sequence of pairs of adjacent databases (x U i , x V i ) and a mechanism M i enjoying (µ i , τ i )-CDP and that will operate on either the left element (if the dealer chose U ) or the right element (if the dealer chose V ) of the pair, and return the output, for 1 ≤ i ≤ k. The adversary's choices are completely adaptive and hence may depend not only on arbitrary external knowledge but also on what has been observed in steps 1, . . . , i − 1. The goal of the adversary is to maximize privacy loss. It is framed as a game because large privacy loss is associated with an increased ability to determine which of (U, V ) was selected by the dealer, and we imagine this to be the motivation of the adversary. Theorem 3.4 (Composition of CDP). For every integer k ∈ N, every µ 1 , . . . , µ k , τ 1 , . . . , τ k ≥ 0, and constructed as in the game described above, we have that Consider the random variables U and V defined above, and the privacy loss random variable L (U ||V ) . This random variable is obtained by picking y ∼ U and outputting ln The mechanism and datasets chosen by the adversary at step i depend on the adversary's view at that time. The adversary's view comprises its randomness and the outcomes it has observed thus far. Letting R U and R V denote the randomness in the U -world and V -world respectively, we have, for any y = (y 1 , . . . , y k ) ∈ Supp(U ) and random string r c i (r, y 1 , . . . , y i ) . Now for every prefix (r, y 1 , . . . , y i−1 ) we condition on R U = r, U 1 = y 1 , . . . , U i−1 = y i−1 , and analyze the the random variable c i (R U , U 1 , . . . , U i ) = c i (r, y 1 , . . . , y i−1 , U (i) . Once the prefix is fixed, the next pair of databases x U i and x V i and the mechanism M i output by the advesary are also determined. Thus U i is distributed according to M i (x U i ) and for any value y i , we have is (µ i , τ i ) subgaussian. By the subgaussian properties of the random variables C i = c i (r, U (1) , . . . , U (i) ), we have that L (U ||V ) = i∈[k] C i , i.e. the privacy loss random variable equals the sum of the C i random variables. By linearity of expectation, we conclude that: and by Lemma 2.2, we have that the random variable: In this section, we explore the relationship between differential privacy and concentrated differential. We show that any differentially private algorithm is also concentrated differentially private. Our main contribution here is a refined upper bound on the expected privacy loss of differentially private algorithms: we show that if M is ε-DP, then its expected privacy loss is only (roughly) ε 2 /2 (for small enough ε). We also show that the privacy loss random variable for any ε-DP algorithm is subgaussian, with parameter τ = O(ε): Theorem 3.5 (DP ⇒ CDP). Let M be any ε-DP algorithm. Then M is (ε · (e ε − 1)/2, ε)-CDP. Proof. Since M is (ε, 0)-differentially private, we know that the privacy loss random variable is always bounded in magnitude by ε. The random variable obtained by subtracting off the expected privacy loss, call it µ, therefore has mean zero and lies in the interval [−ε − µ, ε − µ]. It follows from Hoeffding's Lemma, stated next, that such a bounded, centered, random variable is (ε − µ − (−ε − µ))/2 = ε-subgaussian. Lemma 3.6 (Hoeffding's Lemma). Let X be a zero-mean random variable such that The main challenge is therefore to bound the expectation, namely the quantity D KL (D||D ′ ), where D is the distribution of M(x) and D ′ is the distribution of M(y), and x, y are adjacent databases. In [DRV10] it was shown that: We improve this bound, obtaining the following refinement: The proof of Theorem 3.5 follows from Lemma 3.8. To prove Lemma 3.8, we introduce the notion of antipodal distributions: We then use the following two lemmas about maximally divergent distributions (the proofs follow below) to prove Lemma 3.8: Proof of Lemma 3.9. Let ε = ∆ ∞ (D, D ′ ). We construct M and M ′ iteratively from D and D ′ by enumerating over each x ∈ X . For each such x, we add a new element s x to the support. The idea is that the mass of x in D and D ′ will be "split" between x and s x in M and M ′ (respectively). This split will ensure that the probabilities of s x in M and in M ′ are identical, and the probabilities of x in M and M ′ are "maximally divergent". We will show that the "contribution" of x and s x to the KL divergence from M to M ′ is at least as large as the contribution of x to the KL divergence from D to D ′ . The lemma then follows. We proceed with the full specification of this "split" and then formalize the above intuition. For x ∈ X , take p x = D ′ [x]. Since ∆ ∞ (D, D ′ ) = e ε , there must exist α ∈ [−1, 1] s.t. D[x] = e α·ε · p x . We introduce a new item s x into the support, and set the mass of M and M ′ on x and s x as follows: = e sign(α)·ε · p x · e α·ε − 1 e sign(α)·ε − 1 = p x · (1 − e α·ε − 1 e sign(α)·ε − 1 ) = p x · (e α·ε − e sign(α)·ε · e α·ε − 1 e sign(α)·ε − 1 ) = p x · (e α·ε − (e sign(α)·ε − 1 + 1) · e α·ε − 1 e sign(α)·ε − 1 ) = p x · (e α·ε − (e sign(α)·ε − 1) · e α·ε − 1 e sign(α)·ε − 1 − · e α·ε − 1 e sign(α)·ε − 1 ) = p x · (e α·ε − (e α·ε − 1) − e α·ε − 1 e sign(α)·ε − 1 ) = p x · (1 − e α·ε − 1 e sign(α)·ε − 1 ) Observe that all probabilities are at least zero and sum to 1 (for M and M ′ respectively). Moreover, M and M ′ are antipodal, ∆ ∞ (M, M ′ ) = ε = ∆ ∞ (D, D ′ ). Thus, the distributions M and M ′ satisfy the conditions of the lemma. Finally, we emphasize that by the above we have ∀x ∈ X, M [ We now compare the KL divergence from D to D ′ with the divergence from M to M ′ .
Dwork and Rothblum REF also proposed Concentrated Differential Privacy, a relaxation of Differential Privacy enjoying better accuracy than both pure differential privacy without compromising on cumulative privacy loss over multiple computations.
Concentrated Differential Privacy
ArXiv
ArXiv
Computer Science Mathematics