Source-linked AI summary
Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing
Marco Gaboardi, Hyun woo Lim, Ryan Rogers, Salil Vadhan
TL;DR
The paper addresses how to perform chi-squared goodness-of-fit and independence testing on sensitive categorical data while preserving differential privacy. It introduces noise-aware Monte Carlo and asymptotic tests, achieving target significance and recovering classical-like power with a modest sample-size increase. The main limitation is that some computational procedures become difficult for larger n or require approximations.
Problem
Classical hypothesis tests can expose sensitive information, while applying them directly to differentially private counts can produce unreliable significance levels.
Method
The paper adds Laplace or Gaussian noise to categorical counts and develops Monte Carlo and asymptotic chi-squared tests that account for the noise distribution.
Results
The tests achieve significance near the target 1−α level, and Laplace-noise tests can match classical power with fewer than 3000 additional samples for 2×2 tables.
Takeaways & Limitations
Privacy-preserving chi-squared tests can provide controlled significance and recover power close to classical tests by using additional data.
Takeaways & Limitations
Some parameter-estimation procedures are computationally expensive for n>100 or rely on approximations rather than full likelihood maximization.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops differentially private chi-squared tests for multinomial goodness of fit and categorical independence, accounting for privacy noise when determining significance. Its tests achieve near-target significance, while matching classical power requires additional samples.
- Motivation: The framework addresses privacy risks in hypothesis testing involving sensitive data, including data used in social-science and genomic studies.
- Contributions: Differentially private tests for goodness of fit and independence account for injected noise when determining significance.The paper provides Monte Carlo tests and asymptotic tests modeled on classical chi-squared procedures.
- Contributions: The tests use Laplace or Gaussian noise added to categorical counts and include Monte Carlo and asymptotic approaches.
- Results: The methods achieve significance near the target 1−α level, while privacy noise reduces power relative to classical tests.The paper reports that additional samples can recover power similar to classical tests.
- Contributions: For goodness of fit, the asymptotic private statistic is a linear combination of independent chi-squared variables and supports a less expensive alternative to Monte Carlo testing.
- Contributions: For independence testing, 2MLE estimates null-model probabilities from noisy contingency tables before applying a private chi-squared statistic.
2 Related Work
Prior work studies differential privacy for statistical inference and noisy categorical data, but classical inference can fail after privacy modifications. This paper focuses on finite-sample significance and power for private categorical hypothesis tests.
- Prior work: Correct asymptotic distributions alone do not ensure valid finite-sample significance after differential privacy modifications.The authors report that natural private algorithms can fail dramatically at finite sample sizes.
- Private categorical inference: Earlier approaches include adding noise to statistics or cell counts, restricting data forms, and calibrating sample sizes under prior probability estimates.
- Private categorical inference: Noisy contingency tables may contain negative entries or fail to sum to the known sample size, motivating work on consistency-preserving releases.
- Private categorical inference: The paper’s independence-parameter estimation procedure is inspired by prior work on denoising private degree sequences for random-graph models.
- Comparison: Related work uses Monte Carlo sampling from an asymptotic distribution, whereas this paper’s Monte Carlo approach samples from the exact null distribution.
3 Differential Privacy Preliminaries
The preliminaries define differential privacy through neighboring databases and randomized mechanisms, with privacy obtained by calibrated noise based on sensitivity. The paper assumes the sample size is known and public and uses post-processing to preserve privacy.
- Definitions: Differential privacy compares mechanism outputs on neighboring databases that differ in one individual’s data.
- Privacy parameters: The privacy parameters are interpreted with small ε and cryptographically small δ, often written with explicit dependence on n.
- Mechanisms: Noise calibration depends on a function’s global sensitivity, which measures the impact of an individual on the released output.
- Privacy properties: Post-processing preserves differential privacy for any mapping applied after a private mechanism’s output.
- Assumptions: The paper assumes n is known and public when adding Laplace or Gaussian noise to count vectors.
4 Hypothesis Testing Preliminaries
Hypothesis testing evaluates whether sampled data follow a null model while controlling false rejections. The framework treats Type I error as a hard constraint and seeks low Type II error, whose complement is test power.
- Testing framework: A hypothesis test takes data, a significance level, and a null hypothesis, then decides whether to reject that model.
- Error control: The framework requires Type I error at most α while seeking small Type II error under an alternative hypothesis.
- Error control: Significance is 1−α, power is 1−β, and controlling Type I error is treated as a hard constraint.
5 Goodness of Fit Test
The paper develops differentially private goodness-of-fit tests for multinomial data by adding noise to cell counts and accounting for that noise in significance thresholds. It provides Monte Carlo and asymptotic approaches, showing why classical thresholds can fail and how calibrated thresholds restore desired significance.
- Classical test: The classical goodness-of-fit test compares Q2 with a chi-squared threshold having d−1 degrees of freedom under H0.This follows from the multinomial model and the asymptotic chi-squared distribution of Q2.
- Private statistic: Although the private and nonprivate statistics can share the same asymptotic distribution, directly applying the classical threshold can produce poor significance levels.The problem persists even for relatively large sample sizes, motivating tests that incorporate the privacy-noise distribution.
- Private statistic: Adding mean-zero noise to each count makes the private statistic Q2_D at least as large in expectation as the nonprivate statistic Q2.This shift implies that using the classical threshold can cause excessive rejection of H0.
- Monte Carlo approach: Monte Carlo calibration yields the MCGOFD test, whose significance is at least 1−α for Laplace or Gaussian noise.The test samples from the exact noisy-statistic distribution under H0 and uses an empirical upper quantile as its cutoff.
- Asymptotic approach: For Gaussian noise, the asymptotic private statistic is analyzed as a quadratic form whose distribution is a linear combination of independent chi-squared variables.The analysis represents the limiting noisy vector as multivariate normal and applies a quadratic-form result.
- Power analysis: Power analysis under specified alternatives is left as a future direction because the alternative-hypothesis asymptotic distribution could support effective-sample-size results.The paper identifies determining the sample size needed for Type II error at most β as an important open direction.
6 Independence Testing
The paper develops differentially private independence tests for noisy contingency tables by estimating null-model probabilities and incorporating Laplace or Gaussian noise into Monte Carlo or asymptotic chi-squared procedures.
- Classical independence testing: The independence null hypothesis states that two categorical variables Y(1) and Y(2) are independent, with joint outcomes summarized in a multinomial contingency table.The table records cell counts Xi,j across n independent trials, and the classical test uses ν = (r − 1)(c − 1) degrees of freedom.
- Classical independence testing: The classical Pearson test estimates the null-constrained probability vector with an MLE, computes the chi-squared statistic, and rejects when it exceeds χ2_ν,1−α with all cell counts at least 5.The paper follows this rule of thumb by failing to reject when any cell count is below 5.
- Estimating parameters with private counts: With noisy cell counts, the authors use a two-step approximate MLE that first finds a likely contingency table and then estimates independent marginal probabilities.The optimization uses an ℓ1 objective for Laplace noise and an ℓ2 objective for Gaussian noise; an elastic-net regularizer resolves non-uniqueness for Laplace noise.
- Monte Carlo test: MCIndepD: MCIndepD adds privacy noise, estimates the independent parameters with 2MLE, simulates k > 1/α noisy contingency tables, and uses their ranked statistics to set the rejection threshold.If 2MLE returns NULL, the procedure fails to reject the null hypothesis.
7 Significance Results
The experiments evaluate whether the proposed private tests maintain the target significance level under fixed privacy and compare them with classical tests applied to noisy data.
- Goodness-of-fit significance: PrivGOF achieves near 0.95 significance across tested multinomial null hypotheses and sample sizes, whereas classical GOF is evaluated on Laplace- and Gaussian-noised counts.The experiments use 10,000 trials with α = 0.05 and (ϵ, δ) = (0.1, 10−6).
- Goodness-of-fit significance: For d = 100 multinomial data, Table 2 compares the proportions of 10,000 trials not rejected by PrivGOF and the classical GOF.The classical GOF uses critical value 123.23 in every test, while PrivGOF uses a test-specific critical value.
- Independence significance: When n = 100, the private independence tests almost always fail to reject because 2MLE produces small cell counts and invokes the classical count threshold.This preserves good significance but provides no power guarantee for small n.
- Critical values: Figure 3 reports average critical values for the private tests, with each MCIndepD and PrivIndep trial having its own threshold summarized by an average.Some plotted critical values use a logarithmic scale.
8 Power Results
Figure 4 evaluates the power of the proposed goodness-of-fit and independence tests under specified alternatives and privacy parameters. The goodness-of-fit comparison uses MCGOFD and PrivGOF, while the independence comparison uses MCIndepD and PrivIndep against classical tests.
- The goodness-of-fit experiment estimates rejection proportions over 1,000 trials for varying sample sizes.
- The classical goodness-of-fit test has difficulty distinguishing p0 from p1 at reasonable sample sizes.
- Figure 4 compares MCGOFD and PrivGOF with classical goodness-of-fit testing under an alternate p1 differing from p0 by 0.01.
- Figure 4 compares MCIndepD and PrivIndep with classical independence tests for 2 × 2 tables under alternate covariance 0.01.
9 Conclusion
The paper concludes that its private chi-squared tests achieve near-target significance while sacrificing some power, with Laplace-noise methods performing especially favorably. For 2 × 2 tables, Laplace-based tests match classical power with fewer than 3,000 additional samples.
- Laplace-noise tests achieve the same power as classical tests for 2 × 2 tables with fewer than 3,000 additional samples.
- The proposed tests achieve significance close to the target 1 − α level, either analytically or experimentally.
- All private tests lose power relative to classical non-private tests, while Laplace-noise methods outperform Gaussian-noise methods.
- The observed sample-size increase is better than the expected multiplicative 1/ϵ blowup because sampling error dominates the privacy noise.