Private Identity Testing for High-Dimensional Distributions

Abstract

In this work we present novel differentially private identity (goodness-of-fit) testers for natural and widely studied classes of multivariate product distributions: Gaussians in ${\mathbb{R}}^d$ with known covariance and product distributions over $\{\pm 1{\}}^d$. Our testers have improved sample complexity compared to those derived from previous techniques, and are the first testers whose sample complexity matches the order-optimal minimax sample complexity of $O(d^{1/2}/{\alpha }^2)$ in many parameter regimes. We construct two types of testers, exhibiting tradeoffs between sample complexity and computational complexity. Finally, we provide a two-way reduction between testing a subclass of multivariate product distributions and testing univariate distributions, and thereby obtain upper and lower bounds for testing this subclass of product distributions.

Discussing a mistake in the proof of one of the algorithms (Theorem 1.2, computationally inefficient tester), and pointing to follow-up work by Narayanan (2022) who improves upon our results and fixes this mistake

References in corpus (10)

• Mutual Information Optimally Local Private Discrete Distribution Estimation
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Test without Trust: Optimal Locally Private Distribution Testing
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• Locally Private Gaussian Estimation
• Differentially Private Change-Point Detection
• Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
• Differentially Private Identity and Closeness Testing of Discrete Distributions
• A New Class of Private Chi-Square Tests
• Private Algorithms Can Always Be Extended

Cited by in corpus (1)

• Privacy-preserving parametric inference: a case for robust statistics