Private Identity Testing for High-Dimensional Distributions
Clément L Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, Lydia Zakynthinou
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.
BibTeX
@inproceedings{NEURIPS2020_72b32a1f,
author = {Canonne, Cl\'{e}ment L and Kamath, Gautam and McMillan, Audra and Ullman, Jonathan and Zakynthinou, Lydia},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {10099--10111},
publisher = {Curran Associates, Inc.},
title = {Private Identity Testing for High-Dimensional Distributions},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/72b32a1f754ba1c09b3695e0cb6cde7f-Paper.pdf},
volume = {33},
year = {2020}
}