A statistical framework for differential privacy

Introduction

One goal of data privacy research is to derive a mechanism that takes an input database $X$ and releases a transformed database $Z$ such that individual privacy is protected yet information content is preserved. This is known as disclosure limitation. In this paper we will consider various methods for producing a transformed database $Z$ and we will study the accuracy of inferences from $Z$ under various loss functions.

There are numerous approaches to this problem. The literature is vast and includes papers from computer science, statistics and other fields. The terminology also varies considerably. We will use the terms “disclosure limitation” and “privacy guarantee” interchangeably.

One approach to defining a privacy guarantee that has received much attention in the computer science literature is known as differential privacy (Dwork et al., 2006, Dwork, 2006). There is a large body of work on this topic including, for example, Dinur and Nissim (2003), Dwork and Nissim (2004), Blum et al. (2005), Dwork et al. (2007), Nissim et al. (2007), Barak et al. (2007), McSherry and Talwar (2007), Blum et al. (2008), Kasiviswanathan et al. (2008). Blum et al. (2008) gives a machine learning approach to inference under differential privacy constraints and to some extent our results are inspired by that paper. Smith (2008) shows how to provide efficient point estimators while preserving differential privacy. He constructs estimators for parametric models with mean squared error $(1+o(1))/(nI(\theta))$ where $I(\theta)$ is the Fisher information. Machanavajjhala et al. (2008) consider privacy for histograms by sampling from the posterior distribution of the cell probabilities. We discuss Machanavajjhala et al. (2008) further in Section 4. After submitting the first draft of this paper, new work has appeared on differential privacy that is also statistical in nature, namely, Ghosh et al. (2009), Dwork and Lei (2009), Dwork et al. (2009), Feldman et al. (2009).

The goals of this paper are to explain differential privacy in statistical language, to show how to compare different privacy mechanisms by computing the rate of convergence of distributions and densities based on the released data $Z$, and to study a general privacy method, called the exponential mechanism, due to McSherry and Talwar (2007). We show that the accuracy of this method is intimately linked to the rate at which the probability that the empirical distribution concentrates in a small ball around the true distribution. These so called “small ball probabilities” are well-studied in probability theory. To the best of our knowledge, this is the first time a connection has been made between differential privacy and small ball probabilities. We need to make two disclaimers. First, the goal of our paper is to investigate differential privacy. We will not attempt to review all approaches to privacy or to compare differential privacy with other approaches. Such an undertaking is beyond the scope of this paper. Second, we focus only on statistical properties here. We shall not concern ourselves in this paper with computational efficiency.

In Section 2 we define differential privacy and provide motivation for the definition. In Section 3 we discuss conditions that ensure that a privacy mechanism preserves information. In Section 4 we consider two histogram based methods. In Section 5 and 6, we examine another method known as the exponential mechanism. Section 7 contains a small simulation study and Section 8 contains concluding remarks. All technical proofs appear in Section 9.

We consider several different data release mechanisms that satisfy differential privacy. We evaluate the utility of these mechanisms by evaluating the rate at which $d(P,P_{Z})$ goes to 0, where $P$ is the distribution of the data $X\in{\cal X}$, $P_{Z}$ is the empirical distribution of the released data $Z$, and $d$ is some distance between distributions. This gives an informative way to compare data release mechanisms. In more detail, we consider the Kolmogorov-Smirnov (KS) distance: $\sup_{x\in{\mathcal{X}}}|F(x)-\widehat{F}_{Z}(x)|$, where $F$, $\widehat{F}_{Z}$ denote the cumulative distribution function (cdf) corresponding to $P$ and the empirical distribution function corresponding to $P_{Z}$, respectively. We also consider the squared $L_{2}$ distance: $\int(p(x)-\widehat{p}_{Z})^{2}$, where $\widehat{p}_{Z}$ is a density estimator based on $Z$. Our results are summarized in the following tables, where $n$ denotes the sample size.

The next table summarizes the results for the case where the dimension of $X$ is $r=1$ and the density $p$ is assumed to be in a Sobolev space of order $\gamma$. We only consider the squared $L_{2}$ distance between the true density $p$ and the estimated density $\widehat{p}_{Z}$ in this case. The results are from Section 6 of the paper.

Our results show that, in general, privacy schemes seem not to yield minimax rates. Two exceptions are perturbation methods evaluated under $L_{2}$ loss which do yield minimax rates. An open question is whether the slower than minimax rates are intrinsic to the privacy methods. It is possible, for example, that our rates are not tight. This question could be answered by establishing lower bounds on these rates. We consider this an important topic for future research.

Differential Privacy

Let $X_{1},\ldots,X_{n}$ be a random sample (independent and identically distributed) of size $n$ from a distribution $P$ where $X_{i}\in{\cal X}$. To be concrete, we shall assume that ${\cal X}\equiv^{r}=\times\times\cdots\times$ for some integer $r\geq 1$. Extensions to more general sample spaces are certainly possible but we focus on this sample space to avoid unnecessary technicalities. (In particular, it is difficult to extend differential privacy to unbounded domains.) Let $\mu$ denote Lebesgue measure and let $p=dP/d\mu$ if the density exists. We call $X=(X_{1},\ldots,X_{n})$ a database. Note that $X\in{\cal X}^{n}=^{r}\times\cdots\times^{r}$. We focus on mechanisms that take a database $X$ as input and output a sanitized database $Z=(Z_{1},\ldots,Z_{k})\in{\cal X}^{k}$ for public release. In general, $Z$ need not be the same size as $X$. For some schemes, we shall see that large $k$ can lead to low privacy and high accuracy while while small $k$ can lead to high privacy and low accuracy. We will let $k\equiv k(n)$ change with $n$. Hence, any asymptotic statements involving $n$ increasing will also allow $k$ to change as well.

