Lower Bounds for Differential Privacy from Gaussian Width
Assimakis Kattis

arXiv:1612.02914v1 [] 9 Dec 2016

1,2

∗1

and Aleksandar Nikolov

†2

Department of Computer Science, University of Toronto.

Abstract
We study the optimal sample complexity of a given workload of linear queries under the
constraints of differential privacy. The sample complexity of a query answering mechanism under
error parameter α is the smallest n such that the mechanism answers the workload with error
at most α on any database of size n. Following a line of research started by Hardt and Talwar
[STOC 2010], we analyze sample complexity using the tools of asymptotic convex geometry. We
study the sensitivity polytope, a natural convex body associated with a query workload that
quantifies how query answers can change between neighboring databases. This is the information
that, roughly speaking, is protected by a differentially private algorithm, and, for this reason,
we expect that a “bigger” sensitivity polytope implies larger sample complexity. Our results
identify the mean Gaussian width as an appropriate measure of the size of the polytope, and
show sample complexity lower bounds in terms of this quantity. Our lower bounds completely
characterize the workloads for which the Gaussian noise mechanism is optimal up to constants
as those having asymptotically maximal Gaussian width.
Our techniques also yield an alternative proof of Pisier’s Volume Number Theorem which
also suggests an approach to improving the parameters of the theorem.

1

Introduction

The main goal of private data analysis is to estimate aggregate statistics while preserving individual
privacy guarantees. Intuitively, we expect that, for statistics that do not depend too strongly on
any particular individual, a sufficiently large database allows computing an estimate that is both
accurate and private. A natural question then is to characterize the sample complexity under
privacy constraints: the smallest database size for which we can privately estimate the answers
to a given collection of queries within some allowable error tolerance. Moreover, it is desirable to
identify algorithms that are simple, efficient, and have close to the best possible sample complexity.
In this work, we study these questions for collections of linear queries under the constraints of
approximate differential privacy.
We model a database D of size n as a multiset of n elements (counted with repetition) from
an arbitrary finite universe U . Each element of the database corresponds to the data of a single
individual. To define a privacy-preserving computation on D, we use the strong notion of differential
privacy. Informally, an algorithm is differentially private if it has almost identical behavior on any
two databases D and D ′ that differ in the data of a single individual. To capture this concept
formally, let us define two databases to be neighboring if they have symmetric difference of size at
most 1 (counted with multiplicity). Then differential privacy is defined as follows:
∗
†

Email:kattis@cs.toronto.edu
Email:anikolov@cs.toronto.edu

1

Definition 1 ([DMNS06]). A randomized algorithm A that takes as input a database and outputs
a random element from the set Y satisfies (ε, δ)-differential privacy if for all neighboring databases
′
D, D and all measurable S ⊆ Y we have that:
′

P[A(D) ∈ S] ≤ eε P[A(D ) ∈ S] + δ,
where probabilities are taken with respect to the randomness of A.
One of the most basic primitives in private data analysis, and data analysis in general, are
counting queries and, slightly more generally, linear queries. While interesting and natural in
themselves, they are also quite powerful: any statistical query (SQ) learning algorithm can be
implemented using noisy counting queries as a black box [Kea98]. In our setting, we specify a
linear query by a function q : U → [0, 1] (given
by its truth table). Slightly abusing notation, we
1 P
define the value of the query as q(D) = n e∈D q(e), where the elements of D are counted with
multiplicity. For example, when q : U → {0, 1}, we can think of q as a property defined on U and
q(D) as the fraction of elements of D that satisfy the property: this is a counting query. We call a
set Q of linear queries a workload and an algorithm that answers a query workload a mechanism.
We denote by Q(D) = (q(D))q∈Q the vector of answers to the queries in Q. Throughout the paper,
we will use the letter m for the size of a workload Q.
Starting from the work of Dinur and Nissim [DN03], it is known that we cannot hope to answer
too many linear queries too accurately while preserving even a very weak notion of privacy. For this
reason, we must allow our private mechanisms to make some error. We focus on average error (in
an L2 sense). We define the average error of an algorithm A on a query workload Q and databases
of size at most n as:
1/2

1/2

X (A(D)q − q(D))2
1
2


,
= max E kA(D) − Q(D)k2
err(Q, A, n) = max E
D
D
|Q|
m
q∈Q

where the maximum is over all databases D of size at most n, A(D)q is the answer to query q given
by the algorithm A on input D, and expectations are taken with respect to the random choices of
A. This is a natural notion of error that also works particularly well with the geometric tools that
we use.
In this work we study sample complexity: the smallest database size which allows us to answer
a given query workload with error at most α. The sample complexity of an algorithm A with error
α is defined as:
sc(Q, A, α) = min{n : err(Q, A, n) ≤ α}.
The sample complexity of answering the linear queries Q with error α under (ε, δ)-differential
privacy is defined by:
scε,δ (Q, α) = inf{sc(Q, A, α) : A is (ǫ, δ)-differentially private}.
The two main questions we are interested in are:
1. Can we characterize scε,δ (Q, α) in terms of a natural property of the workload Q?
2. Can we identify conditions under which simple and efficient (ε, δ)-differentially private mechanisms have nearly optimal sample complexity?

2

We make progress on both questions. We identify a geometrically defined property of the workload
that gives lower bounds on the sample complexity. The lower bounds also characterize when one of
the simplest differentially private mechanisms, the Gaussian noise mechanism, has nearly optimal
sample complexity in the regime of constant α.
Before we can state our results, we need to define a natural geometric object associated with
a workload of linear queries. This object has been important in applying geometric techniques to
differential privacy [HT10, BDKT12, NTZ13, Nik15].
Definition 2. The sensitivity polytope K of a workload Q of m linear queries is equal to K =
conv{±Q(D) : D is a database of size 1}.
From the above definition, we see that K is a symmetric (i.e. K = −K) convex polytope in
Rm . The importance of K lies in the fact that it captures how query answers can change between
neighboring databases: for any two neighboring databases D and D ′ of size n and n′ respectively,
nQ(D) − n′ Q(D ′ ) ∈ K. This is exactly the information that a differentially private algorithm is
supposed to hide. Intuitively, we expect that the larger K is, the larger scε,δ (K, α) should be.
We give evidence for the above intuition, and propose the width of K in a random direction as
a measure of its “size”. Let hK be the support function of K: hK (y) = maxx∈K hx, yi. For a unit
vector y, hK (y) + hK (−y) is the width of K in the direction of y; for arbitrary y, hK (ty) scales
linearly with t (and is, in fact, a norm). We define the ℓ∗ -norm of K, also known as its Gaussian
mean width, as ℓ∗ (K) = E[hK (g)], where g is a standard Gaussian random vector in Rm . The
following theorem captures our main result.
Theorem 1. Let Q be a workload of m linear queries, and let K be its sensitivity
polytope. The
ℓ∗ (K)
,
where
C is an
following holds for all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , and any α ≤ Cm(log
2m)2
p
√
absolute constant, and σ(ε, δ) = (0.5 ε + 2 log (1/δ))/ε:

n σ(ε, δ)ℓ∗ (K) σ(ε, δ)√m o
√
scε,δ (Q, α) = O min
;
,
α
mα2


