Revisiting Differentially Private Hypothesis Tests for Categorical Data

Introduction

Hypothesis testing is an important aspect of statistical analysis and data mining. Because of the possibility that the results of an analysis could leak private information (Homer et al. 2008), various research communities such as statistics, official statistics, and computer science have studied how to incorporate statistical disclosure control to prevent such leakage.

A relatively recent development is a computer science privacy definition known as $\epsilon$-differential privacy (Dwork et al. 2006). Statistical disclosure control (SDC) techniques that satisfy differential privacy possess a variety of appealing mathematical guarantees on the privacy of individuals in the data. For instance, the output produced by the SDC techniques is randomized and its probability distribution is barely affected by the inclusion of any individual’s record in the data (Dwork et al. 2006). Furthermore, if data records are independent, it limits any Bayesian inference about an individual: the ratio of posterior odds to prior odds is guaranteed to be bounded by $e^{\epsilon}$ (Kifer and Machanavajjhala 2014) where $\epsilon$ is a privacy parameter. This guarantee even holds if an attacker has access to all but one of the records in the data.

Recent years have seen a rapid development of differentially private SDC techniques for fitting various models to data. However, hypothesis testing is largely unexplored to the extent that existing methods can only be used reliably in rare circumstances. Our paper addresses these limitations, but first let us examine what the difficulties are.

Now let us consider problems raised by earlier applications of differential privacy to hypothesis testing (Johnson and Shmatikov 2013; Uhler et al. 2013; Yu et al. 2014).

Suppose we collected the voter data in Fig. 1. One may be interested in determining if it provides statistical evidence that voting behavior and gender are not independent.

In the classical (non-private) setting, this question is typically answered by performing chi-squared ($\chi^{2}$) or likelihood ratio tests (Ferguson 1996) of independence. This would involve computing the $\chi^{2}$ or likelihood ratio test statistics and taking advantage of theoretical results stating that for such $2\times 2$ tables, under the null hypothesis of independence, these test statistics are asymptotically distributed as chi-squared random variables with 1 degree of freedom (Ferguson 1996). The $p$-value is simply the probability that such a chi-squared random variable would be larger than the actual test statistic. For example, the likelihood ratio statistic for Fig. 1a is $2.918$ with a corresponding $p$-value of $0.0876$, which is generally not considered strong enough to rule out independence. Note that exact tests and permutation tests are other alternatives, but our approach to hypothesis testing with differential privacy extends the asymptotic approaches.

To achieve $\epsilon$-differential privacy, Johnson and Shmatikov 2013 propose to add independent Laplace$(b)$ noise with density $f(x;b)=\frac{1}{2b}e^{-|x|/b}$ and $b=2/\epsilon$ to each cell of the table. As an example, when we added this noise to Fig. 1a, we obtained Fig. 1b. The next step (Johnson and Shmatikov 2013) is to simply run the noisy table through off-the-shelf statistical software (which is unaware of this added noise). Intuitively, this seems a bit dangerous as the point of hypothesis testing is to determine how an analysis is affected by noise in the observed data. On the other hand, theoretical arguments (Johnson and Shmatikov 2013) showed that test statistics computed from the noisy tables (in place of the original tables) still asymptotically have a chi-squared distribution with 1 degree of freedom. What happens in practice? The $p$-values produced by this method are extremely biased and will often lead to false conclusions. For example, the likelihood ratio statistic computed from the noisy table in Fig. 1b is equal to $6.939$ and off-the-shelf software would return an estimated $p$-value of $0.0084$, which is often considered statistically significant and clearly contradicts the likelihood ratio test on the original data. While this is just one example from one table, our experiments in Section 5.1 empirically confirm this trend. This mismatch between theoretical arguments and empirical results also points out the need for a more reliable privacy-preserving statistical theory.

The unreliability of the algorithm proposed by Johnson and Shmatikov 2013 was noticed by Uhler et al. 2013, they proposed an output perturbation method (Uhler et al. 2013; Yu et al. 2014): compute the chi-squared statistic on the original data (here it is $2.916$), determine a quantity called the sensitivity $S$ (the worst-case change in chi-squared values due to the alteration of one individual’s data), add Laplace$(b)$ noise with $b=S/\epsilon$, and then use a different asymptotic distribution for computing the $p$-value. For $2\times 2$ tables with $n=1,000$ (as in our example), the sensitivity $S$ is at least $500$ (achieved by the worst-case tables $\left(\begin{smallmatrix}1&0\\ 0&999\end{smallmatrix}\right)$ and $\left(\begin{smallmatrix}1&1\\ 0&998\end{smallmatrix}\right)$ with $\chi^{2}$ values $1000$ and $499.5$, respectively). This noise has standard deviation at least $500\sqrt{2}/\epsilon$. When such noise is added to the chi-squared statistic of the original table $(i.e.,2.916)$, it completely overwhelms the original value. As a result, Uhler et al. 2013 and Yu et al. 2014 identified special cases where the amount of noise they need to add for privacy can be substantially reduced.

In this paper, similar to Johnson and Shmatikov 2013, we first add noise to the input data before computing the test statistics. However, to get practical tests that work well on small and large datasets, we need to modify the $p$-value computation. First, we show how to appropriately adjust private statistical theory so that asymptotic results become a good approximation of what happens in practice. Then we derive the asymptotic distributions under this modified methodology for likelihood ratio and chi-squared tests for goodness-of-fit, sample proportions, and independence. We use these asymptotic distributions to produce $p$-values. Although more computationally expensive, we provide an extensive experimental evaluation on real datasets that shows our approach provides much more reliable $p$-values. We note that independent work by Gaboardi et al. 2016 considers chi-squared tests under differential privacy. We elaborate on the differences in Section 3 (related work).

We introduce notations and terminologies in Section 2, discuss related work in Section 3, and present our various statistical tests on privacy-enhanced tables in Section 4. Experiments appear in Section 5 and conclusions in Section 6. For completeness, proofs of our results appear in the online appendices.

Preliminaries and Notations

In this section, we introduce notations and review the necessary prerequisites.

Notations such as $T[\cdot]$ and $S[\cdot]$ indicate one-dimensional tables of counts. The $i^{\text{th}}$ entry of $T[\cdot]$ is denoted by $T[i]$.

Similarly, $T[\cdot,\cdot]$ is a two-dimensional table where $T[i,j]$ is the $(i,j)^{\text{th}}$ entry. We will use the standard shorthand $T[\bullet,j]=\sum_{i}T[i,j]$ and $T[i,\bullet]=\sum_{j}T[i,j]$, as well as $T[\bullet,\bullet]=\sum_{i}\sum_{j}T[i,j]$.

The size of a table ($T[\cdot]$ or $T[\cdot,\cdot]$) is the sum of its counts.

We consider the following types of statistical hypothesis tests:

Goodness of fit: given a table $T[\cdot]$ of size $n$ and a probability vector $\theta$, the null hypothesis is that $T[\cdot]$ was sampled from a Multinomial$(n,\theta)$ distribution.

Sample proportions: given tables $T[\cdot]$ of size $n_{1}$ and $S[\cdot]$ of size $n_{2}$, the null hypothesis is that they are samples from the same distribution. That is, $T[\cdot]\sim$Multinomial$(n_{1},\theta)$ and $S[\cdot]\sim$Multinomial$(n_{2},\theta)$, for some unknown $\theta$.

Independence: given a table $T[\cdot,\cdot]$ of size $n$, the null hypothesis is that the rows and columns are independent.

These hypotheses are commonly tested in the following ways:

Compute either the likelihood ratio statistic LR or chi-squared statistic $\chi^{2}$ as follows:

