  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.