σ(ε, δ)ℓ∗ (K)2
.
scε,δ (Q, α) = Ω
m3/2 (log 2m)4 α
The upper bound on sample complexity is achieved by a mechanism 
running
in time polynomial in
√ 
m
m, n, and |U |. Moreover, if ℓ∗ (K) = Ω(m), then scε,δ (Q, α) = Θ σ(ε,δ)
for any α ≤ 1/C,
α
where C is an absolute constant.
The sample complexity upper bounds in the theorem above are known from prior work: one
is given by the projection mechanism from [NTZ13], with the sample complexity upper bound in
terms of ℓ∗ (K) shown in [DNT14]; the other upper bound is given by the Gaussian noise mechanism [DN03, DN04, DMNS06]. The main new contribution in this work are the lower bounds on
sample complexity. The gap between upper and lower bounds is small when ℓ∗ (K) is close to its
maximal value of m. Indeed, when ℓ∗ (K) = Θ(m), our results imply that the Gaussian noise mechanism has optimal sample complexity up to constants. This is, to the best of our knowledge, the first
example of a general geometric condition under which a simple and efficient mechanism has optimal
sample complexity up to constant factors. Moreover, in the constant error regime this condition
is also necessary for the Gaussian mechanism to be optimal up to constants: when ℓ∗ (K) = o(m)
and α = Ω(1), the projection mechanism has asymptotically smaller sample complexity than the
Gaussian mechanism.
We can prove somewhat stronger results for another natural problem in private data analysis,
which we call the mean point problem. In this problem, we are given a closed convex set K ⊂ Rm ,
3

and we are asked to approximate P
the mean D of the database D, where D = {x1 , . . . , xn } is a
1
multiset of points in K and D = n ni=1 xi . This problem, which will be the focus for most of this
paper, has a more geometric flavor, and is closely related to the query release problem for linear
queries. In fact, Theorem 1 will essentially follow from a reduction from the results below for the
mean point problem.
With respect to the mean point problem, we define the error of an algorithm A as:
err(K, A, n) = sup(EkA(D) − Dk22 )1/2 ,
D

where the supremum is over databases D consisting of at most n points from K, and the expectation
is over the randomness of the algorithm. The sample complexity of an algorithm A with error α is
defined as:
sc(K, A, α) = min{n : err(K, A, n) ≤ α}.
The sample complexity of solving the mean point problem with error α over K is defined by:
scε,δ (K, α) = min{sc(K, A, α) : A is (ǫ, δ)-differentially private}.
Our main result for the mean point problem is given in the following theorem:
Theorem 2. Let K be a symmetric convex body contained in the unit Euclidean ball B2m in Rm .
ℓ∗ (K)
The following holds for all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , and any α ≤ C √m(log
, where C
2m)2
p
√
is an absolute constant, and σ(ε, δ) = (0.5 ε + 2 log (1/δ))/ε:

n σ(ε, δ)ℓ∗ (K) σ(ε, δ)√ m o
;
,
scε,δ (K, α) = O min
α2
α


σ(ε, δ)ℓ∗ (K)
scε,δ (K, α) = Ω
.
(log 2m)2 α
The upper bound on sample complexity is achieved by a mechanism running
in time polynomial in

√ 
√
m
m, n, and |U |. Moreover, when ℓ∗ (K) = Ω( m), then scε,δ (Q, α) = Θ σ(ε,δ)
for any α ≤ 1/C,
α
where C is an absolute constant.
The upper bounds again follow from prior work, and in fact are also given by the projection
mechanism and the Gaussian noise mechanism, which can be defined for the mean point problem
2
as well. Notice that the gap between the upper and the lower bound is on the order (log α2m) . If the
lower bound ∗was valid for all values of the error parameter α less than a fixed constant, rather than
ℓ (K)
, Theorem 2 would nearly characterize the optimal sample complexity for the
for α ≤ C √m(log
2m)2
mean point problem for all constant α. Unfortunately, the restriction on α is, in general, necessary
(up to the logarithmic terms) for lower bounds on sample complexity in terms of ℓ∗ (K). For
√
example, we can take K = γB2m , i.e. a Euclidean ball in Rm with radius γ. Then, ℓ∗ (K) = Θ(γ m),
but the sample complexity is 0 when α > γ, since the trivial algorithm which ignores the database
and outputs 0 achieves error γ. Thus, a more sensitive measure of the size of K is necessary to
prove optimal lower bounds. We do, nevertheless, trust that the techniques introduced in this
paper bring us closer to this goal.
We conclude this section with a high-level overview of our techniques. Our starting point is a
recent tight lower bound on the sample complexity of a special class of linear queries: the 1-way
marginal queries. These queries achieve the worst case sample complexity for a family of m linear
√
queries: Ω( m/α) [BUV14, SU15]. The sensitivity polytope of the 1-way marginals is the cube
4

[−1, 1]m , and it can be shown that the lower bound on the sample complexity of 1-way marginals
implies an analogous lower bound on the sample complexity of the mean point problem with
√
√
K = Qm = [−1/ m, 1/ m]m . For the mean point problem, it is easy to see that when K ′ ⊆ K,
the sample complexity for K ′ is no larger than the sample complexity for K. Moreover, we can
show that the sample complexity of any projection of K is no bigger than the sample complexity
′
of K itself. So, our strategy then is to find a large scaled copy of Qm , m′ ≤ m, inside a projection
of K onto a large dimensional subspace whenever ℓ∗ (K) is large. We solve this geometric problem
using deep results from asymptotic convex geometry, namely the Dvoretzky criterion, the low M ∗
estimate, and the M M ∗ estimate.
Our techniques also yield an alternative proof of the volume number theorem of Milman and
Pisier [MP87]. Besides avoiding the quotient of subspace theorem, our proof yields an improvement
in the volume number theorem, conditional on the well-known conjecture that√
any symmetric convex
∗
body K has a position (affine image) T K for which ℓ (T K)ℓ(T K) = O(m log 2m), where ℓ(K)
is the expected K-norm of a standard Gaussian. More details about this connection are given in
Section 7.

1.1

Prior Work

Most closely related to our work are the results of Nikolov, Talwar, and Zhang [NTZ13], who gave a
private mechanism (also based on the projection mechanism, but more involved) which has nearly
optimal sample complexity (with respect to average error), up to factors polynomial in log m and
log |U |. This result was subsequently improved by Nikolov [Nik15], who showed that the log m
factors can be replaced by log n. While these results are nearly optimal for subconstant values of
the error parameter α, i.e. the optimality guarantees do not depend on 1/α, factors polynomial in
log |U | can be prohibitively large. Indeed, in many natural settings, such as that of marginal queries,
|U | is exponential in the number of queries m, so the competitiveness ratio can be polynomial in
m.
The line of work that applies techniques from convex geometry to differential privacy started
with the beautiful paper of Hardt and Talwar [HT10], whose results were subsequently strengthened
in [BDKT12]. These papers focused on the “large database” regime (or, in our language, the setting
of subconstant error), and pure differential privacy (δ = 0).

2

Preliminaries

We begin with the introduction of some notation. Throughout the paper we use C, C1 , etc., for
absolute constants, whose value may change from line to line. We use k · k2 for the Euclidean norm,
and k · k1 for the ℓ1 norm. We define B1m and B2m to be the ℓ1 and ℓ2 unit balls in Rm respectively,
while Qm = [− √1m , √1m ]m ⊆ Rm will refer to the m-dimensional hypercube, normalized to be
contained in the unit Euclidean ball. We use Im for the identity operator on Rm , as well as for
the m × m identity matrix. For a given subspace E, we define ΠE : Rm → Rm as the orthogonal
projection operator onto E. Moreover, when T : E → F is a linear operator between the subspaces
E, F ⊆ Rm , we define kT k = max{kT xk2 : kxk2 = 1} as its operator norm, which is also equal to its
largest singular value σ1 (T ). For the diameter of a set K we use the nonstandard, but convenient,
definition diam K = max {kxk2 : x ∈ K}. For sets symmetric around 0, this is equivalent to the
standard definition, but scaled up by a factor of 2. We use N (µ, Σ) to refer to the Gaussian
distribution with mean µ and covariance Σ, and we use the notation x ∼ N (µ, Σ) to denote that x
is distributed as a Gaussian random variable with mean µ and covariance Σ. For a m×m matrix (or

5

m
equivalently an operator from ℓm
2 to ℓ2 ) A we use A  0 to denote that A is positive semidefinite.
For positive semidefinite matrices/operators A, B, we use the notation A  B to denote B − A  0.

