We introduce a new notion of stability--which we call stable list decoding--and demonstrate its applicability in designing differentially private density estimators. This definition is weaker than global stability [ABLMM22] and is related to the notions of replicability [ILPS22] and list replicability [CMY23]. We show that if a class of distributions is stable list decodable, then it can be learned privately in the agnostic setting. As the main application of our framework, we prove the first upper bound on the sample complexity of private density estimation for Gaussian Mixture Models in the agnostic setting, extending the realizable result of Afzali et al. [AAL24].

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]).