Privately Learning High-Dimensional Distributions

2018/05/01 by Gautam Kamath, Jerry Li, Kamath, Gautam +5 · 12 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #cs.CR #cs.DS #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1805.00216

To appear in COLT 2019

openalex publication_date 2018/05/01 · arxiv created 2019/05/30 · arxiv updated 2019/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The Price of Selection in Differential Privacy
• Revisiting Differentially Private Hypothesis Tests for Categorical Data

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
• Lower Bounds for Public-Private Learning under Distribution Shift
• Optimal Differentially Private Ranking from Pairwise Comparisons
• Private Geometric Median in Nearly-Linear Time
• A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
• Decentralized Quantile Regression for Feature-Distributed Massive Datasets with Privacy Guarantees
• Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions

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