Privately Learning Mixtures of Axis-Aligned Gaussians
Authors: Ishaq Aden-Ali
Hassan Ashtiani
Christopher Liaw
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
distribution learning
mixtures of Gaussians

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



Privately Learning Mixtures of Axis-Aligned Gaussians
Ishaq Aden-Ali
Hassan Ashtiani
Department of Computing and Software
Department of Computing and Software
McMaster University
McMaster University zokaei am@ncmasterr
adenal @mcmaster.c.mm
Christopher Liaw
Department of Computer Science
University of Toronto cvliawecs. toronto edu
Abstract
We consider the problem of learning mixtures Gaussians under the constraint of approximate differential privacy. We prove that Ö ( (a)))/a?e) samples are sufficient to learn a mixture of l axis-aligned Gaussians in TRd to within total variation distance while satisfying (s, 8 ji-fifferential privacy. This is the first re- sult for privately learning mixtures of unbounded axis-aligned (or even unbounded univariate) Gaussians. If the covariance matrices of each of the Gaussians is the identity matrix, show that Ö(kd/a² kd log(1/5)/aa) samples are sufficient. To prove our results, design new technique for privately learning mixture distributions. A class of distributions FF is said to be list-decodable if there is algorithm that, given "heavily corrupted" samples from F, outputs list of distributions one of which approximates f. We show that if F. is privately list-decodable then we can learn mixtures of distributions in F. Finally, show axis-aligned Gaussian distributions are privately distddcodable, thereby proving mixtures of such distributions are privately learnable.
1 Introduction
The fundamental problem of distribution learning concerns the design algorithms (i.c., estimators) that, given samples generated from unknown distribution f. output an "approximation" of While distribution learning has long history (54), studying it under privacy constraints relatively new and unexplored.
In this paper, we work with a rigorous and practical notion of data privacy known as differential privacy [36]. Roughly speaking, differential privacy guarantees that no single data point can influence the output of an algorithm too much. Intuitively, this provides privacy by "hiding" the contribution of each individual. Differential privacy is the de facto standard for modern private analysis and has seen 39
widespread impact both industry and government
In recent years, there has been a flurry of activity in differentially private distribution learning and number techniques have been developed in the literature. In the pure differentially private setting, Bun et al. [17] introduced method to learn classes of distributions that admit a finite cover, i.c. when the class of distributions is well-approximmted by finite number of distributions. They show that this is an exact characterization of distributions which can be learned under pure differential privacy in the sense that class of distributions is learnable under pure differential privacy if and only the class
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

admits finite cover [7 As a consequence of this result, they obtained pure differentially private algorithms for learning Gaussian distributions provided that the mean of the Gaussians are bounded and the covariance matrix of the Gaussians are spectrally bounded Moreover, such restrictions on the Gaussians are necessary under the constraint of pure differential privacy.
One way to remove the requirement of having a finite cover is to relax to a weaker notion of privacy known as approximate differential privacy. With this notion, Bun al. [17] introduced a method to learn a class of distributions that, instead of requiring a finite cover, requires "locally small" cover, i.e a cover where each distribution in the class is well-approximated by only a small number of elements within the cover. They prove that the class of Gaussians with arbitrary mean and a fixed, known covariance matrix has locally small cover which implies an approximate differentially private algorithm to learn this class of distributions. Later, Aden-Ali, Ashtiani, and Kamath [4] proved that the class of mean-zero Gaussians (with no assumptions on the covariance matrix) admits a locally small cover leading to approximate differentially private method to learn the class of all Gaussians.
It is a straightforward observation that if a class of distributions admits finite cover then the class of its mixtures also admits a finite cover. Combined with the aforementioned work of Bun et al., this implies pure differentially private algorithm for learning mixtures of Gaussians with bounded mean and spectrally bounded covariance matrices. It is natural to wonder whether an analogous statement holds for locally small covers. In other words, if a class of distributions admits a locally small cover then does the class of mixtures also admit a locally small cover? If so, this would provide fruitful direction design differentially private algorithms for learning mixtures of arbitrary Gaussians. Unfortunately, there are simple examples of classes of distributions that admit locally small cover yet their mixture do not. This leaves open the question of designing private algorithms for many classes of distributions that are learnable in the non-private setting. One concrete open problem is for the class of mixtures of two arbitrary univariate Gaussian distributions. A more general problem is private learning of mixtures of l axis-aligned (or general) Gaussian distributions.
1.1 Main Results
We demonstrate that it is indeed possible to privately learn mixtures of unbounded univariate Gaus- sians. More generally, we give sample complexity upper bounds for learning mixtures of unbounded d-dimensional axis-aligned Gaussians. the following theorem and the rest of the paper we use Ö to hide polylogarithmic factors, i.e. ((f))) means (ff(z) log" f(x) for some c > 0.
Theorem 1.1 (Informal). The sample complexity of learning a mixture of k d-dimensional axis- aligned Gaussians a-accuracy in total variation distance under (E.f)-differential privacy is δ k (1/6))
The formal statement of this theorem can be found in Theorem 5.1 For technical reasons, we do require that ó E (0. 1/n) for the above theorem to hold. This condition is quite standard in the differential privacy literature. Indeed, for useful privacy, 5 should be "cryptographically small", i.e. 5 1/n.
Even for the univariate case, our result is the first sample complexity upper bound for learning mixture of Gaussians under differential privacy for which the variances are unknown and the parameters of
the Gaussians may be unbounded. In the non-private setting, it is known that θ (kd//o /a2) samples necessary and sufficient to learn a mixture of & axis-aligned Gaussian in Rd 66 61l. In the private setting, the best known sample complexity lower bound is Mdd/ce ar log(d)) under (s, 6)-P when 6 < ((Vd/n) [6]. Obtaining improved upper or lower bounds in this setting remains an open question.
the covariance matrix of each component of the mixture is the same and known or, without loss of generality, equal to the identity matrix, then we can improve the dependence the parameters and obtain a result that is in line with the non-private setting.
When we say that matrix V is spectrally bounded, we mean that there are 0 < a1 S 02 such that 01 1 3 Y I.
2

---

Theorem 1.2 (Informal), The sample complexity of learning a mixture of is d-dimensional Gaussians with identity covariance matrix to a-accuracy in total variation distance under (e, 6)-d6f)frenttic privacy is O kd Iddlgg 1/8) ac
We relegate the formal statement and the proof of this theorem to the supplementary materials (see Appendix F). Note that the work of [53] implies an upper bound of O log² (1/0)/a²c" for private learning of the same class albeit in the incomparable setting of parameter estimation.
Comparison with locally small covers. While the results in 4 [7] for learning Gaussian distribu- tions under approximate differential privacy do not yield finite-time algorithms, they do give strong tnfooottion-thhoretiic upper bounds. This is achieved by showing that certain classes of Gaussians admit locally small covers. It is thus natural ask if we can obtain sharper results by showing that mixtures of Gaussians also admit locally small covers. Unfortunately, the following simple example shows that not even mixtures of two univariate Gaussians admit locally small covers.
Proposition 1.3 (Informal version of Proposition Every cover for the class of mixtures of two univariate Gaussians is not locally small.
1.2 Techniques
To prove our result, we devise a novel technique which reduces the problem of privately learning mixture distributions the problem of private list-decodable learning of distributions. The framework of list-decodable learning was introduced by Balcan, Blum, and Vempala [] and Balcan, Röglin, and Teng ( in the context of clustering but has since been studied extensively in the literature in a number of different contexts 77] 20 21 26 27 49 55 56]. The problem of list-decodable learning of distributions is as follows. There a distribution f of interest that we are aiming to learn. However, we do not receive samples from fi rather we receive samples from a corrupted distribution g = (1- f) + yh where 7 E (0, 1) and is some arbitrary distribution. In our application, y is close to 1, i.e. most of the samples are corrupted. The goal in list-decodable learning is to output a short list of distributions f1. fi..... ... fI with the requirement that f is close to at least one of the ft's. The formal definition of dist-decodable learning can be found in Definition 2.6] Informally, the reduction can be summarized by the following theorem which is formalized in Section 3
Theorem 1.4 (Informal). If a class of distributions F is privately list-decod then mixtures of distributions from F are privately learnable.
Roughly speaking, the reduction from learning mixtures of distribution to list-decodable learning works as follows. Suppose that there is an unknown distribution / which is mixture of & distributions ft,..., A list-decodable learner would then receive samples from f as input and output a short list of distributions f so that for every fi there is some element in f that is close to fi. In particular, some mixture of distributions from FF must be close to the true distribution f. Since f is small finite set, the set of possible mixtures must also be relatively small. This last observation allows us to make use of private hypothesis selection which selects good hypothesis from small set of candidate hypotheses [4] [7]. In Section 3, we describe the aforementioned reduction in more detail. We note that a similar connection between list-decodable learning and learning mixture distributions was also used by Diakonikolas et al. [26]. However, our reduction is focused on the private setting.
The reduction shows that to privately learn mixtures, it is sufficient to design differentially private dist-decodable learning algorithms that work for (corrupted versions of) the individual mixture compo- nents. To devise list-decodable learners for (corrupted) univariate Gaussian, we utilize "stability-based" histograms [1 [1] that satisfy approximate differential privacy.
To design a dictddeco learner for corrupted univariate Gaussians, we follow a three-step approach that is inspired by the seminal work of Karwa and Vadhan [50]. First, we use histogram to output a list of variances one of which approximates the true variance of the Gaussian. As a second step, we would like to output list of means which approximate the true mean of the Gaussian. This can be done using histograms provided that we roughly know the variance of the Gaussian. Since we have candidate variances from the first step, we can use sequence of histograms where the width of the bins of each of the histograms is determined by the candidate variances from the first step. As last step, using the candidate variances and means from the first two steps, we are able to construct a small set of distributions one of which approximates the true Gaussian to within accuracy In the
3

---

axis-alignn aligned Gaussians setting, we use our solution for the univariate case as a subroutine on each dimension separately. Now that we have list-decodable learner for axis-aligned Gaussians, we use our reduction to obtain private learning algorithm for learning mixtures of axis-aligned Gaussians.
Approaches based constructing lists of candidate variances and means in order to learn accurate mixture have been previously considered in the non-private setting [5] 6 23 61]. However, it does seem possible directly privatize the algorithms in this line of work since they construct these candidates directly from the samples, which is clear violation of privacy.
1.3
Open Problems
The most basic open problem is understand the exact sample complexity (up constants) for learning mixtures of univariate Gaussians under approximate differential privacy.
Conjecture 1.5 (Informal). The sample complexity of learning a mixture of k univariate Gaussians to within tota variation distance a with high probability under (e, 6)-DP O
+++++
log(1/5)
Another open question whether is possible privately learn mixtures of (arbitrary) high- dimensional Gaussians. We conjecture that it is possible and with the following sample complexity.
Conjecture 1.6 (Informal), The sample complexity of learning a mixture of k d-dimensional Gaussians to within totl variation distance a with high probability under (e, ()DD is kifa kdf [og(1/8)
ac
1.4 Additional Related Work
Recently, 17 showed how to learn spherical Gaussian mixtures where each Gaussian component
has bounded mean under pure differential privacy. Acharya, Sun and Zhang [3 were able obtain lower bounds in the same setting that nearly match the upper bounds of Bun et al. [17). Both [47] 53 consider differentially private learning of Gaussian mixtures, however their focus is on parameter estimation and therefore require additional assumptions such as separation or boundedness of the components.
There has been a flurry of activity on differentially private distribution learning and parameter estimation in recent years for many problem settings [1 [4] 16 25
30
38
46
48
50
52
53
59 60). There has also been a lot of work in the locally private setting
33
Other work differentially private estimation include I TO
13
19
58
65
For more
comprehensive review of differentially private statistics, see 45
2
Preliminaries
For any m E N, (m] denotes the set {1, 2, .., m... Let X denote a random variable sampled from the distribution f. Let (X*) ym fm denote an i.i.d. random sample of size m from distribution f. For vector E Rd, we refer to the ith element of vector as I;. For any is E N, we define the k-dimensional probability simplex to be A {(W1,.... ....,.... wx) R& Ei= w 1}. For vector μ E Rd and a positive semidefinite matrix E, we use ((,, Σ) to denote the multivariate normal distribution with mean and covariance matrix Σ. We define G to be the class of univariate Gaussians and Gd = [N (j. E) Σij = vi + and En > 0 Vi} to be the class of axis-aligned Gaussians.
Definition 2.1 (F) Let F be class of probability distributions. Then the class of k-mixtures of F, written (-mix(F), defined as
k-mix(F) = E wifs (w,,..., wk) AE. fa F
2.1 Distribution Learning
distribution learning method is (potentially randomized) algorithm that, given a sequence of i.i.d. samples from a distribution f. outputs distribution / as an estimate of f. The focus of this paper on absolutely continuous probability distributions (distributions that have density with respect to

---

the Lebesgue measure), so we refer to a probability distribution and its probability density function interchangeably. The specific measure of "closeness" between distributions that we use the total variation (TV) distance.
Definition 2.2. Let g and f be two probability distributions defined over X and ler be the Borel a-algebra on X. The total variation distance between y and f is defined as
1
1 All E 1].
drv (g, f) sup PP(()) ( 2 *E
[g(x)) - [())dd = -
SEN
where P. Py(S) denotes the probability measure that 9 assigns to S. Moreover, if F is a set of distributions over a common domain, we define drv F) = inf drv
Definition 2.3 (PAC learner). We say algorithm A is PAC-leamer for class of distributions F which uses m(a, 33 samples, if for every v. E (0, 1), every f E F, and every n. 2 mm(, 3) the following holds: if the algorithm is given parameters a, 3 and sequence of i.idd samples from as inputs, then it outputs an approximation ff such that dyv(f.F S a with probability at least 1
We work with additive corruption model often studied in the dist-decod setting that is inspired by the seminal work of Huber [42]. In this model, a sample is drawn from a distribution of interest with some probability, and with the remaining probability is drawn from arbitrary distribution. Our list-decodable learners take samples from these "corrupted" distributions as input.
Definition 2.4 (y-corrupted distributions). Fix some distribution I and let (0,1). We define --corrppeed distribution of J as any distribution such that g = -1- -) + +~ for an arbilrary distribution h. We define (J) ) to be the set of all 7-corrupted distributions of f
Remark 2.5. Observe that (f) is monotone increasing in 7, Lee. H,,l) C (f) for all
n E (7, 1). To see this, note that if g = (1-7) +7h then we can also rewrite g = (1 (0-7)) (-)-//+++/1
where M = 4 -2 f + 2, Hence, g E (f)
In this work, 7 is usually quite close to 1, i.c. the vast majority of the samples are corrupted. Next, we define list-decodable learning. In this setting, the goal is to learn a distribution f given samples from a y-corrupted distribution g of f. As y Rs 1, the goal is to output a list of distributions, one of which approximates f. We use this primitive to design algorithms for learning mixture distributions.
Definition 2.6 (lit-decodable learner). We say algorithm ALIST is an L-list-decodable learner for a class of distributions FF using MLSTT( 3, samples for every a, B, 7 E (0, 1). n Z mLsa(a, B, 7), f F. and g E (f).). the following holds: given parameters a, 3,3,7 and a sequence of n i.i.d. samples from 9 as imputs, ALST outputs set of distributions FF with |F < L. such that with probability no less than 3 we have drv S a.
2.2 Differential Privacy
Let X* = X = D. E X are neighbours if D and D' differ in most one data point. Informally, an algorithm is differentially private if its output on neighbouring databases are similar. Formally, differential privacy ( has the following definition.
be the set of all datasets of arbitrary size over a domain set X. Two datasets
Definition 2.7 (B5 36). A randomized algorithm T X* + is (c, 5) differrrentill private for all > L. for all neighbouring datasets D, D' E X", and for all measurable subsets S C ) (T([(D) E S S et Pr(T(D') E $ 6.
If 8 0, we say that T is e-differentially private.
We refer to e-DP as pure DP, and (e, 8DDP for 8 > 0 as approximate DP. We make use of the following property of differentially private algorithms which asserts that adaptively composing differentially private algorithms remains differentially private. By adaptive composition, we mean that we run a sequence of algorithms M₁ (D).... M....,,,(.. where the choice of algorithm M, may depend on the outputs of M, (D).... (D).
"The probability is over m(a, 3) samples drawn from f and the randomness the algorithm. 'e will use the acronym DP to refer to both the terms "differential privacy" and "differentially private". Which term using will be clear from the specific sentence.
5

---

Lemma 2.8 (Composition of DP (6,371 37 If M is an adaptive composition of differentially private algorithms M.....,AM Mr then the following two statements hold:
M/....., Mr are (E1, 61), ...,.................. (er, 8T )DD, then M is (e, 6)-D for
= Σi= Et and i = ==E== 52-
2. If Mi....,, Mr are (Ea, 61), (Eo, 5r) DDP for some Eo S 1, then for any dg > 0, M is (c, 6)-
DP for
E = E 6T (og(6/))) and 8 - E
The first statement in Lemma 2.8 is often referred to as basic composition and the second statement often referred to advanced composition. We also make of the fact that post-pon processnessing the output of a differentially private algorithm does not impact privacy.
Lemma 2.9 (Post Processing)- If M X + 3/ is (s, (5,8)-diffe 8)-iifferentially private, and P y + Z is any randomized function, then the algorithm P M (e, difffeeirry private.
We define (e, -DP PAC learners and (s, 0)-P L-list-decodable learners as PAC learners and L-list-decodable learners that satisfy (e, 8DD..
List-decodability and Learning Mixtures
In this section, we describe our general technique which reduces the problem of private learning of mixture distributions to private list-decodable learning of distributions. We show that if we have differentially private list-decodable learner for class of distributions then this can be transformed, in a black-box way, to a differentially private PAC learner for the class of mixtures of such distributions. In the next section, we describe private list-decodable learners for the class of Gaussians and thereby obtain private algorithms for learning mixtures of Gaussians.
First, let us begin with some intuition in the non-private setting. Suppose that we have a distribution g which can be written g = Em= f.f. Then we can view g &=d -corrupte distribution of fa for each E [k]. Any list-decodable algorithm that receives samples from as input is very likely to output a candidate set F.. which contains distributions that are close to J' for each i E [k]. Hence, if we let IC {Σiejh) f. f. F}. then g must be close to some distribution in X.. The only remaining task is to find distribution in IC that is close to g; this final task is known hypothesis selection and has a known solution [24]. We note that the above argument can be easily generalized to the setting where is non-uniform mixture, i.e. Σ
w;f: where (w1,..., w)) A..
The above establishes blueprint that distributions. In particular, we aim to come up with a private list-decoding algorithm which receives samples from f to produce set F. Thereafter, we can construct a candidate set IC as mixtures of distributions from F. Note that this step does not access the samples and therefore maintains privacy. In order to choose good candidate from K. we make use of private hypothesis selection
follow in order to obtain private learner for mixture
Formally, the following theorem establishes the reduction from private list-decodable learning to learning of mixtures. The proof can be found in Appendix of the supplementary materials.
Theorem 3.1. Let N and e, E (0,1), 1). If is (s/2, 6)-DP L-list-decodable with must samples then there is an (E, 5DDP PAC learner for k-mix(F) where the number of samples used is m(a, B,e,
3 18' 2k'
E 2'
(llog(Lk/a) + log(1/8) llog(Lk/a) 1og(1/
MILST
+0
18K
This reduction is quite useful because it conceptually much simpler devise list-decodable learners for given class F. In what follows, we will devise such list-decodable learners for certain classes and use Theorem 3.1 obtain private PAC learners for mixtures of these classes.
4 Learning Univariate Gaussian Mixtures
Let & be the class of all univariate Gaussians. this section we consider the problem of privately learning univariate Guassian Mixtures, k-mix(g). In the previous section, we showed that it is

---

sufficient to design private listddecodable learners for univariate Gaussians. As a warm-up and to build intuition about our techniques, we begin with the simpler problem of constructing private list-decodable learners for Gaussians with a single known variance a². In what follows, we often use "tilde" (e.g. M, V) denote sets that are meant to be coarse, constant, approximations and "hat" (e.g. F, M, V) denote sets that are meant to be fine, say O approximations.
4.1 Warm-up: Learning Gaussian Mixtures with a Known, Shared Variance
In this sub-section we construct a private list-decodable learner for univariate Gaussians with known variance o². A useful algorithmic primitive that we will use throughout this section and the next is the stable histogram algorithm.
Lemma 4.1 (Histogram learner 15 51). Let n E N. n,3,E E (0, 1) and 5 (0. 10.1/n). Let D be a dataset of n points over a domain X. Let K be a countable index set and B = (Br
be collection of disjoint bins defined on X, i.e. B; C X and B, B, 0 for + j. Finally,
let Pt = -. [Dr n Ba). There is an (e, (yPP algorithm Stable hibolll-isttgramms. 6, 8, 8, D, B) that takes as input parameters e, 6, B, dataset D and bins B, and outputs estimates (P; ) jeK such that
J.. - p.l S for all E K with probability no less than 1 - 3 so long as n = ? log 1/88)
For any fixed 0² we define Go be the of all univariate Gaussians with variance o², For the remainder of this section, we let g = _N(,, )) E Go and g' E HH, (g). (Recall that g' E H, (g) means that g' (1 ?)g + y/ for some distribution h.) Algorithm I shows how we privately output a list of real numbers, one of which is close to the mean of g given samples from g'. The following lemma shows that the output of Algorithm i a list of real numbers with the guarantee that least one element in the list is close to the true mean of a Gaussian which has been corrupted. Note that the lemma assumes the slightly weaker condition where the algorithm receives an approximation to the standard deviation instead of the true standard deviation. This additional generality is used in the next section.
Lemma 4.2. Algorithm is an (e, 8)-DP algorithm such that for any ((u.02) and g' E (H)())
when given parameters E, C,B,7 E (0, E (0, 1/n), E (a. 20) and dataset D of n i.idd.
samples from g' as input, it outputs set M of real numbers of size |M S r Furthermore, with probability -
B there is an element jú E M such that Ti nl S a, so long as n Ω (1o (og(11/0))
(1-7)E
Algorithm
Input :Parameters e, 3,, E (0,1), 6 E (0,1/n), ō and dataset
Output Set of approximate means M.
Partition IR into bins B {Bi where B, ((i 0.5)ō, (I + 0.5)ō].
2 (ichen + Stable- Hiaile--isttoramm(: 6, (1
3 И + {i : p. > (1 /))
If [ > 12/(1 -7) fail and return M 0
M (1ō i H}
Return M.
We begin by gathering several simple claims whose proofs can be found in Appendix D.1 P Px-g' [X B.] be the probability that sample drawn from g' lands in bin B, Let P. 1 DDnul B be the actual number of samples drawn from g' that have landed in B,. Let j = [p/ō]. It is simple calculation to check that ljö yol S a. Thus, would like to show that jö E M or, equivalently,
Let pt
that j E H. A straightforward calculation shows that Pj 2 (1 11-)) 7//33 Then standard application of Chernoff bound shows that many samples actually land in bin Bj, as asserted by the following claim.
7)) then D. > (1 - 7)/6 with probability at least 3/2.. Claim 4.3. nn 2llll((l00/////// 7))
Next, we claim that the output of the stable histogram approximately preserves the weight of all the bins and, morcover, that the output does not have too many heavy bins. The first assertion implics
7

---

that since bin Bj is heavy, the stable histogram also determines that bin Bj is heavy, The second assertion implies that the algorithm does not fail. Let (Piben be the output of the stable histogram, as defined in Algorithm[]
Claim 4.4. Ifn = (000g(115000000/00 ()))) then with probability - -3/2, we have (i) lo;
Pel S
- 7)/44 24/22//// for all i E N and (i) [H] -i EN: P. (1 -7/88/ - 12/(1 (1
With Claim 4.3 and Claim 4.4 in hand, we are now ready to prove Lemma 4.2
Proof of Lemma 4.2 We briefly prove that the algorithm is private before proceeding to the other
assertions of the lemma.
Privacy. Line 2 is the only part of the algorithm that looks at the data and (c, 5)- by
Lemma 4. The remainder of the algorithm can be viewed as post-processing (Lemma 2.9) so it
does not affect the privacy.
Bound on M For the bound on M), observe that if | 12/(1-1)) then the algorithm fails
so JM| - 12/(1 - 7) deterministically.
Utility. Let g' be defined in the statement of the lemma. We now show that there exists j M such that j pl Let j [u/ō]. For the remainder of the proof, we assume that 7)=).
n
Claim 4.3 asserts that, with probability 1 - 3/2, we have Pj > (1 (1-7)/6. Claim 4.4 asserts that, with probability 1 - 3/2, P; 2 Pj - - 22//44 and that [H] < 12/(1-1 >)). By union bound, with probability 1 - B, we have that D, > (1- (1-7))88 and the algorithm does not fail. This implies that j E H so jō e M. Finally, note that ljō nl I //2 S a where the last incquality uses the assumption that ō < 20.
We can now use Lemma 4.2 to get private list-decodable learner (Corollary 4.5) and then use this private list decodable learner together with our reduction (Theorem 3.1 to get (e. 8PAC learner for k-mix(9 (9) Thheorem(46) The proof of Corollary 4.5 can be found in Appendix Corollary 4.5. For any
10, and 8 (0, 1/n), there is (D L-list-decodable learner for Go with known a > O where L = 0 (1-1aa) and the number of samples used is
mLisT (a, B, 8) O [og(1/88) (1-7)6
Theorem 4.6. For any E (0.1) and 5 E (0,1/n), there is an (s, 6)-DP PAC learner for k-mix(go) with known o > 0 that uses m(a, 8, = (+log(1/8)
klog(1/88)
samples.
4.2 Learning Arbitrary Univariate Gaussian Mixtures
In this subsection, we construct a list-decodable learner for G, the class of all univariate Gaussians. First, in Lemma 4.7 we design an (e, 8D algorithm that receives samples from g' E (g) where g E G and outputs list of candidate values for the standard deviation, one of which approximates the standard deviation of with high probability. Then, in Lemma 4.8 we use Lemma and Lemma 4.7 to design an (c, 5DP list-decoder for G.
4.2.1 Estimating the variance
We begin with a method to estimate the variance. Here, we provide a high-level overview and relegate the details to the appendix. Suppose that g (N, o²) and g' E H. (g). Our goal is to obtain multiplicative estimate of o². The key observation is as follows. If X1, X, g then for some distribution h. In particular, with probability roughly - 71 |Y| itself good estimate of This observation allows us to proceed similarly to the proof of Lemma 4.2 with two changes. First, since our goal is a multiplicative approximation to o², we use bins of the form (2', 2221++1 for E N. Second, given dataset D {X,...., X2m), }, we transform X 22m //22/ and use the previously mentioned observation. The following lemma formalizes the guarantee that we can achieve. The proof can be found in Appendix D.2
Y = (x,,, X2)/ /222/22 is distributed as (1 20_
+ (1-(1111))) ?)
the dataset D' f|X, X2l/v2.... 1X2m-11
8

---

Lemma 4.7. There is an (e, ()PP) algorithm such for any NN,, and g' E Hg when is given parameters E,B. (0. 1). ò E (0.1/n) and dataset of 2n i..dd samples from g' as
12 imput, outputs a set V of positive real numbers of size [V] S (1-7)2- Furthermore, with probability
no less than 33 there an element ō E V such that o S ē 20, so long as n 52
[og(1/86)
(1-2)-8 )
4.2.2 A list-decodable learner for univariate Gaussians
We can now use Lemma and Lemma 4.7 to design a list-decodable learner for G. This is done in few steps. First, we obtain a list of candidate variances using Lemma 4.7 We know that one of these candidates is good approximation to the true variance although we may not know which one, As a second step, we use the algorithm implied by Lemma 4.2 for all the candidate variances to get list of candidate means. Since one of the candidate variances is good estimate of the true variance, Lemma 4.2 promises that one of the candidate means is good estimate of the true mean. Given list of candidate variances and candidate means, we can create list of all pairs of variances and means to obtain a list of distributions such that one is close to the true Gaussian. The guarantee is formalized in the following lemma and the proof appears in Appendix D.3
Lemma 4.8. There is an D.P algorithm such for any = NN,, o²) and g' E H.gg), when it is given parameters E, E,a, 3 (0, å E (0, 1/n) and dataset D of n. i..dd samples from g' as inputs, it outputs set M of real numbers and set V of positive real numbers such that
144 (2-[1/a) + and 1V15
12 10811a (2)
M
(1 7)3
(1 7)
Furthermore, with probability no less than B. we have the following:
1. 3p E M such that I/ μ4| S ao
2. 3ō E V such that jā o S a0
so long as n 57
log2/2(1/80)) 11-7)=
We can now use Lemma 4.8 to get the following result. We defer the proof to Appendix D.4 Corollary 4.9. For any
(0, 1) and 8 (0.1/n) there an (E.8)-DP L-list-decodable
learner for where L. = 0 (1=))=²)) and the number of samples used by the algorithm is (Lssr(a, B, 7, Ō log (1138))
(1
Finally, Corollary 4.9 and Theorem 3.1 immediately imply the following theorem. Theorem 4.10. For any (0. 1) and 5 (0, there is an ()-8)-DP PAC learner for k--mi that uses m(a, (,) Ö (12 2/ a²E
samples.
Learning Mixtures of A Exis-Aligned Gaussians
In this section, we prove the following result, which is formal version of Theorem Theorem 5.1. For any e E 10 and (0,1/v) there is an (c, 5)P PAC learner for k-mix (gd) and the number of samples used by the algorithm is m(a, 3,,, e, 8) Ō 2// arg
The following lemma shows that we can construct an () list-decodable learner for the class of d-dimensional axis-aligned Gaussians, gdt. We explain the high-level details of our approach here. Let g I 9i E gd and g' E (g) For a sample that X; ~ of where of E (g.). We can thus split our dataset by dimension and run our univariate private destddec learner (Corollary 4.9) on each dimension separately to get total of lists of univariate Gaussians. From the guarantee of Corollary 4.9 in the ith list there will be at least one Gaussian that a good approximation to gi, and this holds for all i E [d]. Finally, since g is an axis-aligned Gaussian (product distribution), we can take all possible combinations of the univariate distributions in the d lists to obtain a new list of axis-aligned Gaussians, one of which accurately approximates g. The details of the proof can be found in Appendix E
(X Xa) ~ g', it follows

---

Lemma 5.2. For any E (0,1) and ò E (0, (0.1/n), there is an (E, L-list-decodable learner for 9 where I, (1->)
and the number of samples used by the algorithm is de
(, =0
- (11/86) (1-
We can now put together Lemma 5.2 and Theorem 3.1 to immediately get Theorem 5.1
Acknowledgments and Disclosure of Funding
CL was supported by an NSERC postdoctoral fellowship. HA was supported by an NSERC Discovery Grant.
References
[1] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In Advances in Neural Information Processing Systems 31, NeurIPS 18, pages 6878-6891. Curran Associates, Inc., 2018.
[2] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS '19, pages 1 1120-1129 JMLR,
Inc., 2019.
[3] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam arXiv preprint arXiv:2004.0688. 2020.
[4] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high- nigh-dimensional gaussians. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 185-216. PMLR, 16-19 Mar 2021. URL WRRLhtttp//prrceeeeiii
mlr www.ppress/vv211 aden- aliiia. htmm
[5] Hassan Ashtiani, Shai Ben-David, and Abbas Mehrabian. Sample-efficient learning of mixtures. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI' 18, pages 2679-2686. AAAI Publications, 2018. URL httt::://aaxii.org/aaaaa
[6] Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6):32:1332:443 2020.
[7] Ainesh Bakshi and Pravesh K. Kothari. List-decodable subspace recovery: Dimension inde- pendent error in polynomial time. In Proceedings of the Thioty-Second Anmual ACM-SIAM Symposium Discrete Algorithms, page 1279-1297, 2021.
[8] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. A discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67 671-680, 2008
[9] Maria Florina Balcan, Heiko Röglin, and Shang- Hua Teng. Agnostic clustering, In International Conference on Algorithmic Learning Theory, pages 384-398. Springer, 2009.
[10] Rina Foygel Barber and John C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. CoRR, abs/1412,4451, 2014. URL httt::////// wwtp://....////////aaaa/ooeeee/t 11t.:/4412.44555
[11] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. arXiv preprini 2XXx:200000061188 2020.
[12] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analyties in the crowd. In Proceedings of the 26th ACM Symposium on Operating Systems Principles, SOSP 17, pages 441-459, New York, NY. USA, 2017. ACM.
10

---

[13] Mark Bun and Thomas Steinke. Average- case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances Neural Information Processing Systems 32, NeurIPS '19, pages 181-191. Curran Associates, Inc., 2019.
[14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC '14, pages 1-10, New York, NY, USA, 2014. ACM.
[15] Mark Bun, Kobbi Nissim, and Uni Stemmer. Simultaneous private learning of multiple concepts. In Proceedings of the 7th Conference on Innovations in Theoretical Computer Science, ITCS 11, pages 369-380, New York, NY, USA, 2016. ACM.
[16] Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithmss SODA 17, pages 1306-1325, Philadelphia, PA, USA, 2017. SIAM.
[17] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Advances Neural Information Processing Systems 32, NeurIPS '19 pages 167. Curran Associates, Inc., 2019.
[18] Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint arXiv: /902.04990 2019.
[19] Clément Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou. Private identity testing for high-dimensional distributions. arXiv preprint MiXiv:/905. 1947, 2019.
[20] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing. STOC '17, pages 47-60, New York, NY, USA, 2017. ACM.
[21] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 141-148, 2020. doi: 10. F0.11///0CSS447.222220000
[22] Aref N. Dajani, Amy D. Lauger, Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin Machanavajhhala, Simson 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. Presented at the September 2017 meeting of the Census Scientific Advisory Committee.
[23] Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algorithms for proper learning mixtures of Gaussians. In Proceedings of the 27th Annual Conference on Learning Theory, COLT '14 pages 1183-1213, 2014.
[24] Lue Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer, 2001.
[25] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems 28, NIPS 11, pages 2566-2574. Curran Associates, Inc., 2015.
[26] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estima- tion and learning mixtures of spherical Gaussians. Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18 pages 1047-1060, New York, NY, USA, 2018. ACM.
[27] Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. List-decodable mean estimation via iterative multi-filtering. Advances in Neural Information Processing Systems, 33, 2020.
[28] Differential Privacy Team, Apple. Learning with privacy at scale.
https
httpa//www..aiiign.......ee.ooae com/ sttar///eeeenniiitttttrrrraraaaa December 2017.
applaalifferretttaarrivvvyyyyyee Decembm

---

[29] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems 30, NIPS '17 pages 3571-3580. Curran Associates, Inc., 2017.
[30] Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals. arXiv preprint arXiv:2001.02285. 2020.
[31] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Proceedings of the 32nd Annual Conference on Learning Theory, COLT '19, pages 1161-1191, 2019.
[32] John C. Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information. arXiv preprint 1806. 05756, 2018.
[33] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 2017.
[34] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the si Annual ACM Symposium on the Theory of Computing, STOC '09, pages 371-380, New York, NY, USA, 2009. ACM.
[35] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pages 486-503, Berlin, Heidelberg, 2006. Springer.
[36] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensi- tivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265-284, Berlin, Heidelberg, 2006. Springer.
[37] Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 5 Annual IEEE Symposium on Foundations Computer Science, FOCS '10, pages 51-60, Washington, DC, USA, 2010. IEEE Computer Society.
(38] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS '1, pages 550-669, Washington, DC, USA, 2015. IEEE Computer Society.
[39] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable ordinal response. In Proceedings of the 2014 ACM Conference Computer and Communications Security, CCS '14, pages 1064-1067, New York, NY, USA, 2014. ACM.
[40] Marco Gaboardi, Ryan Rogers, and Or Sheffet. Locally private confidence intervals: Z-test and tight confidence intervals. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 19, pages 2545-2554 JMLR, Inc., 2019.
[41] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing, STOC '10, pages 705-714, New York, NY, USA, 2010. ACM.
[42] Peter J. Huber. Robust Estimation of Location Parameter. The Annals of Matheratical Statistics, 35()):33 101, 1964. doi: 10. /214/20///1177773333 URL https:tts////o..oot orr// 10. wtw.12244mmm/1111/ 1177ppmmmm11777772222
[43] Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Zhiwei Steven Wu. Locally private Gaussian estimation. In Advances in Neural Information Processing Systems 32, NeurlPS '19, pages 2980-2989. Curran Associates, Inc., 2019.
[44] Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. Proceedings of the rd International Conference on Machine Learning, ICMI. '16, pages 2436-2444, JMLR, Inc., 2016.
12

---

[45] Gautam Kamath and Jonathan Ullman. A primer on private statistics. arXiv preprint arXiv:2005.00010, 2020.
[46] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Proceedings of the 32nd Annual Conference on Learning Theory,
COLT 19, pages 1853-1900 1902, 2019.
[47] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated Gaussians, In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 168-180. Curran Associates, Inc., 2019.
[48] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy- tailed distributions. In Proceedings of the 33rd Annual Conference on Learning Theory, COLT '20, 2020.
[49] Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regression. Advances in neural information processing systems, 2019.
[50] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS '18 pages 44:1 14:99, Dagstubl, Germany, 2018. Schloss Ceestuul-LeibnizzZZenmme fuer Informatik.
[51] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th International World Wide Web Conference, WWW '09, pages 171-180, New York, NY, USA, 2009. ACM.
[52] Xiyang Liu, Weihao Kong, Sham M. Kakade, and Sewoong Oh. Robust and differentially private mean estimation. CoRR, 2102.09133
2021. URL ltttp://arxivv. wrgg abs/
[53] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, STOC '07, pages 75-84, New York, NY, USA, 2007. ACM.
[54] Karl Pearson, Contributions the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, pages 71-110, 1894.
[55] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the Fourteenth Annual ACM- Symposium on Discrete Algorithms, pages 161-180. SIAM, 2020.
[56] Prasad Raghavendra and Morris Yau. List decodable subspace recovery. In Conference on Learning Theory, pages 3206- 3226. PMLR, 2020.
[57] Rolf-Dieter Reiss. Approximate distributions of order statistics with applications non- parametric statistics. Springer Series in Statistics. Springer- New York, 1989. ISBN 0-387-96851-2. URL http:://doo....... .rriaiorr//// 10. 1007 0-0007797788---11---9---------
[58] Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing, STOC '11 pages 813-822, New York, NY, USA, 2011. ACM.
[59] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. The Journal of Privacy and Confidentiality, 7(2):322,, 2017.
[60] Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In Proceedings of the 58th Annual IEEE Symposhum on Foundations of Computer Science, FOCS '17, pages 552-563, Washington, DC, USA, 2017. IEEE Computer Society.
[61] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near- optimal-sample estimators for spherical Gaussian mixtures. In Advances in Neural Information Processing Systems 27, NIPS '14, pages 1395-1403, Curran Associates, Inc., 2014.
[62] Roman Vershynin. High-Dimensinn Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018
13

---

[63] Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu. Wei Yang, Xiang- Yang Li, and Chunming Qiao. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv: 1607.08025, 2016.
[64] Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Transactions on Information Theory, 64(8))5662-561 2018.
[65] Huanyu Zhang, Gautam Kamath, Janardhan Kulkamn,, and Zhiwei Steven Wu. Privately learning Markov random fields. In Proceedings of the 37th International Conference on Machine Learning, ICML '20. JMLR, Inc., 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes]] The main claims in the abstract and introduction are given by Theorem 1.1 and Theorem
1.2 They are proved in the paper and the appendix. (b) Did you describe the limitations of your work? [Yes] We have formal theorems for our work and raised some open questions which remain open after our work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is a theoretical paper and is unlikely to have any direct negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Many proof's are in appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL.? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zRtrXNmw4cT", "reviewer": "Reviewer_GCJ5", "summary": "This paper studies differentially-private learning of mixture models -- mixtures of Gaussians, in particular, but many ideas likely extend beyond that setting.\nThe paper introduces new ideas to DP learning of mixture models when the mixture components have a priori unbounded means and (co)variances.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper studies differentially-private learning of mixture models -- mixtures of Gaussians, in particular, but many ideas likely extend beyond that setting.\nMixture models are the canonical theoretical setting for studying non-homogeneous data sets, and differential privacy is the industry-standard mathematically rigorous notion of privacy, so this is a learning problem of fundamental importance.\n\nThe context for the paper is the following state of affairs in private mixture-model learning.\nFirst of all, learning mixtures of Gaussians under the stringent notion of *pure* DP is known to require *a priori* boundedness of the means and covariances.\nThis paper studies private learning without such a prior bounds, which means that one must relax pure DP to the weaker $(\\epsilon,\\delta)$-DP.\n(Allowing additive in addition to multiplicative privacy loss.)\n\nIn the pure DP setting, the canonical approach for learning distributions (at least without worrying about running times) involves finite covers: this technology readily generalizes from learning a class of distributions to learning the class of mixtures of those distributions.\nBut this is not true in the $(\\epsilon,\\delta)$-DP setting: the \"locally small covers\" approach which works for learning (potentially unbounded) Gaussians does not generalize to Gaussian mixtures.\nSo a new idea is needed to show that (potentially unbounded) Gaussian mixtures can be learned without too many samples.\n\nThis paper introduces a new approach to show that this holds at least for univariate and high-dimensional but axis-aligned Gaussian mixtures.\nThe approach is conceptually nice.\nThe authors use the (well known) observation that learning mixture models can be reduced to a harder problem, \"list-decodable learning\", where the goal is to learn a distribution given a list of samples of which a large majority have been corrupted by a malicious adversary.\nSince this is not possible information-theoretically, instead the goal is just to learn a short list of hypotheses of which one must be close to the true underlying distribution.\n\nThe authors observe that (1) the known reduction from mixture model learning to list-decodable learning can be done privately, using private hypothesis selection, and (2) design a differentially private algorithm for list-decodable learning of (potentially unbounded) Gaussians.\nMost of the work for (2) is in the univariate case; algorithms for learning univariate Gaussians often generalize readily to high-dimensional axis-aligned Gaussians and that is the case here.\n\nThis paper provides nice technical progress on a fundamental problem -- it was clear that existing cover-based methods would not work, and this paper provides a new idea.\nI think it should be accepted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The technical ideas are nice but not super surprising or hard.\nStill, I think the conceptual contribution is clear enough that this should not keep the paper from being accepted.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "HvSkfhww3c_", "reviewer": "Reviewer_Xmc7", "summary": "As the title suggests, this paper gives algorithms for learning mixtures of $k$ Gaussians to within total variation distance $\\alpha$. It uses a reduction to private list decodable learners from privately learning mixtures of distributions. The number of samples used is linear in $d$ and quadratic in $k$. The flow of the paper is as follows: first it gives algorithms for estimating mixtures of univariate Gaussians, then uses them to estimate mixtures of axis-aligned Gaussians. The main, non-trivial prior tool used in this paper is the private hypothesis selection algorithm. The algorithm for estimating mixtures of univariate Gaussians first involves creating a list-decodable learner for univariate Gaussians, followed by using the aforementioned reduction.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Update: Based on the authors' response, I have decided to update my final evaluation.\n\nStrengths:\n1. The paper is very theoretical, and has non-trivial ideas for both proofs and algorithms.\n2. The sample complexity achieved is very close to the non-private, and is an improvement over Kamath et al.'s paper on learning mixtures of Gaussians.\n3. The reduction is very useful and general, and could be used for learning mixtures of other kinds of distributions as well.\n4. The paper, in general, is quite well written. I was able to understand everything in one shot. Section 3 is very helpful in understanding the rest of the paper.\n5. It was important to mention that the class of mixtures of univariate Gaussians does not permit locally small covers. This helped me understand why it was important to look into this problem more closely.\n\nWeaknesses:\n1. Although the sample complexity is quite good, the algorithms run possibly in exponential time. hence, they are not practical.\n2. Some proof ideas for the main theorems (like Theorem 4.6) could have been put in, as well.\n3. A nitpick comment. When I usually see exponential time algorithms in differential privacy literature, they are usually optimal or close to being optimal. Here, in terms of $k$ and $\\alpha$, the private sample complexity seems sub-optimal. That could be improved. However, it is a big improvement over [KSSU'19].\n4. Another nitpick comment. Generalisation to arbitrary mixing weights could have been mentioned, too, for the sake of completeness, although I'm aware of the space restrictions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, therefore, it's hard to say what the negative impacts on the society would be. In my opinion, there shouldn't be any, and the authors claim the same themselves.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "13LkC4PPPhW", "reviewer": "Reviewer_XGxw", "summary": "This paper considered the problem of learning a mixture of gaussians under DP constraint. The authors proposed an (exponential time) algorithm for learning univariate k-mixture of gaussian distributions with sample complexity k^2log^(3/2)(1/\\delta)/alpha^2eps. They conjectured the extra k factor in the sample complexity is information theoretically unnecessary. The key of the algorithm is a reduction from the list-decodable learning to learning mixture distributions. Specifically, given a list decodable algorithm, one can enumerate all possible combinations of the k-mixtures and use a private hypothesis selection algorithm to find the most plausible k-mixture. They proposed a list decodable algorithm for learning gaussian distribution, which adopts a similar approach as [48]. \n\nFor the multivariate gaussian setting, they considered the axis-aligned gaussian setting. They first obtain a list of distribution on each dimension, and take all possible combinations of the univariate distribution to form a large list of axis aligned gaussians. This leads to a multivariate gaussian k-mixture learning algorithm with sample complexity k^2dlog^(3/2)(1/delta)/alpha^2eps. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper provides new results on an interesting and fundamental problem. It is a little bit disappointing that very few new ideas are applied in obtaining the result except the connection to list decodable learning which has been similarly observed before. It is also a bit unsatisfactory that the algorithm, even though taking exponential time, is not able to get the optimal sample complexity. I am curious about the authors' thoughts on extending the approach to remove the extra k factor and general (non axis-aligned) mixed gaussian setting. For now I will vote for a weak accept.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes progress on a fundamental problem: Learning mixtures of axis aligned Gaussian distributions under (eps, delta) differential privacy. The paper is a nice combination of two ideas: reduction to list decodable learning, and a private algorithm for list decodable learning. These ideas (particularly the second) should find applications in other places. It would be nice if the authors add a comment about the optimal sample complexity (the extra k factor). 
Decision: Accept (Poster)