INSPECTRE: Privately Estimating the Unseen

arXiv:1803.00008v1 [] 28 Feb 2018

Jayadev Acharya∗
ECE, Cornell University
acharya@cornell.edu

Gautam Kamath†
EECS & CSAIL, MIT
g@csail.mit.edu

Ziteng Sun‡
ECE, Cornell University
zs335@cornell.edu

Huanyu Zhang§
ECE, Cornell University
hz388@cornell.edu
March 2, 2018

Abstract
We develop differentially private methods for estimating various distributional properties. Given a
sample from a discrete distribution p, some functional f , and accuracy and privacy parameters α and ε,
the goal is to estimate f (p) up to accuracy α, while maintaining ε-differential privacy of the sample.
We prove almost-tight bounds on the sample size required for this problem for several functionals
of interest, including support size, support coverage, and entropy. We show that the cost of privacy
is negligible in a variety of settings, both theoretically and experimentally. Our methods are based on
a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear
sample complexities.

1

Introduction

How can we infer a distribution given a sample from it? If data is in abundance, the solution may be simple
– the empirical distribution will approximate the true distribution. However, challenges arise when data
is scarce in comparison to the size of the domain, and especially when we wish to quantify “rare events.”
This is frequently the case: for example, it has recently been observed that there are several very rare
genetic mutations which occur in humans, and we wish to know how many such mutations exist [KC12,
TBO+ 12, NWE+ 12]. Many of these mutations have only been seen once, and we can infer that there are
many which have not been seen at all. Over the last decade, a large body of work has focused on developing
theoretically sound and effective tools for such settings [OSW16] and references therein, including the problem
of estimating the frequency distribution of rare genetic variations [ZVV+ 16].
However, in many settings where one wishes to perform statistical inference, data may contain sensitive
information about individuals. For example, in medical studies, where the data may contain individuals’
health records and whether they carry some disease which bears a social stigma. Alternatively, one can
consider a map application which suggests routes based on aggregate positions of individuals, which contains
delicate information including users’ residence data. In these settings, it is critical that our methods protect
sensitive information contained in the dataset. This does not preclude our overall goals of statistical analysis,
as we are trying to infer properties of the population p, and not the samples which are drawn from said
population.
That said, without careful experimental design, published statistical findings may be prone to leaking
sensitive information about the sample. As a notable example, it was recently shown that one can determine the identity of some individuals who participated in genome-wide association studies [HSR+ 08]. This
∗ Supported

by NSF CCF-1657471 and a Cornell University startup grant.
by ONR N00014-12-1-0999, NSF CCF-1617730, CCF-1650733, and CCF-1741137. Work partially done while
author was an intern at Microsoft Research, New England.
‡ Supported by NSF CCF-1657471 and a Cornell University startup grant.
§ Supported by NSF CCF-1657471 and a Cornell University startup grant.
† Supported

1

realization has motivated a surge of interest in developing data sharing techniques with an explicit focus on
maintaining privacy of the data [JS13, USF13, YFSU14, SSB16].
Privacy-preserving computation has enjoyed significant study in a number of fields, including statistics and almost every branch of computer science, including cryptography, machine learning, algorithms,
and database theory – see, e.g., [Dal77, AW89, AA01, DN03, Dwo08, DR14] and references therein. Perhaps the most celebrated notion of privacy, proposed by theoretical computer scientists, is differential privacy [DMNS06]. Informally, an algorithm is differentially private if its outputs on neighboring datasets
(differing in a single element) are statistically close (for a more precise definition, see Section 2). Differential
privacy has become the standard for theoretically-sound data privacy, leading to its adoption by several large
technology companies, including Google and Apple [EPK14, Dif17].
Our focus in this paper is to develop tools for privately performing several distribution property estimation
tasks. In particular, we study the tradeoff between statistical accuracy, privacy, and error rate in the sample
size. Our model is that we are given sample access to some unknown discrete distribution p, over a domain
of size k, which is possibly unknown in some tasks. We wish to estimate the following properties:
• Support Coverage: If we take m samples from the distribution, what is the expected number of
unique elements we expect to see?
• Support Size: How many elements of the support have non-zero probability?
• Entropy: What is the Shannon entropy of the distribution?
For more formal statements of these problems, see Section 2.1. We require that our output is α-accurate,
satisfies (ε, 0)-differential privacy, and is correct with probability 1 − β. The goal is to give an algorithm
with minimal sample complexity n, while simultaneously being computationally efficient.
Theoretical Results. Our main results show that privacy can be achieved for all these problems at a
very low cost. For example, if one wishes to privately estimate entropy, this incurs an additional additive
cost in the sample complexity which is very close to linear in 1/αε. We draw attention to two features of
this bound. First, this is independent of k. All the problems we consider have complexity Θ(k/ log k), so
in the primary regime of study where k  1/αε, this small additive cost is dwarfed by the inherent sample
complexity of the non-private problem. Second, the bound is almost linear in 1/αε. We note that performing
even the most basic statistical task privately, estimating the bias of a coin, incurs this linear dependence.
Surprisingly, we show that much more sophisticated inference tasks can be privatized at almost no cost.
In particular, these properties imply that the additive cost of privacy is o(1) in the most studied regime
where the support size is large. In general, this is not true – for many other problems, including distribution
estimation and hypothesis testing, the additional cost of privacy depends significantly on the support size or
dimension [DHS15, CDK17, ASZ17, ADR17]. We also provide lower bounds, showing that our upper bounds
are almost tight. A more formal statement of our results appears in Section 3.
Experimental Results. We demonstrate the efficacy of our method with experimental evaluations. As
a baseline, we compare with the non-private algorithms of [OSW16] and [WY18]. Overall, we find that our
algorithms’ performance is nearly identical, showing that, in many cases, privacy comes (essentially) for free.
We begin with an evaluation on synthetic data. Then, inspired by [VV13, OSW16], we analyze text corpus
consisting of words from Hamlet, in order to estimate the number of unique words which occur. Finally, we
investigate name frequencies in the US census data. This setting has been previously considered by [OSW16],
but we emphasize that this is an application where private statistical analysis is critical. This is proven by
efforts of the US Census Bureau to incorporate differential privacy into the 2020 US census [DLS+ 17].
Techniques. Our approach works by choosing statistics for these tasks which possess bounded sensitivity,
which is well-known to imply privacy under the Laplace or Gaussian mechanism. We note that bounded
sensitivity of statistics is not always something that can be taken for granted. Indeed, for many fundamental
tasks, optimal algorithms for the non-private setting may be highly sensitive, thus necessitating crucial
modifications to obtain differential privacy [ADK15, CDK17]. Thus, careful choice and design of statistics
must be a priority when performing inference with privacy considerations.
To this end, we leverage recent results of [ADOS17], which studies estimators for non-private versions of
the problems we consider. The main technical work in their paper exploits bounded sensitivity to show sharp
cutoff-style concentration bounds for certain estimators, which operate using the principle of best-polynomial
approximation. They use these results to show that a single algorithm, the Profile Maximum Likelihood
(PML), can estimate all these properties simultaneously. On the other hand, we consider the sensitivity
of these estimators for purposes of privacy – the same property is utilized by both works for very different

2

