Privacy and Statistical Risk: Formalisms and Minimax Bounds

Introduction

In this paper, we study several definitions of privacy—formalisms for limiting disclosure in statistical procedures—and their consequences in terms of achievable (statistical) risk for estimation and data analysis. We review (and present a few new) definitions that attempt to capture what, intuitively, it should mean to limit disclosures from the output of an inferential task. We focus on several potential definitions for a strong type of disclosure limitation, where an adversary attempts to glean information from data released; in particular, notions of privacy centering around differential privacy (and its relaxations) as formulated by Dwork et al. . As a motivation for the definitions we study, consider a gene association study with a known list of subjects; we focus on guarantees such that even if the adversary knows the disease status (case or control) of many of the subjects in the study, he is not able to easily identify the disease status of remaining subjects. Differential privacy is designed for precisely this setting.

To protect against such an incident, we allow adversaries that are (1) computationally unbounded and (2) may have access to all elements of a sample $\{X_{1},\ldots,X_{n}\}$ except for a single unknown observation $X_{i}$; the estimators we compute must not release too much information about this last observation. While such definitions seem quite strong, they have motivated a body of work in the cryptography, database, and theoretical computer science communities, beginning with the work of Dwork, McSherry, Nissim, and Smith on differential privacy (see also the papers ). It has been quite challenging to give rigorous definitions of privacy against weaker adversaries (such definitions have often been shown to have fatal flaws), but subsequent works have broadened our understanding of acceptable privacy definitions and adversaries .

Our goal in this paper is to make more precise the relationship between privacy constraints and statistical estimation. Thus, in addition to presenting a variety of definitions, we provide comparison by focusing on their consequences for estimation: specifically, we ask whether there are substantive differences between minimax error for estimating parameters of a variety of distributions under different definitions of privacy. We show that, in fact, there are strong commonalities; focusing on mean estimation to be explicit, we find the minimax mean squared error of estimators under different privacy constraints is often very similar for seemingly different definitions of privacy. Nonetheless, some definitions allow more favorable dependence on dimension than standard (differential) privacy definitions, though at the expense of some security.

As a consequence of our focus on definitional aspects of privacy and their effects on statistical estimation and inference problems, we study estimation of population quantities. That is, we observe a sample $X_{i}$, $i=1,\ldots,n$, drawn from an unknown distribution $P$, and we wish to make inferences about some parameter $\theta(P)$ of the data generating distribution $P$ rather than reporting aspects of the sample itself. This focus is different from much of the work on optimality guarantees in private data analysis , though there have been a few authors who have studied population quantities (for example, Beimel and colleagues in the Probably Approximately Correct (PAC) model for concept learning). For more discussion on the issue of population estimation in private settings, see the discussion of Duchi et al. .

We conclude (in Section 5) with some discussion, including a few avenues for future work. We also present a table (Table 1) summarizing, for $d$-dimensional mean estimation problems, the effects of the ambient dimension $d$, the required amount of privacy, and number of moments $k$ assumed for the distribution from which our data is drawn. This table illustrates the main consequences of the results in this paper, allowing a more precise characterization of the tradeoffs between disclosure risk and statistical performance.

Definitions of privacy

We are interested in the setting where the adversary has access to all but one of the observations in the sample: he knows that $X_{1}=x_{1},\dots,X_{i-1}=x_{i-1},X_{i+1}=x_{i+1},\dots,X_{n}=x_{n}$, and seeks to determine the last remaining observation $X_{i}$. We represent the statistician, or estimation procedure, by a channel $Q(\cdot\!\mid\!\cdot)$, which, given a sample $X_{1:n}$ drawn from $\mathcal{X}^{n}$, releases a point $\theta\in\Theta$ according to the distribution $Q(\cdot\!\mid X_{1:n})$. Somewhat more formally, a channel is a regular conditional distribution (or probability kernel) [e.g. 19, Chapter 5] from the sample space $\mathcal{X}^{n}$ to the space $\Theta$. We assume that the data $X_{i}$ are drawn i.i.d. according to some (unknown) distribution $P$ with a parameter $\theta(P)$ we desire to estimate, and the goal of the statistician is to release $\theta$ that is as close as possible to the unknown $\theta(P)$ while guaranteeing that the adversary cannot identify any one observation $X_{i}$. With our privacy goals in mind, we can consider two related frameworks for bounding the information available to the adversary:

Likelihood/probability: Under the channel $Q$, for any region $A\subset\Theta$ of the output space, the likelihood of $A$ varies minimally for different possible values of $X_{i}$.

Hypothesis testing: If the adversary is considering two possible values $x_{i}$ and $x_{i}^{\prime}$ for $X_{i}$, the channel $Q$ provides minimal power for testing these hypotheses against each other.

In the remainder of this section, we give our definitions of privacy, beginning with differential privacy, then proceding to hypothesis-testing variants, and finally showing a variant of privacy that protects against adaptive and posterior inferences (to be made precise) about the sample. We make connections between all three via the hypothesis testing framework 2.

We begin our presentation of definitions with differential privacy, due to Dwork et al. .

A channel $Q$ is $\alpha$-differentially private ($\alpha$-DP) if for all $x_{1:n}$ and $x_{1:n}^{\prime}$ differing in only one observation,

This condition essentially requires that, regardless of the output, the likelihood under $Q$ does not distinguish samples differing in only a small number of observations.

Notably, we have $d_{\rm priv}\leq d_{\rm ham}$, and we thus define the stronger (more secure) version of differential privacy we call smooth differential privacy:

The channel $Q$ satisfies $(\rho_{\rm priv},\alpha)$-smooth differential privacy if for all samples $x_{1:n}$ and $x_{1:n}^{\prime}$,

Both of these definitions are quite strong: they require a likelihood ratio bound to hold even for an extremely low probability event $A$.

Example 1: Suppose that $X_{i}\in$ for all $i$, and we release the mean corrupted by an independent $\mathsf{N}(0,\sigma^{2}/n)$ variable, that is, $\theta=\frac{1}{n}\sum_{i=1}^{n}X_{i}+W$, where $W\sim\mathsf{N}(0,\sigma^{2}/n)$. Then the channel densities satisfy the ratios

which fails to be $\alpha$-DP for any $\alpha$, as we may have $|\theta|>\sigma^{2}\alpha$. Yet the probability of releasing such a large $\theta$ is exponentially small in $n$.

In this example, the probability of releasing a large $\theta$—thus revealing information distinguishing the samples $X_{1:n}$ and $X_{1:n}^{\prime}$—is negligible under both samples. Intuitively, these extremely low probability events should not cause us to declare a channel non-private. Such situations motivated Dwork et al. to define a relaxed version of differential privacy disregarding low-probability events:

A channel $Q$ is $(\alpha,\delta)$-approximately differentially private ($(\alpha,\delta)$-DP) if, for all $x_{1:n}$ and $x^{\prime}_{1:n}$ differing in only one observation,

