Sample-Efficient Private Learning of Mixtures of Gaussians
Not on the map. Why?
Abstract (arXiv)
We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly kd2 + k1.5 d1.75 + k2 d samples suffice to learn a mixture of k arbitrary d-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result [AAL24b] (which required roughly k2 d4 samples) and is provably optimal when d is much larger than k2. Moreover, we give the first optimal bound for privately learning mixtures of k univariate (i.e., 1-dimensional) Gaussians. Importantly, we show that the sample complexity for privately learning mixtures of univariate Gaussians is linear in the number of components k, whereas the previous best sample complexity [AAL21] was quadratic in k. Our algorithms utilize various techniques, including the inverse sensitivity mechanism [AD20b, AD20a, HKMN23], sample compression for distributions [ABDH+20], and methods for bounding volumes of sumsets.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 32 of its 57 references that are in the map. First posted on arXiv 4 Nov 2024.
Builds on
32 of 57 references.
References · 32
- 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 272
- 2017Collecting Telemetry Data Privatelycited by 149
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
- 2017Finite Sample Differentially Private Confidence Intervalscited by 104
- 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
- 2019Private Hypothesis Selectioncited by 60
- 2020Differentially Private Assouad, Fano, and Le Camcited by 55
- 2022Robustness Implies Privacy in Statistical Estimationcited by 47
- 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
- 2020Continuous LWEcited by 37
20 more
- 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
- 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
- 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
- 2022Private Estimation with Public Datacited by 32
- 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
- 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
- 2023From Robustness to Privacy and Backcited by 27
- 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
- 2020Near Instance-Optimality in Differential Privacycited by 23
- 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
- 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 17
- 2015Sample-Optimal Density Estimation in Nearly-Linear Timecited by 16
- 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
- 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
Built on by
Not cited yet.