Privately Learning Mixtures of Axis-Aligned Gaussians

Abstract:
We consider the problem of learning mixtures of Gaussians under the constraint of approximate differential privacy. We prove that Õ(kd log(1/δ)/α2ε) samples are sufficient to learn a mixture of k axis-aligned Gaussians in R to within total variation distance α while satisfying (ε, δ)-differential privacy. This is the first result for privately learning mixtures of unbounded axis-aligned (or even unbounded univariate) Gaussians. If the covariance matrices of each of the Gaussians is the identity matrix, we show that Õ(kd/α + kd log(1/δ)/αε) samples are sufficient. To prove our results, we design a new technique for privately learning mixture distributions. A class of distributions F is said to be list-decodable if there is an algorithm that, given “heavily corrupted” samples from f ∈ F , outputs a list of distributions one of which approximates f . We show that if F is privately list-decodable then we can learn mixtures of distributions in F . Finally, we show axis-aligned Gaussian distributions are privately list-decodable, thereby proving mixtures of such distributions are privately learnable.

heading: 1 Introduction
text: The fundamental problem of distribution learning concerns the design of algorithms (i.e., estimators) that, given samples generated from an unknown distribution f , output an “approximation” of f . While distribution learning has a long history [54], studying it under privacy constraints is relatively new and unexplored.
In this paper, we work with a rigorous and practical notion of data privacy known as differential privacy [36]. Roughly speaking, differential privacy guarantees that no single data point can influence the output of an algorithm too much. Intuitively, this provides privacy by “hiding” the contribution of each individual. Differential privacy is the de facto standard for modern private analysis and has seen widespread impact in both industry and government [12, 22, 28, 29, 39].
In recent years, there has been a flurry of activity in differentially private distribution learning and a number of techniques have been developed in the literature. In the pure differentially private setting, Bun et al. [17] introduced a method to learn classes of distributions that admit a finite cover, i.e. when the class of distributions is well-approximated by a finite number of distributions. They show that this is an exact characterization of distributions which can be learned under pure differential privacy in the sense that a class of distributions is learnable under pure differential privacy if and only if the class
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
admits a finite cover [17, 41]. As a consequence of this result, they obtained pure differentially private algorithms for learning Gaussian distributions provided that the mean of the Gaussians are bounded and the covariance matrix of the Gaussians are spectrally bounded.1 Moreover, such restrictions on the Gaussians are necessary under the constraint of pure differential privacy.
One way to remove the requirement of having a finite cover is to relax to a weaker notion of privacy known as approximate differential privacy. With this notion, Bun et al. [17] introduced a method to learn a class of distributions that, instead of requiring a finite cover, requires a “locally small” cover, i.e. a cover where each distribution in the class is well-approximated by only a small number of elements within the cover. They prove that the class of Gaussians with arbitrary mean and a fixed, known covariance matrix has a locally small cover which implies an approximate differentially private algorithm to learn this class of distributions. Later, Aden-Ali, Ashtiani, and Kamath [4] proved that the class of mean-zero Gaussians (with no assumptions on the covariance matrix) admits a locally small cover leading to an approximate differentially private method to learn the class of all Gaussians.
It is a straightforward observation that if a class of distributions admits a finite cover then the class of its mixtures also admits a finite cover. Combined with the aforementioned work of Bun et al., this implies a pure differentially private algorithm for learning mixtures of Gaussians with bounded mean and spectrally bounded covariance matrices. It is natural to wonder whether an analogous statement holds for locally small covers. In other words, if a class of distributions admits a locally small cover then does the class of mixtures also admit a locally small cover? If so, this would provide a fruitful direction to design differentially private algorithms for learning mixtures of arbitrary Gaussians. Unfortunately, there are simple examples of classes of distributions that admit a locally small cover yet their mixture do not. This leaves open the question of designing private algorithms for many classes of distributions that are learnable in the non-private setting. One concrete open problem is for the class of mixtures of two arbitrary univariate Gaussian distributions. A more general problem is private learning of mixtures of k axis-aligned (or general) Gaussian distributions.

