Sample-Efficient Private Learning of Mixtures of Gaussians
Authors: Hassan Ashtiani
Mahbod Majid
Shyam Narayanan
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Differential Privacy
Density Estimation
Mixtures of Gaussians
Sample Complexity
Primary area: privacy
TL;DR: We provide improved sample complexity bounds for learning mixtures of Gaussians with differential privacy, which are optimal for sufficiently large dimension or for one-dimensional Gaussian Mixtures..

Abstract: We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $kd^2 + k^{1.5} d^{1.75} + k^2 d$ samples suffice to learn a mixture of $k$ arbitrary $d$-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result (which required roughly $k^2 d^4$ samples) and is provably optimal when $d$ is much larger than $k^2$. Moreover, we give the first optimal bound for privately learning mixtures of $k$ univariate (i.e., $1$-dimensional) Gaussians. Importantly, we show that the sample complexity for learning mixtures of univariate Gaussians is linear in the number of components $k$, whereas the previous best sample complexity was quadratic in $k$. Our algorithms utilize various techniques, including the inverse sensitivity mechanism, sample compression for distributions, and methods for bounding volumes of sumsets.

Sample-Efficient Private Learning of Mixtures of Gaussians
Hassan Ashtiani McMaster University zokaei amwmmmatter.c.mm
Mahbod Majid MIT mahbod@mit..o edu
Shyam Narayanan Citadel Securities shyam. manayaaanngmaal....mmm. com
Abstract
We study the problem of learning mixtures of Gaussians with approximate differ- ential privacy. We prove that roughly kd2 k1.. k2 samples suffice learn a mixture of k arbitrary d-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result [AAL24b] (which required roughly & samples) and is provably optimal when d is much larger than k.. Moreover, we give the first optimal bound for privately learning mixtures of l univariate (i.e., 1-dimensional) Gaussians. Impor- tantly, we show that the sample complexity for learning mixtures of univariate Gaus- sians is linear in the number of components k, whereas the previous best sample complexity [AL2T was quadratic in k: Our algorithms utilize various techniques, including the inverse sensitivity mechanism [AD20b] AD20al HKMN23), sample compression for distributions [ABDH 20 and methods for bounding volumes sumsets.
Introduction
Learning Gaussian Mixture Models (GMMs) one of the most fundamental problems in algorithmic statistics. Gaussianity is common data assumption, and the setting of Gaussian mixture models motivated by heterogeneous data that can be split into numerous clusters, where each cluster follows Gaussian distribution. Learning mixture models is among the most important problems in machine learning [Bs066), and at the heart of several unsupervised and semi-supervised machine learning models. The study of Gaussian mixture models has had numerous scientific applications dating back to the 1890s [Pea94], and is a crucial tool modern data analysis techniques a variety of fields, including bioinformatics [KWB22]. anomaly detection [ZSM* 18), and handwriting analysis Bis06].
In this work, we study the problem of learning a GMM from samples. We focus on the density estimation setting, where the goal is to learn the overall mixture distribution up to low total variation distance. Unlike the parameter estimation setting for GMMs, density estimation can be done even without any boundedness or separation assumptions on the parameters of the components. In fact, known that mixtures of & Gaussians in d-dimensions can be learned up to total variation distance using (kkl /a²) samples [ABH 18).
Ensuring data privacy has emerged as an increasingly important challenge in modern data analysis and statistics. Differential privacy (DP) [DMNS06] is rigorous way of defining privacy, and is considered to be the gold standard both in theory and practice, with deployments by Apple [Teal7] Google [EPK14], Microsoft [DKY17), and the US Census Bureau IDLS+17] As is the case for many data analysis tasks, standard algorithms for learning GMMs leak potentially sensitive information about the individuals who contributed data. This raises the question of whether we can do density estimation for GMMs under the constraint of differential privacy.
Work done as student at MIT
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Private density estimation for GMMs with unrestricted Gaussian components is challenging task. In fact, privately learning a single unrestricted Gaussian has been the subject of multiple recent studies [AAK2] KMS 22b
23T HKMN23J Private learning of GMMs significantly more challenging, because even without privacy constraints, parameter estimation for GMMs requires exponentially many samples in terms of the number of components [MV10]. Therefore, it is not clear how to use the typical recipe of "adding noise" to the estimated parameters or "privately choosing" from the finiteddimensional space of parameters. Consequently, the only known sample complexity bounds for privately learning unrestricted GMMs are loose [AAL24b] AAL2II.
AL22 KMV22
Let us first formally define the problem of learning GMMs. We represent a GMM D E WyN Mx) by its parameters, namely {(w,, Me ),)) where w, 0, Σ, wy 1, M4 E RS, and Σ; is a positive definite matrix. In the following, GMM learning algorithm A receives a set of data points in I'' and outputs a (representation of) a GMM. The total variation distance between two distributions is drv (D, D) = SR (D(x) ((x) da
Definition 1.1 (Learning GMMs). For ax B (0, 1), say A learns GMMs with samples up to accuracy and failure probability , if for every GMM D, given samples X1...., ,x, i.dd D, it outputs (a representation of) GMM D such that drv D) with probability at least B.
and 3 are called the accuracy and failure probability, respectively. For clarity of presentation, we will typically fix the value of 3 (e.g., 3 = 1 1/3). The above definition does not enforce the constraint of differential privacy. The following definitions formalizes (approximate) differential privacy.
Definition 1.2 (Differential Privacy (DP) [DMNS06, DKM 06)). Let E, 6 2 O. randomized
algorithm A : X + O is said to be (e, differeetiill private ((E, 8DD))) if for any two neighboring datasets X,X' E xe and any measurable subset O C O,
P[A(X') E O] ef P[A(X) E 0]+
If the GMM learner AA of Definition 1.1 is (c, DDDP, we say that A privately learns GMMs. Formally, we have the following definition.
Definition 1.3 (Privately learning GMMs). Fix the number of samples n, dimension d and number of mixture components k. For a, B E (0, and 8 0, randomized algorithm A, that takes as input XI...., Xx, E Rd, (s, -pprivaty learns GMMs up to accuracy and failure probability B, if:
1. For any GMM 'D that is mixture of up to k Gaussians in d dimensions, if X (X1,..., },) i.s.d. ~ D, A(X1,..., ..)....,,,)) outputs a GMM D such that dry (D. D) < a with probability least 1 - 3 (over the randomness of the data X and the algorithm A).
2. For any neighboring datasets X, X' E (Rd)" (not necessarily drawn from any GMM) and any measurable subset O c O, P[A(X') E O] I e P[A((X) E 0 +
Finally, we assume a default value for 3 of 1 /33 meaning that if not stated, the failure probability / is assumed equal 1/3.
Our main goal in this paper is to understand the number of samples (as function of the dimension d, the number of mixture components k, the accuracy a, and the privacy parameters s, 6) that are needed privately and accurately learn the GMM up to low total variation distance.
1.1 Results
In this work, we provide improved sample complexity bounds for privately learning mixtures of arbitrary Gaussians, improving over previous work of [AAL2] AAL24b). Moreover, our sample complexity bounds are optimal in certain regimes, when the dimension is either or a sufficiently large polynomial in l and log J For general dimension d, we prove the following theorem.
Theorem 1.4. For any a, e, E (0, 1), E there exists an inefficient (),6)-DP algorithum that can learn mixture of k arbitrary full- full-dimensional Gaussians in d dimensions up to accuracy using the following number of samples:
kdl a
kd + 71. log 0.5 (1/8) - 1.1.5 log 1.5 (1/8)
12d
n
ae
α
We are slightly abusing the notation and using D(x) as the pdf of D at points x.

---

Notably, the mixing weights and the means can be arbitrary and the covariances of the Gaussians can be arbitrarily poorly conditioned, as long as the covariances are non-singulaf"
We remark that we omit the dependence on 3 (and assume by default a failure probability of 1 1/3.. However, it is well-known that one can obtain failure probability /3 with only multiplicative Olog 1/3) blowup in sample complexity, in a black-box fashion In fact, our analysis can yield even better dependencies on | in some regimes, though avoid too much complication, we do not analyze this.
For reasonably large dimension, i.e., d 2 k-a (1/6), this can be simplified Ô luff kul
ar
which is in fact optimal (see Theorem 1.6 Hence, we obtain the optimal sample complexity for sufficiently large dimension. Theorem also improves over the previous best sample complexity
upper bound of [AAL24b], which uses
δ 1=2dt + kdd log(1/8)
Add log(//0)
k2d a2g
+
aZe
a3e
samples. Our results provide a polynomial improvement in all parameters, but to simplify the comparison, if we ignore dependencies in the error parameter parameter and privacy parameters e, 8, we improve the sample complexity from k2d to kdf + k + k.1.5g1.75 note that our result is quadratic in the dimension whereas [AAL24 is quartic.
When the dimension is d = 1, we can provide improved result, which is optimal for learning mixtures of univariate Gaussians (see Theorem [.6 a matching lower bound).
Theorem 1.5. For any a, E, 5 E (0, k N, there exists inefficient ( -DD algorithm that can learn a mixture of arbitrary univariate Gaussians (of nonzero variance) up to accuracy a, using the following number of samples:
= k a
+ klog(1/0))
n = =
For privately learning mixtures of univariate Gaussians, the previous best-known result for arbitrary 62t llo2/"((166) samples [AAL2]]. Importantly, we are the first paper to show a²
Gaussians required θ that the sample complexity can be linear in the number of components.
Our work purely focuses sample complexity, and as noted in Theorems a.4 1.5 they do not have polynomial time algorithms. We note that the previous works of (AA22][AA222 also do not run in polynomial time. Indeed, there is reason to believe that even non- non-privately, it is impossible to learn GMMs polynomial time (in terms of the optimal sample complexity) [DKS17 BRST21 GVV22)
Finally, we prove the following lower bound for learning GMMs in any fixed dimension d.
Theorem 1.6. Fix any dimension d > number of components k > 2, any O, most sufficiently small constant c². and ö S (ae/ ddo()) Then, any (E, 6DP algorithm that can learn a mixture of k arbitrary full full-dimensional Gaussians in d dimensions up total variation distance a, with probability at least 2/3, requires at least the following number of samples:
kdd
kdf
llog(115)
a2
aE
aE
Note that for d 1, this matches the upper bound of Theorem 1.5 thus showing that our univariate result is ncar-optimal in all parameters a, E, Moreover, our lower bound refutes the conjecture of [AL2T]] which conjectures that only θ [ az
log(1/8) samples needed in the univari-
ate case and θ kdd note that our lower bound asymptotically differs from the conjectured bound in [AL21 only when is extremely small.
kdd +
log(1/8) samples are needed the d-dimensional case. However, we
a as e
'For clarity of presentation, assume the covariance matrices are singular. However, extending results to degenerate matrices straightforward.
"To obtain success probability 3 with O(n log 1/8) samples, we repeat the procedure T = O 1/3) times on independent groups of n samples each, to get I' estimates D....., Dr. and by a Chernoff bound, at least 51% of the estimates are within total variation distance a of the true mixture D. So. by choosing an
estimate that is within 20 of at least 51% % of the estimates, is still within 3a total variation distance of D.
3

---

1.2 Related work
In the non-privenn non-private setting, the sample complexity of learning unrestricted GMMs with respect to total variation distance (a.k.a. density estimation) known to @(dd²) /a²) [BM18 ABH+18) 18), where
the upper bound is obtained by the so-called distributional compression schemes.
In the private setting, the only known sample complexity upper bound for unrestricted GMMs [AL244]] is roughly k log(1/8)((a'e), which exhibits sub-optimal dependence on various parameters This bound is achieved by running multiple non-private list-decoders and then pri- vately aggregating the results. For the special case of axis-aligned GMMs, an upper bound of ( / (a²E) is known [AAL21]. These are the only known results even for privately learning (unbounded) univariate GMMs. In other words, the best known upper bound for sample complexity of privately learning univariate GMMs has quadratic dependence on k.
In the related public-private setting [BKS22 BBC+23 it is assumed that the learner has access to some public data. In this setting, BBC 23 show that unrestricted GMMs can be learned with a moderate amount of public and private data.
Assuming the parameters of the Gaussian components (and the condition numbers of the covari- ance matrices) are bounded, one can create a cover for GMMs and use private hypothesis selec- tion [BSKW]] or the private minimum distance estimator [AAK2] to learn the GMM. On the flip side, [ prove a lower bound on the sample complexity of learning GMMs, though their lower bound is weaker than ours and is only against pure-DP algorithms.
The focus of our work is on density estimation. A related problem is learning the parameters a GMM, which has received extensive attention in the (non-private) literature (e.g.. [Das99] MVIO
BSI0 LM2 BDJ 22, [L22] among many other papers). To avoid identifiability issues, one has to assume that the Gaussian components are sufficiently separated and have large-enough weights. In the private setting, the early work of [NRS07] demonstrated a privatized version of [VW044] for learning GMMs with fixed (known) covariance matrices. The strong separation assumption (of ((K1/2)) between the Gaussian components in [NRS07] was later relaxed to a weaker separation assumption [CCAd+ 23). A substantially more general result for privately learning GMMs with unknown covariance matrices was established in [KSSU19] based on a privatized version of [MMOS. Yet, this approach also requires a polynomial separation (in terms of k) between the components, as well as a bound on the spectrum of the covariance matrices. [CKM 21] weakened the separation assumption of [SSUU99 and improved over their sample complexity. This result is based on generic method that learns GMM using a private learner for Gaussians and a non-private clustering method for GMMs. Finally, [AAL23 designed an efficient reduction from private learning of GMMs to its non-prin non-private counterpart, removing the boundedness assumptions on the parameters and achieving minimal separation (e.g., by reducing to MVVIO). Nevertheless, unlike density estimation, parameter estimation for unrestricted GMMs requires exponentially many samples in terms [MV10.
A final important question is that of efficient algorithms for learning GMMs. Much of the work on learning GMM parameters focuses on computational efficiency (c.g.. [MVI) BSI0 LM2T 2DJ+22 LL22)), as does some work on density estimation (e.g., ICDSS14 ADLS17)). However, under some standard hardness assumptions, it is known that even non non-privately learning mixtures of
k d-dimensional Gaussians with respect to total variation distance cannot be done in polynomial time as function of It and d [DKS17 BRST21 GVV22
extended the result of [AA224b] for learning unrestricted GMMs to the agnostic (i.e., robust) setting. In contrast, our algorithm works only in the realizable (non-robust) setting. Moreover, [AAL24a] slightly improved the sample complexity result of [AAL24b] from (log(1/ (1)) (Eaa)) to Ó(log(1/0)k3d (d)))dd((eaa))) (Eaa)). The sample complexity of our approach is still significantly better than [AL24a|] in terms of all ceaimnters-ssiillee to the way it improved over [AAL24b).
Addendum. In a concurrent submission, AAL24a
Mooe precisely, the upper hound is Ō [Rd
a +
hd? log(1/8)
(d a +
62d? a²
a²c

---

2 Technical overview and roadmap
We highlight some of our conceptual and technical contributions. We mainly focus on the high- dimensional upper bound, and discuss the univariate upper bound at the end.
2.1 Reducing to crude approximation
Suppose we are promised bound on the means and covariances of the Gaussian components, i.e., R I & D; & R. and ||ull2 S R for all i E [k]. In this case, there is in fact a known algorithm. using private hypothesis selection IS AAK2I that can privately learn the distribution using only O kdd log R
a² + kd Ing R
samples. Moreover, with more careful application of the hypothesis
06
selection results (see Appendix D). we can prove that result holds even if (ux, E,) are possibly
unbounded, but we have some very crude approximation. By this, we mean that if for each i [k] we
know some Eg such that # E. < Ex x R- Σg then it suffices to have n O kd log R a²
Adl log R ac
samples to learn the full GMM in total variation distance.
Our main goal will be to learn every covariance E, with such an approximation, for R poly (k; d, a 2), that log R can be hidden in the Ô factor. To explain why this goal is sufficient, suppose we can crudely learn every covariance E; with approximation ratio R. using n' samples.
We then need fad log R
log R bution using hypothesis selection, so the total sample complexity is Ô (n' + kit log R kd Ing R a²
kdR
additional samples to learn the full distri- kiff
Hence, we will aim for this easier goal of crudely learning each covariance, for both Theorem 1.4 and Theorem 1.5 using as few samples n' as possible. We will also need to approximate each mean μ4 though for simplicity we will just focus on covariances in this section.
2.2 Overview of Theorem 1.5 for univariate GMMs
The main goal will be to simply provide rough approximation to the set of standard deviations σ; = Vi, as we can finish the procedure with hypothesis selection, as discussed above.
Bird's eye view: Say are given a dataset X = (X1. Xn): note that every X, K since are dealing with univariate Gaussians. The main insight is to sort the data in increasing order (i.c., reorder so that X, < X2 < ... < Xn) and consider the unordered multiset of successive differences (X2 - X1, X3 - X2...., X, - -x,-1) One can show that a single datapoint X, is changed, then the set of consecutive differences (up permutation) does not change in more than 3 locations (see Lemma F.3 for a formal proof).
We then apply standard private histogram approach. Namely, for each integer E Z, we create corresponding bucket B., and map each X,+1 - X, into B, 2 I X,,+1 - X, < 20-1 If some mixture component had variance Σ, of we should expect significant number of Xj+1 - Xÿ to least be crudely close o; such for the Xj drawn from the 7th mixture component. So, some corresponding bucket should be reasonably large. Finally, by adding noise to the count of each bucket and taking the largest noisy counts, we will successfully find an approximation to all variances.
In more detail: For each (possibly negative) integer let ca be the number of indices such that 2n < Xj+1 X,, < 20+1_ We will prove that, if the weight of the 7th component in the mixture is Wt and there are points, then we should expect at least O(w; n) indices j to be in bucket with 2 within a poly(n) multiplicative factor of the standard deviation o; (see Lemma F.3). The point of this observation is that there are at most O(log n) buckets B, with 2 between [nly and
O(a,), but there are least 2(w; n) indices mapping to one of these buckets. So by the Pigeonhole principle, one of these buckets has at least ? poly(n] < 2d O(o,).
wenn indices, i.e., Ca 2 Ω log
wyy- for some with Iog
Moreover, we know that if we change single data point Xj. the set of consecutive differences (Xi+1 X,) after sorting changes by at most So, if we change single X,, at most 3 of the counts ca can change, each by at most 3.
5

---

Now, for every integer a, draw noise value from the Truncated Laplace distribution (see Defini- tion A..2 and Lemma A.3) and add it c, to get noisy count é. The details of the noise distribution are not important, but the idea is that this distribution is always bounded by O ( log }). Moreover, the Truncated Laplace distribution preserves (s, 6 This means that the counts {Eo Jaez will have (O(s), ((6))-DP, because the true counts Ca only change minimally across adjacent datasets.
Our crude approximation to the set of standard deviations will be the set of 2 such that e₂ exceeds some threshold which is large multiple of 1
C log 3. In 2 Ô k ( and the weight w, 2 a/k, ar
Tog exceeds a large multiple of 1 log -. So, for each S with weight it is not hard to verify that wyn
o. < < O(a,) will have count C. significantly exceeding the threshold, and thus noisy count ča exceeding the threshold. This will be enough to crudely approximate the values o, coming from large enough weight. We can ignore any component with weight less than a//k, as even if all but one of components have such small weight, together they only contribute a weight. So, we can ignore them and it will only cost us ar total variation distance, which we can afford.
at least a/k, some corresponding a with polyin]
Putting everything together: In summary, we needed δ (1/8(1/88) samples to approximate each covariance (of sufficient weight) up to a poly(n) multiplicative factor. By setting R = poly(n) and using the reduction described in Section 2.1 we then need an additional O
A k n
klog ae
samples.
a²
If we set n Ō (~ +
{log(1/8) we will obtain that n 2 Ô llg(11 oiE
+ +0
llog m
+
slog n
as
06
which is sufficient to solve our desired problem in the univariate setting.
Note that this proof relies heavily on the use of private histograms and the order of the data points in the real line. Therefore, it cannot be extended to the high-dimensional setting. We will use completely different approach to prove Theorem I.4
2.3 Overview of Theorem 1.4 for general GMMs
As in the univariate case, we only need rough approximations of the covariances. We will learn the covariances one at a time: in each iteration, we privately identify a single covariance Σn which crudely approximates some covariance Σ; in the mixture, with (s/ (s/vk loklog(1/)) 8/ B/K)-DP. Using the well-known advanced composition theorem (see Theorem A.I) we will get an overall privacy guarantee of (s, DD.. However, to keep things simple, we will usually aim for (s, 5)DP when learning each covariance, and we can replace s with e/ / log(1/8) and ó with 8/k at the end.
natural approach for parameter estimation, rather than learn >; one at time, learn all of the covariances together. However, we believe that this approach would cause the sample complexity to multiply by a factor of k. compared to learning single covariance. The advantage of learning the covariances one at time is that we can apply advanced composition: this will cause the sample complexity to multiply by roughly /k log(1/5) instead.
In the rest of this subsection, our main focus is to identify a single crude approximation E.
Applying robustness-tus -triissss-------ryy------ The first main insight is to use the robustness- to-pivvac con- version of Hopkins et al. [HKMN23] (see also (AUZ2]). ). Hopkins et al. prove a black-box (but not computationally efficient) approach that can convert robust algorithms into differentially private algorithms, using the exponential mechanism and a well-designed score function. This reduction only works for finite dimensional parameter estimation and therefore cannot be applied directly to density estimation. On the other hand, parameter estimation for arbitrary GMMs requires exponentially many samples in the number of components [MV10. However, we will demonstrate that this lower bound does not hold when we only need a very crude estimation of the parameters.
The idea is the following. For a dataset X [XI....,X,)) let S = S(,, X) be a score function, which takes in dataset X of size n and some candidate covariance Σ, and outputs some non-negative
integer. At high level, the score function S(,, X) will be the smallest number of data points t that we should change in X to get to some new data set X' with a specific desired property: X' should "look like" sample generated from mixture distribution with Σ being the covariance of

---

one of its components namely, component with significant mixing weight. One can define "looks like" in different ways, and we will adjust the precise definition later. We remark that this notion of score roughly characterizes robustness, because if the samples in X were truly drawn from a Gaussian mixture model with covariances {E. )=,)/=>> we should expect S(E,, X) to be (since X should already satisfy the desired property), but if we altered k data points, the score should be at most k. The high-level choice of score function is somewhat inspired by a version of the exponential mechanism called the inverse sensitivity mechanism [AD20b] AD20a), though the precise way of defining the score function requires significant care and is an important contribution of this paper.
The robustness-to- to-iivacy framework of [HKMN23], tailored to learning a single covariance, implies the following general result, which holds for any score function S following the blueprint above. For now, we state an informal (and slightly incorrect) version.
Theorem 2.1 (informal see Theorem C.3 for the formal statement). For any 1 E [0, 1), and any dataset X of size n, define the value V2[(X to be the volume (i.e., Lebesgue measure) of the set of covariance matrices E (where the covariance can be viewed as a vector by flattening, such that S(E,)) 5n.70
Fix a parameter 1j < 0.1, and suppose that for any dataset X of size n such that Va/2(2 is strictly positive, the ratio of volumes V, (T) is at most some K (which doesn' 't depend on X). Then, if n 2 log K there is a differentially private algorithm that can find covariance E of low score (i.e.. 6.7 where X( S 17. n2) using n samples.
Note that Theorem 2.1 does not seem to say anything about whether X comes from a mixture of Gaussians. However, we aim to instantiate this theorem with score function that is carefully designed for GMMs. Recall that we want S(E X) to capture the number of points in X that need to be altered to make look like a data set that was generated from a mixture, with Σ being the covariance of one of the Gaussian components. In other words, S(Ê,X; X) should be small if (and hopefully only if) a "mildly corrupted" version of X includes a subset of points that are generated from a Gaussian with covariance Σ. At the heart of designing such a score function, one needs to come up with form of "robust Gaussianity tester" that tells whether a given set of data points are generated from a Gaussian distribution. Aside from this challenge, the volume ratio associated with the chosen score function needs to be small for every dataset X otherwise the above theorem would require a large n (i.e,, number of samples). These two challenges are, however, related. If the robust Gaussianity tester has high specificity- i.e., rejects most of the sets that are not generated from (corrupted) Gaussian then the volume ratio is likely to be small (i.e., a smaller number of candidates Σ would receive a good/low score).
First Attempt: We first try an approach which resembles that of (HKMN23 for privately learning single Gaussian. We "define" S(Σ, X) as the smallest integer t satisfying the following property: there exists subset Y C X of size n/ kk such that we can change t data points from Y to get to Y', where Y' "looks like" i.idd samples from Gaussian with some covariance Σ that is "similar to" Σ. The choice of Y having size n//k / is motivated by the fact that each mixture component, on average, has n/A l: data points in X.
The notions of "looks like" and "similar to" of course need to be formally defined. We say K is "similar to" Σ (or Σ A Σ) if they are spectrally close, i.c., 0.5E < Σ x 2E. We say that Y' "looks like" samples from Gaussian with covariance Σ if some covariance estimation algorithm predicts that Y' came from a Gaussian with covariance Σ. The choice of covariance estimation algorithm will be quite nontrivial and ends up being key ingredient in proving Theorem 1.4
To apply Theorem 2.1
we first set 7) = c/k for some small constant c. We cannot set a larger value 7, because if we change t ss n/k data points, we could in fact create totally arbitrary new Gaussian component with large weight. Since there is no bound on the eigenvalues of the covariance matrix, this could cause the volume Vy (X) to be infinite. The main question we must answer is how bound the volume ratio V,, (X)/Vn y/22 (X). To answer this question, we first need to understand what it means for S(ε, X) < 11 n. If S(E, X) < <1- n, then there exists a corresponding set Y X of size n n/k, and we can change 77 n = c- Y points from Y to get to some Y' which looks like samples from a Gaussian with covariance Σ x Σ. Thus, Y looks like c-corrupted samples from such Gaussian (i.c..
7

---

a fraction of the data is corrupted). This motivates using robust covariance estimation algorithm: indeed, robust algorithms can still approximately learn Σ even a small constant fraction of data is corrupted, so for any Y C X, we expect that no matter how we change a fraction of Y to obtain Y', the robust algorithm's 's covariance estimate should not change much. So, for any fixed Y, the set. of possible Σ, and thus the set of possible Σ, should not be that large.
In summary, to bound (X) versus (X), there are at most (n,7k) choices for Y C X in the former case, and at least choice in the latter case (since we assume (2//((X)= > 0 in Theorem 2.I.. Moreover, for any such Y, the volume of corresponding Σ should be exponential in d2 (either for (X) or (x)) since the dimensionality of the covariance roughly d², So, this suggests that the overall volume ratio is at most (n//k) eedl)) Since log (n//k) = (n/k) log if we plug into
Theorem 2.1 it suffices to have n 2 (n/k) logkk+ k+d2 Unfortunately this is impossible unless e 2 log k. s-(e/k)
These ideas will serve as good starting point, though we need to improve the volume ratio analysis. To do so, we also modify the robust algorithm, by strengthening the assumptions on what it means for samples to "look like" they came from a Gaussian.
Improvement via Sample Compression: To improve the volume ratio, we draw inspiration from a technique called sample compression, which has been used in previous work on non-private density estimation for mixtures of Gaussians [ABH+ 18 ABDH 20). The idea behind sample compression is that one does not need the full set Y to do robust covariance estimation; instead, we look at smaller set of samples. For instance, if Y C X looks like e-corrupted samples from a Gaussian of covariance Σ x Σ, we expect that a random subset of Y also looks like c-corrupted samples from such a Gaussian. Moreover, long as one uses m 2 (d) corrupted samples from Gaussian, we can still (inefficiently) approximate the covariance. This motivates us to modify the robust algorithm as follows: rather than just checking whether Y looks like c-corrupted samples from Gaussian of covariance roughly Σ, we also test whether an average subset Z C Y of size m does as well. Therefore, if ΣΣ has low score, there exists a corresponding set C X of size m, and there are only (*) I e log choices for Z. So, now it suffices to have n 2 m n+d which will give us a bound e<(c/k)
of ((dk/s)) as long as S O(d)). Importantly, we still check the robust algorithm on Y of size roughly n/K which allows us to keep the robustness threshold 1) at roughly e/k:
There is one important caveat that for each subset Z, there is distinct corresponding covariance E. and the volume of Σ- = E can change drastically as E changes. (For instance, the volume of E R T Σ is (eddd) times as large the volume of Σ x Σ. Since we have no bounds the possible covariances, T could be unbounded.) For our volume ratio to actually be bounded by about (*) e edd), we want the volume of Σ ~ Σ to stay invariant with respect to Σ. This can be done by defining "normalized volume" where the normalization is inversely proportional the determinant (see Appendix C.I for more details). The robustness-to to-privacy conversion (Theorem 2.1 will still hold.
While the hound of ((Pk/e) seems good, we recall that this bound is merely the sample complexity for (e, dD- crude approximation of single Gaussian component. As discussed at the beginning of this subsection, to learn all k Gaussians, we actually need (e/ / log(1/ (1/5), 6/k)-DP, rather than (s, DD.. when crudely approximating a single component. This will still end up leading to a significant improvement over previous work (AAL,24b), but we can improve the volume ratio even further and thus obtain even better sample complexity.
Improving Dimension Dependence: Previously, we used the fact that the volume of candidate Σ (corresponding to a fixed Z) was roughly exponential in d2 for either (X) or VX)X), so the ratio should also be roughly exponential in d², Here, we improve this ratio, which will improve the overall volume ratio.
First, we return to understanding the guarantees of the robust algorithm. It is known that, given m 2 Odd samples from Gaussian of covariance E, we can provide an estimate E such that (1 ((d/m))) & ' (1- - ((Vdd/m)) As above, need to solve this even if fraction of
8

---

samples are corrupted. While this can cause the relative spectral error to increase from 1 1 (dddm) to + O(c+ + Vd/m), for now let us ignore the additional factor.
If (X) > O, then there is some covariance Σ and some set Y of size n/k, where the robust algorithm thinks Y looks like (possibly corrupted) Gaussian samples of covariance >. So, every Σ such that 0.5Σ x Σ き 2Σ has score of most r1/2 n. This gives us lower bound on (x)= We now want to upper bound vi (x). If S(E, < 1pn, we still have that the robust algorithm thinks some Y looks like Gaussian samples of covariance Σ,, where 0.55 전 Σ < 2 But now, we use the additional fact that for some Z Y of size m, the robust algorithm on Z finds covariance E. By the accuracy of the robust algorithm, Σ and Σ should be similar, i.e. (1 O(yd/m))
Σ < (1 - O(vd/ m)) Σ (where we ignored the c factor). Thus, there exists some Z C X of size m and a I < 2(1 O(Vd/m))E.
Σ corresponding to Z, such that 0.5(1 (lvddm))))))
Therefore, from n/2 to 77. we have dilated the candidate set of Σ by a factor of O( dd/m) in the worst case, and we have at least choice in the n1/2 case but at most (.)) choices in the n case.
Thus, the overall volume ratio is at most (m)) (1 O (() = O(m logn (. Vd/mm, since the
dimension of Σ roughly d' Consequently, now suffices to have n 2 m logondd / setting =((/k)
m d5/3 gives us an improved bound of (dP/3k/e) for learning single E,.
There are some issues with this approach: most notably, we ignored the fact that the spectral error is really c+ /d/m rather than /d/m. However, the robust algorithm can do better than just estimating up to spectral error + / /d/me m: it can also get improved Frobenius error. While we will not formally state the guarantees on the robust algorithm here (see Theorem B33 B.3 for the formal statement),
the main high-level observation is that if the robust estimator E can be 1 + e times as large as the true covariance in only (1) directions then for an average direction the ratio of Σ to Σ will be 1 1 O(Vd/m) We can utilize this observation to bound the volume ratio, using some careful e-net arguments (this is executed in Appendix C.3 Our dimension dependence of d will increase to d?/4, though this still improves over the previous de bound.
We will formally define the score function S(,, X) in Appendix R.1 and fully analyze the application of the babustness-to-privan conversion, as outlined here, in Appendix F.2
Accuracy: One important final step that we have so far neglected is ensuring that any Σ of low score must be crudely close to some Σ, if X is actually drawn from a GMM. We will just focus on the case where S(E, X) = O, so some Y C X of size n/k looks like a set of samples from Gaussian with covariance Σ. If the samples Y all came from the i-th component of the GMM, then it will not be difficult show E is similar E,, The more difficult case is when data point in Y are generated from several components.
However, if > 20, then YY| 2 220kd, which means that by the Pigeonhole Principle. least 20d points in Y come from the same mixture component (Mi E.). We are able to prove that, with high probability over samples drawn from single Gaussian component N(H, 2, that the empirical covariance of any subset of size at least 20d is crudely close to Σ, (see Corollary B.5). As a result, when verifying that subset Y "looks like" i.i.d. Gaussian samples with covariance Σ. can ensure that the empirical covariance of every subset Z C Y of size 20d is crudely close to Σ. Thus, if the score S(,,X) X) = 0, Σ is close to E, which is crudely close to some Σn
We also formally analyze the accuracy in Appendix
Putting everything together: To crudely learn a single Gaussian component with (c, 5)-DP, we will need n 2 ((d//k//e) samples to find some covariance Σ with low score, and we also need 2 2lk2d) so that covariance E of low score is actually a crude approximation to one of the real mixture components. To crudely approximate all components, we learn each Gaussian component with (e/ / 7: log(1/5), JDP. The advanced composition theorem will imply that repeating this procedure & times the same data (to learn all & components) will be (s, -DP. Hence, by replacing

---

from the with e/ (1/6)) we get that it suffices for Ô ///0///2 /lug11/6 k2d
we need to crudely learn all of the covariances. Finally, we can apply the private hypothesis selection technique
(recall Section 2.1 which requires an additional Ô d' +
d'k
..ombining these terms will give DE
the final sample complexity.
We remark that the sample complexity obtained above is actually better than the complexity in Theorem 14 There are two reasons for this. The first is that we have been assuming each com- ponent has weight 1/k, meaning it contributes about n/k data points. In reality, the weights may be arbitrary and thus that one can actually ignore any component with less than a/k weight, we want to solve den- sity estimation up total variation distance This will multiply the sample complexity terms δ /7/4///9 (10g
components may have much fewer data points. However, it turns out
k needed for crude approximation, by a factor of 1/a. Finally, the
informal Theorem slightly inaccurate, and the accurate version of the theorem will end up adding the additional term of h log" Along with the final term Ô d d*k 06
as
private hypothesis selection, these terms will exactly match Theorem I.4
2.4 Roadmap
In Appendix A we note some general preliminary results. In Appendix B. we note some additional
preliminaries robust learning of single Gaussian. In Appendix C we discuss the robustness-
to-privacy conversion and prove some volume arguments needed for Theorem I.4] In Appendix D
explain how reduce the crude approximation setting, using private hypothesis selection. In Appendix
[] we design and analyze the algorithm for multivariate Gaussians, and prove Theorem 1.4
In Appendix F we design and analyze the algorithm for univariate Gaussians, and prove Theorem 1.5
In Appendix
G we prove Theorem I.6 Finally, Appendix H proves some auxiliary results that we
state Appendices and
Limitations
Our results are on theoretical guarantees on the sample complexity of privately learning Mixtures of Gaussians. We do not provide any efficient practical algorithms, and focus statistical guarantees. We also do not discuss how to set the parameters and accuracy guarantees for practical applications, this is question best left to practitioners. Finally, assume each sample is i.i.d. drawn from a Gaussian Mixture Model distribution, though we remark that we use a 'robustness-to tobusttess-to-privacy"" framework that will automatically make algorithm robust to roughly a/ fraction of corruptions.
Hassan Ashtiani was supported by an NSERC Discovery grant. Shyam Narayanan was supported by an NSF Graduate Fellowship and a Google Fellowship.
Acknowledgements.
References
[AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-diimensioal gaussians. In Algorithmic Learning Theory, pages 185-216. PMLR, 2021.
[AAL21] Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. Privately learning mixtures of axis-aligned gaussians. Advances in Neural Information Processing Systems, 34:3925- 3938, 2021.
[AAL23] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In International Conference on Machine Learning, pages 1018-1040. PMLR, 2023.
[AAL224a] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Agnostic private density estimation for gmms via list global stability. arXiv e-prints, pages arXiv-2407, 2024.
10

---

[AAL24b] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with polynomial number of samples. In Algorithmic Learning Theory, pages 1-27. PMLR, 2024.
[0B Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67(6): 42, 2020.
[ABH+18] Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehra- bian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. Advances in Neural Information Process- ing Systems, 31, 2018.
[ABMI8] Hassan Ashtiani, Shai Ben-David, and Abbas Mchrabian. Sample-cfficient learning of mixtures. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[AD20a] Hilal Asi and John C Duchi. Instance-optimality differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems, 33:14106-1411 17, 2020.
[AD20b] Hilal Asi and John C Duchi. Near instance-optimaality in differential privacy. CoRR, abs/2005.10630, 2020.
[ADLS17) Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Sample-optimal density estimation in nearly-linear time. In Proceedings of the Twenty-Fightt Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1278-1289. SIAM, 2017.
[AKT 23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating gaussian: Efficient, robust, and optimal. In Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, pages 483-496, 2023.
[AL22] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pages 1075-1076. PMLR, 2022.
[AM05] Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distribu- tions. In International Conference on Computational Learning Theory, pages 458 469. Springer, 2005.
[AS721] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
[AUZ23] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. In International Conference on Machine Learning, pages 1121-1146, PMLR, 2023.
[BBC+23] Shai Ben-David, Alex Bie, Clément L. Canonne, Gautam Kamath, and Vikrant Singhal. Private distribution learning with public data: The view from sample compression. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[BD]+22] Ainesh Bakshi, Iaas Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh S Vempala. Robustly learning mixtures of k arbitrary gaussians. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1234 1247, 2022.
[Bis06] Christopher M. Bishop. Patlern Recognition and Machine Learning. Springer, 2006.
[BKS22] Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. Advances in Neural Information Processing Systems, 2022.
[BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous lwe. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694-707, 2021.
11

---

[BS10] Mikhail Belkin and Kaushik Sinha. Polynomial leamnin of distribution families. In 2010 IEEE Sist Annual Symposium on Foundations of Computer Science, pages 103-112. IEER, 2010.
[BSKW19] Mark Bun, Thomas Steinke, Gautam Kamath, and Zhiwei Steven Wu. Private hypothe- sis selection. Advances in Neural Information Processing Systems, 32, 2019.
[BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 1-10, 2014.
[CCAd+23] Hongjie Chen, Vincent Cohen-Addad, Tommaso d' d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel. Private estimation algorithms for stochastic block models and mixture models. arXiv preprint urXiv:2301.0455 2023.
[CDSS14] Siu-On Chan, Ilias Diakonikolas, Rocco A Servedio, and Xiaorui Sun. Efficient density estimation via piecewise polynomial approximation. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pages 604 613, 2014.
[CKM+21] Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. Differentially-privall clustering of easy instances. In International Conference on Machine Learning, pages 2049-2059. PMLR, 2021.
[Das99] Sanjoy Dasgupta. Learning mixtures of gaussians. 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 634-644, IEEE, 1999.
[DK22] Ilias Diakonikolas and Daniel M. Kane. Algorithmic High-Dimensional Robust Statis- fics. Cambridge University Press, 2022.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology Beapllggy-ERORRYPPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg. Russia, May 28-June 1, 2006. Proceedings 255, pages 486-503. Springer, 2006.
[DKS17] Ilias Diakonikolas, Daniel Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensions gaussians and gaussian mixtures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS $17, pages 73-84, 2017.
[DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances Neural Information Processing Systems (NeurIPS), pages 3571-3580, 2017.
[DLS*17] 17] Aref N. Dajani, Amy D. Lauger. Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin Machanavajjhala, Simson L. Garfinkel, Scot A. Dahl, Matthew Graham, Vishesh Karwa, Hang Kim, Philip Lelere, Ian M. Schmutte, William N. Sexton, Lars Vilhuber, and John M. Abowd. The modernization of statistical disclosure limitation at the u.s. Census Bureau, 2017. In the September 2017 meeting of the Census Scientific Advisory Committee, 2017.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory Cryp- tography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (5-4):211-4077 2014.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable sivaac-preseering ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1054- 1067, 2014.
12

---

[GDGK20] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in upproximate differential privacy. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 89-99. PMLR, 2020.
[GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan, Continuous LWE is as hard as LWE & applications to learning gaussian mixtures. In 63rd IEEF Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 2022, pages 1162-1173. IEEE, 2022.
[HKMN23] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robust- ness implies privacy in statistical estimation. In Symposium on Theory of Computing. pages 497-506, 2023.
[KMS22a] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and generalized fingerprinting lemma. In Advances in Neural Information Processing Systems 35, NeurlPS '22 2022.
(MMS+22b) Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally-effine In Conference on Learning Theory, pages 544-572. PMLR, 2022.
estimator for unbounded gaussians.
[KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Conference on Learning Theory, pages 723-777. PMLR, 2022.
[KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated gaussians. Advances in Neural Information Processing Systems, 32, 2019.
[KV18] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings the Science, ITCS 18, pages 44:1-44:9, Dagstuhl, Germany, 2018. Schloss Dagstuhl- Leibniz-Zentrun fuer Informatik.
the 9th Conference on Innovations in Theoretical Computer
[LKWB22] Ta-Chun Liu, Peter N Kalugin, Jennifer L Wilding, and Walter Bodmer. Gmmchi: gene expression clustering using gaussian mixture modeling. BMC bioinformatics, 23(1):457, 2022.
[LL22] Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polyno- mial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1248-1261. 2022.
[LM21] Allen Liu and Ankur Moitra. Settling the robust learnaiility of mixtures of gaussians. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 518-531, 2021.
[MH08]
Arakaparampil M Mathai and Hans J Haubold. Special functions for applied scientists, volume 4. Springer, 2008
[MV10] Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In 2010 IEÉE 51st Annual Symposium on Foundations of Computer Science, pages 93-102. IEEE, 2010.
[Nar23] Shyam Narayanan. Better and simpler lower bounds for differentially private statistical estimation. arXiv preprint arXiv:2310.06289, 2023.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
[Pea94] Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London, 1894.
13

---

[PH24] Victor S Portella and Nick Harvey. Lower bounds for private estimation of gaus- sian covariance matrices under all reasonable parameter regimes. arXiv preprint arXiv:2404. 17714, 2024.
[Teal7] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 1(8), 2017.
[VW04] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841 --0000 2004.
[ZSM 18] Bo Zong. Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dacki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In International conference on learning representations, 2018.
14

---

A Preliminaries
A.1 Differential Privacy
We state the advanced composition theorem of differential privacy.
Theorem A.1 (Advanced Composition Theorem [DR44 Theorem 3.20)). Ler 8, 8' Z 0 be arbitrary parameters. Let A be algorithms on dataset X, where each A, is ()..)- Then, the concatenation A(X)
is (v2k 222 log 8 5 kg (ef k
- 1), ā 8') -DP.
Moreover, this holds even if the algorithms A, are adaptive. By this, we mean that for all 2 the algorithm A; is allowed to depend on A (x1)) However, privacy must still hold for Ai conditioned on the previous outputs A (X), Ai-3)
Next, we note the properties of the Truncated Laplace distribution and mechanism. Definition A.2 (Truncated Laplace Distribution). For A, E, 5 > the Truncated Laplace Distribution e// on the region [-A, A], where
TLap(4 A, E, 8) is the distribution with PDF proportional
A log + 22""), and PDF outside the region A, A].
Lemma A.3 (Truncated Laplace Mechanism [GDGK20] Theorem 1J). Let f : + R be a real- valued function, and let > O, such that for any neighboring datasets X. [f(X) f(x') A. Then, the mechanism A that outputs fXX + TLap(A,e,,) is (E, (E,
A.2 Matrix and Concentration Bounds
In this section, we note some standard but useful lemmas. We first note the Courant-Fischer theorem. Theorem A.4
Let A E Rdxdd be real symmetric matrix, with eigenvalues A A2 2 >d. Then, for each
A VCR dim(V)
min x Ax=
min VCB dim (V) V-)dV---
x -AA,
TEV ||]
& |==|===
where V refers to a linear subspace Rf
By setting A = JJJ J. we have the following corollary.
Corollary A.5. Let J E RRddd be real (possibly asymmetric) matrix with singular values oi 2 02 2 2 Td. Then, for each k;
max
min ZEV
|Jx||2
min VCB" dim (o)=(V-dd k- 2=
max ØEV
||Jx||2.
VCR
dim
= |al|==1
Next, we note basic proposition.
Proposition A.6. [HKMN23] Lemma 6.8] Let M E Rdxd be real symmetric matrix, and
Rddd be any real-valued (but not necessarily symmetric) matrix such that [[JJ -T S Φ 11 for some parameter &. Then, [JJ JJMM S (1+3g) MIMM
We also note the Hanson-Wrigh inequality.
Lemma A.7 (Hanson- Wright).. Given d x d matrix M E Badd and d-dimensional Gaussian vector X ~ ~(00 I), for any t 2 0,
1
PP (|x MX - E[X MX] 2t) S 2exp (-emin
|M |
|M
for some universal constant 0.
Finally, we note a folklore simple characterization of total variation distance (see also AAL23 Theorem 1.8)).
Lemma A.S. For any μl, U2 E dd and positive definite Σ,, Eg E Rdxd
drv(W( E1),N( Ez)) < 22 max |Σ]
1/2 Σn
Σ
Allr, 1| 1/2 (M1 - -222)12)
15

---

B Robust Estimation of a Single Gaussian
In this section, we establish what a robust algorithm can do for learning single high-dimensional Gaussian. We will state the accuracy guarantees in terms of the following definition, which combines Mahalanobis distance, spectral distance, and Frobenius distance.
Definition B.1. Given mean-covarie covariane pairs (j,, Σ) and (á, Σ), and given parameters P; 7 > 0. we say that (e, 2) p.pp. (H, 2) if
/21122 1lop S 7. (Spectral distance)
|--1/255-1 1/2 I| - (Frobenius distance)
12-1/2(00 p)l1 (Mahalanobis distance)
We will also use Ry,. as a shorthand for ~ 7,Vā-,,.7 i.c., there is no additional Frobenius norm condition beyond what is already imposed by the operator norm condition.
Although S.,p is neither symmetric nor transitive, symmetry and transitivity happen in an approxi- mate sense. Namely, the following result holds: we defer the proof to Appendix H. We remark that similar results are known (e.g.. [AL22 Lemma 3.2], [AAL23 Lemma 4.).).
Proposition B.2 (Approximate Symmetry and Transitivity). Fix any Y P. > O such that 7y I 0.1. Then, for any (Mi, Σ1) Sy,pp. (12, Σ2), we have that (12, Σ2) 22. (Mi, (1,,E1), and for any (m), 21) R.y,0.7 (122 22) and (122, E2) R.,p.r (ua, Ez), we have that (μ1, E1) R4y:Ap,4r (Ma, Ez).
We note the following theorem about the accuracy of robustly learning single Gaussian. While this result will roughly follow from known results and techniques in the literature, we were unable to find formal statement of the theorem, so we prove it in Appendix H
Theorem B.3. For some universal constants co 0.00. and Co > 1, the following holds. Fix any
S 7 S B < 1, and such that Ö(n) S p S covd. Let n 2 Ö 4+tog(1/0) + (d+Hog(1/B))
Then, there exists an (inefficient, deterministic) algorithm Ao with the following property. For any NN,,, E), and for all datasets X'
,, Σ, with probability at least 1 -3 over X (X1, ..) ~ with du (X, S T) n, we have
Ao(X') CCCn,Con.oor (u, E).
We remark that Ao may have knowledge of q1 7/s Ps 3, but does not have knowledge of p. E,, or the uncorrupted data X.
B.1 Directional bounds
In this section, note that, when given i.i.d. samples from a Gaussian, with high probability one cannot choose reasonably large subset with an extremely different empirical mean covariance.
First, note the following proposition, for which the proof follows by s-net type argument. Proposition B.4. Let 2 n' 2 20d, and L 2 Cin² for sufficiently large constant C₁. Suppose that some data points X (X...... Xn3 are i.i.d. sampled from ( I). Then, with probability at least - -R(m', the following both hold.
1. For all X, E X, 1|x1122 < T..
2. For all subsets Y C X of size n', there does not exist any real number and any unit vector u such that (X,, v) - r| S for all X, E Y.
Proof. If ||xil22 2 L, then X MX 2 2 for M the x d identity matrix I. However, B|XT MX] = d. So, by Lemma A.7 the probability of this event is at most 2e meminin /d,n") <
2e -en < 5n -a(nn))
Next, we bound the probability that the first item holds but the second item doesn't 't hold. First, create z neet of unit vectors v'. of size 33 < 3d and -nnct of real numbers r
16

---

from I-L, Li, of size 2L Now, suppose that the first item holds, but there is some unit vector and real number r with [X,, 1)
S f for all X; Y, for some Y X of size n'. In this case, (X,, v) < ||xill S L for all X; X, so we can assume that [r] L. Thus, if v' is the closest unit vector to in the net and r' is the closest real number to in the net, then U'), S (X,,
+ (Xx; v' - u>| + -r-r
||X:ll2 T. + 7. 3.
In other words, if the first event holds and the second does not, there exists v', in the net and Y C X of size n', such that (X;,,') v²) - r S 2 for all X; E Y. We can now bound this via union bound, To perform the union bound, we first bound the probability of this event holding for some fixed v', r,'," Y.
For any fixed v', T'r', W, Y. note that (X,, x'Y is just n' i..d. copies of (0, 1). Let's call these values ..,.... Engt, If there is some r' such that |z -
for all i, then [ =1l - f. for all i. Since the PDF of a (0, 1) is uniformly bounded by at most 1.2 for any fixed 21, the probablity that any other is within 6 of 2 is at most L. so the overall probability is at most (6/ (6/L)='-1.
L
Now, the union bound is done over (") choices of Y, at most ad choices of v', and at most 2L choices of Y. Thus, the overall probability is at most (6/L)"'-1 n=" L 2L <
(6n)" /L -3-3d 2 (67/L..7''. Thus, as long as L 2 100n², this is much smaller than n 2((n))
By shifting and scaling appropriately, we have the following corollary.
Corollary B.5. Let n 2 n' 2 20d, and L 2 Cin², for C1 the same constant as in Proposition B.4 Suppose that some data points X [XI...., Xn) are drawn from N(u, 2). Then, with probability al least - n -Q(n', the following both hold.
1. For all X1 E X, 1|_111(X,---1 12)1= S
2. For all subsets Y C X of size size n', there does not exist any real number r and any nonzero vector such that [X 0) rl S /122/ all X E Y.
B.2 Modified robust algorithm
We modify the robust algorithm of Theorem B.3 to have the following guarantees.
Lemma B.6. Let co; Co be as in Theorem B.3 and Ci be as in Proposition B.4 Let L == Ci n². Also, fix any 17 S 7 < Co, any e B < and and any p such that Ö(n) S p covd. Finally, suppose m > 0
d 7z
Then, there exists an (inefficient, deterministic) algorithm A that, on a dataset Y of size m, outputs either some (β. E) or L, with the following properties.
1. For any datasets Y, Y with du(Y (Y,Y') Sn Sn.mi m, A(Y) = =ii,E) #1 and A(Y") (pl, En) #1, then
(B',\) RSCur,8Cop.SCrr (f, E).
2. For any fixed μ, E, with probability least - 0(3) over Yı...., Ym N(,, A(Y) #1 and
A(Y) Cop (1, E).
3. Fix an integer 2 1, and additionally suppose that m 2 40d k. Suppose that X. (Xi,..., Xn) are drawn i.i.d. from some mixture of k Gaussians (pi, E.}. Then, with probubility at least
O(3) over X, for every Y¹ C X of size m and every Y with du (Y,Y')Y) S m/2, either A(Y) =1, or A(Y) (p., E), where there is some i E [k] such Eg x E 9 Σ, and ||= 1/2 m+)le 101.3
that 3T.
As in Theorem
B.3 A has knowledge of n. 1/ P. but not μ or E.
17

---

Proof. The algorithm A works as follows. Start off by computing Ao(Y) (e, Σ), where Ao the algorithm of Theorem B.3] We can run the algorithm on any arbitrary dataset, even if didn't come from Gaussian samples, and we can assume that the algorithm Ao always outputs some mean-covariance pair (for instance, by having output (0, )) by default instead of 1). Next, A, on a dataset Y, checks if any of the following three conditions hold.
(a) There exists Y' such that du (Y, Y') S v m, and Ao(Y") $3Cor,80o0.8or Ao(Y).
(b) There exists Y, Y such that | - 3L.
(c) There exists subset Z C. Y of size 20d, and unit vector and real number such that for all Y; E Z. KY, v) r| 2T. |
If any of these conditions hold, the output is A(Y) =T. Otherwise, the output is A(Y) = AAoYY.
We now verify that the algorithm satisfies the required properties. Property clearly holds, be- cause if there exist datasets Y, Y' with du Y") I " m, A(Y) # and A(Y') FL, and A(Y) #SCon,SCap,&Car A(Y'), then we would have in fact set A(Y) to L.
For Property 2, note that with probability 1 - 0(3), AY satisfies the desired property by The- orem B.3 since 3 2 e-d so d + log 1/3 = O(d). So. we just need to make sure that we don't set A(Y) be I. Since Yi...., Y,,. ~ NN, E)) then with probability 1 1- 0(3), both Y and any Y' with du Y. Y') S n- satisfy the conditions of Theorem B.3 In other words, Ao Copon
and Aol (Y) Cop So, by Proposition B.2 Ao &Co.7,C Aul (Y) for any Y with (Y, Y') S n. Thus, condition a) is not met.
Moreover, by Corollary B.5 with failure probability at most m (2(2d)) < B, 11- -V)ll S L. for all Y; Y, and for all Z c Y of size 20d, there does not exist real r and nonzero vector v such that (()),)) - rl S I || for all Y, E Y. Now, we know that by Theorem B.3 Σ). So,
(ū, ε.) 50..0005 (v,E).
||S- (Y, - A) S 2
1/2 (Y, -))l2 S 2(11-1121
= 2L + +15334 3L,
and if (Y, - S 2T, ||$1/20/12, then (YY, - rl S + |20//20122 for all Y E Y. Thus, conditions b) and c) are also not met, Property 2 holds.
For Property 3, note that if m 2 40d k then Y X 2 20d k. i.e., Y contains at least 20dk uncorrupted points. So, by the Pigeonhole Principle, for every possible Y, there is some index E [A] such that at least 20d points in Y X come from the 7th Gaussian component.
Now, let us condition on the event that Corollary B.5 holds for X, where n'' = 20d, which happens
with at least 1 - 22(x') > 1- - 3 probability. We claim that for every possible Y. and for an E [A]
such that 20d points Z C Y n X came from the jth Gaussian component, then either A(Y) =1 or
A(Y) = (p. Σn then 1 Σg क Σ < 1 Σ, and || (A- #:ll2 < 1
gLT
First, we verify that g Σg + Σ < *L E.. Otherwise, there exists unit vector such that either
v T Ee 2 7 v T Eie or T Ex S डे.
T E,e. In the former case, by Part I of Corollary B.5 for
all Y; z. || 1/2(X2 p1)1l2 - so
Ke, Yi-+ 1/22//2 U, 23 1/11/2(1 (Y: miMi S L- 1/2 u112 = L.Vo L.1
u Ev
1 3L
1 /
7L
Thus, if we set r = (v, p:). then (Y, r) - < + 111/20112 for all Y, E Z, so the algorithm A would have output 1 due condition c). Alternatively, if there exists unit vector such that T Ee ot. w Exv, then by condition b), 1/2 A)]l < 3L for all Y, E Z, so
le, Y, احم = 1051/22, 1-12 E - |)) S 3L /2 2112 < I || / Pol2.
So, there exists r = (v, (i) such that Kw. Yi) - r| S 1 Vo E,e which is impossible by Part 2 of Corollary B.5
18

---

Next, we verify that | 12/1//(11 (Ā 14)ll2 S 100. By Triangle inequality, for every Y, E Z,
| 18-1/2(X2 (Y; - 2 | 1/2 (Y; - p4ll22 2 |ا 1/2 (c:: 12 But, |>, 1/ 14)l2 $ L
by Part of Corollary B.5 and ||Σ, |/; x)] 3L2 - ||-- م)لل - 31 3L 9T3,
because we just proved that 97,42, > and assuming we do not reject due to condition b). Thus,
|Σ 1/2 (ps 2) - 9L + L 10L
C Volume and the Robustness-to-Privay Conversion
In this section, we explain the cotisstnesstt-prrvagaa conversion [HKM223] that we will utilize in proving Theorem [..4] We will also need some relevant results about computing volume, which will be important in the robustness-lo-privag conversion.
C.1 Normalized Volume
Given a pair (n, M) where μ E RRd and Σ E Rdxd is positive definite, we will define Proj(μ, 2) e Rd-(d+3)/2 to represent the coordinates of along with the upper-diagonal coordinates of Σ. For any set Ω of mean-covariance pairs (μ, Σ), define Proj([2 (Proj(μ, Σ) (1,, Σ) E 92 Because Σ is symmetric, Proj(μ, Σ) fully encodes the information about μu and E. We also define vol(S?) to be the Lebesgue measure of PPoj( i.e., the d(d+-3) -iimensionn measure of points Proj(μ, Σ) for (n, Σ) E Ω. Next, we will define the normalized volume
vol, (9t) :- -- (det E)d+2)/2
(1)
where 0 = (r Σ), and we take Lebesgue integral over 0 E Proj(?).
To motivate this choice of normalized volume, will see that the volume is invariant under some basic transformations.
Given a function f .R. RD, for some integer 2 1 we recall that the Jacobian some the matrix with Jıj Ofs For function that takes a symmetric matrix Σ and outputs the symmetric matrix AΣAT, we view D = d(d+1) and the function E + AEAT as a function f from D + RD by taking the upper triangular part of both Σ and AΣAT, Note that f is linear function (thus f(x) = J. where J E DD and moreover, the following fact is well-known.
2
Lemma C.1.
MH08 Theorem 11.1.5] For as defined above, dct(J) = dct(1))+1
Now, for any fixed E Rd and positive definite Σ E Raxd consider the transformation (á, Σ) + (//// E1/2 + p.), viewed linear map g from Proj(β,, Σ) - Proj n., /12 By setting A 1//2 note that the map g behaves like on the last d(d+1) dinates, and on the first d coordinates,
2 coor-
simply an affine map j + 21/2 μ. Therefore, the overall linear map y has determinant det (EI/2) (Et/Ay/1) (det ()
From this, we can infer the following.
Lemma C.2. Fix any P E IEd and positive definite Rdxdd Let h be the map (f. Σ) (5//22+ n. /./25551133 Then, for any set S of mean-covariand pairs, the normalized volume of S equals the normalized volume of h(S).
19

---

Proof. Let g be the corresponding map from Proj(A, Σ) to Proj(E //2 Using
simple integration by substitution, we have
voln(h(S))
8 ( (det (d+22)22 d9
(EE((Poo(()) (det E)(d+2)/2 d0
I Je-Prol(a (det(22/23)27/22)1444))
(det g)dl
/ Jierrajis) (det E)(d+2)/2 d0 = vol, (S).
C.2 Robustness to Privacy Conversion
We note the following restatement of (the inefficient, approx-DP version of) the main robustness-to- privacy conversion of [HKMN23].
In the following theorem, we will think of the parameter space as lying in RD, with some normalized volume vol, (f2) seea (0)) where p 2 0 is some nonnegative Lebesgue-measurable function and the integration is Lebesgue integration. In our application, we will think of Proj(μ, E), and p(0) (det (d+2)/2 match with (
Theorem C.3. Restatement of [HKMN23 Lemma 4.2] Let < 7 < 0.1 and 10y S 11" S be fixed parameters. Also, fix privacy parameters Eo. 69 and confidence parameter 30 < Let and
= S0 E R>0 be a score function that takes as input a dataset X = {X1,..., parameter E @ C RDP For any dataset X and any 0 S 1f S 1, let (X) be the D-dimensional normalized volume of points E O with score at most 1f -T, i.e., Vi (X) = vol, ((0 ( O: 8(0,X) X) S v mn)).
Suppose the following properties hold:
(Bounded Sensitivity) For any two adjacent datasets X, X' and any 0 E O, |8(0,X) ((0,X') S 1.
(Volumee) For some universal constant C, and for any X of size n such that there exists with S(0 X) < 0.71I n, nt 2 C. (X) (X))4logk) 1/66)
Then, there exists an (Ea, 50) DDP algorithm M, that takes as input X and outputs either some 0 E θ (X)V,,XX))))))
or I., such that for any datasel X, if 2 C outputs some 0 θ of score most 2mm with probability 1 Bo.
max Sn"
Eart
then M(X)
We remark that the algorithm M allowed prior knowledge of n. D, n.n) Eo. 8p, So. as well as the domain O, function p(0) that dictates the normalized volume, and score function S.
We remark that the original result in [HKMN23] assumes the volumes unnormalized, but the result immediately generalizes to normalized volumes. To see why, consider a modified domain S p(0). Also, consider modified score function S' acting on O', where S'(( 2), X) == S(0, X) for for any (6, 2) E e'.
O' E RD+1 where 0' (0, 2) O' if and only if 0 θ and 0
Then, note that the unnormalized volume of O', by Fubini's theorem, is precisely ][e..zeer 1dzd0 Sage d0))dO, which is precisely the normalized volume of corresponding to the new O precisely match the normalized volumes corresponding to the old Ô. A similar calculation will give that the unnormalized volume of points (f, 2) in e' with S' ((0, 2). X) S t equals the normalized volume of points 0 θ with S(8, X) t. for any t.
Thus, to privately find a parameter 0 E O of low score with respect to S (assuming the normalized volume constraints hold), can create O' and S', and apply the unnormalized version of Theorem C.3 to obtain some (0, z). Also, if S'((0, X) & 27m, then S(Ø) = S'((O, x),, S 21m,, and outputting (0, 2) is (E, -D- then is simply outputting 0.
20

---

C.3 Computing Normalized Volume Ratios
Lemma C.A. Let Rdxd be symmetric with || op S 0.1, and let S v S be a scaling
purameter. Then,
det(T + vM) det(1 + M) Sva.
Proof. If the eigenvalues of M are A1..... Ad --01,001|, then
det(1 + vM)
1
det(T + M)
1+
==1
Note that for x [-1.1,0.1] and 2 1, 1+x
142z an increasing function. Therefore,
d 0.1v V. A
1 X
1
0.1
1=1
1=1
and
a
d I 1=1
1 1 v 1
A
0.10
11
2
I 1=1
1+
0.1
[=1
where we used the fact that 1 < 2
We note an important lemmas about the normalized volumes of certain sets.
Lemma C.S. Fix some 7, S 0.1 and some scaling parameters 1 S < 2 and 1 S v2. Let Ri be the set of (M, E) Reys (0, I) and R2 be the set of (1,, E) ies (0, Then, the ratio of normalized volumes
vol, (R2) vol, (Ri)
S vi 112
Proof. By definition of normalized volume, we have
vol, (R2) J wolllllllllllll del(T + / dudM,
where we slightly abusing notation because truly integrating along the upper- trianttri part of M. (Overall, the integral is d(d+3) -imensional.) We have similar expression for vol,(RR,
Let us consider the map sending (μr, I + .) + (V2- I + v1 M). This is a linear map, and for ||æ||a 7 and symmetric ||M lop т, this is bijective map from R, R2. Therefore, by an integration by substitution, we have
/1 M1 det(I v1 M) 11 s 11 a(d+1)/2 vs (v (v-
vol. (R2)
d(d+1)/2 2 DddpdM
SMMloos det(1 M)(d42)/22ddl Muuu
2dd us vol, (R1).
Above, the first line integration by substitution, and the second line uses Lemma C.4
Next, note the following bound the size of net of matrices with small Frobenius norm.
Lemma C.6. Fix some < 0.1 and < < 0.1vd. Let Ra be the set of symmetric matrices
M E ddxd with [[ 5 7 and [| || S Then, for any < l < d, there exists net B of size
at most (ogd such that for any M e R3, there exists B E B such that JM - Bllop < 20
Vi'
21

---

Proof. First, note that the unit sphere in Re has ąio
1 net (in Euclidean distance) of size e(ddlogdd) d).
Let Bo be this net. The net will be the set of matrices Ex- Kmw,y," where every wi E Bo, every Ny is an integral multiple of zh., and every Iayl S 7. The cardinality of B is at most |Bol% (dfo0e S ()g-d
Now, we show that B is actually net. For any matrix M E Ry, we can write M = =E= Aoaa where Ae 2/ are the eigenvalues and eigenvectors, respectively, of M. Assume the eigenvalues are sorted so that [&d] are in decreasing order. Now, since > X < p², which means that |A,] S ve for all > f.
Now, let B1 = Eise Aov;o since the e; 's are orthogonal and | v e this means that Billop S
VF.
a Also, note that M = B1 + Ei= Amaay Suppose we replace each X; with Ky by rounding to the nearest multiple of 1/d'0. and replace each v, with w, e Bo such that ||u, w; ll2 S 1/d'0. Then,
Vi
Σ - k, is in B, and by Triangle inequality, we have
Σ KAWAi
S (1A: +2 Ao- 1|us m2ll2) 0
S Vt
d
op
Thus, ||M
1lp S 2 P. VE'
We also note the following lemma. We defer the proof to Appendix H
Lemma C.7. Fix any a and positive definite E. Then, for any pi, u2, E1, Ez, we have that (P1, )n Pr.po (p2, Ei) if and only if (2 #1 + u, /,,"32,,) Ryype 122/2 + n1 E1/2)
u2,
Our main lemma in this subsection the following, which roughly bounds the normalized volume of a Frobenius norm ball "fattened" by an operator norm ball.
Lemma C.8. Let e E (0,0.01) be a sufficiently small universal constant. Fix any and positive A Vd). Let (i Σ) represent
definite E. Fix some parameters Yı, 72 E (1) and p2 E di TOOO the set of (11, E1)] such that (M1, En) Ryam (H, Let T2( 2) represent the set of {12 E2)} such that (p2, E2) Reym (H1, for some (11, En) Pro.p2m (1, E). Then,
vol, (T2(1, (T,,
S Olda log d. 213 /x)
Furthermore, both (TI, E)) and (T2(H, E)) do not change even if we change μt, E.
Proof. For now, we also assume that = 0 and Σ = I.
Let < é S d be decided later, and let B be the net from Lemma C.6 where we set y 72 and p = p2. Let B, be a 2 -o--ett (in Euclidean distance) over the d-dimensional unit ball, i.e.,
over μ with || < 1. Note that [B1| < @ldloggd) and recall that [B] < OfE- log d). Now,
for any (12, E2) E (0 I). we can write (M2, E2) Soam (MI, E,), where || - Mo < 72.
|| - - S P2, and || S 72. Now, we can choose some p' E B, with || - 1 1|2 S d and
B E B such that ||(E: - T) Bllop= I 2p3 VF
What can we say about the relationship between (/22, Σ2) and (n', T B)? First, note that because
(n2, Σ2) Rymm E1,,E1), we have (1 (1 x Σg & (1 (1+7))E,, Next, since || E (T+ lpp
||(E- I) - Bllop S Vē and since Σ₁ has all eigenvalues between 1 - 7/2 2 and 1 + 722 S
2pa
this means (1 403 En (I+ B) < [ 403 ΣT. Thus, if 4p Vl, we have that
1-7
1+7 (I B).
(I + B) x Σ1 2 1- (4p2/VB)
1 1+ (4)
Next, because (12, E2) Sy.m n (H1, Σ1). have ||ー 1/2 (u2 f1lll2 S 71, which means ||
#1 ll2 I 2'1 Thus, because 1| H l| - d < Y1, this means that ||22 4'll2 S 3% Morcover,
22

---

assuming 10p S vt, the eigenvalues of I + B are at least (1 (1-1) 71) (1- 1/2 2 1. which means
that [I(T + B)-1))((12 - 12)1la & 6n1
In summary, 10p 2 v2, then
1 1-n 1+ (4p2/Ve) (1+B) x E2 ক 1 (4p2/Ve)
1+ (1+ B), I1I 1) - H0)12 : S 6%,1
1+ Note that if 71 S 0.1 and 10p S Vt, then by simple calculation, 1-(4pa/V8) - 1 + 71 + 4
and 1-7
402 This implies that (12, 222) R +10ps//e..n (n', + B), for some
1+(4ps/Ve) VV) 11' B1 and B B. Note that this holds for any (122, Σ2) T2,
71 vi
Therefore, recalling that |B1] I oldlogd) and [B] S (((edlloRd) we can cover T2(0, 7) with at (n',E' Now, by Lemma C.7 (12; E2) 2xy+10ps/ (n'EE) if and only if μ22 //2/2 14D + J' and Mg / En 20/2 where (No: Mo) 8 10tp (0, I). By Lemma C.2 this means that the volume of ((12, Σx) (12, Σ2) x ~nt10ps/V (u', })) equals the volume of {(H0, En)
most e (f-ddlogdd) regions, each of which is the set of (122 E2) +11 Vi,em
(Ho, 2o) 2 71+10ps/V2.0 (0, 1)}.
Thus, if 10p S Vl, then (2, 1) can be covered by e (ledloogd) regions, each of which has the same normalized volume as the volume of {wo, Σo): (Ho, 2n) ~ +1110ps/ (0, (0, Moreover, if we
2d
further have 10p= Vi
S 71, then by Lemma C.8 this is most (1+
10pz
- vol,(T((0,
vin
We will set l
100(dp2)2/3 πr
Since P2 5 l 2 100 as long as 71 S C1 1. Also, L s
2/3
100
Ti 1000
d3/2
= d. Finally,
10pg Vt
n
I 71, since p2 S Vd. Overall, the ratio
d
71
2
vol, (T2(0, [))
< (le-dlogd)
(1+
10p₂
6d < c 0l84/3 log d. 2/3 /17)
vol,, (T)
Vl
Finally, we show how to remove the assumption that μ = and Σ = I. First, note that for any general n, E, (H1, E (0, I) if and only if (11/2 + n. E1/22,
(1, E), by So, by Lemma C.2 voln (u, Σ)) = vol, (0, 1)). Next, (m2, En) Rmm (M), En)
Lemma C.7
and (M1, Σ
222.P2.72 I0.I) if and only if (E1/2k2 + n. 11/ 2y.m (2
(1, Σ1/2E, Σ (2) and (E 14 + n1, E E1/2) 22p.p200 E), by two applications of
Lemma C.7 So, by Lemma C.2 vol, (Ta(u, Σ)) = vol, (T2 I)). Thus, the volume ratios stay the
same as well.
D Fine Approximation via Hypothesis Selection
In this section, we prove that we know a very crude approximation to all of the Gaussian mixture components with sufficiently large weight, we can privately learn the full density of the Gaussian mixture model up to low total variation distance. This will be useful for proving both Theorem I.4 and Theorem
We start with the following auxiliary lemma.
Lemma D.I. Let G 2 1 and Ç S 1 be some parameters. For some d 1. let f E Rd, and let
E E Raxd be positive definite. Let U be the set of (H,, E) such that & E x E x G. E. and 1/-1/2(4- A)1l2 < G. Then, there exists a net Bp of size O(GVa/c)d(d-)) such that for every E) Up there exists (4','') E' Bp.s such that dTv(N (N,, E') SC
Proof. First, assume that E = I and jt 0. Now, let us consider the set U == Uo.1 (1u, E) ||l||2 < G, J 1 x G. 1}. Let G¹ > G be parameter that we will set later. Now, we can look
23

---

at the un-normalized volume of U viewed in Rd(4+3)/2 (i.c., we are projecting to the upper- upper-triangular part of Σ). First, we claim (using a standard volume argument) that there is a cover B U of size (2G*)d(d+3), such that for every (H, 23 E U, there is (p', >n) E B with I| - μ ll2 I き and
| lap 1 c..
To see why, consider maximal packing of (n), M U such that for every i * j. either 1 n > or or || > G.. Then, this set is clearly a cover of (or else we could have increased the size of the packing, breaking maximality). Then, the sets S := ((1, E) || 14 - , Ei - 2G I are disjoint, and are all contained in the set S := [), ||ا|| S 2G', 1E S 2G") Si just shifting and scaling of S. by factor of 4(G"), and thus vol(S) (4())) ()dd)))dd)3//2.voolll
|Σ
12G))d(4+3) vo)(S,). Because every St is disjoint and contained in S, the number of such indices i is most (2G")d((+33.
Next, consider any (j,, Σ) E ll and (n',E') E B with || - ا 122 S
.. 1 E' El S C²
Then, G Also,
//5-////''-1/2 /loop |/-1/2 - 1/2 1| < || || - Elpo S G
|| - p1)ll2 S || |1u u 2|2 S &" In other words, we have found a net B of size (2G))d((+3) such that for every (1, E U. there exists (μ', M²) E B with (x',2") =a/Gr C// E).
Next, consider general A, E. Note that (1, Σ) E Up is equivalent to μ E112 no + û., where l|ooll2 S G. and Σ = $1/2 E where G I Eo < G. So, if we consider the map f (Ho, 2o) + ($11/ po + f., /1/2 $1/2), this bijectively maps U Uz We can also con- sider the cover b = ((B), where B is the cover constructed for U. Then, by Lemma C.7 (16: Σ) Rajor (No, Σo) if and only if f(16, En) 2G/G f(/0,
Hence, regardless of the choice of iú, E, for every (M, E) E Un there exists (n', E') E B with (n',E') Zajaraja E), Moreover, pp = B I (2G")d(a+3) Moreover, (n' GG/G,G/// (u, then || 1) S & and ||8-1/20y-1/2 1 1|1F S
Vd. 11-1//EE-1/2 Tloo vaGG Hence, if we set G² Gvd, (p, E Up there exists (,','') B such that (V,, E')) SC
G So, by Lemma A.8 drv(N (r E), - vaG " then the size of the net B is ((GVV/s) and for every
Next, we note the following result about differentially private hypothesis selection. Theorem D.2. (BSKW19) Let H. = (Hl..... , be a set of probability distributions over some domain D. There exists an e-differentially private algorithm (with respect to a dataset X (X ) which has following guarantees.
Let D be an unknown probability distribution over D, and suppose there exists a distribution H E H such that drv H S a. If 2 O
log M a²
+ log M ). and if X are samples
drawn independently from D. then the algorithm will output a distribution Á E H. such that Arv(D, H) S 4a with probability at least 9/10.
Given Lemma D.I and Theorem D.2 we in position to convert any crude approximation into fine approximation. Namely, we prove the following result.
Lemma D.3. Let D represent an unknown GMM with representation {(w,, ui, En Let G > be some fixed parameter. Then there exists an s-differentially algorithm, on n z o 0f (Ckiogg(G vdjaa) + a²
d Ge vdja)) samples, with the following property.
Suppose the algorithm is given input set {Ag, ((g,,,))5 En) for some k' 2 1, such that for every
(pi, Σx) with weight w, 2 E. there exists S k' such that 1/ E < E, + G E, and ||=; 1/2
ir,)l2 S G. Then, if the samples are XI...., X,, Lid. DD then with probability at least 9/10, the algorithm outputs a mixture of at most ls Gaussians H, with (D, H) < O(a).
24

---

Proof. Let Ç = For each (A,, Eg}, let B3 Ry. be as in Lemma D.1 We define B = Upsk B Bp
Let H be the set of hypotheses consisting of mixtures of up to k Gaussians M(,, 22 with weights w/e with every (1dz 22,) B and with every wa integral multiple of Ç. Note that the number of hypothesis = = is at most [B)O(R) (1/C)0(8) (K' G vd/c) M S (G. kk'va )
Since we set ( = a/k:
Next, let consider the true GMM D, with representation {w,, M4, E,) Because every (1,, Σ,) with W; 2 a satisfies à En < Σg < G En and [|= 1/2 (14 - ,5) I G, by Lemma D.1 there I:
exists (44, 2) E B such that drv (N(u; Ex), (Hl, 2x) S Ç. Moreover, we can round each w; i to some w which is integral multiple of (, such that [w, w/l S Ç. Finally, for each w; a can choose an arbitrary Gaussian in B and round wy to some wt- Then, the total variation distance most
between D and the GMM with representation {(w,, pbg )D)
Σ
(x.
a + lwy - lw::-(;) +
(c+ |wg w/l) sa+ (). kSki 2a/k
Σ
Hence, if we set Ç g there exists a distribution H E H with dT, H s O(a).
Therefore, the algorithm of Theorem D.2 using 2 0 d &klloglG-kk samples, will find H E H. such that drv (D, H) - ((a),, and e-differentially private.
G- -vd/ol
o²
Pseudocode:
We give a simple pseudocode for the algorithm of Lemma D.3 in Algorithm
Algorithm 1: FINE-ESTTMATTE(X,,
E Rd. d, k. W, e, a, G. ((A, Ei)ssw))
Input: Samples X1...., Xn., and crude predictions (Øz, Σy), where 1 J k for some k'. Output: An (E, O)-D prediction H, which a mixture over at most & Gaussians.
Set ( a/k.
2 for j = 1 to k' do
Define the sets st, as in Lemma D.I for parameters G,S. end
18
UJSK
B 2.
Let H. be the set of mixtures (wr, p4, E{) of l or fewer components, where every (n4, B and every w is an integral multiple of C.
Run the e-DP algorithm of Theorem D.2 on X ,I,...,X, Xn with respect to H.
E The High Dimensional Setting
We first describe and provide pseudocode for the algorithm, and then prove that it can privately learn mixtures of d-dimensional Gaussians with low sample complexity.
In this section, we provide the algorithm and analysis for Theorem I.4
E.1 Algorithm
Suppose that the unknown distribution is a GMM with representation "remaining" mean-covariance pairs.
High-Level Approach: {(ws, pr, E.)
Define θ to the set of all feasible mean-covariance pairs (μ, E), i.e., where μ E R and Σ e igddd is positive definite. We also start off with set Ω O which will roughly characterize the region of
At a high level, our algorithm proceeds as follows. We will first learn a very crude approximation of each (n4 E,,, one at a time. Namely, using roughly (Vllog(1/8)
à
-DP, we will learn some
k
25

---

(A1. Σn} E Ω which is "vaguely close" to some E.). We will then remove every (n. Σ) that is vaguely close to this (i, )) from our Ω and then attempt to repeat this process. We will repeat it up to k times, in hopes that every (1i, Ex) is vaguely close to some (ūg, Egy. By advanced composition, the full set of {AA, Σ is still (c, 6D..
At this point, the remainder of the algorithm is quite simple. Namely, we have some crude estimate for every (Mg Σx) (it is "vaguely close" to some (Øg. ), Moreover, one can create fine net of roughly cO(P)) (j,, -)ppiirs that cover all covariane pairs vaguely close to each (Az. E,), since the dimension of (n, Σ) is ((P)). Moreover, the weight vector (W1,.... wis has fine net of size roughly ( As a result, we can reduce the problem to a small set of hypotheses: there are roughly (Old)) choices for each (14: Ex), and @O(k) choices for w, for total of cO(k-d") choices for the mixture of Gaussians. We can then apply known results on private hypothesis selection [BSKW19], which will suffice.
The main difficulty in the algorithm is in privately learning some (úi, Σ) which is "vaguely close" to some (μg, E,). We accomplish this task by applying the robustnessto--rrivag to-privacy conversion of [HKMN23), along with a carefully constructed score function, which we will describe later in this section.
Algorithm Description: Let Co I 0.01 and Co > 1 be the constants of Lemma [B.6 and e₁ I 0.01
be the constant of Lemma C.8 Let 02 I 0.1 min ei) be a sufficiently small constant. We set parameters 11"
22 8k
io E
V 1k log(1/6
5g
2k
5 Po
e We also set m
Ö(d.T5), N = Ō
/llg(11/8)
/T=log//"1//8 + kd and n N 24. Finally, we define
parameters 7 T 02 and p 02 d1/8 (See Lines 1 of Algorithm 2 for more precise description of some of the parameters.)
We now define the main score function. To do so, we first set some auxiliary parameter v/ = = RCo and o' D. We will consider the (deterministic) algorithm A of Lemma B.6 where A is given parameters nf', , '',''' o'.Bo. that acts on a dataset Z and outputs either 1 or some (e. E). Next, for some domain Q c θ of "feasible" mcan-covariance pairs (H, E), we will define a function fa. which takes as input a dataset Y of size N and mcan-covariance pair (H, 2) E O and outputs
{
if (H, EG, A(Y) Ry.e (4, 2), and
P [A(Z) Rep0 (p, 20, 2 ZCY 2
Ja(Y, 1,,,
else.
(2)
Finally, given dataset X of size and (2, Σ) E O, we define the score function
,4, u4, E such that Sn((i,E), = min {t: EX Y', dn dn = Y' X', Y N, (T,E) ROgT (1, E), (Y 14, Σ) 1}. (3)
Note that (Ti, Σ) does not need to be in Ω but it must satisfy (e7, Σ) Ri,e (J1, Σ) for some (/4, Σ) E Ω Also, note that it possible that no matter how one changes the data points, the conditions are never met (for instance (77, Σ) Φ4., (H, Σ) for any (H, E) E Q). This is not a problem: we will simply set the score to be +o0 if this occurs.
With this definition of score function SR, we can let M be an (Eo, 6DP algorithm based on Theorem C.3 with the settings of 1),7777 7)" , Eo, do, fo above, and with D = m(n+3) Here, we recall that (ūt, Σ) is viewed as n(n+3) -dimensional by only considering the apper-triangule part of Σ. We also assume the domain is θ and the normalized volume is as in (I.
Given this algorithm M (which implicitly depends on Q2, the algorithm works as follows. We will actually draw a total of n + ní samples (for as above, and n' to be defined later), though we start by just looking at the first n samples X = (X1,... ). We initially set 52 = O, and run the following procedure up to & times, or until the algorithm outputs 1. For the 7th iteration, use M(X) to
26

---

compute some prediction (Ag, Ez) (or possibly we output 1). Assuming we do not output 1, we remove from Q every (j, m) such that n 12 En x E & 12 Eg and ||= (n - ;g))l22 n!² {(Aj. E3} where 0 S W S k. If K' we simply output L. fresh samples. We the s-DP hypothesis selection on the fresh samples, using parameters G = = and { En)
At the end, we have computed some Otherwise, we will draw n' - L based algorithm, Algorithm
Lh ac
a
Pseudocode:
We give pseudocode for the algorithm in Algorithm 2
Algorithm 2: 1 .,, Xnow E RRd k. 6,
Input: Samples Xi...., ,, Xn+I..... Xntn' Output: An (e, 8)-DP prediction ((7s, E.), w:
/* Set parameters */
Let 02 be sufficiently small constant and K = poly (og(d, k, a 5
log ()) be sufficiently large.
2 17" + 2-a
86
x-
To Eo f
V log(1/)) (1//0 + kd n N 2k
50 - 2%
80 t e-d
m K d1.7 N c K.
7, - c, t 10 d2/8
+ {(u, Σ) / E Rd, E E ddd Symmetric, Positive Definite}.
/* Get */
Obtain samples X + Xx.. Xn}.
/+ Learn crude approximation (Øjz Eni) of the mean-covariance pairs, one at time */ for jrrj=l 1 do
Define fn n. Σ) and (n(( X) as in 2 and (3. respectively.
Let M be the (Eo, DDP algorithm obtained by Theorem C.3 with the score function So.
with parameters n. 1) 17", So: do. 3o defined above, D +[n+3] domain O, and
p(p, 2) (det 2)) (d42)/22
10
A + M(X)
A #1 then
12
Úg. E1 < A
Ω Mill,, E) 122 Eij = n2 Stg and 1 (p Arj)l 22
else
15
Break
// Break out of the for loop
16
end
end
/* Fine approximation, via private hypothesis selection */
18 Set nt' + K
ck
Lk
19 Sample _nt,...., Xn-n', and redefine X +- (Xu+1, Xnta/). Run Algorithm on X, ((2g, }, with k'' #((A,, Ej}} and G 12
E.2 Analysis of Crude approximation
In this section, we analyze Lines 17 of Algorithm The main goal to show that the algorithm is private, and that for samples drawn from mixture of Gaussians, every component (14, E,) with large enough weight w; is "vaguely close" to some (Øy, Ê,)) computed by the algorithm.
First, we show that when the samples are actually drawn as a Gaussian mixture, then under some reasonable conditions, any (μ, Σ) close to true mean-covariance pair has low score.
Proposition E.1. Suppose X {XI...., X is drawn from Gaussian mixture model, with representation [(w, M4,
je E Then, with 1 O(k Bo) probability over X. for any set Ω
27

---

of mean-covariance pairs, for all E [k] such that (14, Et) E Q and wi 2 a/k, and for all (ji, Σ) 7 (ns, Ex), S Σ), X) O.
Proof. Fix any i E [k] with w, 2 a/k. Set μ = 14 and Σ = Σ. Also, let X -X, and Y be a random subset of size N among the samples in X actually drawn from M(p, E,). Note that the number of such samples has distribution (in(n, ws), which for wi 2 E and 2k .N.,N, is at least N with -R(N) S Bu failure probability.
Then, Y is just N i..dd. samples from (i4, E,). So, if we draw a random subset Z of size m of Y, it has the same distribution as i.i.d. samples from ((s, Ex). We apply Part 2 of Lemma (where we use parameters n/' n', p in the application). Note that m 2 δ + least 1 - ((3)) over Z, A() "sCoy" 8Cop 8Co'' SCop (14, Σ,). By our setting of 7 ,,, this means that A()) S.,0. (14, E,).
d2 /² so with probability at
In other words, for each index E (N) and corresponding subset of Y, if we let W; be the indicator that A(Z) Hy.n. (1i, Ex), then P(W, = 1) v ( While the values of W, are not necessarily independent, by linearity of expectation we have that E [ I (M) O(8)), so the probability that B
Wil +
2 a (m) is at most (55) by Markov's is inequality. Moreover, because
N 2 m 2 θ
d d x22
we can apply A on Y and we again obtain that with probability 1 1 0(3))
7
A(Y) S.p. (1i, I.).
In summary, for any fixed i [K] with w7 f: with probability at least 1 ((3a) over X, there
exists Y CX of size N, such that A(Y) R..p. (14, Σx) and at least 2/3 of the subsets Z C Y of size have A(Z) yyp.. (14, E,). Thus, for any set Ω if (m, Σ,) E Q then (n E), X) = 0 for all (7,, Σ) R.y (pt, E.). The proof follows by a union bound over all E [A.].
Next, we show that for any dataset X, if there is even single (μ², Σ*) with low score, there must be region of (7, Σ) which all has low score.
Proposition E.2. Suppose that t = min," .. "))) X). Then, there exists some p. E such that for all (ji, Σ) Ren, (m, E), we have that Sn E), X) L.
Proof. Fix J2" Σ' so that Sn((n,, X) = t. Then, there is some (j,, E) and some X', Y such that du X') = 4, Y C X', Y = N, and Jn(Y,, 14, Σ) = 1. Thus, for any (7, Σ) Ryyr (v, E). by definition, we have that Sn (fū, X) I t. But since is the minimum possible score, we in fact have equality: (p Σ). X) for all such (p, E).
Next, we want to show that regardless of the dataset (even if not drawn from any Gaussian mixture distribution), the set of points of low score can't have that much volume.
Proposition E.3. Fix a dataset X size size n. Then, the set of μ. E such that Sa((T, Σ), Sn" can be partitioned into most (*)) regions Si which is indexed by some (p4, Ed) Moreover for all (P, Σ) E S₁, there exists (μ, Σ) such that (Te, Σ) Ray (p, E) and (H,E) 28y Sp.8r (14, E)).
Proof. Pick any (T,, Σ) with score at most 17" Let X', Y', M4, Σ be such that du (X, X') 17' n, Y' C X', Y' = N, (7, Σ) Rey (p, E), and (Y (Y n1, E) 1. If we define Y c X of size N to be the corresponding subset as Y' is to X', then d (Y, Y') Sn n 7 N.
Now, we take a random subset Z' of size m in Y', and look at the corresponding subset Z of size m in Y. by Chernoff bound, with at least 0.99 probability dz Z') < @ m. Moreover, with at least 2/3 probability over the random subset Z', A(Z') 20 (n, E). Therefore, there always exists subset Z C X of size m and set Z' of size m such that du (Z, Z') S c m and A(Z)) p.p. (n, E).
2
Now, for any fixed Z C X of size m, if we look at any sets Z' Z" of size m and Hamming distance at most & from Z, then du (Z', Z²) S C2 m. So, by Property I of Lemma B.6 for every such Z' and Z" with A(Z'), A(Z") #L, we must have A(Z") Zy,00 A(Z').
28

---

To complete the proof, we order the subsets Z1. Zg..... ((m) of size m in X. For each i S (m) if there exists some Z' such that (Z, Z') < - m and A(Z') _L, choose an arbitrary such Z' and let (14; Ex :- A(Z'. Otherwise, we do not define (pl, M.). Then, for any (ū, Σ of score at most 17* ni there exists (,, 2), a subset Z; C X of size m, and a set Z of size m such that (7,, Σ S,, (Hi 2), du (Z, Z2) I 3 mm, and A(Z)) Rypp. (H, 2). Because A(Z,) ا and Z from Z, this also implies that A(Z)) Sy,po (U4 2.). By
has Hamming distance at most 2
Proposition B.2 this means that (11, Σ) 8p.87 (p4. E2), which completes the proof.
Proposition E.4. Suppose X {X ),) drawn from a Gaussian mixture model, with representation {mu, Pi, Ex) Then, with probability at least 1 O(3) over the randomness of X. for any set St of mean-covariance pairs, and for every (ū, Σ) with So Σ,, S 2,4 there
exists an index E [k] such that ((55) Σ. Σ x (nr)) Dg and ||=; 1/2 ( 2illa S Onn)).
Proof. We apply Part 3 of Lemma B.6 though we use N to replace the value m in Lemma B.6 We are assuming N 40d k. So, by definition of score, (ji. Σ) Rny7 (n, Σ) where fn( (Y', f1, Σ) 1, for some Y' which can be generated by taking subset of X of size at most N and altering at most N/2 elements. Since fo Y', pr, -) 1, this means that if (p. Σ) A(YY) then L) Sy,ppr (4, Σ). So,
by Proposition B.2 (ū. Σ) 88g (e, E) Assuming = T = 22 is sufficiently small, this means that (7t, Σ) 1/2 (ú, Σ) By Part 3 of Lemma
B.6 with probability at least (5v), there exists i E [k] such that O(ns) E, $
E O(n)) E, and 1 1/2 (i- pillla S On²). However, know that S ~ E b 25, which means that Øinzy" Eg O(n*). Thus, by triangle inequality, we have that | /2 (m 12)1 S Onn)).
I < Σ x (( Σ. Moreover, || 1l < 0.5, so |Σ, 1/2 12 S
Now, given set X = (X .,) drawn from GMM with representation {(ws, Mi, E,) we
say X is regular it satisfies Propositions E. and E.4 In other words:
1. for any set Q of mean-covariance pairs, for all e [k] such that (mo, 2x,) S and w, 2 a/k. and for all (ūz, Σ) R,,, (4, Ex), (n E). x) = O.
2. for any set St of mean-covariance pairs, and for every (ūi, Σ) with Sn D), X) s N there
2
exists an index i [k] such that ত.मन.. >n x E x Onn)) 2n and |/--1/2(0 (ī --))ll S (
When we say X is regular, the components (p, Σ,) and weights w; are implicit.
We now show that every step of the crude approximation (Lines 8 16 in Algorithm 2 will, with 1- (3o) probability, find some crude approximation (Øg,L) to some (pi E,). long as (14, E,) Ω
Lemma E.5. For any Q2 C Q the corresponding algorithm M (which depends on 22) is (Eo, 6DP on datasets X.
Suppose additionally that X is regular, and that there exists E [k] such that w; 2 and (Mi, E.) E Ω. Then, with 1 - O(3a) probubility (just over the mechanism M), M(X) = (7,, Σ) and
There exists é E [k] such that o(us) 1 Eg < XxE x ((n5)-55 Eg and [E, |
1/-1/2 172 p1)ll $ 0(no).
*There exists (p, E) e Z such that (ū,, E) Ey,r E). 2).
Proof. We will apply Theorem C.3 We first need to check the necessary conditions. It follows almost immediately from the definition of Sn that Se,(Ni, E),-) -) has the bounded sensitivity property with respect to neighboring datasets, for any fixed Ω, 8, E.
29

---

To check the volume condition, note that for any dataset X of size n, if min,, (p, X) - 0.7m" n, then by Proposition E.2 there exists μ, 3 such that Sn((ū, 2) X) I 0.8n/" for all (it, Σ) R.,7 (M, 2). Conversely, for any X. by Proposition E.3 the set of (T, ف of score at most vj n can be partitioned into (m) regions S,, indexed by (14, 27 Moreover, each S; is contained in the set of (zi, Σ) such that there exists (μ, 2) such that (7i, 2) 2,,5 (1, 2) 8p.88 (p4,2%)
Let us use the notation of Lemma C.8 where ?1 = 7/ 7/2 = 8%, and P2 = 8p. Then, we have that the set of points with score at most 0.81) contains (H, Σ) for some (j, E), but the set of points with score at most 17 is contained in the union of (2 Σ2) for at most (m)) choices of (p4, E So, as
long as ming,,; Sp ((1,, 2), X) = 0.71)" n, we can apply Lemma C.8 to obtain
VU- (X)
n
exp O
/5/3 log d P2
2/3
)
=exp exp (o(d" m mogn))
S
Vo.87 (X)
m
since P2 = 8p 802
d/88 and
711 = 7 = C22 and since 02 is a constant. Thus, if
n C- Old7/4 log d + m n) + log(1/60)
60 '1"
we have that M is (eo, dDP by Theorem C.3 is sufficiently large.
This holds by our parameter settings, assuming K
Next, prove accuracy. Assume that X is regular. We again adopt the notation of Lemma C.8 (with 71- = 7. 72 = 8y, and P2 = 8p). By the first condition of regularity, for all E [K] such that (pt, Σ₁) E Q and Wz 2 a/k, every (p. Σ) E T1 E,) satisfies (7z, Σ), X) = 0. We still have that the set of points of score at most 17" n. is contained in the union of at most sets T2(44, E)) Thus,
Vg- (X)
I cxp (o (d7/4 log d + m logn))
(X)
where we recall that we set 1 = 2- So, by Theorem C.3 long
n n C 0dd log d + m logn) n) + log (1/(So-))) 17)
5o 77
which indeed holds, M(X outputs some (7, Σ) of score at most 2mm,, with 1 - 3o probability. By the second condition of regularity,, there exists an index i E [k] such that लाeउ Σ) x E < 0(r²)) E;
and || 1/2 (ī- p1)ll2 S Onn)) Moreover, because (ū, Σ) has finite score, (7, Σ) :..7 (11. Σ) for
115-1/2(1 some (1z, Σ) E Ω.
Lemma E.6. Lines 77 of Algorithm 2 are (E. Moreover, for every regular set X. with probability at least 1 Ok: Bo) over the randomness of Algorithm 2 for every E [k] such that 12 E, < Σ, < n 12. En and ||= (μ - P2) I 1 12
w; 2 k. there exists j such that n
Proof. The privacy guarantee is immediate by (adaptive) advanced composition. Indeed, the algo- rithm M at each step is (Eu. 5o) and only depends on X and Ω which is determined only by the output of all previous runs of M.
Now, let's say that X = (X1,..., ),, is regular, and we run Algorithm on X. Now, after j 2 0 steps of the loop, define P3 to be the set of indices i E [k] such that w/ 2 I and (14, Σ,) E S2 (where S2 refers to the set Ω after j steps of the loop are completed). Likewise, define Q2 to be the set of indices i such that there exists (f, Σ) E Ω with 1
nio Σ, E < n 10 E, and
|زΣ 12 14)l12 I n 10, Note that Po C Qu= = [R., and that P, C 2, always. Moreover, because Ω only shrinks, P,+1 C P, and Qj+1 C Q, always.
Now, after some step j < k, we claim that if P3 + 0, then 1Q,+1| S |Q,l- - with failure probability at most 0(30), i.e., Q decreases in size for the next step if P isn't currently empty. The failure probability is only over the randomness of A at each step, and holds for any regular dataset X. union bound says the total failure probability is Olk- Bo).
30

---

To see why this holds, note that if some index i E P3. then (H4, Ex) E 2g. So, we can apply Lemma E.5 At step 1, we find some (fi+1, Ej+1), with the following properties. First, there exists an index i' E [k] with लieey Ey & 25+1 < O(n))- Eyr and 12 - pe S O Second, (R5+1, 1)+1) Ry,7 (e, 2), for some (n, 2) E Ωz.
We claim this means / E Q2. To see why, suffices to show that J Es < Σ x 10 En and no | | 1/ 12))l2 1 1 by definition of Q2 and because (p. Σ) E Sz. However, we know that O(1rj Eg. < 25+1 < (( Ev and 2 5 < Σ क 255+1. which implies म. _ E2 x E 5 n 10 Ex. Also, we know that ||ا 1/2 (Rz+1 u2)ll2 S On²)) and ||0-1/2 f S S The latter
inequality along with the fact that Σ < n 10 Ey implies that ||ا,5 1/2 - P As+1)lla - S So, by triangle inequality, | / (n pe 2l2 - 0(n)) n
Next, we claim that i' & PJ+1. so i' & Qj+t. Indeed, we have that O(ne) Ex $ Ej+t + 0(n²) (np which immediately means nio Eşt1 & O(ns) Ejt1 $ Ey < <( Ext1 $ n 10 Ej+t Also, || (0 p2)ll2 S O(n"), and since Ep x 20 -Et+,, this means || 15-1/2 (uw P 1)12 S O(n S 22 Thus, the algorithm will remove (uy, My) from Q at step j + 1. i' & Q1+1-
Thus, either P. is empty, or Q2 decreases in size to Q5+1 for each 0 J S k This implies that Pk is empty. i.e., for every i E [k] such that ul 2 k. (Mi, Σj) & 22 This can only happen if each such (14 E,) was removed at some point. So, for every such i, there was some index j such that
12 Σg x E, & 12 En and | 1/2 - A5)ll2 I n2
E.3 Summary and Completion of Analysis
To prove our main result, need ensure that our algorithm is private, uses few enough samples, and accurately learns the mixture. Privacy will be simple, as we have shown in Lemma E.6 that the crude approximation private, and the hypothesis selection private shown in Appendix D The sample complexity will come from the settings of n and n' in lines 3 and 18 of the algorithm, and from our setting of parameters. Finally, we showed in Lemma E.6 that we have found a set of (pz. Eÿ). of at most is mean- covariance pairs, such that every true (pi, .x) of sufficiently large weight is crudely approximated by some (ūy, E. Indeed, this is exactly the situation for which we can apply the result on private hypothesis selection (Lemma D.3 based on [BSKW19).
We first quickly summarize how to put everything together to prove Theorem 1.4
We are now ready to complete the analysis and prove Theorem 1.4
Proof of Theorem 1.4 By Lemma E.6 note that the algorithm up to Line i7 (c. 5)-DP with respect
to X1..... X,, and does not depend on X X Xn+n'- Assuming {āa. E,)) from these lines
is fixed, Lines 18 20 are (=, 6DP with respect to .,, by Lemma D.3 and do not
depend on XI..... Xn. So, the overall algorithm is (E.
Next, we verify accuracy. Note that by Lemma E.6 and for G = n2 the sets (āj, Σ.) that we find satisfy the conditions for Lemma D.3 with failure probability at most Olk Bo). This probability is at most 0, assuming ed is significantly larger than k. So, it suffices for n', the number of df (fk-log(G 06
samples used in Line 18 of Algorithm to satisfy n' 2 O (dkklog(G-kkV//a) δ
a²
where the last part of the bound holds by our assumptions on G and n. Thus, the
total sample complexity is
kdd (
(kee a
kdd² d..75 log (
11. log 1gg... (1/0)
12d
n n
aE
By Lemma D.3 with failure probability at most 0.1, Lines 18 20 of the algorithm will successfully output hypothesis which is a mixture of & Gaussians, with total variation distance at most ((a) from the right answer. So, the overall success probability is at least 0.8.
31

---

Finally, we note that the assumption that e" is much larger than k can be made WLOG, by padding d' be sufficiently large multiple of log k. Namely, if given samples X; (X,,....... Xi,)), we can add coordinates Xi,++...... X Xollog R) ~ (V 1). Then, if the original samples were a mixture of k
Gaussians (u, Σ,), the new distribution is mixture of & Gaussians NV (6)) 2 9) with
the same mixing weights. So, we can learn the mixture distribution up to total variation distance a in the larger space, and then remove all except the first d coordinates, to output our final answer. This will not affect the sample complexity by more than poly(log k) factor.
F The Univariate Setting
In this section, we provide the algorithm and analysis for Theorem 1.5 We first describe and provide pseudocode for the algorithm, and then we prove that can privately learn mixtures of Gaussians with low sample complexity.
We will use o; == VE, denote the standard deviation univariate Gaussian M(Hs Ex).
F1 Algorithm
As in the algorithm in Appendix we will actually draw total of + n' samples. We start off by only considering the first n data points X {Xi...., .n). where each X, E R. Now, let Y (Yi..... Yn) be the sorted version of X, i.e. Y1 Y2 S S Yn. and (X1...., Xn) and (Yi..... Y,) are the same up to permutation. Finally, for each j S n 1, define Zj to be the ordered pair (Y,, Y,11 Yj), and define Z Z(X) to be the unordered multiset of Zj ss (Note that Z depends deterministically on X.)
The algorithm now works follows. Suppose we have data X = (X,,... X,). After sorting to obtain .i..., Yn, r;; Yj.88 = - Yj. and Zj- (Ty, 85). So, Z(X) = {(rj, 8z) hishsn- viewed an unordered set. Note that every 8, 2 0, and the Ty 's are in nondecreasing order. We will
create set of buckets that the bucket labeled (a, b) E 2² 2f S 83 < 20+1 and b n 2 rj < (b 1) n 2 If 8j 0. we do not assign Z, to any bucket.
be bijected onto Z For each Zj= (r), if 83 > 0 assign Z3
For each element 2.2 keep track of the number of indices j E [n 1] with Zz sent In other words, for (a, b). we define the count ce #li 2n 8j < 20+1 b n. 2n < ry < (b+ (b+1) .. For each Ce. we sample an independent draw Je ~ TLap(1, E/000,,,1000/ 5/10), and define C. Ce + ge. Finally, we let S (fu E,}} be the the set of pairs (b n 2" 220) where (a, satisfics Ce > 100 log 1
Hence, we have computed some {AA E for some K' 2 0. (We will show in the analysis that K' S n always, so k is finite.) If k we simply output L. Otherwise, we will draw Ô (+4+ + }) fresh samples. We run the s-DP hypothesis selection based algorithm, Algorithm on the fresh samples, using parameters G = n and {At, Σn
Pseudocode.
We give pseudocode for the algorithm in Algorithm
F22 Analysis
We start by analyzing Lines covariance pairs.
19 which generates the set S ((is, Ł.:)} of candidate mean-
First, we note very basic proposition.
Proposition F.1. E < 1. Then, with probability 1, TLap(L, 8/10) is at most 100 log 3 in absolute value.
ee/i0 -1 Proof. By definition of Truncated Laplace, [Taap(,, 1 8/10)l < [5/10] log 1
26/10
with probability 1. For e, 8 < this is less than 100 log J.
32

---

Algorithm 3: ESTIMATE CIMMMATEDDCAA D(X1, X2. Xntw E R, h E, s,
Input: Samples X1....,,,, Xn+1..... 1........ Xnta' Output: An (e, 6D-DP prediction ((Tr, E,), w. /* Set parameters */
Let K poly log (A: 4, 1, {) be sufficiently large.
Set + K klg(11/))
/* Get */
Obtain samples X
X...
/* Obtain some candidate mean-co covarioiae pairs (is, Ei) */
Let Y be X in sorted (nondecreasing) order.
Set b(a.b) 0 for all (a, E Z?
for j 1 to
do Set r3 +- 8j.85 + Y++1 y, 23 + (rj: 85).
if 8; > 0 then
Let logg (r,)), b+ 2-
10
Ca. t Co.b + 1.
11
end
12 end
13
S
-
0.
14 for (a, E 2 do
15
Sample Ca + co.6 TLap(1,e/10 8 8/10).
C > 100 log 8 then
16
S U [bb n 20,20,20 22
17
18
end
19
end
/+ Fine approximation, via private hypothesis selection +/
Set n' KK-
az
Sample X, ,+,,.... X nn, and redefine X (Xn+1, ..... Xntn')-
22 Run Algorithm on X, S ((A,, Σ.), with parameters 1, k #(( Ed), and = n
Next, we show that S' is not too large.
Lemma F.2. The number of e (a,b) E L2 such that ū. > 100 |S| 1n
llog 8 is at most 1. Thus,
=
Proof. Note that every Zj only increases the count of single ca. so suffices to prove that ā. 100 -log & only c 2
To prove this, suppose that c, Then, o TLap(1, e 1/10, 8/10) < 100 log 1. by Proposition F.I Thus, 8
100 log & can only happen if c. O. meaning c. 2 1.
Next, we show that for every Gaussian component (14, os) of sufficiently large weight wi, there are several pairs Z3 = (Y,, Ys+1 - -Y,) that crudely approximate (14,
1 Lemma F.3. Ler n 2 K llog(1/)) where K poly log(k, a: z: log 1) is sufficiently large. Let X be i..d. samples from GMM with representation {[w,, μ4, [ Then, with failure probability at least 0.99, for every i E [k] with w, 2 Et there are at least a 8k n indices j such that
Y, [m4 o. p4 σ.] and To Y,+1 Y2 20
Proof. Fix some i [k] such that w; -- Chernoff bound, since we
is sufficiently
large multiple of log k with failure probability at most 1000s. the number of data points X, from component is at least n. Let us condition on T; C [n], the set of indices coming from the th mixture component, and condition T.
Then, by Chernoff bound, with failure
33

---

probability at most 1 1000k at least points X, : T3 are in the interval Ius os, H4; + oil- Next, note that for any Xr, X, ~ (N, of). X, X, ~ (0, 20 and thus has magnitude at least Tops with at most To00 failure probability. So, by a union bound over all r + r' E T, with failure probability, all data points Xr, X, for + r' E T; are separated by at
at most 1000m
1 I 1000k
least of 10
So, with at least 1000k failure probability, there is a subset U, C T, of size least a n, such that 4k for every r E U,. X, X, and for every E U4, X, E [m, 114=00 -ss My + o.]. By a union bound, this holds simultancously for all i E [K] with wy 2 E. with probability at least 0.997.
Conditioned on this event, if we consider the elements X in sorted order (i.e., Y), between every d, consecutive pair X,, X, : 'r, E U; (after sorting), we know X, X, 2 104- So, there exist some X, y, Yj+1 I X, such that Yj+1 -Y, 10t-ne- Hence, for every
[k] with W/ 2 o de 10 Moreover, note that Y, 1 [M oz. 14; J.I. so J+1 Y3 20,, Hence, conditioned on the event from the previous paragraph, the lemma holds.
a there exist at least [U,] - 1 4k
2 a indices j such that Y,+1 - -Y, 2
8k
Given the above lemma, we can prove that for every (14, Ex) in the Gaussian mixture with at least g weight, there is some corresponding crude approximation (ii, )) E
Lemma F4, Assume that the conditions and result of Lemma F3 holds. Then, there exists (Ø, ε.) E S
such that n 10 n-10 Σ E, x no Σ and ع|ا 11-11/(14 B)]1 S n
Proof. Fix any with wi 2 E. Then, for any j with Y,, Y1+ E 1u--0,, o, p4 to, and 10
di
SYs+1-
Y, S 20, the index contributes to the count of some bucket e (a, b). where [log2 d S I [loga(2s;]], Moreover, Y, E [b n² 2 (b + 1) n5. 2%). Therefore, if we consider the set Vi of E (a, b) such that [log2 -o S < [oog((o,)) and [b n² .20 (b + 1) n²
2*) n [P: - o, u4 + 0,] is nonempty, the sum of the counts ce across such e E V2 is at least SE n. But there are at most Ologgn) choices of and since n 2a 20, there at most two choices for b for any fixed a. So, Vil S Olog n). and Eeev, Ge 2 SK n. Assuming that
a n 2 O(log n 1 log }). i.e., n 2 K.
(log(1/8) for a sufficiently large polylogarithmic factor ae
SE
K = poly log (k, a: e: log }), one of these buckets e = (a. b) E Vy must have ce > 200 log }- In this case, & = ce + T'Lap(1, 8/10) > 100 log 1 by Proposition F.1 so we include the pair
1 1.1
(ù, E) = (b n 20, 220 in S.
2 22a) in S. By definition of V, Hence, there exists (a, b) V; such that (β. E) (b (b.n² no.
# S 2" < 20, so no E, I 2 < 4E, S 10 Σ,. Moreover, 1 A 2 a [4 Al..
But the definition of V, means P b. no 2 satisfies jt S 14 + a; and j 2 14 0; n 2 >
14 (2n + 1) o,, So, p pul S (2n² + +1 o, S n 22. Thus, [ 1/2 - p4ll S n
We now prove that the mechanism (until Line 19 is differentially private. First, we note the following auxiliary claim.
Lemma F.S. Let X, X' be adjacent datasets of size n (i.e,, only disfering on a single element). Then, the corresponding sets Z = Z(X) and Z' = Z(X') differ in distance at most 3, where by distance mean that there exists permutation of the elements in Z and Z', respectively, such that at most three indices S n - 1 satisfy Z, # Z'.
Proof. Note that for the sorted versions Y, Y' of X, respectively, by removing one data point and adding one more data point, without affecting the order of any other data points.
convert from Y to Y'
Suppose we remove some Y, from Y. if = 1, then this just removes Z1, and if j = n, then this just > 2, this modifies Z,-1 and removes Z,. Likewise, if we add some new Yy, this will either add one new ordered pair to Z (if Y, is either the smallest or largest element), or replace one ordered pair in Z with two new pairs. Therefore, if we remove Y, and then add Yy, this will change at most of the ordered pairs in Z.
removes -n If
We now prove privacy.
34

---

Lemma F... The set S = {(āg, E of candidate mean-covariance pairs is (s, 6)DPP with respect X (X1..... X-
Proof. Let X, X' be adjacent datasets of size Then, the corresponding sets Z, Z' (after possible permutation) differ in elements. Therefore, if we let {åz hegae be the counts for and {2. be the counts for Z', have that ||c & S 6. Because changing single count ce by leads to (e/10 8/10)-DP, overall, the counts { will satisfy (e, 6)-DP. Finally, is deterministic function of the noisy counts če, and therefore must also be (e,6)
Finally, we can incorporate the fine approximation (i.e., Lines 20 of Algorithm 3 and prove Theorem L.5
Proof Theorem 1.3 By Lemma F.6 the algorithm up Line 19 is (c.0)-DP with respect to
XI...., ......,,,,,,.. and does not depend on Xn+I...... Xn-n' Assuming {(A,, Σ.) from these lines is fixed, Lines 20
22 are (e, 6DD with respect to Xat1,..., Xn+n', by Lemma D.3 and do not depend on XI...... X So, the overall algorithm is (e, 6)-DP.
Next, we verify accuracy. Note that by Lemma and for no the sets (pi. E,) that we find satisfy the conditions for Lemma D33] with failure probability at most 0.01. Moreover, the size of 5 ((14, } is at most by Lemma F.2 So, because d = 1, it suffices for n', the number
of samples used in Line 20 of Algorithm 3 to satisfy n' 2 O A=
a² + A-log(G-Ann (a-K///))))
Ô ( + .x)), where the last part of the bound holds by our assumptions on G and n. Thus, the total sample complexity is
n + n' = Ō (0 log(11/)
k
DE
a
By Lemma D.3 with failure probability at most 0.1, Lines 20 22 of the algorithm will successfully output hypothesis which is mixture of & Gaussians, with total variation distance at most ((a) from the right answer. So, the overall success probability is at least 0.8.
G Lower Bound
In this section, we prove Theorem 1.6 The proof of the lower bound will, at a high level, follow from known lower bounds for privately learning a single Gaussian [KVI8] KMS22a], which we now state.
Theorem G.1. KV18 For some sufficiently small constant c*, (s, 8)-piiaay learning an arbitrary univariate Gaussian N o²) up to total variation distance c* requires Q log(1/8) samples.
Moreover, this lower bound holds even if we are promised that |p| S (1/8) for a sufficiently large constant C, and a 1.
Note that this lower bound immediately implies the same lower bound for general dimension d.
Theorem G.2. [MS22a Let be at most a sufficiently small constant, and let S (ac)
C (at) for sufficiently large constant C. Then, (s, 5) -prrivvat learning a d-dimensional Gaussian N (M, Σ) up
total variation distance requires i de
samples.
as
Moreover, this lower bound holds even if we are promised that μ.. = 0, and Σ 2I.
Note that tighter version of the above theorem has been proved in Nar23 PH24 also refer the reader to BUV14..
Proof Sketch of Theorem 1.6 First, the lower bound of kaft o
is already known see ABH+ 18
The lower bound of hdd as
will follow from Theorem G.2 explain how, we consider à distinct Gaussians (i,, Σj). where the means μ4 are known and very far away from each other, and & E, x are unknown. The overall mixture that we will try to learn the uniform mixture over NW,, E,), i.c., every weight w; 1/k. By making them very far away from each other,
35

---

making learning the full mixture equivalent to learning each component (on average). Namely, even if we are given the information of which Gaussian each sample comes from, we will need to learn at least 2/3 of the Gaussians up to total variation distance ((x), to learn the full mixture up to total variation distance a. Hence, we will need least times as many samples as for learning a single
Gaussian, which means need ?
Idd
total samples.
CE
The lower bound of k log(1/5) will follow from Theorem G.1
Note that it suffices to prove the lower bound in the univariate case. We plant & distinct Gaussians A (14, 1), where the μ4, very far away from each other, i.e., pairwise |14 (1yl > (1/6) 1OC, We also assume that #r = is known, and the remaining μ4 are unknown but we are promised the value of each μ4, up to error (1/8)o. The overall mixture will have the first Gaussian (0,, 1) of weight wi = 1 a/c". and the remaining Gaussians Nip, 1) each have weight w; = a/(c" (k- 1)). Even we are given the information of which Gaussian component each sample comes from, learn the overall mixture up learn at least 2/3 of the small-weight components, each up to total variation distance (c²)). Hence, will need log(1/5) samples from most of the small-weight components. Since the small weight kk log(1 (16) ax
os
a, need to
components have weight (a/k), need f
total samples.
We now give a formal proof of Theorem 1.6.
G.1 Formal Proof Theorem 1.6
First, we note two lemmas that will be helpful in proving the Theorem.
Lemma G.3. Let [0, 1). Let f be a probability density function over Rd, Assume g RR + R22 exists such that
[ [f(x) - g(x)] dx S a.
Then there exists h such that h a probability density function over Rd, and
[ [f(x) h((x)l dr S 2o.
Proof. We know that
Jpe [(x) dr ff ye g(x) de <
$ Ja 1f(x)) g(x)l dr S a.
Therefore, G=
= Se g(x) = 1
Now two cases possible either G < 1, G > 1, otherwise are done. If G < 1, let h(x) be the density function corresponding to the following distribution: with probability take sample from ga and with probability 1 G select O. Then
S (5(x)= h(x)) dx < G G
[ [1()) - -())) dx S 20,
as desired. If G > 1, let h(x) be density function as follows: Vr < h(x) I g(x), and Jgg h(x) dr 1. is easy to see such an h exists by greedily picking h. Then we have Sza 19(x) - Mxx)] dr = Sau g(x) - h(x) dx S S a. Therefore, we can write
[ [5(x) - -(xx) dx < / [5(x) g(+) dr + [ (9(x)) - h(x)) dx S 20,
as desired.
Lemma G.4. Suppose w (0,1) fixed. Suppose an (e, 8) differentially private algorithm exists that takes n samples from the mixture D = wD, + (1 D2, and learns D in total variation distance up to error a, with success probability - 33. Moreover, assume while sampling it is known which component the sumple is sampled from. Then there exists an (e, 8) differentially private algorithm that takes ww/ samples from D, and outputs an estimate of Dr up to total variation distance with success probability 1 3 %
36

---

Proof. We can view the sampling procedure of the mixture as sampling a random variable t ~ (in(n, w), and taking samples from D1 and n - samples from Dz. In order to make an algorithm using nw/7 samples we can take that many samples from D1, and then sample / from Bin(n, w²) and run A on n data points constructed as follows: If is smaller than nw/n use of the samples taken from Dj and set the rest to 0, If is larger than nw/n,, just run A on all zeroes. Finally output the output of A on this input. Clearly, this would be (s, 6) differentially private. We know the Algorithm succeeds with probability 1 - B. over the random coins of the algorithm and the randomness of sampling, if the input is sampled from wD1 - (1 - w) D2. From Markov's inequality, we know Plt S nw/nyl 2 1 % Therefore, our constructed sample is drawn i.i.d from wD1 + (1 w) D) with probability at least 7, where D2 is the fixed 0 distribution. Therefore, there exists an (e, 6) differentially private algorithm that takes nw / many samples from D1 and outputs estimate of D₁ up to total variation distance a with success probability 1 - B - 7/ as desired.
We now prove Theorem I.6
Proof. We prove the lower bound terms one by one. The first term kd (the non private term) is o² known by previous work [ABH* 18). We prove the lower bound for the second term and the last term here using Theorems G.1 and G.2
Let's prove the second term than sufficiently small constant, and 5 I (a)) for sufficiently large C, any (c,6) 5) differentially private algorithm A taking samples in Rdd satisfying
kd?
We apply Theorem G.2 this theorem implies that for any a smaller
az"
VΣ such that ~ Σ x 21: (0. A's internal random bits
Σ)) S a] >> 0.6,
must also satisfy n = 21( _e
Let yás be distinct vectors in Id each having & distance M from each other, for M to be set later. To why such a set exists, can take μ4 M Mie,, where e1 is the first unit vector. Now consider the following set of Gaussians: D; = (H, Σ.), where μ4; 's are known and constructed as above and E, unknown. Consider the uniform mixture D over these Gaussians, with weights w; = 1/k. We also assume that when sampling from this distribution we know that which component the samples came from. Consider an (c, differentially private algorithm A that takes samples from D and outputs distribution D such that drv D) S a with probability 2/3.
Now consider a sample from D;, from standard Gaussian tail bounds we know that at least 1 exp(- 22 /800) fraction of the mass of D, is contained within ball of radius M/10, around p4. Let B, denote this ball, and note that B 's are disjoint.
Let f. fer f be the probability density functions corresponding to D, D,, D respectively. Assuming, write
we are in the success regime,
&
2a > 2ddv -(00)
](w) dx > Σ ///1r0 ((a))
dr.
1=1 B.
Now let B C [k] be the set of indices i such that Se. [((m) - /(x) dx 2 200a//, and G be its complement. Then we have that [B] S k/100. Therefore, there exists such that |g] 2 0.99k, and Vi E G Sp. f(x)- f(x) dr 200a/k. Assume G is one such index. Note that f(x) = - (z)/kk Therefore, we can write
f R3
[ - f(a) dr S
/ [s(a) - -(w)] dx + / [f((x) - f(x) dæ nq
n.
< 2000// + max FX-D, [X $ B,]
371
< 200a /k + expl( -
< 300a/k,
37

---

where the last inequality comes from taking M 2 30ylog(k/110aa) We show that using the distribution D, we can construct an answer to the problem of learning the Gaussian D;. To do so first take 9s to be equal to (x) over B, and 0 everywhere else. We have
S/ 11(())
gi((o)] dr= S B.
- -k(()) dr / [i(x) dr 300a 100a/ / 400a. JRABB
Now we may apply Lemma G.3 and deduce that given D we can construct probability density functions and distributions D,'s 's such that (T, D,) S 800a, for all i G. To recap, so far we have shown that given an (c,6) 6) differentially private algorithm that takes as inputs samples from constructed mixture of Gaussians and outputs a density D that has total variation distance at most a, from the ground truth distribution with success probability 2/3, can use Á to construct densities Dj such that drv (D;, D,) < 800a, for 0.99k of the indices i. This implies that there exists a fixed index i for which the component D; is learned up to error 800a with success probability 2/3 - 0.01 2 0.65. Applying Lemma G.4 implies that there must exist an (e, 6) differentially private algorithm that takes 100n/k k: samples from D, and estimates its density up total variation distance 800a, with success probability at least 0.6. Therefore, applying Theorem G.2 we conclude that n 22 kdf
A: (1/() It is easy to see such a set exists. Now consider the following set of Gaussians: D; = =N 1), where 14''s s are known up to log(1/5)C, and lu = 0 is also known. Consider the mixture D over these Gaussians, with weights wi = - a:/c", and w; = a=(c 1)). We also assume that when sampling from the mixture we know which component each sample comes from. Consider an (c, 5) differentially private algorithm A that takes n samples from D and outputs a distribution Đ such that drv(D) D) S a with probability 2/3.
cx We aim to apply Theorem G.1 Let μt's be k distinct values in E, each having distance M from each other, for M > (1/5) 100 to be set later, where 141
Now let's prove the last term
Now consider sample from D;, from standard Gaussian tail bounds we know that at least 1 - exp(-M² /22000) fraction of the mass of D; is contained within a ball of radius M/10, around μú. Let B, denote this ball, and note that B, 's are disjoint.
Let J, fi, f be the probability density functions corresponding to D, Di, π respectively. Assuming, we are in the success regime, similar to the proof of the previous term, we can show that there exists
((()) M(x) dr S 200a/k. kk Moreover, set G of indices such that |g] > 0.99k, and Vi J...
with a similar argument as the previous term for i E 9 we can say as long as M 2 20 /oglook SP. [xff((z)) - f(x) dx S 3300a/k. We show that using the distribution D, we can construct an
answer the problem of learning the Gaussian D,, for i F 1. To do so take gi be equal to f (z)/w,, over B, and everywhere else. We have
J gx(x)) dr= [
L. |1: f(x)/ws dx S fx(x) dx S
300a: kw; k
100a
+
I 400c..
JRMNB.
Now we may apply Lemma G.3 and deduce that given D, we can construct probability density functions and distributions D,'s such that drv((D, D:) < 800c", for all i E G. To recap, so far we have shown that given an (e differentially private algorithm that takes inputs samples from our constructed mixture of Gaussians and outputs density Î that has total variation distance at most a from the ground truth distribution with success probability 2/3, we can use D to construct densities ń, such that drv (D:, D,) S 800c*, for 0.99k of the indices i. This implies that there exists fixed index + 1, for which the component D; is learned up to error 800c*. with success probability 2/3 - 0.01 2 0.65. Applying Lemma G.4 implies that there must exist an (c, 6) differentially private algorithm that takes 100nw;; samples from D, and estimates its density up to total variation
distance 800c*, with success probability 0.6. Therefore, applying Theorem G.1 and noting that
wi = a/( (ks 1)) we conclude that 2 k log(1/8)
38

---

H
Omitted Proofs
In this section, we prove Proposition B.2 Theorem B.3 and Lemma C.7
H.1 Proof of Proposition B.2
First, we note basic fact.
Fact H.l. For any E [0.9, 1.1), we have that (zy- - 1)2 < 4((x 1)2 1))-)
Proof. Note that jzy 1| Jr- + x 5-- --- 1 V2- -1
Thus, (zy - 1)² < 2( (z 1 + by 11) 4((x 1)a +y
We now prove Proposition B.2
Proof. Let J1 = Ex 1/2 and J2 = Egg 1-1 //1//
21
First, assume (,I,E1) Σ1) p, (12 E2). This means [JJJ Tlppp S and || T|E S p. We then have that Σ 1/1 Sn 1/2
1-1122 = J = (JT Now, note that J.JI and J. Jı are
both symmetric and have the same eigenvalues. If we call these eigenvalues A1...., ,,, Ad, then the eigenvalues of ΣΙ E 1/2 are \o ".....,7'' Now, our assumption (#1. Σ1) Pyyp.r (/2 Eg) implics that 1 7- v > & 1+ and (1- p². This means that, assuming 7 I 0.1, 1 22 S
I A S - < + 27, and E ))
< );)² 2 2. (1 X,) 2p²
This means that |>-
1/2 //2 1/21| 1lop S 27 and |Σ.]
1/2 E3 1/2 S 2p.
Σ₂ (μI p2) has magnitude at 1/2 (MI p2) has magnitude most the maximum singular most 7 by our assumption, 1
Finally, ET - 12) = 1ー 1/2 (11 u2). Because Σn 1/2
value of J times т. But every singular value of J is some X; which is at most 2, so |/ (u2 - = 1/2 (/2111 - p2)ll2 S 2T.
Next, assume (11, E1) Zypp (12, E2) and (#2, E2) Rigar (Ux, Ez). First, note that E, "3 eigenvalues of J2JJJ are (X,). then the singular values of J1 and Jz are {vA,) and VX), respec- tively. By our assumption, 1-7 S Ar < 1+7, which means that -I-75 VT, VX, < +T+ Thus, the singular values J1 are between 1-2 ? and ++7, 7. which means that the eigenvalues of (J2J)) are between (1 72 and (1 + 7 Hence, for y S 0.1, [| J2 -llop 47,
J2J1J JJ (J2J1) If the eigenvalues of JT are {Ap} and the
Assume that År X; are in decreasing order. We now consider the hthh largest singular value of J2J1. Tk == VAg is the gth largest singular value of Jj and of := /X, is the 1eth largest singular value of J2. by Corollary A.5 there exist subspaces V2, V/ of dimension d - ls + such that [|Jeel|2 ax|lelle for all Va and |||2e||2 I ofllell2 for all
V% Therefore, for every E V2 J.'V (note that J1 is invertible since J has all eigenvalues between 1 y and 1 + 7) have that ||l2J ooll/uulla S 1 Because V2 and ' Vg both have dimension d + 1, their intersection has dimension at least d 2 + 2. So, there is a subspace of dimension at least d 2k +2 such that every in the subspace has ||
o.o ||e||22
Thus, the (2k- 1hth largest singular value of Jr.J1 is at most o so the (2k (2k-1)t largest eigenvalue of J2 J22 is at most Xx The same argument, looking at the smallest singular values, tells us that the (2k - 1 smallest eigenvalue of JT J2 is at least Ad- 1a-- 1+1 Thus, for any t, the th largest eigenvalue of J2J J is at most A((0+1/22 X Mic+n/2 and at least )((a+))2) ((aa-)
39

---

Overall, this means that
[22 -11 1
Σ max (AICCD)//\((TD/)) 1)?, (ATa400/21 - -1)²)
Σ
(((441)) +(1444))/N((a-00)1 - -))²)
d
= 2 Σ
(Mr1) - 112
1=1
$ 8 Σ
(A 1)² + " (X/ 1)²
i=1
s 8 (IJI 1| + 1112222 -1 16p²
where the fourth line uses Fact H.1
Thus, |Σ Σx Σn 1/2 1| S 4p.
Finally, note that |<g 1/2 (11 pa)ll2 s |Eg 1/2 ( - | Eg 1/2 1/2 ~ 1| 1/2
(11
222 + Mg 1/2 (12 M4)) 122 By our assumptions, both Σg 1/1 (w1 12) and ΣΣg 15-1/2 1/2 (12 11)ll2
most т, and J2 has operator norm most 1.1 2, which means that || 3r.
1/2 (11 12)lla 5
H.2 Proof Theorem BS
First, we note series of known results that will be key to proving the theorem. We start with the bound for robust covariance estimation spectral error.
Lemma H.2 (e.g., DK22 Exercise 4.3]). Fix any 1i E (0, 17),, where no < 0.01 is a small universal constant, and fix any 3 E (0, 1). There is a (deterministic, inefficient) algorithm A₁ with the following property. Let Σ E Radd be any covariance matrix, and let X = {X1,..., ".....,,,,,
(00 E), where 2 O(d((+log(())) (1/))///////)) Then, with probability at least 1-3 over the randomness of X, for any rp- corruption X' { Xx, Xf A1(X)) outputs En such that | E-1/2 - 1/2 1/2 T S O(n). Importantly, A may have knowledge of and B, but does not have knowledge of X or E.
Next, we prove how to robustly estimate the covariance up to Frobenius enror. We start with the following structural lemma.
Lemma H.3. There exists a universal constant e E (0,0.1) with the following property. Fix any 1 < k < d, and let n 2 O(d k) be a sufficiently large (i.e., 2 dk (C' log(dk)) for some absolute constants C3, C4). we sample i.i.d. X {Xi,..., .... ~ 1), then with probability at least 1 e-on over X. for all symmetric matrices P Raxd of rank most k and Frobenius norm 1, and all subsets S C [n) of size at least (1 - c) n, Eies (X.) - -T S.1.
Proof. Consider any fixed P C [Rdxd of rank & and Frobenius norm 1, and fix any integer m. For any data points XI..... Xm iid NNO, I), let X (X,,.., Xm)) [Rm-dd be the concatenation of X1, X1y...y Xmn and Q ((md)x((md) the block matrix
P
0
0
P
0
P/
40

---

Then, 1 (X, -1 (x, PX; - Tr(P)) = - Tr(Q)). By the
Hanson- Wright inequality, we have that for any fixed ||| S 1, and for any 1 1 1,
IP m
(xQx (x))x- >1) - >1)=
(1x TTTTxx- F==QQx-in -T+(Q) m.
$ exp (-min {{mm)) l(mt))
m || ||
2 exp (-9(m +²))
By setting t = 0.01, we have that for some universal constant C1,
1 m
P
Σ
(Xx77
P)
> 0.01
< 2e mm
Now, we draw XI...., X, ~ (O, I), and take a union bound over all subsets S C [n]] of size at least (1 - c)n (with m (S)) and union bound over a net of possible matrices P. The number of options for S is at most Eisen (*) < (e/c)en. For P. we can choose 1 1/n""-sizee net over the Frobenius norm metric (i.e., the distance between
matrices P1, P2 is || P2(l for each of the k nonzero eigenvalues and eigenvectors in the unit d-dimensional sphere, which has size at most 100d-k Therefore, by a union bound, the probability that | ( - I, P') 0.01 for every 2 (1 c)n and every P' the net is at least (2e/c) 1000 e-cin/2
Finally, we consider P' outside of the net. For any symmetric / of rank k and Frobenius norm 1, it has Frobenius distance at most 1/n from some pr in the net. Let us consider the event that every ||x,122 - 10n, which for n 2 d occurs with failure probability at most 2n e e by Soinsnn-Wrigh..
Under this event, (X:X? - T, P P') S | /| ||P P'I| S (10n + vd)/n² < 0.01.
As a result, with failure probability at most (2e/c)en..g -n 100d - - -cin/2 e is sufficiently small), we have both properties. Namely, 1, EiEss (X,X; - -I,P") I 0.01 for every |S| 2 (1 c)n and every p' in the net, and for any P. (X,X; in the net to P. Overall, this means that for all such and S. π Eies (X.x, - I, P) $ 0.1. 0
-in < e (assuming
1,P - P')0.01 for the closest pr
We prove another lemma which contrasts with Lemma H.3
Lemma H.4. Fix any 2 S S Vd. Let k = p3/ and let 2 Õ k) and c E (0,0.1) be as in Lemma H.3 Fix any covariance matrix E. and let X = (X, ..... Xn) ~ NO, E). Then, with
probability at least e for every E such that 0.95 E < Σ x 1.05 Σ and 1/5-1 1/2 of rank at most is and Frobenius norm 1, and for
I| 2 p.for every symmetric matrix P E Rdxd d every S [n] of size at least (1 c)n,
1/- X,XX L, 2.7.
1/2
T2 ES
Proof. Let - S-122111// and let Y; 1/1 x,. Then, 5-1/2 X; JY,, which means that 1 JY,Y, J - J(,YY, -1yJ +JJ 1).
X-1/2X,xX
From now on, we assume that for all S c [n] of size at least (1-c) c)- -n, and for all symmetric matrices P of rank and Frobenius norm 1, Σ iss (Y,Y, P,P) < 0.1. This happens with least -co probability, by Lemma H.3
Now, for any subset S C [n].
1
E-1/2 X Σ 1/2 T.P) n iEs
1 Σ (JOYY TYJT, P) +) (JJT -T
n
Σ Tr(J(YY - (DTTP)
|S| (JJT I,P)
n
71
1
Σ -I,JT
|5| (JJJ IIP).
n
n
NES
41

---

Now, note that by our assumptions, ||51// Tloop S 0.05 and | 1/2 11I 2 Thus, by Proposition B.2
|1-11/22;-122-111 1loo S 0.1, and by Proposition B.2 again, applied the
reverse direction this time, | 1/-1/25551/22_ -1 2 p/2. We just showed JJ 1 op S 0.1, so
by Proposition A.6 ||J P I p - Therefore, I, EVe, I, J PJ) - 0.2.
Conversely, we just showed |J - F 2 p/2. So, if we order the eigenvalues of JJJ as \1, A2, ................................ Ad (and the corresponding unit cigenvectors V1...... va) such that | 1 are in decreasing
order, then Σi= (A: - 1)2 2 p²/4, which means that Eisl (A, - 1)2 2 1. So, if we choose P to E 0 (A: - 1)²)
-1/2
" (Ai 1)uce we have that || = and
be
4d
-1/2
4d/0²
Adip²
1/2
(JJT - I, =
Σ 1=1
(Ai 1)2 1)²]
Σ
- 1)²
Σ 1=1
(A: - 1)2
21 1.
==1
Therefore.
S 0.2 0.2210
Σ 1/2 1,
C- 0.2 2..200 0.7.
71
n
RS
Now, we can show how to learn the covariance of Σ up Frobenius error.
Lemma H.5. Fix any E (0,10), where no < 0.01 is a small universal constant, any 3 E (0, 1), and any ((n) S p S Vd. There is a (deterministic, possibly inefficient) algorithm A2 with the following property. Let Σ E Rdxd be any covariance matrix, and let X {X1,.... X,}, (0, E), where 2 O
d 2llog((1/9) + +log())) Then, with probability at least 1 - B over the randomness of for any n-corruption X' {Xi.... X² of A2(X') outputs Lng such that ||51 I||F= < (p).. Importantly, A2 may have knowledge of n, p. and B, but does not have knowledge of X or Σ.
Proof. In the case that o S 2, the claim follows immediately from known results (for instance, implicit from [HKMN23))
Alternatively, assume that p 2 In this case, the algorithm works as follows. Assume 7 1/0 S c/2, where is the constant in Lemma H.3 First, compute ΣS based on Lemma H.2 Note that (1 - (())) Σ & En & (1+ + O(r)) D with 1 - 3 probability, since the number of samples is sufficiently large. Now, find any positive definite Σ and a set T C [r]] of size at least (1 - v)),, such that:
(1- EΙ x E < (1+)(1)) ET
* for any S C T of size at least (1 2n))n, 1 1- -1 S 0.2.
First, we note that Σ '' is a feasible choice of Σ. Indeed, the first condition trivially holds. For the second condition, let 7' be the subset uncorrupted data points (i.e., X! = X,). Then, for any S C T, the data points X for i E S are the same X,, so by Lemma H.3 with - 3 probability,
for every such S. 1.4 (E X/2X Σ - 1/2 I, P) < 0.1.
Next, we show that every E with 1/-1/2 that 0.955 & Σ & 1.05E, as otherwise, we cannot simultaneously satisfy (1 11-001 O(n)) ES < Σ x (1+0())) E1 and - O()) Σ E (1+0 Σ, assuming 1) - c/2 is sufficiently small.
I||F 2 p infeasible. First, we may assume
Hence, we just have to verify the infeasibility for every Σ such that ||-- 0.95% & Σ ④ 1.05E. Indeed, for any subset T of size at least (1 - -1)n, let S be the uncorrupted points in T. Because there are at most 7/n uncorrupted points, |S| 2 (1 21)mm. So by Lemma H.4
||| 2 p and
with probability, for every such S, 1 Eies --12 XX E-1/2 - 11)2-1,P) 1, 2 0.8.
42

---

Therefore, with at most ((3) failure probability, some Eg = Σ is returned, and it satisfies /5-1/255-1/2 T|E p.
D
Next, we note some results on robust mean estimation. We first note the definition of stability, and some properties.
Lemma H.6 (DK22 Proposition 3.3]). Let n 2 O((d - log(1/3))/a²), for some a 2 Onn/log 1/n). Let X
{x,] sid. D. where D subgaussian random variable with mean μs. E TR. and covariance Then, with probability 8. for all vectors b [0, 1]" such that E,b; 2 1) and all unit vectors v E Rdd we have:
1. E,bi(r, X; -1)1
2. (U, - 11)2 S
Given a dataset X with these properties, call it (1), o:)-stalle with respect to μ
Lemma H.7 (implicit from [K22 Section 2)). Fix n sufficiently small and a = (n). There is deterministic algorithm A3 that, on a dataset X', outputs is such that ll lull2 S O(a). for any n-corruption X of any X that is (7, -mman stable with respect to any E R.. Importantly, As does not require knowledge of X or μ.
We now prove Theorem B.3
Proof. We first show how to estimate the covariance E. First, we apply "sample pairing" trick (e.g., see DK22, Section 4.4)). Namely, assume WLOG that n is even, and define X to be the set {(X21-1 X2i) /2)m/ and X' {(X)=-1 X2)) 22)/v2/// Note that X are i..dd samples from (( Σ), and X' is at most 2nrcrord.e
n/2
Now, because 7 S y. X' is at most 2 corrupted, so Lemma H.2 on X' (replacing 7 with 2ry) gives us some Σn such that | 1/2 E 1/2 Moop I O7)), by our assumed bound on the number of samples. Next, Lemma H.5 on X' gives some E. such that ||Σ,1//25,
- T|]r < O(p), set Σ to be any covariance such that
by our assumed bound the number of samples. So, 10-1/25,,5114 7llop 0(7) and 1/5-1//5,,55111- T|]r < 3(p)) Note that Σ satisfies these properties, and any E that satisfies these properties must satisfy ||5-//$55-12 and |/0-1/255-11/ I| < Opp), by the approximate symmetry and transitivity properties (Proposition B.2
=[]F s O())
Now, we estimate the mean μ. Taking the original data X', we compute (É-1/2X/), By stability (Lemmal H.7 we know that with 1 - 8 probability, (/-1/2X4 12,, x.) is (n, 7s-table with respect to (where we are using the uncorrupted data and the true covariance E). Letting J 1-//////2 know that J has all singular values between 1 0(7) and 1 O()), and that $1 (n, -sttbble with respect to μ.. Moreover, note that we can write (v, 1/2 112 - p)) (Jr, J-1. Σ E-1/2(X,- (X,,+))) 4)). and that 1 1-0()) < [|Ju||2 < 1++0(y). Therefore. (5 1/2 is (n. (tt))- with respect to 11/2 ps which means that by Lemma H.7 A3 on {5-1/2 x/} outputs some value such that ||ا 2211/2pl12 < ( Thus, by setting j = 11/2 D, we have that - 2)1la < O(r), which means that | ( 1)]l2 || 1/2 m)ll2 (1 0(r)) ||Σ 1/2
is
2)ll2 < 0()).
H.3 Proof of Lemma C.7
In this subsection, we prove Lemma C.7
Proof. First, note that for any positive definite matrices Σ,, Ez, 1/" -llop S 7 is equivalent to (1 7) & 1,1/"2,,0) < (1 + I. Since M being PSD implies AMAT is PSD
-
43

---

(and vice versa if A is invertible), the previous statement is thus equivalent to 7) -E $ El + 7)E2. Next, note that
12 1/2 21 1/2 11 = Tr (In 1 1)2)
Tr 2 1/2 2 2ل - 2. 1011 1/2 + 1)
Tr (E د 2i E1 1 +1:
where the first two lines are straightforward expansion, and the final line simply uses the fact that Tr(AB) (r(BA) for any matrices A, B. Finally, note that
[> ( 2 v (M1 u2) Eg (22)
(5)
Now, consider replacing E with nا := م Dg with جn := 2 /
with μ3 ==
/ 14 + μu, and μ2 with f44 == 1// u2 /1 μ. Again, since M being PSD implies AMA PSD (and vice versa), we have that (1-7).E2 Σ (1+?). Eg if and only if (1-7) Σو $ Σg (1+7)-Ea E4. Moreover, note that
T
Tr (
E 1 1/2) Tr(E, M Σ, Σ Eng
and
TrE = Tr Σg 1- = Tr(E, \ )₂
which means that (4) would be the same if we replaced Σ with Σg and Σg with Σ,. Finally,
(us-)a) Σn (Ms-Pa) = (f p2) 1 1/2 1/2 (I1 p2) = (μr M22 Σの (11-M22
which means that would be the same if we replaced μt with Hax H2 with p4. E₁ with Eg. and Eg with Eg.
Overall, by the definition of R. we have that (n1, En) R... (12, D2) if and only (ug, 2g) Rygr (M4, 24).
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We give complete proofs for all theorem statements.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations about the data assumptions and practical algorithms, the end of the main body.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We give complete proofs for all theorems.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: No experiments.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: No experiments.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No experiments.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: No experiments.
9. Code Of Ethics
45

---

Question:
Does the research conducted in the paper conform, in every respect. with the
NeurIPS Code of Ethics httpgh/ttppp///crr....../ca/aatt
Answer: [Yes]
Justification: Our work is entirely theoretical, and we do not see any potential harms coming from our research.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is entirely theoretical, and do not see any potential negative societal impacts coming from our research.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is entirely theoretical, and poses such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use any existing assets, such as code/ddat//oodelseet.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release any assets
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing or research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing or research with human subjects.
46


Reviews:
[{"review_id": "Nif3EiEA9h", "reviewer": "Reviewer_u11i", "summary": "The paper studies the problem of learning a mixture of $k$ $d$-dimensional Gaussians using a differentially private mechanism with respect to the samples. It provides an improved sample complexity which has asymptotically optimal dependence on the dimension $d$ for small $k$, the lower bound is also given by the paper. Additionally, for $d=1$ the paper provides optimal sample complexity.  \nThe paper follows a high level approach of obtaining crude approximations of the mean and covariances of the component Gaussians, which can be used to reduce – using a net based argument – the problem to private hypothesis selection for which existing algorithm (needing only log the size of the net number of samples) can be used. To obtain the crude approximations respecting the DP guarantee, the paper uses a variant of the exponential mechanism with a carefully constructed scoring function measuring the distance between the a candidate Gaussian and any “heavy” component of Gaussian mixture. This uses a number of samples depending on the size of the sample set $n$ and the dimensionality the hypotheses $d^2$. A naive approach fails due to the blowup incurred, and the paper utilizes sample compression to reduce the dependence to $O(d\\\\log n)$ and improves the dimensionality dependence to $O(d)$ via an estimation argument.  \nThe above is outlined in more detail in the main paper and proved formally in the appendices. While all the details have not been verified by the reviewer, the approach taken by the paper seems correct.", "questions": "It will be useful to combine definitions 1.1 and 1.2 into a precise definition of privately learning GMMs.", "limitations": "Yes, addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper proves improved (and in some cases optimal) sample complexity for privately learning Gaussian mixtures.\n2. The paper uses a novel crude approximation based approach paired with existing algorithm for private hypothesis selection. \n3. The paper leverages inverse sensitivity mechanisms for  decoding the crude approximations, techniques for sample compression, and combines them with a way to improve the dimensionality dependence.\n4. The main result as well the one for univariate case and the lower bound together constitute notable progress on a well studied problem.\n5. The paper is well written and the provided roadmap greatly aids the understanding.", "weaknesses": "1. The sample complexity does not match the lower bound in the dependence on $k$.\n2. The degradation on the dependence on $k$ from the univariate to the multi-variate case is not explained in the main paper.\n3. The details of the various technical parts are tedious and could be alleviated by better presentation, e.g. by listing all the parameters and their dependencies in a table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed feedback. We now address some of the issues/questions raised by the reviewer.\n\nNote that the algorithm for the univariate case (Section F) is completely different from the multivariate case (Section E). The algorithm in the univariate case requires us to order the data points from smallest to largest, which doesn’t make sense in high dimensions. So, it only works for $d = 1$. We could use the multivariate algorithm when $d = 1$ as well, but we would get a worse dependence on $k$ (more specifically, we would get $k^2$ in the bound rather than linear dependence on $k$).\n\nWe are happy to list our results, along with previous results, in a table so that one can easily compare our work with previous work (as well as compare upper/lower bounds). We also agree that a final definition combining Definitions 1.1 and 1.2 would be useful, we will add that immediately after these two definitions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "abno9fb0EE", "reviewer": "Reviewer_9BbN", "summary": "This works focuses on the task of density estimation of a mixture of Gaussians under the restriction of differential privacy. Unlike parameter estimation, density estimation does not require accurately estimating the mixture's parameters, but instead bounds the total variation distance between estimated and true distributions. This task can be achieved even without any boundedness or separation assumptions on the parameters of the components.\n\nThis task is known to require sample size of $O(k d^{2}/\\alpha^{2})$ even in the non-private setting, where $k$ is the number of components, $d$ is the dimension, $\\alpha$ is the bound on the TV distance, and the $O$ notation ignores logarithmic factors. In the private setting, previous work [1] achieved $\\alpha$ accuracy guarantee under $(\\epsilon, \\delta)$-DP with $O(k^{2} d^{4}/\\alpha^{2} \\epsilon)$ (the exact bound includes several other terms that depend on $\\log(1/\\delta)$ as well).\n\nThis work provides an improved bound, reducing the dependence on the parameters to $O \\left(\\frac{k d^{2}}{\\alpha^{2}} + \\frac{k d^{2}}{\\alpha \\epsilon} \\right)$ in the high dimensional regime, $O \\left(\\frac{k}{\\alpha^{2}} + \\frac{k \\cdot \\log(1/\\delta)}{\\alpha \\epsilon} \\right)$ in the univariate setting, and lower bounds which asymptotically match the upper bound in the univariate case and nearly match it in the multivariate one.\n\nThe proposed algorithm relays on first achieving crude estimation of the parameters and then using hypothesis selection to improve the estimation. The crude estimation is achieved using robust GMM estimation techniques and robusteness-to-privacy conversion, based on an inverse sensitivity-like instantiation of the exponential mechanism. This method is computationally inefficient.\n\n[1] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with a polynomial number of samples. In Algorithmic Learning Theory, pages 1–27. PMLR, 2024.", "questions": "As I mentioned before, I will find an additional section that brings all the components together to outline the final proof method, focusing on the final achieved bound, to be very useful.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results presented in this work provide a significant improvement over the previously known ones. Though the proof technique is highly involved, the authors presented the proof outline in a relatively intuitive way, and provided motivation for the various steps it includes.", "weaknesses": "Despite the great work done by the authors and my best efforts, I was not able to follow up all the proof structure. In particular, I could not find the justification for some of terms that appeared in the bound presented on Theorem 1.3. It seems to me like a section that \"puts everything together\" will be of great benefit. I will try to describe my current understanding and existing gaps.\n\nTo the best of my understanding:\n* The $\\frac{k d^{2}}{\\alpha^{2}}$ and $\\frac{k d^{2}}{\\alpha \\epsilon}$ were explained at the \"Reducing to “crude approximation”\" section, and they represent the sample size required to accurately and privately learn the GMM given some crude estimation of its components, using hypothesis selection method.\n* The $\\frac{d^{1.75} k^{1.5} \\sqrt{\\log(1/\\delta)}}{\\alpha \\epsilon}$ was explained at the \"Improving Dimension Dependence\" section, where $\\frac{d^{1.75} k}{\\alpha \\epsilon}$ results from the fact $O\\left(\\frac{d^{1.75} k}{c \\epsilon} \\right)$ points are required to get the crude estimation of the parameters of a single component under $c$-robustness, which then can be translated to a DP estimation with $\\alpha$ accuracy using rubousteness-to-privacy conversion techniques (Theorem 2.1), and the additional $\\sqrt{k \\cdot \\log(1/\\delta)}$ term results from advanced composition over $k$ components.\n* I failed to understand where the additional two terms ($\\frac{(k \\cdot \\log(1/\\delta))^{1.5}}{\\alpha \\epsilon}$ and $\\frac{k^{2} d}{\\alpha}$) come from, and I suspect they were accumulated at some point during the rubousteness-to-privacy transformation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed feedback. We are happy to add some description that puts everything together and explain where each of the terms come from, as suggested by the reviewer. In the following, we explain the terms in the sample complexity that the reviewer asked about.\n\nTo explain the $\\frac{(k \\log (1/\\delta))^{1.5}}{\\alpha \\epsilon}$ term, we note that in the crude estimation part, the sample complexity (from applying Theorem C.3, the formal version of Theorem 2.1) also has an assumption (see the “Volume” bullet) that $n \\ge \\frac{\\log (1/\\delta_0)}{\\epsilon_0 \\cdot \\eta^*}$. Here, $\\epsilon_0, \\delta_0$ represent the privacy terms for a single iteration of the crude estimation (to learn one parameter), and $\\eta^*$ will represent the robustness threshold, and ends up being roughly $\\alpha/k$. The reason the robustness threshold depends on $k$ like this is that each component on average has weight $1/k$, so you can corrupt $1/k$ fraction points and completely alter a component. Also, since we run the crude estimation $k$ times, we can use advanced composition to say that if each iteration was $(\\epsilon_0, \\delta_0) = (\\frac{\\epsilon}{\\sqrt{k \\log (1/\\delta)}}, \\frac{\\delta}{k})$-DP, the overall algorithm is $(\\epsilon, \\delta)$-DP. With all of these parameters set, we precisely get $ \\frac{\\log (1/\\delta_0)}{\\epsilon_0 \\cdot \\eta^*} = \\Theta\\left(\\frac{(k \\log (1/\\delta))^{1.5}}{\\alpha \\epsilon}\\right)$.\n\nTo explain the $\\frac{k^2 d}{\\alpha}$ term, the point is that for the private algorithm to work, we need two things. First, the private algorithm finds a covariance matrix (or more precisely, a mean-covariance pair $(\\tilde{\\mu}, \\tilde{\\Sigma})$) with low score (see Line 932 and the above few lines for the definition). Second, if a mean-covariance pair has a low score, then it is actually similar to a true mixture component $(\\mu_i, \\Sigma_i)$.  The previous terms of $\\frac{d^{1.75} k^{1.5} \\sqrt{\\log (1/\\delta)}}{\\alpha \\epsilon}$ and $\\frac{(k \\log (1/\\delta))^{1.5}}{\\alpha \\epsilon}$ are needed for the first part. However, the $\\frac{k^2 d}{\\alpha}$ term is needed for the second part: that any mean-covariance pair of low score is similar to some true mixture component (this is the goal of Proposition E.4 in our paper).\n\nThe reason for the $k^2$ dependence is nontrivial so here’s a high-level intuition. Given a dataset $X$ and mean-covariance pair $(\\tilde{\\mu}, \\tilde{\\Sigma})$, the score $S((\\tilde{\\mu}, \\tilde{\\Sigma}), X)$ is small if there exists roughly $\\alpha/k$ fraction of data points that “look like” they came from $\\mathcal{N}(\\tilde{\\mu}, \\tilde{\\Sigma})$. The point is that one can have one point come from each of $k$ different mixture components which, together, look like $k$ samples from a totally different Gaussian from any of the $k$ mixture components. As a result, we need to make sure we have more than $k^2/\\alpha$ total points, because then an $\\alpha/k$ fraction of the data points is more than $k$ total samples. We actually need an additional factor of $d$, because it turns out that we can even have $\\Omega(d)$ points from each of the mixture components which look like $\\Omega(kd)$ samples from a totally different Gaussian.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N3Y2kh3qjG", "reviewer": "Reviewer_sFBV", "summary": "This paper investigates the sample complexity of privately learning mixtures of Gaussians. The authors achieve a sample complexity of approximately $O(kd^2+k^{1.5}d^{1.75}+k^2d)\\log R$ where $R$ is an upper bound on the condition number of the covariance matrix and the norm of the mean. This result improves upon the previous best bound of $O(k^2d^4)$. Additionally, they constructed a lower bound of $\\Omega(kd^2+k\\log(1/\\delta)/\\epsilon)$, which refutes a conjecture from prior work, and they achieve optimal sample complexity when $d=1$.", "questions": "1. Where does the $k^2$ term come from in the upper bound?\n2. Are there alternative methods to address this problem that do not rely on the robustness-to-privacy conversion technique?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The improvement in sample complexity is significant.\nThe paper provides a thorough technical overview of the upper bound, detailing the incorporation of sample compression and the methods used to enhance dimension independence within the robustness-to-privacy conversion technique.", "weaknesses": "The paper is technically dense, making it challenging to understand and verify all the details.\nThe authors do not fully utilize the page limit, which could have been used to explain the techniques more clearly.\nThe technique for establishing the lower bound is not discussed in the main body of the paper.\nIncluding formal definitions and crucial lemmas in the main text could help readers better understand the key ideas. For instance, the definition of volume was unclear until I consulted the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed feedback. We would like to emphasize that our bound does not depend on the condition number of the covariance matrix nor on the magnitude of the mean, i.e., our sample complexity has no dependence on $\\log R$. (Otherwise, proving an upper bound would have been easy, e.g., by using private hypothesis selection on a finite cover for the set of possible mixtures.) We agree with the comments about the presentation of the paper, and will improve it in the next version (including adding more details about the definitions,lemmas, or proof sketches in the main paper). In the following we answer the raised questions.\n\n1. To explain the $\\frac{k^2 d}{\\alpha}$ term, the point is that for the private algorithm to work, we need two things. First, the private algorithm finds a covariance matrix (or more precisely, a mean-covariance pair $(\\tilde{\\mu}, \\tilde{\\Sigma})$) with low score (see Line 932 and the above few lines for the definition). Second, if a mean-covariance pair has a low score, then it is actually similar to a true mixture component $(\\mu_i, \\Sigma_i)$.  The term $\\frac{d^{1.75} k^{1.5} \\sqrt{\\log (1/\\delta)}}{\\alpha \\epsilon}$ is needed for the first part. However, the $\\frac{k^2 d}{\\alpha}$ term is needed for the second part: that any mean-covariance pair of low score is similar to some true mixture component (this is the goal of Proposition E.4 in our paper).\n\nThe reason for the $k^2$ dependence in this second term is nontrivial so here’s a high-level intuition. Given a dataset $X$ and mean-covariance pair $(\\tilde{\\mu}, \\tilde{\\Sigma})$, the score $S((\\tilde{\\mu}, \\tilde{\\Sigma}), X)$ is small if there exists roughly $\\alpha/k$ fraction of data points that “look like” they came from $\\mathcal{N}(\\tilde{\\mu}, \\tilde{\\Sigma})$. The point is that one can have one point come from each of $k$ different mixture components which, together, look like $k$ samples from a totally different Gaussian from any of the $k$ mixture components. As a result, we need to make sure we have more than $k^2/\\alpha$ total points, because then an $\\alpha/k$ fraction of the data points is more than $k$ total samples. We actually need an additional factor of $d$, because it turns out that we can even have $\\Omega(d)$ points from each of the mixture components which look like $\\Omega(kd)$ samples from a totally different Gaussian.\n\n2. The only other known approach for privately learning unbounded and high-dimensional GMMs (density estimation) is [AAL24] that uses sample-and-aggregate. For the univariate setting (density estimation for GMMs with unbounded parameters), there is another approach that uses stability-based histograms [AAL21].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xuMfpgJrba", "reviewer": "Reviewer_cTn5", "summary": "The paper studies the important problem of private learning of the Gaussian mixture model to estimate the underlying distribution within a desired total variation distance. By combining different techniques, the authors succeed in deriving bounds that are of quadratic dimension, thus significantly improving the existing results.", "questions": "1. It would be better to explain more the difference between density estimation and parameter estimation.\n\n2. How do the bounds of Theorems 1.3, 1.4., and 1.5 behave with respect to the failure probability $\\beta$ order-wise?\n\n3. Can the authors discuss the assumption $R=n^{100}$ (line 160) a bit more? Why does it depend on $n$ (and not $k$ or $d$?)? Also, is the polynomial dependence restrictive?\n\n4. The first sentence of the informal statement of Theorem 2.1. does not seem rigorous enough. Is such a $\\tilde{\\Sigma}$ unique? I don't think so. Then, if not, which choice of $\\tilde{\\Sigma}$ is taken into account when computing $V_{\\eta}(\\mathbf{X})$? Probably maximum volume?\n\n5. The appendix sections are very difficult to follow. There should be a detailed outline at the beginning to guide the reader as to what each appendix deals with. Also, there should be sufficient references in the main text. For example, after the informal statement of Theorem 2.1., it should be clearly stated where the full statement and proof can be found. Similarly, after each paragraph (e.g., Section 2.1) or after each mentioned previously established result (e.g., advanced composition theorem), there should be an exact pointer to where the complete version can be found in the appendices.\n\n6. Since the submission was allowed for 9 pages, the authors had 1.5 more pages. I think some material from the appendices, for example the algorithms used to privately learn GMM, could be moved to the main text.\n\n7. Finally, what is missing the most is the experimental section. If I'm not mistaken, this should be easy to do. Although not all theoretical work requires experimental verification, I believe that if the experiments verify the theoretical finding, this would greatly increase the importance of the results.\n\nMinor comments:\n\n- Line 52: it is better to add \"The parameters $\\alpha$ and $\\beta$...\".\n\n- The constant $c^*$ in Theorem 1.5. does not appear in the bound. \n\n- In the first paragraph of Section 2.1, it is mentioned that \"... as we can finish the procedure with hypothesis selection, as discussed above\". However, hypothesis selection has not been sufficiently discussed.\n\n- Is it true that the intuition given in Section 2.1. holds if $ n \\gg k^2$?\n\n- Typo line 178 (a a)\n\n- Is $k$ in lines 203-204 the number of components in the Gaussian mixture? Why does this statement (\"if we altered $k$ data points...\") only hold for $k$ changes?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper contains several new results that significantly improve the state of the art. These include i) Theorem 1.3, which establishes a bound with quadratic complexity for any dimension, ii) Theorem 1.4, which proposes an improved bound for $d=1$, showing that the sample complexity can be linear in the number of components, iii) Theorem 1.5, which proposes a lower bound on the sample complexity. The latter, combined with Theorem 1.4, shows the optimality of the established bounds for the univariate Gaussian distributions.  In addition, the paper is generally well and smoothly written.", "weaknesses": "- The paper could benefit from some numerical verifications of the results/algorithms used.\n\n- The appendix section is poorly organized. Without an outline and proof, it is difficult to follow such a long appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed feedback. In the following we answer the raised questions.\n\n1. To clarify this further, the goal of density estimation is to learn the overall distribution’s PDF (up to low total variation distance), whereas in parameter estimation we want to learn every Gaussian component’s mean and covariance. One can construct two different Gaussian mixtures with very similar PDFs, but with somewhat different components (in which case identifying the wrong Gaussian mixture is OK for density estimation but not for parameter estimation). We will add this discussion to the paper.\n\n2. For the sake of clarity of the presentation we tried to avoid writing down the exact dependency on beta in our bounds. However, note that the sample complexity scales at most logarithmically with 1/beta. The reason is that any method that achieves a failure probability of < 0.50 can be boosted to have failure probability of beta with a mild (logarithmically in 1/beta) increase in the sample complexity. This can be done by running the estimator on log(1/beta) data sets, and then simply running private hypothesis selection on the outcomes. We will add this discussion to the paper.\n\n3. The choice of $n^{100}$ is just for convenience, and the effect of the constant 100 on the sample complexity is negligible (i.e., the sample complexity does not change in terms of the $\\tilde{O}(.)$ notation). In Line 157, we mention that the sample complexity (after the crude approximation is obtained) depends on $\\log R$, so even if $R = n^{100}$ this only blows up the sample complexity by $\\log(n^{100}) = O(\\log n)$.\n\n4. Indeed, the $\\tilde{\\Sigma}$ is not unique, and the volume in Theorem 2.1 refers to the volume (i.e., Lebesgue measure) of the set of all possible $\\tilde{\\Sigma}$, for a fixed choice of dataset $X$. As an example, if $d = 1$ (in which case $\\tilde{\\Sigma}$ is just a variance) and every $\\tilde{\\Sigma}$ between $1$ and $4$ satisfies the score function, then the volume is 3. In general, we use higher dimensional Lebesgue measure (see Appendix C.1) to formally define the volume.\n\n5 and 6. We thank the reviewer for their suggestions about improving the presentation of the paper and the appendices. We will use the remaining space to give more details in the main paper (and will also improve the structure of the appendix to make it easier to navigate)\n\n7. We would like to emphasize that our work focuses on the fundamental problem of determining the number of samples for learning a GMM privately. However, our algorithm is not computationally efficient. Note that even without privacy, it is not known whether GMMs can be learned efficiently in high dimensions. This remains an intriguing open problem in the field of computational statistics. \n\nMinor comments:\n\nRegarding Theorem 1.5, we note that $c^*$ will be some universal constant, so it can be hidden in the $\\Omega$ notation. The intuition in Section 2.1 holds as long as $n \\gg k$, so it also holds if $n \\gg k^2$. In lines 203-204, the use of $k$ is a mistake - we will use $t$ (or another variable) to avoid confusing it with the number of components $k$. For all other comments, we agree with you and we will incorporate your feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all of the reviewers for their helpful feedback.

We apologize for the difficulty in reading the paper. We will make changes as suggested by the reviewers to improve the readability of the paper, such as adding a table of results, adding some additional technical description to the main body (up to space limitations), and adding some outline and summary sections in the appendix so that it will be more structured and understandable.

Meta-review: The paper considers the problem of estimating k-component and d-dimensional Gaussian mixtures with central differential privacy. Previous algorithms required k^2 d^4 samples and the proposed work shows that kd^2 + k^1.5 d^1.75 + k^2 d samples suffice. In the high-dimensional setting, when d >>k^2, they further show that this bound is optimal. They also show that sample complexity of learning one dimensional Gaussian mixtures is linear in k. The results are interesting and I recommend acceptance.

As reviewers mention, the writing is dense and based on my own read of the paper, I completely agree.  I strongly urge authors to utilize the full page limit and improve the writing in the final version of the paper by addressing reviewer concerns.  It would also be great if authors can add  additional intuition on how each of the terms in the sample complexity arise and also highlight the technical novelty that enabled this result.
Decision: Accept (spotlight)