A Fourier Approach to Mixture Learning
Authors: Mingda Qiao
Guru Guruganesh
Ankit Singh Rawat
Kumar Avinava Dubey
Manzil Zaheer
Venue: NeurIPS 2022 Accept (2022)
Keywords: Gaussian mixture models
mixture learning

Abstract: We revisit the problem of learning mixtures of spherical Gaussians. Given samples from a mixture $\frac{1}{k}\sum_{j=1}^{k}\mathcal{N}(\mu_j, I_d)$, the goal is to estimate the means $\mu_1, \mu_2, \ldots, \mu_k \in \mathbb{R}^d$ up to a small error. The hardness of this learning problem can be measured by the \emph{separation} $\Delta$ defined as the minimum distance between all pairs of means. Regev and Vijayaraghavan (2017) showed that with $\Delta = \Omega(\sqrt{\log k})$ separation, the means can be learned using $\mathrm{poly}(k, d)$ samples, whereas super-polynomially many samples are required if $\Delta = o(\sqrt{\log k})$ and $d = \Omega(\log k)$. This leaves open the low-dimensional regime where $d = o(\log k)$.
    
In this work, we give an algorithm that efficiently learns the means in $d = O(\log k/\log\log k)$ dimensions under separation $d/\sqrt{\log k}$ (modulo doubly logarithmic factors). This separation is strictly smaller than $\sqrt{\log k}$, and is also shown to be necessary. Along with the results of Regev and Vijayaraghavan (2017), our work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, our algorithm runs in time $\mathrm{poly}(k)\cdot f(d, \Delta, \epsilon)$, and is thus fixed-parameter tractable in parameters $d$, $\Delta$ and $\epsilon$.
    
Our approach is based on estimating the Fourier transform of the mixture at carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.

A Fourier Approach to Mixture Learning
Mingda Qiao" Stanford University mgjaodstanford.com
Guru Guruganesh Google Research gurugāgoogle.cm com
Ankit Singh Rawat Google Research
aakitsravattgoogge..com
Avinava Dubey
Manzil Zaheer
Google Research
Google DeepMind manz:lzaheee@@oogle..co com
avinavaduubyygooggee.co
Abstract
We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture 1/2
Ia). the goal is to estimate the means P1: P2,.... Pa E Rd up small eπrоr. The hardness of this learning problem can measured by the separation A defined the minimum distance between all pairs of means. Regev and Vijayaraghavan [2017] showed that with A = [2 Vlol k) separation, the means can be learned using poly(k, d) samples, whereas super- polynomially many samples are required if A ololo k) and d = ?olog k)) This leaves open the low-dimensional regime where o(log k).
this work, we give an algorithm that efficiently learns the means in (log k/ log log k) dimensions under separation d/ vlog lo (modulo doubly loga- rithmic factors). This separation is strictly smaller than vlog K, and also shown be necessary. Along with the results of (Regev and Vijayaraghavan (2017). work almost pins down the critical separation threshold at which efficient parameter learning becomes possible for spherical Gaussian mixtures. More generally, algorithm runs in time poly(k) f'd,, A, e), and is thus fxed-parameter tractable parameters A and
Our approach is based on estimating carefully chosen frequencies, and both the algorithm and its analysis are simple and elementary. Our positive results can be easily extended to learning mixtures non- Gann-Gausiin distributions, under mild condition the Fourier spectrum of the distribution.
Fourier transform of the mixture at
Introduction
Gaussian mixture models (GMMs) are one of the most well studied models for population with different components. A GMM defines a distribution over the d-dimensional Euclidean space as the weighted sum of normal distributions Σx=1
(N,,, Σ,), which are specified by following quantities: the number components l: E N, the component means 14; E IRdd the component covariances Σn dxd which are positive definite matrices, and the weights w, that sum up to 1. In this work, we consider the uniform spherical case, where the weights w; are uniform wy = 1 and the covariance matrix H; La is the identity matrix. The central problem in this setup is to efficiently estimate the means M.,... A4k To avoid degenerate cases such as when some of the means are the same, common to parameterize the problem by the separation of the means A, which guarantees that ||ا M5 lla 2 A for all +
Part of this work was done while working intern at Google Research.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

More precisely, the problem is to estimate the means Mi..... Ais E R up to an error with runtime that is poly(k, L, d) with as small a separation A as possible. There has been a long line of work on this problem which we survey in Section 1.3
Recently, Regev and Vijayaraghavan 2017 showed that separation A (2(voog F) is strictly
necessary when the dimension d = log k). Two natural questions arise immediately. First, if A Vlog sufficient when d = (log k). Although the original work of Regev and Vijayaraghavan [017] showed that it was information theoretically possible, an actual efficient algorithm was only recently developed by Liu and Li [2022) (who show nearly tight results). The second main question is determining the optimal separation in low dimensions when d = o(log k). Previously, even in (1)) dimensions, the exact separation necessary was unknown. In this paper, we settle the second question and give nearly optimal bounds on the separation necessary in low dimensions (see Figure ! for more
details).
1.1 Overview of Results
We begin with a few definitions. A point set { 22, T'. is called A A-separated if || xz 112 2 A for any j j". - We say that a Gaussian mixture is A-separated (or has separation A) if the means of its components are A A-separated. Two point sets {uI..... ub} and {Ui...., } are e-close if for some permutation over [k], | vo() ll2 S e holds for every j.
Our main result is an algorithm that efficiently learns the parameters of a mixture of k spherical Gaussians under separation A x Vlog polly (log log k) in (log k/ log log k) dimensions. In
d
the low-dimensional regime, this separation is strictly smaller than min( /log k. vd), the smallest separation under which previous algorithms could provably learn the parameters in poly(k) time.
Theorem 1.1 (Upper bound, informal). Let P be uniform mixture of k spherical Gaussians in dimensions with separation A = Ω
dd dv/log(log k)/d) There is poly (tim vlug k algorithm that, given samples from P, outpuus is vectors that are w.h.p. e-close to the true means for O(A/Vd).
0
Tog log
See Theorem 2. and Remark 2.2 for a more formal statement of our algorithmic result, which holds for a wider range of separation A and accuracy parameter e. Our learning algorithm is provably correct for arbitrarily small A, > 0 (possibly with a longer runtime), whereas for most of the previous algorithms, there is breakdown point A such that the algorithm not known work when A < A Two exceptions are the algorithms of Moitra and Valiant (2010), Belkin and Sinha 2010).. both of which allow an arbitrarily small separation but run in e (k() time. We also remark that the runtime of our algorithm scales as Ō(k²)) f(d, A, e), and is thus fixed- sted-marrmeetr tractable in parameters d, A and
We complement Theorem 1.1 with an almost-natching lower bound, showing that the d/ //og separation is necessary for efficient parameter learning in low dimensions.
Theorem 1.2 (Lower bound, informal). For d O log l Tog log
and A Vlogk)
there are two
mixtures of is spherical Gaussians in Rd such that: (1) both have separation A: (2) their means not (A/2) /losse and (3) the total variation (TV) distance between them is k: (1))
See Theorem for more formal version of the lower bound.
Theorem and Theorem together nearly settle the polynomial learnability of spherical Gaussian mixtures in the low-dimensional regime. Up to doubly logarithmic factor, the "critical separation" where efficient learning becomes possible d/ dd/llog. k. To the best of our knowledge, this was previously unknown even for d O(1)
See Figure beloow for a plot of our results in the context of prior work. The green regions cover the parameters (A, d) such that mixtures of le spherical Gaussians in d dimensions with separation A are
Whill we focus the mniform-weight case for simplicity. Theorem 1.1 can be easily extended to the setting where each weight is [1/(Ck), C/k] for some constant C
"An exception is the d = 1 case: A result of Moitra (0155] implies that A = 1/11/ k) suffices (see
Section I.3) and matching lower bound was given by Moitra and Valiant 2010

