Privately Learning High-Dimensional Distributions

2018/05/01 by Kamath, Gautam, Li, Jerry, Singhal, Vikrant +1 · 6 citations
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/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.

Cited by

• On Purely Private Covariance Estimation
• Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
• Privately Estimating Black-Box Statistics
• Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression
• Enhancing Differentially Private Linear Regression via Public Second-Moment
• An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise

Related

• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• Sample-Efficient Private Learning of Mixtures of Gaussians
• Privately Estimating a Gaussian: Efficient, Robust and Optimal
• Private Hypothesis Selection
• Private and polynomial time algorithms for learning Gaussians and beyond