purposes, a connection which may be of independent interest.
We note that bounded sensitivity of a statistic may be exploited for purposes other than privacy. For
instance, by McDiarmid’s inequality, any such statistic also enjoys very sharp concentration of measure,
implying that one can boost the success probability of the test at an additive cost which is logarithmic in
the inverse of the failure probability. One may naturally conjecture that, if a statistical task is based on a
primitive which concentrates in this sense, then it may also be privatized at a low cost. However, this is not
true – estimating a discrete distribution in `1 distance is such a task, but the cost of privatization depends
significantly on the support size [DHS15].
One can observe that, algorithmically, our method is quite simple: compute the non-private statistic, and
add a relatively small amount of Laplace noise. The non-private statistics have recently been demonstrated
to be practical [OSW16, WY18], and the additional cost of the Laplace mechanism is minimal. This is
in contrast to several differentially private algorithms which invoke significant overhead in the quest for
privacy. Our algorithms attain almost-optimal rates (which are optimal up to constant factors for most
parameter regimes of interest), while simultaneously operating effectively in practice, as demonstrated in
our experimental results.
Related Work. Over the last decade, there have been a flurry of works on the problems we study
in this paper by the computer science and information theory communities, including Shannon and Rényi
entropy estimation [Pan03, VV17, JVHW17, AOST17, OS17, WY18], support coverage and support size estimation [OSW16, WY18]. A recent paper studies the general problem of estimating functionals of discrete
distribution from samples in terms of the smoothness of the functional [FS17]. These have culminated in a
nearly-complete understanding of the sample complexity of these properties, with optimal sample complexities (up to constant factors) for most parameter regimes.
Recently, there has been significant interest in performing statistical tasks under differential privacy
constraints. Perhaps most relevant to this work are [CDK17, ASZ17, ADR17], which study the sample
complexity of differentialy privately performing classical distribution testing problems, including identity and
closeness testing. Other works investigating private hypothesis testing include [WLK15, GLRV16, KR17,
KSF17, Rog17, GR17], which focus less on characterizing the finite-sample guarantees of such tests, and
more on understanding their asymptotic properties and applications to computing p-values. There has
also been study on private distribution learning [DHS15, DJW17, KV18], in which we wish to estimate
parameters of the distribution, rather than just a particular property of interest. A number of other problems
have been studied with privacy requirements, including clustering [WWS15, BDL+ 17], principal component
analysis [CSS13, KT13, HP14], ordinary least squares [She17], and much more.

2

Preliminaries

We will start with some definitions.
Pk
def
Let ∆ = {(p(1), . . . , p(k)) : p(i) ≥ 0, i=1 p(i) = 1, 1 ≤ k ≤ ∞} be the set of discrete distributions over
a countable support. Let ∆k be the set of distributions in ∆ with at most k non-zero probability values.
A property f (p) is a mapping from ∆ → R. We now describe the classical distribution property estimation
problem, and then state the problem under differential privacy.
Property Estimation Problem. Given α, β, f , and independent samples X1n from an unknown distribution p, design an estimator fˆ : X1n → R such that with probability at least 1 − β, fˆ(X1n ) − f (p) < α.


def
The sample complexity of fˆ, is Cfˆ(f, α, β) = min{n : Pr fˆ(X1n ) − f (p) > α < β} is the smallest number
of samples to estimate f to accuracy α, and error β. We study the problem for β = 1/3, and by the median trick, we can boost the error probability to β with an additional multiplicative log(1/β) more samples:
def

Cfˆ(f, α) = Cfˆ(f, α, 1/3). The sample complexity of estimating a property f (p) is the minimum sample
complexity over all estimators: C(f, α) = minfˆ Cfˆ(f, α).
An estimator fˆ is ε-differentially private (DP) [DMNS06] if for any X1n and Y1n , with dham (X1n , Y1n ) ≤ 1,
Pr (f (X1n )∈S)
≤ eε , for all i, and measurable S.
Pr (f (Y1n )∈S )

3

Private Property Estimation. Given α, ε, β, f , and independent samples X1n from an unknown distribution p, design an ε-differentially private estimator fˆ : X1n → R such that with probability at least 1 − β,
fˆ(X1n ) − f (p) < α. Similar to the non-private setting, the sample complexity of ε-differentially private
estimation problem is C(f, α, ε) = minfˆ:fˆis ε-DP Cfˆ(f, α, 1/3), the smallest number of samples n for which
there exists such a ±α estimator with error probability at most 1/3.
In their original paper [DMNS06] provides a scheme for differential privacy, known as the Laplace mechanism. This method adds Laplace noise to a non-private scheme in order to make it private. We first define
the sensitivity of an estimator, and then state their result in our setting.
def
Definition 1. The sensitivity of an estimator fˆ : [k]n → R is ∆n,fˆ = maxdham (X1n ,Y1n )≤1 fˆ(X1n ) − fˆ(Y1n ) .

Let Dfˆ(α, ε) = min{n : ∆n,fˆ ≤ αε}.
Lemma 1.


n
 α o
,ε
.
C(f, α, ε) = O min Cfˆ(f, α/2) + Dfˆ
4
fˆ

Proof. [DMNS06] showed that for a function with sensitivity ∆n,fˆ, adding Laplace noise X ∼ Lap(∆n,fˆ/ε)
makes the output ε-differentially private. By the definition of Dfˆ( α4 , ε), the Laplace noise we add has
|x|

1 − b
, hence we have
e
parameter at most α4 . Recall that the probability density function of Lap(b) is 2b
1
α
Pr (|X| > α/2) < e2 . By the union bound, we get an additive error less than α = 2 + α2 with probability at
most 1/3 + e12 < 0.5. Hence, with the median trick, we can boost the error probability to 1/3, at the cost of
a constant factor in the number of samples.

To prove sample complexity lower bounds for differentially private estimators, we observe that the estimator can be used to test between two distributions with distinct property values, hence is a harder problem.
For lower bounds on differentially private testing, [ASZ17] gives the following argument based on coupling:
Lemma 2. Suppose there is a coupling between distributions p and q over X n , such that E [dham (X1n , Y1n )] ≤
D. Then, any ε-differentially private
algorithm that distinguishes between p and q with error probability at

most 1/3 must satisfy D = Ω 1ε .

2.1

Problems of Interest

Support Size. The support size of a distribution p is S(p) = |{x : p(x) > 0}|, the number of symbols with
non-zero probability values. However, notice that estimating S(p) from samples can be hard due to the
presence of symbols with negligible, yet non-zero probabilities. To circumvent this issue, [RRSS09] proposed
def

to study the problem when the smallest probability is bounded. Let ∆≥ k1 = {p ∈ ∆ : p(x) ∈ {0} ∪ [1/k, 1]}
be the set of all distributions where all non-zero probabilities have value at least 1/k. For p ∈ ∆≥ k1 , our goal
is to estimate S(p) up to ±αk with the least number of samples from p.
P
Support Coverage. For a distribution p, and an integer m, let Sm (p) = x (1 − (1 − p(x))m ), be the
expected number of symbols that appear when we obtain m independent samples from the distribution p.
The objective is to find the least number of samples n in order to estimate Sm (p) to an additive ±αm.
Support coverage arises in many ecological and biological studies [CCG+ 12] to quantify the number of
new elements (gene mutations, species, words, etc) that can be expected to be seen in the future. Good and
Toulmin [GT56] proposed an estimator that for any constant α, requires m/2 samples to estimate Sm (p).
P
1
Entropy. The Shannon entropy of a distribution p is H(p) = x p(x) log p(x)
, H(p) is a central object
in information theory [CT06], and also arises in many fields such as machine learning [Now12], neuroscience [BWM97, NBdRvS04], and others. Estimating H(p) is hard with any finite number of samples due
to the possibility of infinite support. To circumvent this, a natural approach is to consider distributions in
∆k . The goal is to estimate the entropy of a distribution in ∆k to an additive ±α, where ∆k is all discrete
distributions over at most k symbols.
4

3

Statement of Results

Our theoretical results for estimating support coverage, support size, and entropy are given below. Algorithms for these problems and proofs of these statements are provided in Section 4. Our experimental results
are described and discussed in Section 5.
Theorem 1. For any ε = Ω(1/m), the sample complexity of support coverage is


m log(1/α) m log(1/α)
C(Sm , α, ε) = O
+
.
log m
log(εm)
Furthermore,


m log(1/α)
1
C(Sm , α, ε) = Ω
+
.
log m
αε
Theorem 2. For any ε = Ω(1/k), the sample complexity of support size estimation is

C(S, α, ε) = O


k log2 (1/α) k log2 (1/α)
+
.
log k
log(εk)

Furthermore,


k log2 (1/α)
1
C(S, α, ε) = Ω
+
.
log k
αε
Theorem 3. Let λ > 0 be any small fixed constant. For instance, λ can be chosen to be any constant
between 0.01 and 1. We have the following upper bounds on the sample complexity of entropy estimation:
 

log2 (min{k, n})
1
1
k
+
+
log
C(H, α, ε) = O
α
α2
αε
αε
and
k
log2 (min{k, n})
C(H, α, ε) = O
+
+
λ2 α log k
α2



1
αε

1+λ !
.

Furthermore,

C(H, α, ε) = Ω


k
log2 (min{k, n}) log k
+
+
.
α log k
α2
αε

We provide some discussion of our results. At a high level, we wish to emphasize the following two points:
1. Our upper bounds show that the cost of privacy in these settings is often negligible compared to the
sample complexity of the non-private statistical task, especially when we are dealing with distributions
over a large support. Furthermore, our upper bounds are almost tight in all parameters.
2. The algorithmic complexity introduced by the requirement of privacy is minimal, consisting only of
a single step which noises the output of an estimator. In other words, our methods are realizable in
practice, and we demonstrate the effectiveness on several synthetic and real-data examples.
First, we examine our results on support size and support coverage estimation. We note that we focus
on the regime where ε is not exceptionally small, as the privacy requirement becomes somewhat unusual.
For instance, non-privately, if we have m samples for the problem of support coverage, then the empirical
plug-in estimator is the best we can do. However, if ε = O(1/m), then group privacy [DR14] implies that
the algorithm’s output distribution on any dataset of m samples must be very similar – however, these
samples may have an arbitrary value of support coverage ∈ [m], which precludes hopes for a highly accurate
estimator. To avoid degeneracies of this nature, we restrict our attention to ε = Ω(1/m). In this regime, if
ε = Ω(mγ /m) for any constant γ > 0, then up to constant factors, our upper bound is within a constant
factor of the optimal sample complexity without privacy constratints. In other words, for most meaningful
values of ε, privacy comes for free.

5

Next, we turn our attention to entropy estimation. We note that the second upper bound in Theorem 3
has a parameter λ that indicates a tradeoff between the sample complexity incurred in the first and third
term. This parameter determines the degree of a polynomial to be used for entropy estimation. As the degree
becomes smaller (corresponding to a large λ), accuracy of the polynomial estimator decreases, however, at
the same time, low-degree polynomials have a small sensitivity, allowing us to privatize the outcome.
In terms of our theoretical results, one can think of λ = 0.01. With this parameter setting, it can be
observed that our upper bounds are almost tight. For example, one can see that the upper and lower bounds
match to either logarithmic factors (when looking at the first upper bound), or a very small polynomial
factor in 1/αε (when looking at the second upper bound). For our experimental results, we experimentally
determined an effective value for the parameter λ on a single synthetic instance. We then show that this choice
of parameter generalizes, giving highly-accurate private estimation in other instances, on both synthetic on
real-world data.

4

Algorithms and Analysis

In this section, we prove our results for support coverage in Section 4.1, support size in Section 4.2, and
entropy in Section 4.3. In each section, we first describe and analyze our algorithms for the relevant problem.
We then go on to describe and analyze a lower bound construction, showing that our upper bounds are almost
tight.
All our algorithms fall into the following simple framework:
1. Compute a non-private estimate of the property;
2. Privatize this estimate by adding Laplace noise, where the parameter is determined through analysis
of the estimator and potentially computation of the estimator’s sensitivity.

4.1

Support Coverage Estimation

In this section, we prove Theorem 1, about support coverage estimation:
Theorem 1. For any ε = Ω(1/m), the sample complexity of support coverage is


m log(1/α) m log(1/α)
+
.
C(Sm , α, ε) = O
log m
log(εm)
Furthermore,


1
m log(1/α)
+
.
C(Sm , α, ε) = Ω
log m
αε
Our upper bound is described and analyzed in Section 4.1.1, while our lower bound appears in Section 4.1.2.
4.1.1

Upper Bound for Support Coverage Estimation

Let ϕi be the number of symbols that appear i times in X1n . We will use the following non-private support
coverage estimator from [OSW16]:
Ŝm (X1n ) =

n
X


ϕi 1 + (−t)i · Pr (Z ≥ i) ,

i=1

where Z is a Poisson random variable with mean r (which is a parameter to be instantiated later), and
t = (m − n)/n.
Our private estimator of support coverage is derived by adding Laplace noise to this non-private estimator
with the appropriate noise parameter, and thus the performance of our private estimator, is analyzed by
bounding the sensitivity and the bias of this non-private estimator according to Lemma 1.
The sensitivity and bias of this estimator is bounded in the following lemmas.
Lemma 3. Suppose m > 2n, then the maximum coefficient of ϕi in Ŝm (p) is at most 1 + er(t−1) .
6

Proof. By the definition of Z, we know Pr (Z ≥ i) =

P∞

k=i

k

e−r rk! , hence we have:

|1 + (−t)i · Pr (Z ≥ i)| ≤ 1 + ti
≤1+e

∞
X

e−r

k=i
∞
X
−r
k=i

≤ 1 + e−r
=1+e

rk
k!

(rt)k
k!

∞
X
(rt)k

k=0
r(t−1)

k!

The bias of the estimator is bounded in Lemma 4 of [ADOS17]:
Lemma 4. Suppose m > 2n, then
h
i
E Ŝm (X1n ) − Sm (p) ≤ 2 + 2er(t−1) + min(m, S(p)) · e−r .
Using these results, letting r = log(1/α), [OSW16] showed that there is a constant C, such that with
n = C logmm log(1/α) samples, with probability at least 0.9,
Ŝm (X1n ) Sm (p)
−
≤ α.
m
m
Ŝ (X n )

Our upper bound in Theorem 1 is derived by the following analysis of the sensitivity of m m 1 .
If we change one sample in X1n , at most two of the ϕj ’s change. Hence by Lemma 3, the sensitivity of
the estimator satisfies
!

2 
Ŝm (X1n )
≤ · 1 + er(t−1) .
(1)
∆
m
m
By Lemma 1, there is a private algorithm for support coverage estimation as long as
!
Ŝm (X1n )
≤ αε,
∆
m
which by (1) holds if
2(1 + exp(r(t − 1))) ≤ αεm.
Let r = log(3/α), note that t − 1 =

m
n

− 2. Suppose αεm > 2, then, the condition above reduces to
  



1
3
m
·
− 2 ≤ log
αεm − 1 .
log
α
n
2

This is equivalent to
m log(3/α)
log( 21 αεm − 1) + 2 log(3/α)
m log(3/α)
=
log( 23 εm − 3/α) + log(3/α)

n≥

Suppose αεm > 2, then the condition above reduces to the requirement that


m log(1/α)
n=O
.
log(εm)
7

(2)

4.1.2

Lower Bound for Support Coverage Estimation

We now prove the lower bound described in Theorem 1. Note that the first term in the lower bound is the
sample complexity of non-private support coverage estimation, shown in [OSW16]. Therefore, we turn our
attention to prove the latter term in the sample complexity.
Consider the following two distributions. u1 is uniform over [m(1 + α)]. u2 is distributed over m + 1
α
1
∀i ∈ [m] and u2 [4] = 1+α
. Moreover, 4 ∈
/ [m(1 + α)]. Then,
elements [m] ∪ {4} where u2 [i] = m(1+α)


m 
1
Sm (u1 ) = m(1 + α) · 1 − 1 −
,
m(1 + α)
and
Sm (u2 ) =


m· 1− 1−

1
m(1 + α)

m 



+ 1− 1−

α
1+α

m 

hence,
Sm (u2 ) − Sm (u1 )


= mα · 1 − 1 −

1
m(1 + α)

m 



− 1− 1−

α
1+α

m 

= Ω(αm)
α
Hence we know there support coverage differs by Ω(αm). Moreover, their total variation distance is 1+α
.
The following lemma is folklore, based on the coupling interpretation of total variation distance, and the
fact that total variation distance is subadditive for product measures.

Lemma 5. For any two distributions p, and q, there is a coupling between n iid samples from the two
distributions with an expected Hamming distance of dTV (p, q) · n.
Using Lemma 5 and dTV (u1 , u2 ) =

α
1+α ,

we have

Lemma 6. Suppose u1 and u2 are as defined before, there is a coupling between un1 and un2 with expected
α
Hamming distance equal to 1+α
n.
Moreover, given n samples, we must be able to privately distinguish between u1 and u2 given an α
accurate estimator of support coverage with privacy considerations. Thus, according to Lemma 2 and 6, we
have:
 
α
1
1
n≥ ⇒n=Ω
.
1+α
ε
εα

4.2

Support Size Estimation

In this section, we prove our main theorem about support size estimation, Theorem 2:
Theorem 2. For any ε = Ω(1/k), the sample complexity of support size estimation is

C(S, α, ε) = O


k log2 (1/α) k log2 (1/α)
+
.
log k
log(εk)

Furthermore,


1
k log2 (1/α)
+
.
C(S, α, ε) = Ω
log k
αε
Our upper bound is described and analyzed in Section 4.2.1, while our lower bound appears in Section 4.2.2.

8

4.2.1

Upper Bound for Support Size Estimation

In [OSW16], it is shown that the support coverage estimator can be used to obtain optimal results for
estimating the support size of a distribution. In this fashion, taking m = k log(3/α), we we may use an
estimate of the support coverage Sm (p) as an estimator of S(p). In particular, their result is based on the
following observation.
Lemma 7. Suppose m ≥ k log(3/α), then for any p ∈ ∆≥ k1 ,
|Sm (p) − S(p)| ≤

αk
.
3

Proof. From the definition of Sm (p), we have Sm (p) ≤ S(p). For the other side,
X
X
m
S(p) − Sm (p) =
(1 − p(x)) ≤
e−mp(x)
x

x

≤ k · e− log(3/α)

=

kα
.
3

Therefore, estimating Sm (p) for m = k log(3/α), up to ±αk/3, also estimates S(p) up to ±αk. Therefore,
the goal is to estimate the smallest value of n to solve the support coverage problem.
Suppose r = log(3/α), and m = k log(3/α) = k · r in the support coverage problem. Then, we have
t=

k log(3/α)
m
−1=
− 1.
n
n

(3)

Then, by Lemma 4 in the previous section, we have
h
i
E Ŝm (X1n ) − S(p)
h
i
≤ E Ŝm (X1n ) − Sm (p) + |Sm (p) − S(p)|
≤ 2 + 2er(t−1) + min{m, k} · e−r +
≤ 2 + 2er(t−1) + k · e− log(3/α) +
≤ 2 + 2er(t−1) + 2

kα
3

kα
3

kα
.
3

We will find conditions on n such that the middle
 term above is at most kα. Toward this end, note that
2er(t−1) ≤ αk holds if and only if r(t − 1) ≤ log αk
2 . Plugging in (3), this holds when


 
k log(3/α)
αk
log(3/α) ·
− 2 ≤ log
,
n
2
which is equivalent to

n≥

k log2 (3/α)
log αk
2 + 2 log


3
α

=O

k log2 (1/α)
log k



where we have assumed without loss of generality that α > k1 .
The computations for sensitivity are very similar. From Lemma 1 1, we need to find the value of n such
that
2 + 2er(t−1) ≤ αεk,
where we assume that n ≤ 12 k log(3/α), else we just add noise to the true number of observed distinct
elements By computations similar to the expectation case, this reduces to
n≥

k log2 (3/α)
.
3
log αεk
2 + log α
9

Therefore, this gives us a sample complexity of
k log2 (1/α)
n=O
log (εk)



(4)

for the sensitivity result to hold.
We note that the bound above blows up when ε ≤ k1 . However, we note that our lower bound implies
that we need at least Ω(1/ε) = Ω(k) samples in this case, which is not in the sub-linear regime that we are
interested in. We therefore consider only the regime where the privacy parameter ε is at least 1/k.
4.2.2

Lower Bound for Support Size Estimation

In this section, we prove a lower bound for support size estimation, as described in Theorem 2. The techniques
are similar to those for support coverage in Section 4.1.2. The first term of the complexity is the lower bound
for non-private setting. This follows by combining the lower bound of [OSW16] for support coverage, with
the equivalence between estimation of support size and coverage as implied by Lemma 7. We focus on the
second term in the sequel.
Consider the following two distributions: u1 is a uniform distribution over [k] and u2 is a uniform
distribution over [(1−α)k]. Then the support size of these two distribution differs by αk, and dTV (u1 , u2 ) = α.
Hence by Lemma 5, we know the following:
Lemma 8. Suppose u1 ∼ U [k] and u2 ∼ U [(1 − α)k], there is a coupling between un1 and un2 with expected
Hamming distance equal to αn.
Moreover, given n samples, we must be able to privately distinguish between u1 and u2 given an α
accurate estimator of entropy with privacy considerations. Thus, according to Lemma 2 and Lemma 8, we
have:
 
1
1
.
αn ≥ ⇒ n = Ω
ε
εα

4.3

Entropy Estimation

In this section, we prove our main theorem about entropy estimation, Theorem 3:
Theorem 3. Let λ > 0 be any small fixed constant. For instance, λ can be chosen to be any constant
between 0.01 and 1. We have the following upper bounds on the sample complexity of entropy estimation:
 

log2 (min{k, n})
1
1
k
+
+
log
C(H, α, ε) = O
α
α2
αε
αε
and
k
log2 (min{k, n})
C(H, α, ε) = O
+
+
λ2 α log k
α2



1
αε

1+λ !
.

Furthermore,

C(H, α, ε) = Ω


k
log2 (min{k, n}) log k
+
+
.
α log k
α2
αε

We describe and analyze two upper bounds. The first is based on the empirical entropy estimator, and is described and analyzed in Section 4.3.1. The second is based on the method of best-polynomial approximation,
and appears in Section 4.3.2. Finally, our lower bound is in Section 4.3.3.
4.3.1

Upper Bound for Entropy Estimation: The Empirical Estimator

Our first private entropy estimator is derived by adding Laplace noise into the empirical estimator. The
parameter of the Laplace distribution is ∆(H(ε p̂n )) , where ∆(H(p̂n )) denotes the sensitivity of the empirical
estimator. By analyzing its sensitivity and bias, we prove an upper bound on the sample complexity for
private entropy estimation and get the first upper bound in Theorem 3.
10

Let p̂n be the empirical distribution, and let H(p̂n ) be the entropy of the empirical distribution. The
theorem is based on the following three facts:


log n
∆(H(p̂n )) = O
.
(5)
n
 
k
|H(p) − E [H(p̂n )]| = O
,
(6)
n
 2

log (min{k, n})
V ar (H(p̂n )) = O
,
(7)
n
With these three facts in hand, the sample complexity of the empiricalestimator can be bounded as follows.
1
1
log( αε
)
. We also need |H(p) − E [H(p̂n )]| =
By Lemma 1, we need ∆(H(p̂n )) ≤ αε, which gives 
n = O αε

2
log (min{k,n})
k
2
O(α) and V ar (H(p̂n )) = O α , which gives n = O n +
.
α2
Proof of (5). The largest change in any Nx when we change one symbol is one. Moreover, at most two
Nx change. Therefore,
n
j
n
j+1
log
− log
n
j+1 n
j
j
j
1
n
= 2 · max
log
+ log
j=1...n−1 n
j+1 n
j+1


j
1
n
j
log
,
log
≤ 2 · max max
j=1...n−1
n
j+1
n
j+1


1 log n
≤ 2 · max
,
,
n n
log n
.
=2·
n

∆(H(p̂n )) ≤ 2 ·

Proof of (6).

max

j=1...n−1

(8)
(9)

(10)

By the concavity of entropy function, we know that
E [H(p̂n )] ≤ H(p).

Therefore,
E [|H(p) − H(p̂n )|] = H(p) − E [H(p̂n )]
"
#
X
=E
(p̂n (x) log p̂n (x) − p(x) log p(x))
x

"
=E

X
x

#
"
#
X
p̂n (x)
p̂n (x) log
+E
(p̂n (x) − p(x)) log p(x)
p(x)
x

= E [D(p̂n kp)]


≤ E dχ2 (p̂n || p)
"
#
X (p̂n (x) − p(x))2
=E
p(x)
x
X (p(x)/n)
≤
p(x)
x
=

(11)
(12)

(13)

k
.
n

(14)

11

2

Proof of (7). The variance bound of logn k is given precisely in Lemma 15 of [JVHW17]. To obtain the
other half of the bound of, we apply the bounded differences inequality in the form stated in Corollary 3.2
of [BLM13].
Lemma 9. Let f : Ωn → R be a function. Suppose further that
max

0

0
z1 ,...,zn ,zi

f (z1 , . . . , zn ) − f (z1 , . . . , zi−1 , zi , . . . , zn ) ≤ ci .

Then for independent variables Z1 , . . . , Zn ,
n

Var(f (Z1 , . . . , Zn )) ≤

1X 2
c .
4 i=1 i

Therefore, using Lemma 9 and Equation (5)

V ar (H(p̂n )) ≤ n ·
4.3.2

4 log2 n
n2


=

4 log2 n
.
n

Upper Bound for Entropy Estimation: Best-Polynomial Approximation

We prove an upper bound on the sample complexity for private entropy estimation if one adds Laplace noise
into best-polynomial estimator.This will give us the second upper bound in Theorem 3.
In the non-private setting the optimal sample complexity of estimating H(p) over ∆k is given by Theorem
1 of [WY16]


k
log2 (min{k, n})
Θ
+
.
α log k
α2
However, this estimator can have a large sensitivity. [ADOS17] designed an estimator that has the same
sample complexity but a smaller sensitivity. We restate Lemma 6 of [ADOS17] here:
Lemma 10. Let λ > 0 be a fixed small constant, which may be taken to be any value between 0.01 and 1.
Then there is an entropy estimator with sample complexity


1
k
log2 (min{k, n})
+
Θ 2·
,
λ α log k
α2
and has sensitivity nλ /n.
We can now invoke Lemma 1 on the estimator in this lemma to obtain the upper bound on private
entropy estimation.
4.3.3

Lower Bound for Entropy Estimation

We now prove the lower bound for entropy estimation. Note that any lower bound on privately testing two
distributions p, and q such that H(p) − H(q) = Θ(α) is a lower bound on estimating entropy.
We analyze the following construction for Proposition 2 of [WY16]. The two distributions p, and q over
[k] are defined as:
1 − p(1)
2
,p(i) =
, for i = 2, . . . , k,
3
k−1
2−η
1 − q(1)
q(1) =
,q(i) =
, for i = 2, . . . , k.
3
k−1
p(1) =

Then, by the grouping property of entropy,
H(p) = h(2/3) +

1
1+η
· log(k − 1), and H(q) = h((2 − η)/3) +
· log(k − 1),
3
3
12

(15)
(16)

which gives
H(p) − H(q) = Ω(η log k).
For η = α/ log k, the entropy difference becomes Θ(α).
The total variation distance between p and q is η/3. By Lemma 5 in the paper, there is a coupling over
X1n , and Y1n generated from p and q with expected Hamming distance at most dTV (p, q) · n. This along with
Lemma 2 in the paper gives a lower bound of Ω(log k/αε) on the sample complexity.

5

Experiments

We evaluated our methods for entropy estimation and support coverage on both synthetic and real data.
Overall, we found that privacy is quite cheap: private estimators achieve accuracy which is comparable or
near-indistinguishable to non-private estimators in many settings. Our results on entropy estimation and
support coverage appear in Sections 5.1 and 5.2, respectively. Code of our implementation is available at
https://github.com/HuanyuZhang/INSPECTRE.

5.1

Entropy

We compare the performance of our entropy estimator with a number of alternatives, both private and
non-private. Non-private algorithms considered include the plug-in estimator (plug-in), the Miller-Madow
Estimator (MM) [Mil55], the sample optimal polynomial approximation estimator (poly) of [WY16]. We analyze the privatized versions of plug-in, and poly in Sections 4.3.1 and 4.3.2, respectively. The implementation
of the latter is based on code from the authors of [WY16]1 . We compare performance on different distributions including uniform, a distribution with two steps, Zipf(1/2), a distribution with Dirichlet-1 prior, and
a distribution with Dirichlet-1/2 prior, and over varying support sizes.
While plug-in, and MM are parameter free, poly (and its private counterpart) have to choose the degree L
of the polynomial to use, which manifests in the parameter λ in the statement of Theorem 3. [WY16] suggest
the value of L = 1.6 log k in their experiments. However, since we add further noise, we choose a single L as
follows: (i) Run privatized poly for different L values and distributions for k = 2000, ε = 1, (b) Choose the
value of L that performs well across different distributions (See Figure 1). We choose L = 1.2·log k from this,
and use it for all other experiments. To evaluate the sensitivity of poly, we computed the estimator’s value at
all possible input values, computed the sensitivity, (namely, ∆ = maxdham (X1n ,Y1n )≤1 |poly(X1n )−poly(Y1n )|),

and added noise distributed as Lap 0, ∆
ε .

0.6
0.4

0.8
0.6

500

750

1000

1250

1500

Number of samples

1750

2000

0.0

1.0
0.8

500

750

1000

1250

1500

Number of samples

1750

2000

0.0

1.50
1.25
1.00
0.75

L=0.3log(k)
L=0.6log(k)
L=0.9log(k)
L=1.2log(k)
L=1.5log(k)
L=1.8log(k)

2.0
1.5
1.0
0.5

0.25

0.2
250

L=0.3log(k)
L=0.6log(k)
L=0.9log(k)
L=1.2log(k)
L=1.5log(k)
L=1.8log(k)

1.75

0.50

0.4

0.2
250

1.2

0.6

0.4

0.2
0.0

1.0

1.4

Dirichlet-1/2 prior

Dirichlet-1 prior

L=0.3log(k)
L=0.6log(k)
L=0.9log(k)
L=1.2log(k)
L=1.5log(k)
L=1.8log(k)

1.6

RMSE

0.8

1.2

RMSE

RMSE

1.0

Zipf 1/2
L=0.3log(k)
L=0.6log(k)
L=0.9log(k)
L=1.2log(k)
L=1.5log(k)
L=1.8log(k)

1.4

RMSE

Two steps
L=0.3log(k)
L=0.6log(k)
L=0.9log(k)
L=1.2log(k)
L=1.5log(k)
L=1.8log(k)

RMSE

Uniform
1.2

250

500

750

1000

1250

1500

Number of samples

1750

2000

0.00

250

500

750

1000

1250

1500

Number of samples

1750

2000

0.0

250

500

750

1000

1250

1500

Number of samples

1750

2000

Figure 1: RMSE comparison for private Polynomial Approximation Estimator with various values for degree
L, k = 2000, ε = 1.
The RMSE of various estimators for k = 1000, and ε = 1 for various distributions are illustrated in
Figure 2. The RMSE is averaged over 100 iterations in the plots.
We observe that the performance of our private-poly is near-indistinguishable from the non-private
poly, particularly as the number of samples increases. It also performs significantly better than all other
alternatives, including the non-private Miller-Madow and the plug-in estimator. The cost of privacy is
minimal for several other settings of k and ε, for which results appear in Section A.
1 See

https://github.com/Albuso0/entropy for their code for entropy estimation.

13

2.5

1.5

2.5

2.0
1.5

2.0

2.0
1.5

1.0

1.0

0.5

0.5

0.5

0.5

400

600

800

0.0

1000

Number of samples

200

400

600

800

0.0

1000

Number of samples

200

400

600

800

Number of samples

2.0
1.5
1.0
0.5

0.0

1000

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5

1.5

1.0

200

Dirichlet-1/2 prior
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5

1.0

0.0

Dirichlet-1 prior

3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

2.0

RMSE

RMSE

2.5

Zipf 1/2
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

Two steps
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

Uniform

3.5

200

400

600

800

0.0

1000

Number of samples

200

400

600

800

1000

Number of samples

Figure 2: Comparison of various estimators for the entropy, k = 1000, ε = 1.

5.2

Support Coverage

We investigate the cost of privacy for the problem of support coverage. We provide a comparison between the
Smoothed Good-Toulmin estimator (SGT) of [OSW16] and our algorithm, which is a privatized version of
their statistic (see Section 4.1.1). Our implementation is based on code provided by the authors of [OSW16].
As shown in our theoretical results, the sensitivity of SGT is at most 2(1 + er (t − 1)), necessitating the
addition of Laplace noise with parameter 2(1 + er(t−1) )/ε. Note that while the theory suggests we select the
2
1
loge n(t+1)
parameter r = log(1/α), α is unknown. We instead set r = 2t
t−1 , as previously done in [OSW16].
5.2.1

Evaluation on Synthetic Data

In our synthetic experiments, we consider different distributions over different support sizes k. We generate
n = k/2 samples, and then estimate the support coverage at m = n · t. For large t, estimation is harder.
Some results of our evaluation on synthetic are displayed in Figure 3. We compare the performance of SGT,
and privatized versions of SGT with parameters ε = 1, 2, and 10. For this instance, we fixed the domain size
k = 20000. We ran the methods described above with n = k/2 samples, and estimated the support coverage
at m = nt, for t ranging from 1 to 10. The performance of the estimators is measured in terms of RMSE
over 1000 iterations.

1500

Uniform

1000

Non-private
Private eps=10
Private eps=2
Private eps=1

800

Two steps

1200

Non-private
Private eps=10
Private eps=2
Private eps=1

1000

Zipf 1/2

1400

Non-private
Private eps=10
Private eps=2
Private eps=1

1200
1000

800

400

RMSE

RMSE

RMSE

RMSE

600
1000

600
400

500

0
1

200

2

3

4

5

t

6

7

8

9

10

0
1

3

4

5

t

6

7

8

9

10

0
1

1800
1600
1400

600

3

4

5

t

6

7

8

9

10

0
1

1000
800
600
400

200
2

Dirichlet-1/2 prior
Non-private
Private eps=10
Private eps=2
Private eps=1

1200

800

400

200
2

Dirichlet-1 prior
Non-private
Private eps=10
Private eps=2
Private eps=1

RMSE

2000

200
2

3

4

5

t

6

7

8

9

10

0
1

2

3

4

5

t

6

7

8

9

10

Figure 3: Comparison between the private estimator with the non-private SGT when k = 20000
We observe that, in this setting, the cost of privacy is relatively small for reasonable values of ε. This
is as predicted by our theoretical results, where unless ε is extremely small (less than 1/k) the non-private
sample complexity dominates the privacy requirement. However, we found that for smaller support sizes
(as shown in Section A.2), the cost of privacy can be significant. We provide an intuitive explanation for
why no private estimator can perform well on such instances. To minimize the number of parameters, we
instead argue about the related problem of support-size estimation. Suppose we are trying to distinguish
between distributions which are uniform over supports of size 100 and 200. We note that, if we draw n = 50
samples, the “profile” of the samples (i.e., the histogram of the histogram) will be very similar for the two
distributions. In particular, if one modifies only a few samples (say, five or six), one could convert one
profile into the other. In other words, these two profiles are almost-neighboring datasets, but simultaneously
correspond to very different support sizes. This pits the two goals of privacy and accuracy at odds with each
other, thus resulting in a degradation in accuracy.
5.2.2

Evaluation on Census Data and Hamlet

We conclude with experiments for support coverage on two real-world datasets, the 2000 US Census data and
the text of Shakespeare’s play Hamlet, inspired by investigations in [OSW16] and [VV17]. Our investigation
14

on US Census data is also inspired by the fact that this is a setting where privacy is of practical importance,
evidenced by the proposed adoption of differential privacy in the 2020 US Census [DLS+ 17].
The Census dataset contains a list of last names that appear at least 100 times. Since the dataset is so
oversampled, even a small fraction of the data is likely to contain almost all the names. As such, we make
the task non-trivial by subsampling mtotal = 86080 individuals from the data, obtaining 20412 distinct last
names. We then sample n of the mtotal individuals without replacement and attempt to estimate the total
number of last names. Figure 4 displays the RMSE over 100 iterations of this process. We observe that even
an exceptionally stringent privacy budget of ε = 0.5, the performance is almost indistinguishable from the
non-private SGT estimator.
6000

Non-private
Private eps=2
Private eps=1
Private eps=0.5

5000

RMSE

4000
3000
2000
1000
0
0.1

0.2

0.3

0.4

0.5

0.6

Fraction of seen names

0.7

0.8

0.9

1.0

Figure 4: Comparison between our private estimator with the SGT on Census Data
The Hamlet dataset has mtotal = 31, 999 words, of which 4804 are distinct. Since the distribution is
not as oversampled as the Census data, we do not need to subsample the data. Besides this difference, the
experimental setup is identical to that of the Census dataset. Once again, as we can see in Figure 5, we
get near-indistinguishable performance between the non-private and private estimators, even for very small
values of ε. Our experimental results demonstrate that privacy is realizable in practice, with particularly
accurate performance on real-world datasets.
1800

Non-private
Private eps=2
Private eps=1
Private eps=0.5

1600
1400

RMSE

1200
1000
800
600
400
200
0
0.1

0.2

0.3

0.4

0.5

0.6

Fraction of seen words

0.7

0.8

0.9

1.0

Figure 5: Comparison between our private estimator with the SGT on Hamlet

References
[AA01]

Dakshi Agrawal and Charu C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Proceedings of the 20th ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database Systems, PODS ’01, pages 247–255, New York, NY,
USA, 2001. ACM.

15

[ADK15]

Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems 28, NIPS ’15,
pages 3577–3598. Curran Associates, Inc., 2015.

[ADOS17]

Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. A unified
maximum likelihood approach for estimating symmetric properties of discrete distributions.
In Proceedings of the 34th International Conference on Machine Learning, ICML ’17, pages
11–21. JMLR, Inc., 2017.

[ADR17]

Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity
and closeness testing of discrete distributions. arXiv preprint arXiv:1707.05497, 2017.

[AOST17]

Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Estimating
rényi entropy of discrete distributions. IEEE Transactions on Information Theory, 63(1):38–56,
2017.

[ASZ17]

Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and
closeness of discrete distributions. arXiv preprint arXiv:1707.05128, 2017.

[AW89]

Nabil R. Adam and John C. Worthmann. Security-control methods for statistical databases:
A comparative study. ACM Computing Surveys (CSUR), 21(4):515–556, 1989.

[BDL+ 17]

Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differentially private clustering in high-dimensional euclidean spaces. In Proceedings of the 34th
International Conference on Machine Learning, ICML ’17, pages 322–331. JMLR, Inc., 2017.

[BLM13]

Stephane Boucheron, Gabor Lugosi, and Pierre Massart. Concentration Inequalities: A
Nonasymptotic Theory of Independence. Oxford University Press, 2013.

[BWM97]

Michael J. Berry, David K Warland, and Markus Meister. The structure and precision of retinal
spike trains. Proceedings of the National Academy of Sciences, 94(10):5411–5416, 1997.

[CCG+ 12]

Robert K. Colwell, Anne Chao, Nicholas J. Gotelli, Shang-Yi Lin, Chang Xuan Mao, Robin L.
Chazdon, and John T. Longino. Models and estimators linking individual-based and samplebased rarefaction, extrapolation and comparison of assemblages. Journal of Plant Ecology,
5(1):3–21, 2012.

[CDK17]

Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv’it: Private and sample efficient
identity testing. In Proceedings of the 34th International Conference on Machine Learning,
ICML ’17, pages 635–644. JMLR, Inc., 2017.

[CSS13]

Kamalika Chaudhuri, Anand D. Sarwate, and Kaushik Sinha. A near-optimal algorithm
for differentially-private principal components. Journal of Machine Learning Research,
14(Sep):2905–2943, 2013.

[CT06]

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2006.

[Dal77]

Tore Dalenius. Towards a methodology for statistical disclosure control. Statistisk Tidskrift,
15:429–444, 1977.

[DHS15]

Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems 28, NIPS
’15, pages 2566–2574. Curran Associates, Inc., 2015.

[Dif17]

Differential Privacy Team, Apple. Learning with privacy at scale. https://machinelearning.
apple.com/docs/learning-with-privacy-at-scale/appledifferentialprivacysystem.
pdf, December 2017.

[DJW17]

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal procedures for
locally private estimation. Journal of the American Statistical Association, 2017.
16

[DLS+ 17]

Aref N. Dajani, Amy D. Lauger, Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin
Machanavajjhala, Simson L. Garfinkel, Scot A. Dahl, Matthew Graham, Vishesh Karwa, Hang
Kim, Philip Lelerc, Ian M. Schmutte, William N. Sexton, Lars Vilhuber, and John M. Abowd.
The modernization of statistical disclosure limitation at the U.S. census bureau, 2017. Presented
at the September 2017 meeting of the Census Scientific Advisory Committee.

[DMNS06]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography,
TCC ’06, pages 265–284, Berlin, Heidelberg, 2006. Springer.

[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,
PODS ’03, pages 202–210, New York, NY, USA, 2003. ACM.

[DR14]

Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Now
Publishers, Inc., 2014.

[Dwo08]

Cynthia Dwork. Differential privacy: A survey of results. In Proceedings of the 5th International
Conference on Theory and Applications of Models of Computation, TAMC ’08, pages 1–19,
Berlin, Heidelberg, 2008. Springer.

[EPK14]

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable
privacy-preserving ordinal response. In Proceedings of the 2014 ACM Conference on Computer
and Communications Security, CCS ’14, pages 1054–1067, New York, NY, USA, 2014. ACM.

[FS17]

Kazuto Fukuchi and Jun Sakuma. Minimax optimal estimators for additive scalar functionals
of discrete distributions. In Proceedings of the 2017 IEEE International Symposium on Information Theory, ISIT ’17, pages 2103–2107, Washington, DC, USA, 2017. IEEE Computer
Society.

[GLRV16]

Marco Gaboardi, Hyun-Woo Lim, Ryan M. Rogers, and Salil P. Vadhan. Differentially private
chi-squared hypothesis testing: Goodness of fit and independence testing. In Proceedings of
the 33rd International Conference on Machine Learning, ICML ’16, pages 1395–1403. JMLR,
Inc., 2016.

[GR17]

Marco Gaboardi and Ryan Rogers. Local private hypothesis testing: Chi-square tests. arXiv
preprint arXiv:1709.07155, 2017.

[GT56]

I.J. Good and G.H. Toulmin. The number of new species, and the increase in population
coverage, when a sample is increased. Biometrika, 43(1-2):45–63, 1956.

[HP14]

Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications.
In Advances in Neural Information Processing Systems 27, NIPS ’14, pages 2861–2869. Curran
Associates, Inc., 2014.

[HSR+ 08]

Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill
Muehling, John V. Pearson, Dietrich A. Stephan, Stanley F. Nelson, and David W. Craig.
Resolving individuals contributing trace amounts of dna to highly complex mixtures using
high-density snp genotyping microarrays. PLoS Genetics, 4(8):1–9, 2008.

[JS13]

Aaron Johnson and Vitaly Shmatikov. Privacy-preserving data exploration in genome-wide
association studies. In Proceedings of the 19th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’13, pages 1079–1087, New York, NY, USA,
2013. ACM.

[JVHW17]

Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of
functionals of discrete distributions. IEEE Transactions on Information Theory, 61(5):2835–
2885, 2017.

17

[KC12]

Alon Keinan and Andrew G. Clark. Recent explosive human population growth has resulted
in an excess of rare genetic variants. Science, 336(6082):740–743, 2012.

[KR17]

Daniel Kifer and Ryan M. Rogers. A new class of private chi-square tests. In Proceedings of
the 20th International Conference on Artificial Intelligence and Statistics, AISTATS ’17, pages
991–1000. JMLR, Inc., 2017.

[KSF17]

Kazuya Kakizaki, Jun Sakuma, and Kazuto Fukuchi. Differentially private chi-squared test
by unit circle mechanism. In Proceedings of the 34th International Conference on Machine
Learning, ICML ’17, pages 1761–1770. JMLR, Inc., 2017.

[KT13]

Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13,
pages 1395–1414, Philadelphia, PA, USA, 2013. SIAM.

[KV18]

Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In
Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS ’18,
New York, NY, USA, 2018. ACM.

[Mil55]

George A. Miller. Note on the bias of information estimates. Information Theory in Psychology:
Problems and Methods, 2:95–100, 1955.

[NBdRvS04] Ilya Nemenman, William Bialek, and Rob de Ruyter van Steveninck. Entropy and information
in neural spike trains: Progress on the sampling problem. Physical Review E, 69(5):056111:1–
056111:6, 2004.
[Now12]

Sebastian Nowozin. Improved information gain estimates for decision tree induction. In Proceedings of the 29th International Conference on Machine Learning, ICML ’12, pages 571–578.
JMLR, Inc., 2012.

[NWE+ 12]

Matthew R. Nelson, Daniel Wegmann, Margaret G. Ehm, Darren Kessner, Pamela St. Jean,
Claudio Verzilli, Judong Shen, Zhengzheng Tang, Silviu-Alin Bacanu, Dana Fraser, Liling
Warren, Jennifer Aponte, Matthew Zawistowski, Xiao Liu, Hao Zhang, Yong Zhang, Jun Li,
Yun Li, Li Li, Peter Woollard, Simon Topp, Matthew D. Hall, Keith Nangle, Jun Wang,
Gonçalo Abecasis, Lon R. Cardon, Sebastian Zöllner, John C. Whittaker, Stephanie L. Chissoe,
John Novembre, and Vincent Mooser. An abundance of rare functional variants in 202 drug
target genes sequenced in 14,002 people. Science, 337(6090):100–104, 2012.

[OS17]

Maciej Obremski and Maciej Skorski. Renyi entropy estimation revisited. In Proceedings of
the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX ’17, pages 20:1–20:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik.

[OSW16]

Alon Orlitsky, Ananda Theerta Suresh, and Yihong Wu. Optimal prediction of the number of
unseen species. Proceedings of the National Academy of Sciences, 113(47):13283–13288, 2016.

[Pan03]

Liam Paninski. Estimation of entropy and mutual information.
15(6):1191–1253, 2003.

[Rog17]

Ryan Michael Rogers. Leveraging Privacy in Data Analysis. PhD thesis, University of Pennsylvania, May 2017.

[RRSS09]

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for
approximating distribution support size and the distinct elements problem. SIAM Journal on
Computing, 39(3):813–842, 2009.

[She17]

Or Sheffet. Differentially private ordinary least squares. In Proceedings of the 34th International
Conference on Machine Learning, ICML ’17, pages 3105–3114. JMLR, Inc., 2017.

18

Neural Computation,

[SSB16]

Sean Simmons, Cenk Sahinalp, and Bonnie Berger. Enabling privacy-preserving GWASs in
heterogeneous human populations. Cell Systems, 3(1):54–61, 2016.

[TBO+ 12]

Jacob A. Tennessen, Abigail W. Bigham, Timothy D. O’Connor, Wenqing Fu, Eimear E.
Kenny, Simon Gravel, Sean McGee, Ron Do, Xiaoming Liu, Goo Jun, Hyun Min Kang, Daniel
Jordan, Suzanne M. Leal, Stacey Gabriel, Mark J. Rieder, Goncalo Abecasis, David Altshuler,
Deborah A. Nickerson, Eric Boerwinkle, Shamil Sunyaev, Carlos D. Bustamante, Michael J.
Bamshad, Joshua M. Akey, Broad GO, Seattle GO, and on behalf of the NHLBI Exome Sequencing Project. Evolution and functional impact of rare coding variation from deep sequencing of human exomes. Science, 337(6090):64–69, 2012.

[USF13]

Caroline Uhler, Aleksandra Slavković, and Stephen E. Fienberg. Privacy-preserving data sharing for genome-wide association studies. The Journal of Privacy and Confidentiality, 5(1):137–
166, 2013.

[VV13]

Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy
and other properties. In Advances in Neural Information Processing Systems 26, NIPS ’13,
pages 2157–2165. Curran Associates, Inc., 2013.

[VV17]

Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy
and other properties. Journal of the ACM, 64(6):37:1–37:41, 2017.

[WLK15]

Yue Wang, Jaewoo Lee, and Daniel Kifer. Revisiting differentially private hypothesis tests for
categorical data. arXiv preprint arXiv:1511.03376, 2015.

[WWS15]

Yining Wang, Yu-Xiang Wang, and Aarti Singh. Differentially private subspace clustering. In
Advances in Neural Information Processing Systems 28, NIPS ’15, pages 1000–1008. Curran
Associates, Inc., 2015.

[WY16]

Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via
best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702–3720,
2016.

[WY18]

Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics, 2018.

[YFSU14]

Fei Yu, Stephen E. Fienberg, Aleksandra B. Slavković, and Caroline Uhler. Scalable privacypreserving data sharing methodology for genome-wide association studies. Journal of Biomedical Informatics, 50:133–141, 2014.

[ZVV+ 16]

James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha,
Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel G. MacArthur. Quantifying unobserved
protein-coding variants in human populations provides a roadmap for large-scale sequencing
projects. Nature Communications, 7, 2016.

A

Additional Experimental Results

This section contains additional plots of our synthetic experimental results. Section A.1 contains experiments
on entropy estimation, while Section A.2 contains experiments on estimation of support coverage.

A.1

Entropy Estimation

We present four more plots of our synthetic experimental results for entropy estimation. Figures 6 and 7
are on a smaller support of k = 100, with ε = 1 and 2, respectively. Figures 8 and 9 are on a support of
k = 1000, with ε = 0.5 and 2.

19

Uniform

3.0

2.0

2.5

1.5

2.0
1.5

2.5

1.5
1.0

0.5

0.5

0.5

40

60

Number of samples

80

100

20

Zipf 1

2.0

40

60

Number of samples

80

0.0

100

2.5

RMSE

RMSE

1.5

0.5

0.5

0.5

80

100

20

40

60

Number of samples

(a)

100

1.5
1.0

60

80

80

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.0

1.0

40

60

2.5

1.0

Number of samples

40

Number of samples
Dirichlet-1/2 prior

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.0
1.5

20

20

Dirichlet-1 prior
3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5

RMSE

2.0

1.0

20

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

1.0

0.0

Zipf 1/2

3.5

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

RMSE

2.5

Two steps

3.5

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

RMSE

3.5

100

20

40

60

Number of samples

(b)

80

100

(c)

Figure 6: Comparison of various estimators for the entropy, k = 100, ε = 1.

Uniform

3.0

2.0
1.5

Zipf 1/2
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0
2.5

RMSE

RMSE

2.5

Two steps

3.5

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.0
1.5

2.5
2.0
1.5

1.0

1.0

1.0

0.5

0.5

0.5

20

40

60

Number of samples

80

0.0

100

Zipf 1
2.5

40

60

Number of samples

80

100

20

Dirichlet-1 prior

3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.0

20

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

3.5

60

80

100

Dirichlet-1/2 prior
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5

40

Number of samples

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5
2.0

1.5

1.0

1.0

0.5

0.5
20

40

60

Number of samples
(a)

80

100

RMSE

1.5

RMSE

RMSE

2.0
1.5
1.0
0.5
20

40

60

Number of samples
(b)

80

100

20

40

60

Number of samples
(c)

Figure 7: Comparison of various estimators for the entropy, k = 100, ε = 2.

20

80

100

Two steps

Uniform
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

2.0

3.0
2.5

RMSE

1.5

2.5

1.5

2.0
1.5

1.0

1.0

0.5

0.5

0.5

0.0

0.0

1.0

200

400

600

800

Number of samples

1000

Zipf 1
1.75
1.50

1.00

400

600

800

Number of samples

0.0

1000

200

Dirichlet-1 prior

400

600

800

Number of samples

1000

Dirichlet-1/2 prior
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5
2.0

2.0

RMSE

1.25

200

3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.00

RMSE

2.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

RMSE

RMSE

2.5

Zipf 1/2
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

RMSE

3.5

1.5

0.75

1.0

0.50

0.5

1.5
1.0
0.5

0.25
200

400

600

800

Number of samples

0.0

1000

200

400

600

800

Number of samples

(a)

0.0

1000

200

400

600

800

Number of samples

(b)

1000

(c)

Figure 8: Comparison of various estimators for the entropy, k = 1000, ε = 0.5.

Two steps

Uniform
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

2.0

3.0
2.5

RMSE

1.5

2.5

1.5

2.0
1.5

1.0

1.0

0.5

0.5

0.5

0.0

0.0

1.0

200

400

600

800

Number of samples

1000

Zipf 1

2.00

1.50

1.00
0.75

400

600

800

Number of samples

200

400

600

800

Number of samples

1000

Dirichlet-1/2 prior
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.0
1.5
1.0

0.50

0.0

1000

Dirichlet-1 prior

2.5

RMSE

1.25

200

3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

1.75

RMSE

2.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

3.0

Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

2.5
2.0

RMSE

RMSE

2.5

Zipf 1/2
Plug-in
Miller
Poly
Poly-Laplace
Plug-in-Laplace

RMSE

3.5

1.5
1.0
0.5

0.5

0.25
0.00

200

400

600

800

Number of samples
(a)

1000

0.0

200

400

600

800

Number of samples
(b)

1000

0.0

200

400

600

(c)

Figure 9: Comparison of various estimators for the entropy, k = 1000, ε = 2.

21

800

Number of samples

1000

200

150

100

50

0
1
300
250

Two steps

200

Non-private
Private eps=10
Private eps=2
Private eps=1

150

RMSE

RMSE

150

Uniform
Non-private
Private eps=10
Private eps=2
Private eps=1

RMSE

200

100

50

2

3

4

5

6

t
Zipf 1

7

8

9

0
1

10

200

Non-private
Private eps=10
Private eps=2
Private eps=1

150

Zipf 1/2
Non-private
Private eps=10
Private eps=2
Private eps=1

100

50

2

3

4

5

6

t
Dirichlet-1 prior

7

8

9

0
1

10

200

Non-private
Private eps=10
Private eps=2
Private eps=1

150

2

3

4

5

6

7

8

9

10

6

7

8

9

10

t
Dirichlet-1/2 prior

Non-private
Private eps=10
Private eps=2
Private eps=1

150

RMSE

RMSE

RMSE

200
100

100

100
50

50

50
0
1

2

3

4

5

t

6

7

8

9

(a)

10

0
1

2

3

4

5

t

(b)

6

7

8

9

10

0
1

2

3

4

5

t

(c)

Figure 10: Comparison between the private estimator with the non-private SGT when k = 1000.

A.2

Support Coverage

We present three additional plots of our synthetic experimental results for support coverage estimation. In
particular, Figures 10, 11, and 12 show support coverage for k = 1000, 5000, 100000.

22

450

Non-private
Private eps=10
Private eps=2
Private eps=1

500

400
350

RMSE

RMSE

400
300
200
100

Two steps

450

Non-private
Private eps=10
Private eps=2
Private eps=1

400
350

300

300

250

250

RMSE

Uniform

600

200

0
1
1000
800

2

3

4

5

6

t
Zipf 1

7

8

9

150

100

100

0
1

10

600

Non-private
Private eps=10
Private eps=2
Private eps=1

500

50
2

3

4

5

6

t
Dirichlet-1 prior

7

8

9

0
1

10

600

Non-private
Private eps=10
Private eps=2
Private eps=1

500

RMSE

RMSE

400
200
0
1

2

3

4

5

t

6

7

8

9

300

3

4

5

6

7

8

9

10

6

7

8

9

10

t
Dirichlet-1/2 prior

Non-private
Private eps=10
Private eps=2
Private eps=1

300

200

200

100

100

0
1

10

2

400

RMSE

400
600

200

150

50

Zipf 1/2
Non-private
Private eps=10
Private eps=2
Private eps=1

2

3

4

5

(a)

t

6

7

8

9

0
1

10

2

3

4

5

(b)

t

(c)

Figure 11: Comparison between the private estimator with the non-private SGT when k = 5000.

3000
2500

RMSE

RMSE

4000

12000

2

3

4

5

6

t
Zipf 1

7

8

9

1500

0
1

10

4500

Non-private
Private eps=10
Private eps=2
Private eps=1

4000
3500

6000

2

3

4

5

6

t
Dirichlet-1 prior

7

8

9

6000

Non-private
Private eps=10
Private eps=2
Private eps=1

5000

2000

3

4

5

(a)

t

6

7

8

9

10

3

4

5

6

7

8

9

10

6

7

8

9

10

t
Dirichlet-1/2 prior

Non-private
Private eps=10
Private eps=2
Private eps=1

3000
2000
1000

500
2

2

4000

2500

0
1

1500

0
1

10

1000

2000

2000

500

1500

4000

Zipf 1/2
Non-private
Private eps=10
Private eps=2
Private eps=1

1000

3000

8000

0
1

2500

500

RMSE

RMSE

10000

3000

1000

2000

14000

3500

2000

6000

0
1

Two steps
Non-private
Private eps=10
Private eps=2
Private eps=1

RMSE

8000

Uniform
Non-private
Private eps=10
Private eps=2
Private eps=1

RMSE

10000

2

3

4

5

(b)

t

6

7

8

9

10

0
1

2

3

4

5

t

(c)

Figure 12: Comparison between the private estimator with the non-private SGT when k = 100000.

23

