{'fraction_non_alphanumeric': 0.050838036599965795, 'fraction_numerical': 0.018813066529844366, 'mean_word_length': 3.932721712538226, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A New Class of Private Chi-Square Tests

In this paper, we develop new test statistics for private hypothesis testing. These statistics are designed specifically so that their asymptotic distributions, after accounting for noise added for privacy concerns, match the asymptotics of the classical (non-private) chi-square tests for testing if the multinomial data parameters lie in lower dimensional manifolds (examples include goodness of fit and independence testing). Empirically, these new test statistics outperform prior work, which focused on noisy versions of existing statistics.


Introduction
In 2008, Homer et al. [13] published a proof-of-concept attack showing that participation of individuals in scientific studies can be inferred from aggregate data typically published in genome-wide association studies (GWAS). Since then, there has been renewed interest in protecting confidentiality of participants in scientific data [15,22,27,20] using privacy definitions such as differential privacy and its variations [7,6,3,5].
An important tool in statistical inference is hypothesis testing, a general framework for determining whether a given model -called the null hypothesis H 0 -of a population should be rejected based on a sample from the population. One of the main benefits of hypothesis testing is that it gives a way to control the probability of false discovery or Type I error -falsely concluding that a model should be rejected when it is indeed true. Type II error is the probability of failing to reject H 0 when it is false. Typically, scientists want a test that guarantees a pre-specified Type I error (say 0.05) and has high power -complement of Type II error.
The standard approach to hypothesis testing is to (1) estimate the model parameters from the data, (2) compute a test statistic T (a function of the data and the model parameters), (3) determine the (asymptotic) distribution of T under the assumption that the model generated the data, (4) compute the p-value (Type I error) as the probability of T being more extreme than the realized value computed from the data. 1 Our main contribution is a general template for creating test statistics involving categorical data. Empirically, they improve on the power of previous work on differentially private hypothesis testing [12,24], while maintaining at most some given Type I error. Our approach is to select certain properties of non-private hypothesis tests (e.g., their asymptotic distributions) and then build new test statistics that match these properties when Gaussian noise is added (e.g., to achieve concentrated differential privacy [5,3] or (approximate) differential privacy [6]). Although the test statistics are designed with Gaussian noise in mind, other noise distributions can be applied, e.g. Laplace. 2 We point out that implications of this work extend beyond simply alleviating privacy concerns. In adaptive data analysis, data may be reused for multiple analyses, each of which may depend on previous outcomes thus potentially overfitting. This problem was recently studied in the computer science literature by Dwork et al. [8], who show that differential privacy can help prevent overfitting despite reusing data. There have been several follow up works [9,4,1] that improve and extend the connection between differential privacy and generalization guarantees in adaptive data analysis. Specifically, [18] deals with post-selection hypothesis testing where they can ensure a bound on Type I error even for several adaptively chosen tests, as long as each test is differentially private.
We discuss related work in Section 2, provide background information about privacy in Section 3, present our extension of minimum chi-square theory in Section 4 and show how it can be applied to goodness of fit (Section 5) and independence testing (Section 6). Experiments appear in these latter two sections. We evaluate our test statistics with non-Gaussian noise in Section 7. We present conclusions in Section 8.

Related Work
One of the first works to study the asymptotic distributions of statistics that use differentially private data came from Wasserman and Zhou [25]. Smith [21] then showed that for a large family of statistics, there is a corresponding differentially private statistic that shares the same asymptotic distribution as the original statistic. However, these results do not ensure that statistically valid conclusions are made for finite samples. It is then the goal of a recent line of work to develop statistical inference tools that give valid conclusions for even reasonably sized datasets.
The previous work on private statistical inference for categorical data can be roughly grouped together into two main approaches (with most primarily dealing with GWAS specific applications). The first group adds appropriately scaled noise to the sampled data (or histogram of data) to ensure differential privacy and uses existing classical hypothesis tests, disregarding the additional noise distribution [15]. This approach is based on the argument that the impact of the noise becomes small as the sample size grows large. Along these lines, [23] studies how many more samples would be needed before the test with additional noise recovers the same level of power as the original test on the actual data. However, as pointed out in [11,16,17,12], even for moderately sized datasets, the impact of privacy noise is non-negligible and therefore such an approach can lead to misleading and statistically invalid results, specifically with much higher Type I error than the prescribed amount.
The second group of work consists of tests that focus on adjusting step (3) in the standard approach to hypothesis testing given in the introduction. That is, these tests use the same statistic in the classical hypothesis tests (without noise) and after making the statistic differentially private, they determine the resulting modified asymptotic distribution of the private statistic [22,27,24,12]. Unfortunately, the resulting asymptotic distribution cannot be written analytically, and so Monte Carlo (MC) simulations or numerical approximations are commonly used to determine at what point to reject the null hypothesis.
We focus on a different technique from these two different approaches, namely modifying step (2) in our outline of hypothesis testing. Thus, we consider transforming the test statistic itself so that the resulting distribution is close to the original asymptotic distribution when additional Gaussian noise is used. If the noise is non-Gaussian, then this is followed by another step that appropriately adjusts the asymptotic distribution. The idea of modifying the test statistic for regression coefficients to obtain a t-statistic in ordinary least squares has also been considered in [19].

Privacy Preliminaries
Formal privacy definitions can be used to protect scientific data with the careful injection of noise. Hypothesis testing must then properly account for this noise to avoid generating false conclusions. Since our primary focus is on the noise added by the privacy definitions (rather than their specific privacy semantics), we briefly discuss the privacy definitions and then elaborate on how to add noise to satisfy those definitions.
Let X be an arbitrary domain for records. We define two datasets x = (x 1 , · · · , x n ), x = (x 1 , · · · , x n ) ∈ X n to be neighboring if they differ in at most one entry, i.e. there is some i ∈ [n] where x i = x i , but x j = x j for all j = i. We now define differential privacy (DP) [7,6]. If δ = 0, we simply say M is -DP.
In this work, we focus on a recent variation of differential privacy, called zero concentrated differential privacy (zCDP) [3] (see also [5] for the definition of concentrated differential privacy which [3] modified). In order to define zCDP, we first define the Rényi-divergence between two probability distributions. Definition 3.2 (Rényi-Divergence). Let P 1 and P 2 be probability distributions on space Ω. For α ∈ (1, ∞), we define the Rényi-Divergence of order α of P 1 from P 2 as Remark 3.3. Note as α → 1 we get KL-divergence and as α → ∞ we get max-divergence.
We are now ready to define zCDP.
Definition 3.4 (zCDP). A mechanism M : X n → O is ρ-zero concentrated differentially private (zCDP), if for all neighboring datasets x, x ∈ X n and all α ∈ (1, ∞) we have The following result shows that zCDP lies between pure-DP where δ = 0 and approximate-DP where δ may be positive.
In order to compute some statistic f : X n → R d on the data, a differentially private mechanism is to simply add symmetric noise to f (x) with standard deviation that depends on the global sensitivity of f , which we define as In statistical hypothesis tests, it is typical to use the central limit theorem to form statistics of the data that are asymptotically normally distributed. Then we can determine whether to reject the given model in hypothesis testing by computing the corresponding p-values based on the asymptotic distribution of the statistic, which works well in practice. Because Gaussian random variables have nice composition guarantees, like the sum of two Gaussian random variables is again Gaussian (a property that is not shared with Laplace random variables), it is then desirable to use a privacy definition which is more accustomed to Gaussian perturbations. We then define the Gaussian mechanism M Gauss : X n → R d for statistic f : (1) Theorem 3.6. For statistic f : X n → R d , the Gaussian mechanism M Gauss is ρ-zCDP.
We now state several of the nice properties that zCDP shares with DP.
Theorem 3.7 (Post Processing [3]). Let M : X n → O and g : O → O be randomized algorithms.
Theorem 3.8 (Composition [3]). Let M 1 : X n → O and M 2 : X n → O be randomized algorithms where M 1 is ρ 1 -zCDP and M 2 is ρ 2 -zCDP. Then the composition M : For this work we will be considering categorical data. That is, we assume the domain X has been partitioned into d buckets or outcomes and the function f : X n → R d returns a histogram counting how many records are in each bucket. Our test statistics will only depend on this histogram. Since neighboring datasets x, x of size n differ on only one entry, their corresponding histograms differ by ±1 in exactly two buckets. Hence, we will say that two histograms are neighboring if they differ in at most two entries by at most 1. In this case, ∆ 1 (f ) = 2 and ∆ 2 (f ) = √ 2. To preserve privacy, we will add noise to the corresponding histogram X = (X 1 , · · · , X d ) of our original dataset to get X = (X 1 , . . . ,X d ). We perform hypothesis testing on this noisy histogramX. By Theorem 3.7, we know that each of our hypothesis tests will be ρ-zCDP as long as we add Gaussian noise with variance 1/ρ to each count in X. Similarly, if we add Laplace noise with scale 2/ to each count, we will achieve -DP (this is just an instance of the Laplace Mechanism [7]).

General Chi-Square Tests
In the non-private setting, a chi-square test involves a histogram X and a model H 0 that produces expected counts X over the d buckets. In general, H 0 will have k < d parameters and will estimate the parameters from X. The chi-square test statistic is defined as If the data were generated from H 0 and if k parameters had to be estimated, then the asymptotic distribution of T chi is χ 2 d−k−1 , a chi-square random variable with d − k − 1 degrees of freedom. This is the property we want our statistics to have when they are computed from the noisy histogram X instead of X. Note that in the classical chi-square tests (e.g. Pearson independence test), the statistic T chi is computed and if it is larger than the 1 − α percentile of χ 2 d−k−1 , then the model is rejected.
The above facts are part of a more general minimum chi-square asymptotic theory [10], which we overview in Section 4.2. However, we first explain the differences between private and non-private asymptotics [24,12].

Private Asymptotics
In non-private statistics, a function of n data records is considered a random variable, and nonprivate asymptotics considers this distribution as n → ∞. In private asymptotics, there is another quantity σ 2 n , the variance of the added noise. In the classical private regime, one studies what happens as n/σ 2 n → ∞; i.e., when the variance due to privacy is insignificant compared to sampling variance in the data (i.e. O(n)). In practice, asymptotic distributions derived under this regime result in unreliable hypothesis tests because privacy noise is significant [22].
In the variance-aware private regime, one studies what happens as n/σ 2 n → constant as n → ∞; that is, when the variance due to privacy is proportional to sampling variance. In practice, asymptotic distributions derived under this regime result in hypothesis tests with reliable Type I error (i.e. the p-values they generate are accurate) [12,24]. From now on, we will be using the variance-aware privacy regime. 3

Minimum Chi-Square Theory
In this section, we present important results about minimum chi-square theory. The discussion is based largely on [10] (Chapter 23). Our work relies on this theory to construct new private test statistics in Sections 5 and 6 whose asymptotic behavior matches the non-private asymptotic behavior of the classical chi-square test.
We consider a sequence of d-dimensional random vectors V (n) for n ≥ 1 (e.g. the data histogram). The parameter space Θ is a non-empty open subset of R k , where k ≤ d. The model A maps a k-dimensional parameter θ ∈ Θ into a d-dimensional vector (e.g., the expected value of V (n) ), hence it maps Θ to a subset of a k-dimensional manifold in d-dimensional space.
In this abstract setting, the null hypothesis is that there exists a θ 0 ∈ Θ such that: 4 where C(θ) ∈ R d×d is a covariance matrix. Intuitively, Equation 2 says that the Central Limit Theorem can be applied for θ 0 . We measure the distance between V (n) and A(θ) with a test statistic given by the following quadratic form: where M (θ) ∈ R d×d is a symmetric positive-semidefinite matrix; different choices of M will result in different test statistics. We make the following standard assumptions about A(θ) and M (θ).
Assumption 4.1. For all θ ∈ Θ, we have: • A(θ) is bicontinuous, 5 • A(θ) has continuous first partial derivatives, which we denote asȦ(θ) with full rank k, The following theorem will be useful in determining the distribution for the quadratic form D (n) (θ). 3 Note that taking n and σ 2 n to infinity is just a mathematical tool for simplifying expressions while mathematically keeping privacy noise variance proportional to the data variance; it does not mean that the amount of actual noise added to the data depends on the data size. 4 Here D → means convergence in distribution, as in the Central Limit Theorem [10]. 5 i.e. θj → θ ⇔ A(θj) → A(θ).

Theorem 4.2 ([10]
). Let W ∼ N (0, Λ). W W ∼ χ 2 r (chi-square distribution with r degrees of freedom) if and only if Λ is a projection of rank r. If Λ is invertible, W Λ −1 W ∼ χ 2 r . If θ 0 is known, setting M (θ) = C(θ) −1 in (3) and applying Theorem 4.2 shows that then D (n) (θ 0 ) converges in distribution to χ 2 d . However, as we show in Section 5, this can be a sub-optimal choice of M .
When θ 0 is not known, we need to estimate a good parameter θ (n) to plug into (3). One approach is to set θ (n) = arg min θ∈Θ D (n) (θ). However, this can be a difficult optimization. If there is a rough estimate of θ 0 based on the data, call it φ(V (n) ), and if it converges in probability to θ 0 (i.e. φ(V (n) ) P → θ 0 as n → ∞), then we can plug it into the middle matrix to get: and then set our estimator θ (n) = arg min θ∈Θ D (n) (θ). The test statistic becomes D (n) ( θ (n) ) and the following theorems describe its asymptotic properties under the null hypothesis. We use the shorthand A = A(θ 0 ), M = M (θ 0 ), and C = C(θ 0 ). See the appendix for the full proof, which follows a similar argument as in [10]. We then state the following result using a slight modification of Theorem 24 in [10], which we prove in the appendix.
then for θ (n) given in Theorem 4.3 and D (n) (θ) given in (4) we have:

Private Goodness of Fit Tests
As a warmup, we will first cover goodness of fit testing where the null hypothesis is simply testing whether the underlying unknown parameter is equal to a particular value. We consider categorical data vector over the d outcomes. We want to test the null hypothesis H 0 : p = p 0 , where each component of p 0 is positive, but we want to do so in a private way. We then have the following classical result [2].
where Σ has rank d − 1 and can be written as

Unprojected Private Test Statistic
To preserve ρ-zCDP, we will add appropriately scaled Gaussian noise to each component of the histogram X (n) . We then define the zCDP statistic U and We next derive the asymptotic distribution of U (n) ρ under both private asymptotic regimes in Section 4.1 (note that σ 2 = 1/ρ).
Proof. We know from the central limit theorem that U (n) ρ will converge in distribution to a multivariate normal with covariance matrix given in (7). We now show that Σ ρ is full rank. From (5) we know that Σ is positive-semidefinite because it is a covariance matrix, hence it has all nonnegative eigenvalues. We then consider the eigenvalues of Σ ρ . Let x ∈ R d be be an eigenvector of Σ ρ with eigenvalue λ ∈ R, i.e.
We then must have that x is also an eigenvector of Σ. Because Σ is positive-semidefinite we have the following inequality Thus, all the eigenvalues of Σ ρ are positive, which results in Σ ρ being nonsingular.
Because Σ ρ is invertible when the privacy parameter ρ > 0, we can create a new statistic based on U (n) ρ that has a chi-square asymptotic distribution under variance-aware privacy asymptotics.
ρn be given in (6) for nρ n → ρ > 0. If the null hypothesis H 0 : p = p 0 holds, then for Σ nρn given in (7), we have Proof. We directly apply Theorem 4.2 with W (n) = Σ ρn which is asymptotically multivariate normal with mean zero and covariance Σ By computing the inverse of Σ nρn we can simplify the statistic Q (n) ρn .
Lemma 5.4. We can rewrite the statistic in (8) as Proof. We begin by writing the inverse of the covariance matrix Σ ρ from (7) by applying Woodbury's formula [26] which gives the inverse of a modified rank deficient matrix, where ω(ρ) = p 0 We note that the vector 1 1 1 is an eigenvector of Σ ρ and Σ −1 ρ with eigenvalue 1/ρ and ρ, respectively. LettingX We can then rewrite the term in the denominator, Recalling the form of U (n) ρ from (6) concludes the proof.
Note that the coefficient on the second term of (9) grows large as nρ → ∞, so this test statistic does not approach the nonprivate test for a fixed ρ. This is not surprising since Σ nρ must converge to a singular matrix as nρ → ∞. Further, the additional noise adds a degree of freedom to the asymptotic distribution of the original statistic. This additional degree of freedom results in increasing the point in which we reject the null hypothesis, i.e. the critical value. Thus, rejecting an incorrect model becomes harder as we increase the degrees of freedom, and hence decreases power.

Projected Private Test Statistic
Given that the test statistic in the previous section depends on a nearly singular matrix, we now derive a new test statistic for the private goodness of fit test. It has the remarkable property that its asymptotic distribution is χ 2 d−1 under both private asymptotics. We start with the following observation. In the classical chi-square test, the random variables The classical test essentially uncorrelates these random variables and projects them onto the subspace orthogonal to p 0 . We will use a similar intuition for the privacy-preserving random vector U (n) ρ . The matrix Σ ρ in (7) has eigenvector 1 1 1 with eigenvalue 1/ρ -regardless of the true parameters of the data-generating distribution. Hence we think of this direction as pure noise. We therefore project U (n) ρ onto the space orthogonal to 1 1 1 (i.e. enforce the constraint that the entries in U (n) ρ add up to 0, as they would in the noiseless case). We then define the projected statistic Q Q Q (n) ρ as the following where we write the projection matrix P P P It will be useful to write out the middle matrix in Q Q Q (n) ρn for analyzing its asymptotic distribution which we prove in the supplementary file.
Lemma 5.5. For the covariance matrix Σ nρn given in (7), we have the following identity when Further, when nρ n → ∞, we have the following P P P Σ −1 nρn P P P → P P P Diag p 0 −1 P P P Proof. To prove (12), we use the fact that Σ −1 ρ has eigenvalue ρ with eigenvector 1 1 1. We then focus on proving (13). We use the identity for the inverse of Σ −1 nρn from (10).
We then focus on the second term and write We consider entry (i, j) of the above matrix, which we can write as .
We then let n → ∞ to get Thus, we have shown that for nρ n → ∞, P P P Σ −1 nρn P P P → P P P Diag p 0 −1 P P P .
We now show that the projected statistic is asymptotically chi-square distributed in both private asymptotic regimes.
Theorem 5.6. Let U (n) ρ be given in (6). For null hypothesis H 0 : p = p 0 , we can write the projected Further for nρ n → ρ > 0, if the null hypothesis holds then Q Q Q We first show that we can write the projected statistic in (11) in the proposed way. Using (12), we can write the projected statistic in terms of the unprojected statistic in (9), which will give the expression in (14) We then turn to determining the asymptotic distribution of the projected statistics when nρ n → ρ > 0. Recall that 1 1 1 is an eigenvector of Σ ρ . Note that Σ ρ is diagonalizable, i.e. Σ ρ = BDB where D is a diagonal matrix and B is an orthogonal matrix with one column being 1/d · 1 1 1. For the following matrix Λ, we can write it as a d × d identity matrix except one of the entries on the diagonal is zero.
Thus, Λ is idempotent and has rank d − 1. We define W ∼ N (0, I d−1 ). We then know that Q Q Q (n) ρn has the same asymptotic distribution as W W and so we can apply Theorem 4.2.
Theorem 5.7. For histogram data X (n) , the projected statistic Q Q Q Proof. Although Σ −1 nρn does not exist as nρ n → ∞, we can still write the asymptotic projected statistic. The middle matrix in the projected statistic when nρ n → ∞ is then P P P Diag(p 0 ) −1 P P P .
When nρ n → ∞, we also have that U (n) ρn D → N (0, Σ) from Lemma 5.2. We then analyze the asymptotic distribution of the projected statistic, where we write U ∼ N (0, Σ) and study the distribution of U P P P Diag(p 0 ) −1 P P P U . We note that we have U 1 1 1 = 0, which simplifies the asymptotic distribution of the projected statistic.
Note that this last final form is exactly the original chi-square statistic used in the classical test, which is known to converge to χ 2 d−1 .

Comparison of Statistics
We now want to compare the two private chi-square statistics in (8) and (11) to see which may lead to a larger power (i.e. smaller Type II error). The following theorem shows that we can write the unprojected statistic (8) as a combination of both the projected statistic (11) and squared independent Gaussian noise.
Theorem 5.8. Consider histogram data X (n) that has Gaussian noise Z ∼ N (0, 1/ρ · I d ) added to it. For the statistics Q ρ based on the noisy counts given in (8) and (11) respectively, we have Further, for any fixed data X (n) , Q Q Q To prove this we will use the noncentral version of Craig's Theorem.
Theorem 5.9 (Craig's Theorem [14]). Let Y ∼ N (µ, V ). Then the quadratic forms Y AY and Y BY are independent if AV B = 0.
We are now ready to prove our theorem.
Proof of Theorem 5.8. We first show that we can write Q n and Σ −1 ρ has eigenvalue ρ with eigenvector 1 1 1. We then have We now apply Craig's Theorem to show that for a fixed histogram where µ = (X (n) −np 0 )/ √ n. If we set A = P P P Σ −1 nρ P P P , then our projected statistic can be rewritten as Y AY . Further, if we define B = 1 1 11 1 1 , then . We next note that Y = Z + µ and that 1 1 1 µ = 0. Hence, Algorithm 1 (zCDP-GOF) shows how to perform goodness of fit testing with either of these two test statistics, i.e. unprojected (8) or projected (11). We note that our test is zCDP for neighboring histogram datasets due to it being an application of the Gaussian mechanism and Theorem 3.7. Hence: Theorem 5.10. zCDP-GOF(·; ρ, α, p 0 ) is ρ-zCDP.

Power Analysis
From Theorem 5.8 we see that the difference between Q (n) ρ and Q Q Q (n) ρ is the addition of squared independent noise. This additional noise can only hurt power, because for the same data the Algorithm 1 zCDP Chi-Square Goodness of Fit Test procedure zCDP-GOF(X (n) ; ρ, α, H 0 : For the unprojected statistic: For the projected statistic: ρ has larger variance than Q Q Q (n) ρ and does not depend on the underlying data. If we fix an alternate hypothesis, we can obtain asymptotic distributions for our two test statistics.
Theorem 5.11. Consider the null hypothesis H 0 : p = p 0 and the alternate hypothesis Assuming the data X (n) comes from the alternate H 1 , the two statistics Q Q Q We point out that in the case where nρ n → ∞, the projected statistic has the same asymptotic distribution as the classical (nonprivate) chi-square test under the same alternate hypothesis.
We will use the following result to prove this theorem.
Proof of Theorem 5.11. In this case we have the random vector U (n) ρn from (6) converging in distribution to N (∆ ∆ ∆, Σ ρ ) if nρ n → ρ > 0 or N (∆ ∆ ∆, Σ) if nρ n → ∞ by Lemma 5.2. We first consider the case when nρ n → ρ > 0. Consider U ∼ N (∆ ∆ ∆, Σ ρ ) and Y = Σ . We then know that Y Y and the unprojected statistic Q (n) ρn have the same asymptotic distribution. In order to use Lemma 5.12, we need to verify that Σ We then consider the projected statistic Q Q Q (n) ρn where nρ n → ρ > 0. Similar to the proof of Theorem 5.6, we diagonalize Σ ρ = BDB where B is an orthogonal matrix with one column being 1/d · 1 1 1 and D is a diagonal matrix. We then let U ∼ N (∆ ∆ ∆, Σ ρ ) and let Y = Σ −1/2 ρ P P P U We then have Y Y and Q Q Q (n) ρn will have the same asymptotic distribution. Recall that Λ = Σ −1/2 ρ P P P Σ ρ P P P Σ −1/2 ρ is idempotent with rank d − 1. Lastly, to apply Lemma 5.12 we need to show the following Λ Σ −1/2 ρ P P P∆ ∆ ∆ = Σ −1/2 ρ P P P∆ ∆ ∆.
Let B ∈ R d×(d−1) be the same as matrix B whose corresponding column for 1/d ·1 1 1 is missing, which we assume to be the last column of B. Further, we define D ∈ R (d−1)×(d−1) to be the same as D without the last row and column. We can then write P P P Σ ρ P P P = B D B . We can then simplify the left hand side to have The noncentral parameter is then ∆ ∆ ∆ P P P Σ −1 ρ P P P∆ ∆ ∆ We then note that i ∆ i = 0.
For the case when nρ n → ∞. From (13), we have P P P Σ nρn P P P → M ∞ , which can be diagonalized. As we showed in Theorem 5.7, we have From Lemma 5.2, we know that U (n) ρn D → N (∆ ∆ ∆, Σ). We then write U ∼ N (∆ ∆ ∆, Σ) so that our projected chi-square statistic has the same asymptotic distribution as Note that the noncentral parameters in the previous theorem are the same for both statistics and only the degrees of freedom are different.

Experiments for Goodness of Fit Testing
Throughout all of our experiments, we will fix α = 0.05 and privacy parameter ρ = 0.001. All of our tests are designed to achieve Type I error at most α, as we empirically show for different null hypotheses p 0 and sample size n in Figure 1. We include 1.96 times the standard error of our 100, 000 independent trials (giving a 95% confidence interval) for each sample size and each null hypothesis.  Figure 1: Empirical Type I Error for our new goodness of fit tests in zCDP-GOF with error bars corresponding to 1.96 times the standard error in 100, 000 trials. We set ρ = 0.001 which corresponds to a variance of 1, 000 for the additional noise to the counts due to privacy. The horizontal line corresponds to the target α = 0.05 Type I error that we permit.
We then empirically check the power of our new tests in zCDP-GOF for both the projected and unprojected statistic. Subject to the constraint that our tests achieve Type I error at most α, we seek to maximize power, or the probability of rejecting the null hypothesis when a distribution p 1 = p 0 , called the alternate hypothesis, is true. We expect to see the projected statistic achieve higher power than the unprojected statistic due to Theorem 5.8. Further, the fact that the critical value we use for the projected statistic is smaller than the critical value for the unprojected statistic might lead to the projected statistic having higher power.
Here we present a typical experimental scenario. For our experiments, we set the null hypothesis p 0 = (1/2, 1/6, 1/6, 1/6) and alternate hypothesis p 1 = p 0 + 0.01 · (1, −1/3, −1/3, −1/3) for various sample sizes (we empirically found this to be a tough alternative hypothesis for our statistics). For each sample size n, we sample 5, 000 independent datasets from the alternate hypothesis and test H 0 : p = p 0 in zCDP-GOF. We present the resulting power plots in Figure 2a for zCDP-GOF from Algorithm 1. We label "NonPrivate" as the classical chi-square goodness of fit test used on the actual data (and thus not private). Further, we write "ProjGOF" as the test from zCDP-GOF with the projected statistic whereas "UnProjGOF" uses the unprojected statistic. Clearly in our results the projected outperforms the unprojected statistic.
We then compare the projected and unprojected statistic in zCDP-GOF to prior work in Figure 2b. Since the projected statistic outperforms the other tests, we plot the difference in power between the projected statistic and the other tests. We label "GLRV MCGOF GAUSS" as the Monte-Carlo (MC) based test with Gaussian noise from [12], 6 and "GLRV GOF Asympt" as the hypothesis test based on the asymptotic distribution with Gaussian noise from [12,24]. Note that the error bars show 1.96 times the standard error in the difference of proportions from 100, 000 trials, giving a 95% confidence interval.

General Chi-Square Private Tests
We now consider the case where the null hypothesis contains many distributions, so that the best fitting distribution must be estimated and used in the test statistics. The data is multinomial X (n) ∼ Multinomial(n, p(θ 0 )) and p is a function that converts parameters into a d-dimensional multinomial probability vector. The null hypothesis is H 0 : θ 0 ∈ Θ; i.e. p(θ 0 ) belongs to a subset of a lower-dimensional manifold. We again use Gaussian noise Z ∼ N (0, 1/ρ · I d ) to ensure ρ-zCDP, and we define With θ 0 being the unknown true parameter, we are now ready to define our two test statistics in terms of some function φ : R d → R, such that φ(X (n) + Z) P → θ 0 (recall from Section 4.2 that φ is a simple but possibly a suboptimal estimate of the true parameter θ 0 based on the noisy data) and the covariance matrix We define the unprojected statistic R (n) ρ (θ) as follows: 6 We set the the number of MC trials m = 59 in these experiments, which guarantees at most 5% Type I error.    [12]. We use ρ = 0.001, which corresponds to the variance of 1, 000 for the additional noise to the counts.
For the projected statistic R R R (n) ρ (θ), the corresponding substitutions are P P P = I d − 1 d 1 1 11 1 1 , V (n) = P P P · X (n) +Z n , A(θ) = P P P · p(θ), and again M (θ) = (Σ nρ (θ)) −1 giving: We then assume that for both the projected and unprojected statistic Assumption 4.1 holds using their relative vectors V (n) , A(θ), and matrix M (θ). We now present the asymptotic distribution of both statistics, which is proved using the result in Theorem 4.4 .
Theorem 6.1. Under H 0 : θ 0 ∈ Θ, the following are true as n → ∞. Setting θ (n) = arg min θ∈Θ R (n) Proof. To prove this result, we appeal to Theorem 4.4. For the unprojected statistic R (n) ρ (·) we have that C(θ) = Σ ρ (θ) and the middle matrix M (θ) is simply the inverse of it, which satisfies the hypotheses of Theorem 4.4.
This completes the proof for both cases nρ n → ρ > 0 and nρ n → ∞.
Again, the projected statistic has the same distribution under both private asymptotic regimes and matches the non-private chi-square test asymptotics. We present our more general test zCDP-Min-χ 2 in Algorithm 2. The quick-and-dirty estimator φ(·) is application-specific (Section 6.1 gives independence testing as an example). 7 Further, for neighboring histogram data, we have the following privacy guarantee.
For the unprojected statistic: For the projected statistic: if T( θ (n) ) > t then Reject

Application -Independence Test
We showcase our general chi-square test zCDP-Min-χ 2 by giving results for independence testing. Conceptually, it is convenient to think of the data histogram as an r × c table, with p i,j being the probability a person is in the bucket in row i and column j. We then consider two multinomial random variables Y ∼ Multinomial(1, π (1) ) for π (1) ∈ R r (the marginal row probability vector) and Y ∼ Multinomial(1, π (2) ) for π (2) ∈ R c (the marginal column probability vector). Under the null hypothesis of independence between Y and Y , p i,j = π j . Generally, we write the probabilities as p(π (1) , π (2) ) = π (1) π (2) so that X (n) ∼ Multinomial n, p(π (1) , π (2) ) .
Thus we have the underlying parameter vector θ 0 = π (1) 1 , · · · , π (1) r−1 , π 1 , · · · , π (2) c−1 -we do not need the last component of π (1) or π (2) because we know that each must sum to 1. Also, we have d = rc and k = (r − 1) + (c − 1) in this case. We want to test whether Y is independent of Y . For our data, we are given a collection of n independent trials of Y and Y . We then count the number of joint outcomes in a contingency table given in Table 1. Each cell in the contingency table contains element X (n) i,j that gives the number of occurrences of Y i = 1 and Y j = 1. Since our test statistics notationally treat the data as a vector, when needed, we convert X (n) to a vector that goes from left to right along each row of the table.
In order to compute the statistic R ρ ( θ (n) ) in zCDP-Min-χ 2 , we need to find a quick-and-dirty estimator φ(X (n) + Z) that converges in probability to p π (1) , π (2) as n → ∞. We will use the estimator for the unknown probability vector based on the marginals of the table with noisy counts, so that for naïve estimatesπ 1 , · · · ,π (2) c−1 (18) Note that as n → ∞, the marginals converge in probability to the true probabilities even for Z ∼ N (0, 1/ρ n · I rc ) with ρ n = ω(1/n 2 ), i.e. we have thatπ j for all i ∈ [r] and j ∈ [c]. Recall that in Theorem 6.1, in order to guarantee the correct asymptotic distribution we require the nρ n → ρ > 0, or in the case of the projected statistic, we need ρ n = Ω(1/n). Thus, Theorem 6.1 imposes more restrictive settings of ρ n for the unprojected statistic than what we need in order for the naïve estimate to converge to the true underlying probability. For the projected statistic, we only need ρ n = ω(1/n) to satisfy the conditions in Theorem 6.1 and for φ(X (n) + Z) P → p π (1) , π (2) . We then use this statistic φ(X (n) +Z) in our unprojected and projected statistic in zCDP-Min-χ 2 to have a ρ-zCDP hypothesis test for independence between two categorical variables. Note that in this setting, the projected statistic has a χ 2 (r−1)(c−1) distribution, which is exactly the same asymptotic distribution used in the classical Pearson chi-square independence test.
For our results we will again fix α = 0.05 and ρ = 0.001. In Figure 3 we give the empirical Type I error for our independence tests given in zCDP-Min-χ 2 for both the projected and unprojected statistic in 100, 000 trials for various n and data distributions. We note that for small sample sizes we are achieving much smaller Type I Errors than the target α due to the fact that sometimes the noise forces us to have small expected counts (< 5 in any cell) in the contingency table based on the noisy counts, in which case our tests are inconclusive and fail to reject H 0 .   [12] We then compare the power zCDP-Min-χ 2 achieves for either of our test statistics. As a sample of our experiments, we set r = c = 2 and π (1) = (2/3, 1/3), π (2) = (1/2, 1/2). We then sample our contingency table X (n) from Multinomial(n, p(π (1) , π (2) ) + ∆ ∆ ∆) where ∆ ∆ ∆ = 0.01 · (1, 0, −1, 0), so that the null hypothesis is indeed false and should be rejected. We give the empirical power of zCDP-Min-χ 2 in Figure 4a using both the unprojected R (n) ρ ( θ (n) ) from (16) and projected statistic R R R (n) ρ ( θ (n) ) from (17) for 5, 000 independent trials and various sample sizes n. Note that again we pick θ (n) from Theorem 4.3 relative to the statistic we use. We label "NonPrivate" as the classical Pearson chi-square test used on the actual data and"ProjIND" as the test from zCDP-Min-χ 2 with the projected statistic whereas "UnProjIND" uses the unprojected statistic.
The projected statistic again outperforms prior work, so in Figure 4b, we plot the difference in power between the projected statistic in zCDP-Min-χ 2 and the competitors (the unprojected statistic and independence tests from [12]) in 50, 000 trials. Note that we label "GLRV MCIND GAUSS" as the MC based independence test with Gaussian noise and "GLRV IND Asympt" as the hypothesis test based on the asymptotic distribution from [12].

Application -GWAS Testing
We next turn to demonstrating that our new general class of private hypothesis tests for categorical data significantly improves on existing private hypothesis tests even when extra structure is assumed about the dataset. Specifically, we will be interested in GWAS data, which was the primary reason for why hypothesis tests for independence should be made private [13]. We will then assume that r = 3 and c = 2 and the data is evenly split between the two columns -as is the case in a control and case group. For such tables, we can directly compute the sensitivity of the classical chi-square statistic q(·): 22,27]). The 1 and 2 global sensitivity of the chi-square statistic q(·) based on a 3 × 2 contingency table with positive margins and n/2 cases and n/2 controls is ∆(q) = 4n/(n + 2).
Hence, a different approach for a private independence test is to add Gaussian noise with variance σ 2 = ∆ 2 (q) 2 2ρ to the statistic q(·) itself, which we call output perturbation. Our statistic is then simply Gaussian mechanism M Gauss for statistic q. We then compare the private statistic value with the distribution of T Gauss (n, ρ) = χ 2 2 +N 0, σ 2 where the degrees of freedom is 2 because we have (r − 1) · (c − 1) = 2. Thus, given a Type I error of at most α, we then set our critical value as τ Gauss (α; n, ρ) where Pr [T Gauss (n, ρ) > τ Gauss (α; n, ρ)] = α Hence, if M Gauss (X (n) ) for the statistic q is larger than τ Gauss (α; n, ρ) then we reject the null hypothesis.
For our experiments, we again set ρ = 0.001 and α = 0.05. We fix the probability vector (1/3, 1/3, 1/3) over the 3 rows in the first column whereas in the second column we set (1/2, 1/4, 1/4), therefore the case and control groups do not produce the same outcomes. In Figure 5, we show a comparison in the power between our test with the projected statistic, which assumes no structure on the data, and the output perturbation test, which crucially relies on the fact that the data is evenly split between the case and control groups. We label "ProjIND" and "UnProjIND" as the tests from zCDP-Min-χ 2 with the projected statistic and unprojected statistic, respectively. Further, we label "YFSU Gauss" as the output perturbation tests for Gaussian noise proposed in [27]. Note that our new proposed test does significantly better than the output perturbation test, sometimes requiring 5 times more samples to achieve the same level of power than for our projected statistic test.

General Chi-Square Tests with Arbitrary Noise Distributions
We next show that we can apply our testing framework in Algorithm 2 for any type of noise distribution we want to include for privacy concerns. For example, we consider adding Laplace noise rather than Gaussian noise if our privacy benchmark were (pure) differential privacy (DP). In this case, we add Laplace noise with variance 8/ 2 when computing the two statistics R (n) 2 /8 ( θ (n) ) from (16) and R R R (n) 2 /8 ( θ (n) ) from (17) so that the resulting tests will be -DP and hence from Theorem 3.5. Note that the resulting asymptotic distribution in this case will not be chisquare when we use noise other than Gaussian. We will then rely on Monte Carlo (MC) sampling to find the critical value in which to reject the null hypothesis. We give the MC based test which adds independent Laplace noise with variance 8/ 2 in Algorithm 3 and is thus -DP, but any noise distribution can be used where we replace the parameter 1/ρ in the two statistics to be the variance of the noise that is added to each count. In fact, Gaussian noise can be used in this framework although the asymptotic distribution seems to do well in practice even for small sample sizes.

Application -Goodness of Fit Testing
We first show that we can use the general chi-square test DP-MC-MIN with -DP which uses Laplace noise in Algorithm 3 for goodness of fit testing H 0 : p = p 0 . In this case we select p( θ (n) ) = p 0 and φ(X (n) + Z) = p 0 in both the unprojected and projected statistics. From the way that we have selected the critical value τ (α, ) in Algorithm 3, we have the following result on Type I error, which follows directly from Theorem 5.3 in [12].
Theorem 7.1. When the number of independent samples m we choose for our MC sampling is larger than 1/α, testing H 0 : p = p 0 in Algorithm 3 guarantees Type I error at most α .
For the projected statistic: Set θ (n) = argmin θ∈Θ T(θ) Sample {r 1 , · · · , r m } as m samples from the distribution of T( θ (n) ). Set τ (α, ) to be the (m + 1)(1 − α) -largest value of {r 1 , · · · , r m }. if T( θ (n) ) > τ (α, ) then Reject to Theorem 3.5. We set the number of independent samples we draw from the distribution of the statistic under the null hypothesis as m = 59. In Figure 6a, we compare the power of the projected and unprojected statistitic in DP-MC-GOF, labeled "ProjGOF LAP" and "UnProjGOF LAP" respectively, with the classical non-private chi-square test for various n each with 5, 000 trials. Note that there is a drastically larger power when we use the projected statistic as opposed to the unprojected statistic.
We then show that the projected statistic using Laplace noise achieves significantly higher power than using the other unprojected test statistic as well as previous DP hypothesis tests with Laplace noise from [12]. We then label "GLRV MCGOF LAP" as the MC based test with Laplace noise from [12] and plot the power loss in Figure 6b that the other DP goodness of fit tests suffer when compared to the power that DP-MC-GOF achieves with the projected statistic. Note that the error bars in the figure show 1.96 times the standard error in the difference of proportions from 100, 000 trials.

Application -Independence Testing
We then apply our general framework to independence testing as in Section 6.1. Unlike our goodness of fit testing, we are not guaranteed to have Type I error at most α when we have composite tests, e.g. independence testing, in DP-MC-MIN because we are not sampling from the exact data distribution.
We then empirically show the Type I error is at most the desired level α = 0.05. We again fix = √ 2 * 0.001 ≈ 0.045, which ensures -DP as well as (ρ = 0.001)-zCDP due to Theorem 3.5. We will use m = 59 samples in all of our MC testing. We then give the empirical Type I error for (b) The empirical loss in power from using other private goodness of fit tests instead of using the projected statistic in DP-MC-GOF. The error bars correspond to 1.96 times the standard error of each difference for 100, 000 trials. Figure 6: Empirical power results for our new DP goodness of fit tests in DP-MC-MIN and a comparisons to a previous private test in [12] that uses Laplace noise with variance 4, 000 added to each cell count. .001 * 2 ≈ 0.045 which corresponds to variance 1, 000 due to noise for each cell count. It is desired to have Type I error at most α = 0.05, which is given as the horizontal line.
various n and data distributions in Figure 7. Note that we use the same rule of thumb as before where if our naïve estimate for the probability distribution produces expected cell counts smaller than 5, then our test in inconclusive and fails to reject. This is why in our experiments, the Type I error is close to zero for small sample sizes.
We then label "GLRV MCIND LAP" as the MC based test with Laplace noise from [12]. Note that the error bars show 1.96 times the standard error in the difference of proportions from 10, 000 trials, giving a 95% confidence interval.

Conclusions
We have demonstrated a new broad class of private hypothesis tests zCDP-Min-χ 2 for categorical data based on the minimum chi-square theory. We gave two statistics (unprojected and projected )   [12] that uses Laplace noise. that converge to a chi-square distribution when we use Gaussian noise and thus lead to zCDP hypothesis tests. Unlike prior work, these statistics have the same asymptotic distributions in the private asymptotic regime as the classical chi-square tests have in the classical asymptotic regime.
Our simulations show that with either the unprojected or projected statistic our tests achieve at most α Type I error. We then empirically showed that our tests using the projected statistic significantly improves the Type II error when compared to the unprojected statistic and previous private hypothesis tests from [12]. Further, our new tests give comparable power to the classical (nonprivate) chi-square tests. We then gave further applications of our new statistics to GWAS data and how we can incorporate other noise distributions (e.g. Laplace) using an MC sampling approach.

A Proofs for Section 4.2
Proof of Theorem 4.3. Since φ(V (n) ) converges in probability to θ 0 and M (·) is a continuous mapping, then for any b > 0, c > 0 there exists an n 0 such that when n ≥ n 0 then M (φ(V (n) )) is within a distance b from M (θ 0 ) with probability at least 1 − c, which makes M (φ(V (n) )) positive definite with high probability for sufficiently large n. Furthermore, for any d > 0, we can choose n large enough so that the smallest eigenvalue of M (φ(V (n) )) is at least γ − d.
Since the parameter space is compact, we know a minimizer exists for R (n) (θ). Together, this implies that for sufficiently large n and with high probability D (n) ( θ (n) ) ≥ 0.