A data release mechanism $Q_{n}(\cdot|X)$ is a conditional distribution for $Z=(Z_{1},\ldots,Z_{k})$ given $X$. Thus, $Q_{n}(B|X=x)$ is the probability that the output database $Z$ is in a set $B\in{\cal B}$ given that the input database is $x$, where ${\cal B}$ are the measurable subsets of ${\cal X}^{k}$. We call $Z=(Z_{1},\ldots,Z_{k})$ a sanitized database. Schematically:

The marginal distribution of the output database $Z$ induced by $P$ and $Q_{n}$ is $M_{n}(B)=\int Q_{n}(B|X=x)dP^{n}(x)$ where $P^{n}$ is the $n$-fold product measure of $P$.

A simple example to help the reader have a concrete example in mind is adding noise. In this case, $Z=(Z_{1},\ldots,Z_{n})$ where $Z_{i}=X_{i}+\epsilon_{i}$ and $\epsilon_{1},\ldots,\epsilon_{n}$ are mean 0 independent observations drawn from some known distribution $H$ with density $h$. Hence $Q_{n}$ has density $q_{n}(z_{1},\ldots,z_{n}|x_{1},\ldots,x_{n})=\prod_{i=1}^{n}h(z_{i}-x_{i})$.

Given two databases $X=(X_{1},\ldots,X_{n})$ and $Y=(Y_{1},\ldots,Y_{n})$, let $\delta(X,Y)$ denote the Hamming distance between $X$ and $Y$: \delta(X,Y)=\#\Bigl{\{}i:\ X_{i}\neq Y_{i}\Bigr{\}}.

A general data release mechanism is the exponential mechanism (McSherry and Talwar, 2007) which is defined as follows. Let $\xi:{\cal X}^{n}\times{\cal X}^{k}:\to[0,\infty)$ be any function. Each such $\xi$ defines a different exponential mechanism. Let

that is, $\Delta_{n,k}$ is the maximum change to $\xi$ caused by altering a single entry in $x$. Finally, let $(Z_{1},\ldots,Z_{k})$ be a random vector drawn from the density

where $\alpha\geq 0$, $z=(z_{1},\ldots,z_{k})$ and $x=(x_{1},\ldots,x_{n})$. In this case, $Q_{n}$ has density $h(z|x)$. We’ll discuss the exponential mechanism in more detail later.

There are many definitions of privacy but in this paper we focus on the following definition due to Dwork et al. (2006) and Dwork (2006).

Let $\alpha\geq 0$. We say that $Q_{n}$ satisfies $\alpha$-differential privacy if

where ${\cal B}$ are the measurable sets on ${\cal X}^{k}$. The ratio is interpreted to be 1 whenever the numerator and denominator are both 0.

The definition of differential privacy is based on ratios of probabilities. It is crucial to measure closeness by ratios of probabilities since that protects rare cases which have small probability under $Q_{n}$. In particular, if changing one entry in the database $X$ cannot change the probability distribution $Q_{n}(\cdot|X=x)$ very much, then we can claim that a single individual cannot guess whether he is in the original database or not. The closer $e^{\alpha}$ is to 1, the stronger privacy guarantee is. Thus, one typically chooses $\alpha$ close to 0. See Dwork et al. (2006) for more discussion on these points. Indeed, suppose that two subjects each believe that one of them is in the original database. Given $Z$ and full knowledge of $P$ and $Q_{n}$ can they test who is in $X$? The answer is given in the following result. (In this result, we drop the assumption that the user does not know $Q_{n}$.)

Suppose that $Z$ is obtained from a data release mechanism that satisfies $\alpha$-differential privacy. Any level $\gamma$ test which is a function of $Z$, $P$ and $Q_{n}$ of $H_{0}:X_{i}=s$ versus $H_{1}:X_{i}=t$ has power bounded above by $\gamma e^{\alpha}$.

Thus, if $Q_{n}$ satisfies differential privacy then it is virtually impossible to test the hypothesis that either of the two subjects is in the database since the power of such a test is nearly equal to its level. A similar calculation shows that if one does a Bayes test between $H_{0}$ and $H_{1}$ then the Bayes factor is always between $e^{-2\alpha}$ and $e^{2\alpha}$. For more detail on the motivation for the definition as well as consequences, see Dwork et al. (2006), Dwork (2006), Ganta et al. (2008), Rastogi et al. (2009).

The following result, which is proved in McSherry and Talwar (2007) (Theorem 6), shows that the exponential mechanism always preserves differential privacy.

(McSherry and Talwar, 2007) The exponential mechanism satisfies the $\alpha$-differential privacy.

If $T(X,R)$ satisfies differential privacy then $U=h(T(X,R))$ also satisfies differential privacy for any measurable function $h$.

(Proposition 1 from Dwork et al. (2006).) Let $f(x)$ be a function of $x=(x_{1},\ldots,x_{n})$ and define $S(f)=\sup_{x,x^{\prime}:\delta(x,x^{\prime})=1}\left\lVert f(x)-f(x^{\prime})\right\rVert_{1}$ where $\left\lVert a\right\rVert_{1}=\sum_{j}|a_{j}|$. Let $R$ have density $g(r)\propto e^{-\alpha|r|/S(f)}$. Then $T(X,R)=f(X)+R$ satisfies differential privacy.

Informative Mechanisms