where $E[i]=n\theta[i]$ are estimated expected null hypothesis cell counts and $r$ is the number of cells in $T$. Under the null hypothesis, the asymptotic distribution of both $LR$ and $\chi^{2}$ is a chi-squared random variable with $r-1$ degrees of freedom. Thus the $p$-value can be approximated as the probability that the chi-squared random variable exceeds the chosen test statistic computed from $T$. Alternatively, we can sample many tables from the Multinomial$(n,\theta)$ distribution and compute the test statistic of each one. The $p$-value could then be approximated as the fraction of sampled tables whose test statistic is greater than or equal to the test statistic of the actual table.

Given $T[\cdot]$ of size $n_{1}$ and $S[\cdot]$ of size $n_{2}$, compute $LR$ or $\chi^{2}$ as follows:

where $E_{1}[i]=n_{1}(S[i]+T[i])/(n_{1}+n_{2})$ and $E_{2}[i]=n_{2}(S[i]+T[i])/(n_{1}+n_{2})$ are estimated expected null hypothesis cell counts, and $r$ is the number of cells in $T$ and $S$. Under the null hypothesis, the asymptotic distribution of both $LR$ and $\chi^{2}$ is a chi-squared random variable (r.v.) with $r-1$ degrees of freedom. We approximate the $p$-value as the probability that the chi-squared r.v. exceeds the chosen test statistic computed from $T$ and $S$.

Given table $T[\cdot,\cdot]$ with $r$ rows and $c$ columns, compute LR or $\chi^{2}$ as:

where $E[i,j]=T[i,\bullet]T[\bullet,j]/T[\bullet,\bullet]$ are estimated expected null hypothesis cell counts. Under the null hypothesis, the asymptotic distribution of both $LR$ and $\chi^{2}$ is a chi-squared random variable with $(r-1)(c-1)$ degrees of freedom. The $p$-value can be approximated as the probability that the chi-squared random variable exceeds the chosen test statistic computed from $T$.

A low $p$-value (say, 0.01, depending on the application) indicates strong evidence against the null hypothesis while a larger $p$-value indicates absence of evidence. As can be observed from Definitions 1, 2, 3, the likelihood ratio and chi-squared tests are asymptotically equivalent (Ferguson 1996). However, as we explain in Section 4, differences will emerge due to privacy constraints.

2 Review of Differential Privacy

Differential privacy (Dwork et al. 2006) is a set of restrictions on statistical disclosure control algorithms and guarantees that any data associated with an individual will have little impact on the result of the computation.

A randomized algorithm $\randalg$ satisfies $\epsilon$-differential privacy if for all contingency tables $T$ and $T^{\prime}$ that are derived from datasets that differ on the value of one record, and for all $V\subseteq\range(\randalg)$,

This definition means that if we modify any arbitrary record before tabulating our data into a table, the probability of generating any output is changed by a factor of at most $e^{\epsilon}$. When $\epsilon$ is small (i.e. close to $0$), the probabilities are barely affected. This severely limits the ability of an attacker to make inferences about any record in the data. For additional interpretations of the privacy guarantees of differential privacy and suggestions for setting the privacy parameter $\epsilon$, see Dwork 2006, Kifer and Machanavajjhala 2014 and Machanavajjhala and Kifer 2015.

There are many ways of constructing SDC algorithms that satisfy differential privacy. One of the simplest methods is called the Laplace Mechanism (Dwork et al. 2006). It relies on a concept called sensitivity and adds noise scaled by the sensitivity value.

Let $h$ be a function over contingency tables (the output of $h$ can be either a scalar or a vector). The sensitivity of $h$, denoted by $\sensitivity(h)$, is defined as $\sensitivity(h)=\max_{T,T^{\prime}}\|h(T)-h(T^{\prime})\|_{1}$, where the maximum is over all pairs of tables that are derived from datasets differing on the value of one record.

Intuitively, the sensitivity of a function $h$ measures the largest possible change that $h$ can experience as a result of modifying one record in some underlying dataset.

Given a (vector or scalar valued) function $h$, privacy parameter $\epsilon$, contingency table $T$, and upper bound $\mathcal{S}$ on the sensitivity $\sensitivity(h)$, the Laplace mechanism adds independent Laplace($\mathcal{S}/\epsilon$) random variables (with density $f(x)=\frac{\epsilon}{2\mathcal{S}}e^{-\epsilon|x|/\mathcal{S}}$) to each component of $h(T)$.

Related Work

Genome-wide association studies (GWAS) use statistical tests for finding associations between diseases and single-nucleotide polymorphisms (SNPs). The need for privacy became evident after Homer et al. 2008 raised the possibility of identifying individual participants in GWAS based on published SNP data. With GWAS in mind, Johnson and Shmatikov 2013 proposed differentially private algorithms for independence testing (e.g., $\chi^{2}$-tests) using input perturbation as discussed in Example 1.1. This method often produces unreliable conclusions except for extreme data sizes, as noted by Uhler et al. 2013 and our own experiments. Similar types of negative results produced by running off-the-shelf statistical analyses after input perturbation were reported by Vu and Slavkovic 2009 and Fienberg et al. 2010. Thus, Uhler et al. 2013 instead proposed computing the true $\chi^{2}$ statistic, adding noise to it, and then adjusting the asymptotic distribution used to compute $p$-values. Their method was limited to $3\times 2$ contingency tables where each of the 2 columns added up to $n/2$. Yu et al. 2014 later removed these restrictions but still required the column-sums to be released exactly (i.e., in a non-private way). In both cases, under the null hypothesis of independence, collecting more data will not result in convergence to the non-private analysis over the original data. Independent work by Gaboardi et al. 2016 follow earlier drafts of our work (Wang et al. 2015). They consider chi-squared tests for goodness-of-fit and independence under the differential privacy model and also a weaker model known as approximate differential privacy (Nissim et al. 2007; Machanavajjhala and Kifer 2015). There are several key distinctions between our work. First, we evaluate our methods on a variety of real datasets (they only consider synthetic data). Second, our formalization of a more accurate asymptotic regime provides asymptotic guarantees on the level of our tests. Without such a formalization, Gaboardi et al. 2016 need synthetic data for empirical validation of Type 1 error (we provide such an empirical evaluation for our tests as well). We additionally consider the test of sample proportions and show a modified equivalence between chi-squared tests and likelihood ratio tests under the new asymptotic regime. Finally, our methods work for any $0$-mean finite variance noise distribution that is added to data (we specialize the discussion to Laplace noise, but any such distribution can be used in its place).

In a general setting, Smith 2011 studied statistical estimators that are known to have asymptotically normal distributions and provided differentially-private versions of those estimators that are also asymptotically normal. As with the tests proposed by Johnson and Shmatikov 2013 (discussed in Example 1.1), very large data sizes are needed to observe approximate normality. Differential privacy has also been applied to other statistical tasks such as computing commonly used robust statistical estimators (Dwork and Lei 2009) and computing private M-estimators (Lei 2011). Chaudhuri and Hsu 2012 established a formal connection between differential privacy and robust statistics by deriving convergence rates in terms of a concept called gross error sensitivity. Dwork et al. 2015 presented a framework for controlling the false discovery rate of a large sequence of hypothesis tests. The method relies on injecting noise directly into $p$-values, which removes their guarantee that they must be (approximately) uniformly distributed under the null hypothesis. Specific instantiations of the framework for various statistical tests are not given and its empirical performance is unknown. Wasserman and Zhou 2010 studied rates of convergence between true distributions and differentially private estimates of distributions. They found that the provable convergence rates under differential privacy were often slower than in the non-private case.

Private Hypothesis Testing

