# Private High-Dimensional Hypothesis Testing

arXiv: https://arxiv.org/abs/2203.01537 · HTML: https://mlsanity.com/paper/2203.01537/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 64 references that are in the map.
- First posted on arXiv 3 Mar 2022.

## Builds on (most cited first, 30 of 32)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Confidence Intervals and Hypothesis Testing for High-Dimensional Regression](https://mlsanity.com/paper/1306.3171/) (2013)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing](https://mlsanity.com/paper/1602.03090/) (2016)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [Private Identity Testing for High-Dimensional Distributions](https://mlsanity.com/paper/1905.11947/) (2019)
- [Test without Trust: Optimal Locally Private Distribution Testing](https://mlsanity.com/paper/1808.02174/) (2018)
- [Differentially Private Nonparametric Hypothesis Testing](https://mlsanity.com/paper/1903.09364/) (2019)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [Locally Private Hypothesis Testing](https://mlsanity.com/paper/1802.03441/) (2018)
- [Local Private Hypothesis Testing: Chi-Square Tests](https://mlsanity.com/paper/1709.07155/) (2017)
- [Improved Differentially Private Analysis of Variance](https://mlsanity.com/paper/1903.00534/) (2019)
- [Differentially Private Change-Point Detection](https://mlsanity.com/paper/1808.10056/) (2018)
- [Differentially Private High Dimensional Sparse Covariance Matrix Estimation](https://mlsanity.com/paper/1901.06413/) (2019)
- [Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models](https://mlsanity.com/paper/1901.07361/) (2019)
- [The Sample Complexity of Robust Covariance Testing](https://mlsanity.com/paper/2012.15802/) (2020)
- [Revisiting Differentially Private Hypothesis Tests for Categorical Data](https://mlsanity.com/paper/1511.03376/) (2015)

## Built on by (most cited first, 12 of 12)

- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [The Test of Tests: A Framework For Differentially Private Hypothesis Testing](https://mlsanity.com/paper/2302.04260/) (2023)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Differentially private Bayesian tests](https://mlsanity.com/paper/2401.15502/) (2024)
- [SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics](https://mlsanity.com/paper/2602.18910/) (2026)
- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)

## Abstract (arXiv)

We provide improved differentially private algorithms for identity testing of high-dimensional distributions. Specifically, for d-dimensional Gaussian distributions with known covariance Sigma, we can test whether the distribution comes from N(μ^*, Sigma) for some fixed μ^* or from some N(μ, Sigma) with total variation distance at least α from N(μ^*, Sigma) with (varepsilon, 0)-differential privacy, using only [tildeOleft(fracd1/2α2 + fracd1/3α4/3 · varepsilon2/3 + frac1α · varepsilonright)] samples if the algorithm is allowed to be computationally inefficient, and only [tildeOleft(fracd1/2α2 + fracd1/4α · varepsilonright)] samples for a computationally efficient algorithm. We also provide a matching lower bound showing that our computationally inefficient algorithm has optimal sample complexity. We also extend our algorithms to various related problems, including mean testing of Gaussians with bounded but unknown covariance, uniformity testing of product distributions over -1, 1d, and tolerant testing. Our results improve over the previous best work of Canonne et al.~citeCanonneKMUZ20 for both computationally efficient and inefficient algorithms, and even our computationally efficient algorithm matches the optimal non-private sample complexity of Oleft(frac√dα2right) in many standard parameter settings. In addition, our results show that, surprisingly, private identity testing of d-dimensional Gaussians can be done with fewer samples than private identity testing of discrete distributions over a domain of size d citeAcharyaSZ18, which refutes a conjectured lower bound of~citeCanonneKMUZ20.