A challenge in privacy theory is to find $Q_{n}$ that satisfies differential privacy and yet yields datasets $Z$ that preserve information. Informally, a mechanism is informative if it is possible to make precise inferences from the released data $Z_{1},\ldots,Z_{k}$. Whether or not a mechanism is informative will depend on the goals of the inference. From a statistical perspective, we would like to infer $P$ or functionals of $P$ from $Z$. Blum et al. (2008) show that the probability content of some classes of intervals can be estimated accurately while preserving privacy. Their results motivated the current paper. We will assume throughout that the user has access to the sanitized data $Z$ but not the mechanism $Q_{n}$. The question of how a data analyst can use knowledge of $Q_{n}$ to improve inferences is left to future work.

There are many ways to measure the information in $Z$. One way is through distribution functions. Let $F$ denote the cumulative distribution function (cdf) on ${\cal X}$ corresponding to $P$. Thus $F(x)=P(X\in(-\infty,x_{1}]\times\cdots\times(-\infty,x_{r}])$ where $x=(x_{1},\ldots,x_{r})$. Let $\widehat{F}\equiv\widehat{F}_{X}$ denote the empirical distribution function corresponding to $X$ and similarly let $\widehat{F}_{Z}$ denote the empirical distribution function corresponding to $Z$. Let $\rho$ denote any distance measure on distribution functions.

$Q_{n}$ is consistent with respect to $\rho$ if $\rho(F,\widehat{F}_{Z})\stackrel{{\scriptstyle P}}{{\to}}0$. $Q_{n}$ is $\epsilon_{n}$-informative if $\rho(F,\widehat{F}_{Z})=O_{P}(\epsilon_{n})$.

An alternative to requiring $\rho(F,\widehat{F}_{Z})$ to be small is to require $\rho(\widehat{F},\widehat{F}_{Z})$ to be small. Or one could require $Q_{n}(\rho(\widehat{F},\widehat{F}_{Z})>\epsilon|X=x)$ be small for all $x$ as in Blum et al. (2008). These requirements are similar. Indeed, suppose $\rho$ satisfies the triangle inequality and that $\widehat{F}$ is consistent in the $\rho$ distance, that is, $\rho(\widehat{F},F)\stackrel{{\scriptstyle P}}{{\to}}0$. Assume further that $\rho(\widehat{F},F)=O_{P}(\epsilon_{n})$. Then $\rho(F,\widehat{F}_{Z})=O_{P}(\epsilon_{n})$ implies that

Similarly, $\rho(\widehat{F},\widehat{F}_{Z})=O_{P}(\epsilon_{n})$ implies that $\rho(F,\widehat{F}_{Z})=O_{P}(\epsilon_{n})$.

There are many possible choices for $\rho$. We shall mainly focus on the Kolmogorov-Smirnov (KS) distance $\rho(F,G)=\sup_{x}|F(x)-G(x)|$ and the squared $L_{2}$ distance $\rho(F,G)=\int(f(x)-g(x))^{2}dx$ where $f=dF/d\mu$ and $g=dG/d\mu$. However, our results can be carried over to other distances as well.

Before proceeding let us note that we will need some assumptions on $F$ otherwise we cannot have a consistent scheme as shown in the following theorem. The following result — essentially a re-expression of a result in Blum et al. (2008) in our framework — makes this clear.

Suppose that $Q_{n}$ satisfies differential privacy and that $\rho(F,G)=\sup_{x}|F(x)-G(x)|$. Let $F$ be a point mass distribution. Thus $F(y)=I(y\geq x)$ for some point $x\in$. Then $\widehat{F}_{Z}$ is inconsistent, that is, there is a $\delta>0$ such that $\liminf_{n\to\infty}P^{n}(\rho(F,\widehat{F}_{Z})>\delta)>0$.

Sampling From a Histogram

The goal of this section is to give two concrete, simple data release methods that achieve differential privacy. The idea is to draw a random sample from histogram. The first scheme draws observations from a smoothed histogram. The second scheme draws observations from a randomly perturbed histogram. We use the histogram for its familiarity and simplicity and because it is used in applications of differential privacy. We will see that the histogram has to be carefully constructed to ensure differential privacy. We then compare the two schemes by studying the accuracy of the inferences from the released data. We will see that the accuracy depends both on how the histogram is constructed and on what measure of accuracy we use.

Let $L>0$ be a constant and suppose that $p=dP/d\mu\in{\cal P}$ where

is the class of Lipschitz functions. We assume throughout this section that $p\in{\cal P}$. The minimax rate of convergence for density estimators in squared $L_{2}$ distance for ${\cal P}$ is $n^{-2/(2+r)}$ (Scott, 1992).

Let $h=h_{n}$ be a binwidth such that $0<h<1$ and such that $m=1/h^{r}$ is an integer. Partition ${\cal X}$ into $m$ bins $\{B_{1},\ldots,B_{m}\}$ where each bin $B_{j}$ is a cube with sides of length $h$. Let $I(\cdot)$ denote the indicator function. Let $\widehat{f}_{m}$ denote the corresponding histogram estimator on ${\cal X}$, namely,

where $\widehat{p}_{j}=C_{j}/n$ and $C_{j}=\sum_{i=1}^{n}I(X_{i}\in B_{j})$ is the number of observations in $B_{j}$. Recall that $\widehat{f}_{m}$ is a consistent estimator of $p$ if $h=h_{n}\to 0$ and $nh_{n}^{r}\to\infty$. Also, the optimal choice of $m=m_{n}$ for $L_{2}$ error under ${\cal P}$ is $m_{n}\asymp n^{r/(2+r)}$, in which case $\int(p-\widehat{f}_{m})^{2}=O_{P}(n^{-2/(2+r)})$ (Scott, 1992). Here, $a_{n}\asymp b_{n}$ means that both $a_{n}/b_{n}$ and $b_{n}/a_{n}$ are bounded for large $n$.

