Private Identity Testing for High-Dimensional Distributions
Clément L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou
Spotlight presentation: Orals & Spotlights Track 10: Social/Privacy
on 2020-12-08T07:10:00-08:00 - 2020-12-08T07:20:00-08:00
on 2020-12-08T07:10:00-08:00 - 2020-12-08T07:20:00-08:00
Toggle Abstract Paper (in Proceedings / .pdf)
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 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.