---

Learnable with poly(k) samples
dimension d
Not saampe)s learnable
log k
III
Theorem 2
Theorem
IV
1///log
Jng
separation A
Figure 1:
Region is direct corollary of Moitra and Valiant 2010 Proposition 15]. Regions II, III, and IV are shown by Regev and Vijayaraghavan 2017] Theorems 1.2, 1.3, and 1.4] respectively. The upper boundary of Region IV is the curve A vd. Theorems 1.1 and .22 settle the learnability in the remaining area, by proving that the line = d/v dloloog g k the boundary between polynomial and super- super-polynone polynoooll sample complexities (up doubly-logarithmic factor).
learnable (up O(A) error) using poly(k) samples The red regions contain the parameters under which polynomial-sample learning is provably impossible.
The algorithm that underlies Theorem I. can be easily extended beyond the spherical Gaussian case. The following more general result states that for any distribution 'D whose the Fourier transform does not decay too fast, the following, let D denote the distribution of X + μ when X drawn from D.
efficiently learn the parameters of a mixture of k translated copies of D. In
Theorem 1.3 (Learning more general mixtures, informal). Let P= Σ}= Dps for A-separated Pi...., Ui Rd. There an algorithm that, given e and samples from P. runs time
e X "I""
poly k. A/c, 1/6,
E
for some 5 = c(D,c) and M = M(k, d, A, c), and outputs ji...., fü that are w.h.p. c-close to the true parameters.
See Theorem F. and Corollary for a more formal statement of the runtime. Theorem 1.3 applies to many well-known distribution families that are specified by either a "location parameter" or a "scale parameter". Table D gives a few examples of applying Theorem 1.3 to mixtures of single-parameter
univariate distributions; see Appendix F2 and Appendix F33 for more details.
Limitations of our work. The main limitation is that the positive results only apply to the regime that the dimension d is logarithmic in the number of clusters, and that all clusters are translated copies of the same distribution. A concrete future direction would be to extend our results to learning mixtures of general Gaussians, even in one dimension.
1.2 Proof Overview
For simplicity, we focus on the one dimensional case that P W 1) for A-separated means 14 E R. We index the components such that [Mg] S P22 < ... < | and focus
'In terms of the computational complexity, all the green regions (except small portion of Region III) admit efficient algorithms. The algorithm Li Liu and Li 2022 is efficient when 22( 1/2+=) for any > and thus almost covers Region III. For Region IV, Regev and Vijayaraghavan 2017 gave an efficient algorithm only for d O(1), whereas Theorem [.] covers the entire Region IV.

---

