Privately Learning High-Dimensional Distributions
arXiv:1805.00216
Abstract
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and learning a product distribution over the Boolean hypercube in total variation distance. The sample complexity of our algorithms nearly matches the sample complexity of the optimal non-private learners for these tasks in a wide range of parameters, showing that privacy comes essentially for free for these problems. In particular, in contrast to previous approaches, our algorithm for learning Gaussians does not require strong a priori bounds on the range of the parameters. Our algorithms introduce a novel technical approach to reducing the sensitivity of the estimation procedure that we call recursive private preconditioning.
arXiv commentTo appear in COLT 2019
References in corpus (7)
- The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
- Revisiting Differentially Private Hypothesis Tests for Categorical Data
- Differentially Private Testing of Identity and Closeness of Discrete Distributions
- PSI (Ψ): a Private data Sharing Interface
- Differentially Private Identity and Closeness Testing of Discrete Distributions
- The Price of Selection in Differential Privacy
- A New Class of Private Chi-Square Tests