We consider the following setting: a data owner has a table of counts (e.g., $T[\cdot]$ or $T[\cdot,\cdot]$) and obtains noisy tables (e.g., $\widetilde{T}[\cdot]$, $\widetilde{T}[\cdot,\cdot]$) by adding independent $0$-mean noise with finite variance to each table cell. The table size $n_{0}$, the density function of the noise, and the noisy tables themselves are publicly released. If the noise follows a Laplace$(2/\epsilon)$ distribution, then this output satisfies $\epsilon$-differential privacy. Our goal is to conduct goodness-of-fit, sample proportions, and independence tests using such noisy data. We feel this is a natural setting as such releases of noisy counts do not force the end-users into any particular analysis task. We first justify our chosen asymptotic regime (Section 4.1), present the modified equivalence between chi-squared and likelihood ratio tests when computed over noisy data (Section 4.2) then derive asymptotic distributions for our tests (Section 4.3). We use these distributions for $p$-value computation in Section 4.4 and then evaluate empirical performance in Section 5.

When discussing asymptotics, it is important to distinguish between the actual table that was collected, let us call it $T_{0}$, with sample size $n_{0}$ and the hypothetical data $T$ with sample size $n$ that goes to infinity. The key to asymptotically approximating the null distribution of a test statistic in the classical (non-private) case is the Central Limit Theorem (CLT), which, for example, states that as $n\rightarrow\infty$, $\frac{T-np_{1}}{\sqrt{n}}\rightarrow N(0,p_{1}(1-p_{1}))$ in distribution (where $np_{1}$ is the expected value of $T$ and $N(0,\sigma^{2})$ is the zero-mean Gaussian with variance $\sigma^{2}$). In practice, this Gaussian approximation works well even if $n$ is not large. In the private setting, the data collector is planning to release $T_{0}+V_{\epsilon}$ where, for example, $V_{\epsilon}$ is a table of independent Laplace$(2/\epsilon)$ random variables. One way to analyze it asymptotically is to replace $T_{0}$ with $T$ (and then let $n\rightarrow\infty$):

The first term on the right hand side is often well-approximated by the Gaussian distribution. As $n\rightarrow\infty$, the second term converges to $0$ in probability. However, we should not use $0$ as a finite-sample approximation to this term – it is only accurate when $n$ is very large (in particular, $\sqrt{n}$ must be very large compared to the standard deviation of $V_{\epsilon}$). As discussed in Section 1, for many data sets of interest, this is not the case and so the extra noise due to SDC cannot be ignored.

Our proposed solution is based on the following idea. We view the first term in Equation 7 as the signal and the second term as the noise. As $n\rightarrow\infty$, we want to maintain the ratio of variance in the first term vs. variance in the second term as in the actual data $T_{0}$. Thus we tie the standard deviation of the added noise to $\sqrt{n}$ as follows:

where $\kappa$ is a constant equal to 1/\sqrt{{\color[rgb]{0,0,0}n_{0}}}. In this case, $\lim\limits_{n\rightarrow\infty}(\widetilde{T}-np_{1})/\sqrt{n}=N(0,p_{1}(1-p_{1}))+V_{\epsilon}\kappa$ so that asymptotics is only used to smooth out irregularities in the data and not to wipe out the noise terms. We justify this asymptotic regime with the following result, which states that if the data are well-approximated by a Gaussian, then the noisy data are just as well approximated by the limit of our proposed asymptotic regime. Here we measure the quality of the approximation by the largest difference in cumulative distribution functions ( the same measure used to quantify convergence to the Gaussian in the Central Limit Theorem). The proof is in online Appendix A.

Let $X_{n_{0}},X_{n_{0}+1},X_{n_{0}+2}\dots$ be a sequence of (vector-valued) random variables such that $X_{n}/\sqrt{n}\rightarrow N(0,\sigma^{2})$ in distribution. Let $Y$ be an independent random variable and let $Z_{n}=X_{n}+\frac{\sqrt{n}}{\sqrt{n_{0}}}Y$ for $n=n_{0},n_{0}+1,n_{0}+2,\dots$. Then:

as $n\rightarrow\infty$, $Z_{n}/\sqrt{n}$ converges in distribution to a random variable, whose cumulative distribution function we will refer to as $G_{Z}$.

Letting $\Phi$ and $\phi$ represent the CDF and density of $N(0,\sigma^{2})$ and letting $F_{0}$, $G_{0}$ represent the cumulative distribution functions of $X_{n_{0}}/\sqrt{n_{0}}$, $Z_{n_{0}}/\sqrt{n_{0}}$, respectively, then $\sup_{\vec{x}}|G_{0}(\vec{x})-G_{Z}(\vec{x})|\leq\sup_{\vec{x}}|F_{0}(\vec{x})-\Phi(\vec{x})|$.

2 Relations between Likelihood Ratio and Chi-Squared Statistics

In classical statistics, likelihood ratio tests and chi-squared tests are asymptotically equivalent (Ferguson 1996). In the privacy-preserving case, this equivalence is modified.

Suppose the probabilities under the true null hypothesis are nonzero. Consider the noisy table $\widetilde{T}=T+V\kappa\sqrt{n}$ where $V$ is a $0$-mean random variable with fixed variance. Let $\widetilde{\chi^{2}}$ denote the chi-squared statistic obtained by replacing $T$ with the noisy $\widetilde{T}$ (and the expected counts $E$ computed from $\widetilde{T}$ instead of $T$). Let $\widetilde{LR}$ denote the likelihood ratio statistic with the same substitutions and from each term $i$ subtract $2(\widetilde{T}[i]-E[i])$. Then $\widetilde{\chi^{2}}$ and $\widetilde{LR}$ have the same asymptotic distribution as $n\rightarrow\infty$.

For proof, see the online Appendix B. This theorem extends in the obvious way (and essentially the same proof) for the test of sample proportions for tables $S[\cdot]$ and $T[\cdot]$. In the classical chi-squared and likelihood ratio tests, the tests can be inaccurate when some counts are very small (e.g., 0). Since we must use noisy counts instead of raw counts, we can extend the classical rules of thumb to the following: the tests can be used if all noisy cell counts are larger than 5 + several standard deviations (of the noise). More refined rules of thumb are an open problem. The usefulness of this theorem is that sometimes it is easier to work with the likelihood ratio statistic and sometimes it is easier to work with $\chi^{2}$ when deriving asymptotic distributions.

3 The Asymptotic Distributions

In this section we derive asymptotic distributions for our various tests so that we can evaluate them in Section 5. We phrase the results in terms of added Laplace noise for differential privacy, but the results hold when the noise $V$ follows any $0$-mean distribution with finite variance. We use these distributions for $p$-value computation in Section 4.4. The proof of the following results are in the online Appendices C and D.

(Independence testing). Let $T[\cdot,\cdot]$ be a contingency table sampled from a Multinomial$(n_{0},\theta_{0})$ distribution. Consider the noisy table $\widetilde{T}=T+V_{\epsilon}\kappa\sqrt{n_{0}}$ where $V_{\epsilon}$ is a table of independent Laplace$(2/\epsilon)$ random variables. If the rows and columns under $\theta_{0}$ are independent and if no cells have probability $0$, then as $n_{0}\rightarrow\infty$, the chi-squared statistic and the likelihood ratio statistic (Definition 3) computed from $\widetilde{T}$ (instead of $T$) asymptotically have the distribution of the random variable:

where $V^{*}$ has the same distribution as $V_{\epsilon}$ and the vectorized version $vec(A)\sim N(\bm{0},\diag(vec(\theta_{0}))-vec(\theta_{0})vec(\theta_{0})^{t})$. It is asymptotically equivalent to the quantity we get by replacing $\theta_{0}[i,j]$ with $\frac{\widetilde{T}[i,\bullet]\widetilde{T}[\bullet,j]}{\widetilde{T}[\bullet,\bullet]^{2}}$.