Distribution
Parameter
Density Function
Runtime
Cauchy
P
<1+(2=-0)))
1
O(k2) (((VOEET/A)
Logistic
1
(I+e RT)2
(e
O(ki)) ((O(VOO
Laplace
1
2 6
-2=
0(k3/A²)
Exponential In A
Xe- Aue
(x 2 0]
O(k2) (oooog k/A)
Table 1: Implication of Theorem 1.3 for learning various families of mixtures of univariate distribu-
tions beyond Gaussians, assuming that the parameters of different components are A-separated. The algorithm outputs & parameters that are ( (-A)-ee to the true parameters.
on the following testing problem: Given 0 and samples from P. determine whether μ 0 or Mi 2 e, assuming that one of them is true. Note that this testing problem is not harder than estimating [1, .e....,-4. M4g up error c/3- in the former case that 141 = 0, one of the mean estimates would fall into [-c/3, c/3], whereas all of them must be outside (-2c/3. 2c 2c/3) in the latter case. Conversely, as will prove in Section 2 an algorithm for the testing version can be used for recovering the means as well.
Examine the Fourier spectrum. We start by examining the Fourier transform of P, (FP)(E) = Ex-P [ett]] more commonly known the literature as the churacteristic function. Since the Fourier transform of Gaussian is still Gaussian, and translation in the time domain shifts the phase in the frequency domain, have
[eEx]] e -/
Σ
We will focus on the quantity Ac(() = Σラ= einse, which is the "total phase" over the & components of P. Equation essentially states that (5) can be estimated by averaging eiEX over samples X ~ P.
The key observation is that each term eins of A₁(()) behaves quite differently depending on the magnitude of pg: If Mj O, ct = 1 is a constant, whereas eΔvs is high-frequency wave when |ريا is large. This suggests that the two cases (/4 = and |nr| 2 e) can distinguished by estimating (E) at different frequencies. The cost of estimating (E) however, depends heavily on the frequency & Equation [ together with simple concentration bound shows that O(k²) O(s") samples are sufficient for estimating (5) up to a constant error.
Therefore, the crux of this approach is to find the minimum M > such that the be distinguished by estimating (g) over & E [-M, M). (This known as the super-resolution problem, which we discuss in Section The sample complexity of the testing problem can then be roughly bounded by Ok:2). (MM) In the following, we explore different ways of picking from the range M, M).
can
Choosing & randomly. Our overall strategy is to draw & randomly from some distribution De over interval [- .M, M) and evaluate Rg-D, [E)] We will argue that this expectation is very close to its first term Eş~D; [eim]]] which takes different values depending on whether μ4 = 0 or ||L] 2 e. Then, De needs to be chosen such that: (1) There is gap in the value of LE [ between the two cases; (2)
Σ} 2 Eg [efasE] is small enough for the gap in the first term be easily identified.
As warmup, let De be the uniform distribution over [0, .). A simple calculation shows that the gap in the first term EgwD, [ between the two cases (Az = 0 or [μn] 2 e) is lower bounded by M(min Me,, 13), whereas the contribution from the j-th component satisfies [Eg-D, [e

---

0
Furthermore, the A-separation between the means implies |ayl = 2(A)). Thus,
M|ng/
k Σ
log k MA
Mlul
MA
3
2=
The above is much smaller than Min 1) if we set M 2 max
logk
log
Unfortunately,
even when A and e are constants, we have O(k²) cO(M)) = 4Ollog)) k) and the resulting sample complexity is already super- poper-polynomiill in k.
better choice of Dz. turns out that choosing De to be a truncated Gaussian leads to much lower sample complexity. For some a & M, we draw & ~ (0, o²) and then truncate it to [-M, M). Without the truncation, the expectation of elvi has a nice closed form:
[e e e u3//2
E (0,
which is exactly the Fourier weight of M o2) at frequency My. Note that this decreases very fast as [pyl grows, compared the previous rate of Mayl when D3 is uniform.
again follows from a simple calculation that: (1) Depending on whether μr = 0 or |11 2 c, the
gap between ggg [efure] is Mmmin(o2* ;1)): (2) The total contribution from j = 2, ..... upper bounded by
Σ J=2 (0,2)
[ewse]
Σ 2=2
S(PPA3))) = -
e
where the second step applies |ay1 2(Aj) and the last step holds assuming addition, we need to deal with the error incurred by the truncation. The Gaussian tail bounds imply that [<] 2 M happens with probability e - /a"), Since (x) < k for any &. the noise from the truncation is most e /oM in magnitude.
(11/A). In
remains to choose M, a > 0 that satisfy the two inequalities:
~ < minfo2e2,13 and k e E---a( < min(o"22,1)
suffices to choose a S 1 2 and M S 3/ 2 A Vog AA For 6 = 2(A), the sample complexity O(k²) O(MS)) reduces to 0001433) which is polynomial in A for any fixed A. We note that in the above derivation, the assumption that each cluster of is Gaussian is only applied in Equation the quantity (,) Σラ= elpn can still read off from the Fourier transform of at frequency except that the extra factor e <2 becomes (F) the Fourier transform of at frequeney &. This observation leads to our algorithm for learning a mixture of multiple translated copies of D (Theorem 1.3)
(through the Fourier transform). For any distribution D over and P = Σ3 j==1 Day, !
Gaussian truncation. For the spherical Gaussian case, however, the above only gives an algorithm with runtime 400/22), which becomes super-polynomial soon A o(1), falling short of achieving the near-optimal separation of log log in Theorem 1.1
log
We further improve our algorithm for the spherical Gaussian case using a "Gaussian truncation" technique. Intuitively, when deciding whether the mixture P contains cluster with mean zero, sample X P is much more informative when X is small. This motivates us to focus on samples with small magnitude via truncation.
We apply such a truncation in soft way way-weighting each sample X with e -x This turns out to be sufficiently effective while keeping the entire analysis simple. Note that the weighting effectively multiplies the mixture P with the standard Gaussian AC pointwise. The result is
5