3

Probability Theory

We make use of some basic comparison theorems from the theory of stochastic processes. First
we state the well-known symmetrization lemma. We also give the short proof for completeness.
Recall that ξ1 , . . . , ξn are a sequence of Rademacher random variables if each ξi is uniformly and
independently distributed in {−1, 1}.
Lemma 1 (Symmetrization). Let p > 1, and let k · k be a norm on Rm . Then, for any sequence
x1 , . . . , xn of independent random variables in Rm such that Ekxi kp is finite for every i, we have
X
X
X
p
p
ξ i xi ,
xi − E
xi ≤ 2p E
E
i

i

i

where ξ1 , . . . , ξn are Rademacher random variables, independent of x1 , . . . , xn . Each expectation
above is with respect to all random variables involved.
P
P
Proof. Let x′1 , . . . , x′n be independent copies of x1 , . . . , xn . Then, E i xi = E i x′i , and, by
convexity of the function k · kp and Jensen’s inequality,
X
X
X
X
X
p
p
p
xi − E
x′i ≤ E
xi − x′i .
xi − E
xi = E
E
i

i

i

i

i

Because xi and x′i are independent and identically distributed,
the random
x′i and
P
Pvariables x′ i −
′
′
p
p
xi − xi are also identically distributed. Therefore, Ek i xi − xi k = Ek i ξi (xi − xi )k , where
ξ1 , . . . , ξn are independent Rademacher random variables, as in the statement of the lemma. Finally,
by Minkowski’s inequality (i.e. triangle inequality for Lp ), we have
!
1/p p
 X
 X
X
X
p 1/p
p
p
ξi (xi − x′i ) ≤
ξ i xi
+ Ek
ξi x′i kp
E
E
ξ i xi ,
= 2p E
i

i

i

i

as desired.
Next we state a simple comparison theorem for Gaussian random variables.
Lemma 2. Let x ∼ N (0, Σ) and x′ ∼ N (0, Σ′ ) be Gaussian random variables in Rm , and assume
Σ  Σ′ . Then, for any norm k · k on Rm , we have:
Ekxk ≤ Ekx′ k.
Proof. Couple x and x′ so that they are independent, and define a new random variable y ∼
N (0, Σ′ − Σ), independent of x and x′ . Then the random variables x + y and x − y are distributed
identically to x′ , and, by linearity of expectation and the triangle inequality we have


kx + yk + kx − yk
′
≥ Ekxk.
Ekx k = E
2
This completes the proof.
Note that the same conclusion follows under weaker assumptions from Slepian’s lemma.
6

3.1

Convex Geometry

In this section, we outline the main geometric tools we use in later sections. For a more detailed
treatment, we refer to the lecture notes by Vershynin [Ver09] and the books by Pisier [Pis89] and
Artstein-Avidan, Giannopoulos, and Milman [AAGM15].
Throughout, we define a convex body K as a compact subset of Rm with non-empty interior. A
convex body K is (centrally) symmetric if and only if K = −K. We define the polar body K ◦ of K
as: K ◦ = {y : hx, yi ≤ 1 ∀x ∈ K}. The following basic facts are easy to verify and very useful.
Fact 1. For convex bodies K, L ⊆ Rm , K ⊆ L ⇔ L◦ ⊆ K ◦ .
Fact 2 (Section/Projection Duality). For a convex body K ⊆ Rm and a subspace E ⊆ Rm :
1. (K ∩ E)◦ = ΠE (K ◦ );
2. (ΠE (K))◦ = K ◦ ∩ E.
In both cases, the polar is taken in the subspace E.
Fact 3. For any invertible linear map T and any convex body K, T (K)◦ = T −∗ (K ◦ ), where T −∗
is the inverse of the adjoint operator T ∗ .
A simple special case of Fact 3 is that, for any convex body K, (rK)◦ =
property alongside Fact 1, we have the following useful corollary.

1 ◦
rK .

Using this

Corollary 1. For a convex body K ⊆ Rm and E ⊆ Rm a subspace with k = dim E, the following
two statements are equivalent:
1. ΠE (rB2m ) ⊆ ΠE (K);
2. K ◦ ∩ E ⊆ 1r (B2m ∩ E),
where, as before, taking the polar set is considered in the subspace E. Notice that the second
statement is also equivalent to diam(K ◦ ∩ E) ≤ 1r .
Our work relies on appropriately quantifying the “size” of (projections and sections of) a convex
body. It turns out that, for our purposes, the right measure of size is related to the notion of width,
captured by the support function. Recall from the introduction that the support function of a
convex body K ⊂ Rm is given by hK (y) = maxx∈K hx, yi for every y ∈ Rm . The support function
is intimately related to the Minkowski norm k · kK , defined for a symmetric convex body K ⊆ Rm
by kxkK = min {r ∈ R : x ∈ rK}, for every x ∈ Rm . It is easy to verify that k · kK is indeed a
norm. The support function hK is identical to the Minkowski norm of the polar body K ◦ (which
is also the dual norm to k · kK ): hK (y) = kykK ◦ for every y ∈ Rm .
Now we come to the measure of the “size” of a convex body which will be central to our results:
the Gaussian mean width of the body, defined next.
Definition 3. The Gaussian mean width and Gaussian mean norm of a symmetric convex body
K ⊆ Rm are defined respectively as:
ℓ∗ (K) = EkgkK ◦ = E[hK (g)],

ℓ(K) = EkgkK ,

where g ∼ N (0, Im ) is a standard Gaussian random variable.
7

The next lemma gives an estimate of how the mean width changes when applying a linear
transformation to K.
m
Lemma 3. For any symmetric convex body K ⊂ Rm , and any linear operator T : ℓm
2 → ℓ2 :

ℓ∗ (T (K)) ≤ kT kℓ∗ (K).
Proof. Notice that, for a standard Gaussian g ∼ N (0, Im ),
ℓ∗ (T (K)) = E sup hT (x), gi = E sup hx, T ∗ (g)i = EkT ∗ (g)kK ◦ .
x∈K

x∈K

Treating T ∗ T as an m × m matrix in the natural way, we see that T ∗ (g) ∼ N (0, T ∗ T ). By applying
Lemma 2 to Σ = T ∗ T and Σ′ = kT k2 Im , we have that
ℓ∗ (T (K)) = EkT ∗ (g)kK ◦ ≤ kT k · EkgkK ◦ = kT kℓ∗ (K).
This finishes the proof of the lemma.
Similar to approaches in previous works ([HT10], [NTZ13]), we exploit properties inherent to a
specific position of K to prove lower bounds on its sample complexity.
Definition 4 (ℓ-position). A convex body K ⊆ Rm is in ℓ-position if for all linear operators
m
T : ℓm
2 → ℓ2 :
ℓ∗ (K) · ℓ(K) ≤ ℓ∗ (T (K)) · ℓ(T (K)).
Clearly, K is in ℓ-position if and only if K ◦ is in ℓ-position, since ℓ∗ (K) = ℓ(K ◦ ) for any
convex body K. Note further that the product ℓ∗ (K) · ℓ(K) is scale-invariant, in the sense that
ℓ∗ (rK) · ℓ(rK) = ℓ∗ (K) · ℓ(K) for any real r. This is because, for any x, y ∈ Rm , kxkrK = 1r kxkK ,
and hrK (y) = rhK (y), so ℓ∗ (rK) = rℓ∗ (K) and ℓ(rK) = 1r ℓ(K).
We will relate the Gaussian mean width of K to another measure of its size, and the size of its
projections and sections, known as Gelfand width. A definition follows.
Definition 5 (Gelfand width). For two symmetric convex bodies K, L ⊂ Rm , the Gelfand width
of order k of K with respect to L is defined as:
ck (K, L) = inf inf{r : K ∩ E ⊆ r(L ∩ E)} = inf sup{kxkL : x ∈ K ∩ E},
E

E