heading: 1.1 Main Results
text: We demonstrate that it is indeed possible to privately learn mixtures of unbounded univariate Gaussians. More generally, we give sample complexity upper bounds for learning mixtures of unbounded d-dimensional axis-aligned Gaussians. In the following theorem and the rest of the paper we use Õ to hide polylogarithmic factors, i.e. Õ(f(x)) means O(f(x) logc f(x)) for some c > 0.
Theorem 1.1 (Informal). The sample complexity of learning a mixture of k d-dimensional axisaligned Gaussians to α-accuracy in total variation distance under (ε, δ)-differential privacy is Õ ( k2d log3/2(1/δ)
α2ε
) .
The formal statement of this theorem can be found in Theorem 5.1. For technical reasons, we do require that δ ∈ (0, 1/n) for the above theorem to hold. This condition is quite standard in the differential privacy literature. Indeed, for useful privacy, δ should be “cryptographically small”, i.e., δ 1/n. Even for the univariate case, our result is the first sample complexity upper bound for learning mixture of Gaussians under differential privacy for which the variances are unknown and the parameters of the Gaussians may be unbounded. In the non-private setting, it is known that Θ̃(kd/α2) samples are necessary and sufficient to learn a mixture of k axis-aligned Gaussian in Rd [6, 61]. In the private setting, the best known sample complexity lower bound is Ω(d/αε log(d)) under (ε, δ)-DP when δ ≤ Õ( √ d/n) [46]. Obtaining improved upper or lower bounds in this setting remains an open question.
If the covariance matrix of each component of the mixture is the same and known or, without loss of generality, equal to the identity matrix, then we can improve the dependence on the parameters and obtain a result that is in line with the non-private setting.
1When we say that a matrix Σ is spectrally bounded, we mean that there are 0 < a1 ≤ a2 such that a1 · I Σ a2 · I .
Theorem 1.2 (Informal). The sample complexity of learning a mixture of k d-dimensional Gaussians with identity covariance matrix to α-accuracy in total variation distance under (ε, δ)-differential privacy is Õ ( kd α2 + kd log(1/δ) αε ) .
We relegate the formal statement and the proof of this theorem to the supplementary materials (see Appendix F). Note that the work of [53] implies an upper bound of O(k2d3 log2(1/δ)/α2ε2) for private learning of the same class albeit in the incomparable setting of parameter estimation.
Comparison with locally small covers. While the results in [4, 17] for learning Gaussian distributions under approximate differential privacy do not yield finite-time algorithms, they do give strong information-theoretic upper bounds. This is achieved by showing that certain classes of Gaussians admit locally small covers. It is thus natural to ask if we can obtain sharper results by showing that mixtures of Gaussians also admit locally small covers. Unfortunately, the following simple example shows that not even mixtures of two univariate Gaussians admit locally small covers.
Proposition 1.3 (Informal version of Proposition B.6). Every cover for the class of mixtures of two univariate Gaussians is not locally small.

heading: 1.2 Techniques
text: To prove our result, we devise a novel technique which reduces the problem of privately learning mixture distributions to the problem of private list-decodable learning of distributions. The framework of list-decodable learning was introduced by Balcan, Blum, and Vempala [8] and Balcan, Röglin, and Teng [9] in the context of clustering but has since been studied extensively in the literature in a number of different contexts [7, 20, 21, 26, 27, 49, 55, 56]. The problem of list-decodable learning of distributions is as follows. There is a distribution f of interest that we are aiming to learn. However, we do not receive samples from f ; rather we receive samples from a corrupted distribution g = (1 − γ)f + γh where γ ∈ (0, 1) and h is some arbitrary distribution. In our application, γ is close to 1, i.e. most of the samples are corrupted. The goal in list-decodable learning is to output a short list of distributions f1, . . . , fm with the requirement that f is close to at least one of the fi’s. The formal definition of list-decodable learning can be found in Definition 2.6. Informally, the reduction can be summarized by the following theorem which is formalized in Section 3.
Theorem 1.4 (Informal). If a class of distributions F is privately list-decodable then mixtures of distributions from F are privately learnable.
Roughly speaking, the reduction from learning mixtures of distribution to list-decodable learning works as follows. Suppose that there is an unknown distribution f which is a mixture of k distributions f1, . . . , fk. A list-decodable learner would then receive samples from f as input and output a short list of distributions F̂ so that for every fi there is some element in F̂ that is close to fi. In particular, some mixture of distributions from F̂ must be close to the true distribution f . Since F̂ is a small finite set, the set of possible mixtures must also be relatively small. This last observation allows us to make use of private hypothesis selection which selects a good hypothesis from a small set of candidate hypotheses [4, 17]. In Section 3, we describe the aforementioned reduction in more detail. We note that a similar connection between list-decodable learning and learning mixture distributions was also used by Diakonikolas et al. [26]. However, our reduction is focused on the private setting.
The reduction shows that to privately learn mixtures, it is sufficient to design differentially private list-decodable learning algorithms that work for (corrupted versions of) the individual mixture components. To devise list-decodable learners for (corrupted) univariate Gaussian, we utilize “stability-based” histograms [15, 51] that satisfy approximate differential privacy.
To design a list-decodable learner for corrupted univariate Gaussians, we follow a three-step approach that is inspired by the seminal work of Karwa and Vadhan [50]. First, we use a histogram to output a list of variances one of which approximates the true variance of the Gaussian. As a second step, we would like to output a list of means which approximate the true mean of the Gaussian. This can be done using histograms provided that we roughly know the variance of the Gaussian. Since we have candidate variances from the first step, we can use a sequence of histograms where the width of the bins of each of the histograms is determined by the candidate variances from the first step. As a last step, using the candidate variances and means from the first two steps, we are able to construct a small set of distributions one of which approximates the true Gaussian to within accuracy α. In the
axis-aligned Gaussians setting, we use our solution for the univariate case as a subroutine on each dimension separately. Now that we have a list-decodable learner for axis-aligned Gaussians, we use our reduction to obtain a private learning algorithm for learning mixtures of axis-aligned Gaussians.
Approaches based on constructing lists of candidate variances and means in order to learn an accurate mixture have been previously considered in the non-private setting [5, 6, 23, 61]. However, it does not seem possible to directly privatize the algorithms in this line of work since they construct these candidates directly from the samples, which is a clear violation of privacy.