---

still a (un (un-normalized) mixture of Gaussians: Up to constant factor, the pointwise product is 1 - - 11222 Consequently, if we repeat the analysis from previous paragraphs to this weighted mixture, the noise coming from components with large |ayl become even smaller.
This eventually allows us to learn the mixture efficiently at separation A
log log log k
We prove
Theorem
1.1 via natural extension of this analysis to the d-dimensional case.
Lower bound. Our proof of Theorem 1.2 follows an approach similar to those in the previous
lower bound proof's of Moitra and Valiant 2010 Hardt and Price 2015 Regev and Vijayaraghavan
2017]: First, construct two sets of well-separated points {ui (
P* and {u] (
())
with (approximately) matching lower-order moments, i..., T ش3=1
for every small 1. Then, show that these matching moments imply that after a convolution with Gaussian, the resulting mixtures are close in TV-distance and thus hard to distinguish.
In more detail, similar to the proof of Regev and Vijayaraghavan [217]]. we start by choosing NN arbitrary points from a small &g ball, such that they are A --eeparated. The main difference is that Regev and Vijayaraghavan (017) pick N >>> k, and show that among all the (+) possible mixtures, there are at least two mixtures with similar moments via pigeon-hole type argument. In contrast, we work in the NN < l regime, and obtain two point sets with matching lower-order moments by slightly perturbing these N points in opposite directions. The existence of such a good perturbation is shown via a careful application of the Borsuk-Ulam Theorem, which is inspired by similar application in Hardt and Price 2015
1.3 Related Work
Learning Gaussian mixture models. Most closely related to this paper is the line of work in the theoretical computer science literature on algorithms that provably Iearn mixtures of Gaussians. The pioneering work of Dasgupta 1999] showed that an ((vd) separation between the means of different components is sufficient for the samples to be easily clustered. Several subsequent work (e.g.. Vempala and Wang (2004), [Arora and Kannan 2005),[Achlion
and McSherry (2005), Kannan
et al.
2005], Dasgupta and Schulman [2007]. J. Brubaker and Vempala| (2008)) further generalized
this result and the separation condition is relaxed to A 12(min k. d) poly(log k log d))
by Vempala and Wang (2004). We refer the readers to Regev and Vijayaraghavan [0177 for a more
detailed survey of these results.
Moitra and Valiant 2010) and Belkin and Sinha 2010 gave the first algorithms for learning general mixtures of Gaussians (with different unknown covariances) under an arbitrarily small separation between different components. Both algorithms are based on the method of moments, and run in time polynomial in d and the inverse of the minimum TV-distance between different components when A = (1). For large k however, the runtime exponential in k.
Regev and Vijayaraghavan (017) showed that poly f, d) samples are sufficient to estimate the means of a mixture of spherical Gaussians, if the means are separated by == ==[(vlo k). Unfortunately, their algorithm involves an exhaustive search and is computationally inefficient. Subsequently, three concurrent work (Diakonikolas et al., 2018 Hopkins and Li 2018 Kothari et al.) 2018 developed algorithms based on the Sum-of-Squares hierarchy that run in time (dk))ooly[17)) and learn mixtures gives quasi-polynomial time algorithm that achieves the Vlog Ie separation in Regev and Vijayaraghavan (2177). A very recent work of Liu and Li (022) made further progress towards learning 32 ([(llog k) -separated mixtures efficiently, by giving a polynomial-time algorithm that succeeds under separation (log k) 1/2+c for any constant e > 0.
with separation A 2(k)). In particular, setting ? se log lo
log
Lower bounds. On the lower bound side, Moitra and Valiant 2010 first proved, by explicitly constructing a hard instance, that learning a mixture of & Gaussians with separation A = ((1VV)) requires (lkk)) samples even
dimension. Hardt and Price 2015 focused on the regime where k == 0(1) and the recovery error goes to zero, and showed that 2-6k) samples are necessary. Anderson et al. 2014] proved a lower bound that strengthens the result of Moitra and Valiant [2010]: Separation A- 1/poly(k) is insufficient for the mixture to be learnable with polynomially many

---