(Test of Sample Proportions). Let $T[\cdot]$ and $S[\cdot]$ be samples from Multinomial$(n_{1},\theta_{0})$ and Multinomial$(n_{2},\theta_{0})$ distributions, respectively. Consider the noisy versions $\widetilde{T}=T+V^{1}_{\epsilon}\kappa_{1}\sqrt{n_{1}}$ and $\widetilde{S}=S+V^{2}_{\epsilon}\kappa_{2}\sqrt{n_{2}}$ where $V^{1}_{\epsilon}$, $V^{2}_{\epsilon}$ are vectors of independent Laplace$(2/\epsilon)$ random variables. If no cells have probability $0$, then as $n_{1},n_{2}\rightarrow\infty$, the chi-squared and likelihood ratio statistics (Definition 2) computed from $\widetilde{T}$ and $\widetilde{S}$ (instead of $T$ and $S$) asymptotically have the distribution of the random variable:

where $V^{*}_{1},V^{*}_{2}$ are independent with the same distribution as $V^{1}_{\epsilon},V^{2}_{\epsilon}$ and $A_{1},A_{2}\sim N(\bm{0},\diag(\theta_{0})-\theta_{0}\theta_{0}^{t})$, and $A_{1}$, $A_{2}$ are independent. It is asymptotically equivalent to the quantity we get by replacing $\theta_{0}[j]$ with $(\widetilde{T}[j]+\widetilde{S}[j])/(n_{1}+n_{2})$.

4 p-Value Algorithms

To apply Theorems 3, 4, 5 (5 comes later in this Section), we set $\kappa=1/\sqrt{n_{0}}$, where $n_{0}$ is the actual table size (in the case of the test of sample proportions, we set $\kappa_{1}=1/\sqrt{n_{1}}$ and $\kappa_{2}=1/\sqrt{n_{2}}$). The recipe for computing $p$-values is relatively simple:

Compute the appropriate test statistic from the noisy tables (e.g., $\widetilde{T}[\cdot,\cdot]$, $\widetilde{T}[\cdot]$ and/or $\widetilde{S}[\cdot]$). Let $t^{*}$ be its value.

For goodness of fit, the test statistics are given by Equations 9 or 10.

For sample proportions, they are obtained from Definition 2 by replacing the true tables $T[\cdot]$ and $S[\cdot]$ with their noisy versions $\widetilde{T}[\cdot]$ and $\widetilde{S}[\cdot]$. The $E_{1}$ and $E_{2}$ values from the definition must also be computed from the noisy tables.

For independence, they are obtained from Definition 3 by replacing the true table $T[\cdot,\cdot]$ with the noisy version $\widetilde{T}[\cdot,\cdot]$ and the $E[i,j]$ values from the definition are computed as $\widetilde{T}[i,\bullet]\widetilde{T}[\bullet,j]/\widetilde{T}[\bullet,\bullet]$.

Sample $m$ reference points $t_{1},\dots,t_{m}$ (discussed next).

Set the $p$-value to be $\left|{\left\{t_{i}~:~t_{i}\geq t^{*}\right\}}\right|/m$.

The $m$ reference points $t_{1},\dots,t_{m}$ are obtained from Algorithm 1 for independence testing and Algorithm 2 for test of sample proportions. Goodness-of-fit testing is actually a standard simulation trick (also noted by Gaboardi et al. 2016): since goodness-of-fit tests whether the table came from a Multinomial($n_{0},\theta_{0}$) distribution, for a prespecified $\theta_{0}$, one simply generates $m$ tables $Q_{1},\dots,Q_{m}$ from this distribution, adds fresh independent Laplace$(2/\epsilon)$ noise to each table to get $\widetilde{Q}_{1},\dots,\widetilde{Q}_{m}$, sets $t_{i}$ to be the value of the test statistic computed from $\widetilde{Q}_{i}$, and compares all the $t_{i}$ to the test statistic $t^{*}$ on $\widetilde{T}$.

(Goodness-of-fit). Let $T[\cdot]$ be a sample from a Multinomial$(n_{0},\theta_{0})$ distribution. Let $\widetilde{T}=T+V_{\epsilon}\kappa\sqrt{n_{0}}$ where $V_{\epsilon}$ is a vector of independent Laplace$(2/\epsilon)$ random variables. If no cells have probability $0$, then as $n_{0}\rightarrow\infty$, then the statistics:

asymptotically have the same distribution as: $\sum\limits_{j}\left(A[j]+\kappa V^{*}[j]\right)^{2}/\theta_{0}[j]$ where $V^{*}$ has the same distribution as $V_{\epsilon}$ and $A\sim N(\bm{0},\diag(\theta_{0})-\theta_{0}\theta_{0}^{t})$.

The $p$-value algorithms satisfy $\epsilon$-differential privacy.

The algorithms only use the differentially private noisy tables, the table sizes (which are assumed to be known according to the definition of differential privacy in Definition 4), and the density of the noise distribution (which is also public knowledge). At no point do they access the true data or the true noise that was added to it. As such, our algorithms are strictly post-processing algorithms and hence satisfy differential privacy due to the post-processing property of differential privacy (Dwork et al. 2006).

Experiments

We evaluate our proposed algorithms on a variety of datasets, both large and small, with various settings of the differential privacy parameter $\epsilon$. In particular, we use extremely challenging conditions where the added noise is significant compared to the standard deviation of the data. Small data sets are commonly seen in the social sciences since the effort of collecting experimental data naturally limits the data size. However, large datasets allow one to use very small $\epsilon$ values (such as $0.0001$) to provide very strong privacy guarantees for individuals.

The goal of the experiments is to determine at what point the methods break down. This will serve to identify the frontier for future research. Generally, we found that the tests work extremely well on large data even with large amounts of privacy noise. The tests work well on small datasets (e.g., $n\approx 1,800$) where the non-private $p$-value strongly rejects the null hypothesis (e.g., $p\leq 0.01$). Beyond that, the agreement with non-private tests starts to degrade (a significant improvement over prior work (Johnson and Shmatikov 2013; Uhler et al. 2013; Yu et al. 2014) in terms of reliability and agreement with non-private tests).

We use five real data sets from which we obtain seven contingency tables. The first dataset (Czech) was used in Fienberg et al. 2010. Its purpose is to study the risk factors for coronary thrombosis with data collected from all men employed in a Czech car factory at the beginning of the $15$ year follow-up study. Its sample size is $1841$. The second dataset (Rochdale) was also used in Fienberg et al. 2010 and it contains information on $665$ households in Rochdale, UK, which was used to study the factors that influence whether a wife is economically active or not. Its sample size is $665$. The third data set was used in Yang et al. 2012. It is a synthetic dataset which contains information about home zone, work zone and income category of individuals. It was formed using an ad hoc privacy approach for data extracted from a $2000$ census database. Its sample size is $2291$. The fourth data set was used in Wright and Smucker 2014 and contains data from the $1972$ National Opinion Research Center General Society Survey about white Christians’ attitude toward abortion. Its sample size is $1055$. The previous datasets are relatively small (and hence very challenging for privacy-preserving statistical testing). For a large dataset, which allows us to explore very small $\epsilon$ settings, we used the 2014 NYC Taxi data (available at http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml) which contains trip records for all NYC yellow taxis in 2014. This dataset has a sample size of $165,114,361$. Fig. 13 from online Appendix F summarizes the dataset. Other details for these datasets can be found from online Appendix F. We evaluate the reliability of our methods in Section 5.1. We evaluate the quality of the $p$-values on the real datasets in Section 5.2. Our experiments use 10,000 reference points to compute $p$-values and $p$-value results in Section 5.2 are averaged over 100 runs (of privacy-preserving table perturbations).

A $p$-value is a strong statistical statement: under the null hypothesis, P(\text{p-value}\leq q)=q. In other words, under the null hypothesis, $p$-values must be uniformly distributed. This criterion allows us to evaluate the reliability of tests: pick a null distribution, sample data from it, compute $p$-values from each sampled dataset, and plot the quantiles of the resulting $p$-values against the uniform distribution. The result is a Q-Q plot and a perfect match will be a diagonal line. We compare the reliability of our $p$-value computations for the $\chi^{2}$ and likelihood ratio statistics (denoted by $\widetilde{\chi^{2}}$ and $\widetilde{LR}$) against the reliability of the earlier method proposed by Johnson and Shmatikov 2013, which simply ran noisy tables through off-the-shelf software (we denote their results by $\chi^{2}$-JS and LR-JS). In each Q-Q plot, we only show every $400^{\text{th}}$ points from the total $10,000$ points for each test in case we cannot distinguish between the markers due to stacking.

