Private Identity Testing for High-Dimensional Distributions
This addresses the challenge of private statistical testing for high-dimensional data, which is incremental but provides concrete efficiency gains for applications in privacy-preserving data analysis.
The paper tackles the problem of differentially private identity testing for high-dimensional product distributions, achieving testers with improved sample complexity that matches order-optimal minimax bounds in many regimes, such as O(d^{1/2}/α^2).
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}/α^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.