The first method for generating released data $Z$ from a histogram while achieving differential privacy proceeds as follows. Recall that the sample space is $^{r}$. Fix a constant $0<\delta<1$ and define the smoothed histogram

Let $Z=(Z_{1},\ldots,Z_{k})$ where $Z_{1},\ldots,Z_{k}$ are $k$ iid draws from $\widehat{f}_{m,\delta}(x)$. If

then $\alpha$-differential privacy holds.

Note that for $\delta\to 0$ and $\frac{m}{n\delta}\to 0$, $\log\left(\frac{(1-\delta)m}{n\delta}+1\right)=\frac{m}{n\delta}(1+o(1))\approx\frac{m}{n\delta}$. Thus (6) is approximately the same as requiring

Equation (7) shows an interesting tradeoff between $m$, $k$ and $\delta$. We note that sampling from the usual histogram corresponding to $\delta=0$ does not preserve differential privacy.

Now we give a result that shows how accurate the inferences are in the KS distance using the smoothed histogram sampling scheme.

In this case we see that we have consistency since $\rho(F,\widehat{F}_{Z})=o_{P}(1)$ but the rate is slower than the minimax rate of convergence for density estimators in KS distance, which is $n^{-1/2}$. Now let $\widehat{q}_{j}=\#\{Z_{i}\in B_{j}\}/k$ and

Assume the conditions of the previous theorem. Let $\rho$ be the squared $L_{2}$ distance as defined in (8). Then choosing

Again, we have consistency but the rate is slower than the minimax rate which is $n^{-2/(2+r)}$. (Scott, 1992)

2 Sampling From a Perturbed Histogram

The second method, which we call the sampling from a perturbed histogram, is due to Dwork et. al. (2006). Recall that $C_{j}$ is the number of observations in bin $B_{j}$. Let $D_{j}=C_{j}+\nu_{j}$ where $\nu_{1},\ldots,\nu_{m}$ are independent, identically distributed draws from a Laplace density with mean 0 and variance $8/\alpha^{2}$. Thus the density of $\nu_{j}$ is $g(\nu)=(\alpha/4)e^{-|\nu|\alpha/2}$. Dwork et. al. (2006) show that releasing $D=(D_{1},\ldots,D_{m})$ preserves differential privacy. However, our goal is to release a database $Z=(Z_{1},\ldots,Z_{k})$ rather than just a set of counts. Now define

Since $D$ preserves differential privacy, it follows from Lemma 2.6 that $(\widehat{q}_{1},\ldots,\widehat{q}_{m})$ also preserve differential privacy; Moreover, any sample $Z=(Z_{1},\ldots,Z_{k})$ from $\widetilde{f}(x)=h^{-r}\sum_{j=1}^{m}\widehat{q}_{j}I(x\in B_{j})$ preserve differential privacy for any $k$.

Hence, this method achieves the minimax rate of convergence in $L_{2}$ while the first data release method does not. This suggests that the perturbation method is preferable for the $L_{2}$ distance. The perturbation method does not achieve the minimax rate of convergence in KS distance; in fact, the exponential mechanism based method achieves a better rate as we shown in Section 5 (Theorem 5.4). We examine this method numerically in Section 7.

They show that differential privacy requires $a_{j}+C_{j}\geq k/(e^{\alpha}-1)$ for all $j$. If we take $a_{1}=a_{2}=\cdots=a_{m}$ then this is similar to the first histogram-based data release method we discussed in this section. They also suggest a weakened version of differential privacy.

Exponential Mechanism

In this section we will consider the exponential mechanism in some detail. We’ll derive some general results about accuracy and apply the method to the mean, and to density estimation. Specifically, we will show the following for exponential mechanisms:

Choosing the size $k$ of the released database is delicate. Taking $k$ too large compromises privacy. Taking $k$ too small compromises accuracy.

The accuracy of the exponential scheme can be bounded by a simple formula. This formula has a term that measures how likely it is for a distribution based on sample size $k$, to be in a small ball around the true distribution. In probability theory, this is known as a small ball probability.

The formula can be applied to several examples such as the KS distance, the mean, and nonparametric density estimation using orthogonal series. In each case we can use our results to choose $k$ and to find the rate of convergence of an estimator based on the sanitized data.

In light of Theorem 3.2, we know that some assumptions are needed on $P$. We shall assume throughout this section that $P$ has a bounded density $p$; note that this is a weaker condition than (4).

Recall the exponential mechanism. We draw the vector $Z=(Z_{1},\ldots,Z_{k})$ from $h(z|x)$ where

For KS distance $\Delta_{n,k}\leq\frac{1}{n}$.

This framework is used in Blum et al. (2008). For the rest of this section, assume that $Z=(Z_{1},\ldots,Z_{k})$ are drawn from an exponential mechanism $Q_{n}$.

Let $F$ denote the cumulative distribution function on $\mathcal{X}$ corresponding to $P$. Let $\widehat{G}$ denote the empirical cdf from a sample of size $k$ from $P$, and let

$R(k,\epsilon)$ is called the small ball probability associated with $\rho$.

The following theorem bounds the accuracy of the estimator from the sanitized data by a simple formula involving the small ball probability.

Assume that $P$ has a bounded density $p$, and that there exists $\epsilon_{n}\to 0$ such that