For approximate differential privacy, as in differential privacy, one typically thinks of $\alpha$ as a constant (or decreasing polynomially to 0 as $n\to\infty$). To protect against catastrophic disclosures, one usually assumes that $\delta$ decreases super-polynomially, though not exponentially, to zero, that is, that that $\delta\leq\exp(-p(n))$ where $p(n)$ is a function satisfying $\log n\ll p(n)\ll n$. While the relaxed conditions of approximate differential privacy address situations such as Example 2.1, we show in Section 3 that the consequences for estimation under each of the privacy definitions 1, 2, and 3 are quite similar.

2 Testing-based and divergence-based definitions of privacy

We now turn to alternate definitions of privacy, again considering an adversary who knows most of the data in the sample, but we build on a framework of hypothesis testing. We believe these variants both give some intuition for the definitions of disclosure limitation and suggest potential weakenings of Definitions 1–3. Our first observation, essentially noted by Wasserman and Zhou [30, Thm. 2.4] due to Oh and Viswanath , is that differential privacy is equivalent to a form of false negative and false positive rate control for hypothesis tests that distinguish samples $X_{1:n}$ and $X_{1:n}^{\prime}$ differing in a single observation. In particular, let us assume that a test $\psi:\Theta\to\{0,1\}$ tries to distinguish the following two hypotheses, where $X_{1:n}$ is known except for its $i$th entry:

Here a result of 0 from the test $\psi$ indicates evidence that $X_{i}=x_{i}$, while a 1 indicates evidence instead that $X_{i}=x^{\prime}_{i}$. For shorthand let $Q(\cdot\!\mid H_{j})$ denote the channel (private) distribution under $H_{j}$. We have the following result; we provide a proof for completeness in Sec. A.1.

A channel $Q$ satisfies $(\alpha,\delta)$-approximate differential privacy if and only if for all hypothesis tests $\psi$ mapping to $\{0,1\}$, for any $x_{1:n},x^{\prime}_{1:n}$ with $d_{\rm ham}(x_{1:n},x^{\prime}_{1:n})\leq 1$,

where we define hypotheses $H_{0}:X_{1:n}=x_{1:n}$ and $H_{1}:X_{1:n}=x^{\prime}_{1:n}$. Moreover, $(\alpha,\delta)$-approximate differential privacy implies

That is, for small $\alpha$, the sum of the false positive rate and false negative rate, when testing $H_{0}$ against $H_{1}$, is nearly $1$ under differential privacy (this is similarly true for approximate differential privacy). This suggests a potential weakening of differential privacy: can we require that the adversary cannot test $H_{0}$ against $H_{1}$ with any high power? That is, will we achieve sufficient protection if we base privacy on mechanisms that achieve disclosure risk bounds of the form (3)?There is also a Bayesian interpretation of differential privacy that says that an adversaries prior and posterior beliefs after observing the output of $Q$ cannot change much; we defer discussion to Section 5.

As a first approach, we note that Le Cam’s inequality [e.g. 29, Chapter 2.4] implies that for any distributions $P_{0}$ and $P_{1}$, we have

where the infimum is taken over all measurable functions, and we recall that the total variation distance is $\left\|{P_{0}-P_{1}}\right\|_{\mathsf{TV}}=\sup_{A}|P_{0}(A)-P_{1}(A)|=\frac{1}{2}\int|dP_{0}-dP_{1}|$. Based on Le Cam’s inequality (4) and the consequence (3) of differential privacy, we arrive at the following proposal for privacy, which bounds differences rather than ratios of likelihoods:

A channel $Q$ is $\alpha$-total variation private ($\alpha$-TVP) if, for all $x_{1:n}$ and $x^{\prime}_{1:n}$ differing in only one observation,

Equivalently, the error for testing $x_{1:n}$ against $x_{1:n}^{\prime}$ has lower bound

Here the notation $Q(\psi=1\mid x_{1:n})$ is shorthand for $Q(\{\theta:\psi(\theta)=1\}\mid x_{1:n})$.

Notably, $\alpha$-total variation privacy means that an adversary cannot accurately test between $x_{1:n}$ and $x_{1:n}^{\prime}$. Comparing inequality (5) with inequality (3), we see that $\alpha$-TV privacy is less stringent than differential privacy. Unfortunately, while differential privacy may be strong, the testing-based weakening (5) may not be fully satisfactory, as the following well-known example (e.g. ) shows:

Example 2 (“Release one at random”): Consider a channel $Q$ that selects one observation at random and releases it, so that $Q(A\mid x_{1:n})=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\!\left\{{x_{i}\in A}\right\}$. Here the sample space and output space are equal, $\mathcal{X}=\Theta$. When samples $x_{1:n}$ and $x^{\prime}_{1:n}$ differ only at position $i$, then $|Q(A\mid x_{1:n})-Q(A\mid x^{\prime}_{1:n})|\leq\frac{1}{n}$ for any set $A\subset\mathcal{X}$, so $Q$ is $\alpha$-TV private for any $\alpha\geq 1/n$.

While pathological, the constructed channel is clearly not private in an intuitive sense—one of the $n$ individuals in the sample will suffer a complete loss of privacy, even though initially each individual had only a small chance of having his data revealed. Thus, simple hypothesis testing variants of privacy, such as inequality (3) (and the equivalent total variation privacy of Definition 4) do not provide sufficient protection against disclosure risk. One way to address this problem is to impose stronger divergence requirements on the channels $Q$ in Definition 4, for example, choosing a measure between distributions that is infinite when they are not mutually absolutely continuous.

where $\mu$ denotes a measure with respect to which $P$ and $Q$ are absolutely continuous (with densities $p$ and $q$). For such a convex $f$, we define

The channel $Q$ is $\alpha$-$f$-divergence private if

We recover Definition 4 by taking $f(t)=|t-1|$, we may take $f(t)=t\log t$ to obtain $\alpha$-Kullback-Leibler ($\alpha$-KL) privacy (which is more stringent than TV-privacy by Pinsker’s inequality):

We show in the sequel that mechanisms $Q$ satisfying KL-privacy (and hence TV-privacy) can yield more accurate estimates than approximately differentially private mechanisms. In contrast to these two divergence-based definitions, however, differential privacy offers “privacy in hindsight,” where even after the channel releases its output, each individual’s privacy is relatively secure.

3 Conditional hypothesis testing privacy

The “release-one-at-random” example highlights a need for stronger privacy requirements than hypothesis testing privacy (or equivalently, total variation privacy). With this in mind, we turn to a more restrictive notion of privacy based on hypothesis testing, where we assess the accuracy of a hypothesis test $\psi$ conditional on the output. This inspires an extension of our hypothesis testing idea that conditions on the observed output of the channel.

To define this notion of conditional hypothesis testing, we require a few additional definitions. We write $\mathcal{P}_{\mathcal{Y}}$ to denote the set of all distributions on the space $\mathcal{Y}$ (treating the $\sigma$-algebra as implicit), and given two spaces $\mathcal{X}$ and $\mathcal{Y}$, we abuse notation and write $Q:\mathcal{X}^{n}\to\mathcal{P}_{\mathcal{Y}}$ to denote that $Q$ is a regular conditional probability for $Y$ taking values in $\mathcal{Y}$ given $X_{1:n}\in\mathcal{X}^{n}$, that is, $Q(\cdot\!\mid x_{1:n})$ is a probability distribution on $\mathcal{Y}$ for each $x_{1:n}\in\mathcal{X}^{n}$ and is $\mathcal{X}^{n}$-measurable (a Markov kernel from $\mathcal{X}^{n}$ to $\mathcal{Y}$). With this notation, we define channel composition as follows.