heading: 1.3 Open Problems
text: The most basic open problem is to understand the exact sample complexity (up to constants) for learning mixtures of univariate Gaussians under approximate differential privacy. Conjecture 1.5 (Informal). The sample complexity of learning a mixture of k univariate Gaussians to within total variation distance α with high probability under (ε, δ)-DP is Θ ( k α2 + k αε + log(1/δ) ε ) .
Another open question is whether it is possible to privately learn mixtures of (arbitrary) highdimensional Gaussians. We conjecture that it is possible and with the following sample complexity.
Conjecture 1.6 (Informal). The sample complexity of learning a mixture of k d-dimensional Gaussians to within total variation distance α with high probability under (ε, δ)-DP is Θ ( kd2
α2 + kd2 αε + log(1/δ) ε
) .

heading: 1.4 Additional Related Work
text: Recently, [17] showed how to learn spherical Gaussian mixtures where each Gaussian component has bounded mean under pure differential privacy. Acharya, Sun and Zhang [3] were able to obtain lower bounds in the same setting that nearly match the upper bounds of Bun et al. [17]. Both [47, 53] consider differentially private learning of Gaussian mixtures, however their focus is on parameter estimation and therefore require additional assumptions such as separation or boundedness of the components.
There has been a flurry of activity on differentially private distribution learning and parameter estimation in recent years for many problem settings [3, 11, 14, 16–18, 25, 30, 38, 46, 48, 50, 52, 53, 59, 60]. There has also been a lot of work in the locally private setting [2, 31–33, 40, 43, 44, 63, 64]. Other work on differentially private estimation include [1, 10, 13, 19, 34, 58, 65]. For a more comprehensive review of differentially private statistics, see [45].

heading: 2 Preliminaries
text: For any m ∈ N, [m] denotes the set {1, 2, . . . ,m}. Let X ∼ f denote a random variable X sampled from the distribution f . Let (Xi)mi=1 ∼ fm denote an i.i.d. random sample of sizem from distribution f . For a vector x ∈ Rd, we refer to the ith element of vector x as xi. For any k ∈ N, we define the k-dimensional probability simplex to be ∆k := {(w1, . . . , wk) ∈ Rk≥0 : ∑k i=1 wi = 1}. For a vector µ ∈ Rd and a positive semidefinite matrix Σ, we use N (µ,Σ) to denote the multivariate normal distribution with mean µ and covariance matrix Σ. We define G to be the class of univariate Gaussians and Gd = {N (µ,Σ) : Σij = 0 ∀i 6= j and Σii > 0 ∀i} to be the class of axis-aligned Gaussians. Definition 2.1 (k-mix(F)). LetF be a class of probability distributions. Then the class of k-mixtures of F , written k-mix(F), is defined as
k-mix(F) := { ∑k i=1 wifi : (w1, . . . , wk) ∈ ∆k, f1, . . . , fk ∈ F }.