samples, even when the means of the Gaussians are drawn uniformly at random from [0, 1]d for Olog k/ log log k).
Regev and Vijayaraghavan 2017 proved that in = Olog k) dimensions, no polynomial-sample algorithm exists it A (lv log k). In particular, even when the means are chosen randomly, the resulting mixture is still hard to learn with high probability. This lower bound, together with their
positive result for the A (Vlog k) regime, shows that vlog is the critical separation threshold in high dimensions.
If we restrict attention statistical query (SQ) algorithms, Diakonikolas et al. 2017 proved that any SQ algorithm needs ((2()) queries if d 2 poly(k) and non-spherical components are allowed.
Density estimation. In contrast to the parameter estimation setting that we focus on, the density estimation setting requires the learning algorithm to output (the representation of) hypothesis distribution 1 that close to the mixture P in TV-distance. Ashtiani et al. (2020) proved that the sample complexity of learning Gaussian mixtures up to TV-distance of c is (ddk/c²) in general, and ((dk/=²) ) if all components are axis-aligned. Unfortunately, their learning algorithms are not computationally efficient and run in time exponential in k. For the spherical case. Diakonikolas and Kane 22200] gave more efficient algorithm that runs in quasi muasi-polynomial time poly(d) (k/c))(lo kj, In the proper learning setting (i.e., P must be Gaussian mixture), Suresh et al. [2014] gave an algorithm that takes voly(dk//c) samples and runs in time poly(d) (k/c))(k))
Super-resolution, and mixture learning using Fourier analysis. Finally, we acknowledge that the Fourier approach that we explore in this work is fairly natural, and similar ideas have appeared in prior work. particular, our approach is closely related to the super-resolution problem (Donoho 1992]. Candès and Fernandez- Granda (013 2014) to recover & unknown locations M1..... M4
k Rd from (exact noisy) observations of the form Σ j=m ca for ||E|| < M, where M is called approach (outlined in
the cutoff frequency, and the norm is typically lz & In comparison,
Section 1.2p differs in two aspects: (1) We focus on simpler testing version of the problem-to decide whether one of the locations is near given reference point; (2) The Gaussian truncation
significantly down-weights the observation coming from the points that are far from the reference
point.
showed that a cutoff frequency of M = ((1A)) suffices the points are A-separated. This implies algorithm that efficiently learns spherical Gaussian mixtures in one dimension under separation 1/ l/olog k. which is (nearly) recovered by our positive result. For the general case, Huang and Kakade 2015 gave algorithm that provably works for (l2) cutoff frequency M- = O([vdlog
For the d = case, Moitra 2015
log A)A When applied to learning GMMs, however, their
algorithm requires separation vd. It is conceivable that the algorithm of Huang and Kakade [2015). equipped with appropriate modifications and tighter analysis (e.g., the approach of Chen and Moitra (202T)), might give guarantee similar to ours, but no such analysis is explicit in the literature to the best of our knowledge. Moreover, our approach leads to an arguably simpler algorithm with an elementary analysis.
More recently, Chakraborty and Narayanan 2020 gave algorithm that is similar ours for learning mixtures of spherical Gaussians via deconvolving the mixture. However, their algorithm is only shown to work when A = 2 d). Chen et al. [2020] studied the problem of learning mixtures of linear regressions (MLRs), which can be reduced to estimating the minimum variance in a mixture of zero-mean Gaussians. They solved this problem by estimating the Fourier moments - the moments of the Fourier transform, and gave the first sub-exponential time algorithm for learning MLRs. Chen and Moitra (202T) studied learning mixtures of Airy disks, a problem that is motivated by the physics of diffraction. Their algorithm also proceeds by first estimating the Fourier transform of the mixture, and then dividing it pointwise by the Fourier spectrum of the "basc" distribution.
1.4 Organization of the Paper
In Section 2 we formally state our main algorithmic result as well as our main technical theorem, which addresses testing version of the problem. We then sketch how our upper bound follows from
7

---

simple reduction from parameter learning to testing. In Section we give simple algorithm that solves this testing version by examining the Fourier transform the mixture.
The pseudocode of our algorithms are presented in Appendix A We defer a few technical proofs to Appendices B through D We prove our lower bound result (Theorem 1.2] in Appendix [ Finally, in Appendix F we formally state and prove the guarantees for learning non- Gausaan mixtures and present few applications of this result.
2 From Learning to Testing
We first state our main positive result the formal version of Theorem
I.I
Theorem 2.1. Let P E Nu Ia) be a uniform mixture of k 2 spherical Gaussians with (im/AA100,, (32 /minnd..nn.. In kn)] There is an algorithm
A sepparrtedd means Id and (Algorithm D that, given samples from P. outputs k vectors that are e-close to pi.... He with high probability. The runtime (and thus the sample complexity) of the algorithm is upper bounded by
O((A/c)*R3 1.3 log² k) max{(d/e))os)
d0ld) (
c(MP)
where 2 x A7 (min(d, log k- + log +) (minfd + log k. d log(2 + })} + log 2)
Remark 2.2. When d = O
log &s log log
and A/E @(vd), the runtime can be simplified into
poly(k))-oo exp (o
d (0(
min log k. d log 2 12 ))) A
which poly(k) if A = =5 Vlogk k
log log
When d = o(log this condition is strictly
looser than both A = Q d) and A 22( Vlg k).
We prove Theorem 2.1 by reducing the parameter learning problem into the following testing version: Given samples from mixture P, determine whether P contains cluster with mean that is close to given guess 1¹ E IRd Formally, we prove the following theorem:
Theorem 2.3. Let P = E/= N Ia) be uniform mixture of k 2 2 spherical Gaussians with A-separated means Red Lei < min //100,, A /322 In k})} and μ² Rdd There is an algorithm (Algorithm 2 that, given samples from P. either "accepts" "rejects", such that it:
Accepts with probability 2/3 if minje(M) ||l 10112 || S c/2.
Rejects with probability 2 2/3 minje(M [|w; μ² 11 c.
The runtime (and thus the sample complexity) of the algorithm is upper bounded by O(k2(A/e))) O(d+M(), where M² < - (minfd, log k} log } (min + log k, d log(2 + - log +)
Assuming the above theorem, the proof of our main theorem straightforward and is thus deferred to Appendix C The proof proceeds by first drawing few samples X1...., Xy from the mixture, and then running the tester (from Theorem 2.3) to decide whether each X, is close to one of the mean vectors of the mixture. Then, simple argument shows that the samples that the tester accepts can be easily clustered to recover the means. Note that if a sample X, comes from the j-th component A (pgg Ta), there is decent probability (e.g., R(c) when d = 1) that X; is c-close to μıj. Thus, can guarantee that X,...., X, contain good guesses for all the means for moderately large N.
3 Solve the Testing Problem using Fourier Transform
Now we solve the testing problem and prove Theorem 2.3 We assume without loss of generality that n = 0, since we can reduce to this case by subtracting μ** from each sample from P. We also re-index the unknown means ,,...., #4 so that ||u is non-decreasing in j. The testing problem is then equivalent to deciding whether ||l||| S e/2 or | 2 2 e.
The following simple lemma, which we prove in Appendix D gives the Fourier transform of the mixture P when a "Gaussian truncation" of - is applied.
8

---

Lemma 3.1. For P = Mug, Ia) and any E I,
e -111/11//2 edls ed(s" x0] --1111144
e e-11811/4
E X-P
e 1111y11/// edly 6/2)
2d/2k A,(5),
20/2k
where we define A,(E) = E5= e- 1251l2/4 E/2)
We will show that (5) behaves quite differently depending on whether ||1/|2 S c/2 or || 2 c. Thus, we can solve the testing problem by estimating (E) for carefully chosen &. Coneretely, we will draw & from (0, o² Id) and then truncate it to B(0, MM := {ar E ||>|| s M), for parameters M, a > 0 to be chosen later. Formally, we focus on the following expectation:
Tp = (~((0,
(A) 1||lll2 < M]].
The key step of our proof of Theorem 2.3 is to show that Tμ is close to (a" (1+)) and is thus helpful for deciding whether || e/2 or | ll e. The following lemma, the proof of which relegated to Appendix D helps us to bound the difference between Tμ and (a" 12) 3/4
Lemma 3.2. For any M, >> 0 that satisfy M / 2 5d.
T2 Σ - (o' 12+ + o (e-MMMM ((03))
Ils 11//4
where the (xx) notation hides complex number with modulus S
By Lemma 3.2 the difference Tμ (0² 1141111111/// is given by
1 12 3/4 + 0 (e M² MM(((a))))
Let S1 Σj (a² 12+ and S. Σラ= e- Ill 12/4 denote the two summations above.
We have the following upper bounds on S1 and S2, which we prove Appendix D
Claim 3.3. Assuming (a² / 1)42 2 100 min k; d), S1
min (k, 24).
2,
A 100d,
Claim 3.4. We have S² <
14 +
267d A
max
32d
d/2 AZ
A 100d.
Furthermore, S2 <
10 min {R. 1+ 32d d/2+1]
Now put all the pieces together and prove Theorem 2
Proof of Theorem
2.3
By Lemma 3.1
E
(E)
[|Ell2 & M]]
(0,
E 12))
24/2
1//l// - 11 ((Tx)) x) [[[[] s M]
Since the term inside the expectation has modulus S k (d) a Chernoff bound implies that we can estimate Tμ up to any additive error > using (({+/n)?) o(d+M)2 samples from P.
By Lemma 3.2 and our definition of S, and Sg, assuming M / 2 5d,
Tμ - -
(a² 122/ < S +e M /((a(())))))) (5aa))
In the rest of the proof, we will pick a and M carefully so that both S and - S2 are upper bounded by = (o² 1)e² /64. Assuming this, done: We can simply estimate Tμ