Given channels $Q:\mathcal{X}^{n}\rightarrow\mathcal{P}_{\mathcal{Y}}$ and $Q^{\prime}:\mathcal{Y}\rightarrow\mathcal{P}_{\mathcal{Z}}$, the composition of $Q^{\prime}$ with $Q$, denoted $Q^{\prime}\circ Q:\mathcal{X}^{n}\rightarrow\mathcal{P}_{\mathcal{Z}}$ is defined via the hierarchical model

That is, we view $Q^{\prime}$ as a stochastic kernel from the set $\mathcal{Y}$ to the set $\mathcal{Z}$, where

With this definition of composition, we give a definition capturing when a channel communicates less than another, which also provides a partial order on channels.

Given channels $Q:\mathcal{X}^{n}\rightarrow\mathcal{P}_{\mathcal{Y}}$ and $Q^{\prime}:\mathcal{X}^{n}\rightarrow\mathcal{P}_{\mathcal{Z}}$, we say $Q^{\prime}$ is less informative than $Q$, written $Q^{\prime}\preceq Q$, if there exists a channel $Q^{\prime\prime}:\mathcal{Y}\rightarrow\mathcal{P}_{\mathcal{Z}}$ such that $Q^{\prime}=Q^{\prime\prime}\circ Q$.

The definition coincides with the notion of deficiency arising in the literature on statistical inference and comparison of experiments, dating to Blackwell’s work in the 1950s (see, for example, Le Cam and Yang [22, Chapter 2], or Liese and Vajda [24, Section VI]).

Definition 7 is natural: as we construct $Q^{\prime}$ from $Q$ via an independent randomization, no new information about the sample $X_{1:n}$ arises by moving from $Q$ to $Q^{\prime}$. Indeed, any channel $Q^{\prime}\preceq Q$ inherits privacy properties of $Q$; further processing cannot increase disclosure risk. More specifically, we have an information processing inequality (cf. [24, 7, Chapter 2]; see Section A.2 for a proof).

If $Q$ is $\alpha$-$f$-divergence private (Definition 5) then $Q^{\prime}$ is $\alpha$-$f$-divergence private.

If $Q$ is $(\alpha,\delta)$-differentially private, then $Q^{\prime}$ is $(\alpha,\delta)$-differentially private.

Using the notion of deficiency, we now provide a strengthened version of testing-based privacy.

A channel $Q$ is $(\alpha,\delta)$-conditional hypothesis testing private (CHTP) if for any pair of samples $x_{1:n}$, $x^{\prime}_{1:n}$ with $d_{\rm ham}(x_{1:n},x^{\prime}_{1:n})\leq 1$, any set $A\subset\Theta$ satisfying $Q(A\mid x_{1:n})\wedge Q(A\mid x^{\prime}_{1:n})\geq\delta$, and any test $\psi:\mathcal{Y}\rightarrow\{0,1\}$, we have

where the conditional channel is defined as

We make a few remarks on this definition. It says that the channel $Q$ must have large probability of error in testing between samples $x_{1:n}$ and $x^{\prime}_{1:n}$, even conditional on the output $\theta$ of the channel (at least for $\theta$ in sets with high enough probability). The definition is nontrivial only for $\alpha<1$. Unlike the notions of privacy introduced earlier (DP, TVP, and HTP), which are inherited (Observation 1), CHTP is not inherited—there exist channels $Q^{\prime}\preceq Q$ where $Q$ is $(\alpha,\delta)$-CHTP while $Q^{\prime}$ is not.

While expression (7) is superficially similar to our earlier testing-based definitions of privacy, its reliance on the conditioning set $A$ is important. It addresses the criticism of our original definition of testing-based privacy (cf. Example 2.2), which only provides a priori protection. This new definition says that even after observing the output of the channel $Q$, it is hard to test accurately between samples $x_{1:n}$ and $x^{\prime}_{1:n}$ differing in only a single entry; this posterior protection is more substantial. Another way to interpret posterior privacy, as compared to a priori privacy, is that we would like to limit the accuracy of hypothesis tests even when the hypotheses $H_{0}$ and $H_{1}$ and the test $\psi$ are constructed adaptively upon observing the output of the channel $Q$. To contrast with our earlier definitions, recall Example 2.2 (“release-one-at-random”). Under the release-one channel, we have little power a priori to test hypotheses $H_{0}:X_{i}=x_{i}$ and $H_{1}:X_{i}=x_{i}^{\prime}$ against each other, since it is unlikely (probability $\frac{1}{n}$) that the $i$th data point will be released. However, writing $i_{\text{released}}$ to denote the index of the randomly released data point, we are able to test hypotheses about $X_{i_{\text{released}}}$ with perfect accuracy. Requiring conditional hypothesis testing privacy, on the other hand, accounts for this issue and does not allow the “release-one-at-random” mechanism.

Interestingly, we can show that Definition 8 is essentially equivalent to (approximate) differential privacy, once we account for the issue of “inheritance” of the CHTP property:

If $Q$ is $(\alpha,\delta)$-DP, then it is $(\alpha_{\mathsf{CH}},\delta_{\mathsf{CH}})$-CHTP where

Conversely, suppose that for some $\alpha_{\mathsf{CH}}<1$ and $\delta_{\mathsf{CH}}$, $Q^{\prime}$ is $(\alpha_{\mathsf{CH}},\delta_{\mathsf{CH}})$-CHTP for every $Q^{\prime}\preceq Q$. Then $Q$ is $(\alpha,\delta)$-DP with

See Appendix A.3 for a proof of this theorem.

We have thus come full circle: differential privacy appears to be a strong requirement, so the simple a priori variants of testing-based privacy may seem more natural, requiring only that the chances of discovering any particular person in a dataset are small. However, the “release-one-at-random” example motivates us to move away from a priori privacy towards the posterior privacy guaranteed by the new notion of conditional hypothesis testing—which is equivalent to differential privacy.

Lower bounds on estimation of population quantities

where the expectation is taken over both the sample $X_{1:n}$ and the estimator $\widehat{\theta}(X_{1:n})$. To be precise, the data $X_{1},\dots,X_{n}$ are drawn i.i.d. from the distribution $P$, then the estimator $\widehat{\theta}(X_{1:n})$ is drawn according to the channel $Q(\cdot\!\mid X_{1:n})$ conditional on $X_{1:n}$.

We are interested in minimizing this error over all possible privacy-preserving mechanisms, so that for a family $\mathcal{Q}$ (i.e. the set of channel distributions $Q$ satisfying some chosen definition of privacy), we study the minimax risk for estimation of the population parameter $\theta(P)$, defined as

