Concentrated Differential Privacy

arXiv:1603.01887v2 [] 16 Mar 2016

Cynthia Dwork

Guy N. Rothblum

Abstract
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.

1

Introduction

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
p
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 t2 /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
p
( 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
p 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:




x2
x2
Pr[ξ ≥ x] ≤ exp − 2
and Pr[ξ ≤ −x] ≤ exp − 2
2τ
2τ
Thus, concentrated differential privacy ensures that the expected privacy loss is µ and the proba2
bility of loss exceeding its mean by x = tτ is bounded by e−t /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.
√
For example, for O(n) counting queries errors on the order of o( n) on all but a 0.239 fraction of queries
leads to
p
blatant non-privacy [DMT07], while noise drawn from a Laplace distribution with standard deviation O( n ln(1/δ)/ε)
yields (ε, δ)-differential privacy [DMNS06, DRV10].
2

3

A random variable X is subgaussian with standard τ for a constant τ > 0 if ∀λ ∈ R : E[eλ·X ] ≤ e
Section 2.2.

2

λ2 ·τ 2
2

. See

• Improved Accuracy. Concentrated differential privacy is tailored to the (realistic!) case of
large numbers of computations. Traditionally, to ensure small cumulative loss with
p 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 t2 /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 s2 . The situation for (ε, δ)differential privacy is not quite so elegant: the literature shows (sε, ses−1 δ)-differential privacy
for groups of size s, a troubling exponential increase in the failure probability (the ses−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 mechanisms5 , and
the addition of Gaussian noise, any (µ, τ )-concentrated differential privacy mechanism
satisfies (s2 ·µ, s·τ )-concentrated differential privacy for groups of size s, which is optimal.
2

2

2. Every ( τ2 , τ )-concentrated differential privacy mechanism satisfies (s2 · τ2 · (1 + o(1)), s ·
τ · (1 + o(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
2
Theorem 4.1 for the formal statement. We also assume here that µ ≤ τ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 achievep(ε, δ)-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.

3

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.

1.1

Recent Developments

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.

2

Preliminaries

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:


Pr[Y = y]
DKL (Y ||Z) = Ey∼Y ln
,
Pr[Z = y]
where if the support of Y is not equal to the support of Z, then DKL (Y ||Z) is not defined.
Definition 2.2 (Max Divergence). The Max Divergence between two random variables Y and Z
is defined to be:


Pr[Y ∈ S]
,
D∞ (Y ||Z) = max
ln
Pr[Z ∈ S]
S⊆Supp(Y )
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:


Pr[Y ∈ S]
δ
D∞
(Y ||Z) =
max
ln
,
Pr[Z ∈ S]
S⊆Supp(Y ):Pr[Y ∈S]≥δ

δ (Y ||Z) is not defined.
where if Pr[Y ∈ Supp(Y ) \ Supp(Z)] > δ, then D∞

2.1

Differential Privacy

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.
Definition 2.3 ((ε, 0)-Differential Privacy ((ε, 0)-DP) [DMNS06]). A randomized algorithm M is
ε-differentially private if for all pairs of adjacent databases x, y, and for all sets S ⊆ Range(M(x))∪
Range(M(y))
Pr[M(x) ∈ S] ≤ eε · P r[M(y) ∈ S],
where the probabilities are over algorithm M’s coins. Or alternatively:
D∞ (M(x)||M(y)), D∞ (M(y)||M(x)) ≤ ε
5

Definition 2.4 ((ε, δ)-Differential Privacy ((ε, δ)-DP) [DKM+ 06]). A randomized algorithm M
gives (ε, δ)-differential privacy if for all pairs of adjacent databases x and y and all S ⊆ Range(M)
Pr[M(x) ∈ S] ≤ eε · Pr[M(y) ∈ S] + δ,
where the probabilities are over the coin flips of the algorithm M. Or alternatively:
δ
δ
D∞
(M(x)||M(y)), D∞
(M(y)||M(x)) ≤ ε

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:
Pr[M(x) = o]
(o)
.
L(M(x)||M(y)) = ln
Pr[M(y) = o]
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
(o)
x (as opposed to y). It is sampled by taking y ∼ M(x) and outputting L(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 ε.

2.2

Subgassian Random Variables

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.
Definition 2.5 (Subgaussian Random Variable [Kah60]). A random variable X is τ -subgaussian
for a constant τ > 0 if:
∀λ ∈ R : E[eλ·X ] ≤ e

λ2 ·τ 2
2

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:
τ (X) = inf {τ ≥ 0 : X is τ -subgaussian}
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:
2 /2

Pr[X ≥ t · τ ] ≤ e−t

,

2 /2

Pr[X ≤ −t · τ ] ≤ e−t
6

Proof. For every λ > 0 and t > 0:
Pr[X ≥ t · τ ] = Pr[eλ·X ≥ eλ·t·τ ]
≤ e−λ·t·τ · E[eλ·X ]

≤ e

λ2 ·τ 2
−λ·t·τ
2

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:
2 /2

Pr[X ≥ t · τ ] ≤ e−t
2 /2

The proof that Pr[X ≤ −t · τ ] ≤ e−t

is similar.

Fact 2.1 (Subgaussian Variance). The variance of any τ -subgaussian random variable Y is bounded
by Var (Y ) ≤ τ 2 .
Fact 2.2 (Subgaussian Moments). For any τ -subgaussian random variable Y , and integer k, the
k-th moment is bounded by:


E[Y k ] ≤ (⌈k/2⌉!) · 2⌈k/2⌉+1 · τ k

Lemma 2.2 (Sum of Subgaussians). Let X1 , . . . , Xk be (jointly distributed) real-valued random
variables such that for every i ∈ [k], and for every (x1 , . . . , xi−1 ) ∈ Supp(X1 , . . . , Xk−1 ), it holds
that the random variable (Xi |X1 = x1 , . . . , Xq
i−1 = xi−1 ) is τi -subgaussian. Then the random
P
P
2
variable i∈[k] Xi is τ -subgaussian, where τ =
i∈[k] τi .

Proof. The proof is by induction over k. The base case k = 1 is immediate. For k > 1, for any
λ ∈ R, we have:
h
i
P
P
E[eλ· i∈[k] Xi ] = E(x1 ,...,xk−1 )∼(X1 ,...,Xk−1 )) EXk [eλ· i∈[k] Xi |X1 = x1 , . . . , Xk−1 = xk−1 ]
i
h P
λ· i∈[k−1] xi
λ·Xk
|X1 = x1 , . . . , Xk−1 = xk−1 ]
· EXk [e
= E(x1 ,...,xk−1 )∼(X1 ,...,Xk−1 )) e
 P

2
2
λ ·τk
≤ E(x1 ,...,xk−1 )∼(X1 ,...,Xk−1 )) eλ· i∈[k−1] xi · e 2
= e
≤ e
= e

2
λ2 ·τk
2

· E[eλ·

i∈[k−1]

Xi

]

P
λ2 · i∈[k−1] τi2

2
λ2 ·τk
2
P
λ2 · i∈[k] τi2
2

·e

P

2

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:
p
E[X · eY ] ≤ E[X] + E [X 2 ] · (τ + 3τ 2 )
p
≤ E[X] + ( Var (X) + E[X]) · (τ + 3τ 2 )
(1)

Proof. Taking the Taylor expansion of eY we have:
"
E[X · eY ] = E X ·

1+Y +

∞
X
Yk
k=2

k!
"

!#

= E[X] + E[X · Y ] + E X ·

∞
X
Yk
k=2

k!

!#

(2)

By the Cauchy-Schwartz inequality:
E[X · Y ] ≤
≤

p

p

E[X 2 ] ·

p

E[Y 2 ]

E[X 2 ] · τ

(3)

2
where√the last inequality
√ uses the fact that for a τ -subgaussian RV Y , Var (Y ) ≤ τ (Fact 2.1), and
√
that a + b ≤ a + b (for any a, b ≥ 0). To bound the last summand in Inequality 2, we use
linearity of the expectation and Cauchy-Schwartz:

"

E X·

∞
X
Yk
k=2

k!

!#


∞  
X
Yk
E X·
=
k!
k=2
s 

∞ p
X
Y 2k
2
E [X ] · E
≤
(k!)2
k=2
s 

∞
X
p
Y 2k
2
E
= E [X ] ·
(k!)2
k=2

Using the fact that for any τ -subgaussian distribution Y , the 2k-th moment E[Y 2k ] is bounded by

8


(k!) · 2k+1 · τ 2k (see Fact 2.2), we conclude from the above that for τ < 1:
"

E X·

∞
X
Yk
k=2

k!

!#

∞
X

s

(k!) · 2k+1 · τ 2k
(k!)2

s

(k!) · 2k+1 · τ 2k
(k!)2

s

2k+1 · τ 2k
(k!)

≤

p

E [X 2 ] ·

=

p

E [X 2 ] ·

p

E [X 2 ] ·

≤

p

E [X 2 ] ·

=

p

E [X 2 ] · 2τ 2 ·

=

p

=

k=2

∞
X
k=2

∞
X

k=2
∞ √
X

4τ 2k

k=2

∞
X

τk

k=0

2τ 2
E [X 2 ] ·
1−τ

(4)

Putting together Inequalities (2), (3), (4), we conclude that for τ ≤ 1/2:

 p
p
2τ 2
Y
2
2
E[X · e ] ≤ E[X] +
E [X ] · τ +
E [X ] ·
1−τ


2
p
2τ
= E[X] + E [X 2 ] · τ +
1−τ
p
≤ E[X] + E [X 2 ] · (τ + 3τ 2 )
p
≤ E[X] + ( Var (X) + E[X]) · (τ + 3τ 2 )

where
the p
next-to-last inequality holds
τ ≤
p
√ 1/3, and the last inequality is because
√ whenever
√
E[X 2 ] ≤ Var (X) + E[X] (because a + b ≤ a + b for any a, b > 0).

3

Concentrated Differential Privacy: Definition and Properties

Definition 3.1 (Privacy Loss Random Variable L(Y ||Z)). For two discrete random variables Y and
Z, the privacy loss random variable L(Y ||Z), whose range is R, is distributed by drawing y ∼ Y , and
outputting ln(Pr[Y = y]/Pr[Z = y]). In particular, the expectation of LY ||Z is equal to DKL (Y ||Z).
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.
Definition 3.2 (Subgaussian Divergence and Indistinguishability). For two random variables Y
and Z, we say that DsubG (Y ||Z)  (µ, τ ) if and only if:
1. E[L(Y ||Z) ] ≤ µ
9

2. The (centered) distribution (L(Y ||Z) − E[L(Y ||Z)]) is defined and subgaussian, and its subgaussian parameter is at most τ .
If we have both DsubG (Y ||Z)  (µ, τ ) and DsubG (Z||Y )  (µ, τ ), then we say that the pair of
random variables X and Y are (µ, τ )-subgaussian-indistinguishable.
Definition 3.3 ((µ, τ )-Concentrated Differential Privacy ((µ, τ )-CDP)). A randomized algorithm
M is (µ, τ )-concentrated differentially private if for all pairs of adjacent databases x, y, we have
DsubG (M(x)||M(y))  (µ, τ ).
Corollary 3.1 (Concentrated Privacy Loss). For every (µ, τ )-CDP algorithm M, for all pairs of
adjacent databases x, y, taking Y to be the distribution of M(x), and Z to be the distribution of
M(y):
t2
Pr[L(Y ||Z) ≥ µ + (t · τ )] ≤ exp(− )
2
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.
Theorem 3.2 (Gaussian is CDP). Let f : x → R be any real-valued function with sensitivity ∆(f ).
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:
ln

Pr[M(d) = (f (d) + x)]
Pr[M(d ′ ) = (f (d) + x)]

= ln

e(−1/2σ
e(−1/2σ

2 )·x2

2 )·(x+∆f )2

2
2
2
= ln e(−1/2σ )·[x −(x+∆f ) ]

1 
= − 2 · x2 − (x2 + 2x · ∆f + (∆f )2 )
2σ

1 
= − 2 · −2x · ∆f − (∆f )2
2σ




∆f x
1 ∆f 2
=
·
+
σ σ
2
σ

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 /σ,
we get that DsubG (M(d)||M(d ′ ))  (τ 2 /2, τ ).

10

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
peach 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.

3.1

Composition

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 M1 , . . . , Mk .
In the U sequence (reality), the random variable U (i) is sampled by running mechanism Mi 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 Mi 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
V
adjacent databases (xU
i , xi ) and a mechanism Mi 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
(U, V ) = ((U (1) , V (1) ), . . . , (U (k) , V (k) ))
11

P
P
constructed as in the game described above, we have that DsubG (U ||V )  ( ki=i µi , ( ki=1 τi2 )1/2 ).

Proof. Consider the random variables U and V defined above, and the privacy loss random variable
Pr[U =y]
L(U ||V ) . This random variable is obtained by picking y ∼ U and outputting ln Pr[V
=y] .
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 RU and RV denote the randomness in the U -world and V -world respectively, we
have, for any y = (y1 , . . . , yk ) ∈ Supp(U ) and random string r
!
Q
(i) = y |U (i−1) = y
(1) = y ]
i
i−1 , . . . , U
1
Pr[RU = r]
Pr[U = y]
i∈[k] Pr[U
= ln
·Q
ln
(i) = y |V (i−1) = y
(1) = y ]
Pr[V = y]
Pr[RV = r]
i
i−1 , . . . , V
1
i∈[k] Pr[V
=

X

ln

i∈[k]

,

X

Pr[U (i) = yi |U (i−1) = yi−1 , . . . , U (1) = y1 ]
Pr[V (i) = yi |V (i−1) = yi−1 , . . . , V (1) = y1 ]

ci (r, y1 , . . . , yi ) .

i∈[k]

Now for every prefix (r, y1 , . . . , yi−1 ) we condition on RU = r, U1 = y1 , . . . , Ui−1 = yi−1 , and
analyze the the random variable ci (RU , U1 , . . . , Ui ) = ci (r, y1 , . . . , yi−1 , U (i) . Once the prefix is
V
fixed, the next pair of databases xU
i and xi and the mechanism Mi output by the advesary are
also determined. Thus Ui is distributed according to Mi (xU
i ) and for any value yi , we have


Pr[Mi (xU
i ) = yi ]
ci (r, y1 , . . . , yi−1 , yi ) = ln
Pr[Mi (xVi ) = yi ]
which is simply the privacy loss when Mi (xU
V
i ) = yi . By the CDP properties of Mi , L(Mi (xU
i )||Mi (xi ))
is (µi , τi ) subgaussian.
By thePsubgaussian properties of the random variables Ci = ci (r, U (1) , . . . , U (i) ), we have that
L(U ||V ) = i∈[k] Ci , i.e. the privacy loss random variable equals the sum of the Ci random variables.
By linearity of expectation, we conclude that:
X
X
X
E[L(U ||V ) ] = E[
Ci ] =
E[Ci ] =
µi
i∈[k]

i∈[k]

iin[k]

and by Lemma 2.2, we have that the random variable:
X
(L(U ||V ) − E[L(U ||V ) ]) =
(Ci − E[Ci ])
i∈[k]

is

P

3.2

2
i∈[k] τi

1/2

-subgaussian.

Relationship to DP

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(ε):
12

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 Pr[X ∈
2
2
[a, b]] = 1. Then E[eλX ] ≤ e(1/8)λ (b−a) .

The main challenge is therefore to bound the expectation, namely the quantity DKL (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:

Lemma 3.7 ([DRV10]). For any two distributions D and D ′ such that D∞ (D||D ′ ), D∞ (D ′ ||D) ≤ ε,
DKL (D||D ′ ) ≤ DKL (D||D ′ ) + DKL (D ′ ||D) ≤ ε · (eε − 1)
We improve this bound, obtaining the following refinement:
Lemma 3.8. For any two distributions D and D ′ such that ∆∞ (D, D ′ ) = ε,
DKL (D||D ′ ) ≤ ε · (eε − 1)/2
The proof of Theorem 3.5 follows from Lemma 3.8. To prove Lemma 3.8, we introduce the
notion of antipodal distributions:
Definition 3.4 (Antipodal Distributions). Let D and D ′ be two distributions with support X ,
D[x]
such that ∆∞ (D, D ′ ) ≤ ε for some ε > 0. We say that D and D ′ are antipodal if ∀x ∈ X , ln D
′ [x] ∈
{−ε, 0, ε}.
We then use the following two lemmas about maximally divergent distributions (the proofs
follow below) to prove Lemma 3.8:
Lemma 3.9. For any two distributions D and D ′ , there exist antipodal distributions M and M ′
such that ∆∞ (M, M ′ ) = ∆∞ (D, D ′ ) and DKL (D, D ′ ) ≤ DKL (M, M ′ ). Note that the support of
D, D ′ may differ from the support of M, M ′ .
Lemma 3.10. For any antipodal distributions M and M ′ , as in Definition 3.4, DKL (M, M ′ ) =
DKL (M ′ , M ).
Proof of Lemma 3.8. By Lemma 3.9 there exist antipodal distributions M and M ′ s.t. ∆∞ (M, M ′ ) ≤
ε and DKL (D, D ′ ) ≤ DKL (M, M ′ ). By lemma 3.7, DKL (M ||M ′ ) + DKL (M ′ ||M ) ≤ ε · (eε − 1). By
Lemma 3.10, DKL (M ||M ′ ) = DKL (M ′ ||M ), and so DKL (M, M ′ ) ≤ ε · (eε − 1)/2. Putting these
together:
DKL (D, D ′ ) ≤ DKL (M, M ′ ) ≤ ε · (eε − 1)/2

13

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 sx to the support. The idea
is that the mass of x in D and D ′ will be “split” between x and sx in M and M ′ (respectively).
This split will ensure that the probabilities of sx 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 sx 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 px = D ′ [x]. Since ∆∞ (D, D ′ ) = eε , there must exist α ∈ [−1, 1] s.t. D[x] = eα·ε · px .
We introduce a new item sx into the support, and set the mass of M and M ′ on x and sx as follows:
eα·ε − 1
esign(α)·ε − 1
M [x] = esign(α)·ε · M [x]

M ′ [x] = px ·

= esign(α)·ε · px ·

eα·ε − 1
esign(α)·ε − 1

M ′ [sx ] = D ′ [x] − M ′ [x]
eα·ε − 1
= px · (1 − sign(α)·ε
)
e
−1
M [sx ] = D[x] − M [x]

eα·ε − 1
)
esign(α)·ε − 1
eα·ε − 1
)
px · (eα·ε − (esign(α)·ε − 1 + 1) · sign(α)·ε
e
−1
eα·ε − 1
eα·ε − 1
px · (eα·ε − (esign(α)·ε − 1) · sign(α)·ε
− · sign(α)·ε
)
e
−1
e
−1
eα·ε − 1
)
px · (eα·ε − (eα·ε − 1) − sign(α)·ε
e
−1
eα·ε − 1
px · (1 − sign(α)·ε
)
e
−1
M ′ [sx ]

= px · (eα·ε − esign(α)·ε ·
=
=
=
=
=

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 [sx ] =
M ′ [sx ].
We now compare the KL divergence from D to D ′ with the divergence from M to M ′ .
DKL (M, M ′ ) − DKL (D, D ′ ) =
=

X

x∈X

X

x∈X

M [x] · ln
M [x] · ln

M [x]
D[x] 
M [sx ] 
− D[x] · ln ′
+ M [sx ] · ln ′
′
M [x]
D [x]
M [sx ]

M [x]
D[x] 
−
D[x]
·
ln
M ′ [x]
D ′ [x]

Proposition 3.1 below, shows that for every x ∈ X , the summand of x in the above sum is
non-negative. The lemma follows.
14

Proposition 3.1. For every x ∈ X :
M [x] · ln

D[x] 
M [x]
−
D[x]
·
ln
≥0
M ′ [x]
D ′ [x]

Proof. We use the following equality, and the complete the proof using a case analysis, depending
on whether α ≥ 0 or α < 0.
M [x] · ln

D[x]
M [x]
− D[x] · ln ′
′
M [x]
D [x]

=
=
=
=
We proceed with a case analysis:
Case I: α ≥ 0.

eα·ε − 1
· sign(α) · ε) − (px · eα·ε · (α · ε))
esign(α)·ε − 1

eα·ε − 1
− eα·ε · α
px · ε · sign(α) · esign(α)·ε · sign(α)·ε
e
−1

px · ε
sign(α)·ε
· (sign(α) · e
· (eα·ε − 1) − ((esign(α)·ε − 1) · eα·ε · α)
sign(α)·ε
e
−1
sign(α)·ε

px · ε · e
· sign(α) · (eα·ε − 1) − (eα·ε · α) + (e−sign(α)·ε · eα·ε · α)
sign(α)·ε
e
−1
sign(α)·ε

px · ε · e
α·ε
−sign(α)·ε
·
e
·
(sign(α)
+
α
·
(−1
+
e
))
−
sign(α)
esign(α)·ε − 1

= (px · esign(α)·ε ·

Here sign(α) = 1. We use the following inequality:

Claim 3.11. For ε ≥ 0, α ∈ [0, 1]:
α · (−1 + e−ε ) ≥ e−α·ε − 1
Proof. Observe that, for any fixed α ∈ [0, 1], we have equality when ε = 0 (both the left-hand and
right-hand sides of the above inequality equal 0). Taking derivatives (by ε) for both sides, on the
left-hand side the derivative is −α · e−ε , whereas on the right-hand side it is −α · e−α·ε . We conclude
that ∀ε > 0, α ∈ [0, 1], the derivative left-hand side is at least the derivative on the right-hand side
(because in this range −α · e−ε ≥ −α · e−α·ε ).
Now, by the above we have:
M [x] · ln

Case II: α < 0.

M [x]
D[x]
− D[x] · ln ′
M ′ [x]
D [x]


px · ε · eε
· eα·ε · (1 + α · (−1 + e−ε )) − 1
ε
e −1

px · ε · eε
α·ε
−α·ε
≥
·
e
·
(1
+
(e
−
1))
−
1
eε − 1
= 0

=

Here sign(α) = −1. We use the following inequality:

Claim 3.12. For ε ≥ 0, α ∈ [−1, 0):
α · (−1 + eε ) ≤ −e−α·ε + 1

15

Proof. Observe that, for any fixed α ∈ [−1, 0), we have equality when ε = 0 (both the left-hand
and right-hand sides of the above inequality equal 0). Taking derivatives (by ε) for both sides, on
the left-hand side the derivative is α · eε , whereas on the right-hand side it is α · e−α·ε . We conclude
that ∀ε ≥ 0, α ∈ [−1, 0), the derivative on the left-hand side is always at most the derivative on the
right-hand side (because in this range α · eε ≤ α · e−α·ε ).
Recall from above that:
M [x] · ln

M [x]
D[x]
− D[x] · ln ′
M ′ [x]
D [x]

=


px · ε · e−ε
α·ε
ε
·
e
·
(−1
+
α
·
(−1
+
e
))
+
1
e−ε − 1

The right-hand side of this equation is a product of two terms. The first is:
px · ε · e−ε
≤0
e−ε − 1
(because the numerator is positive, and the denominator is negative).
For the second term in the product, we use Claim 3.12, and get:

(eα·ε · (−1 + α · (−1 + eε )) + 1) ≤ (eα·ε · (−1 + −e−α·ε + 1) + 1)
= 0

We conclude that in this case (α < 0), the difference in x’s contribution to the KL divergences
equals the product of two non-positive terms, and so it must be non-negative.
Proof of Lemma 3.10. Let ε = ∆∞ (M, M ′ ). Since M and M ′ are antipodal, w.l.o.g we can study
their KL divergence for the special case where the support is over 3 items: {x, y, s}, and where
M [x] = p, M [y] = q, M [s] = r
M ′ [x] = p′ = p · e−ε , M ′ [y] = q ′ = q · eε , D ′ [s] = r ′ = r

We analyze the expected privacy losses, or KL divergences, from M to M ′ and from M ′ to M .
First, observe that 1 = (p + q + r) = (p′ + q ′ + r ′ ). We conclude that:
p + q = p′ + q ′ ⇒ p + q = p · e−ε + q · eε

⇒ p · (1 − e−ε ) = q · (eε − 1)
eε − 1
⇒ p=q·
1 − e−ε

Examining the KL divergences, we have:
DKL (M ||M ′ ) = px · ln(p/p′ ) + q · ln(q/q ′ ) + s · ln(s/s′ )
= px · ε − q · ε

′

= ε · (px − q)

DKL (M ||M ) = p′ · ln(p′ /p) + q ′ · ln(q ′ /q) + s′ · ln(s′ /s)
= −px · e−ε · ε + q · eε · ε

= ε · (q · eε − px · e−ε )
16

We bound the difference as follows:
DKL (M ||M ′ ) − DKL (M ′ ||M ) = ε · (p − q) − ε · (q · eε − p · e−ε )

= ε · p · (e−ε + 1) − q · (eε + 1)

eε − 1
· (e−ε + 1) − (eε + 1)
= ε·q·
−ε
1−e

eε − 1
−ε
ε
= ε·q·
·
(e
−
1
+
2)
−
(e
+
1)
1 − e−ε

eε − 1
(eε − 1) · (e−ε − 1)
+
2
·
− (eε + 1)
= ε·q·
−ε
−ε
1−e
1−e
eε − 1
ε
− (eε + 1))
= ε · q · − (e − 1) + 2 ·
1 − e−ε

eε − 1
= 2·ε·q·
− eε
−ε
1−e
(eε − 1) − eε · (1 − e−ε ) 
= 2·ε·q·
1 − e−ε
ε
(e − 1) − eε + 1 
= 2·ε·q·
1 − e−ε
= 0

4

Group Privacy

We show that arbitrary mechanisms that guarantee concentrated differential privacy also provide
concentrated differential privacy for groups. This is stated in Theorem 4.1 below. The bounds
are asymptotically nearly-tight, up to low-order terms. It would be interesting to tighten these
bounds to match the tight group privacy guarantees of (all) known concentrated differential privacy
mechanisms, such as the Gaussian Mechanism or pure-ε Differentially private mechanisms. See the
discussion in the introduction.
Theorem 4.1 (Group CDP). Let M be a (µ, τ )-concentrated differentially private mechanism.
Let x, y be a pair of databases that differ on exactly s rows. Suppose that (τ · s · log3 s) is bounded
from above by a sufficiently small constant and µ ≤ τ 2 /2. Then:


(s · τ )2
2.5
1.5
+ Õ((s · τ ) ), (s · τ ) + Õ((s · τ ) )
DsubG (M(x)||M(y)) 
2
(Note that since (s · τ ) < 1, this implies that the privacy loss random variable has expectation
2
roughly (s·τ2 ) , and the subgaussian standard is roughly (s · τ ), all up to the low-order terms).
Proof. We assume for convenience that s is a power of 2. The proof will be by induction over the
value of log s. For s = 1 the claim follows immediately. For the induction step, suppose that the
claim is true for databases differing on 2m rows. We will show that it is true for x, y that differ
on 2m+1 rows. We take µm and τm to be bounds on the expectation and the standard of the
17

(centered) privacy loss distribution for databases that differ on at most 2m rows, so µ0 = µ and
2 /2 (for the base case m = 0 this holds by the
τ0 = τ . We maintain the invariant that µm ≤ τm
lemma conditions).
For the induction step, let z be an “midpoint” database that differs from both x and y on exactly
m
2 rows. Define the mechanism’s output distributions on these databases by D = M(x), D ′ =
M(z), D ′′ = M(y). By the induction hypothesis, we conclude that:
DsubG (D||D ′ ), DsubG (D ′ ||D)  (µm , τm )

DsubG (D ′′ ||D ′ ), DsubG (D ′ ||D ′′ )  (µm , τm )
We use Lemmas 4.2 and 4.3, stated and proved in Sections 4.1 and 4.2 below, to bound µm+1 and
τm+1 .
Bounding τm+1 .

By Lemma 4.3, we have that
1.5
τm+1 ≤ 2τm + 34τm

(5)

We prove that this recursive relation implies that:
τm+1 ≤ (2m+1 · τ ) + α · (2m+1 · (m + 1)3 · τ )1.5

(6)

where α > 0 is a sufficiently large universal constant specified below. This implies the claimed
bound on τlog s .
To prove the bound in Inequality (6), consider τm in light of the recurrence relation of Equation
(5). We bound τm by proving a bound of the following form:
τm ≤ 2m · τ +

m
X

i=1
m
X

= cm,0 · τ +
=

m
X
i=0

i

cm,i · τ 1.5

(7)
i

cm,i · τ 1.5

i=1

i

cm,i · τ 1.5

Where the term cm,0 is (by definition) equal to 2m , and we bound the terms {cm,i }m∈[1,log s],i∈[1,m]
as follows. For m ∈ [1, log s], i ∈ [1, m], we show that:
i

i+1 −1.5)

cm,i ≤ 2 · (2m )1.5 · 342·(1.5

i+1 −1.5)

· m2·(1.5

We conclude that:
i+1 )

i

cm,i < (2m )1.5 · 342·(1.5

i

i

i

i+1 )

· m2·(1.5

= 2m·1.5 · 343·1.5 · m3·1.5
i

= (2m · 343 · m3 )1.5

18

(8)

These bounds are shown below. Plugging the bounds into equation (7) we get:
m+1

τm+1 ≤ (2

· τ) +

= (2m+1 · τ ) +

m+1
X

i=1
m+1
X
i=1

i

i

(2m+1 · 343 · (m + 1)3 )1.5 · τ 1.5
i

(2m+1 · 343 · (m + 1)3 · τ )1.5

≤ (2m+1 · τ ) + 2(2m+1 · 343 · (m + 1)3 · τ )1.5

= (2m+1 · τ ) + α · (2m+1 · (m + 1)3 · τ )1.5

where the next-to-last inequality assumes that (τ · s · log3 s · 343 ) ≤ 1/2, and the last inequality
holds for a sufficiently large universal constant α = 2 · 344.5 . This proves the bound claimed in
Equation (6).
We prove Inequalities (7) and (8) by induction on m. The base case is for m = 0, where c0,0 = 1
and for i ≥ 1 we have c0,i = 0. Assuming the bounds are true for m, and using Inequality (5)
(derived from Lemma 4.3), we have:
1.5
τm+1 ≤ 2τm + 34τm

≤2
≤2

m
X

i=0
m
X
i=0

cm,i · τ

1.5i

cm,i · τ

1.5i

= 2cm,0 · τ +

m
X
i=1

m
X

!

+ 34 ·

!

√
+ 34 · m + 1 ·

i=0

cm,i · τ

1.5i

m
X
i=0

!1.5
c1.5
m,i · τ

1.5i+1

√
 1.5
2cm,i + (34 m + 1 · c1.5
m,i−1 ) · τ

!

(9)
(10)

√
P
1.5 ≤
where
(9) uses the fact that for positive terms ai we have ( m
m+1 ·
i=0 ai )
Pm Inequality
( i=0 ai1.5 ), which follows from Jensen’s Inequality (since x1.5 is a convex function).
Using Inequality (10), we can define the terms cm+1,i as follows:
cm+1,0 = 2cm,0 = 2m+1 · τ
√
∀i ∈ [1, m], cm+1,i = 2cm,i + 34 · m + 1 · c1.5
m,i−1
It remains to prove Inequality (8) for i ∈ [1, m]. The proof is by induction. The base case for m = 0
follows by definition. Assume for a fixed value m, the inequality holds ∀i ∈ [1, m]. I.e.:
i

i+1 −1.5)

cm,i ≤ (2m )1.5 · 342·(1.5

19

i+1 −1.5)

· m2·(1.5

Then we get that ∀i ∈ [1, m + 1]:
√
cm+1,i = 2cm,i + 34 · m + 1 · c1.5
m,i−1
1.5



√
i−1
i
i
i
i+1
i+1
≤ 2 (2m )1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5) + 34 m + 1 · (2m )1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5)




√
i
i+1
i+1
i
i+1
2
i+1
2
= 2 2m·1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5) + 34 m + 1 · 2m·1.5 · 342·(1.5 −1.5 ) · m2·(1.5 −1.5 )

 

i+1
2
i+1
2
i
i+1
i+1
i
< 2 2m·1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5) + 2m·1.5 · 342·(1.5 −1.5 )+1 · (m + 1)2·(1.5 −1.5 )+1/2

 

i+1
i+1
i
i+1
i+1
i
= 2 2m·1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5) + 2m·1.5 · 342·(1.5 −1.5)−0.5 · (m + 1)2·(1.5 −1.5)−1