for some $c>1$. Further suppose that $\rho$ satisfies the triangle inequality. Let $Z=(Z_{1},\ldots,Z_{k})$ be drawn from $g_{x}(z)$ given in (9). Then,

Thus, if we can choose $k=k_{n}$ in such a way that the right hand side of (11) goes to 0, then the mechanism is consistent. We now show some examples that satisfy these conditions and we show how to choose $k_{n}$.

Suppose that $P$ has a bounded density $p$ and let $B:=\log\sup_{x}p(x)>0$. Let $Z=(Z_{1},\ldots,Z_{k})$ be drawn from $g_{x}(z)$ given in (9) with $\rho$ being the KS distance. By requiring that $k_{n}\asymp\left(\frac{3\alpha}{B}\right)^{2/3}n^{2/3}$, we have for $\epsilon_{n}=2\left(\frac{B}{3\alpha}\right)^{1/3}n^{-1/3}$, and for $\rho$ being the KS distance,

Note that $\rho(F,\widehat{F}_{Z})$ converges to 0 at a slower rate than $\rho(F,\widehat{F}_{X})$. We thus see that the rate after sanitization is $n^{-1/3}$ which is slower than the optimal rate of $n^{-1/2}$. It is an open question whether this rate can be improved.

2 The Mean

It is interesting to consider what happens when $\rho(F,\widehat{F}_{Z})=||\mu-\overline{Z}||^{2}$ where $\mu=\int xdP(x)$ and $\overline{Z}$ is the sample mean of $Z$. In this case $\Delta\leq r/n$. Thus, $h(u|x)\approx e^{-n||\overline{X}-\overline{Z}||^{2}/(2\alpha)}$ so, approximately, $Z_{1},\ldots,Z_{k}\sim N(\overline{X},k\alpha/n)$. Indeed, it suffices to take $k=1$ in this case since then $\overline{Z}=\overline{X}+O_{P}(1/\sqrt{n})$. Thus $\overline{Z}$ converges at the same rate as $\overline{X}$. This is not surprising: preserving a single piece of information requires a database of size $k=1$.

Orthogonal Series Density Estimation

In this section, we develop an exponential scheme based on density estimation and we compare it to the perturbation approach. For simplicity we take $r=1$. Let $\{1,\psi_{1},\psi_{2},\ldots,\}$ be an orthonormal basis for $L_{2}(0,1)=\{f:\ \int_{0}^{1}f^{2}(x)dx<\infty\}$ and assume that $p\in L_{2}(0,1)$. Hence

We assume that the basis functions are uniformly bounded so that

Let ${\cal B}(\gamma,C)$ denote the Sobolev ellipsoid

The minimax rate of convergence in $L_{2}$ norm for ${\cal P}(\gamma,C)$ is $n^{-2\gamma/(2\gamma+1)}$ (Efromovich, 1999). Thus

for some $c_{1}>0$. This rate is achieved by the estimator

where $m_{n}=n^{1/(2\gamma+1)}$ and $\widehat{\beta}_{j}=n^{-1}\sum_{i=1}^{n}\psi_{j}(X_{i}).$ See Efromovich (1999).

Under the above scheme we have $\Delta\leq\frac{2c_{0}^{2}m_{n}}{n}$ for $c_{0}$ as defined in (13). Hence,

Let $Z=(Z_{1},\ldots,Z_{k})$ be drawn from $g_{x}(z)$ given in (17). Assume that $\gamma>1$. If we choose $k\asymp\sqrt{n}$ then

We conclude that the sanitized estimator converges at a slower rate than the minimax rate. Now we compare this to the perturbation approach. Let $Z=(Z_{1},\ldots,Z_{k})$ be an iid sample from

where $\nu_{1},\ldots,\nu_{m}$ are iid draws from a Laplace distribution with density $g(\nu)=(n\alpha/(2c_{0}m))e^{-n\alpha|\nu|/(c_{0}m)}$. Thus, i the notation of 2.6, $R=(\nu_{1},\ldots,\nu_{m})$. It follows from Lemma 2.6 that, for any $k$, this preserves differential privacy. If $\widehat{q}(x)<0$ for any $x$ then we replace $\widehat{q}$ by $\widehat{q}(x)I(\widehat{q}(x)>0)/\int\widehat{q}(s)I(\widehat{q}(s)>0)ds$ as in Hall and Murison (1993).

Let $Z=(Z_{1},\ldots,Z_{k})$ be drawn from $\widehat{q}$. Assume that $\gamma>1$. If we choose $k\geq n$, then

where $\widehat{p}_{Z}$ is the orthogonal series density estimator based on $Z$.

Hence, again, the perturbation technique achieves the minimax rate of convergence and so appears to be superior to the exponential mechanism. We do not know if this is because the exponential mechanism is inherently less accurate, or if our bounds for the exponential mechanism are not tight enough.

Example

Here we consider a small simulation study to see the effect of perturbation on accuracy. We focus on the histogram perturbation method with $r=1$. We take the true density of $X$ to be a Beta(10,10) density. We considered sample sizes $n=100$ and $n=1,000$ and privacy levels $\alpha=0.1$, and $\alpha=0.01$. We take $\rho$ to be squared error distance. Figure 1 shows the results of 1,000 simulations for various numbers of bins $m$.

As expected, smaller values of $\alpha$ induce a larger information loss which manifests itself as a larger mean squared error. Despite the fact that the perturbed histogram achieves the minimax rate, the error is substantially inflated by the perturbation. This means that the constants in the risk are important, not just the rate. Also, the risk of the sanitized histograms is much more sensitive to the choice of the number of cells than the original histogram is.