Our goal, for the remainder of this section, is to find lower bounds on this minimax error (both for the mean estimation problem and the general setting) under each of the privacy frameworks in the prequel. In Section 4, we derive upper bounds on the minimax error for mean estimation via concrete constructions of private channels $Q$ under the various frameworks.

A standard route for lower bounding the minimax risk (8) is to reduce the estimation problem to a testing problem, where we aim to identify a point $\theta\in\Theta$ from a finite collection of well-separated points . Given an index set $\mathcal{V}$ of finite cardinality, the indexed family of distributions $\{P_{\nu},\nu\in\mathcal{V}\}\subset\mathcal{P}$ is said to be a $2\delta$-packing of $\Theta$ if $\rho(\theta(P_{\nu}),\theta(P_{{\nu^{\prime}}}))\geq 2\delta$ for all $\nu\neq{\nu^{\prime}}\in\mathcal{V}$.

In the standard hypothesis testing problem (without privacy constraints), nature chooses $V\in\mathcal{V}$ uniformly at random, then (conditional on $V=\nu$) draws a sample $X_{1},\dots,X_{n}$ i.i.d. from the distribution $P_{\nu}$; the problem is to identify the member $V$ of the packing set $\mathcal{V}$. Several techniques exist for lower bounding the risk of this testing problem (see, for example, Yu , Tsybakov , or Yang and Barron for a survey of such techniques). In short, however, under the $2\delta$-packing construction above, each begins with the classical reduction of estimation to testing that

1 Lower bounds for weak forms of privacy

We begin by focusing on private estimation under the weakest privacy setting we have defined: the $\alpha$-$f$-divergence privacy settings (recall Definitions 4 and 5). In particular, we prove all results in this subsection using $\alpha$-total variation privacy; this is, in a sense, the smallest $f$-divergence (cf. Liese and Vajda [24, Section V], where it is shown that all $f$-divergences can be written as mixtures of variation-like distances) and thus the weakest form of privacy. The lower bounds we prove here extend immediately to all the definitions of privacy in this paper, as all the variants of differential privacy (Definitions 1, 2, 3) and KL-divergence privacy (6) imply total variation privacy.

For a channel $Q$, the information available to an observer about the original distribution $P$ of the data is disguised via $Q$. To that end, for a channel $Q$ and distribution $P_{\nu}$, we define the marginal

where $P_{\nu}^{n}$ is the $n$-fold product distribution (that is, $X_{1:n}\sim P_{\nu}^{n}$ is equivalent to $X_{1},\dots,X_{n}\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{\nu}$). This is the marginal distribution of the privately released estimator $\widehat{\theta}$ when the initial sample $X_{1:n}$ is drawn from $P_{\nu}^{n}$.

For the binary test described above, the probably of making an error is lower bounded as

where the infimum is taken over all testing procedures.

With this result in mind, if we can prove that the marginals $M_{\nu}$ are substantially closer in variation distance than are the $P_{\nu}$, we may obtain sharper minimax lower bounds on estimation. To that end, we prove the following quantitative data processing inequality, which says that for small privacy parameter $\alpha$ (i.e. a high privacy level), the output of the channel contains relatively little information about the true distribution $P$. (See Sec. B.1 for a proof.)

Let $P_{0}$ and $P_{1}$ be probability distributions on $\mathcal{X}$ and $P_{\nu}^{n}$, $\nu\in\{0,1\}$, be their $n$-fold products. Under $\alpha$-total-variation privacy (definition 4),

We now give two applications of this contraction inequality to classical estimation problems.

However, after adding a privacy constraint, we have the following result, which is a consequence of inequality (10), Lemma 1, and Theorem 2.

Consider the problem of mean estimation over the class (11) of distributions. If $\mathcal{Q}^{\mathsf{TV}}_{\alpha}$ denotes the family of $\alpha$-TV-private channels, then

We apply Le Cam’s method and the lower bound (10). First, we fix $\delta>0$ (to be chosen later), and we define the distributions $P_{0}$ and $P_{1}$ on $\{-r\delta^{-1/k},0,r\delta^{-1/k}\}$ via

where we have used the contraction inequality of Theorem 2. Choosing $\delta=1/(4n\alpha)$, we substitute to find

Our choice of $Q$ was arbitrary, so once we note that the lower bound $r^{2}/n$ on minimax estimation of a mean holds even in non-private settings, we obtain the lower bound. ∎

Inequality (12) exhibits some interesting effects of privacy, even under such weak definitions as total variation privacy. We might like to let $\alpha$ approach zero—meaning that the privacy guarantees become stronger—as the sample size $n$ grows. If the distribution is bounded, with $\left\|{X}\right\|_{2}\leq r$ always, then taking $k=\infty$ is possible and the lower bound in (12) scales as $r^{2}/n+r^{2}/(n^{2}\alpha^{2})$. The proposition then suggests (and we show later) that we can allow privacy at a level of $\alpha=1/\sqrt{n}$ without negatively affecting convergence rates. Under the weaker assumption that $2<k<\infty$, however, the proposition disallows such quickly decreasing $\alpha$; if $\alpha\ll n^{\frac{2-k}{2k-2}}$, there is a degradation in rate of convergence. Moreover, if all we can guarantee is a second moment bound ($k=2$), then any amount of privacy $\alpha<1$ forces the rate to degrade, and it is impossible to take $\alpha\to 0$ as $n\to\infty$ without suffering non-parametric rates of convergence.

1.2 Support estimation under total variation privacy

Let $\mathcal{Q}^{\mathsf{TV}}_{\alpha}$ denote the family of $\alpha$-TV-private channels, and for $t>0$ let $\mathcal{P}_{t}$ denote the collection of uniform distributions $\mathsf{Uni}[0,\theta]$ with $\theta\leq t$. Then in absolute value error,

Note that by Jensen’s inequality, the lower bound (13) implies that

There is thus no possible privacy setting allowing estimation at the statistically efficient rate.

Fix $\delta\in[0,t]$ and consider the two distributions $P_{0}=\mathsf{Uni}[0,t-\delta]$ and $P_{1}=\mathsf{Uni}[0,t]$. Comparing their variation distances, we have $\left\|{P_{1}-P_{2}}\right\|_{\mathsf{TV}}=\delta/t$. Moreover, their respective maxima $\theta_{0}=t-\delta$ and $\theta_{1}=t$ satisfy the separation condition $|\theta_{0}-\theta_{1}|=\delta$. Thus, by letting $M^{n}$ denote the marginal distribution of the released statistic, Le Cam’s method (Lemma 1) coupled with the estimation-to-testing lower bound (10) implies

By the contraction inequality of Theorem 2, we obtain the lower bound

Choosing $\delta=t/(4n\alpha)$ gives the result (13). ∎

2 Lower bounds with variants of differential privacy

We now turn to lower bounds on estimation when the mechanism $Q$ satisfies (a variant of) differential privacy. We will see that this implies stronger lower bounds than those implied by $\alpha$-total variation privacy, as we obtain results that exhibit dependence on the ambient dimension $d$ as well as on the privacy parameter $\alpha$. These lower bounds are based on a type of “uniformity of probability mass” argument. Roughly, they are consequences of a guarantee that differentially private estimators $\widehat{\theta}$ assign relatively high probability mass to all parts of the parameter space $\Theta$ as a consequence of the likelihood ratio guarantee that is their definition.