m·1.5i · 342·(1.5i+1 −1.5) · (m + 1)2·(1.5i+1 −1.5)


2
i
i+1
i+1
= 2 2m·1.5 · 342·(1.5 −1.5) · m2·(1.5 −1.5) +
340.5 · (m + 1)
i

i+1 −1)

< 2.5 · 2m·1.5 · 342·(1.5
i

i

i+1 −1/2)

· (m + 1)2·(1.5
i+1

i+1

= 2.5 · 2((m+1)·1.5 )−1.5 · 342·(1.5 −1.5) · (m + 1)2·(1.5 −1.5)
2.5
i+1
i+1
i
= 1.5i · 2(m+1)·1.5 · 342·(1.5 −1.5) · (m + 1)2·(1.5 −1.5)
2
i+1
i+1
i
< 2(m+1)·1.5 · 342·(1.5 −1.5) · (m + 1)2·(1.5 −1.5)
Bounding µm+1 .

We prove that:
µm+1 ≤

(2m+1 · τ )2
+ α · (2m+1 · τ )2.5 · m4.5 .
2

(11)

(where α is the universal constant specified above). The proof will be by induction over m. For
the base case m = 0, we know that µ ≤ τ 2 /2 by the lemma conditions. For the induction step, by
2 /2:
Lemma 4.2 and using µm ≤ τm
2
3
4
µm+1 ≤ 2µm + τm
+ 3.5τm
+ 1.5τm
.

(12)

Using the induction hypothesis and the bound on the subgaussian standard τm shown above (Inequality (6)), we conclude (so long as τm is a sufficiently small constant) that:

2
3
4
µm+1 ≤ 2µm + τm
+ 3.5τm
+ 1.5τm

≤ 2µm + (2m · τ )2 + 3α · ((2m · τ )2.5 · m4.5 )


≤ (2m · τ )2 + 2α · (2m · τ )2.5 · m4.5 + (2m · τ )2 + 3α · ((2m · τ )2.5 · m4.5 )
= 2(2m · τ )2 + 5α · ((2m · τ )2.5 · m4.5 )
<

(2m+1 · τ )2
+ α · (2m+1 · τ )2.5 · m4.5 .
2

This implies the claimed bound on µlog s (since (s · polylogs · τ ) < 1).

20

Relationship between µm+1 and τm+1 .
2
µm+1 ≤ τm+1
/2. To see this:

Finally, we show that the above bounds maintain that

2
τm+1
= (2m+1 · τ ) + α · (2m+1 · (m + 1)3 · τ )1.5



≥ (2m+1 · τ )2 + 2α · (2m+1 · τ ) · (2m+1 · (m + 1)3 · τ )1.5

= (2m+1 · τ )2 + 2α · (2m+1 · τ )2.5 · m4.5

≥ 2µm+1

4.1

Group Privacy: Bounding the Expected Privacy Loss

In this section we bound the expected privacy loss for groups, using the following Lemma:
Lemma 4.2. Let D, D ′ , D ′′ be distributions over domain X , such that DsubG (D||D ′ ), DsubG (D ′ ||D) 
(µ1 , τ1 ) and that DsubG (D ′ ||D ′′ ), DsubG (D ′′ ||D ′ )  (µ2 , τ2 ). Suppose moreover that τ1 ≤ 1/3. Then
it is also the case that:

DKL (D||D ′′ ) ≤ µ1 + µ2 + τ1 · τ2 + (2τ12 · τ2 ) + ((τ1 + 3τ12 ) · µ2 )
′

[x]
′
′′
Proof. For x ∈ X , we define S(x) to be the centered value S(x) = ln D
D[x] − DKL (D ||D), and S (x)
′

D [x]
′
′′
′
to be the centered value S ′′ (x) = ln D
′′ [x] − DKL (D ||D ). When x is drawn by D [x], both S[x]
and S ′′ [x] are (centered) subgaussian random variables. We use Var (S), Var (S ′′ ) to denote the
variances of these random variables (which are bounded by τ12 , τ22 respectively). We have that:

X
D[x]
′′
DKL (D||D ) =
D[x] · ln ′′
D [x]
x∈X


X
D ′ [x] 
D[x]
+ ln ′′
=
D[x] · ln ′
D [x]
D [x]
x∈X



X
X
D ′ [x]
D[x]
+
D[x] · ln ′′
(13)
=
D[x] · ln ′
D [x]
D [x]
x∈X

x∈X

21

The first of these summands is DKL (D||D ′ ) = µ1 . We bound the second summand:
 X

X
D ′ [x]
D[x]
D ′ [x]
′
=
D [x] · ′ · ln ′′
D[x] · ln ′′
D [x]
D [x]
D [x]
x∈X
x∈X


′
X
[x]
D ′ [x]
−ln D
′
D[x]
=
D [x] · e
· ln ′′
D [x]
x∈X


X
D ′ [x]
D ′ [x]
−(ln D[x] −DKL (D ′ ||D)+DKL (D ′ ||D))
′
· ln ′′
=
D [x] · e
D [x]
x∈X


X
′
D ′ [x]
= e−DKL (D ||D) ·
D ′ [x] · e−S(x) · ln ′′
D [x]
x∈X


X
D ′ [x]
≤
D ′ [x] · e−S(x) · ln ′′
D [x]
x∈X


D ′ [x] −S(x)
·e
= E ′ ln ′′
x∼D
D [x]
where the next-to-last inequality is by non-negativity of KL-divergence. Recall that S(x) denotes
the centered log-ratio of probabilities by D ′ and by D (and is τ1 -Subgaussian). By Lemma 2.3 we
conclude that:



X
D ′ [x] −S(x)
D ′ [x]
·e
≤ E ′ ln ′′
D[x] · ln ′′
x∼D
D [x]
D [x]
x∈X
p

Var (S ′′ ) + DKL (D ′ ||D ′′ ) · (τ1 + 3τ12 )
≤ DKL (D ′ ||D ′′ ) +

q
2
τ2 + µ2 · (τ1 + 3τ12 )
≤ µ2 +

= µ2 + τ1 · τ2 + (3τ12 · τ2 ) + ((τ1 + 3τ12 ) · µ2 )
(14)
Putting together Equations (13) and (14) we get that:


DKL (D||D ′′ ) ≤ µ1 + µ2 + τ1 · τ2 + (3τ12 · τ2 ) + ((τ1 + 3τ12 ) · µ2 )

4.2

Group Privacy: Bounding the Subgaussian Standard

Lemma 4.3. Let D, D ′ , D ′′ be distributions over domain X , such that DsubG (D||D ′ ), DsubG (D ′ ||D) 
(µ1 , τ1 ) and that DsubG (D ′ ||D ′′ ), DsubG (D ′′ ||D ′ )  (µ2 , τ2 ). Suppose moreover that τ1 , τ2 ≤ τ ≤ 1/4
and that µ1 , µ2 ≤ τ 2 /2. Then for any real λ:


′′
λ2
1.5 2
λ·(ln DD[x]
′′ [x] −DKL (D||D ))
E e
≤ e 2 ·(2τ +34τ )
(15)
x∼D

i.e. the (centered) privacy-loss random variable from D to D ′′ is subgaussian, and its standard is
bounded by 2τ + O(τ 1.5 ).

22

Proof. We assume without loss of generality that:
λ · DKL (D ′ ||D) ≥ λ · DKL (D ′ ||D ′′ )

⇒ (λ + 1) · DKL (D ′ ||D) ≥ λ · DKL (D ′ ||D ′′ )

(16)

(otherwise we flip the roles of D and D ′′ ). As in the proof of Lemma 4.2, for x ∈ X , we define
′ [x]
′
′′
S to be the centered value S(x) = ln D
D[x] − DKL (D ||D), and S (x) to be the centered value
′

D [x]
′
′′
′
′′
S ′′ (x) = ln D
′′ [x] − DKL (D ||D ). Recall that when x is drawn by D [x], both S[x] and S [x] are
(centered) subgaussian random variables.
We want to show that Inequality (15) holds for any real λ. We proceed with a case analysis for
the value of λ as a function of τ .

Case I: |λ| ≥ 8√1 τ . Observe that:

 X

λ·ln DD[x]
λ·ln DD[x]
′′ [x]
′′ [x]
E e
=
D[x] · e
x∼D

x∈X

=

X

x∈X

=

X

x∈X

=

X

x∈X

D[x]
D ′ [x]

′

ln

′

−(λ+1)·ln

D [x] · e
D [x] · e

D[x]
D ′ [x]
+ln D
′′ [x] )
D ′ [x]

