Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing

By Marco Gaboardi, Hyun Woo Lim, Ryan M. Rogers, Salil P. Vadhan. 2016

152 citations recorded by the source corpus.

Hypothesis testing is a useful statistical tool in determining whether a given model should be rejected based on a sample from the population. Sample data may contain sensitive information about individuals, such as medical information. Thus it is important to design statistical tests that guarantee the privacy of subjects in the data. In this work, we study hypothesis testing subject to differential privacy, specifically chi-squared tests for goodness of fit for multinomial data and independence between two categorical variables. We propose new tests for goodness of fit and independence testing that like the classical versions can be used to determine whether a given model should be rejected or not, and that additionally can ensure differential privacy. We give both Monte Carlo based hypothesis tests as well as hypothesis tests that more closely follow the classical chi-squared goodness of fit test and the Pearson chi-squared test for independence. Crucially, our tests account for the distribution of the noise that is injected to ensure privacy in determining significance. We show that these tests can be used to achieve desired significance levels, in sharp contrast to direct applications of classical tests to differentially private contingency tables which can result in wildly varying significance levels. Moreover, we study the statistical power of these tests. We empirically show that to achieve the same level of power as the classical non-private tests our new tests need only a relatively modest increase in sample size.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “One line of work [WLK15, GLRV16, KR17, KSF17, CBRG18, SGHG + 19, CKS + 19] designs differentially private versions of popular test statistics for testing goodness-of-ﬁt, closeness, and independence, as well as private ANOVA, focusing on the performance at small sample sizes.”
Marginal Release Under Local Differential Privacy (2017, background): “in [17] suggest increasing p since comparing a differentially private χ(2) statistic to a noise unaware critical value may not lead to a good significance level even for large N .”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “A recent line of work [27, 18, 21, 5] has studied distribution testing with privacy constraints.”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, methodology): “, 2017)) provides significantly stronger guarantees compared to (Gaboardi et al., 2016).”
Differentially private model selection with penalized and constrained likelihood (2016, background): “…and Shmatikov, 2013; Uhler et al., 2013; Yu et al., 2014; Karwa et al., 2014; Solea, 2014; Dwork et al., 2015; Sheffet, 2015; Wang et al., 2015; Gaboardi et al., 2016) and statistical lower bounds (Chaudhuri and Hsu, 2011; Duchi et al., 2013); there is also a large literature on private…”
Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “Here the algorithm itself is run by a trusted curator who has access to all the user data, but needs to ensure that the output of the test maintains differential privacy; see [21, 28, 33] for a sampling of results on identity and independence testing.”
A New Class of Private Chi-Square Tests (2016, methodology): “We label “GLRV MCGOF GAUSS” as the Monte-Carlo (MC) test with Gaussian noise from [12],(7) and “GLRV GOF Asympt” as the asymptotics-based test with Gaussian noise from [12, 23].”
Improved Differentially Private Analysis of Variance (2019, methodology): “[10] are notable exceptions, giving power curves for several different approaches.”
Finite Sample Differentially Private Confidence Intervals (2017, methodology): “We came to the problem of constructing confidence intervals for a normal mean as part of an effort to bring differential privacy to practice in the sharing of social science research data through the design of the software tool PSI (Gaboardi et al., 2016a), as confidence intervals are a workhorse of”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, background): “Mean estimation also naturally arises in hypothesis testing [33, 18, 7, 9, 10, 8].”
Differentially Private Nonparametric Hypothesis Testing (2019, methodology): “For these same tests, Monte Carlo simulation has been shown to offer more precise analysis in some cases [14,36].”
Differentially Private Releasing via Deep Generative Model (2018, background): “…categorized into supervised settings, such aslogistic regression [5]and supportvectormachine (SVM) [5, 31], and unsupervised settings, such as publishing histograms [37], [38], hypothesis testing [13], collaborative recommendation [42], K-Means clustering [34], and spectral graph analysis [35].”
Local Private Hypothesis Testing: Chi-Square Tests (2017, methodology): “…works have studied differentially private hypothesis tests that can be used in place of the standard, non-private hypothesis tests (Uhler et al., 2013; Yu et al., 2014; Sheffet, 2015; Karwa and Slavković, 2016; Wang et al., 2015; Gaboardi et al., 2016; Kifer and Rogers, 2017; Cai et al., 2017).”
INSPECTRE: Privately Estimating the Unseen (2018, background): “Other works investigating private hypothesis testing include (Wang et al., 2015a; Gaboardi et al., 2016; Kifer & Rogers, 2017; Kakizaki et al., 2017; Rogers, 2017; Gaboardi & Rogers, 2017), which focus less on characterizing the finite-sample guarantees of such tests, and more on understanding their”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “Besides goodness-of-ﬁt, there is also work in this setting on testing independence between discrete variables [Wang et al., 2015, Gaboardi et al., 2016], and in testing independence between a discrete and a continuous variable by constructing diﬀerentially private versions of classical rank-based…”
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals (2018, background): “, 2015) mostly focusing on robust statistics; but only a handful of works study rigorously the significance and power of hypotheses testing under differential privacy (Vu and Slavkovic, 2009; Uhler et al., 2013; Wang et al., 2015; Gaboardi et al., 2016; Kifer and Rogers, 2017; Cai et al., 2017; Shef”