We repeated the simulations with a bimodal density, namely, $p(x)$ being an equal mixture of a Beta(10,3) density and Beta(3,10) density. The results turned out to be nearly identical to those above.

Conclusion

Differential privacy is an important type of privacy guarantee when releasing data. Our goal has been to present the idea in statistical language and then to show that loss functions based on distributions and densities can be useful for comparing privacy mechanisms.

We have seen that sampling from a histogram leads to differential privacy as long as either the histogram is shifted away from 0 by a factor $\delta$ or if the cells are perturbed appropriately. The latter method achieves a faster rate of convergence in $L_{2}$ distance. But, the simulation showed that the risk can nonetheless be quite large. This suggests that more work is needed to get precise finite sample risk bounds. Also, the choice of the smoothing parameter (number of cells in the histogram) has a larger effect on the sanitized histogram than on the original histogram.

We also studied the exponential mechanism. Here we derived a formula for assessing the accuracy of the method. The formula involves small ball probabilities. As far as we know, the connection between differential privacy and small ball probabilities has not been observed before.

Minimaxity is desirable for any statistical procedure. We have seen that in some cases the minimax rate is achieved and in some cases it is not. We do not yet have a complete minimax theory for differential privacy and this is the focus of our current work. We close with some open questions.

When is it possible for $\rho(F,\widehat{F}_{Z})$ to have the same rate as $\rho(F,\widehat{F}_{X})$?

When adaptive minimax methods are used, such as adapting to $\gamma$ in Section 6 or when using wavelet estimation methods, is some form of adaptivity preserved after sanitization?

Many statistical methods involve some sort of risk minimization. A example is choosing a bandwidth by cross-validation. What is the effect of sanitization on these procedures?

Are there other, better methods of sanitization that preserve differential privacy?

Proofs

Without loss of generality take $i=1$. Let $M_{0}(B)$ $=$ $\int Q(B|s,x_{2},\ldots,x_{n})$ $dP(x_{2},\ldots,x_{n})$ and $M_{1}(B)=\int Q(B|t,x_{2},\ldots,x_{n})dP(x_{2},\ldots,x_{n})$. By the Neyman-Pearson lemma, the highest power test is to reject $H_{0}$ when $U>u$ where $U(z)=(dM_{1}/dM_{0})(z)$ and $u$ is chosen so that $\int I(U(z)>u)dM_{0}(z)\leq\gamma$. Since $(s,x_{2},\ldots,x_{n})$ and $(t,x_{2},\ldots,x_{n})$ differ in only one coordinate, $M_{1}(B)\leq e^{\alpha}M_{0}(B)$ and so the power is $M_{1}(U>u)\leq e^{\alpha}M_{0}(U>u)\leq\gamma e^{\alpha}$. $\;\;\scriptstyle\Box$

2 Proof of Lemma 2.6

For the second part, let $Z=(Z_{1},\ldots,Z_{k})$ and note that $Z$ is independent of $X$ given $T(X,R)$. Let $H$ be the distribution of $T(X,R)$. Hence,

3 Proof of Theorem 3.2

Let $v>0$ be any point in $$such that$Q_{n}(Z=v|X=X_{(0)})=0$. Let$X_{(1)}=\{v,0,\ldots,0\}$,$X_{(2)}=\{v,v,0,\ldots,0\}$, …,$X_{(n)}=\{v,v,\ldots,v\}$. By assumption,$Q_{n}(Z=X_{(j)}|X=X_{(0)})=0$for all$j\geq 1$. Differential privacy implies that$Q_{n}(Z=X_{(j)}|X=X_{(1)})=0$for all$j\geq 1$. Applying differential privacy again implies that$Q_{n}(Z=X_{(j)}|X=X_{(2)})=0$for all$j\geq 1$. Continuing this way, we conclude that$Q_{n}(Z=X_{(j)}|X=X_{(n)})=0$for all$j\geq 1$.

Next let $P=\delta_{v}$. Arguing as before, we know that $Q_{n}(\widehat{F}_{Z}(v)<1-\delta|X=X_{(n)})\to 0$. And since $F(v-)=0$ we also have that $Q_{n}(\widehat{F}_{Z}(v-)>\delta|X=X_{(n)})\to 0$. Here, $F(v-)=\lim_{i\to\infty}F(v_{i})$ where $v_{1}<v_{2}<\ldots$ and $v_{i}\to v$. Hence, for $j/n>1-\delta$, $Q_{n}(Z=X_{(j)}|X=X_{(n)})>0$ which is a contradiction. $\;\;\scriptstyle\Box$

4 Proof of Theorem 4.1

Suppose that $X$ differs from $Y$ in at most one observation. Let $\widehat{f}$ denote the perturbed histogram $\widehat{f}_{m,\delta}$ based on $X$ and let $\widehat{g}_{m,\delta}$ denote the histogram based on $Y$, such that $X$ and $Y$ differ in one entry. We also use $\widehat{p}_{j}(X)$ and $\widehat{p}_{j}(Y)$ for cell proportions. Note that $|\widehat{p}_{j}(X)-\widehat{p}_{j}(Y)|<1/n$ by definition. It is clear that the maximum density ratio for a single draw $x_{i}$, or all $i$, occurs in one bin $B_{j}$. Now consider ${\bf x}=(x_{1},\ldots,x_{i})$ such that for all $i=1,\ldots,k$, we have $x_{i}\in B_{j}\subset^{r}$ and the following bounds.