As in the previous section, we have a (semi)metric $\rho$ on the parameter space $\Theta$, and a family of distributions $\mathcal{P}$, where $\mathcal{V}$ indexes a subset $\{P_{\nu}\}_{\nu\in\mathcal{V}}\subset\mathcal{P}$. Additionally, we assume there exists a distribution $P_{0}$ on the space $\mathcal{X}$ such that for some (fixed) $p\in$, we have $(1-p)P_{0}+pP_{\nu}\in\mathcal{P}$ for all $\nu\in\mathcal{V}$. With this fixed $p$ in place, we may define the parameters we wish to estimate by

where $\theta:\mathcal{P}\to\Theta$ is our population statistic. (We omit $p$ from our notation for $\theta_{\nu}$, leaving it implicit.) We then define the separation of the set $\{\theta_{\nu}\}_{\nu\in\mathcal{V}}$ by

Now we come again to a standard testing problem: we choose a private procedure $\widehat{\theta}$ (given by a channel $Q$). After we make this choice, nature chooses one of the indices $\nu\in\mathcal{V}$, generating a sample $X_{1},\ldots,X_{n}$ drawn i.i.d. from the distribution $(1-p)P_{0}+pP_{\nu}$. Our goal is then to estimate the parameter \theta_{\nu}=\theta\big{(}(1-p)P_{0}+pP_{\nu}\big{)} accurately, which (essentially) corresponds to identifying the index $\nu$ nature chooses. Under this setting, we can develop a result inspired by arguments of Hardt and Talwar and Beimel et al. . In particular, we show that private mechanisms necessarily are (non-trivially) likely to release parameters far away from the true parameter. In our case, however, we study population parameters rather than sample quantities (in contrast to Hardt and Talwar ), approximate privacy, and use a more classical estimation framework rather than PAC learning .

The following theorem (whose proof we give in Section B.2) is our main tool for proving concrete lower lower bounds.

Fix $p\in$, and define $P_{\theta_{\nu}}=(1-p)P_{0}+pP_{\nu}\in\mathcal{P}$. Let $\widehat{\theta}$ be an $(\alpha,\delta)$-approximately differentially private estimator. Then

In the remainder of this section, we illustrate the consequences of this result via two examples, the first on mean estimation and the second on non-parametric density estimation. Roughly, we show that with appropriate choice of the mixture parameter $p$, Theorem 3 implies it is difficult to distinguish between the distributions $(1-p)P_{0}+pP_{\nu}$ and $(1-p)P_{0}+pP_{{\nu^{\prime}}}$, when $\nu\neq{\nu^{\prime}}$, as long as the packing set $\mathcal{V}$ is large enough. In particular applications, we show how this implies substantial dependence on the ambient dimension $d$ of the parameter space.

Let $\mathcal{Q}_{\alpha,\delta}$ denote the family of $(\alpha,\delta)$-approximately differentially private channels. Then for the mean estimation problem,

We usually think of $\delta$ as decreasing quite quickly with $n$—as a simple example, as $\delta=e^{-\sqrt{n}}$ with $\alpha\leq 1$—so that the sample complexity bound (16) implies the optimal statistically efficient rate is possible only if $n\geq(d^{2}/\alpha^{2})^{\frac{k-1}{k-2}}$. Thus, at least for suitably quickly decreasing $\delta$, we observe a quadratic-like penalty in convergence rate from the dimension.

Now, we apply the reduction of estimation to testing with this packing $\mathcal{V}$, which implies

We now choose $p$ to (approximately) maximize the preceding display, which makes the average probability of error constant. Without loss of generality, we may assume that $d\geq 2$ (as Proposition 2 gives the result when $d=1$), so that $2^{d}-1\geq e^{d/2}$. We choose

The second term in the minimum (17) is sufficiently small that

where we have used that the first term in the minimum (17) implies that $e^{d/2}e^{-\alpha(np+1)}\geq 1$. For the result (15), substitute the value (17) in the preceding display. ∎

2.2 Nonparametric density estimation under differential privacy

In this case, we obtain the following result; we prove the result only in the case of $\alpha$-differentially private channels ($\delta=0$) for simplicity. (See Section B.3 for the proof.)

Let $\mathcal{Q}_{\alpha}$ denote the family of $\alpha$-differentially private channels. Then for a constant $c_{d}>0$ that may depend on the dimension $d$,

The bound (18) is matched by known upper bounds. The $n^{-2/(2+d)}$ term in the bound is the well-known minimax rate for estimation of a Lipschitz density on $^{d}$; a standard histogram estimator achieves this convergence rate (see, for example, Yang and Barron or Tsybakov ). To attain the latter part of the lower bound, we recall Wasserman and Zhou [30, Theorem 4.4]. Making the immediate extension of their results to $d$ dimensions, we note that Wasserman and Zhou show that constructing a standard histogram estimator with $k$ equally sized bins on $^{d}$, then adding independent Laplace noise (of appropriate magnitude dependent on $\alpha$ and $k$) to each of the bins, and returning this histogram, gives an estimator $\widehat{f}_{\rm hist}$ that is $\alpha$-differentially private and satisfies

The first two terms are the standard bias-variance tradeoff in density estimation (e.g. [29, 8, Chapter 3]), while the last $k^{2}/n^{2}\alpha^{2}$ term is reminiscent of the bounds (15) in its additional quadratic penalty. Choosing $k=\min\{n^{1/(d+2)},(n\alpha)^{1/(d+1)}\}$ in expression (19) gives the bound (18).

We make one more remark on Proposition 5. Though our observations $X_{i}$ are bounded, as are the densities we estimate, we may not take the privacy parameter $\alpha$ to 0 as quickly as in the parametric problems in the preceding section. Indeed, if $\alpha=o(n^{-\frac{1}{2+d}})$ as $n\to\infty$, expression (18) shows it is impossible to attain the non-private rate. In contrast, in expression (15), we see that (assuming $k=+\infty$) as long as $\alpha\gg n^{-1/2}$, as $n\to\infty$ we attain the classical parametric rate.

A few upper bounds for mean estimation

The estimator (20) is a type of robustified estimator of location where outlying estimates are truncated to be within a ball of radius $T$; similar ideas for estimation of parameters have been used by Smith and are frequent in robust statistical estimation . By specific choices of $W$ and $T$, however, we can achieve order optimal rates of convergence for our private estimators.

We consider three distributions for $W$ that variously satisfy our privacy definitions. Before giving them, we note that if we define $v=\frac{1}{n}\sum_{i=1}^{n}\pi_{T}\left({x_{i}}\right)$ and $v^{\prime}=\frac{1}{n}\sum_{i=1}^{n}\pi_{T}\left({x_{i}^{\prime}}\right)$, then it is clear that