λ·(ln

·e

D ′ [x]
D[x]

λ·ln

·e

D ′ [x]
D ′′ [x]





′

D ′ [x] · e−(λ+1)·(S(x)+DKL (D ||D)) · eλ·(S

′′ (x)+D

KL (D

′ ||D ′′ ))




 X

′′
′
′
′′
D ′ [x] · e−(λ+1)·S(x) · eλ·S (x)
= e(−(λ+1)·DKL (D ||D))+(λ·DKL (D ||D )) ·
x∈X

≤

X

x∈X

′

−(λ+1)·S(x)

D [x] · e

λ·S ′′ (x)

·e



where the last inequality is by Equation (16). Recall that S(x) and S ′′ (x) are both subgaussian
(when x is drawn by D ′ [x]), with standards τ1 , τ2 . Applying the Cauchy-Schwartz inequality to the
above, we conclude:
 sX

sX
D[x]
λ·ln D ′′ [x]
′′
′
−2(λ+1)·S(x)
≤
E e
D [x] · e
·
D ′ [x] · e−2λ·S (x)
x∼D

x∈X

≤

p

2 +4λ+2)·τ 2
1

e(2λ

2 ·τ 2 +λ2 ·τ 2
1
2

= e(λ+1)

Since |λ| ≥

1
√
,
8 τ

x∈X

·

p

2 ·τ 2
2

e2λ

we have that:
1 2
)
λ√
≤ λ2 · (1 + 8 τ )2
√
= λ2 · (1 + 16 τ + 64τ )
√
≤ λ2 · (1 + 48 τ )

