Current browse context:
stat.ML
Change to browse by:
References & Citations
Statistics > Machine Learning
Title: Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
(Submitted on 7 Sep 2023 (v1), last revised 23 Apr 2024 (this version, v3))
Abstract: We study the problem of estimating mixtures of Gaussians under the constraint of differential privacy (DP). Our main result is that $\text{poly}(k,d,1/\alpha,1/\varepsilon,\log(1/\delta))$ samples are sufficient to estimate a mixture of $k$ Gaussians in $\mathbb{R}^d$ up to total variation distance $\alpha$ while satisfying $(\varepsilon, \delta)$-DP. This is the first finite sample complexity upper bound for the problem that does not make any structural assumptions on the GMMs.
To solve the problem, we devise a new framework which may be useful for other tasks. On a high level, we show that if a class of distributions (such as Gaussians) is (1) list decodable and (2) admits a "locally small'' cover (Bun et al., 2021) with respect to total variation distance, then the class of its mixtures is privately learnable. The proof circumvents a known barrier indicating that, unlike Gaussians, GMMs do not admit a locally small cover (Aden-Ali et al., 2021b).
Submission history
From: Mohammad Afzali [view email][v1] Thu, 7 Sep 2023 17:02:32 GMT (49kb,D)
[v2] Thu, 28 Sep 2023 15:59:02 GMT (49kb,D)
[v3] Tue, 23 Apr 2024 14:54:23 GMT (49kb,D)
Link back to: arXiv, form interface, contact.