heading: 2.1 Distribution Learning
text: A distribution learning method is a (potentially randomized) algorithm that, given a sequence of i.i.d. samples from a distribution f , outputs a distribution f̂ as an estimate of f . The focus of this paper is on absolutely continuous probability distributions (distributions that have a density with respect to
the Lebesgue measure), so we refer to a probability distribution and its probability density function interchangeably. The specific measure of “closeness” between distributions that we use is the total variation (TV) distance. Definition 2.2. Let g and f be two probability distributions defined over X and let Ω be the Borel σ-algebra on X . The total variation distance between g and f is defined as
dTV(g, f) = sup S∈Ω |Pg(S)−Pf (S)| =
1
2 ∫ x∈X |g(x)− f(x)|dx = 1 2 ‖g − f‖1 ∈ [0, 1].
where Pg(S) denotes the probability measure that g assigns to S. Moreover, if F is a set of distributions over a common domain, we define dTV(g,F) = inff∈F dTV(g, f). Definition 2.3 (PAC learner). We say algorithm A is a PAC-learner for a class of distributions F which uses m(α, β) samples, if for every α, β ∈ (0, 1), every f ∈ F , and every n ≥ m(α, β) the following holds: if the algorithm is given parameters α, β and a sequence of n i.i.d. samples from f as inputs, then it outputs an approximation f̂ such that dTV(f, f̂) ≤ α with probability at least 1− β.2
We work with an additive corruption model often studied in the list-decodable setting that is inspired by the seminal work of Huber [42]. In this model, a sample is drawn from a distribution of interest with some probability, and with the remaining probability is drawn from an arbitrary distribution. Our list-decodable learners take samples from these “corrupted” distributions as input. Definition 2.4 (γ-corrupted distributions). Fix some distribution f and let γ ∈ (0, 1). We define a γ-corrupted distribution of f as any distribution g such that g = (1 − γ)f + γh for an arbitrary distribution h. We defineHγ(f) to be the set of all γ-corrupted distributions of f . Remark 2.5. Observe that Hγ(f) is monotone increasing in γ, i.e. Hγ(f) ⊂ Hγ′(f) for all γ′ ∈ (γ, 1). To see this, note that if g = (1−γ)f +γh then we can also rewrite g = (1−γ′)f +γ′h′, where h′ = γ
′−γ γ f + γ γ′h. Hence, g ∈ Cγ′(f).
In this work, γ is usually quite close to 1, i.e. the vast majority of the samples are corrupted. Next, we define list-decodable learning. In this setting, the goal is to learn a distribution f given samples from a γ-corrupted distribution g of f . As γ ≈ 1, the goal is to output a list of distributions, one of which approximates f . We use this primitive to design algorithms for learning mixture distributions. Definition 2.6 (list-decodable learner). We say algorithm ALIST is an L-list-decodable learner for a class of distributions F usingmLIST(α, β, γ) samples if for every α, β, γ ∈ (0, 1), n ≥ mList(α, β, γ), f ∈ F , and g ∈ Hγ(f), the following holds: given parameters α, β, γ and a sequence of n i.i.d. samples from g as inputs, ALIST outputs a set of distributions F̃ with |F̃ | ≤ L such that with probability no less than 1− β we have dTV(f, F̃) ≤ α.

heading: 2.2 Differential Privacy
text: Let X∗ = ∪∞i=1Xi be the set of all datasets of arbitrary size over a domain set X . Two datasets D,D′ ∈ X∗ are neighbours if D and D′ differ in at most one data point. Informally, an algorithm is differentially private if its output on neighbouring databases are similar. Formally, differential privacy (DP)3 has the following definition. Definition 2.7 ([35, 36]). A randomized algorithm T : X∗ → Y is (ε, δ)-differentially private if for all n ≥ 1, for all neighbouring datasets D,D′ ∈ Xn, and for all measurable subsets S ⊆ Y ,
Pr [T (D) ∈ S] ≤ eε Pr[T (D′) ∈ S] + δ . If δ = 0, we say that T is ε-differentially private.
We refer to ε-DP as pure DP, and (ε, δ)-DP for δ > 0 as approximate DP. We make use of the following property of differentially private algorithms which asserts that adaptively composing differentially private algorithms remains differentially private. By adaptive composition, we mean that we run a sequence of algorithms M1(D), . . . ,MT (D) where the choice of algorithm Mt may depend on the outputs of M1(D), . . . ,Mt−1(D).
2The probability is over m(α, β) samples drawn from f and the randomness of the algorithm. 3We will use the acronym DP to refer to both the terms “differential privacy” and “differentially private”.
Which term we are using will be clear from the specific sentence.
Lemma 2.8 (Composition of DP [36, 37]). If M is an adaptive composition of differentially private algorithms M1, . . . ,MT then the following two statements hold:
1. If M1, . . . ,MT are (ε1, δ1), . . . , (εT , δT )-DP, then M is (ε, δ)-DP for ε = ∑T t=1 εt and δ = ∑T t=1 δt. 2. If M1, . . . ,MT are (ε0, δ1), . . . , (ε0, δT )-DP for some ε0 ≤ 1, then for any δ0 > 0, M is (ε, δ)DP for
ε = ε0 √ 6T log(1/δ0) and δ = δ0 + ∑T t=1 δt.
The first statement in Lemma 2.8 is often referred to as basic composition and the second statement is often referred to as advanced composition. We also make use of the fact that post-processing the output of a differentially private algorithm does not impact privacy. Lemma 2.9 (Post Processing). If M : Xn → Y is (ε, δ)-differentially private, and P : Y → Z is any randomized function, then the algorithm P ◦M is (ε, δ)-differentially private.
We define (ε, δ)-DP PAC learners and (ε, δ)-DP L-list-decodable learners as PAC learners and L-list-decodable learners that satisfy (ε, δ)-DP.

