Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models
This addresses the challenge of private learning for high-dimensional GMMs, which is incremental as it builds on prior non-private methods to enable privacy guarantees.
The paper tackles the problem of privately estimating parameters of unbounded Gaussian Mixture Models (GMMs) by developing a framework to privatize existing non-private algorithms with minimal overhead, resulting in the first polynomial-time algorithm and sample complexity upper bound for this task without parameter bounds.
We study the problem of privately estimating the parameters of $d$-dimensional Gaussian Mixture Models (GMMs) with $k$ components. For this, we develop a technique to reduce the problem to its non-private counterpart. This allows us to privatize existing non-private algorithms in a blackbox manner, while incurring only a small overhead in the sample complexity and running time. As the main application of our framework, we develop an $(\varepsilon, δ)$-differentially private algorithm to learn GMMs using the non-private algorithm of Moitra and Valiant [MV10] as a blackbox. Consequently, this gives the first sample complexity upper bound and first polynomial time algorithm for privately learning GMMs without any boundedness assumptions on the parameters. As part of our analysis, we prove a tight (up to a constant factor) lower bound on the total variation distance of high-dimensional Gaussians which can be of independent interest.