When no noise is added to the tables, both methods match the ideal diagonal line and so are reliable, as expected and shown in Fig. 2 (left two) for independence testing and Fig. 2 (right) for test of sample proportions.

Fig. 3 shows the Q-Q plots under a variety of settings, such as sample size $n_{0}$, number of rows $r$, number of columns $c$ and the type of null distribution: the null distribution probability of table entry $T[i,j]$ is set to $P_{row}[i]P_{col}[j]$. As can be seen from Fig. 3, our methods remain reliable throughout these settings while the competitors returned unreliable $p$-values. The upward bend of the reliability curve for LR-JS (and $\chi^{2}$-JS) indicates strong bias towards producing small $p$-values and hence would lead to many false discoveries if applied in practice.

Reliability plots for the test of sample proportions can be found in Fig. 4 and goodness-of-fit in Fig. 5. Recall that test of sample proportions tests whether two tables come from the same multinomial distribution. In the figure, we report the settings of the two table sizes $n_{1}$ and $n_{2}$, the number of cells in each table, and the null distribution Multinomial probability vector $\theta_{0}$ used to generate tables for the reliability plot. The various settings for the goodness-of-fit reliability plots are presented in Fig. 5.

Those reliability results show that under privacy settings the naive method proposed by Johnson and Shmatikov 2013 is not reliable at all, and suggest that our $p$-value computations are more reliable and thus should be used instead.

2 P-value comparison on Real Data

Now we evaluate the $p$-values generated by our methods using real datasets and compare them to non-private $p$-values. All private $p$-values are averages over 100 repetitions. Please note that the experimental settings are challenging as the standard deviation of the added noise $(\sqrt{8}/\epsilon)$ is substantial compared to the standard deviation of the data itself ($O(\sqrt{n})$). For example, the taxi data has sample size $n_{0}=165,114,361$ and we used $\epsilon=0.0001$. Here $\sqrt{n_{0}}=12,849.7$ and noise std$=28,284.3$ so a loss in agreement with non-private tests is expected. Nevertheless, we generally find that when the null hypothesis is strongly rejected (non-private $\chi^{2}$ or LR $p$-value $\leq 0.01$), our private tests $\widetilde{\chi^{2}}$ and $\widetilde{LR}$ also reject the null hypothesis at level $0.01$. The output perturbation methods of Uhler et al. 2013; Yu et al. 2014 required too much noise and are omitted to avoid skewing the graphs. Fig. 6 shows our results for various tests on large NYC taxi data. The $p$-values show very good performance, as the null hypothesis is rejected (as with the original data) even when the privacy noise is extremely large ($\epsilon=0.0001$).

Next we move to extremely challenging cases with small sample sizes but high relative noise. We arrange the figures so that from left to right there is a decrease in sample size and a reduction in statistical significance of non-private analysis. Fig. 7 and Fig. 10 show results for independence testing and test of sample proportions, respectively. The results show good agreement with the non-private tests when the null hypothesis is strongly rejected (non-private $p\leq 0.01$) with sample sizes of $1,800$ or more. Agreement decreases as sample size decreases and non-private $p$-value increases. Of particular interest is the Rochdale data (Fig. 7, right). It is a small dataset with a very high $p$-value and small test statistic that is dominated by noise. Since the noise obscures any statistical signal, the $p$-value behaves more like a uniform random variable (hence we add 80% error bars on the plot). This is expected, and note that the null hypothesis would be erroneously rejected only in rare circumstances (which is the expected behavior of $p$-values).

Fig. 8 shows the results for independence tests with Census data. Again, as we move from left to right we observe smaller data sizes and less (non-private) evidence against the null hypothesis seem to reduce agreement with non-private tests. Fig. 9 shows the results for test of sample proportions with Czech car worker and Rochdale data. Again, as we move from left to right we observe smaller data sizes and less (non-private) evidence against the null hypothesis seem to reduce agreement with non-private tests. The extreme case is again the Rochdale data where the small non-private test statistic gets dominated by noise. The resulting $p$-value is closer to being uniformly distributed as noise gets larger.

For goodness of fit tests, we used extremely small sample sizes (on the order of a few hundred) with large standard deviation of Laplace noise relative to the standard deviation of the data. The results are shown in Figs. 11 and 12. The private $p$-values are still in good quality but their quality degrades as the sample size is further diminished. Again, the Rochdale data with only 79 data points has a very small non-private $\chi^{2}$ and LR value and so is completely dominated by noise, leading to large variance but no false conclusions except in rare cases (as is allowed by the definition of $p$-value).

We have several observations from the above results. For very large datasets, our tests show very good agreement with the non-private tests even with very rigorous differential privacy guarantee. When it comes to the cases with small sample sizes but high relative noise, our tests perform very well when there is strong signal against the null hypothesis. Agreement with non-private tests appears to decrease as sample size decreases and non-private $p$-value increases. Even for very small datasets where the statistical signal is dominated by noise, our tests only lead to false conclusions in rare cases.

Conclusions

In this paper, we revisited the topic of $\epsilon$-differentially private hypothesis testing. We provided $p$-value algorithms that, for the first time, allow reliable private hypothesis tests for data sizes often used in social sciences, as well as reliable tests with very strong privacy protections (i.e. small $\epsilon$ values) for large data sizes. The advantages of our algorithms over previous approaches have been verified through the extensive experiments. We believe that new test statistics tailored for the privacy domain may yield even further improvement, but those test statistics are open problems.

References

Appendix A Proof of Theorem 1

For vectors, we will use the notation $\vec{z}\prec\vec{t}$ to mean each component of $\vec{z}$ is less than or equal to the corresponding component of $\vec{t}$. Hence a cumulative distribution function $F_{A}(\vec{t})$ for a vector-valued random variable $A$ represents $P(A\prec\vec{t})$.

Since $X_{0}$ and $Y$ may be discrete random variables while the Gaussian is continuous, let $\mu$ be a suitable measure (e.g., mixture of Lebesgue and counting measure) so that we can write $f_{Y}$ to be the Radon-Nikodym derivative of the $Y$ with respect to $\mu$, $f_{0}$ to be the Radon-Nikodym derivative of $X_{0}$ with respect to $\mu$ and $f_{X}$ be the Radon-Nikodym derivative of $N(0,\sigma^{2})$ with respect to $\mu$. Then, for any $\vec{t}$:

The density of $X_{n_{0}}/\sqrt{n_{0}}$ is $f^{*}(\vec{x})\equiv\sqrt{n_{0}}f_{0}(\sqrt{n_{0}}\vec{x})$

The density of $Z_{n_{0}}/\sqrt{n_{0}}$ is then $g_{0}(\vec{z})\equiv\int_{\vec{x}}f^{*}(\vec{x})\sqrt{n_{0}}f_{Y}(\sqrt{n_{0}}(\vec{z}-\vec{x}))~d\mu(\vec{x})=\int_{\vec{x}}\sqrt{n_{0}}f_{0}(\sqrt{n_{0}}\vec{x})\sqrt{n_{0}}f_{Y}(\sqrt{n_{0}}(\vec{z}-\vec{x}))~d\mu(\vec{x})$

We claim that for all $\vec{t}$, $G_{Z}(\vec{t})=\int_{\vec{z}\prec\vec{t}}\int_{\vec{x}}\phi(\vec{x})\sqrt{n_{0}}f_{Y}(\sqrt{n_{0}}(\vec{z}-\vec{x}))~d\mu(\vec{z})~d\mu(\vec{x})$, which is the CDF of the convolution of the Gaussian with $Y/\sqrt{n_{0}}$. This follows immediately from Slutsky’s Theorem because the $X_{n}$ are independent from $Y$. Then,