Let us first consider the divergence-based variants of privacy, focusing on $\alpha$-KL privacy (6). In this case, take $W\sim\mathsf{N}(0,\frac{2T^{2}}{n^{2}\alpha_{\mathsf{KL}}}I_{d\times d})$. Letting $Q$ denote the distribution of $\widehat{\theta}$, for samples $x_{1:n}$ and $x_{1:n}^{\prime}$ differing in at most a single observation we have

because $\left\|{v-v^{\prime}}\right\|_{2}\leq 2T/n$. Therefore, this estimator achieves KL-privacy as desired.

Turning now to the variants of differential privacy, we note that the Hamming-Lipschitz guarantee (21) implies that if we take $W\sim\mathsf{N}(0,\frac{2T^{2}\log\frac{1}{\delta}}{n^{2}\alpha^{2}}I_{d\times d})$, then the estimator $\widehat{\theta}$ is $(\alpha,\delta)$-approximately differentially private (see, for example, Dwork et al. or Hall [14, Section 1.3.2]).

Finally, we show how to satisfy the strongest variant of privacy, smooth differential privacy (Definition 2). In particular, using the metric $\rho_{\rm priv}(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|_{2}\wedge 2T$ and $d_{\rm priv}(x_{1:n},x_{1:n}^{\prime})=\frac{1}{2T}\sum_{i=1}^{n}\rho_{\rm priv}(x_{i},x_{i}^{\prime})$, we claim that taking $W$ to have independent coordinates, each Laplace distributed with density $p(w)\propto\exp(-\kappa|w|)$, where $\kappa=\alpha n/2T\sqrt{d}$, satisfies smooth differential privacy. Indeed, we have that the ratio of the densities

where the final inequality uses the bound (21). In particular, this additive Laplace noise mechanism satisfies smooth differential privacy and, by extension, differential privacy.

With these three mechanisms in place, we have the following proposition, whose proof we provide in Section C.

Consider the estimator (20). The following hold.

Choose $T=r(n^{2}\alpha_{\mathsf{KL}}/d)^{1/(2k)}$ and let $W\sim\mathsf{N}(0,\frac{2T^{2}}{n^{2}\alpha_{\mathsf{KL}}}I_{d\times d})$. Then $\widehat{\theta}$ is $\alpha_{\mathsf{KL}}$-KL private, and

Choose $T=r(n^{2}\alpha^{2}/(d\log\frac{1}{\delta}))^{1/(2k)}$ and let $W\sim\mathsf{N}(0,\frac{2T^{2}\log\frac{1}{\delta}}{n^{2}\alpha^{2}}I_{d\times d})$. Then $\widehat{\theta}$ is $(\alpha,\delta)$-approximately differentially private, and

Choose $T=r(n\alpha/d)^{1/k}$ and let $W$ have independent $\mathop{\rm Laplace}(\alpha n/(2T\sqrt{d}))$-distributed coordinates. Then $\widehat{\theta}$ is $\alpha$-differentially private and $(\rho_{\rm priv},\alpha)$-smoothly differentially private (Def. 2) with metric $\rho_{\rm priv}(x,x^{\prime})=\left\|{x-x^{\prime}}\right\|_{2}\wedge 2T$, and

Proposition 6 shows that many of the lower bounds we have provided on population estimators in Section 3 are tight. We summarize each of the convergence guarantees in Table 1, which shows upper and lower bounds on estimation of a population mean that we have derived. (Note that by Pinsker’s inequality , $2\left\|{P_{0}-P_{1}}\right\|_{\mathsf{TV}}^{2}\leq D_{\rm kl}\left({P_{0}}\|{P_{1}}\right)$, so that lower bounds for $\alpha$-total variation privacy imply lower bounds for $\sqrt{\alpha_{\mathsf{KL}}}$-KL privacy, and convergence guarantees for $\alpha_{\mathsf{KL}}$-KL private estimators give convergence guarantees for $\alpha^{2}$-TV private estimation.) While our bounds for $\alpha_{\mathsf{KL}}$-KL and $\alpha$-TV private estimators are not sharp—we are missing a factor of the dimension $d$ between upper and lower bounds—we see that divergence-based privacy allows substantially better convergence guarantees as a function of the dimension as compared with differential privacy. However, it does not permit better scaling with the moments $k$ of the problem; all privacy guarantees suffer as the number $k$ of moments available shrinks. Moreover, Proposition 6, when coupled with the lower bounds provided by Proposition 4, shows that there is (essentially) no difference in estimation rates between smooth differential privacy and differential privacy. In a sense, it is possible to provide even stronger guarantees than differential privacy without suffering in performance.

Summary and open questions

In this paper, we have provided a variety of definitions and formalisms for privacy, as well as reviewing definitions already present in the literature. We showed that testing-based definitions of privacy, which provide a priori protection against disclosures of sensitive data, have some similarities with differential privacy and related notions of privacy. On the other hand, differential privacy provides posterior guarantees of privacy and testing, and is in fact equivalent to variants of testing-based notions of privacy that provide protection against inferences conditional on the output of the private procedure.

To complement the definitional study we provide, we also investigated consequences of our definitions for different estimation tasks for population quantities. We identified a separation between estimating means under (smooth) differential, approximate differential, and the divergence-based (a priori testing) versions of privacy, as exhibited by Table 1. It is clear that there are many open questions remaining: first, our results are not all sharp, as our upper and lower bounds match precisely only for the strongest variants of privacy. Perhaps more interestingly, the weakest (testing-based) definitions of total variation privacy is unsatisfactory (recall the “release-one-at-random” scenario in Example 2.2), but perhaps other divergences (Definition 5) provide satisfactory privacy protection. Such schemes allow substantially better estimation than differential privacy constraints, as shown in Table 1, and may provide adequate assurances of privacy in scenarios with a weaker adversary.

We believe that future work on alternate definitions of privacy, which consider weaker adversaries (see Bassily et al. ), should be fruitful. For example, differential privacy is equivalent to guarantees that an adversary’s posterior beliefs on the presence or absence of a data point $x$ in a sample $X_{1:n}$ cannot be too different from his prior beliefs—no matter the adversary’s prior . Can restrictions on an adversary’s prior beliefs, as studied by Bassily et al. , allow more accurate estimation? We believe any proposal for privacy definitions should also include an exploration of the fundamental limits of inferential procedures, as without such an understanding, it is difficult to balance statistical utility and disclosure risk. We hope that the techniques and insights we have developed here provide groundwork for such future study into the tradeoffs between privacy guarantees and estimation accuracy.

We thank Philip Stark and Martin Wainwright for several insightful conversations on and feedback about the paper, and Philip for suggesting several variants of privacy and testing inequalities.

Appendix A Proofs related to privacy definitions

In this section, we collect proofs of the equivalence between our various notions of privacy as well as a few consequences of our different definitions.

We begin by proving that inequality (2) is equivalent to $\alpha$-differential privacy. Indeed, let $A\subset\Theta$ be an arbitrary set and let $\psi(\theta):=\mathbf{1}\!\left\{{\theta\in A}\right\}$. Then if inequality (2) holds, we have

Since $A$ was arbitrary, the channel $Q$ satisfies Definition 1. The other direction is trivial.

Now we demonstrate inequality (3). Applying (2) twice, we have

(where the second version holds by swapping $x_{1:n}$ with $x^{\prime}_{1:n}$, and replacing $\psi$ with $1-\psi$, then applying (2)). Adding these two inequalities together, we obtain

proving the first inequality in (3). The second statement of the inequality follows because $\frac{2}{1+e^{\alpha}}\geq 1-\frac{\alpha}{2}$ for all $\alpha\geq 0$.

A.2 Proof of Observation 1

The first statement of the observation is immediate because of the data processing inequality for $f$-divergences (see, e.g. Liese and Vajda [24, Theorem 14]): we are guaranteed that for any samples $x_{1:n}$ and $x^{\prime}_{1:n}$ in $\mathcal{X}^{n}$,

by the Markovian construction of $Q^{\prime}$ from $Q$, that is, $Q^{\prime}=Q^{\prime\prime}\circ Q$ for some $Q^{\prime\prime}$ by Definition 7.

Applying the same reasoning to the sample $x^{\prime}_{1:n}$, and using the fact that $Q$ is $(\alpha,\delta)$-differentially private, we then have

A.3 Proof of Theorem 1

We split the proof into the two statements: differential privacy implies conditional hypothesis testing privacy, and conditional hypothesis testing privacy (for $Q$ and for all less informative channels $Q^{\prime}\preceq Q$) implies differential privacy.

We need to show that for any samples $x_{1:n}$ and $x^{\prime}_{1:n}$ differing in at most one observation and measurable sets $A\subset\mathcal{Y}$ satisfying $Q(A\mid x_{1:n})\wedge Q(A\mid x^{\prime}_{1:n})\geq\delta_{\mathsf{CH}}$,

We assume that $Q(A\mid x^{\prime}_{1:n})\geq(e^{2\alpha}-e^{\alpha})^{-1}\delta$, as otherwise CHTP is satisfied regardless.

Let $B=\psi^{-1}(\{1\})\subset\mathcal{Y}$ be the acceptance region for the test $\psi$. Then by Bayes’ rule and differential privacy, we have

where inequality (i) follows from the assumption that $Q(A\mid x^{\prime}_{1:n})\geq\delta_{\mathsf{CH}}=(e^{2\alpha}-e^{\alpha})^{-1}\delta$. Adding the fractions in the previous display, we obtain

where the second inequality follows again by assumption that $Q(A\mid x^{\prime}_{1:n})\geq\delta_{\mathsf{CH}}$.

A.3.2 CHTP implies DP

First, solving for $\alpha_{\mathsf{CH}}$ and $\delta_{\mathsf{CH}}$ in the statement of the theorem, we have

We need to show that $Q$ is $(\alpha,\delta)$-differentially private, as long as for any $\widetilde{Q}\preceq Q$, and for any samples $x_{1:n}$ and $x^{\prime}_{1:n}$ with $d_{\rm ham}(x_{1:n},x^{\prime}_{1:n})\leq 1$, we have

For the sake of contradiction, let us assume that $Q$ is not $(\alpha,\delta)$-differentially private, and so there is a set $B$ and two samples $x_{1:n}$ and $x^{\prime}_{1:n}$ with $d_{\rm ham}(x_{1:n},x^{\prime}_{1:n})\leq 1$ such that

In particular, we will show that if there is a set $B$ satisfying inequality (23), then the upper bound (22) fails to hold. Let $C=B^{c}$ be the complement of $B$. Set the thresholds

Let the channel $\widetilde{Q}$ be defined by $\widetilde{Q}(\cdot\!\mid X)=Q(\cdot\!\mid X)\times\mathsf{Uni}$, that is, the output of $\widetilde{Q}$ conditional on $X$ is the pair $(Y,U)$, where $Y\sim Q(\cdot\!\mid X)$ and $U$ is an independent uniform random variable. In this case, we have the relation $\widetilde{Q}\preceq Q$, so that $\widetilde{Q}$ must satisfy inequality (22) for any test $\psi$ and samples $x_{1:n}$ and $x^{\prime}_{1:n}$ satisfying $d_{\rm ham}(x_{1:n},x^{\prime}_{1:n})\leq 1$. If we define the Cartesian products

we also obtain the following pair of inequalities:

Moreover, we have the string of equalities

With the strict inequalities (24) and equation (25), we can derive our desired contradiction to the testing upper bound (22), which we prove by conditioning on $Z\in\widetilde{A}\coloneqq\widetilde{B}\cup\widetilde{C}$. First, we must check that $\widetilde{Q}(\widetilde{A}\mid x_{1:n})\wedge\widetilde{Q}(\widetilde{A}\mid x^{\prime}_{1:n})\geq\delta_{\mathsf{CH}}$. Indeed, since $\widetilde{A}=\widetilde{B}\cup\widetilde{C}$, we have

by Eq. (25). By assumption (23), we know that $Q(B\mid x_{1:n})>\delta=e^{\frac{\alpha}{2}}\delta_{\mathsf{CH}}$, and inequality (23) implies $1-Q(C\mid x_{1:n})>e^{\alpha}(1-Q(C\mid x^{\prime}_{1:n}))+\delta$, and so

Therefore, the bound $\widetilde{Q}(\widetilde{A}\mid x_{1:n})\wedge\widetilde{Q}(\widetilde{A}\mid x^{\prime}_{1:n})\geq\delta_{\mathsf{CH}}$ holds, and we turn to contradicting the inequality (22), that is,

To that end, we choose a particular test: let $\psi(y)=\mathbf{1}\!\{{y\in\widetilde{C}}\}$. Then by Bayes’ rule and the fact that $\widetilde{B}$ and $\widetilde{C}$ are disjoint, we obtain

where step (i) follows by inequality (24b) and step (ii) follows from Eq. (25). To lower bound the second probability in the testing upper bound (22), we have

where we have used inequality (24a) for step (i) and Eq. (25) again for step (ii). Combining the two preceding displays, we obtain

where we have recalled the definition of $\alpha_{\mathsf{CH}}$. This contradicts the testing bound (22).

Appendix B Proofs of Minimax Lower Bounds

In this section, we collect proofs of each of our minimax lower bounds and their related results.

In this section we prove a slightly more general form of Theorem 2. Let $P_{0,i}$ and $P_{1,i}$, $i=1,\ldots,n$ be probability distributions on $\mathcal{X}$, and let $P_{\nu}^{n}$ be their $n$-fold products for $\nu=0,1$ (that is, we draw independent, but not necessarily identically distributed, observations $X_{1}\sim P_{\nu,1}$, …, $X_{n}\sim P_{\nu,n}$). Under $\alpha$-total-variation privacy (Def. 4), we will prove that

For the special case that $P_{\nu,i}=P_{\nu}$ for all $i=1,\dots,n$ (for each $\nu=0,1$), this proves that

The inequality $\left\|{M_{0}^{n}-M_{1}^{n}}\right\|_{\mathsf{TV}}\leq\left\|{P_{0}^{n}-P_{1}^{n}}\right\|_{\mathsf{TV}}$ is immediate from the classical data processing inequality (cf. [24, Theorem 14]), so proving inequality (26) is sufficient to prove the theorem.

Now we turn to the proof of (26). By the product nature of $P_{\nu}^{n}(x_{1:n})$ for each $\nu=0,1$, we have

For any set $A\in\sigma(\mathcal{Z})$, we thus have

where the supremum is taken over samples with $d_{\rm ham}(x_{1:n},x_{1:n}^{\prime})\leq 1$. By our privacy assumption, we have

and since $\int|dP_{0,i}-dP_{1,i}|=2\left\|{P_{0,i}-P_{1,i}}\right\|_{\mathsf{TV}}$, this completes the proof.

B.2 Proof of Theorem 3

We begin the proof of Theorem 3 by stating a lemma that shows, roughly, that a set $A$ with high probability under a distribution $P_{\theta_{\nu}}$ must also have high probability under $P_{\theta_{{\nu^{\prime}}}}$, so long as the estimator $\widehat{\theta}$ is $\alpha$-differentially private. We recall the definition of $P_{\theta_{\nu}}=(1-p)P_{0}+pP_{\nu}$ (where the sample size $n$ is implicit).

Let $A$ be a measurable set, and $\nu,{\nu^{\prime}}\in\mathcal{V}$. Assume that $P_{\theta_{\nu}}\in\mathcal{P}$ for all $\nu$. Then if $\widehat{\theta}$ is $(\alpha,\delta)$-approximately differentially private,

where we have used the definition (28) of $P_{\mathsf{succ}}$. Rearranging terms, we obtain

Lower bounding $1-P_{\mathsf{succ}}$ gives the theorem.

Proof of Lemma 2 Let $B=\{B_{i}\}_{i=1}^{n}$ be sequence of i.i.d. $\mathop{\rm Bernoulli}(p)$ random variables. Now, assume that observations are generated according to the following distribution: first, draw $W_{1}^{0},\dots,W_{n}^{0}\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{0}$ and draw $W^{\nu}_{1},\dots,W^{\nu}_{n}\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{\nu}$. Then for each $i$, if $B_{i}=0$, set $X_{i}=W_{i}^{0}$, while if $B_{i}=1$, set $X_{i}=W^{\nu}_{i}$. By inspection, we have that observations are marginally drawn i.i.d. according to the mixture $P_{\theta_{\nu}}=(1-p)P_{0}+pP_{\nu}$. Additionally, for fixed ${\nu^{\prime}}\in\mathcal{V}$, generate an alternate sample by drawing $W^{{\nu^{\prime}}}_{i}\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{{\nu^{\prime}}}$ and setting

for each $i$. By construction, we observe that

By definition of $(\alpha,\delta)$-approximate differential privacy, we have for any fixed sequence $b\in\{0,1\}^{n}$ that

Applying the approximate differential privacy lower bound (29), we obtain the further lower bound

the last inequality following from a union bound. The median of the $\mathsf{Binomial}(n,p)$ distribution is no larger than $\left\lceil{np}\right\rceil$, so we obtain

B.3 Proof of Proposition 5

The first term in the bound (18) is a standard result in nonparametric density estimation; see, for example, Tsybakov [29, Theorem 2.8], Devroye and Györfi [8, Chapter 4], or Yang and Barron [31, Section 6]. We thus focus on the second term in the lower bound (18).

Let $P_{0}$ be the uniform distribution on $^{d}$, with density $f\equiv 1$. Standard results in approximation theory and density estimation (see, for example, the Devroye and Györfi [8, Chapter 4], Yang and Barron , or Lorentz [25, Section 5]) show the following result: the packing entropy for the collection of $1$-Lipschitz densities on $^{d}$ scales as $(1/\epsilon)^{d}$. More concretely, there exist constants $c_{0},c_{1}>0$ (that may depend on the dimension $d$) such that for any $\epsilon\in\left({0},{1}\right]$, there exists a collection $\{f_{\nu}\}_{\nu\in\mathcal{V}}$ of densities $f_{\nu}$, where each density $f_{\nu}$ is $1$-Lipschitz continuous, $\left\|{f_{\nu}-f_{{\nu^{\prime}}}}\right\|_{2}\geq c_{0}\epsilon$, the set $\mathcal{V}$ has cardinality

Now, choose $p\in\left({0},{1}\right]$, and set $\epsilon=p$ in the construction leading to the inequalities (30). Then the density $1+(1/p)(f_{\nu}-1)$ is a valid density and is $(1/p)$-Lipschitz. If $P_{\nu}$ denotes the distribution with this density, then we have $(1-p)P_{0}+pP_{\nu}\in\mathcal{P}$, and moreover, the mixture $(1-p)P_{0}+pP_{\nu}$ has density $(1-p)+p[\frac{1}{p}(f_{\nu}-1)+1]=f_{\nu}$. In particular, we have the separation (for the metric $\rho(f,g)=\left\|{f-g}\right\|_{2}$)

We now apply Theorem 3, setting $\delta=0$ as we are working with differential privacy. Letting $f_{P}$ denote the density associated with the distribution $P$, we obtain that for any $\alpha$-differentially private estimator $\widehat{f}$ based on $n$ observations and any $p\in$ that

By choosing $p=\min\{\frac{1}{2}(n\alpha/c_{1})^{-\frac{1}{d+1}},1\}$ we obtain

where $c_{d}$ is a constant that may depend on $d$. This gives the desired result (18).

Appendix C Proof of Proposition 6

We begin our proof by presenting two lemmas, the first of which gives a bound on the bias of our estimator, the second showing that the variance of random vectors projected onto convex sets is always smaller than the initial variance.

where the second inequality follows from Markov’s inequality. ∎

where each step follows from the fact that $X$ and $X^{\prime}$ are i.i.d. Similarly, we also have

Now, for each of the privacy types, we evaluate the risk of the resulting estimator when we perturb the mean of the truncated variables by $W$. We begin with $\alpha$-KL privacy (equation (6)). In this case, we take $W\sim\mathsf{N}\left(0,\frac{T^{2}}{n^{2}\alpha_{\mathsf{KL}}}I_{d\times d}\right)$, and using the decomposition (31), the rate of convergence is bounded by

Setting $T=(n^{2}\alpha_{\mathsf{KL}}/d)^{1/(2k)}$ to approximately minimize the preceding expression, we obtain that

To obtain the results for $(\alpha,\delta)$-approximate differential privacy and $\alpha$-differential privacy, we sample $W$ from a $\mathsf{N}(0,\frac{T^{2}\log\frac{1}{\delta}}{n^{2}\alpha^{2}}I_{d\times d})$ distribution, which yields $(\alpha,\delta)$-approximate differential privacy as noted previously, and that

Choosing $T=(n^{2}\alpha^{2}/(d\log\delta^{-1}))^{1/(2k)}$ gives the second result of the proposition.

so that as before, choosing $T=(n^{2}\alpha^{2}/d^{2})^{1/(2k)}$ gives the final result. ∎

References