heading: 3 List-decodability and Learning Mixtures
text: In this section, we describe our general technique which reduces the problem of private learning of mixture distributions to private list-decodable learning of distributions. We show that if we have a differentially private list-decodable learner for a class of distributions then this can be transformed, in a black-box way, to a differentially private PAC learner for the class of mixtures of such distributions. In the next section, we describe private list-decodable learners for the class of Gaussians and thereby obtain private algorithms for learning mixtures of Gaussians.
First, let us begin with some intuition in the non-private setting. Suppose that we have a distribution g which can be written as g = ∑k i=1 1 kfi. Then we can view g as a k−1 k -corrupted distribution of fi for each i ∈ [k]. Any list-decodable algorithm that receives samples from g as input is very likely to output a candidate set F̂ which contains distributions that are close to fi for each i ∈ [k]. Hence, if we let K = { ∑ i∈[k] 1 k f̂i : f̂i ∈ F̂}, then g must be close to some distribution in K. The only remaining task is to find a distribution in K that is close to g; this final task is known as hypothesis selection and has a known solution [24]. We note that the above argument can be easily generalized to the setting where g is a non-uniform mixture, i.e. g = ∑k i=1 wifi where (w1, . . . , wk) ∈ ∆k.
The above establishes a blueprint that we can follow in order to obtain a private learner for mixture distributions. In particular, we aim to come up with a private list-decoding algorithm which receives samples from f to produce a set F̂ . Thereafter, we can construct a candidate set K as mixtures of distributions from F̂ . Note that this step does not access the samples and therefore maintains privacy. In order to choose a good candidate from K, we make use of private hypothesis selection [4, 17]. Formally, the following theorem establishes the reduction from private list-decodable learning to learning of mixtures. The proof can be found in Appendix C of the supplementary materials. Theorem 3.1. Let k ∈ N and ε, δ ∈ (0, 1). If F is (ε/2, δ)-DP L-list-decodable with mLIST samples then there is an (ε, δ)-DP PAC learner for k-mix(F) where the number of samples used is m(α, β, ε, δ) =
mLIST
( α
18 , β 2k , 1− α 18k , ε 2 , δ
) +O ( k log(Lk/α) + log(1/β)
α2 + k log(Lk/α) + log(1/β) αε
) .
This reduction is quite useful because it is conceptually much simpler to devise list-decodable learners for a given class F . In what follows, we will devise such list-decodable learners for certain classes and use Theorem 3.1 to obtain private PAC learners for mixtures of these classes.

heading: 4 Learning Univariate Gaussian Mixtures
text: Let G be the class of all univariate Gaussians. In this section we consider the problem of privately learning univariate Guassian Mixtures, k-mix(G). In the previous section, we showed that it is
sufficient to design private list-decodable learners for univariate Gaussians. As a warm-up and to build intuition about our techniques, we begin with the simpler problem of constructing private list-decodable learners for Gaussians with a single known variance σ2. In what follows, we often use “tilde” (e.g. M̃, Ṽ ) to denote sets that are meant to be coarse, or constant, approximations and “hat” (e.g. F̂ , M̂ , V̂ ) to denote sets that are meant to be fine, say O(α), approximations.