where the first infimum is over subspaces E ⊆ Rm of co-dimension at most k − 1 (i.e. of dimension
at least m − k + 1). When k > m, we define ck (K, L) = 0. We denote ck (K) = ck (K, B2m ), and we
call ck (K) simply the Gelfand width of K of order k.
Note that ck (K) = inf E diam(K ∩ E), where the infimum is over subspaces E ⊆ Rm of codimension at most k − 1. Observe also that for any K and L, ck (K, L) is non-increasing in k. It is
well-known that the infimum in the definition is actually achieved [Pin85].

3.2

Composition of Differential Privacy

One of the most important properties of differential privacy is that it behaves nicely under (adaptively) composing mechanisms.
Lemma 4 (Composition). For randomized algorithms A1 and A2 satisfying (ε1 , δ1 )- and (ε2 , δ2 )differential privacy respectively, the algorithm A(D) = (A1 (D), A2 (A1 (D), D)) satisfies (ε1 +ε2 , δ1 +
δ2 )-differential privacy.
8

3.3

Known Bounds

In this section, we recall some known differentially private mechanisms, with bounds on their sample
complexity, as well as a lower bound on the optimal sample complexity. We start with the lower
bound:
Theorem 3 ([BUV14, SU15]). For all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) and α ≤ 1/10:
!
p
m log 1/δ
m
.
scε,δ (Q , α) = Ω
αε

(1)

Next we recall one of the most basic mechanisms in differential privacy, the Gaussian mechanism.
A proof of the privacy guarantee, with the constants given below, can be found in [NTZ13].
Theorem 4 (Gaussian Mechanism [DN03, DN04, DMNS06]).p
Let D = {x1 , . . . , xn } be such that
√
∀i : kxi k2 ≤ σ. If w ∼ N (0, σ(ε, δ)2 σ 2 Im ), σ(ε, δ) = (0.5 ε + 2 log (1/δ))/ε and Im ∈ Rm×m is
the identity matrix, then the algorithm AGM defined by AGM (D) = D + n1 w is (ε, δ)-differentially
private.
Corollary 2. For any symmetric convex K ⊆ B2m :
p

scε,δ (K, α) = O

m log 1/δ
αε

!

.

√ √
0.5 ε+ 2 log (1/δ)
In the rest of the paper we will use the notation σ(ε, δ) =
from the theorem
ε
statement above.
Finally, we also present the projection mechanism from [NTZ13], which post-processes the
output of the Gaussian mechanism by projecting onto K.

Theorem 5 (Projection Mechanism [NTZ13, DNT14]). Let K ⊆ B2m be a symmetric convex body,
and define AP M to be the algorithm that, on input D = {x1 , . . . , xn } ⊂ K, outputs:
ŷ = arg min{kŷ − ỹk22 : ŷ ∈ K},
where ỹ = D + n1 w, w ∼ N (0, σ(ε, δ)2 Im ). Then AP M satisfies (ε, δ)-differential privacy and has
sample complexity:


σ(ε, δ)ℓ∗ (K)
sc(K, AP M , α) = O
.
α2
Corollary 3. For any symmetric convex K ⊆ B2m :


σ(ε, δ)ℓ∗ (K)
.
scε,δ (K, α) = O
α2

4

Basic Properties of Sample Complexity

In this section, we prove some fundamental properties of sample complexity that will be extensively
used in later sections.
Lemma 5. L ⊆ K ⇒ ∀α ∈ (0, 1) : scε,δ (L, α) ≤ scε,δ (K, α).
9

Proof. Observe first that for any algorithm A and any n, err(L, A, n) ≤ err(K, A, n), because
err(K, A, n) is a supremum over a larger set than err(L, A, n). This implies that sc(K, A, α) ≤
sc(L, A, α) holds for any algorithm A, and, in particular, for the (ε, δ)-differentially private algorithm A∗ that achieves scε,δ (K, α). Then, we have:
scε,δ (L, α) ≤ sc(L, A∗ , α) ≤ sc(K, A∗ , α) = scε,δ (K, α),
as desired.
Corollary 4. For all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) and α ≤ 1/10:
!
p
m
log
1/δ
.
scε,δ (B2m , α) = Ω
αε
Proof. Since Qm ⊆ B2m , this follows directly from Lemma 5 and Lemma 3.
Lemma 6. For any α ∈ (0, 1), any linear operator T : Rm → Rm and any symmetric convex body
K ⊂ Rm :
scε,δ (K, α) ≥ scε,δ (T (K), α · kT k).
Proof. Let A be an (ε, δ)-differentially private algorithm that achieves scε,δ (K, α). Fix a function
f : T (K) → K so that for every x′ ∈ T (K), f (x′ ) ∈ T −1 (x′ ) ∩ K. We define a new algorithm A′
that takes as input D ′ = {x′1 , ..., x′n } ⊂ T (K) and outputs A′ (D ′ ) = T (A(D)), where D = f (D ′ ) =
{f (x′1 ), . . . , f (x′n )}. We claim that A′ is (ε, δ)-differentially private and that err(T (K), A′ , n) ≤
kT k · err(K, A, n) holds for every n. This claim is sufficient to prove the lemma, because it implies:
scε,δ (T (K), α · kT k) ≤ sc(T (K), A′ , α · kT k) ≤ sc(K, A, α) = scε,δ (K, α).
To show the claim, first observe that, by linearity, D ′ = T (D). We get:
EkA′ (D ′ ) − D ′ k22 = EkT (A(D)) − T (D)k22
= EkT (A(D) − D)k22

≤ kT k2 · EkA(D) − Dk22 ≤ kT k2 err(K, A, n)2 ,
where the first inequality follows by the definition of the operator norm. Since this holds for
arbitrary n and D ′ ⊂ T (K) of size n, it implies the claim on the error bound of A′ . It remains to
show that A′ is (ε, δ)-differentially private. Note that for every two neighboring databases D1′ and
D2′ of points in T (K),the corresponding databases D1 = f (D1′ ) and D2 = f (D2′ ) of points in K are
also neighboring. Then A(D) = A(f (D ′ )) is (ε, δ)-differentially private as a function of D ′ , and the
privacy of A′ follows from Lemma 4.
Corollary 5. For any t > 0:
scε,δ (tK, tα) = scε,δ (K, α).
Proof. Taking T = tIm in Lemma 6, where Im is the identity on Rm , the lemma implies scε,δ (tK, tα) ≤
scε,δ (K, α). Since this inequality holds for any t and K, we may apply it to K ′ = tK and t′ = 1/t,
and we get scε,δ (K, α) = scε,δ ((1/t)tK, (1/t)tα) ≤ scε,δ (tK, tα).
Since for any subspace E of Rm , the corresponding orthogonal projection ΠE has operator norm
1, we also immediately get the following corollary of Lemma 6:

10

Corollary 6. For any subspace E:
scε,δ (K, α) ≥ scε,δ (ΠE (K), α).
In the next theorem, we combine the lower bound in Corollary 4 and the properties we proved
above in order to give a lower bound on the sample complexity of an arbitrary symmetric convex
body K in terms of its geometric properties. In the following sections we will relate this geometric
lower bound to the mean Gaussian width of K.
Theorem 6 (Geometric Lower Bound). For all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , any convex
symmetric body K ⊆ Rm , any 1 ≤ k ≤ m and any α ≤ 1/(10ck (K ◦ )):
!
p
√
log 1/δ
m−k+1
.
·
scε,δ (K, α) = Ω
αε
ck (K ◦ )
Proof. Let us fix k and let E be the subspace that achieves ck (K ◦ ), i.e. diam(ΠE (K ◦ )) = ck (K ◦ )
and dE = dim E ≥ m − k + 1. By Corollary 1, we have ck (K ◦ )−1 ΠE (B2m ) ⊆ ΠE (K). Applying
Corollary 6, Lemma 5, and Corollary 5 in sequence, we get:
scε,δ (K, α) ≥ scε,δ (ΠE (K), α) ≥ scε,δ (ck (K ◦ )−1 ΠE (B2m ), α)
= scε,δ (Π(B2m ), αck (K ◦ )).