---

up to an additive enror of 7. Let Ta denote the estimate. We accept if and only if Re 2 0 =
(1 +e (02/2+11
Indeed. suppose that 1| - e/2, we have
Re Re 2 Re T - 2 c (0 / 11/4 (S) + c >M/ (()))))))))))))))))))))))))))) 52) - 2
-3y-
Similarly, Re Tu e 12-22211) + By if 1ull 122 2 e. we set a such that 12 I 1, have /=(02 ( /16 e 10 10 2 (0 1)e² = 8y, which implies Re Tu > 0 in the former case and Re Tu < 0 in the latter case. Therefore, our algorithm decides correctly.
Choice of parameters. Claim 3.3 implies that we set 0²/2 + = (min (d. In k3 In 2) we can ensure S1 I (o2/2 + 1)e² 2 64 7- Furthermore, this choice of and the assumption 6 < / 100, A/(32 min (d, k}) guarantee the condition (a²/2 + 1)e² < that we need.
It remains to pick M such that e- //oa) S2 - (22/2+1)e* /64 64. We also need M²/0²² N 5d to ensure that Lemma 3.2 can be applied. It suffices to let M² 2 5 (d+ In S2 + (0'/2+1)e²
Our choice of a guarantees In (a2/2+1)6²
64 I 2n 5. so it is in turn sufficient to pick M such that
5120
+ In A) 2)
( d (d+ 2lm
M
min (n,n(d,Ink))
+ In S2
A
Applying Claim
3.4 shows that M can be chosen such that
1 2
minfd,log k} + log 2) (min d log k. dog 2 Az ) log
A)
A
2 <
Runtime, The runtime of our algorithm is dominated by the number of samples drawn from P P-O((K/7)²) old+-rr) where = O((o² + 1)E²). Plugging our choice of a into gives 1/7 O((A/))?) The runtime can thus be upper bounded by (()(())))+) o(d+
Acknowledgments
We would like to thank the anonymous reviewers of earlier versions of this paper for their suggestions on the presentation and for pointers to the literature.
References
D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In Conference Learning Theory (COLT), pages 458-469, 2005.
Anderson, M. Belkin, N. Goyal, L. Rademacher, and J. Voss. The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures. In Conference Learning Theory (COLT), pages 1 1135-1164 2014.
S. Arora and R. Kannan. Learning mixtures of separated nonspherical gaussians. The Annals of Applied Probability, 15(1 A):69 2005.
H. Ashtiani, S. Ben-David, N. J. Harvey, C. Liaw, A. Mehrabian, and Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67(6):1-42 2020.
M. Belkin and Sinha. Polynomial learning of distribution families. In Foundations of Computer Science (FOCS), pages 103-112, 2010.
S. C. Brubaker and S. Vempala. Isotropic and affine-invarian clustering. In Foundations of Computer Science (FOCS), pages 551-560, 2008.
E. J. Candès and C. Fermandez- Super-resolution from noisy data. Journal of Fourier Analysis and Applications, 1299-1222-1254, 2013.
10

---

E. J. Candès and C. Femandez-Granme Granda. Towards mathematical theory of super-resolution. Commu- nications on pure and applied Mathematics, 67(6))906 90009 2014.
Chakraborty and H. Narayanan. Learning mixtures of spherical gaussians via fourier analysis. arXiv preprini urXiv:2004.05813, 2020.
Chen and A. Moitra. Algorithmic foundations for the diffraction limit. In Symposium on Theory of Computing (STOC), pages 490-503, 2021.
S. Chen, J. Li, and Z. Song. Learning mixtures of linear regressions in subexponential time via fourier moments, In Symposium on Theory of Computing (STOC), pages 587-600, 2020.
S. Dasgupta. Learning mixtures of gaussians. In Foundations of Computer Science (FOCS), pages 634-644, 1999.
S. Dasgupta and L. J. Schulman. A probabilistic analysis of em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research (JMLR), 8:203-226, 2007.
I. Diakonikolas and D. M. Kane. Small covers for near-zero sets polynomials and learning latent variable models. In Foundations Computer Science (FOCS), pages 184-195, 2020.
I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of ligh-dimensional gaussians and gaussian mixtures. In Foundations of Computer Science (FOCS), pages 73-84, 2017.
I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Symposium Theory of Computing (STOC), pages 1047-1060, 2018.
D. L. Donoho. Superresolution via sparsity constraints. SIAM Journal on Mathematical Analysis, 23 (5):1309-133) 1992.
M. Hardt and E. Price. Tight bounds for learning a mixture of two gaussians. In Symposium on Theory of Computing (STOC), pages 753-760, 2015.
B. Hopkins and J. Li. Mixture models, robustness, and sum of squares proofs. Symposium on Theory of Computing (STOC), pages 1021-1034, 2018.
Q. Huang and S. M. Kakade. Super-resolution off the grid. In Advances in Neural Information Processing Systems (NIPS), pages 2665-2673, 2015.
R. Kannan, H. Salmasian, and S. Vempala. The spectral method for general mixture models. In Conference on Learning Theory (COLT), pages 444-457, 2005.
P. K. Kothari, J. Steinhardt, and D. Steurer. Robust moment estimation and improved clustering via sum of squares. In Symposium Theory of Computing (STOC), pages 1035-1046, 2018.
B. Laurent and Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
A. Liu and Li. Clustering mixtures with almost optimal separation in polynomial time. In Symposium on Theory of Computing (STOC), pages 1248-1261, 2022.
J. Matoušek, A. Björner, and G. M. Ziegler. Using the Borsuk-Ulam theorem: lectures topological methods combinatorics and geometry. Springer, 2003.
A. Moitra. Super-resolution, extremal functions and the condition number of vandermonde matrices.
In Symposium on Theory of Computing (STOC), pages 821-830, 2015.
A. Moitra and G. Valiant. Settling the polynomial learnability of mixtures of gaussians. In Foundations of Computer Science (FOCS), pages 93-102, 2010.
O. Regev and A. Vijayaraghavan. On learning mixtures of well-separated gaussians. Foundations of Computer Science (FOCS), pages 85-96, 2017.