heading: 4.1 Warm-up: Learning Gaussian Mixtures with a Known, Shared Variance
text: In this sub-section we construct a private list-decodable learner for univariate Gaussians with a known variance σ2. A useful algorithmic primitive that we will use throughout this section and the next is the stable histogram algorithm. Lemma 4.1 (Histogram learner [15, 51]). Let n ∈ N, η, β, ε ∈ (0, 1) and δ ∈ (0, 1/n). Let D be a dataset of n points over a domain X . Let K be a countable index set and B = {Bi}i∈K be a collection of disjoint bins defined on X , i.e. Bi ⊆ X and Bi ∩ Bj = ∅ for i 6= j. Finally, let pi = 1 n · |D ∩ Bi|. There is an (ε, δ)-DP algorithm Stable-Histogram(ε, δ, η, β,D,B) that takes as input parameters ε, δ, η, β, dataset D and bins B, and outputs estimates {p̃i}i∈K such that |pi − p̃i| ≤ η for all i ∈ K with probability no less than 1− β so long as n = Ω ( log(1/βδ)
ηε
) .
For any fixed σ2 > 0 we define Gσ to be the set of all univariate Gaussians with variance σ2. For the remainder of this section, we let g = N (µ, σ2) ∈ Gσ and g′ ∈ Hγ(g). (Recall that g′ ∈ Hγ(g) means that g′ = (1− γ)g+ γh for some distribution h.) Algorithm 1 shows how we privately output a list of real numbers, one of which is close to the mean of g given samples from g′. The following lemma shows that the output of Algorithm 1 is a list of real numbers with the guarantee that at least one element in the list is close to the true mean of a Gaussian which has been corrupted. Note that the lemma assumes the slightly weaker condition where the algorithm receives an approximation to the standard deviation instead of the true standard deviation. This additional generality is used in the next section. Lemma 4.2. Algorithm 1 is an (ε, δ)-DP algorithm such that for any g = N (µ, σ2) and g′ ∈ Hγ(g), when it is given parameters ε, β, γ ∈ (0, 1), δ ∈ (0, 1/n), σ̃ ∈ [σ, 2σ) and dataset D of n i.i.d. samples from g′ as input, it outputs a set M̃ of real numbers of size |M̃ | ≤ 121−γ . Furthermore, with
probability 1− β there is an element µ̃ ∈ M̃ such that |µ̃− µ| ≤ σ, so long as n = Ω (
log(1/βδ) (1−γ)ε
) .
Algorithm 1: Univariate-Mean-Decoder(β, γ, ε, δ, σ̃,D). Input :Parameters ε, β, γ ∈ (0, 1), δ ∈ (0, 1/n), σ̃ and dataset D Output :Set of approximate means M̃ .
1 Partition R into bins B = {Bi}i∈N where Bi = ((i− 0.5)σ̃, (i+ 0.5)σ̃]. 2 {p̃i}i∈N ← Stable-Histogram(ε, δ, (1− γ)/24, β/2, D,B). 3 H ← {i : p̃i > (1− γ)/8} 4 If |H| > 12/(1− γ) fail and return M̃ = ∅ 5 M̃ ← {iσ̃ : i ∈ H} 6 Return M̃ .
We begin by gathering several simple claims whose proofs can be found in Appendix D.1. Let pi = PX∼g′ [X ∈ Bi] be the probability that a sample drawn from g′ lands in bin Bi. Let pi = 1n |D ∩Bi| be the actual number of samples drawn from g′ that have landed in Bi. Let j = dµ/σ̃c. It is a simple calculation to check that |jσ̃ − µ| ≤ σ. Thus, we would like to show that jσ̃ ∈ M̃ or, equivalently, that j ∈ H . A straightforward calculation shows that pj ≥ (1− γ)/3. Then a standard application of a Chernoff bound shows that many samples actually land in bin Bj , as asserted by the following claim. Claim 4.3. If n = Ω(log(1/β)/(1− γ)) then pj > (1− γ)/6 with probability at least 1− β/2.
Next, we claim that the output of the stable histogram approximately preserves the weight of all the bins and, moreover, that the output does not have too many heavy bins. The first assertion implies
that since bin Bj is heavy, the stable histogram also determines that bin Bj is heavy. The second assertion implies that the algorithm does not fail. Let {p̃i}i∈N be the output of the stable histogram, as defined in Algorithm 1. Claim 4.4. If n = Ω(log(1/βδ)/(1− γ)ε) then with probability 1− β/2, we have (i) |pi − p̃i| ≤ (1− γ)/24 for all i ∈ N and (ii) |H| = |{i ∈ N : p̃i > (1− γ)/8}| ≤ 12/(1− γ).
With Claim 4.3 and Claim 4.4 in hand, we are now ready to prove Lemma 4.2.
Proof of Lemma 4.2. We briefly prove that the algorithm is private before proceeding to the other assertions of the lemma.
Privacy. Line 2 is the only part of the algorithm that looks at the data and it is (ε, δ)-DP by Lemma 4.1. The remainder of the algorithm can be viewed as post-processing (Lemma 2.9) so it does not affect the privacy.
Bound on |M̃ |. For the bound on |M̃ |, observe that if |H| > 12/(1− γ) then the algorithm fails so |M̃ | ≤ 12/(1− γ) deterministically. Utility. Let g, g′, µ be as defined in the statement of the lemma. We now show that there exists µ̃ ∈ M̃ such that |µ̃ − µ| ≤ σ. Let j = dµ/σ̃c. For the remainder of the proof, we assume that n = Ω(log(1/βδ)/(1− γ)ε). Claim 4.3 asserts that, with probability 1 − β/2, we have pj > (1 − γ)/6. Claim 4.4 asserts that, with probability 1 − β/2, p̃j ≥ pj − (1 − γ)/24 and that |H| ≤ 12/(1 − γ). By a union bound, with probability 1− β, we have that pj > (1− γ)/8 and the algorithm does not fail. This implies that j ∈ H so jσ̃ ∈ M̃ . Finally, note that |jσ̃ − µ| ≤ σ̃/2 ≤ σ where the last inequality uses the assumption that σ̃ ≤ 2σ.
We can now use Lemma 4.2 to get a private list-decodable learner (Corollary 4.5) and then use this private list decodable learner together with our reduction (Theorem 3.1) to get an (ε, δ)-PAC learner for k-mix(G) (Theorem 4.6). The proof of Corollary 4.5 can be found in Appendix D. Corollary 4.5. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP L-list-decodable learner for Gσ with known σ > 0 where L = O ( 1
(1−γ)α
) , and the number of samples used is
mLIST(α, β, γ, ε, δ) = O ( log(1/βδ) (1−γ)ε ) .
Theorem 4.6. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP PAC learner for k-mix(Gσ) with known σ > 0 that uses m(α, β, ε, δ) = Õ
( k+log(1/β)
α2 + k log(1/βδ) αε
) samples.

