mlsanityData to 14 Oct 2026

Privately Learning High-Dimensional Distributions

arXiv 1805.00216 ↗First posted 1 May 2018cs.DS cs.CR cs.LGcited by 104

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 104 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 14; 2022: 19; 2023: 29; 2024: 18; 2025: 15; 2026: 9.

104 papers.

Sort:

  1. 2022Measuring Forgetting of Memorized Training Examplescited by 118
  2. 2021Learning with User-Level Privacycited by 72
  3. 2021Robust and Differentially Private Mean Estimationcited by 66
  4. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  7. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  8. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  9. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  10. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  11. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  12. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
38 more
  1. 2022Private Estimation with Public Datacited by 32
  2. 2023From Robustness to Privacy and Backcited by 27
  3. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  4. 2022Optimal and Differentially Private Data Acquisition: Central and Local Mechanismscited by 24
  5. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  6. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  7. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  8. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  9. 2021Differentially-Private Clustering of Easy Instancescited by 17
  10. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 17
  11. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
  12. 2021Differential Privacy Over Riemannian Manifoldscited by 16
  13. 2022Sentence-level Privacy for Document Embeddingscited by 16
  14. 2022Differentially Private Covariance Revisitedcited by 15
  15. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  16. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 14
  17. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  18. 2022Private High-Dimensional Hypothesis Testingcited by 12
  19. 2022Differentially private Riemannian optimizationcited by 12
  20. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  21. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  22. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  23. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 12
  24. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  25. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 11
  26. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  27. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 10
  28. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  29. 2022Differentially Private Sampling from Distributionscited by 8
  30. 2023On User-Level Private Convex Optimizationcited by 8
  31. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  32. 2022Instance-Optimal Differentially Private Estimationcited by 7
  33. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  34. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  35. 2023On Private and Robust Banditscited by 6
  36. 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
  37. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  38. 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6

50 most cited of 104 All 104 (JSON)