Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples

Density estimation--also known as distribution learning--is the fundamental task of estimating a distribution given samples generated from it. In the most commonly studied setting, the data points are assumed to be generated independently from an unknown distribution f and the goal is to find a distribution ˆf that is close to f with respect to the total variation (TV) distance. Assuming that f belongs to (or is close to a member of) a class of distributions F, an important question is to characterize the number of samples that is required to guarantee that with high probability ˆf is close to f in TV distance. There is a large body of work on characterizing the optimal sample complexity (or the related minimax error rate) of learning various classes of distributions (see Diakonikolas [Dia16], Devroye and Lugosi [DL01], and Ashtiani and Mehrabian [AM18] for an overview). Nevertheless, determining the sample complexity (or even learnability) of a general class of distributions remains an important open problem (e.g., Open Problem 15.1 in Diakonikolas [Dia16]).