heading: 4.2 Learning Arbitrary Univariate Gaussian Mixtures
text: In this subsection, we construct a list-decodable learner for G, the class of all univariate Gaussians. First, in Lemma 4.7, we design an (ε, δ)-DP algorithm that receives samples from g′ ∈ Hγ(g) where g ∈ G and outputs a list of candidate values for the standard deviation, one of which approximates the standard deviation of g with high probability. Then, in Lemma 4.8, we use Lemma 4.2 and Lemma 4.7 to design an (ε, δ)-DP list-decoder for G.

heading: 4.2.1 Estimating the variance
text: We begin with a method to estimate the variance. Here, we provide a high-level overview and relegate the details to the appendix. Suppose that g = N (µ, σ2) and g′ ∈ Hγ(g). Our goal is to obtain a multiplicative estimate of σ2. The key observation is as follows. If X1, X2 ∼ g′ then Y = (X1 −X2)/ √ 2 is distributed as (1− γ)2N (0, σ2) + (1− (1− γ)2)h for some distribution h. In particular, with probability roughly (1− γ)2, |Y | is itself a good estimate of σ. This observation allows us to proceed similarly to the proof of Lemma 4.2 with two changes. First, since our goal is a multiplicative approximation to σ2, we use bins of the form (2i, 2i+1] for i ∈ N. Second, given a dataset D = {X1, . . . , X2m}, we transform it to the dataset D′ = {|X1 −X2|/ √ 2, . . . , |X2m−1 −
X2m|/ √
2} and use the previously mentioned observation. The following lemma formalizes the guarantee that we can achieve. The proof can be found in Appendix D.2.
Lemma 4.7. There is an (ε, δ)-DP algorithm such that for any g = N (µ, σ2) and g′ ∈ Hγ(g), when it is given parameters ε, β, γ ∈ (0, 1), δ ∈ (0, 1/n) and dataset D of 2n i.i.d. samples from g′ as input, it outputs a set Ṽ of positive real numbers of size |Ṽ | ≤ 12(1−γ)2 . Furthermore, with probability
no less than 1− β there is an element σ̃ ∈ Ṽ such that σ ≤ σ̃ < 2σ, so long as n = Ω (
log(1/βδ) (1−γ)2ε
) .

heading: 4.2.2 A list-decodable learner for univariate Gaussians
text: We can now use Lemma 4.2 and Lemma 4.7 to design a list-decodable learner for G. This is done in a few steps. First, we obtain a list of candidate variances using Lemma 4.7. We know that one of these candidates is a good approximation to the true variance although we may not know which one. As a second step, we use the algorithm implied by Lemma 4.2 for all the candidate variances to get a list of candidate means. Since one of the candidate variances is a good estimate of the true variance, Lemma 4.2 promises that one of the candidate means is a good estimate of the true mean. Given a list of candidate variances and candidate means, we can create a list of all pairs of variances and means to obtain a list of distributions such that one is close to the true Gaussian. The guarantee is formalized in the following lemma and the proof appears in Appendix D.3. Lemma 4.8. There is an (ε, δ)-DP algorithm such for any g = N (µ, σ2) and g′ ∈ Hγ(g), when it is given parameters ε, α, β, γ ∈ (0, 1), δ ∈ (0, 1/n) and dataset D of n i.i.d. samples from g′ as inputs, it outputs a set M̂ of real numbers and a set V̂ of positive real numbers such that
|M̂ | ≤ 144 · (2 · d1/αe+ 1) (1− γ)3 and |V̂ | ≤ 12 · dlog1+α(2)e (1− γ)2 .
Furthermore, with probability no less than 1− β, we have the following:

heading: 1. ∃µ̂ ∈ M̂ such that |µ̂− µ| ≤ ασ

heading: 2. ∃σ̂ ∈ V̂ such that |σ̂ − σ| ≤ ασ
text: so long as n = Ω̃ (
log3/2(1/βδ) (1−γ)2ε
) .
We can now use Lemma 4.8 to get the following result. We defer the proof to Appendix D.4. Corollary 4.9. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP L-list-decodable learner for G where L = O ( 1
(1−γ)5α2
) and the number of samples used by the algorithm is
mLIST(α, β, γ, ε, δ) = Õ ( log3/2(1/βδ) (1−γ)2ε ) .
Finally, Corollary 4.9 and Theorem 3.1 immediately imply the following theorem. Theorem 4.10. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP PAC learner for k-mix(G) that uses m(α, β, ε, δ) = Õ ( k2 log3/2(1/βδ)
α2ε
) samples.

heading: 5 Learning Mixtures of Axis-Aligned Gaussians
text: In this section, we prove the following result, which is a formal version of Theorem 1.1. Theorem 5.1. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP PAC learner for k-mix ( Gd )
and the number of samples used by the algorithm is m(α, β, ε, δ) = Õ ( k2d log3/2(1/βδ)
α2ε
) .
The following lemma shows that we can construct an (ε, δ)-DP list-decodable learner for the class of d-dimensional axis-aligned Gaussians, Gd. We explain the high-level details of our approach here. Let g = ∏d i=1 gi ∈ Gd and g′ ∈ Hγ(g). For a sample X = (X1, . . . , Xd) ∼ g′, it follows that Xi ∼ g′i where g′i ∈ Hγ(gi). We can thus split our dataset by dimension and run our univariate private list-decodable learner (Corollary 4.9) on each dimension separately to get a total of d lists of univariate Gaussians. From the guarantee of Corollary 4.9, in the ith list there will be at least one Gaussian that is a good approximation to gi, and this holds for all i ∈ [d]. Finally, since g is an axis-aligned Gaussian (product distribution), we can take all possible combinations of the univariate distributions in the d lists to obtain a new list of axis-aligned Gaussians, one of which accurately approximates g. The details of the proof can be found in Appendix E.
Lemma 5.2. For any ε ∈ (0, 1) and δ ∈ (0, 1/n), there is an (ε, δ)-DP L-list-decodable learner for Gd where L = O ( d2
(1−γ)5α2
)d and the number of samples used by the algorithm is
mLIST(α, β, γ, ε, δ) = Õ ( d log3/2(1/βδ)
(1−γ)2ε
) .
We can now put together Lemma 5.2 and Theorem 3.1 to immediately get Theorem 5.1.
Acknowledgments and Disclosure of Funding
CL was supported by an NSERC postdoctoral fellowship. HA was supported by an NSERC Discovery Grant.

Review summaries:
As the title suggests, this paper gives algorithms for learning mixtures of $k$ Gaussians to within total variation distance $\alpha$. It uses a reduction to private list decodable learners from privately learning mixtures of distributions. The number of samples used is linear in $d$ and quadratic in $k$. The flow of the paper is as follows: first it gives algorithms for estimating mixtures of univariate Gaussians, then uses them to estimate mixtures of axis-aligned Gaussians. The main, non-trivial prior tool used in this paper is the private hypothesis selection algorithm. The algorithm for estimating mixtures of univariate Gaussians first involves creating a list-decodable learner for univariate Gaussians, followed by using the aforementioned reduction.

This paper considered the problem of learning a mixture of gaussians under DP constraint. The authors proposed an (exponential time) algorithm for learning univariate k-mixture of gaussian distributions with sample complexity k^2log^(3/2)(1/\delta)/alpha^2eps. They conjectured the extra k factor in the sample complexity is information theoretically unnecessary. The key of the algorithm is a reduction from the list-decodable learning to learning mixture distributions. Specifically, given a list decodable algorithm, one can enumerate all possible combinations of the k-mixtures and use a private hypothesis selection algorithm to find the most plausible k-mixture. They proposed a list decodable algorithm for learning gaussian distribution, which adopts a similar approach as [48].   For the multivariate gaussian setting, they considered the axis-aligned gaussian setting. They first obtain a list of distribution on each dimension, and take all possible combinations of the univariate distribution to form a large list of axis aligned gaussians. This leads to a multivariate gaussian k-mixture learning algorithm with sample complexity k^2dlog^(3/2)(1/delta)/alpha^2eps.