Appendix B Proof of Theorem 2

Without loss of generality, assume all of the noisy tables have been stuffed into one vector $\widetilde{T}$ and similarly for the expected counts $E$.

Note that asymptotically, the correction of terms where $\widetilde{T}[i]<0$ will not be needed since $\widetilde{T}[i]/n$ converges in probability to the true parameter $\theta[i]$.

We will use the Taylor series expansion of $\log(1+x)$ around $x=0$:

Now, both $\widetilde{T}/n$ and $E/n$ converge in probability to the true (nonzero) null distribution and so $\widetilde{T}/E$ converges to 1 in probability. Thus, an application of Slutsky’s theorem (Ferguson 1996) allows us to conclude that the term containing the integral converges in distribution to the same limit as $2\sum_{i}\int_{0}^{1}\int_{0}^{1}u\frac{(\widetilde{T}[i]-E[i])^{2}}{E[i]}~dv~du=\sum_{i}\frac{(\widetilde{T}[i]-E[i])^{2}}{E[i]}$.

Thus $2\sum_{i}\left(\widetilde{T}[i]\log\frac{\widetilde{T}[i]}{E[i]}-\widetilde{T}[i]+E[i]\right)$ and $\frac{(\widetilde{T}[i]-E[i])^{2}}{E[i]}$ converge in distribution to the same limit.

Appendix C Proof of Theorem 3

Let $T$ be a contingency table sampled from a Multinomial$(n,\theta)$ distribution with no entries having $0$ probability. Let $V_{\epsilon}$ be a table (with same dimensions as $T$) of independent Laplace$(2/\epsilon)$ random variables. Let $\widetilde{T}=T+V_{\epsilon}\kappa\sqrt{n}$. Then as $n\rightarrow\infty$, $\frac{\widetilde{T}-n\theta}{\sqrt{n}}$ converges in law to the distribution of the random variable $A+\kappa V^{*}$, where $V^{*}$ has the same distribution as $V_{\epsilon}$ and $vec(A)\sim N(0,\diag(vec(\theta))-vec(\theta)vec(\theta)^{t})$

Since $T$ and $V_{\epsilon}$ are independent, the result follows from the Central limit theorem and a variation of Slutsky’s theorem (Ferguson 1996).

The proof of Theorem 3 is provided below.

When convenient, we will treat $\widetilde{T}$, $T$ and $\theta$ as either vectors (with one index) or 2-d arrays with two indices (e.g., $\theta[i,j]$). The conversion is simple: $\theta[(i-1)*c+j]=\theta[i,j]$.

We will consider the noisy likelihood ratio statistic as it is easier to work with (we apply Theorem 2 and note that in the theorem, $E[i,j]=\widetilde{T}[i,\bullet]\widetilde{T}[\bullet,j]/\widetilde{T}[\bullet,\bullet]$ and so $\sum_{ij}E[i,j]-\sum_{ij}\widetilde{T}[i,j]=0$):

use the second order taylor expansion to expand these quantities around $n\theta_{0}[i,j]$, $n\theta_{0}[i,\cdot]$ $n\theta_{0}[\cdot,j]$ and $n\theta_{0}[\cdot,\cdot]$. That is, $f(x)=f(x_{0})+(x-x_{0})^{t}\nabla f(x_{0})+(x-x_{0})^{t}\int_{0}^{1}\int_{0}^{1}\nabla^{2}vf(x_{0}+uv(x-x_{0}))~du~dv(x-x_{0})$.

use the fact that $\theta_{0}[i,j]=\theta_{0}[i,\cdot]\theta_{0}[\cdot,j]$.

use convergence in probability of $\widetilde{T}/n$ to $\theta_{0}$ to deduce that $n/[n\theta_{0}[i,j]+uv(\widetilde{T}[i,j]-n\theta_{0}[i,j])]\rightarrow 1/\theta_{0}[i,j]$ in probability.

Where the last two lines follow from: (a) noting that under the null hypothesis $\theta_{0}[i,j]=\theta_{0}[i,\cdot]\theta_{0}[\cdot,j]$, (b) convergence in probability (e.g., $\frac{\widetilde{T}}{\sum_{ij}\widetilde{T}[i,j]}\rightarrow\theta_{0}$), (c) Lemma C.10 and (d) Slutsky’s theorem (Ferguson 1996).

The theorem follows for the likelihood ratio statistic. The asymptotic equivalence follows from convergence in probability. Together with Theorem 2, the theorem also follows for the chi-squared statistic.

Appendix D Proof of Theorem 4

Note that $E_{1}[i]=\frac{n_{1}(\widetilde{T}[j]+\widetilde{S}[j])}{n_{1}+n_{2}}$ and $E_{2}[i]=\frac{n_{2}(\widetilde{T}[j]+\widetilde{S}[j])}{n_{1}+n_{2}}$ and $\sum_{i}E_{1}[i]+\sum_{j}E_{2}[j]=\sum_{i}\widetilde{T}[i]+\sum_{j}\widetilde{S}[j]$ (which we use when applying Theorem 2).

According to Definition 2, the chi-squared statistic based on $\widetilde{T}$ and $\widetilde{S}$ is:

where the last line follows from a) convergence in probability \frac{(\widetilde{T}[j]+\widetilde{S}[j])}{n_{1}+n_{2}}\rightarrow\text{\theta_{0}{}}[j], (b) Lemma C.10 in Appendix C), and (c) Slutsky’s theorem (Ferguson 1996).

The theorem follows for the chi-squared statistic. Together with Theorem 2, the theorem also follows for the likelihood ratio statistic. The asymptotic equivalence also follows from convergence in probability.

Appendix E Proof of Theorem 5

According to Definition 1, the chi-squared statistic based on $\widetilde{T}$ is:

The theorem follows for the chi-squared statistic. Together with Theorem 2, the theorem also follows for the likelihood ratio statistic.

Appendix F Datasets Used in Experiments

We provide details for the $5$ datasets used in the experiments in this section.

The first dataset (Czech) was used in Fienberg et al. 2010 and it was collected from all men employed in a Czech car factory at the beginning of a $15$ year follow-up study. It was used to study the risk factors for coronary thrombosis. Its sample size is $1841$. There are $6$ binary attributes in the dataset. A: smoking, B: strenuous mental work, C: strenuous physical work, D: systolic blood pressure, E: ratio of $\beta$ and $\alpha$ lipoproteins, F: family anamnesis of coronary heart disease.

The second dataset (Rochdale) was also used in Fienberg et al. 2010 and it contains information from $665$ households in Rochdale, UK. It was used to study the factors which influence whether a wife is economically active or not. Its sample size is $665$. There are $8$ binary attributes in the dataset. A: wife employed? (yes, if wife is economically active), B: wife’s age $>38$? C: husband employed? D: child? (yes, if there is a child of age $<4$ in the household), E: wife’s education is O-level+? F: husband’s education is O-level+? G: Asian origin? H: household working? (yes, if any other member than wife or husband of the household is working).

The third dataset was used in Yang et al. 2012. It is a synthetic dataset which contains information about home zone, work zone and income category of individuals. It was formed using an ad hoc privacy approach for data extracted from a $2000$ census database. Its sample size is $2291$. There are $3$ categorical variables, with $4$ zones of origin (Home Zone), $4$ zones of destination (Work Zone) and $16$ income categories (Income Category).

The fourth dataset was used in Wright and Smucker 2014 and contains data from the $1972$ National Opinion Research Center General Society Survey about white Christians’ attitude toward abortion. Its sample size is $1055$. There are $3$ categorical variables with $3$ religions (Religion), $3$ groups of education years (Education) and $3$ attitudes (Attitudes).