Notice that ΠE (B2m ) is the Euclidean unit ball in the subspace E, and, therefore:
scε,δ (Π(B2m ), αck (K ◦ )) = scε,δ (B2dE , αck (K ◦ )).
Finally, by Corollary 4, we get the following lower bound, as long as αck (K ◦ ) ≤ 1/10:
!
!
p
p
√
d
log
1/δ
log
1/δ
m
−
k
+
1
E
=Ω
.
·
scε,δ (B2dE , αck (K ◦ )) = Ω
αck (K ◦ )ε
αε
ck (K ◦ )
Combining the inequalities completes the proof.

5

Optimality of the Gaussian Mechanism

In this section, we present the result that the Gaussian mechanism is optimal, up to constant
factors, when K ⊆ B2m is sufficiently large. More specifically, if the Gaussian mean width of K
is asymptotically maximal, then we can get a tight lower bound on the sample complexity of the
Gaussian mechanism. This is summarized in the theorem below.
Theorem 7. For all ε < O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , sufficiently small constant α, and any
symmetric convex body K ⊆ B2m , if
√
ℓ∗ (K) = Ω( m),
then:
scε,δ (K, α) = Θ

p

!
m log 1/δ
,
αε

and scε,δ (K, α) is achieved, up to constants, by the Gaussian mechanism.

11

By Corollary 2 we have an upper bound for the Gaussian mechanism defined previously. To
prove its optimality, we use a classical result from convex geometry, known as Dvoretzky’s criterion,
to show a matching lower bound for the sample complexity. This result relates the existence of
a nearly-spherical section of a given convex body to the Gaussian mean norm. It was a key
ingredient in Milman’s probabilistic proof of Dvoretzky’s theorem: see Matoušek’s book [Mat02]
for an exposition.
Theorem 8 ([Mil71]; Dvoretzky’s Criterion). For every symmetric convex body K ⊆ Rm such
that B2m ⊆ K, and every β < 1, there exists a constant c(β) and a subspace E with dimension
dim E ≥ c(β)ℓ(K)2 for which:
ℓ∗ (K)
ℓ(K)
(1 − β) √ B2m ∩ E ⊆ K ∩ E ⊆ (1 + β) √ B2m ∩ E.
m
m
Proof of Theorem 7. Given the matching upper bound on sample complexity in Corollary 2, it
suffices to show the equivalent lower bound, namely that:
!
p
m log 1/δ
scε,δ (K, α) = Ω
.
αε
To this end, we will show that there exists a k ≤ (1 − c)m + 1, for an absolute constant c, so that
ck (K ◦ ) = O(1). Then the lower bound will follow directly from Theorem 6.
We will prove the claim above by applying Dvoretzky’s criterion to K ◦ . By Fact 1, K ⊆ B2m ⇒
B2m ⊆ K ◦ . We can then apply Dvoretzky’s criterion with β = 1/2, ensuring that there exists a
subspace E of dimension dim E ≥ c(1/2)ℓ(K ◦ )2 for which:
K◦ ∩ E ⊆

ℓ(K ◦ ) m
√ B ∩ E.
2 m 2