Let $\widehat{p}_{j}(Y)=0$; then in order to maximize $\widehat{f}({\bf x})/\widehat{g}({\bf x})$, we let $\widehat{p}_{j}(X)=1/n$ and obtain

Otherwise, we let $\widehat{p}_{j}(Y)\geq 1/n$, (as by definition of $\widehat{p}_{j}$, it takes $z/n$ for non-negative integers $z$) and let $\widehat{p}_{j}(X)=\widehat{p}_{j}(Y)\pm 1/n$. Now it is clear that in order to maximize the density ratio at $x$, we may need to reverse the role of $X$ and $Y$,

where the maximum is achieved when $\widehat{p}_{j}(Y)=1/n$ and $\widehat{p}_{j}(X)=0$, given a fixed set of parameters $m,n,\delta$.

and the theorem holds. $\;\;\scriptstyle\Box$

5 Proof of Theorem 4.2

The Vapnik-Chervonenkis dimension of the class of sets of the form $\{(-\infty,x_{1}]\times\cdots\times(-\infty,x_{r}]$ is $r$ and so by the standard Vapnik-Chervonenkis bound, we have for $\epsilon>0$ that

By the triangle inequality, we have for all $x\in^{r}$,

where the last step follows from the VC bound as in (18) for $F_{m}(x)$.

Next we bound $\sup_{x\in^{r}}\left\lvert F_{m}(x)-F(x)\right\rvert$. Now $F(x)=P(A)$ where $A=\{(s_{1},\ldots,s_{r}):\ s_{i}\leq x_{i},i=1,\ldots,r\}$. If $x=(j_{1}h,\ldots,j_{r}h)$ for some integers $j_{1},\ldots,j_{r}$ then $F(x)-F_{m}(x)=0$. For $x$ not of this form, let $\widetilde{x}=(j_{1}h,\ldots,j_{r}h)$ where $j_{i}=\lfloor x_{i}/h\rfloor$. Let $R=\{(s_{1},\ldots,s_{r}):\ s_{i}\leq\widetilde{x}_{i},i=1,\ldots,r\}$. So

where $P_{m}(B)=\int_{B}dF_{m}(u)$ and the set $A\setminus R$ intersects at most $rh/h^{r}$ number of cubes in $\{B_{1},\ldots,B_{m}\}$, given that ${\rm Vol}(A\setminus R)\leq 1-(1-h)^{r}\leq rh$. Now by the Lipschitz condition (4), we have $\sup_{x\in^{r}}|p(x)-\bar{f}_{m}(x)|\leq Lh\sqrt{r}$ and

6 Proof of Theorem 4.3

Let $\widehat{f}_{Z}$ be the histogram based on $Z$ as in (8). Then

where $\preceq$ means less than, up to constants. Hence,

where $R_{m}$ is the usual $L_{2}$ risk of a histogram under the Lipschitz condition (4), namely, $m^{-2/r}+m/n$. Conditional on $X$, $\widehat{f}_{Z}$ is an unbiased estimate of $\widehat{f}_{m}$ with integrated variance $m/k$. So,

7 Proof of Theorem 4.4

(1) Note that $p-\widehat{f}_{Z}=p-\widetilde{f}+\widetilde{f}-\widehat{f}_{Z}=p-\widetilde{f}+O_{P}\left(\frac{m}{k}\right).$ When $k\geq n$, the latter error is lower order than the other terms and may be ignored. Now,

The expected value of the first term is the usual risk, namely, $O(m^{-2/r}+m/n)$.

For the second term, we proceed as follows. Let $\widehat{p}_{j}=C_{j}/n$ and

almost surely, for all large $n$. We have

where $R_{n}=(\sum_{s=1}^{m}(C_{s}+\nu_{s})_{+})/n$. Now

where $M=\max\{|\nu_{1}|,\ldots,|\nu_{m}|\}$. Let $A>0$. The density for $\nu_{j}$ has the form $f(\nu)=(\beta/2)e^{-\beta|\nu|}$. So,

By choosing $A$ large enough we have that $M<A\log m$ a.s. for large $n$, by the Borel-Cantelli lemma. Therefore,

Therefore, $1/R_{n}=(1+O(m\log m/n))$ and thus

Next we claim that $\widehat{p}_{j}=O(1/m)$ a.s. To see this, note that $p_{j}\leq C/m$, by definition of $C$: $1\leq C=\sup_{x}p(x)<\infty$. Hence, by Bernstein’s inequality,

for all $n\geq 16m\log n/3C$; Thus $\widehat{p}_{j}=O(1/m)$ a.s. for all large $n$. Thus, $\widehat{q}_{j}-\widehat{p}_{j}=O(\log m/n)$ almost surely for all large $n$. Hence,

for $n\geq m\log^{2}m$. This is the usual risk. Hence, we can choose $m\asymp n^{r/(2+r)}$ to achieve risk $n^{-2/(2+r)}$ for all $n$ large enough.

(2) Let $\widehat{F}_{m}$ be the cdf based on the original histogram and let $\widetilde{F}_{m}$ be the cdf based on the perturbed histogram. We have

Since we may take $k$ as large as we like, we can make the last term arbitrarily small. From (22),

Let $\widehat{f}(x)=h^{-r}\sum_{j=1}^{m}\widehat{p}_{j}I(x\in B_{j})$ and Let $\widetilde{f}(x)=h^{-r}\sum_{j=1}^{m}\widehat{q}_{j}I(x\in B_{j})$. Let $x^{\prime}=(u_{1}h,\ldots,u_{r}h)$ where $u_{i}=\lceil x_{i}/h\rceil,\forall i=1,\ldots,r$. Recall that $B_{1},\ldots,B_{m}$ are the $m$ bins of $\mathcal{X}$ with sides of length of $h$. Let $B_{x}$ denote the cube with the left-most corner being and the right-most corner being $x$. Then for all $x$, we have

where we use the fact that there are at most $m$ cubes. Hence,

where we use the fact that $\max_{j}|\widehat{p}_{j}-\widehat{q}_{j}|=O(\log m/n)$ a.s. So,

Hence for $r=1$, the rate is $O\left(\sqrt{\frac{\log n}{n}}\right)$. For $r\geq 2$, the rate is dominated by the first term inside $O()$, and hence the rate is $O\left(\log n\times n^{-2/(2+r)}\right)$. $\;\;\scriptstyle\Box$

8 Proof of Theorem 5.3

Let B_{\epsilon}=\Bigl{\{}u=(u_{1},\ldots,u_{k}):\ \rho(F,\widehat{F}_{u})\leq\epsilon\Bigr{\}} where $\widehat{F}_{u}$ is the empirical distribution based on $u=(u_{1},\ldots,u_{k})\in{\cal X}^{k}$. Also, let $A_{n}=\{\rho(\widehat{F}_{X},F)\leq\epsilon_{n}/16\}$. For notational simplicity set $\Delta=\Delta_{n,k}$. Then

By the triangle inequality $\rho(\widehat{F}_{u},\widehat{F}_{X})\geq\rho(\widehat{F}_{u},F)-\rho(\widehat{F}_{X},F)$. Then,

By the triangle inequality, we also have $\rho(\widehat{F}_{u},\widehat{F}_{X})\leq\rho(\widehat{F}_{u},F)+\rho(\widehat{F}_{X},F)$ and

where $\widehat{G}$ is the empirical cdf from a sample of size $k$ drawn from $P$. Thus we have

Thus the theorem holds. $\;\;\scriptstyle\Box$

9 Proof of Lemma 5.1

Proof of Lemma 5.1. We start with KS, By the triangle inequality, we have for all $z\in{\mathcal{X}}^{k}$ and for all $x,y\in{\mathcal{X}}^{n}$,

Notice that changing one entry in $x$ will change $\widehat{F}_{x}(t)$ by at most $\frac{1}{n}$ at any $t$ by definition, that is,

Thus the conclusion holds for the KS-distance. $\;\;\scriptstyle\Box$

10 Proof of Theorem 5.4

We need the following small ball result; see Li and Shao (2001).

Let $r\geq 3$, and $\{X_{t},t\in^{r}\}$ be the Brownian sheet. Then there exists $0<C_{r}<\infty$ such that for all $0<\epsilon\leq 1$,

where $C_{r}$ depends only on $r$. The same bound holds for a Brownian bridge.

Proof of theorem 5.4. The Vapnik-Chervonenkis dimension of the class of sets of the form $\{(-\infty,x_{1}]\times\cdots\times(-\infty,x_{r}]$ is $r$ and so by the standard Vapnik-Chervonenkis bound, we have for $\epsilon_{n},k_{n}$ as specified in the theorem statement,

for some constants $c_{5},c_{6},c_{7},C_{2}>0$ for $n$ large enough. Thus (10) holds. Now we compute the small ball probability. Note that $\sqrt{k}(\widehat{F}_{k}-F)$ converges to a Brownian bridge $B_{k}$ on $^{r}$. More precisely, from Csörgő and Révész (1975) there exist a sequence of Brownian bridges $B_{k}$ such that

where $\gamma=1/(2(r+1))$. It is clear that the RHS of (25) is $o(1)$ a.s. given a fixed $r$. Hence we have for $k=k_{n}$ and $\epsilon_{n}$ as chosen in the theorem statement, and for all $\epsilon\geq\epsilon_{n}$, it holds that

for all large $n$, where (26) follows from (25) and (27) holds given that $\sqrt{k}\epsilon\geq\sqrt{k_{n}}\epsilon_{n}\geq c$ for some constant $c>1/2$ due to our choice of $k_{n}$ and $\epsilon_{n}$. Also, $\Delta\leq 1/n$ for KS distance. Hence, by Theorem 5.3 and (24), we have for $B=\log\sup_{x}p(x)>0$,

for some constants $C_{0},C_{1},C_{2}$ and $C_{3}$, where (28) holds when we take w.l.o.g. $k_{n}=\frac{1}{16}\left(\frac{3\alpha}{B}\right)^{2/3}n^{2/3}$ and $\epsilon_{n}\geq 2\left(\frac{B}{3\alpha}\right)^{1/3}n^{-1/3}$, given that $\epsilon_{n}\geq 2\left(\frac{B}{3\alpha}\right)^{1/3}n^{-1/3}=\frac{32k_{n}B}{3n\alpha}$ and hence $\frac{3\alpha\epsilon_{n}}{16}\geq\frac{2Bk_{n}}{n}$. Thus the result follows. $\;\;\scriptstyle\Box$

The constants taken in the proof are arbitrary; indeed, when we take $k_{n}=C_{4}\left(\frac{3\alpha}{B}\right)^{2/3}n^{2/3}$ and $\epsilon_{n}=32C_{4}\left(\frac{B}{3\alpha}\right)^{1/3}n^{-1/3}$ with some constant $C_{4}\geq 1/16$, (28) will hold with slightly different constants $C_{2},C_{3}$. For $k_{n}$ and $\epsilon_{n}$ as chosen above, it holds that $\sqrt{k_{n}}\epsilon_{n}\asymp 1$.