The fifth dataset contains all NYC yellow taxi trip data in $2014$ (available at http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml). This dataset has a sample size of $165,114,361$. There are $2$ categorical variables: passenger count (Passenger Count) and payment type (Payment Type). Fig. 13 summarizes the dataset.

Appendix G Permutation Testbed

The likelihood ratio and $\chi^{2}$ statistics are general-purpose statistical tools that can be adapted to a variety of tests. However, it is likely that some unknown privacy-specific test statistics could outperform them. Finding such test statistics is an open problem and, as we have seen, approximating their null distributions will generally not be easy. It would be very helpful to be able to estimate how well a new test statistic could perform on real data before figuring out all of these mathematical details. This is the purpose of our permutation-based testbed.

First, we need to choose an application that is rich enough to exhibit variations between various test statistics. Naively, one could select the goodness-of-fit test since it is possible to exactly sample from its null distribution (see Section 4). However, goodness-of-fit is too simple: rejecting the null hypothesis is the same as rejecting 1 possible distribution for the data. On the other hand, independence testing is a much richer scenario. The null hypothesis (independence of rows and columns) consists of infinitely many possible distributions (those where rows and columns are independent) and rejecting the null hypothesis means rejecting all of these distributions.

We argue that the ideal testbed is differentially-private independence testing when row and column sums are known (in other words, it protects information about individuals modulo what can be learned from the marginals). In practice, releasing row and column sums could cause a breach of privacy. Hence, this is only a method for exploring how test statistics would behave under statistical disclosure control (and for most applications it is not to be used for actually releasing analytical results). As a testbed, it has several appealing properties (which we explain in this section):

The standard permutation test of independence provides a null sampling distribution that works with any test statistic, hence there is no need to derive asymptotic approximations for the testbed.

Real-data experimental results on input-perturbation methods would carry over straightforwardly to the unrestricted case (i.e. unknown row and column sums).

Real-data experimental results on output-perturbation methods would be a lower bound on the unrestricted case, hence allowing experimenters to rule out statistics that do not perform well in the testbed.

First, we explain how to do differentially-private hypothesis testing when row and column sums are known in Section G.1. Then we discuss how experimental results would carry over to the unrestricted case in Section G.2. We illustrate its use in Section G.3. We present experiments in Section G.4 to compare likelihood ratio and $\chi^{2}$ with other statistics to confirm our intuition that there exist other test statistics that are better suited for privacy. Earlier work by Uhler et al. 2013 and Yu et al. 2014 studied differential privacy when only exact column sums (but not row sums) are known – this scenario would not be suitable for a testbed as the exact null distribution cannot be sampled from.

Consider a set of records $D={\left\{x_{1},\dots,x_{n}\right\}}$ and suppose the records have two distinguished categorical attributes, which we call $R$ and $C$. We can construct a table $T[\cdot,\cdot]$ where $T[i,j]$ is the number of records with $R=i$ and $C=j$. Although $T$ is not public knowledge, suppose its row and column sums are known (i.e. for any $i,j$, $T[\bullet,j]$ and $T[i,\bullet]$ are public). We are interested in publishing the rest of the information in $T$ in a private manner that does not leak any more information beyond what the row and column sums already revealed. The privacy definition that allows us to do this was proposed by Kifer and Machanavajjhala 2014 – it ends up being a variant of differential privacy based on a concept called marginal neighbors.

(Marginal Neighbors (Kifer and Machanavajjhala 2014)). Two datasets $D_{1},D_{2}$ are marginal neighbors if $D_{2}$ can be obtained from $D_{1}$ by swapping some of the attributes between $2$ records from $D_{1}$. Two tables $T_{1}[\cdot,\cdot],T_{2}[\cdot,\cdot]$ are marginal neighbors if they are tabulated from datasets that are marginal neighbors.

($\epsilon$-MN-Differential Privacy (Kifer and Machanavajjhala 2014)). $\randalg$ satisfies $\epsilon$-mn-differential privacy if for all $T$ and $T^{\prime}$ that are marginal neighbors (and have the same row and column sums as the true data) and for all $V\subseteq\range(\randalg)$,

Achieving $\epsilon$-mn-differential privacy is straightforward:

Given a vector-valued function $h$, $\epsilon$-mn-differential privacy can be achieved by adding independent Laplace$(s_{h}/\epsilon)$ noise to each component of $h(T)$, where $s_{h}\geq\max||h(T_{1})-h(T_{2})||_{1}$ (and the max is over all marginal neighbors $T_{1},T_{2}$ having the same row/column sums as the true data). In particular, if $h(T)$ just outputs the table $T$, then $s_{h}=4$.

Given a test statistic $h$ and a real table $T$, the testbed works as follows:

If one is interested in input perturbation, compute the private statistic value $t^{*}=h(T+V_{\epsilon})$, where $V_{\epsilon}$ is a random table that ensures $\epsilon$-mn-differential privacy (e.g., a table of independent Laplace$(4/\epsilon)$ random variables). For output perturbation, set $t^{*}=h(T)+V_{\epsilon}$, where $V_{\epsilon}$ is a noisy random variable (such as Laplace$(s_{h}/\epsilon)$) that ensures $\epsilon$-mn-differential privacy.

Generate multiple pseudo-tables $T_{1},\dots,T_{m}$. Conceptually we do this by creating two urns: urn $U_{r}$ containing $T[1,\bullet]$ balls labeled ”1”, $T[2,\bullet]$ balls labeled ”2”, etc.; and urn $U_{c}$ containing $T[\bullet,1]$ balls labeled ”1”, etc. Generate $n$ samples $r_{1},\dots,r_{n}$ from $U_{r}$ without replacement, generate $c_{1},\dots,c_{n}$ from $U_{c}$ without replacement. Set the data $D_{i}={\left\{(r_{1},c_{1}),(r_{2},c_{2}),\dots\right\}}$ and tabulate $T_{i}$ from $D_{i}$. These are samples from the null hypothesis of independence and are probabilistically equivalent to randomly permuting the $R$ attribute in the original data $D$ (Good 2004).

Compute the test statistic value $t_{i}$ for each of the $T_{i}$ using the exact same procedure as in Step 1, but using fresh noise and operating on $T_{i}$ instead of $T$.

Set the $p$-value to be $|{\left\{t_{i}:~t_{i}\geq t^{*}\right\}}|/m$.

The testbed satisfies $\epsilon$-mn-differential privacy.

Step 1 satisfies $\epsilon$-mn-differential privacy by construction and the rest of the steps just use public data (hence they are just post-processing steps). By the post-processing property (Dwork et al. 2006), the whole procedure satisfies $\epsilon$-mn-differential privacy.

G.2 Translating Experimental Results

Let us compare input perturbation noise for $\epsilon$-differential privacy and for $\epsilon$-mn-differential privacy. We need Laplace$(2/\epsilon)$ noise for the former and Laplace$(4/\epsilon)$ noise for the latter (i.e. the tables are twice as noisy). Thus $\epsilon$-differential privacy and $2\epsilon$-mn-differential privacy use the same amount of noise and therefore would generate the same values for the test statistic $t^{*}$ (in the case of input perturbation), so the $p$-value one gets under this testbed using $2\epsilon$-mn-differential privacy should correspond to the $p$-value an experimenter would have gotten under $\epsilon$-differential privacy (had statistical details, such as approximating the null distribution with unknown row/columns sums, been worked out in advance).

For output perturbation, we add Laplace$(s_{h}/\epsilon)$ noise for $\epsilon$-mn differential privacy (where $s_{h}$ is defined in Lemma G.17) and Laplace$(\mathcal{S}(h)/\epsilon)$ noise for $\epsilon$-differential privacy (where $\mathcal{S}(h)$ is defined in Definition 5). Thus the noise added under this testbed using $\frac{s_{h}\epsilon}{\mathcal{S}(h)}$-mn differential privacy is equal to the noise added under $\epsilon$-differential privacy (and hence sets up the correspondence between the resulting $p$-values). What if one hasn’t yet fully worked out the sensitivity $\mathcal{S}(h)$ under $\epsilon$-differential privacy? In this case, the statements are slightly less precise, but by comparing the following:

it follows directly from the definitions (and the triangle inequality applied to the $L_{1}$ norm) that $s_{h}\leq s^{*}\leq 2\mathcal{S}(h)$. This means Laplace$(s_{h}/2\epsilon)$ has less variance than Laplace$(\mathcal{S}(h)/\epsilon)$ and so the quality of $p$-values for output perturbation under $2\epsilon$-mn-differential privacy are expected to be a lower bound on the quality for $\epsilon$-differential privacy. We note that typically, $s_{h}$ can be much smaller than $s^{*}$ while $\mathcal{S}(h)\approx s^{*}/2$.

G.3 Usage

We will use our permutation testbed to compare the likelihood ratio and $\chi^{2}$ statistics (with both input and output perturbation) to two other statistics that are rarely, if ever, used for independence testing in the non-private case, log-likelihood (LL) and absolute difference between actual count and expected count (Diff):

An important point of distinction is that for input perturbation, we will be using the noisy values $\widetilde{T}[i,j]$, $\widetilde{T}[i,\bullet]$ (equal to $\sum_{j}\widetilde{T}[i,j]$) and $\widetilde{T}[\bullet,j]$ to compute the statistics instead of the true values $T[i,j]$, $T[i,\bullet]$, $T[\bullet,j]$. This is because in the unrestricted case, the true values will not be available once the input has been perturbed.

In contrast, for output perturbation, we will use the true values of $T[i,\bullet],T[\bullet,j]$ to compute the statistics (since they are public in $\epsilon$-mn-differential privacy). This is because the output perturbation results would be a lower bound to the quality we should expect in the unrestricted case, and the sensitivity $s_{h}$ using this method is easier to compute (another advantage of this testbed!).

We now provide $s_{h}$ calculations for the output perturbation versions of the test statistics. In some cases, $s_{h}$ depends on the dimensions of $T$. Proofs can be found in Appendix H. One important fact to note is that the Diff statistic has lowest $s_{h}$ and so, intuitively, is expected to perform well in the privacy setting.

The $s_{h}$ value of the $\chi^{2}$-statistic for a $2\times 2$ contingency tables is:

where $C=\frac{n^{2}}{T[\cdot,1]T[\cdot,2]T[1,\cdot]T[2,\cdot]}$.

The Proof of Theorem G.20 is provided in Appendix H.1. Note that table margins are $O(n)$, so the constant $C$ in Theorem G.20 is $O(1/n^{2})$ and so the $s_{h}$ value is $O(1)$ for $2\times 2$ tables. However, the chi-squared statistic does not grow with $n$ under the null hypothesis, so the noise can be a significant part of the output.

The $s_{h}$ value of the $\chi^{2}$-statistic for an $r\times c$ table $T$ with $r\geq 3$, $c\geq 3$ is:

where $a=\min(T[i_{1},\cdot],T[\cdot,j_{1}])$, $d=\min(T[i_{2},\cdot],T[\cdot,j_{2}])$, $b=\min(T[i_{1},\cdot],T[\cdot,j_{2}])-1$, $c=\min(T[i_{2},\cdot],T[\cdot,j_{1}])-1$ and $C^{\prime}=\frac{n^{2}}{T[\cdot,j_{1}]T[\cdot,j_{2}]T[i_{1},\cdot]T[i_{2},\cdot]}$.

The proof of Theorem G.21 is provided in Appendix H.2.

A simple analysis shows that the $s_{h}$ in Theorem G.21 is $O(1)$.

The $s_{h}$ value of the likelihood ratio statistic for $2\times 2$ contingency tables is

The proof of Theorem G.22 is provided in Appendix H.3.

The $s_{h}$ of the likelihood ratio statistic LR on $r\times c$ ($r\geq 3$, $c\geq 3$) contingency tables is

where $a=\min(T[i_{1},\cdot],T[\cdot,j_{1}])$, $d=\min(T[i_{2},\cdot],T[\cdot,j_{2}])$, $b=\min(T[i_{1},\cdot],T[\cdot,j_{2}])-1$, $c=\min(T[i_{2},\cdot],T[\cdot,j_{1}])-1$.

The proof of Theorem G.23 is provided in Appendix H.4. Thus $s_{h}=O(\log n)$ while the statistic itself does not grow with $n$ under the null hypothesis.

The $s_{h}$ value of the log-likelihood statistic based on $2\times 2$ contingency tables is

The proof of Theorem G.24 is provided in Appendix H.5.

The $s_{h}$ value of the LL statistic (from Equation 11) for $r\times c$ tables ($r\geq 3$, $c\geq 3$) is

where $a=\min(T[i_{1},\cdot],T[\cdot,j_{1}])$, $d=\min(T[i_{2},\cdot],T[\cdot,j_{2}])$, $b=\min(T[i_{1},\cdot],T[\cdot,j_{2}])-1$, $c=\min(T[i_{2},\cdot],T[\cdot,j_{1}])-1$.

The proof of Theorem G.25 is provided in Appendix H.6. Here $s_{h}$ also grows logarithmically.

The $s_{h}$ value of the Diff statistic (from Equation 12) is equal to $4$.

Proof of Theorem G.26 is provided in Appendix H.7. The Diff statistic is the only one out of them that has a constant sensitivity. Clearly the value of the statistic should grow with $n$, even under the null distribution, so it should quickly overwhelm the Laplace noise.

G.4 Experiments for Permutation Testbed

Now we experiment with our permutation testbed to compare the $\chi^{2}$ and likelihood ratio LR statistics to the non-traditional LL and Diff statistics considered in Section G.3. We compare the non-private versions (evaluated on actual data) to the input perturbation (with suffix “-in”) and output perturbation (with suffix “-out”) versions. The method of Uhler et al. 2013; Yu et al. 2014 is denoted $\chi^{2}$-out and has lower noise requirements in the testbed than in general.

Our first batch of results is shown in the top row of Fig. 14 and illustrates three separate interesting phenomena. The left table has $p$-values that, in the non-private case, are generally considered highly significant. The output perturbation methods (including the perturbed $\chi^{2}$ statistic) generally have high variance and perform much worse than the input perturbation methods due to the amount of noise they require. The exception is the Diff statistic, whose output perturbation version requires the least amount of noise. The middle table has $p$-value that is often considered borderline for rejecting the null hypothesis. Again, we see the same pattern, with slightly more variance even for the input perturbation results. The reason for this is that the higher the non-private $p$-value, the smaller the value of the non-private test statistic. When that is small and when $n$ is small, the resulting value of the test statistic is easily dominated by the noise (creating large variance), but does not lead to unsupported rejections of the null hypothesis. This behavior is actually expected and desired. Even in the non-private case, when the null hypothesis is true, the $p$-values should be uniformly distributed while if the null hypothesis is false, the $p$-values should gravitate towards very small values.

The bottom row of Fig. 14 shows typical results. Generally, the output perturbation methods have high variance because of their noise requirements. Meanwhile, input perturbation methods perform reasonably well even in these tough noise scenarios. The exception is the output perturbation of the Diff statistic, which is clearly the best and requires the least noise of all. The Diff statistic grows with $n$, and so would not have an asymptotic distribution in the unrestricted case, however, it is a promising starting point upon which other privacy-aware statistics could be built.

Appendix H Proof of Sensitivities

From Definition 3, the $\chi^{2}$ statistic based on a $2\times 2$ contingency table $T$ with fixed marginals $T[1,\cdot]$, $T[2,\cdot]$, $T[\cdot,1]$, $T[\cdot,2]$ is