Agnostic Private Density Estimation for GMMs via List Global Stability
Not on the map. Why?
Abstract (arXiv)
We consider the problem of private density estimation for mixtures of unrestricted high dimensional Gaussians in the agnostic setting. We prove the first upper bound on the sample complexity of this problem. Previously, private learnability of high dimensional GMMs was only known in the realizable setting [Afzali et al., 2024]. To prove our result, we exploit the notion of textitlist global stability [Ghazi et al., 2021b,a] that was originally introduced in the context of private supervised learning. We define an agnostic variant of this definition, showing that its existence is sufficient for agnostic private density estimation. We then construct an agnostic list globally stable learner for GMMs.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 43 of its 62 references that are in the map. First posted on arXiv 5 Jul 2024.
Builds on
43 of 62 references.
References · 43
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
- 2017Finite Sample Differentially Private Confidence Intervalscited by 103
- 2018Privately Learning High-Dimensional Distributionscited by 103
- 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
- 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
- 2021Robust and Differentially Private Mean Estimationcited by 66
- 2021Differential privacy and robust statistics in high dimensionscited by 64
- 2020An Equivalence Between Private Classification and Online Predictioncited by 63
- 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
- 2019Private Hypothesis Selectioncited by 60
- 2015Differentially Private Release and Learning of Threshold Functionscited by 58
- 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
31 more
- 2022Robustness Implies Privacy in Statistical Estimationcited by 47
- 2022Reproducibility in Learningcited by 44
- 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
- 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
- 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2015Simultaneous Private Learning of Multiple Conceptscited by 34
- 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
- 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
- 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
- 2022Private Estimation with Public Datacited by 31
- 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
- 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
- 2023From Robustness to Privacy and Backcited by 27
- 2021Realizable Learning is All You Needcited by 25
- 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
- 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
- 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
- 2021Differentially-Private Clustering of Easy Instancescited by 17
- 2023Statistical Indistinguishability of Learning Algorithmscited by 17
- 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
- 2020Closure Properties for Private Classification and Online Predictioncited by 15
- 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
- 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
- 2017Sample-Efficient Learning of Mixturescited by 9
- 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
- 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
- 2023Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problemcited by 4
- 2024Distribution Learnability and Robustnesscited by 4
- 2018Privacy and Utility Tradeoff in Approximate Differential Privacycited by 3
- 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
Built on by
Citing papers per year: 2024: 1; 2025: 0; 2026: 1.
2 papers.