On Learning Parallel Pancakes with Mostly Uniform Weights
Authors: Ilias Diakonikolas
Daniel Kane
Sushrut Karmalkar
Jasper C.H. Lee
Thanasis Pittas
Venue: ICML 2025 spotlightposter (2025)
Keywords: gaussian mixture models
parallel pancakes
statistical query
high-dimensional statistics
Primary area: theory->learning_theory
TL;DR: We study the complexity of learning k-mixtures of Gaussians with shared covariance and non-trivial weights, establishing a lower bound matching existing algorithms and extending testing algorithms to handle more general weight distributions.

Abstract: We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on $\mathbb R^d$. This task is known to have complexity $d^{\Omega(k)}$ in full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying additional structural properties. A natural assumption posits that the component weights are not exponentially small and that the components have the same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi-polynomial upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a quasi-polynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary.

On Learning Parallel Pancakes with Mostly Uniform Weights
Ilias Diakonikolas' Daniel M. Kane 2 Sushrut Karmalkar 34 Jasper C.H. Lee" Thanasis Pittas'
Abstract
which is one of the most studied problems in statistics and machine learning, with a large body of research over the past few decades, e.g., Vempala & Wang (2002); Kannan et al. (2005); Achlioptas & McSherry (2005) - see Appendix A for a detailed literature review.
We study the complexity of learning k-mixtures of Gaussians (k-GMMs) on IRd. This task is known to have complexity d((k) in full generality. To circumvent this exponential lower bound on the number of components, research has focused on learning families of GMMs satisfying addi- tional structural properties. natural assumption posits that the component weights are not expo- nentially small and that the components have the same unknown covariance. Recent work gave a dO(log(1/ (/m////miiitieeee algorithm for this class of GMMs, where Wiin is the minimum weight. Our first main result is a Statistical Query (SQ) lower bound showing that this quasi- muasippolynomill upper bound is essentially best possible, even for the special case of uniform weights. Specifically, we show that it is SQ-hard to distinguish between such a mixture and the standard Gaussian. We further explore how the distribution of weights affects the complexity of this task. Our second main result is a polss-pplynomial upper bound for the aforementioned testing task when most of the weights are uniform while a small fraction of the weights are potentially arbitrary.
The setup is as follows: the learning algorithm observes i..dd samples from k-component GMM model (k- (B-GMM) in R2, P = Ex= wyN( (14, 2,), and the goal is to either learn the mixture total variation distance, learn its param- eters, or cluster samples from the GMM correctly. The first task is known to be poly (d, k) samples, as are the second and third, provided the components are sufficiently well-separated, however known algorithms often require more. While the particular case of spherical mixtures (i.e., M; = /) can be learned in poly (d, k)) time and samples, (Liu & Li, 2022; Diakonikolas & Kane, 2024), the best-known algorithms for learning arbi- trary GMMs (i.e. with arbitrary weights, and arbitrary and different component covariances) have sample complexity that scales with (o() (Bakshi et al., 2022). In this paper, we are concerned with an intermediate regime between the two extremes, where the components share an unknown but common covariance matrix.
feasible with
Diakonikolas al. (2017) showed that for such mixtures, any cub-exxonential time algorithm in the Statistical Query (SQ) model requires a sample complexity of 22(k) The SQ model consists of algorithms that, instead of drawing samples from the data distribution, make queries to approxi- mate expectations of bounded functions (formally defined in Definition 1.2).
1. Introduction
Learning mixture models in high dimensions is a classic and fundamental task with applications in a plethora of domains, such as bioinformatics, astrophysics, and marketing (Lind- et al., 2010); see Titterington
The hard instances they proposed are "parallel pancakes" MiiMs-rittures of mairwise-separater Gaussians whose component means are collinear along an unknown direction e, with arbitrary variance in the v-direction and identity covariance in the orthogonal subspace. This will be formally defined in Problem 1.1. Bruna et al. (2021); Gupte et al. (2022) further extended the hardness result to general algorithms but under cryptographic assumptions: similar hardness results were also shown for sum-of-squares algorithms (Diakonikolas et al., 2024).
say. 1995; al. (1985) for extensive list of applications. The pro- totypcall case is that of Gaussian Mixture Models (GMMs)
Author names in alphabetical order Department of Computer Sciences, University Wisconsin Madison, Madison, United States University of California San Diego, San Diego United States Microsooft Research, Cambridge. England "Some of this work was done while the author was postdoctoral researcher UW-Madison. Uniiversity of California Davis, Davis, United States. Correspondence to: Thanasis Pittas <pittas @ wis...ddu>>.
While these results together might suggest that k-GMM learning is fully understood algorithmically, the current theory remains unsatisfactory, in the following sense: the
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Learning Parallel Pancakes with Mostly Uniform Weights
hard instances developed in Diakonikolas et al. (2017) have rather ill-conditioned mixing weights- Some of the mixing weights are 1/ poly(k), but others can be as small as 2 A natural question then is: is it possible to improve the com- plexity of learning algorithms when all weights are more naturally conditioned, i.e., w; 2 //pol(()) for all i?
mine the maximum number m of moments that k-parallel- pancake GMMs can match with (N 7). Our SQ lower bound (Theorem 1.3) comes from showing that m = Qilog k), by employing a result from design theory. Our second, algorithmic result (Theorem 1.4) critically builds on an umpossibility-of-mooo mom-m-ommttchiiine argument (Proposi- tion 4. I). showing that if there are k' S k arbitrary weights in the k- k-GMM, then m must be (log(() + k'). We show this through a novel proof strategy that bounds the ratio of expectations of appropriately chosen non-negative polyno- mials that vanish on the points with arbitrary weights.
This question was considered in Buhai & Steurer (2023): Anderson al. (2024), which study GMMs that have a minimum mixing weight Wmin 2 1/ poly(k) and unknown but common covariance across components. Under the assumption that the mixture components are separated in total variation distance, they provide an algorithm that can correctly cluster 99% of the points, using time and sample complexity (1/g(1/mm))) I k). In particular, their results apply to parallel pancake instances, showing that it is possible to circumvent the d' (()()) (SQ) lower bound under mixing weight assumptions.
1.1. Our Results
We first formally state the hypothesis testing problem which requires the algorithm to distinguish between a k-parallel pancake and the standard Gaussian (O,
Problem 1.1 (Parallel Pancakes Testing Problem). One has (i.i.d, sample or SQ) access to a distribution where either:
These prior results on learning mixtures with restricted mix- ing weights serve as motivation and the starting point of the present work. In particular, the first question we study is:
(Null Hypothesis) D (0,
(Alternative Hypothesis) D is a Gaussian mixture of the form Σie(y) w.N( 1 8ve ). for some unit vector
Is it possible to substantially improve the algorithm of Anderson et al. (2024) to a poly (d, k) time algorithm for parallel pancakes when each wi 2 1/ poly(k)?
E S centers μ4; E I, and weights w, 2 0 for i E [k:]. with Eie(s] W, = 1. That is, D is a k-GMM with collinear centers and variance - 5 along the direction of the centers and 1 in every orthogonal direction.
Our first main result rules out this possibility for SQ algorithms. Specifically, we show in Theorem 1.3 that even when the mixing weights are uniform, any SQ algorithm for such instances requires (logg)) k) complexity. In fact, the lower bound holds even for the more basic task of distin- guishing between a k-GMM from that family and /N0, I).
The goal is to distinguish between the two cases.
Before presenting our first main result, we recall the definition of SQ algorithms. These algorithms,, instead of directly accessing samples, query expectations of bounded functions of the distribution. The SQ model, introduced in (Kearn,, 1998), has since been extensively studied in var- ious contexts (Feldman, 2016). Many supervised learning algorithms,, and several known machine learning techniques are implementable using SQs (Feldman et al., 2017a;b).
Our second question stems from the fact that the algo- rithm in Anderson al. (2024) has complexity ( meaning that single point with arbitrarily small weight (e.g.. 2-k can result in d² complexity.
What is the correct complexity dependence on Wmin for learning k-component parallel pancakes?
Definition 1.2 (STAT Oracle). Let D be a distribu- tion on Rd. A statistical query is a bounded function [ : Rd [-1, 1). Given ʃ and an accuracy parameter T > O, (TAT(() returns a E RR such that |e - E=>D(f(=)] S T.
Specifically, we consider again the testing problem of distinguishing between d-parallel-pancake GMM and (O, I). but where k' S k components can have arbitrary weights while the remaining &- - k' points must have uni- form weights. We show that this mixing weight restriction implies that the testing problem can be solved with time and sample (kz)) +log k) + (log k)/w /Wminn - an inverse-linear dependence on Wmin instead of quasi-polynomial as suggested by the Anderson et al. (2024) result. While this testing upper bound does not imply general learning algorithm A I-GM,, it serves as first step in understanding the nuances of the computational landscape of GMMs with respect to the assumptions on the mixing weights.
Since call to STAT(T) can be simulated in the standard PAC model by averaging 1/7² samples, 7 serves as the SQ model's analog to sample complexity. An information- computation tradcoff in the SQ model states that any SQ algorithm for a given problem must either make a large number of queries or least one query with very fine accu- racy (which informally implies a tradeoff between sample complexity and runtime in the standard PAC model). We are now ready to state our first main result.
Theorem 1.3 (SQ Lower Bound for Uniform Weights). Let C be a sufficiently large absolute constant, k >> C and d z (log k log d)a be integers. If we further restrict the
The technical core for both our main results is to deter-
2

---

On Learning Parallel Pancakes with Mostly Uniform Weights
alternative hypothesis in Problem 1.1 to have wi 1/k for all i E [k], any SQ algorithm requires either 2d queries or at least one query of accuracy d- (-D(log)))
known as a I-design, has been well-studied. Kane (2015) shows that designs of small size match the moments of distribution Q exist when the support of Q is "path- connected".. The design's 's size is upper bounded by the number K, which is defined to be the supremum of the ratio suParx p(x) taken over all degree-1 zero-mean poly- x p(x)] nomials p. Thus, it suffices to show K =20(1) to prove Theorem 1.3. However, since the Gaussian distribution has unbounded support, there are (many) polynomials p where SuPRER p(z) is infinite while the infimum is clearly finite.
Remarks Buhai & Steurer (2023); Anderson et al. (2024) presented an algorithm for solving Problem 1.1 using d'llogk) time and samples (e.g., Theorem 1.1 in the first paper, which was the first to achieve this). Our Theorem 1.3 shows that this complexity is best possible. Notably their work requires the components to be statistically separated, but this is something that we can also ensure by taking 6 sufficiently small (since 8 does not affect the complexity lower bound).
To address this, we can instead consider another distribution Q supported on an interval of length O(Vt), which also matches the first moments with (O, 1) (Lemma 3.3 from Diakonikolas et al. (2017)). Thus, by creating a design to match Q we only need to bound K with X = I, which is now possible (Lemma 3.5). Specifically, by expressing p in the Hermite basis, we can show that supser p(x) I E [ by Gaussian cati-concentration, we can show that any zero-mean polynomial p of degree i has a 2-0(() probability of being less than -2 -2-0(t) 1 This shows that jinfzez p(z)] 2 Eo--:)o.
We now move to our second main result.
Theorem 1.4 (Testing Algorithm for Parallel Pancakes). Consider the version of the parallel pancakes hypothesis testing problem (Problem 1.1), where K' S k of the weights w, in the Gaussian mixture are unconstrained and the re- maining 6-- ke' are assumed to be equal to each other. There is an algorithm for that problem which draws n = O (kkd/))0(k +log(k)) + log(k)) //min) samples (where 5 is as in Problem 1.1 and Wmin mingg kk] wi is the smallest weight), has runtime polynomial in n, d, and it outputs the correct hypothesis with probability at least 0.99.
Additionally,
We can also show that this bound is tight: if A is the uniform distribution on k points, it cannot match more than Ollog k) moments with NV 1). The argument is E.-aI
The algorithm is based on estimating the first OlK' + log k) moment tensors through the empirical tensors, and thus it is also naturally expressible in the SQ model.
that for any non-negative function f. E.-A [(a) S k. If A matches the first 4t moments with No 1). setting fzz = x makes the ratio 20(t), implying t = O(log k).
Remarks A single component with arbitrarily small weight can make the complexity in (Buhai & Steurer, 2023; Anderson et al., 2024) blow up quasipolynomially. By con- trast, our algorithm can handle any number of such points, and the complexity interpolates smoothly between the all- uniform and the fully general weights cases.
In fact, we can extend the result to non-uniform distributions where all but k points in the support have equal weight, showing that such distributions cannot match more than Olog((k) +') moments with (O, 1) (Proposition 4.1). As we will explain later, this will lead to the testing algorithm in Theorem 1.4.
The first step towards Proposition 4.1 is to show that, if all but k'' points have weight at least Wo, then it is impossible to match more than ((log(1/w)) + k') moments with ( 1) (Proposition 4.2). The proof relies on extending the idea of the previous paragraph that any non-negative function f which vanishes (i.e. gives value zero) the k' points in question satisfies Ex=a[f((ri] < 1/wg-- We specifically use E==A
1.2. Overview of Techniques
For Theorem 1.3, it suffices to show existence of a one- dimensional distribution (corresponding the projection along the hidden direction v in the parallel pancakes mixture in Problem 1.1) that matches a lot of moments with (O, 1) and is thus hard to distinguish. Concretely, the goal is to show the existence of a set S C TR. of size such that Exws(z'] = E E. [ for all i = 1,..., t, where I = 2loog k) and x ~ S denotes the uniform distribution on S. Once established, the theorem follows from standard SQ theory: convolving this discrete distribution with narrow Gaussian yields k-GMM B that still matches the first/ f. moments with (0, A standard result from (Diakonikolas et al., 2023) then shows that hiding B along an unknown direction is hard to distinguish from (0,, I).
f(z) = x'p(z), where p(x) = (x - p1)².... (x - )2:)2 and Mi,... Me are the points in the support of A with unrestricted weights. The goal then is to show that the E.-a[f((x)] is at least 20((-k() - combin- ratio r == F=-a(f(=)]= ing this with our earlier lower bound S 1/mg implies = ([og()/wo)+kk)), To bound r, we assume A matches O(1 + R') moments, allowing us to replace Em=a[]] with Ez-A(o,1) in the definition of r. Since p(z) has de- gree 2k', we show p(x) 2 2 2-0(k)) En
Fortunately, the desired moment matching construction,
3

---

On Learning Parallel Pancakes with Mostly Uniform Weights
near x. /21 (Corollary 4.5). The contribution to E Be (x)) from x [0.9v/t, 1.1 will then be at least (3.6t)' (0
expressed as [(x) Eizaayl(x))
Probability Facts The first fact below follows from direct calculations, the second from the Carbery-Wright inequality, and the last from Hölder's inequality combined with Fact 2.3.
(x)]2 ( 0((0) (see Equa- tions (7) and (8) for the full calculations). Mcan- while, by Hölder's inequality, En-Aao..n[f(=)]]] S Bw (230/2/2//8 (0 lx (x)))//3 which by hyper- contractivity is most (2/ (=r-N1oou)((()))1/222000 Combining these bounds establishes r 2 20((-k) and proves Proposition 4.2.
Fact 2.1 (Gaussian Moments).
E x~N(0,1)
[xy] I (t/e) Vt20.
Fact 2.2. For every polynomial of degree and every e 0. Præ-N((01)) (Ip(x)) S <lIpllt) S Orre
We can also argue that the previous paragraph's 's result can
Fact 2.3 (Gaussian Hypercontractivity). 1f'p is a degree r polynomial and k > 2, then l|p|| S (kc - /
always be used with we 2 22-0(k') 1/k (Proposition 4.1). By considering the same polynomial p which vanishes at the points with unconstrained weights, we can combine the hypercontractivity of with the Cauchy-Schwarz inequality to derive a lower bound on the total weight of the equal- weight points: E0244 ii 2 2 O(k),, This immediately implies wo 2 2--0k)/
Fact 2.4. For any polynomial p of degree r.
|l ll 3
Arithmetic Mean-Geometric Mean Inequality We record the following continuous analog of the Arithmetic Mean- Geometric Mean (AM-GM) inequality. We refer to Ap- pendix for a more detailed discussion.
We have shown that any discrete distribution with k' arbitrary weights and k - k' equal weights cannot match more than (log(k) + k') moments with (o, 1). This result extends to approximate moment matching within error 2 (00(9) and holds even after convolving the distribution with a Gaussian (cf. Lemma D.3). For the parallel pancakes testing problem, this implies that for some i S Ollog(k)= + K)) the i-th order tensor of the GMM in the alternative hypothesis differs significantly from that of ( I). This gap can be detected by estimating the tensor via averaging samples (an operation that has complexity (0(m),, leading to the testing algorithm of Theorem 1.4.
Fact 2.5 (Continuous AM-GM Incquality). Let RR +
R be a function, and let I E R be finite interval. If fx) and In (x) are integrable on I, then the following holds: 1 J, (x))2 2 exp ( S,In f(x)dx)
[
Non-Gaussian Component Analysis The parallel pancakes Problem 1.1 a special case of the following problem.
Problem 2.6 (Non-Gaussian Component Analysis (NGCA)). Let B be distribution on R. For unit vector e, we denote by PB. the distribution with the density (B.((z) := Be r))_o(T), where (1o(2) = exp (-I1z the distribution that coincides with B on the direction v and is standard Gaussian in every orthogonal direction. We define the following hypothesis testing problem:
z))ll//2) (ollB/2)((2T)(( /(T i.e.,
2. Preliminaries
We present only the essential preliminaries here; see Appendix B for a full version.
Ho: The data distribution is (0)
Notation We use Z+ for positive integers, Rtt for non- negative reals, and [n] = nI. We use x @ for the tensor product of two vectors. For a random variable following distribution D, we write ~ DD and E[a] for its expectation. The Gaussian distribution with mean μ and covariance Σ is [(,, Σ). and Pr(E') denotes the prob- ability of event E. The indicator function of E is (E)) The Lp norm of an IR-valued random variable x is ||=r||,- ///,, and for a function f : Rd + R. it [l, = (e [xx) We use a S to indicate a S Cb for an absolute constant C independent of a and b.
Hy: The data distribution is PB,e, for some vector E
def
8d-1 in the unit sphere.
It is known that solving Problem 2.6 when B matches the first m moments with (0, 1) requires at least d(((m com- plexity in the statistical query model (Proposition B.8).
3. The Uniform Weights Case
In this section we prove the following proposition, which is sufficient for showing our first result, Theorem 1.3. Proposition 3.1. For each k that is larger than sufficiently large absolute constant, there exists set S of k points in R such that the uniform distribution over S matches the first 2ilog k) moments with (0, 1).
Hermite Analysis In this paper, we use the normalized prob- abilist's 's Hermite polynomials, which form an orthonormal basis of L² := {f 1 (x))) < oo} with respect to the Gaussian measure, i.e., fr hy (x) (x)e =2/2 dx = 2k = m). Every function f E L2 can be uniquely
Given the above, Theorem 1.3 follows directly from stan- dard SQ theory. The details are provided in Appendices B.5
4

---

On Learning Parallel Pancakes with Mostly Uniform Weights
and C, but the steps are summarized as follows: Let A be the uniform distribution on the set S from Proposition 3.1. We can define the distribution B to be what one obtains by first drawing sample from A, rescaling it by 1/Vō and adding Gaussian noise (0, - 6). This operation preserves moment matching and makes Ba a GMM. The NGCA Prob- lem 2.6 with that B then becomes equivalent to the parallel pancakes Problem 1.1. Since B matches m 22 k) moments with (O0 1), its standard SQ hardness state that its complexity is d(lm) d k) (Proposition B.8). We refer to Appendix C for the details of this paragraph.
( p(z) + I p(z)o(2)dx)
=2
Jusplo)<elolii
3 221p|12 smN(0.1)
Pr (p(x) 2 ellplli)
+ +2c|pp11 z~N(0,11)
Pr (p(xx) S <llpll1)
s 221pp|2
Pr (p(x) 2 elIp|la) + 2e pellpli x>1(0,1)
where the first line used that Em--V(o.)(((x))) = 0, the penultimate inequality used the Cauchy-Schwand inequal- ity for the first term and the bound p(x) Σ |l for the second term, and the last line used the Carbery- Wright inequality (Fact 2.2). Rearranging, we obtain Pro=-No.i))Plle > <lp 2 We rename the constant 2C to C.
In the remainder, we focus on proving Proposition 3.1 by leveraging a result on designs theory from Kane (2015). The original result in Kane (2015) highly general and applies to wide range of topological, path-connected design prob- lems. However, as we will only use the theorem for intervals, we present here a specialized version tailored to this case.
1 l|plla (1 - 2Ctel+
2 2|irlla
We now bound K₂ from Fact 3.2 with [=(-CVi.CVV
Fact 3.2 (see Theorem 4 in Kane (2015)). Lett E Z+ be an integer, I C R be an interval and Q be a distribution on I. Let We be the vector space of all polynomials of degree at most t, and Ve be the vector space of polynomials p of degree at most t. with Ex~2(p((x)] = O. Define sup,ci p(ar)
Lemma 3.5. Let t >> C be integer, where C is suf- ficiently large constant, and define I= --I-Cvi++CVl For every polynomial p of degree at most t with Ee-N((o,)/((=])]] 0 it holds sup=cip(c) [illet P(a) < 20(0.
K, SUP Tintzer p( Then for every integer n > - (t- + 1) there exists a set S C I of n points such that [ST Exesp(x) = E (v(w:) for all p E W.
Proof. It suffices to upper bound the numerator by Iplla and lower bound the denominator by 2 2-000))l)) [pll1.
Our goal is to show that K₁- 20()) for Q which would directly imply Theorem 1.3. However, as noted in Section 1.2 1.2, K₂ may be infinite when J = R.. To address this, we use distribution Q supported on bounded interval of R that matches the first t moments of (0, 1). Applying Fact 3.2 with this Q also suffices for establish Theorem 1.3.
1).
Upper bound on numerator We require the following:
Fact 3.6 (Krasikov (2004)). For the k-th normal- ized probabilist's Hermite polynomial hi, we have supaER (((z))==*() O(K-1/6).
Consider polynomial p which has degree at most t and satisfies (o.)((()))pp()))) O. We first expand the poly- nomial in the Hermite basis: p(x) = Σi (ghx(r), where the summation starts from k because do E2- [x(x)) 0. For any T we have (the first step uses Cauchy-Schwar Schwarz inequality):
Lemma 3.3 (Gaussian Quadrature (Lemma 4.3 in Di- akonikolas et al. (2017))). There is a discrete distribution Q on the real line, supported on L points, that agrees with (O, 1) on the first 2t- moments. All points x in the support of Q have [x|| O(vi).
We start with an anti-concentration property of Gaussian polynomials that will be useful for bounding the numerator in the definition of K,
Ip(x)] =
Σ a (x))(z)
S
a
12(x))
k=1
Lemma 3.4. Let C' be a sufficiently large constant. For every polynomial R > IK of degree at most t with (o.(o,)))p(()) = 0 and for every > it holds
< |llllz
Σ
2x2
22//2/21//
(by Fact 3.6)
k=1
(1
||P|l (Ileell (1- Ctel+1/t)?
Pr (p(x) > <lpl)1) 2 2~110.1)
< |1l112 2010)
k 1/6 --/6
(using |z|| = O(vk)
2 lpllz
< |lel22 2010)001)
(using Eken 1166 = (0(1)
Proof. Denote by o(z) the pdf of (0, 1). We have the following (each step is explained below):
< ||e||2 2010
< 200) (using Fact 2.4)
|Pl| = ((())((2)dx - ((x))(=)dr== = ff(x)
Lower bound on the denominator From Lemma 3.4 with
p(m)20 p(a)50
5

---

On Learning Parallel Pancakes with Mostly Uniform Weights
-p in place of p and = 2_ and Fact 2.4 we get that
We just showed that there is polynomial p of de- gree at most m = Ollo((k) + k',, where the expec- tations under B and .N 1) differ significantly: À := Eg-B [p(x]] - En-N(o,)) 1) [|] > (5/2)Cm. An averag- ing argument further implies that a gap holds even for some monomial x². Lifting this to the d-dimensional parallel pancakes, we have the moment tensor gap E [r E Eg~A((,)) =
1 1plla (1
2 (1-C12
)²
Pr (p(x) < --2-(1el(l)) 2 (0,1)
2
1ppl12
3/3 ( (1 C12 -12)
2
2 4t
where we used that t is big enough so that C 2 <0.5. Then,
The Frobenius norm of the gap is À > (8/2)cm, implying that between the (expected) moment tensors, at least one en- try differs by at least := A/d" = (d/ 8)(C)Cmm We will test by searching for such an entry in the empirical tensor.
Pr (p(x) < -2 -1p'1lp,,,,, E z0.10.1)
2 Pr (p(x) < (2-11p))) - Pr (x II) x=
(0,1)
2 2 -2 2- 1001 > 00,
Algorithm Testing Algorithm (simplified)
+CVB where in the last line we used that / -CV for large constant C. We have thus shown that inf p(x)= I -p-lll and therefore infzer p(x) > 2-ll--
1: Input: n. Output: H E {Ho, H1}.
2: For = 1,2,3...... C (log(A) + +') do
0
3: Draw IT,, In ~ D.
Define M s 1 - 2
4. The Mostly Equal Weights Case
n Define M' ;- EE-N(u.n)
6: If ar==011,....
such that |Ma 1Ma-MM MMa > Cm Cm
This section focuses on Theorem 1.4 and is organized as fol- lows. The key structural result is the following impossibility of moment matching: if A is a distribution on k points, with k' points having unconstrained weights and the remaining ks k' equal, then A cannot match more than Oloog k + k') moments with the standard Gaussian.
7:
then Output H1 and terminate.
8:
Return Ho.
The tester above is simplified version. However, it is not fully correct, as we must ensure the concentration of the empirical tensor to bound the sample complexity. The Gaussian (0, I)'s empirical tensor is well-concentrated. While the parallel pancake's is tensor might not concentrate well, this happens only when there is a Gaussian component much farther than vd from the origin - otherwise every sample from the parallel pancake is within O(Vd) in norm in high probability, and the empirical tensor is entrywise well-concentrated (e.g. by Hoeffding). This is also testable condition: with >> log(k)/vur Wmin samples, we will be able to check if every component is centered at most O(vd) from the origin. The full version of the algorithm with this additional preliminary check, along with its correctness proof, are provided in Appendix D.I.
Proposition 4.1. Let k' < k be positive integers, and let A be a discrete distribution on k points in R. Suppose k- Kk of the points have equal probability masses, while the remain- ing k points have unrestricted probability masses. Denote by m the highest degree for which every degree-m' < m polynomial g satisfies |E [g]=)]] (0- [x(]]] <
2 C-m [g]] l, then m must satisfy < O(log k) + O(K).
Section 4.1 explains how Proposition 4.1 leads to testing algorithm (the full proof appears in Appendix D.1). Section 4.2 provides the proof of Proposition 4.1.
4.1. Proof Sketch of Theorem 1.4
4.2. Proof of Proposition 4.1
Consider the parallel pancakes problem from Theo- rem 1.4, which is equivalent to the NGCA problem (Prob- lem 2.6) with the 1-d GMM B- = Σie(M waN(u, 1-8). If B approximately matches m moments of ( 1), we aim to show that mg0 k+kk), enabling a testing algorithm that detects significant deviations in moment tensors. Specifically, suppose every polynomial p of degree m'mm with ||a||==1 satis- fies EEzzB [===)pp(=)]- Em-,No.,))(()))) 5(5/2)Cm for some large constant C > 1. Now, consider the discrete distribu- tion A, which assigns weight w. to each center ui/Vō, By Lemma D.3, A also approximately matches the moments of (0, 1). but with an error of 2 O(m) instead of (6/2)((m) Then Proposition 4.1 yields m S Ollog k+ as desired.
We now show Proposition 4.1. We will actually show a slightly different version below, where k' of the points have arbitrary weights and the rest have weight at least wo-
Proposition 4.2. Let C be sufficiently large constant, and ler k'' < k be positive integers. Let A be discrete distribu- tion on k points in IR with probability masses W1.-.., Wke where w; 2 wo for = Wk' + 1,....k .k (i.e., the last l- k- k weights are lower bounded by wi, while the first k' weights are unrestricted). Let m be the largest degree such that every polynomial g of degree ml E m satisfies
E [g(x)] - A~A
E
[o(x)]
swo 2 3---mllgll (1)
x~
6

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Then m S O(log(1/wo)) O(K).
Next, we can combine this with Equation (4), divide both sides by Ez- (x p(x)) (and use Σ -i- wi S 1) to
Proposition 4.1 can be derived from this via the fol- lowing observation (shown in Appendix D.2): in the setting of Proposition 4.2, let p(x) where M1...., PRk are the points in the support of A with the unconstrained weights. Then, the weights of the - k' points with uniform weights is always iell
obtain the following, where À := 2 C(2++4));
[ - (a),
E 1(0.) (22
1
1 E 1V-.. [x'p(x))]
wo
+ x² BenN(O.1) [T22 (1))
E E [x(p(x)]
[ [x)))
Di=K++ wa 2 E=~A[T(1]]] Ipll 2 3-22', where the first step uses Cauchy-Schwarz inequality, the second uses the (approximate) moment matching, and the third is a consequence of Gaussian hypercontracttvity (Fact 2.4). This means that every such weight is w; 2 3 3-22' /k; which when plugged into Proposition 4.2 gives Proposition 4.1.
E==A(p(x))
E [x(p(z))]
+X
Let us simplify this inequality. Let r be the ratio on the LHS. The second term on the RHS is X² The third term is at most 3(22k' Xr, by applying Gaussian hypercon- tractivity (Fact 2.3) to the polynomial x' z'p(z). Thus, the inequality becomes r(1 - X² - A3 2 1/wβ- Since A = 2 ((2(+-4k)) for large constant C, the expression inside the parentheses is greater than 0.5. Therefore, the inequality implies that S 1/w6.
We now focus on showing Proposition 4.2. We will follow a top-down presentation, starting with the proof strategy and concluding with a derivation of the necessary bounds.
We will use a reparameterization m = 2t + 4k' with even. The goal is to show that if A is assumed to approximately match the first (in the sense of Equation (1)), then & must be at most (log(1/w0)) + k'). Let ,I...., Ph be the points on which A is supported, where the first k' points are the ones with the unrestricted weights, and consider the polynomial f(x) = r'p(z), where p(z) = (a (x) 2 (z- (2. The proof strategy is the following: if the expectation of
The next step is to establish a lower bound for r, specifi- cally to show that 2 20(1) /20(k). If this can be done, combining the two bounds 22(() /20(k) < 1/w/ and taking logarithms yields f = (log (1/w))) + Okk), completing the proof of Proposition 4.2.
2t + 4k' moments with (O, 1)
4.2.1. LOWER BOUNDING THE RATIO
We want to establish the following, which was the missing piece in the proof of Proposition 4.2 above.
under A approximately matches that of N (0, 1), then the value of f on every point μ4 cannot be too large, which will cause the expectations of f² to deviate.
Lemma 4.3. Let p: IR - R be polynomial of the form p(x) = (xr )1) - 122 ... (ar mw.) Then
Because of Equation (1) with g(x) = (x) we have:
E E.-A(0.1) [x px())
20(())
2 20(R)
E ( [x'p(z))]
Σ
wi p(us) E [x'p(x)]
and
i=++1
The most difficult part involves lower bounding the numera- tor. To this end, we will show the following bound:
1<'p(t)]l
[x(p(x)] + wo 20(24448))
(3)
z=N(0.1)
Lemma 4.4. Let p IR + IR be a polynomial of the form p(z) = (z-p1) μ2) .... (x pk) where . Pig R. and define 1 == 10.9/2t 121 For every t> > 0 and for every (1, ,l,...., puk E IR the following holds:
This, together with the lower bound w; 2 wp for the points i = k' +1, +l..... A and the fact that / is even, implies that for all i = k' ++1. +,,..., k it holds
p(p))) S
1 E wo 1-11111)
[<'p(x)]+ +
|=(p(x)]l2 20(2(+48)) + (4)
1 / ZET exp (
In lo(()dd
>
Ip())) DER:UlISV 20(K)
max
(5)
We will actually apply Lemma 4.4 after taking expectations of both sides. This version is presented below, and its proof follows by taking expectations and performing some manip- ulations (see Appendix D.3 for a detailed proof).
We now examine the expectations of the square of f(x).
Because of Equation (1) with g(z) = (z), we have
21 p² (r)] + 1 2 (x)
2220 p² (x)]
<
E ANA
(0,1)
20(2++48))
Corollary 4.5. Let p: RR + R be a polynomial of the form p(x) = (x- u2) ... (x- pw)) where μi, , Mk
1 (x) (x)1l
Σ Wi (ni
+
R are arbitrary parameters. Define I = [0.9 2t, 1.1 2t)
20(2++16)
For all I. 2 1 we have exp (1n Seer In lx(x)dxx) > 20125
i=#41
7

---

On Learning Parallel Pancakes with Mostly Uniform Weights
To why the above bound is needed to prove Lemma 4.3, we will first prove Lemma 4.3 assuming Corollary 4.5. Then, we will prove Lemma 4.4.
Proof of Lemma 4.4. Fix arbitrary y E Ik with lvl s vl. First, note that by the property of logarithms and sums, can write the left hand side as
k'
Proof of Lemma 4.3. First, for the denominator, we have the following:
exp Σ
In us/dx 221
E
2 p(x)]
E
(x))
E (0.1)
I
////////
x0,1
x0.1
In order to show Equation (5), it suffices to work with each term and show the following for each E [k']:
< lpPls
3t
1/2
2
lplz
3t
1/2
(6)
2e
2e
1 [ / ma p4l 0(1)
where the first step uses Hölder's inequality, the second step uses the Gaussian moments bound (Fact 2.1), and the final step uses Gaussian hypercontractivity (Fact 2.3).
Equivalently, it suffices to show that Equation (5) holds for every linear polynomial of the form p(x) = x a. Therefore, the goal for the rest of this proof is to show that
We now lower bound the numerator. Define T := [0.9v/t, 1.]. We have the following (see below for explanations of each step):
exp (in See In |z aldr) 2 ly al/O(1) (9)
JZEI
E (0.1)
I
21 (x))
2
1 2 -22
(2²) dr
holds for every E R and E R with /v S Vt. We will examine two cases.
21 e- 12 dx
xEI
The first case is when the root a of the polynomial is outside the interval 1. In this case, we can show that Jx al/ly allllyya al (1), which implies in |ar - al 2 In ly al O11), and the desired conclusion (Fquation (9)) follows by integrating both sides and applying the exp(-) function.
Case 1
2 (1.621)e -0.814 [ p²x) dx
Jxer
=(1.221'' -0.81171 (000))0-000111 (i
p² (c))dr)
WEI
(
S
To show the earlier claim that Jæ al/ly al O(1), we can consider the following sub-cases:
R (1.621)& 0.811 -
(x)
(7)
DEL
1. Case a 2 1.1/2t (i.e., a is to the right I): Suppose 1.1/2t++ for some non-negative Then, a-r y) (LL//t-z)++u 0(vt)+ +u and a a- y-y- = (1.1v2t- Therefore, for any u 2 0, the ratio | lr-a//lu - al (0(vl) + w) + (1).
where the third inequality uses that minger e 22
(1.62t) (1.62t)(c-0.811 0.811, and the final inequality uses that [7] 0.2v21 ((1). We now focus the root mean square term ग ('r)) dæ, which we will bound using the AM- GM inequality (Fact 2.5) and the geometric mean bound from Lemma 4.4. The first step below applies Fact 2.5 with :=>>;=)),,
2. The cases a -Vi and [Vī, 0.9v can be shown in similar manner.
f(z) == (z)), and the next step uses Corollary 4.5.
2 ||r|l3 / (z) dr exp [ In (p(x)) dr) [4] 2
Suppose that the root of the polynomial p lies within the interval I. In that case, we show via derivative analysis that f'a) := 지 S In [x |r- al dæ for a E I is min- imized at the midpoint of I, i.e., at a v2f, and confirm that /( /(221) 2 vi/20 = 2(1y al). These calculations are provided in Appendix D.3.
Case 2
20(6))
Combining with Equation (7), we obtain the following bound for the numerator:
2t px)) 2 (1.62t)' 0.81I 1Irl12
E (0.1)
(8)
20(²))
Conclusions and Future Work
Combining Equation (6) and Equation (8), we conclude
Our work makes progress in understanding the complexity of learning parallel pancake GMMs, in terms of both lower and upper bounds. We establish the tightness of cxisting algorithms for uniform weights and provide an improved testing algorithm for uneven weights. number of interest- ing open problems remain:
Ex-A(o.) 202''' (x))
(1.62)*
(1.3)*
Gos E [x'p(x))) (..1 2013) -00K3 J
We conclude this section by proving Lemma 4.4.
8

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Can extend our testing algorithm learning the known direction of the parallel pancakes? More broadly, can we characterize the complexity of learning GMMs with common covariance and not necessarily collinear means as function of the weights distribution?
Belkin, M. and Sinha, K. Polynomial learning of distribution families. SIAM Journal on Computing. 44(4):889-911, 2015.
Bogachev, V. Gaussian Measures. 1998.
Can we obtain an algorithm with polasi-polyoomiall (i.e., (p(log(1/wmmm)) complexity for GMMs whose components have unknown (and potentially different) covariances?
Brubaker, S. C. and Vempala, S. Isotropic pea and affine- invariant clustering. Building Bridges: Between Mathe- matics and Computer Science, pp.
2008.
Impact Statement
Bruna, J., Regev, O., Song, M. J., and Tang, Y. Continuous LWE. In Symposium Theory of Computing (STOC), 2021.
This work is theoretical in nature and focuses advanc- ing fundamental knowledge. As such, it does not directly raise any societal or ethical concerns that warrant special consideration.
Buhai, R. and Steurer, D. Beyond parallel pancakes: Quasi- polynomial time guarantees for non-spherical gaussian mixtures. In The Thirty Sixth Annual Conference Learning Theory, pp. 548-611. PMLR, 2023.
Acknowledgments
Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. Daniel M. Kane was supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). The work of Jasper C.H. Lee was done in part while he was at UW Madison, supported by NSF Medium Award CCF-2107079.
Carbery, A. and Wright, J. Distributional and 1 norm in- equalities for polynomials over convex bodies in R". Mathematical Research Letters, 8(3):233-248, 2001. ISSN 10732780, 1945001X. doi: 10.4310/ML.2000L..... n3.al.
Dasgupta, S. Learning mixtures of gaussians. In Founda- tions of Computer Science (FOCS), 1999.
References
Daskalakis, C. and Kamath, G. Faster and sample near- optimal algorithms for proper learning mixtures of gaus- sians. Conference on Learning Theory, pp. 1183-1213. PMLR, 2014.
Achlioptas, D. and McSherry, On spectral learning of mixtures of distributions. In Proc. 18th Annual Confer- ence on Learning Theory (COLT), 2005.
Anderson, P., Bafna, M., Buhai, R. D., Kothari, P. K., and Steurer, D. Dimension reduction via sum-of- -f-uarrsss and improved clustering algorithms for non-spherical mix- tures. arXiv preprint arXiv:2411.12453 2024.
Diakonikolas, I. and Kane, D. M. Implicit high-order mo- ment tensor estimation and learning latent variable mod- els. arXiv preprint arXiv:2411.
2024.
Diakonikolas, I,, Kane, D. M., and Stewart, A. Statisti- cal query lower bounds for robust estimation of high- dimensional gaussians and gaussian mixtures. In Proc. 58th IEEE Symposium Foundations of Computer Sci- ence (FOCS), 2017. doi: TLL.////OCS.00......
Andrews, G. E., Askey, R., and Roy, R. Special Functions. 1999.
Arora, S. and Kannan, R. Learning mixtures of arbitrary Gaussians. In Proc. 33rd Annual ACM Symposium Theory of Computing (STOC), 2001.
Diakonikolas, I., Hopkins, S. B., Kane, D., and Karmalkar, S. Robustly learning any clusterable mixture of gaussians. urXiv:2005.06417 2020.
Bakshi, A. and Kothari, P. K. Outlier-robust clustering of non non-spherical mixtures. arXiv:2005.0299 02970, 2020.
Bakshi, A., Diakonikolas, I., Hopkins, S. B., Kane, D., Kar- malkar, S., and Kothari, K. Outlier-robust clustering of gaussians and other non-spherical mixtures. In Founda- tions of Computer Science (FOCS), 2020.
Diakonikolas, I., Kane, D. M.. Kongsgaard, D., Li, J., and Tian, K. Clustering mixture models in almost-lines linear time via list-decodable mean estimation. In Proc. 54th Annual ACM Symposium on Theory of Computing (STOC), 2022.
Bakshi, A., Diakonikolas, I., Jia, H., Kane, D. M., Kothari, P. K., and Vempala, S. S. Robustly learning mixtures of k arbitrary gaussians. In Proceedings of the 54th An- mual ACM SIGACT Symposium on Theory of Computing (STOC 2022), 2022. Also available arXiv:2012.0211
Diakonikolas, I., Kane, D., Ren, L., and Sun, Y. Sq lower bounds for non non- ganssaassian component analysis with weaker assumptions. Advances Neural Information Processing Systems, 2023.

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Diakonikolas, I., Karmalkar, S., Pang. S., and Potechin, A. Sum-of-squares lower bounds for non-gaussian compo- nent analysis. In 2024 IEEE 65th Annual Symposium Foundations of Computer Science (FOCS), pp. 949-958. IEEE, 2024.
Krasikov, New bounds the Hermite polynomials. arXiv preprint math/04013 10, 2004.
Lindsay, B. Mixture models: theory, geometry and applica-
tions. Institute for Mathematical Statistics, 1995.
Liu, A. and Li, J. Clustering mixtures with almost opti- mal separation in polynomial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1248-122 1261, 2022.
Feldman, V. Statistical query learning. In Encyclopedia of Algorithms, pp. 2090-2095. Springer New York, 2016.
Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S., and Xiao, Y. Statistical algorithms and lower bound for detecting planted cliques. Journal of the ACM, 64(2), 2017a. doi: 10.1 145/3046674.
Liu, A. and Moitra, A. Settling the robust learnability of mixtures of gaussians. In Proceedings of the 53rd An- nual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 518-531, 2021.
Feldman, V., Guzman, C., and Vempala, S. S. Statistical query algorithms for mean vector estimation and stochas- tic convex optimization. 2017b.
Liu, A. and Moitra, A. Learning gmms with nearly optimal robustness guarantees. In Proc. 35th Annual Conference on Learning Theory (COLT), 2022.
Garefa- Parefa-Escudero, L., Gordaliza, A., Matrán, C., and Mayo- Iscar, A. A review of robust clustering methods. Advances in Data Analysis and Classification, 4(2):89-109, 2010. doi: 10.1007/s 1334-100-006-52
Moitra, A. and Valiant, G. Settling the polynomial learnabil- ity of mixtures of gaussians. In Proceedings of the S1st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 93-102, 2010.
Gupte, A., Vafa, N., and Vaikuntanathan, V. Continuous LWE is as hard as LWE & applications to learning gaus- sian mixtures. CoRR, abs/2204.02550, 2022.
Nelson, E. The free markoff field. Journal of Functional Analysis, 1973.
Hardt, M. and Price, Tight bounds for learning a mixture of two gaussians. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pp- 753-760, 2015.
O'Donnell, R. Analysis of Boolean Functions. 2014.
Pearson, K. Contributions to the mathematical theory of evo- lution. Philosophical Transactions of the Royal Society of London. Series A, 185:71-110, 1894.
Hopkins, S. B. and J. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th An- nual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1021-1034, 2018.
Suresh, A. T., Orlitsky, A., Acharya, J., and Jafarpour, A. Near Near-optimal paan-opt--l--amplle estimators for spherical gaussian mixtures. Advances in Neural Information Processing Systems, 2014.
Kane, D. Small designs for path-connected spaces and path-connected homogeneous spaces. Transactions of the American Mathematical Society, 2015.
Szegö, G. Orthogonal Polynomials, volume XXIII of American Mathematical Society Colloquium Publications. American Mathematical Society, 1989.
Kannan, R., Salmasian, H., and Vempala, S. The spectral method for general mixture models. In Proc. 18th Annual Conference on Learning Theory (COLT), 2005.
Titterington, D., Smith, A., and Makov, U. Statistical Anal- ysis of Finite Mixture Distributions. Wiley, New York, 1985.
Kearns, M. J. Efficient noise-tolerant learning from sta- tistical queries. Journal of the ACM, 1566),983- 1998.
Vempala, and Wang. G. A spectral algorithm for learning mixtures of distributions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 113-122, 2002.
Kothari, P. K. and Steurer, D. Outlier-robust moment- estimation via sum-of-squares. arXiv preprint 1711. 2017.
Kothari, P. K., Steinhardt, J., and Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1035-1046, 2018.
10

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Supplementary Material
Organization Appendix discusses additional related work on Gaussian mixture models, Appendix provides the full version of the preliminaries needed for the technical proofs, Appendix C provides the missing details from the proof of our first main result, Theorem 1.3, and Appendix provides the missing details from our second main result, Theorem 1.4.
A. Additional Related Work
Learning Gaussian Mixture Models (GMMs) is one of the most studied problems in statistics, dating back to Pearson (1894). Over the years, a plethora of works has explored this area (Dasgupta, 1999; Arora & Kannan, 2001; Vempala & Wang. 2002; Achlioptas & McSherry, 2005; Kannan et al., 2005; Brubaker & Vempala, 2008; Moitra & Valiant, 2010; Belkin & Sinha, 2015; Suresh et al., 2014; Daskalakis & Kamath, 2014; Hardt & Price, 2015; Diakonikolas al., 2020; Bakshi et al.,
2020; Diakonikolas et al., 2022; Liu & Moitra, 2021; Bakshi et al., 2022). Here, we provide a brief exposition of part of this literature, though this is not comprchensive survey.
A key starting point was Dasgupta (1999), which studied learning GMMs with well-separated, spherical covariance components. Subsequent work by Vempala & Wang (2002); Achlioptas & McSherry (2005); Kannan et al. (2005) improved the separation condition to be dimension-in mameessoonnddeeenddnnt Hopkins & Li (2018) and Kothari et al. (2018) later refined the separation assumption to the information- theoretic limit, achieving this with quasi posesippoynomiil-ttee timee algorithms. Notably, most of the aforementioned works extend beyond spherical Gaussians: however, they measure the pairwise mean separation between components relative to the largest eigenvalue of the components' covariance matrices. More recently, Liu & Li (2022) improved the runtime to polynomial for spherical Gaussians.
The case of arbitrary Gaussians with unknown component covariances has also been extensively studied (Belkin & Sinha, 2015; Moitra & Valiant, 2010; Bakshi & Kothari, 2020; Diakonikolas et al., 2020; Liu & Moitra, 2022; Bakshi et al., 2022). While the first works in this list had complexities doubly exponential in k, the number of components, the most recent have reduced this to d((k), As noted in Section I, hardness results from Diakonikolas et al. (2017); Bruna et al. (2021); Gupte al. (2022) showed this complexity is necessary. However, certain special cases of GMMs can eircumvent these lower bounds. This was the focus of Buhai & Steurer (2023) and Anderson al. (2024), who studied GMMs with minimum mixing weight Wiin 2 1/ poly(k) and unknown but shared covariance across components. These papers motivated us to study whether further improvements are possible for this family of GMMs.
B. Additional Preliminaries
B.I. Notation
We use Σ+ to denote positive integers. For E Z4 we denote [n] def .I.....n.. We denote by EF the set of all non-negative positive real numbers. We denote by exp(x) = ex the exponential function, and by In(x)) the natural logarithm (the logarithm with base e). We write x y to denote the tensor product between two vectors y. The tensor product of two vectors u E IRm and E IR" is a matrix 8 v E m defined such that (u @ v)1j Uyyy, where each entry is the product of the corresponding components of u and v. This can be extended to product between more than two vectors. We denote go the f-lfld tensor product of the vector x with itself. If A is a tensor, ||A|||: denotes its Frobenius norm, which is the Euclidean norm of the vector obtained by stacking all entries of the tensor into a single vector. We write x ~ D for a random variable x following the distribution DD and use E[r] for its expectation. We use N(4, Σ) to denote the Gaussian distribution with mean i and covariance matrix Σ. We write Pr(E) for the probability of an event E. We denote by 1()) the indicator function of the event E. The Lp norm of (R- (alveled)) random variable is defined to be ||æ|||p El /p, The Lp norm of function f R + R. is defined to be the I,p norm of the random variable fxx i.e., I|5l = ( (z)))))
We use a S 6 to denote that there exists an absolute universal constant C > 0 (independent of the variables or parameters on which a and b depend) such that a S Cb. Sometimes, we will also use the (()), notation with the standard meaning.
B.2. Hermite Analysis
Hermite polynomials form a complete orthogonal basis of the vector space (R, 1)) of all functions f R + R such that |x>=)),))//x))) < oo. We will use the normalized probubilist's 's Hermite polynomials, which have unit norm

---

On Learning Parallel Pancakes with Mostly Uniform Weights
and are pairwise orthogonal with respect the Gaussian measure, i.e., Sg (2) /2 2 m). These polynomials the ones obtained by Gram-Schmidt orthonormalization of the basis 11, with respect the inner product (f, () := B==-wo..n[((r)((zx) Every function f E (2 1)) can be uniquely written as f(z) = مi= (z) and we have lim Ex=NNo..)(((2))) - -i= azh,(x)) 0 (see Andrews et al. (1999) for more detailed exposition of Hermite polynomial's properties). We have the following closed form formula (see, e.g., Szegö
(1989)):
[n/2|
(-1) j-0 j!(n
(x) vn!
Σ
2j) 2=
(10)
We will use the following fact, stating that the largest coefficient in the above expansion cannot be too large. Fact B.1 (Upper Bound on Hermite Polynomial Coefficients). Let (x) denote the normalized probabilist's Hermite polynomial of order n. In the monomial expansion (x) ش5=1 a,ar), it holds |az S 20()) for all j E [n]].
Proof. This follows by Equation (10). The j-th coefficient is VVn((11///IC) 2/)12)) S vnt/(ii(n 2f)12'). Then
one can use the elementary inequalities e(k/e)* < k! S ek(k/e)* to bound the factorials that appear in the numerator and denominator and optimize the resulting function. The derivative analysis of the resulting function gives two points of zero derivative: 1 (1 2n /I + 4n) and j = (1 + 2n vI + 4n). For each point, can be checked that the function is smaller than 2 in the limit n oc.
Operator). For a p [-1, 1]. we define the Ornstein- Uhlenbeck (or Gaussian noise) operator Up as the operator that maps a distribution F on IR to the distribution of the random variable pX + /1-+v111pp p2 where ~ and Z (0, independently of X.
Definition B.2
Ornstein-Uhlenbeck
A well-known property of Ormstein-Uhlenbeek operator is that it operates diagonally with respect to Hermite polynomials.
Fact B.3 (see, e.g., O'Donnell (2014)). For any normalized Hermite polynomial h,, any distribution F on R, and 5 E [-1, it holds that Ex~U,F [X)] = p² (xx))
B.3. Properties of Polynomials Under the Gaussian Measure
Fact 2.1 (Gaussian Moments).
E
[x'] S (t/e)//2 Vt20.
2=NN(0,1)
Fact B.4 (Carbery-Wi) Wright Inequality (Carbery& & Wright, 2001)). There is an absolute constant C such that the following holds. Let E B μ E Red E E RRdxd such that E is symmetric PSD and p: Rd + R be a multivariate polynomial of degree at most r. Then
Pr (()))))>>)0 (=N()N))
(En>A(()))) [1<(2))s/7))1//
The way that we will apply this is with the following choice of parameters: 1, -, 1.9 1,g=r =r and y >< <(p/|1, where e is new parameter. This gives: Fact 2.2. For every polynomial of degree and every c > 0, Pra- (Ip(=)) < <lIpll)) ) S (O(r!)r)
The following inequality can be easily derived using Hölder's 's inequality. Fact B.5. ||0||a < || ||=
2/3 for any random variable.
The following inequality is the Gaussian Hypercontractivity property (see, e.g., Bogachev (1998); Nelson (1973)) Fact 2.3 (Gaussian Hypercontractivity). If is degree r polynomial and > 2, then ||]| I (I - 1)r/2 |pl12
In particular we will use the above in the following way: П|l|
Fact 2.4. For any polynomial p of degree r, |
> 3
12

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Proof. lIplla 2
Ipll
lllll
|Illla [Iella
2
3 "lp 12, where the first step used Fact B.5 and the last step used Gaussian
lell
Hypercontractivtiy (Fact 2.3) with le
4. Rearranging completes the proof.
Fact B.6 (Gaussian Norm Concentration). If ~ N (1e, 1), with probubility 1 - T we have that
||||| - (Iul) + (d)))(+d)) x log + + (vd+ + (1uel) v 1108= -
1
B.4. Arithmetic Mean-Geometric Mean Inequality
In this paper, we will use a continuous analog of the Arithmetic Ceca-Geemettric Mean (AM-GM) inequality. The continuous analog for the arithmetic mean of a sequence ! > is what one obtains by replacing the summation with its continuous counterpart. Specifically, the arithmetic mean of a function f IR + IR over an interval 7 is defined as: (1/) J, (x))x.
The geometric mean of a discrete sequence is Ih= z. Its generalization relies on the property that In IT== 1/"
1/" x > In W; (assuming v; > 0). By replacing the summation with an integral, the generalization of the geometric mean of a function f over an interval is: exp (in Sj In f())dx) The continuous analog of the AM-GM inequality thus is the following statement. The proof follows directly from Jensen's 's inequality:
Fact 2.5 (Continuous AM-GM Inequality). Let f R - BI be a function, and let I S R be a finite interval. If fx) and In (x) are integrable on I, then the the following holds: J ((x)dr 2 exp ( S₁ In f(x)dx).
B.5. Statistical Query Lower Bounds Background
We first restate the definition of the non- nan-Gassiian component analysis (NGCA) hypothesis testing problem.
Problem 2.6 Non--aussian Component Analysis (NGCA)). Let B be a distribution on R. For a unit vec- tor V. we denote by PB.. the distribution with the density (B,0(z) == B(v x))1.(z), where ΦIv(T) = exp (-I1æ- - (uTx)) (=x>el///22) ((2m))(-1)/2 i.e., the distribution that coincides with B on the direction v and is standard Gaussian in every orthogonal direction. We define the following hypothesis testing problem:
Ho: The data distribution is (O)
H1: The data distribution is PR.v, for some vector Sd-1 in the unit sphere.
Condition B.7 (Approximate moment matching). Let m E Zμ. The distribution B on F is such that Eg [x''
1g [x']] S v for all i [m].
known result is that the NGCA problem of Problem 2.6 is hard in the SQ model if B matches of moments with the standard Gaussian. This was shown in (Diakonikolas al., 2017) and later strengthened in Diakonikolas et al. (2023). The following is Theorem 1.5 in Diakonikolas et al. (2023) using À 1/2 and c (1 A)/8 1/16.
Proposition B.8 (Thcorem 1.5 Diakonikolas et al. (2023)). Let d, m be positive integers with d 2 lml d)?. Any SQ algorithm that solves Problem 2.6 for a distribution B satisfying Condition B.7 requires either ( many queries or at least one query with accuracy d/16 + (1 + o(L)),.
C. Omitted Details from Section 3
We restate and prove Theorem 1.3.
Theorem 1.3 (SQ Lower Bound for Uniform Weights). Let C be a sufficiently large absolute constant, > C and 2 (log k log d)2 be integers. If we further restrict the alternative hypothesis in Problem 1.1 to have w, = 1/k all i [k). any SQ algorithm requires either 20) queries or at least one query of accuracy d d'l(log)) k)
Proof. Let S be the set from Proposition 4.2 and A be the uniform distribution on S. That is, A is a discrete distribution supported on ls points and is guaranteed to match the first m 2(log k) moments with ( 1). Let B U be the distribution which obtained by applying the Ornstein- Uhlenneckhhhkkkkk operator (Definition B.2) with v8. Then B is a
13

---

On Learning Parallel Pancakes with Mostly Uniform Weights
k-GMM with uniform weights and variance 6 for each component. Moreover, for every L 0, 1,,,,,, m we have the following for the i-th Hermite polynomial
E ge [1,[
=
E Z~U,A
[x)=)
p' E a>
hx(=)]= =
E x-.((.1))
[h,(T)]
(11)
where the above uses Fact B.3 and the moment matching property of A. Since E 1 [h)( for 0 and 1 [xx] for all i >> Equation (11) means that (g-B(/((x)] ((, (x)], i.e. B matches the first moments with (0,
An application of Proposition B.8 with v = 0 shows that the NGCA Problem 2.6 that uses the distribution B from above has SQ complexity ( Noting that this problem is equivalent to Problem 1.1 completes the proof of Theorem 1.3.
We conclude by addressing an edge case. The proof above implicitly assumes that the set contains distinct points (as otherwise, the weights in the corresponding GMM might not all be exactly 1/k). Here, we argue that Theorem 1.3 still holds even if S contains duplicates. Specifically, one can perturb each point in S by most an arbitrarily small amount A, ensuring that the points become distinct and that the moments in the resulting GMM distribution B are being matched up to an error of rather than exactly (note that for any y can find perturbation that the moment gap is more than v). The SQ lower bound from Proposition B.8 then implies that we either require 2 queries or least one query with accuracy d- mm16 (1 o()))v. By choosing A appropriately small, ensure that d d-m/16
D. Omitted Details from Section 4
D.I. Omitted Details from Section 4.1
The lemma below shows that if the approximate momement matching condition violated, then it has to be violated by a monomial (up to small deterioration of parameters).
Lemma D.1. Let C be a sufficiently large absolute constant. If there exists a polynomial g R - R of degree r and unit norm (Ex= 1) such that
E m
[g(2)]
E [g(z)]
(0,10
then there exists monomial xf with i for which
E A~A
E (0.))
[x*]]
> 2 c-r.
Proof. We will show this by contradiction. Suppose that every monomial of degree S r satisfies E [xr] Ex < 2 Cry Then, if expand g(z) in the hermite basis, i.e., g(x) = Σ/- (2); we have
E [g(x)]]
-
E
[o(z)]
S
aa
E [,,(,))
E (0.1)
A
(0.1)
las1
12
E [x)(
-
E
[xx(2)]]
(12)
2~N(0.11
where the second step uses Schwwrr inequality. To further upper bound this, first note that Di=1 aa by Parseval's identity and our assumption of unit norm. For the other factor above, we can write h; (1( Σÿ b1y and use the fact that |b.y| < 20()) (Fact B.I). Then,
||ll|2 1,
E [h((t)] z
E [hx(z)]
<
bis
E [x*]
E
[x+]]
No
xnd
< 20()
[x"]
[x']]
$ 20 Cryy 2 --1122
N(
14

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Plugging that in Equation (12), we obtain [Bgaa((<=) Ex(o,,)9(())] s VF2-Cr/2y 7, which gives the desired contradiction.
The lemma below provides testing algorithm for the NGCA problem (Problem 2.6) in the special case where the distribution B is k-G 6-GMM for which moment of order at most in is guaranteed to be significantly different than the corresponding moment of (0, 1).
Lemma D.2 (Testing Algorithm for Parallel Pancakes when the m-th Moment Deviates). Let B be Gaussian mixture I. of the form B Σ (yNN o²), where (0, 1) and w, 2 Wmin for all E [k]. For a decreasing sequence Xm denote by m the biggest integer such that every degree-m' m potynomial g satisfies
E [s((x)]] xx
E I-N(0,1)
[o(x)]
S Am
E a~N((,1) (x))
(13)
Consider the non-Gaussian component analysis hypothesis testing Problem 2.6. Let in be any upper bound for m i.e., m I There is an algorithmm that takes as input in and Wmin- draws (mdjormy samples, and distinguishes correctly between Hg and H1 with probability polynomial in n and d.
An X -0(1)
+ (og(k)wwil log(1/r)
Moreover the runtime of the algorithm is
Proof. We will do the proof for m = m. The proof trivially extends to any m bigger than m. For degree m + 1, there exists a polynomial that violates the condition in Equation (13). By Lemma D.I, there exists a monomial xf' with S m + such that
E mーB
E N(O.1)
[x']
> 2
C-m Am
For the corresponding d-dimensional distributions PB.v (defined in Problem 2.6) and (((, 7), we have
E
[x 84
E
8i = 88
2m PB.
(0.1)
Thus, the Frobenius norm
E Pr. (0,1)
E
=x> 2 C.m
2-cmm Am
This means that at least one entry in the difference of the two tensors has gap at least c == d- d Am The idea for the testing algorithm to approximate every entry of Eg-Ps.. (x E [x)) up to absolute error e/ e/100, and test whether some entry bigger than c/2. This is done in Algorithm 2 and Algorithm
Algorithm 2 Testing Algorithm
1: Input: ks, m E Z4, Wmin E (0, 1].
2: Output: A E (Ho. H1).
for 1,,,,,,.... .,, M + do
4: Run Algorithm with input k i, m, Wmin repetitively log((m + 1)/7) times and let i be the most frequent output.
5: if H = H2 then
6: Return Hı
7:
Return Ho-
We start with the correctness the sub-routine, Algorithm 3. always agrees with the true hypothesis, with the exception of the following case, where mistakes are permitted: this case is when the true hypothesis is Hy, the data distribution satisfies max ||wil12 S Cvd (recall that p. are the centers of the f-GMM distribution B) and Ep. [i Er-N((,n)) [=] < Cm Am- We will show that the output of Algorithm is indeed "successful" this sense with constant probability.
We say that that the output Algorithm 3 is "successful"
15

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Algorithm 3 Checking the i-th order tensor mismatch
1: Input: k, m E E.,, E E④, Wmin E (0, 1].
2: Output: H E (Ho. H1}.
+ log(k) (k)(k) w for sufficiently large C. 4: Draw ZI.-..,Ir i.i.d. from the data distribution.
3: Define n= (mi)) Cma in
5: if there exists E [n] with ||aalle Cvd then
6: Output H1 and terminate.
7: else
8: Form the empirical tensor M = -M=EEs Ea-ss(2
9: Let M' denote the Gaussian tensor E Ee.-N0..1122%
10: if there is an entry in Ma...... with |Mss....i M W > d d- Am then
11: Output H and terminate.
12:
Return Ho-
Having that claim established, Lemma D.2 follows straightforwardly: First, note that the probability of success can be amplified - by repeating the subroutine log(1/r) times and taking the majority vote. Second, if the true hypothesis is H1, there exists an such that |Eg-Pa.. [x (o, [2.0*]] [1.1) || > 2 2- Am- -m Combined with the claim of the previous paragraph about Algorithm 3, this ensures that running Algorithm 3 for that i will be Hi, as desired. Similarly, under Ho,
the output is always Ho. which guarantees that the output of Algorithm 2 matches the true hypothesis.
We now move to showing the claim that Algorithm 3 is "successful" with constant probability. We examine the following cases:
Case 1 The true hypothesis is Ho. In this case, the data distribution is D = NN(, I). By Gaussian norm concentration
(Fact B.6) we have Pr P (0. r) [max, ||æ > Cod n| < 0.01. This means that Algorithm 3 will enter line 7. Then, by standard entry-wise concentration of Gaussian tensors (see e.g., Fact 5.6 and Equation (5.4) in (Kothari & Steurer, 2017)) we have that if n d //2,, for C" >> C, we will have [= (1 Er @r]o < d=Cm the condition in 10 will be false, resulting in the algorithm output Hg.
Cm Am and thus
The hypothesis under effect is H1 and maxiel I|aill > Cydlog The claim is that for log(k)) (umm samples, with high constant probability, one sample from every component will be observed, and the sample that comes from the component with ||u l22 > CVdlog n will satisfy ||ж||| > CVdlog by Fact B.6. To see the first part of the claim, fix an E [K.] With 10/ Wmin samples, one sample from will be observed with least 0.9 probability. We can boost that probability
Case 2
1/k by repeating log(k) times. Then, by union bound, this means that one sample from each component is observed with constant probability.
The hypothesis under effect is H1 and max ||all2 S CyVlog In this case the data distribution is a k-GMM where the center of every Gaussian component is bounded in norm by most = CVdlog n. By Gaussian norm concentration, if 21,...; Sr are points drawn from that GMM, then with constant probability we will have ||æella S 2C' Therefore the algorithm will enter 7, and because of the bound |ææ|lle /CV/loo n, we can treat the distribution as bounded and use Hoeffding bound for the tensor concentration. That application of Hoeffding's 's inequality shows that if n > RC "C'C /Xg" then the estimation error is at most d=Cm Xm-- Thus, in this case, the algorithm will output H1 and only if E ( Ez~A10.1) (2. [x < 2- Cm Am-
Case 3
This completes the proof of the claim.
Our main result, Theorem 1.4 will be based on Lemma D.2 and our impossibility of matching result, Proposition 4.2 that will allow us to use M- = Olog(k) + k') in Lemma D.2. However, Proposition 4.2 concerns only discrete distributions, while the parallel pancakes uses Gaussian mixture. In order to bridge this difference, we show the following lemma, which states that the impossibility of moment matching can be indeed extended to Gaussian mixtures.
Lemma D.3. Let P be Gaussian mixture distribution on IR of the form B = Σ w.N(ps 5), where w; > O with E wi = are the weights of each component, (1,,... l4k E are the centers and 5 E (0, 1] is the parameter
16

---

On Learning Parallel Pancakes with Mostly Uniform Weights
associated with the common variance of the components. Suppose that for every polynomial of degree most m'' and PewN(0.1)l (x²())) the following holds
E [p(x]]
[(x0] SA. (0,1
E
(14)
Then, if A denotes the discrete distribution on fpr /
/i../ Ma/ Vo that assigns mass w; the point p [k]] the following is tree For every polynomial with degree most m' and Eg,N((a (x)] 1 it holds
E w~ (0,10
[(()]]
E
[(x)]] S Vm' Ad 1
(15)
Proof. We can write the distribution B as the result of applying the Ornstein-Ullenbect (Definition B.2) operator to A, i.c., B U with p v8. By Fact B.3, we have the following for every 1,2,...:
E [h((x)] 8/2/2 [h,]
E z~B
(16)
Fix i [m²]. Using the above and the fact that B matches approximately the first moments with (/ 1) (in the sense of Equation (14)) we have the following for the gap between the expectations of the Hermite polynomial h; under A and N(,, 1):
[,)]
[x:(x)]
8-2/2 E [h,(,))] -
2 [x)[
(using Equation (16))
A
20,10
D=B
8/1/2 E
[hs [+x(
(x)) (using (h= = for i 2 1)
vaB
< 8
1/2
E (nnN(0.1)
( [+([x)] +2)
(using Equation (14))
(using (o [x)] for 2
For the special case i 0, we have exact matching, Ez~A [z)] = (xxNNo..)) since ho(z) = 1.
Now, in order to show Equation (15), consider a general polynomial p(a) with Ez (v = 1. Expanding in the Hermite basis, we can write p(z) = Eiejney azh;(x) with Eiejn of (which means that (e = by Parseval's identity). We have
m
m'
2
E a
[p(x)]
E x0
p(x)]]
S
Σ a
E
[+((1)]
E
[h((x)]
x~N(0,1)
< Vmm
max
E
Th (x)
E
[b:[10]]
iE(m")
I~N(0.1)
< v m' 8 8-m'12
We now combine the previous statements to show our main theorem.
Theorem 1.4 (Testing Algorithm for Parallel Pancakes). Consider the version of the parallel pancakes hypothesis testing problem (Problem 1.1), where W' k of the weights w; in the Gaussian mixture unconstrained and the remaining k- - K are assumed to be equal each other. There is an algorithm for that problem which draws = 0 (kd/))00(++ogll +lg(()) + log(k))/wol Wwain) samples (where 8 is as in Problem 1.1 and Wmin = min W; is the smallest weight), has runtime polynomial n, d, and it outputs the correct hypothesis with probability least 0.99.
17

---

On Learning Parallel Pancakes with Mostly Uniform Weights
Proof. First, note that the parallel pancakes testing problem of interest is special case of the non-Gaussian component analysis Problem 2.6 where B = Σieja WyN(1u; 1 6), where wi, 14 and ō the ones from Problem 1.1, in particular k' of the wt's s are unconstrained and the rest are assumed to be uniform.
The proof consists of two parts: The first part argues that this one-dimensional distribution B cannot match approximately more than the first m = Ollog k + k)) moments with ((0, 7) (the approximate moment matching will be quantified shortly). Then, for the second part, we can show that since the m + 1 moment deviates significantly from that of (0, I), estimating the empirical moment tensor of order m + 1 and comparing with the one from (N, I) yields a successful test.
We now proceed with the quantification. Let C' be sufficiently large constant, and define to be the largest integer such that for every polynomial p of degree m' S m and ||pi|a we have
E a~
[x(x)]
E 1~N(0.1)
p(())]
S Am
(17)
To prove our claim by contradiction, suppose that m > C(k' + log k.). For each degree m' S m We will use Lemma D.3 with X = (6/2)cm. The application of Lemma D.3 yields that the discrete distribution A supported on a scaled version of the centers μ4; and using the same weights w; approximately matches the same m first moments with (O0, 1), i.e., for every polynomial p of degree m' I m and Ipll2 = we have
E [v(r)]
E N
b((a) S vmmmm m222 < 2- Cm//2 Nio.
(18)
where the last step uses that X = (26)-Cm. CC
The conclusion of Equation (18) contradicts Proposition 4.1. This is because the discrete distribution D from above, is of the form that Proposition 4.1 considers: supported on points, with K of the points having arbitrary mass and the remaining k'' having equal masses.
Thus far, we have shown that if m is the largest degree for which all moments m' m of the distribution A match with (0,, 1) in the sense of Equation (17), then m O(log(k) (A:) + k').
The result then follows by Lemma D.2 with in = C(log(k) + k") for a sufficiently large constant C, o²= Am = (8/2)C*.
= =1- - 8, and
D.2. Omitted Details from Section 4.2
We restate and prove a version of Proposition 4.2 which does not involve minimum weight wy of points with equal weights.
Proposition 4.1. Let k' < k be positive integers, and let A be discrete distribution on k points in R. Suppose k- 'k' of the points have equal probability masses, while the remaining k points have unrestricted probability masses. Denote by m the highest degree for which every degree-m' I m polynomial g satisfies Ez~A[g(z)] E=== 2 C.m 199122 then m must satisfy m E O(log k) + O(K).
Proof. Suppose that the order m is bigger than C'log k + Ck', If C' is sufficiently large, we will show that this moment matching is impossible.
Let pI.... Me be the points on which A is supported, and by Wi...., we the probability masses of the points. Without loss of generality, assume that the first ke points are the ones which do not have any restriction on their probability mass, and the remaining k- k are the points with equal probability masses (w: wy for all i E (K' + I....,k) k} with i + j). Let p(z) (x 14) ... (x ) be the polynomial whose roots are the first k points.
We will show the following series of inequalities (we use the notation |||||- = Buw-va.nllee)))1
B
|pll1
w;
2
E (22 1x:)
|p
2 3 3-2k
(19)
i=++1
18

---

On Learning Parallel Pancakes with Mostly Uniform Weights
The third step is Fact 2.4. To how the first step is derived, let & be the event that E {K' + ,..., kj. Then
1pl1 E [p(())] 14m4
E ((())1())) 14--
E u
Pr[E]
l1plla Pr( llll2
Σ k=++1
w
where the first step above uses the fact that ,i,,..., |ak are roots of p. Rearranging gives Di=k" wi 2 (1P/11///lll1))
remains to show the second step in Equation (19), which is due to the approximate moment matching property: Let Am := 2 Cm to save space. For the numerator, we have E 2 |pl| Am Ipll 2 |ppli 3m3 2 lllla/ where the first step uses the approximate moment matching, the second step uses Fact 2.4 and the last part that Am 2p2 Cm with C being sufficiently large constant and > k'. We can work similarly for the denominator to get A [x)] < | + Am 1 < 1 Am3*') ) I 21. where we used Fact 2.3 in the penultimate step. Combining the bounds for numerator and denominator conclude the proof of the second step in Equation (19).
We can now conclude the proof of Theorem 1.4, Since we have assumed that the weights for the last k k' points are equal to each other, Equation (19) implies that mitl;=&' k +l...... wi 33-2k /k: Using Proposition 4.2 with wp 33-2k /k concludes the proof.
D.3. Omitted Details from Section 4.2.1
We restate and prove the following corollary of Lemma 4.4.
Corollary 4.5. Let p: R + R be a polynomial of the form p(x) (x p1) (22 (.))...(1 me) where f1, .i...... Muk E R are arbitrary parameters. Define I
For all t 2 we have exp [2] Seez In lo(x))dz)) 2 2000"""
1lp|
Proof. We can multiply both sides of the conclusion of Lemma 4.4 (Equation (5)) with the Gaussian density e /2 ///2//2T and then integrate both sides. This yields
Vi
12 exp (1) / In lnlp())ldx) dy
Vi
pp(v)] 1 -2 20(2)) /2T
2m
The left hand side is (exp ((1/17)) SOEI In lp(=))dx)) The right hand side is
V
e 12
dy = 2011)
|p())]
E
[p(()]]
[Ip())|1(()) > vi)) 2 O(K))
2T
(1
v~N10.1)
E 10
[p(w)]| - -1plle /
Pr
[lv| =1] 2 2-0(K)
(using the Cauchy- Seech--Shhwaz-h inequality)
v-N(0,1)
[p(3)]] 11lpllle-- 12/2 2 2-0(K))
E
1)
[Iell2
1lel|z llell2e-1//2) =//2) 2 -0((k)
(using Fact 2.4)
12l2
(using t > 1)
We now restate Lemma 4.4 and provide the complete proof which includes the details that were missing from Section 4.2.
Corollary 4.5. Let R + R be polynomial of the form p(rr) (xr [x) (12)) ... (xr mx)) where 11, .......; M4g
E
R
are arbitrary parameters. Define =
For all t 2 we have exp ( Seer In (p(x)\dx) 2
2002
Proof. Fix arbitrary y R with lyl x Vt. First, note that by the property of logarithms and sums, we can write the left hand side as
exp 1
In |x ps/dz
JoET
19

---

On Learning Parallel Pancakes with Mostly Uniform Weights
In order show Equation (5), it suffices work with each term and show the following for each [k]]
1 1n [
2 -
IEI
Equivalently, it suffices to show that Equation (5) holds for every linear polynomial of the form p(z) = I a. Therefore, the goal for the rest of this proof is to show that
exp (H/
In /2 - aldz) 2 y al/0(),
(20)
holds for every E IN and E I with lul S Vt. We will examine two cases.
Case 1 The first case is when the root a of the polynomial is outside the interval J. In this case, we can show that
Ix alyly - al = @11,, which implies In | - al 2 In ly - - 0(1), and the desired conclusion (Equation (20)) follows
by integrating both sides and applying the exp(-) function.
To show the earlier claim that Jr al/ly al ((), we can consider the following sub-cases:
1. Case 2 1.1v2t (i.e., is to the right of I): Suppose 1.1v2t + for some non-negative u. Then, (1.1/2 - z) + O (vv))
and x - alllllll al = (o(vt) + (e(() + u) (().
(1.1 v) u O Vt) + u. Therefore, for any u 2 0, the ratio
2. The cases - vi and [vt, 0.9 can be shown in similar manner.
Case 2 The complementary case is when the root of the polynomial p belongs in the interval I. In that case,
1.1v2 In(x-a)e a dr + in(a-r)dz.
In l - a/
[1]
[ 0.92
ZET
Define A := 0.2v/11 12 11.1//1 In(r a dr and ==
0.2v2: Jo.9 In(a z)dr. We will work with each integral separately. For A, we have the following (after change of variable in the integral):
1
1.127-u
In de
1
[-2 +
21n 2
V
0.2
21
0.2v
5.5
5.5
In (L.V26-0).
0.2v
0.2V
we can rewrite the above as A = -C1 + + Recalling that we have assumed E 20, 1.1 G1 5.5 0.2v E 1].
In In
a), where
We now work with the integral defined as A previously in a similar way:
m29.9/2t
1-2 2 In 11=))==0000000
B
In de
0.2 J
0.2v
4.5 +
1.5)
In In(a-0.9v21)
0.2v2t
0.2
Taking into consideration that E [0.9/2t, 1.1 1 the above can be written as B = -C2 + Cn 0.9 where C2 o
0.2v2: - 4.5 E [0, 1].
Combining the bounds for A and B together with the definitions Ci 5.5 0.2/2
and C2 0.2//t 4.5, obtain
exp(A + B) = (a) 1), where [(a the function
f(a) = 5.5 0.2
1n(1.122t- a)+
4.5) In(a 0.9V2t)
0.
20

---

On Learning Parallel Pancakes with Mostly Uniform Weights
We verify through derivative analysis that the minimum is achieved the midpoint of I, i.e., for 2
9000000--22]) (In(10a - 2/ - ln(11 -
(a) = 22
is easy to that (1(2 O. Furthermore, the second derivative (a) 1/(1/50- (a - 22) which is non-negative for all E I. Thus, the only minimizer in I is v 2t. For that point, exp(A B) becomes:
exp(A+ 2 exp
In(t/50) 2
1
2
V
20
52
where we used y al lyl + +a| S + < 2.6V
21


Reviews:
[{"review_id": "CZ1BnzWbfe", "reviewer": "Reviewer_E3iV", "summary": "This paper studies the hypothesis-testing problem of parallel Gaussian pancakes, specifically under structural assumptions on the component weights. The goal is to distinguish between the standard gaussian and the k gaussian pancakes with collinear centers and common covariance. For learning the general mixture of k gaussians, the best known algorithm have sample complexity $d^{O(k)}$, and in the statistical query model, this problem requires sample complexity $d^{\\Omega(k)}$. Recent work considers the setting where the minimum weight of component is $w_{\\min}$ and components have common covariance. In this case, they provide $d^{O(\\log(1/w_{\\min}) )}$ time algorithm to learn the GMM. \n\nIn this paper, they first provide a SQ lower bound which shows that even when all component weights are uniform, distinguishing between such a mixture and the standard Gaussian requires $d^{\\Omega(\\log k)}$ complexity. This implies that the algorithm above is essentially best possible in this case. \nThen they provide an algorithm for the hypothesis testing problem when most of the weights are uniform but a small fraction can be arbitrary. Their algorithm has the complexity $(kd)^{O(k'+\\log k)} + \\log k/w_{\\min}$ where $k'$ components have arbitrary weights and the minimum weight is $w_{\\min}$. Their algorithm is more efficient than the previous algorithm even if there is one component has an exponentially small weight, like $2^{-k}$. Their results refine existing complexity bounds and offer new insights into the role of weight distributions in learning Gaussian mixtures.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their effort and their positive assessment of our work. We will fix the typos pointed out in the final version. We respond to their question below:\n\n(**Is the $\\log(k)/w_{\\min}$ term in the sample complexity necessary?**) This term corresponds to (roughly) the number of samples required to observe at least one sample from each Gaussian component, which is necessary for distinguishing the hypotheses. Suppose that the parameter $\\delta$ is sufficiently small such that distinguishing between $N(0, I)$ and $N(0, I - \\delta vv^\\top)$ requires more than $\\log(k)/w_{\\min}$ samples. If the parallel pancakes distribution has all but the $i$-th component centered at the origin, then the algorithm cannot make the correct prediction unless it sees a sample from that special component. This shows that $1/w_{i}$ samples are necessary. Since the algorithm does not know which component is the special $i$-th one, our analysis applies a union bound over all components and uses the bound $w_i > w_{\\min}$ to arrive at the $\\log(k)/w_{\\min}$ term in the sample complexity. While there might be some room for improving the $\\log(k)$ factor with a potentially better argument than the naive union bound, the $1/w_{\\min}$ term is essentially required by the initial argument.", "claims_and_evidence": "Yes, the claims are all supported by rigorous theoretical analysis.", "methods_and_evaluation_criteria": "Yes, the lower bound and algorithm makes sense and uses various techniques from statistical query complexity, moment-matching analysis, and probability theory.", "theoretical_claims": "Yes, I checked the correctness of the proofs for theorem 1.3 and 1.4.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper builds on prior work in Gaussian mixture model learning, particularly results on statistical query hardness and moment-based learning methods. It extends previous findings by refining complexity bounds and considering more structured weight distributions. The techniques used in the paper can potentially have a broader impact on the learning theory and statistics.", "essential_references_not_discussed": "No, the paper cites the related literature thoroughly.", "other_strengths_and_weaknesses": "Strengths: The paper provides a solid theoretical contribution by tightening known complexity bounds and introducing novel proof techniques. They also provide a new algorithm that can achieve better complexity for the testing problem of Gaussian pancakes when the weight distribution is structured.", "other_comments_or_suggestions": "Minors:\n\n- Fact 3.2, Line 236, $p \\in V_t \\setminus$ {0}.\n- Lemma 3.5, $p\\neq 0$ in the statement, and Line 260, $|x| = O(\\sqrt{t})$. \n- Line 280, $\\epsilon = (\\delta / d)^{Cm}$?\n- Line 356, g(x) = f(x) ?\n- Line 409, $O(\\sqrt{t})$ ?\n- Appendix D.3, the second Corollary 4.5 should be the restatement of Lemma 4.4.", "questions_for_authors": "1. Given the analysis of the algorithm, is it possible to argue about the lower bound in the case? Is this $O(\\log k/ w_{\\min})$ term necessary for this problem in the worst case? It seems this is only used to check whether the components are more than $O(\\sqrt{d})$ far away from the origin?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hJ6e6k0rVw", "reviewer": "Reviewer_Disr", "summary": "This paper studies the problem of learning mixtures of Gaussians where each component in the mixture has a shared covariance.\n\nFirst, an SQ lower bound is proved, matching a recent positive algorithmic result and indicating that it likely cannot be improved. It is shown that even in the case when the mixture is of $k$ equally weighted Gaussians, the problem of distinguishing the $k$-GMM from a spherical Gaussian has SQ complexity $d^{\\Omega(\\log(k))}$. This indicates that a recent result showing an algorithm with a $d^{O(\\log(1/w_{min}))}$ is likely optimal when $w_{min} = \\Omega(1/\\mathrm{poly}(k)))$.\n\nNext, this paper works on understanding the optimal complexity dependence on $w_{min}$. It is shown that for instances that are close to uniformly-weighted mixtures (but with a small number of arbitrarily-weighted components), the complexity in $k$ and $w_{min}$ can be somewhat decoupled, and solved with $d^{O(\\log(k))}$ operations/samples instead of $d^{O(\\log(1/w_{min}))}$ complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their effort and their positive assessment of our work.", "claims_and_evidence": "Yes, the proofs are clear and I was easily able to follow the general strategy despite this being a very technical work.", "methods_and_evaluation_criteria": "Yes, proofs make sense", "theoretical_claims": "I checked the proofs in the main text, and they seemed correct", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "There is a large literature on learning Gaussian Mixture Models. This paper represents new fundamental advances in our understanding of the complexity of this problem, which is not yet fully settled. I think that this paper will be well appreciated within its literature.", "essential_references_not_discussed": "I am not aware of any", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "* Typo in Fact 3.2, the infimum should be over V_t \\setminus \\{0\\} instead of over V \\setminus \\{0\\}.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IwkaPelJhd", "reviewer": "Reviewer_4JWr", "summary": "The paper studies a hypothesis testing problem where the main task is to distinguish (with as few as possible samples) between a standard Gaussian $N(0,I_d)$, and a \"parallel pancakes\" distribution. This distribution is characterized by k discrete mean points along an unknown line in d dimensions. Now the distribution orthogonal to the line is standard Gaussian, but along the line, the variance is squeezed by a factor $1-\\delta$.\n\nThe main results are:\n1. a $d^{\\Omega(\\log(k))}$ lower bound against distinguishing a standard normal from a pancake mixture where all mixture weights are equal (resp $> 1/poly(k)$). This matches under the same weight assumptions an upper bound of Anderson 2024, $d^{O(\\log(1/w_min))}$.\n\n2. When even one $w$ is not bounded below, the upper bound $d^{O(\\log(1/w_{min}))}$ becomes $2^{O(k)}$. As a consequent next step the authors provide a testing algorithm with a dominating factor of $(kd)^{O(\\log(k) + k')}$ where $k'$ weights are unbounded and $k-k'$ are bounded below by $1/poly(k)$. The minimum weight still plays a role but is only linear in $1/w_min$, so must be super tiny to dominate.\n\nThe analyses are highly technical and are based on the observations that there are discrete distributions that share many but not too many smaller moments with the standard Gaussian. The lower bound comes from the fact that the pancakes with the support set as means and spread along a random directional vector are hard to distinguish from the standard normal in d dimensions. And the upper bounds are shown by showing that only a relatively small number of moments are so close that they are indistinguishable. So the algorithm can check all $i$-th moment tensors up to $i \\in O(\\log(k) + k')$ and must then find at least one larger deviation.\n\n### update after rebuttal:\nThe authors have addressed my points satisfactorily. Remaining issues are easily resolvable typos. I will therefore retain my initial score \"4: Accept\".", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you to the reviewer for the positive assessment of our work and their thorough reading. When we refer to matching the $m$ moments, we always mean the first $m$ moments. We will ensure to clarify this whenever it is not currently explicit. The other points raised are typos, and we will fix them in the final version.", "claims_and_evidence": "All claims are rigorously proven.", "methods_and_evaluation_criteria": "N/A purely theoretical paper", "theoretical_claims": "All theoretical claims seem correct.", "experimental_designs_or_analyses": "N/A purely theoretical paper", "relation_to_broader_scientific_literature": "Testing of Gaussians and mixtures thereof seems to be an important and active field.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "The paper is super well written. The high level description of even very technical parts can be followed without prior knowledge in the field.", "other_comments_or_suggestions": "There are a few lines that are unclear to me, possibly typos:\n- p6: \"A cannot match more than O(log k + k') moments with the standrad Gaussian\" - it would be more clear to say that it refers to the *smallest* O(...) moments. Or os there some monotonicity property that I am not aware of (such as if m-th moment matches then also all m'-th moments for m'<m match)?\n- p6: \\epsilon := \\lambda/d^m = (d/\\delta)^{(C-1)m}: by the previous bound on lambda, shouldn't the final expression be ((\\delta/2)^{C}/d)^m, it seems to be stated inversely?\n- line 6 of algo 1 (also algo in the apendix): (i_1 ... j_i), should be (j_1...j_i) or even (1..i) ?\n- definition of p(x) is sometimes prod (x-mu_i) (p6) and sometimes prod (x-mu_i)^2 (p7). maybe better to stick to the former and then work with p or p^2 as required.\n- p7 l.356: it should be g(x)=f(x), no? f^2 comes only in the next step.", "questions_for_authors": "I have no additional questions", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "axx9LYViEV", "reviewer": "Reviewer_Y4N2", "summary": "This paper is concerned with learning mixtures of $k$ Guassians, when given i.i.d samples from the mixture. When the mixture weights and covariances of the individual components are unknown and arbitrary, the best-known algorithm from the literature (due to Bakshi et al. 2022) has sample complexity $d^{O(k)}$. A lower bound instance due to Diakonikolas et al. 2017, known as the \"parallel pancakes\" mixture, comprises of a family of mixtures of $k$ Gaussians having identical covariances. For this family, any SQ based algorithm necessarily requires sample complexity $d^{\\Omega(k)}$. However, the weights of the mixture in the family of the lower bound instance end up having to be as small as $2^{-\\Omega(k)}$. A natural question here is: can the lower bound be circumvented if the mixture weights are constrained to be at least $1/poly(k)$? Recent results by Anderson et al. 2024, Buhai and Steurer 2023 show that the answer is yes. In particular, they show an algorithm that correctly clusters most points drawn from a $k$-mixture of Gaussians using only $d^{\\log(1/w_{min})}$ many samples, where $w_{min}$ is the smallest weight in the mixture.\n\nThe first main result in this paper shows that this sample complexity bound is essentially optimal. Theorem 1.3 constructs a family with uniform mixture weights, such that any SQ algorithm must necessarily have sample complexity $d^{\\Omega(\\log(k))}$.\n\nThe algorithms due to Anderson et al. 2024, Buhai and Steurer 2023 have sample complexity $d^k$, even if only a single mixture weight is $2^{-k}$. One can ask if this can be improved. Specifically, consider the setting where $k'$ out of the $k$ mixture weights are allowed to be arbitrary, but the rest are the same. The second main result in the paper (Theorem 1.4) shows that for the task of distinguishing the standard Gaussian from a mixture of this form, there is an algorithm that has sample complexity that scales as $1/{w_{min}}$, which is a better sample complexity that of Anderson et al. 2024, Buhai and Steurer 2023. Note however that the upper bound is only for the testing problem, and not for the learning problem.\n\nFor the first result, the authors use a previous construction by Kane 2015, and combine it with a construction from Diakonikolas et al. 2017, to obtain a one-dimensional discrete distribution over $2^{O(t)}$ elements that matches $t$ moments of the standard Gaussian. For the second result, the authors use that their construction for the previous part is essentially optimal. Namely, the uniform distribution on any $k$ points cannot match more that $O(\\log k)$ moments of the standard Gaussian. This can be extended to arguing that distributions that are arbitrary on $k'$ out of the $k$ points, but uniform on the rest of $k-k'$ points, cannot match more than $O(\\log(k)+k')$ moments of the Gaussian. This fact allows distinguishing between a $k$-mixture from the standard high-dimensional gaussian using higher order tensors that reveal the differences in the higher order moments.\n\n## update after rebuttal\nI thank the authors for the clarifications. It would be useful to include them appropriately in the revision of the paper. I maintain my evaluation of the paper, and my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their time and positive assessment of our work. We respond to the individual questions below:\n\n(**Difference between Bakshi et al. 2022 and Diakonikolas et al. 2017**) Yes, the reviewer is correct that the algorithm from Bakshi et al. 2022 applies to all GMMs, while in the lower bound of Diakonikolas et al. 2017, the mixtures share a common covariance matrix and potentially different means and weights. This special structure *strengthens* the lower bound, because even the simpler case of common covariance is as hard to learn. We also achieve the common covariance structure in our lower bound, and most importantly, we get a lower bound with *uniform* weights as opposed to the exponentially small weights in Diakonikolas et al. 2017. If one wants to further explore the nuances between common and different covariances, we would like to point out that it is an open and interesting problem to refine the computational landscape based on whether the covariances are the same or not. For example, one open problem that we mention in the paper is whether a learning algorithm with complexity $d^{O(\\log(1/w_{\\min}))}$ exists that works for arbitrary covariances, which would improve over the $d^{O(k)}$ algorithm by Bakshi et al.\n\n(**Comparison of different kinds of learning guarantees**) The main difference between these guarantees is that for clustering or parameter estimation, one must assume that the mixture components are statistically separated (see the pairwise mean separation assumption in Buhai and Steurer 2023); otherwise, the clustering or parameter estimation goal is information-theoretically impossible. In contrast, if the goal is simply to output a mixture that is close in total variation (TV) distance to the mixture that generated the samples (as in Bakshi et al. 2022), then the separation assumption is not necessary. We emphasize that both the Diakonikolas et al. 2017 lower bound construction and our new construction yield GMMs whose components are indeed pairwise separated, thus they imply lower bounds for all of clustering, parameter estimation and learning-in-TV-distance.\n\n(**Testing -> Learning?**) There are multiple ways to define a learning version of our problem, which we comment on below:\nLearning a parallel pancake distribution in the form defined in Problem 1.1, under the weight restriction assumption of Theorem 1.4 (with $k’$ arbitrary weights and $k-k’$ uniform weights): \n * First, it should be possible, though not immediately straightforward, to learn the hidden direction $v$ of the parallel pancake distribution (the direction along which the distribution is non-Gaussian). The reasoning behind this is that, since the difference between the population moment tensor of the standard Gaussian and the one for the pancake distribution is the tensor power of the unknown vector $v$, a more sophisticated argument—such as performing tensor SVD to estimate the top eigenvector (in contrast to the simpler argument of our testing algorithm, which just estimates the norm of the moment difference)—might work for learning $v$. Once $v$ is learned, one could attempt to project the samples into direction $v$ to learn the non-Gaussian distribution $A$. There are multiple levels of approximation here: approximating the moments from samples, relating the top eigenvector of the moment tensors to the one from the population version, and bounding the learning error of $A$ along the learned direction. Thus, although the result seems plausible, we have not yet worked out how this propagation of errors can be analyzed.\n* Learning an unknown $k$-mixture of GMMs where k’ weights are arbitrary and $k-k’$ are uniform: This is a much more general problem, thus our testing result provides very limited insight for this problem. As mentioned, there are interesting open problems in this direction.\n\n(**Has the combination of Kane 2015, and Diakonikolas et al. 2017 been used before?**) To the best of our knowledge, the combination of Kane 2015 and Diakonikolas et al. 2017 has not been used in prior work. One key advantage of this approach is that it enables us to establish the lower bound for exactly uniform mixtures, rather than for mixtures with weights that are only polynomially related or differ by a constant factor. Given that we are presenting the first SQ lower bound for equal-weight Gaussian mixtures, it is unlikely that other works would have employed the results and techniques of Kane 2015.", "claims_and_evidence": "The claims and evidence appear convincing to me.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I only glanced over the proofs, and did not verify calculations line-by-line. They appear correct to me, and the progression in the overall analysis checks out to me.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The problem of learning mixtures of Gaussians is a fundamental problem in statistics that goes back to the days of Karl Pearson from the 1890s, with applications to a variety of sciences. Pinning down the computational and statistical complexity of this problem in different regimes is central to the theory of this problem.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper is generally quite well-written. Personally, I find that the results in the paper add to the gaps in understanding the sample complexity of learning mixtures of Gaussians, a classical problem in statistics. In particular, the conclusion that the recent postive results due to Anderson et al 2024, Buhai and Steurer 2023 are essentially optimal, is important and satisfying. Furthermore, the additional positive result for the slightly weaker testing problem also indicates algorithms with better dependence on the minimum cluster weight may be attainable for the learning problem. Overall, I find the conclusions in the paper to be important, and they tangibly further our understanding of the gaussian mixture model problem.", "other_comments_or_suggestions": "Please see questions below.", "questions_for_authors": "1) Am I correct in understanding that the general sample complexity upper bound of $d^{O(k)}$ in Bakshi et al. 2022 applies to arbitrary Gaussian mixtures (arbitrary weights, arbitrary means, arbitrary covariances), whereas the lower bound of Diakonikolas et al. 2017 has an additional special property that it is a family of mixtures where for each mixture, the covariances of the components are identical (although means are different, and weights can be exponentially small)?\n2) The results of Anderson et al. 2024, Buhai and Steurer 2023 seem to be about clustering points drawn from a mixture model. Could you comment on the differences between this task, and on the task of learning the mixture (i.e., either estimating the parameters/learning a distribution close in TV)?\n3) Could you comment on your thoughts on how the positive result for testing (your second result) could extend to a positive learning result? Presently, while the sample complexity of your testing algorithm is better, it is only for a weaker problem. In particular, what are the primary difficulties in employing standard conversions of testing algorithms to learning algorithms?\n4) In terms of technical novelty: it seems that beyond the conclusions, the primary technical novelty in the paper is the connection between the construction of Kane 2015, and the past result of Diakonikolas et al. 2017 which shows that one can approximate $t$ moments of the standard Gaussian using a distribution having support only on an interval of size $O(\\sqrt{t})$. Has this combination of the Kane 2015 construction and Lemma 3.3 from Diakonikolas et al 2017 been used in the literature in the past?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of learning the mixture of k Gaussians with shared unknown covariance and bounded minimum mixture weight. The paper first shows a statistical query lower bound showing that the recent upper bound is tight even when the mixture weights are  uniform. The paper also shows an algorithm for testing whether the given distribution is a mixture of mostly uniform weights or the standard gaussian, with query complexity separating the term required for uniform weight and the term depending on the minimum weight. This is an important evident that more efficient algorithms might be possible for smaller mixture weight lower bounds. All reviewers consider the paper to be a timely contribution to a classical problem and might lead to future improvements in the upper bounds. They also suggest that the paper is well-written.
Decision: Accept (spotlight poster)