(λ + 1)2 = λ2 · (1 +

23

(17)

(recall also that τ ≤ 1/4, so τ ≤
E
x∼D

√


τ /2). Plugging this into Equation (17), we get that:

D[x]
2 2
2 2
λ·ln D ′′ [x]
e
≤ e(λ+1) ·τ1 +λ ·τ2
√

2 ·τ 2 ·(1+48
1

≤ e(λ

τ ))+(λ2 ·τ22 )

2 ·(τ 2 +τ 2 +48τ 2.5 )
1
2

≤ eλ
≤e
1
√
,
8 τ

We conclude that for λ ≥
Case II: |λ| <

1
√
8 τ





E
x∼D

λ·ln

e

D[x]
D ′′ [x]

λ2
·(2τ +12τ 1.5 )2
2

.

the “standard” is bounded by (2τ + 12τ 1.5 ).

Taking a Taylor expansion, we get that:



 X

∞
λk
λ2
2 D[x]
k D[x]
· E ln
· E ln
= 1 + λ · DKL (D||D ) +
+
2 x∼D
D ′′ [x]
k! x∼D
D ′′ [x]
′′

(18)

k=3

(where we observe that the linear summand in the Taylor expansion is the expected log ratio or
“privacy loss” from D to D ′′ ). In the following two claims, we bound the higher moments in the
Taylor expansion:
Claim 4.4.
E
x∼D




D[x]
≤ 2(τ12 + τ22 ) + 2µ21 + 2µ22 + 50τ1 · τ22
ln
D ′′ [x]
2

≤ 4τ 2 + 51τ 3

≤ 4τ 2 + 26τ 2.5

(19)

Claim 4.5.
∞
X
λk
k=3

k!

· E

x∼D



lnk


D[x]
≤ (33 · τ12.5 · λ2 ) + (32 · τ22.5 · λ2 )
D ′′ [x]
≤ 55 · τ 2.5 · λ2

The proofs of Claims 4.4 and 4.5 follow below. Before presenting these proofs, we complete the
proof of the bound for case II. Plugging the bounds from the Claims into Inequality (18) we get:


D[x]
λ2 · (4τ 2 + 26τ 2.5 )
λ·ln D ′′ [x]
+ 55τ 2.5 · λ2
E e
= 1 + λ · DKL (D||D ′′ ) +
x∼D
2
4λ2 · τ 2
+ 68τ 2.5 · λ2
= 1 + λ · DKL (D||D ′′ ) +
2
≤ eλ·DKL (D||D
≤ eλ·DKL (D||D

2
′′ )+ λ ·((2τ )2 +136τ 2.5 )
2
2
′′ )+ λ ·(2τ +34τ 1.5 )2
2

Thus, for the centered privacy-loss random variable we have:


′′
λ2
1.5 2
λ·(ln DD[x]
′′ [x] −DKL (D||D ))
≤ e 2 ·(2τ +34τ )
E e
x∼D

24

We conclude that for λ < 8√1 τ , the “standard” is bounded by (2τ + 34τ 1.5 ).
Before proceeding to prove the claims, we state and prove the following useful fact:
Fact 4.1. For a real value k ≥ 1 and for any two reals a, b:

(a + b)k ≤ 2k−1 · (ak + bk )

Proof. Since the function xk is convex, by Jensen’s inequality we have:


2a 2b k
(2a)k + (2b)k
k
(a + b) =
≤
+
= 2k−1 · (ak + bk )
2
2
2
Proof of Claim 4.4. We observe that, since (a + b)2 ≤ 2a2 + 2b2 (for all a, b, see Fact 4.1):




D ′ [x] 2
D[x]
2 D[x]
E ln
= E (ln ′ + ln ′′ )
x∼D
x∼D
D ′′ [x]
D [x]
D [x]




′
2 D[x]
2 D [x]
≤ 2 E ln
+ 2 E ln
x∼D
x∼D
D ′ [x]
D ′′ [x]


D ′ [x]
≤ 2(τ12 + µ21 ) + 2 E ln2 ′′
x∼D
D [x]

(20)

where the last inequality uses Fact 2.1 (and the fact that E[X 2 ] = Var (X) + (E[X])2 for any RV
X). To bound the second summand in Inequality (20), we use Lemma 2.3 and conclude that:




′ [x]
′
′
− ln D
2 D [x]
2 D [x]
D[x]
·e
= E ′ ln
E ln
x∼D
x∼D
D ′′ [x]
D ′′ [x]
 s



′
′
2 D [x]
4 D [x]
≤ E ′ ln
+
· (τ1 + 3τ12 )
E
ln
x∼D
x∼D ′
D ′′ [x]
D ′′ [x]
 q

′
2 D [x]
= E ′ ln
+
E [(S ′′ (x) + DKL (D ′ ||D ′′ ))4 ] · (τ1 + 3τ12 )
x∼D
x∼D ′
D ′′ [x]
 q

′
2 D [x]
+ 8 · ( E ′ [S ′′ (x)4 ] + DKL (D ′ ||D ′′ )4 ) · (τ1 + 3τ12 )
≤ E ′ ln
D ′′ [x]
x∼D
x∼D

where the last inequality uses Fact 4.1 (with k = 4). By the bound on the 4-th moment of the
subgaussian S ′′ (x) (Fact 2.2), we conclude that:


q
′
2 D [x]
2
2
8 · (16τ24 + µ42 ) · (τ1 + 3τ12 )
E ln
≤
(τ
+
µ
)
+
2
2
x∼D
D ′′ [x]
q
≤ (τ22 + µ22 ) + 8 · (16τ24 + µ42 ) · 2τ1
≤ (τ22 + µ22 ) + 24τ1 · τ22 + 6τ1 · µ22
≤ (τ22 + µ22 ) + 25τ1 · τ22

Claim 4.4 follows from inequalities (20) and (21):


2 D[x]
E ln
≤ 2(τ12 + µ21 ) + 2(τ22 + µ22 + 25τ1 · τ22 )
x∼D
D ′′ [x]
≤ 2(τ12 + τ22 ) + 2µ21 + 2µ22 + 50τ1 · τ22

25

(21)

Proof of Claim 4.5. Observe that, by Fact 4.1:




D ′ [x] k
D[x]
k D[x]
= E (ln ′ + ln ′′ )
E ln
x∼D
x∼D
D ′′ [x]
D [x]
D [x]


′
D[x]
k−1
k
k D [x]
≤ E 2
· (ln
+ ln
)
x∼D
D ′ [x]
D ′′ [x]





′
k−1
k D[x]
k D [x]
=2
· E ln
+ E ln
x∼D
x∼D
D ′ [x]
D ′′ [x]

(22)

By Fact 2.2, and using also Fact 4.1, the first term is bounded by:



h
i
k−1
k
′ k
k D[x]
≤2
· E S(x) + DKL (D||D )
E ln
x∼D
x∼D
D ′ [x]

≤ (2k−1 · 2⌈k/2⌉+1 · (⌈k/2⌉)! · τ1k ) + (2µ1 )k /2
= (2τ1 )k · 2⌈k/2⌉ · (⌈k/2⌉)! + (2µ1 )k /2

√ 
≤ (2τ1 )k · 2k/2+1 · k! + (2µ1 )k /2

(23)

We bound the second term using Lemma 2.3 and Fact 4.1:




′
′
D[x]
− ln D
k D [x]
k D [x]
′ [x]
E ln
·e
= E ′ ln
x∼D
x∼D
D ′′ [x]
D ′′ [x]
 s



′
′
2k D [x]
k D [x]
+
· (τ1 + 3τ12 )
E ln
≤ E ′ ln
x∼D ′
x∼D
D ′′ [x]
D ′′ [x]
s


i
h
′
′′
k
′
′′ k
k−1
2k D [x]
· (τ1 + 3τ12 )
≤2
· E ′ S (x) + DKL (D ||D ) +
E ln
D ′′ [x]
x∼D
x∼D ′


 s

h
i
′
k−1
′′
k
k
2k D [x]
≤2
· (τ1 + 3τ12 )
E S (x) + µ2 +
E ln
x∼D ′
x∼D ′
D ′′ [x]
 q

i
h
k
′′
k
k−1
≤2
E S (x) + µ2 + 22k−1 · E ′ [S ′′ (x)2k + DKL (D ′ ||D ′′ )2k ] · (τ1 + 3τ12 )
x∼D ′
x∼D
 q


q
i
h
k
′′
k
k−1
2k
′′
2k
2k−1
2k−1
· E ′ [S (x) ] + 2
≤2
·
E S (x) + µ2 +
2
· µ2 · (τ1 + 3τ12 )
x∼D
x∼D ′
i q
h
≤ 2k−1 · E ′ S ′′ (x)k + 22k−1 · E ′ [S ′′ (x)2k ] · (τ1 + 3τ12 ) + (2µ2 )k ,
x∼D

x∼D

where the last inequality follows because τ1 + 3τ12 ≤ 7/16 < 1/2. By Fact 2.2, we conclude from
the above that:

 

 q
′
k D [x]
k
⌈k/2⌉
2
2k
E ln
≤ (2τ2 ) · 2
· (⌈k/2⌉)! +
22k−1 · 2k+1 · (k!) · τ2 · (τ1 + 3τ1 ) + (2µ2 )k
x∼D
D ′′ [x]


 
√
= (2τ2 )k · 2⌈k/2⌉ · (⌈k/2⌉)! + (2τ2 )k · 2k/2 · k! · (τ1 + 3τ12 ) + (2µ2 )k

√ 
≤ (2τ2 )k · 2k/2+1 · k! + (2µ2 )k
(24)
26

Plugging the bounds from Equations (23) and (24) into Equation (22), we conclude that:

 
 
√ 
k D[x]
k
k
k/2
k! + (2µ2 )k + (2µ2 )k
E ln
≤
(4τ
)
+
(4τ
)
·
2
·
1
2
x∼D
D ′′ [x]
 

√ 
≤ (4τ1 )k + (4τ2 )k · 2k/2 · k! + 2 · (2µ1 )k
Using the fact that for k ≥ 3 we have
∞
X
λk
k=3

k!

· E

x∼D



√
2k/2 · k!
k!

(25)

< 2, we get that:

 X
∞


D[x]
(2µ1 · λ)k
k
k
ln
≤
+
2
·
2
(4τ
·
λ)
+
(4τ
·
λ)
1
2
D ′′ [x]
k!
k=3
!
!
∞
∞
X
X
= 2 · (4τ1 · λ)3 ·
(4τ1 · λ)k + (µ1 · λ)2
(4τ1 · λ)k + 2 · (4τ2 · λ)3 ·
k

k=0

k=0

k

where the last inequality uses the fact that for k ≥ 3, we have (2µ1k!·λ) < (µ1 · λ)2 · (1/4)k (because
√
we assume here that λ < 1/8 τ , so µ1 · λ ≤ τ 1.5 /16 < 1/128). Moreover, since 4τ1 · λ, 4τ2 · λ ≤ 1/2,
the geometric sums above converge to a value smaller than 2, and we get:
∞
X
λk
k=3

Finally, since

√

k!

τ1 · λ,

∞
X
λk
k=3

· E

k!

x∼D

√



lnk


D[x]
≤ 44 · (τ1 · λ)3 + 44 · (τ2 · λ)3 + (µ2 · λ)2
D ′′ [x]

τ2 · λ ≤ 1/8, and µ2 ≤ τ12 /2, we get that:

· E

x∼D




D[x]
ln
≤ (32 · τ12.5 · λ2 ) + (32 · τ22.5 · λ2 ) + (τ14 · λ2 )
D ′′ [x]
k

≤ (33 · τ12.5 · λ2 ) + (32 · τ22.5 · λ2 )

References
[BK00]

V.V. Buldygin and I.U.V. Kozachenko. Metric Characterization of Random Variables
and Random Processes. Cross Cultural Communication. American Mathematical Soc.,
2000.

[BS15]

Mark Bun and Thomas Steinke. Concentrated differential privacy revisited. Manuscript,
2015.

[DKM+ 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni
Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in
Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory
and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June
1, 2006, Proceedings, pages 486–503, 2006.
27

[DL09]

C. Dwork and J. Lei. Differential privacy and robust statistics. In STOC, 2009.

[DMNS06] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in
private data analysis. In TCC, pages 265–284, 2006.
[DMT07]

C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of lp
decoding. In STOC, pages pp. 85–94, 2007.

[DN03]

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In PODS,
pages 202–210, 2003.

[DRV10]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential
privacy. In FOCS, pages 51–60, 2010.

[Dwo06]

C. Dwork. Differential privacy. In ICALP, pages 1–12, 2006.

[Kah60]

J. Kahane. Proprits locales des fonctions sries de fourier alatoires. Studia Mathematica,
19(1):1–25, 1960.

[KOV15]

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for
differential privacy. In ICML, pages 1376–1385, 2015.

[MV16]

Jack Murtagh and Salil P. Vadhan. The complexity of computing the optimal composition of differential privacy. In TCC(A), pages 157–175, 2016.

[Riv12]

Omar Rivasplata. Subgaussian random variables: An expository note. Unpublished
note, 2012.

28