Let us define k = m − dim E + 1; then k ≤ m − c(1/2)ℓ(K ◦ )2 + 1 = m − c(1/2)ℓ∗ (K)2 + 1. Since,
by assumption ℓ(K ∗ ) = Ω(m), there exists a constant c so that k ≤ (1 − c)m + 1. Finally, by the
◦
√ ) = O(1), as desired. This completes the proof.
definition of Gelfand width, ck (K ◦ ) ≤ ℓ(K
2 m

6

Gaussian Width Lower Bounds in ℓ-position

In Section 5 we showed that the Gaussian Mechanism is optimal when the Gaussian mean width of
K is asymptotically as large possible. Our goal in this and the following section is to show general
lower bounds on sample complexity in terms of ℓ∗ (K). This is motivated by the sample complexity
upper bound in terms of ℓ∗ (K) provided by the projection mechanism.
It is natural to follow the strategy from Section 5: use Dvoretzky’s criterion to find a nearlyspherical projection of K of appropriate radius and dimension. An inspection
of the proof of 7 shows

ℓ∗√
(K)2
(ignoring the dependence on
that the sample complexity lower bound we get this way is Ω
m
ε, δ, and α here, and in the rest of this informal discussion). Recall that we are aiming for a lower
∗
bound of of Ω(ℓ∗ (K)), so we are off by a factor of ℓ√(K)
. Roughly speaking, the problem is that
m
Dvoretzky’s criterion does too much: it guarantees a spherical section of K ◦ , while we only need a
bound on the diameter of the section. In order to circumvent this difficulty, we use a different result
from asymptotic convex geometry, the low M ∗ -estimate, which bounds the diameter of a random
section of K ◦ , without also producing a large ball contained inside the section. A technical difficulty
is that the resulting upper bound on the diameter is in terms of the Gaussian mean K-norm, rather
12

than the (reciprocal of the) mean width. When K is in ℓ-position, this is not an issue, because
results of Pisier, Figiel, and Tomczak-Jaegermann show that in that case ℓ(K)ℓ∗ (K) = O(log m).
In this section we assume that K is in ℓ-position, and we remove this requirement in the subsequent
section.
The main result of this section is summarized below.
Theorem 9. For all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , all symmetric convex bodies K ⊆ Rm in
∗
, where C is an absolute constant:
ℓ-position, and for α ≤ C √ℓm(K)
log 2m
scε,δ (K, α) = Ω

p

!
log 1/δ ℓ∗ (K)
.
·
αε
log 2m

The following two theorems are the main technical ingredients we need in the proof of Theorem 9.
Theorem 10 ([FTJ79], [Pis80]; M M ∗ Bound). There exists a constant C such that for every
symmetric convex body K ⊂ Rm in ℓ-position:
ℓ(K) · ℓ∗ (K) ≤ C · m log 2m.

√
It is an open problem whether this bound can be improved to m log 2m. This would be tight
for the cube Qm . This improvement would lead to a corresponding improvement in our bounds.
Theorem 11 ([PTJ86]; Low M ∗ estimate). There exists a constant C such that for every symmetric
convex body K ⊂ Rm there exists a subspace E ⊆ Rm with dim E = m − k for which:
ℓ∗ (K)
diam (K ∩ E) ≤ C · √ .
k
Combining Theorems 10 and 11, we get the following key lemma.
Lemma 7. There exists a constant C such that for every symmetric convex body K ⊂ Rm in ℓposition, and every β ∈ (0, 1 − 1/m), there exists a subspace E of dimension at least βm satisfying:
√
m log 2m
.
diam(K ∩ E) ≤ C √
1 − β · ℓ(K)
Proof. Let k = ⌊(1 − β)m⌋ ≥ 1. Using the low M ∗ estimate on K, there exists a subspace E with
dim E = m − k = ⌈βm⌉ for which:
ℓ∗ (K)
diam (K ∩ E) ≤ C1 · √ .
k
By the M M ∗ upper bound, since K is in ℓ-position, we have that:
ℓ∗ (K) ≤ C2 ·

m log 2m
,
ℓ(K)

and, combining the two inequalities, we get that:
√
m log 2m
m log m
,
diam(K ∩ E) ≤ C1 C2 √
≤ C√
1 − β · ℓ(K)
k · ℓ(K)
for an appropriate constant C. This completes the proof.

13

The proof of the desired lower bound now follows easily from this lemma.
Proof of Theorem 9. By Theorem 6, it suffices to show that
√
 ∗

ℓ (K)
m−k+1
m
max
=Ω
.
k=1
ck (K ◦ )
log 2m

(2)

Indeed,
if k∗ is the value of k for which the maximum on the left hand side is achieved, then
√
∗
m−k +1
◦
∗
c ∗ (K ◦ ) is a lower bound on the sample complexity for all α ≤ 1/(10ck (K )), and by (2):
k

1
=Ω
10ck∗ (K ◦ )



ℓ∗ (K)
√
m − k + 1 · log 2m



=Ω



ℓ∗ (K)
√
m · log 2m



.

In the rest of the proof, we establish (2).
Since K (and thus also K ◦ ) are in ℓ-position by assumption, from Lemma 7 applied to K ◦ we
have that there exists a subspace E such that dim E ≥ m/2 and:

√

√
m log 2m
m log 2m
=
O
.
diam(K ◦ ∩ E) = O
ℓ(K ◦ )
ℓ∗ (K)
Setting kE = m − dim E + 1 ≤ m/2 + 1, and because ckE (K ◦ ) ≤ diam(K ◦ ∩ E) by definition, we
get that:
√
√
 ∗

m−k+1
dim E
ℓ (K)
m
max
≥
=Ω
,
k=1
ck (K ◦ )
diam(K ◦ ∩ E)
log 2m
as desired.

7

Gaussian Width Lower Bounds for Arbitrary Bodies

In this section, we remove the assumption that K is in ℓ-position from the previous section. Instead,
we use a recursive charging argument in order to reduce to the ℓ-position case. The resulting
guarantee is worse than the one we proved for bodies in ℓ-position by a logarithmic factor.
The main lower bound result of this section is the following theorem.
Theorem 12. For all ε = O(1), 2−Ω(n) ≤ δ ≤ 1/n1+Ω(1) , any symmetric convex body K ⊂ Rm ,
ℓ∗ (K)
, where C is an absolute constant:
and any α ≤ C √m(log
2m)2
scε,δ (K, α) = Ω



σ(ε, δ)ℓ∗ (K)
(log 2m)2 α



.

The lower bound follows from the geometric lemma below, which is interesting in its own right.
Lemma 8. There exists a constant C such that, for any symmetric convex body K ⊂ Rm ,
!
m
X
1
∗
√
ℓ (K) ≤ C(log 2m)
.
i · cm−i+1 (K ◦ )
i=1

14

(3)

Lemma 8 is closely related to the volume number theorem of Milman and Pisier [MP87], which
1
states that the inequality (3) holds with cm−i+1
(K ◦ ) replaced by the volume number vi (K), defined
as:
vol(ΠE (K))1/i
,
vi (K) = sup
m 1/i
E:dim E=i (vol(ΠE (B2 ))
where the supremum is over subspaces E of Rm . Inequality (3) is stronger than the volume
1
1
number theorem, because cm−i+1
(K ◦ ) ≤ vi (K). Indeed, setting r = cm−i+1 (K ◦ ) , by Corollary 1 and
the definition of Gelfand width we have that there exists a subspace E of dimension i such that
rΠE (B2m ) ⊆ ΠE K. Therefore, vol(ΠE (K)) ≥ r i vol(ΠE (B2m )), which implies the desired inequality.
Even though the volume number theorem is weaker than (3), the proof given by Pisier in his
book [Pis89], with minor modifications, appears to yield the stronger inequality we need. Rather
than repeat this argument, we give a self-contained and slightly different proof below. Our proof
only uses the low M ∗ estimate, the M M ∗ estimate, and elementary linear algebra, while Pisier’s
∗
proof uses
√ Milman’s quotient of subspace theorem. Moreover, if the M M estimate can be improved
would imply a corresponding improvement of the logarithmic factor
to O(m log 2m), our argument
√
in (3) from log 2m to log 2m. This does not appear to be the case in Pisier’s proof, where
the logarithmic factor comes from the (tight) upper estimate of the K-convexity constant of mdimensional Banach spaces.
To prove Lemma 8 we will first establish an auxiliary lemma.
Lemma 9. There exists a constant C such that, for any symmetric convex body K ⊂ Rm and
m ≥ 4, there exists a subspace E ⊆ Rm such that dim E ≥ ⌊m/4⌋ and:
√
m
∗
.
ℓ (ΠE (K)) ≤ C(log 2m)
c2⌊m/4⌋+1 (K ◦ )
Proof. Let T be a linear operator such that T (K) is in ℓ-position. By the rotational invariance of
Gaussians, ℓ∗ (U T (K)) = ℓ∗ (T (K)) and ℓ(U T (K)) = ℓ(T (K)) for any orthogonal transformation
U ; so, we may assume that T is self-adjoint and positive definite.
Let λ1 ≥ . . . ≥ λm > 0 be the eigenvalues of T . Let us set k = ⌊m/4⌋ and define E to be the
subspace spanned by the eigenvectors of T corresponding to λ1 , . . . , λk . Observe that ΠE and T
commute because they are simultaneously diagonalized by the eigenvectors of T .
Using Lemma 3, we calculate:
ℓ∗ (ΠE (K)) = ℓ∗ (ΠE T −1 T (K)) ≤ kΠE T −1 kℓ∗ (T (K)).
By the definition of E, the singular values of ΠE T −1 are λ−1
≥ . . . ≥ λ−1
1 , and therefore the
k
operator norm of ΠE T −1 is kΠE T −1 k = λ−1
.
Thus
we
have:
k
ℓ∗ (ΠE (K)) ≤

ℓ∗ (T (K))
.
λk

Since T (K), and thus T (K)◦ , is in ℓ-position, we can apply Lemma 7 to T (K)◦ and β =
and get that there exists a subspace F of dimension at least m − k so that:
√
m
ℓ∗ (T (K)) ≤ C1 (log 2m)
,
diam(T (K)◦ ∩ F )
where C1 is an absolute constant.

15

(4)
m−k
m

≥

1
4

Let G = E ⊥ be the orthogonal complement of the subspace E, i.e. the space spanned by the
eigenvectors of T corresponding to the eigenvalues λk+1 , . . . , λm . The restriction T |G : G → Rm of
T to G has eigenvalues λk+1 ≥ . . . ≥ λm . Therefore kT |G k ≤ λk+1 ≤ λk . Because G is spanned by
eigenvectors of T , it is invariant under action by T , i.e. T (G) = G, and, equivalently, T −1 (G) = G.
Therefore T −1 (K ◦ ) ∩ G = T −1 (K ◦ ∩ G) and K ◦ ∩ G = (T |G )T −1 (K ◦ ∩ G). It follows that:
diam(K ◦ ∩ F ∩ G) = diam((T |G )T −1 (K ◦ ∩ G) ∩ F )

≤ kT |G k diam(T −1 (K ◦ ∩ G) ∩ F )

≤ λk diam(T −1 (K ◦ ) ∩ F )

= λk diam(T (K)◦ ∩ F ).

Setting H = F ∩ G and combining the inequalities, we get that:
√
√
λk m
λk m
≤
C
(log
2m)
,
ℓ∗ (T (K)) ≤ C1 (log 2m)
1
diam(K ◦ ∩ H)
c2k+1 (K ◦ )
where the final inequality follows from the definition of Gelfand width, since the co-dimension of
H is at most 2k. Sibstituting this inequality into the right hand side of (4) finishes the proof of
the lemma.
We are now ready to prove Lemma 8.
Proof of Lemma 8. Let us first establish the lemma for m ≤ 16. Notice that:
cm (K ◦ ) =

min diam(K ◦ ∩ {tθ : t ∈ R}).

θ:kθk2 =1

But diam(K ◦ ∩ {tθ : t ∈ R}) = kθk1 ◦ for any unit vector θ, by the definition of Minkowski norm.
K
Therefore, 1/cm (K ◦ ) = max{kθkK ◦ : kθk2 = 1}. It follows that, for a standard Gaussian g in Rm :
√
(Ekgk22 )1/2
4
m
Ekgk2
∗
◦
≤
=
≤
.
(5)
ℓ (K) = EkgkK ≤
cm (K ◦ )
cm (K ◦ )
cm (K ◦ )
cm (K ◦ )
This establishes the lemma for m ≤ 16.
For m > 16, we will use an induction argument. We will strengthen the induction hypothesis
to:


⌈k/2⌉
X
1
.
√
ℓ∗ (K) ≤ C(log 2k) 
(6)
◦)
i
·
c
(K
k−i+1
i=1

Assume the inequality holds for a sufficiently large absolute constant C and all symmetric convex
bodies K ⊆ Rk , in any dimension k < m. We will show that the inequality then holds in dimension
k = m as well. The inequality (5), provides the base case for the induction (k ≤ 16).
We proceed with the inductive step. By Lemma 9 there exists a subspace E of dimension at
least ⌊m/4⌋ such that:
√
m
∗
.
ℓ (ΠE (K)) ≤ C1 (log 2m)
c2⌊m/4⌋+1 (K ◦ )
Observe that, since 2⌊m/4⌋ ≤ ⌊m/2⌋, and cj (K ◦ ) is monotone non-increasing in j, we have that
c2⌊m/4⌋+1 (K ◦ ) ≥ cm−i+1 (K ◦ ) for any i ≤ ⌈m/2⌉. Moreover,
⌈m/2⌉

1 √
1
√ ≥
m,
C2
i
i=⌈3m/8⌉+1
X

16

for all m > 16 and an absolute constant C2 . These observations together imply that
∗

ℓ (ΠE (K)) ≤ C1 (log 2m)

√
m
c2⌊m/4⌋+1

(K ◦ )

≤ C1 C2 (log 2m)

⌈m/2⌉

X

i=⌈3m/8⌉+1

√

1
i · cm−i+1 (K ◦ )

.

(7)

For a standard Gaussian g ∼ N (0, Im ), using the triangle inequality and the fact that Im =
ΠE + ΠE ⊥ , we have:
ℓ∗ (K) = E max |hx, gi|
x∈K

= E max |hΠE x, gi + ΠE ⊥ x, gi|
x∈K

≤ E max |hΠE x, gi| + E max |hΠE ⊥ x, gi|
x∈K

∗

x∈K

∗

= ℓ (ΠE K) + ℓ (ΠE ⊥ K).
Then, the inductive hypothesis follows by (7) and by the inductive hypothesis (6) applied to
ℓ∗ (ΠE ⊥ ). This finishes the proof of the lemma.
Proof of Theorem 12. As in the proof of Theorem 9, it is sufficient to prove that:
√
 ∗

ℓ (K)
m−k+1
m
=Ω
.
max
k=1
ck (K ◦ )
(log 2m)2

(8)

But this inequality follows easily from Lemma 8 and the trivial case of Hölder’s inequality:
!
!
!
√
m
m
X
X
1
1
i
m
∗
√
ℓ (K) ≤ C(log 2m)
· max
≤ C(log 2m)
◦)
i=1 cm−i+1 (K ◦ )
i
i
·
c
(K
m−i+1
i=1
i=1
!
√
i
m
= O((log 2m)2 ) · max
.
i=1 cm−i+1 (K ◦ )
Then, the proof of the theorem follows from (8) analogously to the proof of Theorem 9.
We now have everything in place to prove our main result for the mean point problem.
Proof of Theorem 2. The upper bounds on sample complexity follow from Theorem 4, Corollary 2,
Theorem 5, and Corollary 3. The lower bounds follow from Theorem 12. The statement after
“moreover” follows from Corollary 2 and Theorem 7.

8

From Mean Point to Query Release

All the bounds we proved so far were for the mean point problem. In this section we show reductions
between this problem, and the query release problem, which allow us to translate our lower bounds
to the query release setting and prove Theorem 1. We will show that the problem of approximating
Q(D) for a query workload Q under differential privacy is nearly equivalent to approximating the
mean point problem with universe K ′ = √1m K, where K is the sensitivity polytope of Q. The main
technical lemma follows.

17

Lemma 10. Let Q be a workload of m linear queries over the universe U with sensitivity polytope
K. Define K ′ = √1m K. Then, we have the inequalities:
scε,δ (Q, α) ≤ scε,δ (K ′ , α);


16 diam(K ′ )
′
scε,δ (K , α) ≤ max sc2ε,2δ (Q, α/4),
.
α2

(9)
(10)

Moreover, we can use an (ε, δ)-differentially private algorithm A′ as a black box to get an (ε, δ)differentially private algorithm A such that sc(Q, A, α) = sc(K ′ , A′ , α). A makes a single call to
A′ , and performs additional computation of worst-case complexity O(mn), where n is the size of
the database.
Proof. Note that inequality (9) is implied by the statement after “moreover”. We prove this
claim first. The algorithm A uses D to form a database D ′ of elements from K ′ which contains,
for each e ∈ D, a copy of √1m Q({e}). This transformation clearly takes time O(mn). Then A
√
simply outputs mA′ (D ′ ). Because any two neighboring databases D1 , D2 drawn from U are
transformed into neighboring databases D1′ , D2′ of points from K ′ , and A′ was assumed to be
′
(ε, δ)-differentially private, we have that A is (ε, δ)-differentially private as well. Also, since D =
√1 Q(D), err(Q, A, n) = err(K ′ , A, n) by definition, which implies that sc(Q, A, α) = sc(K ′ , A′ , α).
m
The second inequality (10) is more challenging. We will show that for any (ε, δ)-differentially
private algorithm A there exists an (2ε, 2δ)-differentially private algorithm A′ such that:
err(K ′ , A′ , n) ≤ 2 err(Q, A, n) +

2 diam(K ′ )
√
.
n

A simple calculation then shows that this implies the desired inequality. In constructing A′ we
will run A on a database formed by sampling from the vertices of K ′ (which correspond to universe elements) so that the true query answers are preserved in expectation. The analysis uses
symmetrization.
Let A′ be given the input D ′ = {x1 , . . . , xn }, which is a multiset of points from K ′ . A′ will
randomly construct two databases D+ and D− (i.e. multisets of elements from U ), and output
√1 (A(D+ ) − A(D− )).
m
Next we describe how D+ and D− are sampled. Observe that, for each i, xi is a convex
combination of vertices of K ′ . Therefore, by Caratheodory’s
theorem, there exist universe elements
1 Pk i
√
ei,1 , . . . , ei,ki ∈ U , where ki ≤ m + 1, such that xi = m j=1 αi,j Q(ei,j ) for some αi,1 , . . . , αi,ki ∈
P i
[−1, 1] satisfying kj=1
|αi | = 1. We would like to fix a unique way to pick the ei,j and αi,j for each
xi , and indeed for any point in K ′ . To this end, fix an arbitrary order on U , and for each xi choose
a minimal sequence ei,1 , . . . , ei,ki that satisfies the conditions above and which comes earliest in the
lexicographic order induced by the order on U . Once we have chosen the ei,j and αi,j , we construct
D+ and D− using the following sampling procedure: for each i ∈ [n], we independently sample ji
from [ki ], s.t. P[ji = j] = |αi,j |; we add ei,ji to D+ if αi,ji ≥ 0, and to D− otherwise. Then, as
mentioned above, A′ outputs √1m (A(D+ ) − A(D− )).
First, we show that A′ is (2ε, 2δ)-differentially private. Let D1′ = {x1 , . . . , xn } and D2′ =
{x1 , . . . , xn , xn+1 } be two neighboring databases and let {ei,j } and {αi,j } be defined as above,
(1)
(1)
where 1 ≤ i ≤ n + 1 and for each i, 1 ≤ j ≤ ki . Let D+ , D− be the random databases sampled by
(2)

(2)

A′ on input D1′ , and let D+ , D− be the random databases sampled on input D2′ . Let us couple
(1)
(2)
(2)
(1)
D+ and D+ so that they have symmetric difference at most 1 and D+ is a superset of D+ . We
18

(1)

can achieve this by sampling ji ∈ [ki ] as described above for 1 ≤ i ≤ n and adding ei,ji to both D+
(2)
and D+ if αi,ji ≥ 0 (or to neither otherwise) and sampling jn+1 ∈ [kn+1 ] and adding en+1,jn+1 to
(2)
(1)
(2)
D+ if αn+1,jn+1 ≥ 0. Because, with this coupling, D+ and D+ are always neighboring, by the
(ε, δ)-differential privacy guarantee for A we have that, for any measurable S in the range of A:
(2)

(1)

P[A(D+ ) ∈ S] ≤ eε P[A(D+ ) ∈ S] + δ,
(2)

(1)

P[A(D+ ) ∈ S] ≥ e−ε P[A(D+ ) ∈ S] − δ,
(2)

(1)

where the probabilities are taken over the random choices of D+ and D+ , and over the randomness
(2)

(1)

of A. An analogous argument holds for D− and D− . Therefore, each of the two calls of A made
by A′ , composed with the sampling procedure that produces the input to A, is (ε, δ)-differentially
private with respect to the input to A′ . The privacy claim follows by composition (Lemma 4).
Finally we analyze the error of A′ . By Minkowski’s inequality, we have:


2 1/2
2 1/2
1
1
′
(EkA′ (D ′ ) − D k22 )1/2 ≤ E A(D+ ) − √ Q(D+ )
+ E A(D− ) − √ Q(D− )
2
2
m
m


1/2
2
1
′
+ E √ (Q(D+ ) − Q(D− )) − D
m
2


1
′ 2 1/2
.
≤ 2 err(Q, A, n) + E √ (Q(D+ ) − Q(D− )) − D
m
2

We proceed to bound the second term on the right hand side. Observe that, by the way we sample
′
D+ and D− , linearity of expectation, and the linearity of Q(·), D = E √1m (Q(D+ ) − Q(D− )).

Let, for each i ∈ [n], ji ∈ [ki ] be sampled as above, and let yi = √1m sign(αi,j )Q(ei,ji ). Then
Pn
′
1 Pn
√1 (Q(D+ ) − Q(D− )) = 1
i=1 yi , so E n
i=1 yi = D . The vectors y1 , . . . , yn are independent
n
m
and all belong to K ′ ⊆ R · B2m , where R = diam(K ′ ). Let ξ1 , . . . , ξn be Rademacher random
variables, independent from everything else; by Lemma 1 and the parallelogram identity:
1
′
E √ (Q(D+ ) − Q(D− )) − D
m

2
2

n

n

1X
1X
=E
yi − E
yi
n
n
≤

4
E
n2

i=1
n
X
i=1

i=1

ξi y i

2
2

=

4
n2

2
2

n
X
i=1

kyi k22 ≤

4R2
.
n

With this, we have established the desired bound on err(K ′ , A′ , n), and, therefore, the lemma.
We will also use a simple lemma that relates the sample complexity at an error level α to the
sample complexity at a lower error level α′ < α. The proof is a padding argument and can be found
in [SU15].
Lemma 11. For any workload Q, any 0 < α′ < α < 1, and any privacy parameters ε, δ, we have
 α 
· scε,δ (Q, α),
scε,δ (Q, α′ ) = Ω
Cα′
for an absolute constant C.

We are now ready to finish the proof of our main result for query release.

19

Proof of Theorem 1. The upper bounds on sample complexity follow from the upper bounds in
Theorem 2 together with Lemma 10.
ℓ∗ (K)
ℓ∗ (K ′ )
= Cm(log
be the smallest error parameter
Denote K ′ = √1m K, and let α0 = C √m(log
2m)2
2m)2
for which Theorem 12 holds. Then, by Theorem 12 and Lemma 10:




σ(ε, δ)ℓ∗ (K)
diam(K)
√
√
=
Ω
max scε,δ (Q, α0 ),
.
m(log 2m)2 α0
mα20
√
It is easy to show that scε,δ (Q, α0 ) = Ω(diam(K)/(α0 m)) for all sufficiently small ε and δ.
Therefore, we have:


σ(ε, δ)ℓ∗ (K)
.
scε,δ (Q, α0 ) = Ω √
m(log 2m)2
By Lemma 11, we get that for any α ≤ α0 the sample complexity is at least:




σ(ε, δ)ℓ∗ (K)α0
σ(ε, δ)ℓ∗ (K)2
scε,δ (Q, α) = Ω √
.
=
Ω
m(log 2m)2 α
m3/2 (log 2m)4 α
An analogous proof, with α0 = 1/C set to the smallest error parameter for which Theorem 7
holds, establishes the statement after “moreover”.

References
[AAGM15] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman. Asymptotic geometric analysis. Part I, volume 202 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2015.
[BDKT12] Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Unconditional differentially private mechanisms for linear queries. In Proceedings of the
44th symposium on Theory of Computing, STOC ’12, pages 1269–1284, New York, NY,
USA, 2012. ACM.
[BUV14]

Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of
approximate differential privacy. In Proceedings of the 46th Annual ACM Symposium
on Theory of Computing, pages 1–10. ACM, 2014.

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise
to sensitivity in private data analysis. In Theory of Cryptography Conference, pages
265–284. Springer, 2006.
[DN03]

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In
Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles
of Database Systems, pages 202–210. ACM, 2003.

[DN04]

Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In Annual International Cryptology Conference, pages 528–544.
Springer, 2004.

[DNT14]

Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Using convex relaxations for
efficiently and privately releasing marginals. In 30th Annual Symposium on Computational Geometry, SOCG’14, Kyoto, Japan, June 08 - 11, 2014, page 261. ACM, 2014.
20

[FTJ79]

T. Figiel and Nicole Tomczak-Jaegermann. Projections onto Hilbertian subspaces of
Banach spaces. Israel J. Math., 33(2):155–171, 1979.

[HT10]

Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings
of the 42nd ACM Symposium on Theory of Computing, STOC ’10, pages 705–714, New
York, NY, USA, 2010. ACM.

[Kea98]

Michael Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM,
45(6):983–1006, 1998.

[Mat02]

Jiřı́ Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[Mil71]

V. D. Milman. A new proof of A. Dvoretzky’s theorem on cross-sections of convex
bodies. Funkcional. Anal. i Priložen., 5(4):28–37, 1971.

[MP87]

V. D. Milman and G. Pisier. Gaussian processes and mixed volumes. Ann. Probab.,
15(1):292–304, 1987.

[Nik15]

Aleksandar Nikolov. An improved private mechanism for small databases. In Automata,
Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto,
Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer
Science, pages 1010–1021. Springer, 2015.

[NTZ13]

Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy:
the sparse and approximate cases. In Symposium on Theory of Computing Conference,
STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 351–360. ACM, 2013.

[Pin85]

Allan Pinkus. n-widths in approximation theory, volume 7 of Ergebnisse der Mathematik
und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. SpringerVerlag, Berlin, 1985.

[Pis80]

G. Pisier. Sur les espaces de Banach K-convexes. In Seminar on Functional Analysis,
1979–1980 (French), pages Exp. No. 11, 15. École Polytech., Palaiseau, 1980.

[Pis89]

Gilles Pisier. The volume of convex bodies and Banach space geometry, volume 94 of
Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.

[PTJ86]

Alain Pajor and Nicole Tomczak-Jaegermann. Subspaces of small codimension of finitedimensional Banach spaces. Proc. Amer. Math. Soc., 97(4):637–642, 1986.

[SU15]

Thomas Steinke and Jonathan Ullman. Between pure and approximate differential
privacy. CoRR, abs/1501.06095, 2015.

[Ver09]

R. Vershynin.
Lectures in geometric functional analysis.
personal.umich.edu/ romanv/papers/GFA-book/GFA-book.pdf, 2009.

21

http://www-