---

D. J. Smith and M. K. Vamanamurthy, How small is a unit ball? Mathematics Magazine, 62(2): 101-107, 1989.
A. Suresh, A. Orlitsky, J. Acharya, and A. Jafarpour. Near-optimal-smppl estimators for spherical gaussian mixtures. In Advances in Neural Information Processing Systems (NIPS), pages 1395- 1403, 2014.
S. Vempala and G. Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-86) 2004.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The results are theoretical.
(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] The assump- tions are stated in the theorems.
(b) Did you include complete proofs theoretical results? [Yes] The main paper includes part of the proof and most of the proof ideas. Technical proofs are included in the 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 or as 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 to 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 are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) 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]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "XC5rqcRqAVL", "reviewer": "Reviewer_phfG", "summary": "This paper considers the problem of learning Gaussian mixture models; specifically estimating the means of a uniform spherical mixture of $k$ Gaussians with identity covariance matrix in $d$ dimensions. A common parametrization is the minimum separation ($\\Delta$) between any mean-pair. Previous works have shown that for polynomial sample complexity a) if $\\delta$ is $o(\\sqrt{logk})$ then $d$ cannot be $\\Omega(\\log k)$, b) $\\delta = \\Omega(\\sqrt{log k })$ is possible, and c) $\\delta = o(1/\\sqrt{log k })$ is not possible. This paper nails down the $\\delta$, $d$ tradeoff in the intermediate $\\delta$ region. Specifically it shows that $\\delta = d/\\sqrt{log k}$ is optimal. \n\nThe crux of the algorithm is two fold. First sample ln k/p samples from the mixture where p is the probability that a sample from the mixture is \\eps close to some cluster's mean. Then the key part of the algorithm is to test if a given guess of the mean is close to one of the mean vectors or far away from it. This is done by estimating the expectation of the Fourier transform under truncated Gaussian as a statistic.  ", "questions": "Apart from the presentation comment, I don't have other questions. ", "limitations": "The limitations section in the paper is adequate. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper settles a gap in existing literature about a fundamental problem that the machine learning community has studied for a while. The analysis is based on a novel technique that possibly might generalize to other mixture models. \n\nI don't have any major complaints. Nevertheless, I think the presentation of the paper could be vastly improved to make it stronger. For example, section 1.2 appears out of nowhere - it is not apiori clear why one might want to consider a testing problem. Even in the later sections, the flow of the algorithm is not clear which is particularly not ideal because only background forms the first 7 out of 9 pages of the submission. It would be much better if main ideas of the algorithm were in the submission instead of the appendix. For instance, it would be cleaner for the main submission to have more details about why drawing samples from the mixture is sufficient to give good mean guesses.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M7XwNfVj5GJ", "reviewer": "Reviewer_eNbi", "summary": "This paper provides a Fourier approach to the problem learning mean parameters of spherical Gaussians and its computation complexity. In the low-dimensional regime, the computation complexity of the algorithm is shown to be polynomial in the number of clusters. The computation complexity bound is examined carefully with respect to the magnitude of the the number of dimensions, the number of clusters, and the separateness of the mean parameters. The algorithm can also be extended to learn mixtures of other well-known local families of distributions.", "questions": "1. Can you provide some simulation studies with the proposed algorithms and demonstrate the complexity with some figures? It would be very helpful to understand the theory better (especially to differentiate the regimes in Figure 1) and to show that the algorithm works. With the considered setting, simulation studies should not be very difficult.\n\n2. How can we compare the complexity of this Fourier-based algorithm to well-known algorithm solving mixture models such as Expectation-Maximization? It is worth mentioning this in the Related Work section. ", "limitations": "The considered problem is of interest to the Mixtures Learning community. A limitation of this paper is the lack of experimental studies. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: The writing style of the paper helps the reader to quickly understand its main contributions without going too deeply into details with several technical terms when bounding the computation complexity. The proofs in Appendix are clear and carefully written. \n\n**Weakness**: The paper lacks experiment components. Without some simulation studies, it is hard to understand the advantages of this approach to other algorithms in the literature. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "DUUWu_YXx_6", "reviewer": "Reviewer_6EhS", "summary": "The authors consider the problem of estimating means $(\\mu_i)_{i=1}^k$  from $m$ sample of the mixture\n\n$\\sum_{i = 1}^k \\mathcal{N}(\\mu_i, I_d)$, up to a small error. The ability to estimate the means primarily depend on the minimum separation between all pairs of means, the number of samples $m$, dimension of samples $d$, and number of clusters $k$. It also desirable to estimate the means, up to an error, with runtime that is polynomial in the parameters. The authors answer this problem in the low dimension regime where $d =o(\\log k)$, which has been an open problem. Their main result provides an algorithm that provided samples from the mixture, efficiently learns the parameters in dimension $O(\\log k/\\log \\log k)$ if the minimum separation between the means is at least $\\frac{d}{\\sqrt{\\log k}}$. The runtime is shown to be polynomial in $k$. Their algorithm considers the Fourier transform of the mixture and estimates the corresponding characteristic function by carefully designing a sampling strategy for the frequency in this Fourier domain. I think the paper is well-written and clear.", "questions": "- Is there a quantifiable (in parameter like $d$, $\\Delta$, $k$, $\\dots$) number of sample lower bound required for estimating the means to a fixed error?\n- Echoing the points above, what are the practical limitations of the algorithm?\n\n", "limitations": "The paper very briefly mentions its limitations. \n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-written and clear. The authors clearly explain the problem, outlining their contributions. Their proof for $d=1$ provides a good initiation for the general proof.\n- The problem being considered is a well-studied problem and, to my knowledge, the contribution seem significant.\n\n\nWeakness:\n- While the paper is primarily of a theoretical nature, the authors provide an algorithm to estimate the means of the spherical Gaussian. If possible, it would be very interesting to see numerical performance of this algorithm, or a discussion on why this is not feasible.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept