SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Authors: Ilias Diakonikolas
Daniel Kane
Lisheng Ren
Yuxin Sun
Venue: NeurIPS 2023 poster (2023)
Keywords: Non-Gaussian Component Analysis

Abstract: We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model.
Prior work developed a methodology to prove SQ lower bounds for NGCA that have been applicable to a wide range of contexts.
In particular, it was known that for any univariate distribution $A$ satisfying certain conditions,
distinguishing between a standard multivariate Gaussian and a distribution that behaves like $A$ in a random hidden direction and like a standard Gaussian in the orthogonal complement, is SQ-hard.
The required conditions were that (1) $A$ matches many low-order moments with a standard Gaussian,
and (2) the chi-squared norm of $A$ with respect to the standard Gaussian is finite.
While the moment-matching condition is clearly necessary for hardness, the chi-squared condition was only required for technical reasons.
In this work, we establish that the latter condition is indeed not necessary.
In particular, we prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only.

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Ilias Diakonikolas University of Disconsin-Maddinn ilias@cs. wisc. edu
Daniel M. Kane University of California, San Diego dakane@cs, uesd.edu
Lisheng Ren University of Mircoonnii-Maiiion 1ren29@wisc.co edu
Yuxin Sun
University of Wisconsin-Madison yxsunOcs, wisc. edu
Abstract
We study the complexity of Von-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. Prior work developed a general methodology to prove SQ lower bounds for this task that have been applicable wide range of contexts. In particular, was known that for any univariate distribution A satis- fying certain conditions, distinguishing between standard multivariate Gaussian and a distribution that behaves like A in a random hidden direction and like a stan- dard Gaussian in the orthogonal complement, is SQ-hard. The required conditions were that (1) A matches many low-order moments with the standard univariate Gaussian, and (2) the chi-squared norm of A with respect to the standard Gaus- sian is fimite. While the mottnnt-atching condition is necessary for hardness, the chi-squared condition was only required for technical reasons. In this work, we establish that the latter condition is indeed not necessary. In particular, we prove near-optimal SQ lower bounds for NGCA under the moment- matching condition only. Our result naturally generalizes to the setting of hidden subspace. Lever- aging our general SQ lower bound, we obtain near-optimal SQ lower bounds for a range of concrete estimation tasks where existing techniques provide sub-optimal or even vacuous guarantees.
Introduction
Non-Gaussian Component Analysis (NGCA) a statistical estimation task first considered in the signal processing literature (BKS 06). As the name suggests, the objective is find a non- mon-gaussian direction (or, more generally, low-dimensional subspace) in a high-dimensional dataset. Since its in- troduction, the NGCA problem has been studied in range of works from algorithmic standpoint; see (VVI8, GS19 and references therein. Here we explore this problem from a hardness perspec- tive in the Statistical Query (SQ) model. Before motivate and state results, require basic background on the SQ model.
SQ Model SQ algorithms bounded functions on the underlying distribution through the SQ oracle rather than directly ac- cess samples. The model was introduced by Kearns [Kea98) as natural restriction of the PAC model [Va184] in the context of learning Boolean functions. Since then, the SQ model has been extensively studied in range of settings, including unsupervised learning [Fel16]. The class of SQ algorithms is broad and captures range of known algorithmic techniques in machine learning in-
class of algorithms that are allowed to query expectations of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

cluding spectral techniques, moment and tensor methods, local search (e.g., EM), and many others (see, e.g., [FGR 17 [FVV17] and references therein).
Definition 1.1 (SQ Model). Let D be a distribution on IR= A statistical query is bounded function q: R [-1, 1]. We define (TAT((r) to be the oracle that given any such query q. outputs a value v such that Iv Ex-D Ex=]l[(x)] S т, where > is the tolerance parameter of the query. A statistical query (SQ) algorithm an algorithm whose objective is learn some information about an unknown distribution D by making adaptive calls to the corresponding STAT(() oracle.
The following family of high-dimensional distributions forms the basis for the definition of the NGCA problem.
Definition 1.2 [Hidden-Suuspace Distribution). For a distribution A supported on I and matrix V E R2xm with VTV = Im we define the distribution P supported on R such that dis- tributed according to A in the subspace span(V1, ........ (v.......... Vm) and is an independent standard Gaussian in the orthogonal directions, where Vi...., Vm denote the column vectors of V. In particular, if A a continuous distribution with probability density function A(y), then P.V. is the distribution over Rn with probability density function
(x) A((v1, (),1,x),.-... x)...., (V x)) exp(-l|x VVT x/2//11////// (22/2)/(2m)) (2-
That is, P is the product distribution whose orthogonal projection onto the subspace of V is A, and onto the subspace perpendicular to V is the standard (n m)-dimensionnal normal distribution. An important special case of the above definition considers to subspace is a hidden direction); for this setting, we will use the notation PA for such a distribution, where A is mee-iimeniooall distribution and v E IR is unit vector.
(i.e., the case when the hidden
Since we are focusing on establishing hardness, we will consider the following hypothesis test- ing version of NGCA (since the learning/search version typically reduces to the testing problem). We use N₁ to denote the standard n-dimensional Gaussian distribution (0, I,.) We use ('(On,,) to denote the uniform distribution over the set of all orthogonal matrices V E Ruxm; namely, this is the distribution obtained by taking RV', where R. E Rax= is a random rotation matrix and V E Rn is an arbitrary orthogonal matrix.
Definition 1.3 (Hypothesis Testing Version of NGCA), Let m be integers. For a distribu- tion supported on IR"", one is given access to a distribution D such that either:
Ho: =N
H₁: i given by pd where V (..m).
The goal is to distinguish between these two cases Hu and H1.
For the special case that m 1 (i.e., for a univariate distribution A), prior work [DKS17] established SQ-hardness of NGCA under the following condition:
Condition 1.4. Let E Z+. The distribution A on R is such that (i) the first d moments of A agree with the first d moments of N00 1), and (ii) the chi-squared distance x²,ANN) is finite, where the chi-squared distance for two distributions (with probubility density functions) P,Q R R is
defined as QP,
def JKER= P(x))/Q(xxx)
Specifically, the main result of (DKS17) shows that any SQ algorithm that solves the testing version
of NGCA requires either 2n (()) many SQ queries or least one query with accuracy
((d) / (A,
It is worth noting that subsequent works (see DD222a and (DKF221) generalized this result so that it only requires that (i) A approximately matches moments with the standard Gaussian, and (ii) A is din-esenniioal distribution embedded in hidden low-dimensional subspace, instead of -ie-dimensional distribution.
While the SQ lower bound result of DKS17 was phrased for the search version of NGCA, they can be directly translated to the testing version; see, e.g.. Chapter 8 of [DK23

---

The starting point of our investigation is key technical limitation of this line of work. Specif- ically, if (O, 1)) is very large (or infinite), e.g.. if A has constant probability mass on a discrete set, the aforementioned SQ lower bound of [DKS17 can be very weak (or even vacuous). It is thus natural to ask if the finite chi-squared assumption is in fact necessary for the corresponding SQ lower bounds to hold.
A concrete motivation to answer this question comes from the applications of a generic SQ lower bound for NGCA to various learning problems. The SQ-hardness of NGCA can be used to obtain similar hardness for a number of well-studied learning problems that superficially ap- pear very different. These include learning mixture models (DKS17 DKP723 DKS23], robust mean/covariance estimation (DKS17), robust linear regression [KS19) learning halfspaces and other natural concepts with adversarial semi-random label noise [K720) GGK20 DK22a DKPZ21 DKK+221, list-decodable mean estimation and linear regression [DKS18 21P+
learning simple neural networks [DKKZ20) GGJ and even learning simple generative mod- els [CLL22]. In several of these applications, the requirement of bounded chi-squared distance is somewhat problematic, in some cases leading to quantitatively sub-optimal results. Moreover, in certain applications, this restriction leads to vacuous guarantees.
1.1
Our Results
1.1.1
Main Result
Our main result is qualitatively near-optimal (up to the constant factor the exponent) SQ lower bound for the NGCA problem, assuming only the moment-matching condition (i.e., without the chi-squared distance restriction). Informally, we essentially show that in order to solve the NGCA in dimensions with an m-dimensional distribution A that (approximately) matches moments with the standard Gaussian up to degree d, any SQ algorithm will either require one query with accuracy On (d)) or exponential n many queries.
Formally, we establish the following theorem.
Theorem 1,5 (Main SQ Lower Bound Result). Let X E 10,1) and n, m, d E N with d even and m, d. S n². Let u E R.,4 and be a distribution on T.Th such that for any polynomial f: : R. - R of degree at most d and Ex-N [xx]²] 1, the following holds: [Ex~A [x)) Ex-N.,, [xx]] S v. Let < (1- (1- and n be at least sufficiently large constant depending on c. Then any SQ algorithm solving the n-dimensional NGCA problem (as in Definition 1.3) with 2/3 success probubility requires either (i) query of tolerance Om,d (n- ((1)(()))/
+ o(1))e, or (ii)
go many queries.
A few comments regarding the parameters are order here. We first note that the constant in O -
is roughly the size of the Binomial coefficient (ld+m)/2-1), Furthermore, m will have m, d < 1/). Therefore,
would like to point out that for most applications the parameters À and e can be taken to be arbitrarily close to O. So, informally, our lower bound on the query accuracy can be roughly thought of as (((+m)/22-1)) nn-
For all the applications given in this paper, the above theorem will be applied for the special case that m namely, the case that the hidden subspace is hidden direction and A is univariate distribution.
Relation to LLL-based Algorithms for NGCA Consider the special case of the NGCA problem corresponding to m = 1 where A is discrete distribution that matches its first d moments with the standard Gaussian. Theorem 1.5 implies that any SQ algorithm for this version of the problem either uses a query with accuracy n Q(d) or exponential many queries. On the other hand, recent works (K22b, ZSWB22 gave polynomial-time algorithms for this problem with sample complex- ity (n)) regardless of the degree d. worth noting that the existence of these algorithms does not contradict our SQ lower bound, as these algorithms are based on the LLL-method for lattice basis reduction that is not captured by the SQ framework. An an implication, follows that LLL-- based methods surpass any efficient SQ algorithm for these settings of NGCA. A similar observation was previously made in (DH23 for the special case that the discrete distribution is supported on {0, +1}; consequently, [D233 could only obtain quadratic separation. Finally, we note that this

---

limitation of SQ algorithms is also shared by two other prominent restricted families of algorithms (namely, SoS algorithms and low-degree polynomial tests).
1.1.2 Applications
We believe that Theorem 1.5 is interesting in its own right, as elucidates the SQ complexity of a natural and well-studied statistical problem. Here discuss concrete applications to some natural statistical tasks. We note that the SQ lower bound in the prior work [DKS17 cannot give optimal (or even nontrivial) lower bounds for these applications.
List-decodable Gaussian Mean Estimation One can leverage our result to obtain a sharper SQ lower bound for the task of list-decodable Gaussian mean estimation. In this task, the algorithm is given as input points from R where an & < 1/2 fraction of the points are drawn from an unknown mean and identity covariance Gaussian (H, I), and the remaining points are arbitrary. The goal of the algorithm is to output list of O(1/a) many hypothesis vectors at least one of which is close to I in f2-norm with probability at least 2/3. DKSI& established the following SQ lower bound for this problem (see also [DK23) for different exposition).
Fact 1.6 (DKS18). For each d E Z4 and e E 1/2) there exists Ca > O such that for any 0 sufficiently small the following holds. Any SQ algorithm that is given access to a (1 - ----rrurpeeedd Gaussian N NH, I) in n > d3le dimensions and returns a list of hypotheses such that with probability at least 2/3 one of the hypotheses is within fz-distance cate" -1/d -1j= the true mean μ., does one of the (üi
following: (i) Uses queries with error tolerance at most exp(O(a (pp(((==/4)))0m (()-))))------ Uses at least exp(S2(n")) many queries. (iti) Returns a list of at least (x)( many hypotheses.
The above statement is obtained using the framework of DKS17 by considering the distribu- tion testing problem between NV N(J,, distribution of the following form.
[ I) and PA, where A is the one miedimensiooal moment-matching
Fact 1.7 (DKSS8), see Lemma 8.21 in DK23)). For d E Z+, there exists a distribution A = aN 1) + (1 - E, for some distribution E and μ = 10c such that the first moments of A agree with those of (0. Furthermore, the probability density function of E can be taken to be pointwise at most twice the pdf of the standard Gaussian.
We note that x2 (A,W) O(exp(x²)) and this results in the exp(O -2/4) term in the error tolerance of Fact 1.6 Consequently, if a < log(n)-44f= the error tolerance is greater than one and Fact[1.6, fails to give a non-trivial bound. It is worth noting that the setting of "small a" (e.g., a sub-constant in the dimension) is of significant interest in various applications, including in mean estimation. A concrete application is in the related crowd-sourcing setting of [MVI8] dealing with this parameter regime.
We can circumvent this technical problem by combining our main result (Theorem
1.5) with
Fact 1.7 to obtain the following sharper SQ lower bound (see Appendix C foor the proof).
Theorem 1.8 (SQ Lower Bound for List-Decoding the Mean). Let X (0,1) and n, E N with d be even and d < n². Let > O and n be at least a sufficiently large constant depending There exists ca > such that for any a > 0 sufficiently small the following holds. Any SQ algorithm that is given access to (1 ccorruppe Gaussian N(u, I) in n dimensions and returns list of hypotheses such that with probability at least 2/3 one of the hypotheses is within En-dittacce caa -1/d of the true mean μ. does one of the following: (i) Uses queries with error tolerance at most Oa(n ((1))(((1))80))))) (ii) Uses at least nn many hypotheses.
c.
Die)
many queries. (iii Returns a list of at least cxp()((n))
inti-concentration Detection Anti-concentration (AC) detection is the following hypothesis test- ing problem: given access to an unknown distribution D over R", where the input distribution D is promised to satisfy either (i) D is the standard Gaussian; or (ii) D has at least < 1 of its probabil- ity mass residing inside a dimension (n 1) subspace V c R". The goal is to distinguish between the two cases with success probability 2/3.
order to use our main result to derive an SQ lower bound for this task, we require the follow- ing lemma on univariate moment-matching (see Appendix C for the proof).
3

---

Lemma 1.9. Let Do denote the distribution that outputs with probability 1. For d Z4,, there exists ad E (0, 1) and a univariate distribution A = aaDo + (1 o.) for some distribution E, such that the first d moments of A agree with those of (0, 1). Furthermore, the pdf of E can be taken to be pointwise at most twice the pdf of the standard Gaussian.
Using the above lemma and our main result, we can deduce the following SQ lower bound on the anti-concentration detection problem (see Appendix for the proof).
Theorem 1.10 (SQ Lower Bound for AC Detection). For any a E (0,1/2), any SQ algorithm that has access to a n-dimensional distribution that is either (i) the standard Gaussian; or (ii) distribution that has at least a < 1 probability mass in a (n-1 (t-1)-dimensional subspace V C RR, and distinguishes the two cases with success probability at least 2/3, either requires query with error at most n -wa (1), or uses at least 2nh() many queries.
Learning Periodic Functions Another application is for the well-studied problem of learning periodic functions, see, e.g., [SVWX17] and [SZB2I], which is closely related to the continuous Learning with Errors (cLWE) problem [BRST2I]. In the task of learning periodic functions, the algorithm is given sample access to a distribution D of (x, y) over R" x R. The distribution D is such that ~ *N I,) and y c2s(2 (w. x) + ()) with noise
NNO, o²). This implies that y is a periodic function of x along the direction of w with a small amount of noise. While the frequency and noise scale parameters ó, a R++ are known to the algorithm, the parameter
w E gn-1 is unknown; the goal of the algorithm is to output a hypothesis h : IR" + R such that Ex~D[(h(x) =)²] is minimized.
order to use our main theorem to derive an SQ lower bound for this problem, we need to show that for any E [-1, 1], D conditioned on y t approximately matches moments with N(0. I.). To this end, we introduce the following definition and fact of discrete Gaussian measure from DK22al
Definition 1.11. For s E R. and E R, let G..0 denote the measure of the "s-spaced discrete Gaussian distribution". In particular, for each E Z. G..0 assigns mass sg(ns + 8) to the point ns + 0, where g is the pdf function of (O 1).
Note that although Gs.o is not probability measure (as the total measure is not one), it can be thought of as a probability distribution since the total measure is close to one for small a. To see this, we introduce the following fact.
Fact 1.12 (Lemma 3.12 from DK22al) For all l E N, > 0 and all 0 E R. we have that (Eo,,1 E
(s)( exp(=S(1/>2)).
Using the above fact, we are now ready to prove our SQ lower bound for learning periodic functions (see Appendix for the proof).
Theorem 1.13 (SQ Lower Bound for Learning Periodic Functions). Let e >> 0 and be at least sufficiently large constant depending on c. Let D be the distribution of (x. y) over RR x IR that is generated by x (O, In) and y cos(2n(6 a be known and w be unknown to the algorithm. Then any SQ algorithm that has access to the distribution D and returns hypothesis h R R such that E(xx))-D(((()) y) o(), either requires a query with error at most exp(-n" -n d' < min(2e, 1/10), or uses at least 20)) many queries.
+ {)) with noise C ~~ (O, o²). Let 8 > n²,
1.2 Technical Overview
We start by noting that we cannot use the standard SQ dimension argument [FGR + 17] to prove our result, due to the unbounded chi-squared norm. To handle this issue. we need to revisit the underlying ideas of that proof. In particular, we will show that for any bounded query function f: R. - [-1, 1]. with high probability over some
UO,,,,. it holds that [Ex-A, [f()) E [f will be small. This allows an adversarial oracle to return Ex-N,, [x)) to every query / regardless of which case we are in, unless the algorithm is lucky enough (or uses high accuracy) to find an f that causes Ex [/(x) - Ex-P3 [x)] to be at least T.
Our approach for calculating E Ex~p3lf(x) will be via Fourier analysis. In particular, using the Fourier decomposition of f, we can write fxx) Ex (Te, H₂ (x)), where (x(x) is the

---

properly normalized degree-k Hermite polynomial tensor and Tç is the degree-k Fourier coefficients of f. Taking the inner product with the distribution py involves computing the expectation of
Ex-Pe H&(x)), which can be seen to be (V As, Tk), where A = Ex~A(H+(x))) Thus, we obtain (at least morally speaking) that
Ex Ex [f(xx]) = =E (V A
TA)
S
Σ (Ax (VT) M TTY S k==
A Axllel((V)))
8*
Tall2- (I)
k=0
kmm
The kt 0 term of the above sum will be exactly To- Ex [xx].. By the moment-matchin condition, the k = 1 through &o- = d terms will be very small. Finally, we need to argue that the higher degree terms are small with high probability. To achieve this, we provide non-trivial upper bound for (v- (V. (rrTT [3]. Combining with the fact that Σx= |T&ll = II513 S 1,
this allows to prove high probability bounds on each term, and thus their sum.
Furthermore, if we want higher probability estimates of the terms with small k, we can instead bound Ev~u(O.... (VT) (yT)@TTxll2 for some integer Unfortunately, there are non-trivial tech- nical issues with the above approach, arising from issues with [ To begin with, as no assumptions other than moment-matching (for a few low-degree moments) were made on A, it is not guaranteed that A₃ is finite for larger values of k. To address this issue, we will truncate the distribution A. In particular, we pick parameter B (which will be determined carefully), and define A' to be A conditioned on the value in the ball 18*h (B). Due to the higher-moment bounds, we can show that A and A' are close in total variation distance, and thus that Exxpy [fx) is close to Ex-Py [f (x) for any bounded f.
Furthermore, using the higher moment bounds, we can show that A' nearly matches the low- degree moments of Nm- The second issue arises with the interchange of summations used to de- rive ① In particular, although fxx = Ek=o (T H4 (x)), it does not necessarily follow that we can interchange the infinite sum on the right-hand-side side with taking the expectation over x ~ Pt- To fix this issue, we split f into two parts fse (consisting of its low-degree Fourier components) and fzt We note that (I) does hold for f as the summation there will be finite, and we can use the above argument to bound Ex-N,, (x)] - Ex-p [ff((())] with high probability. To bound 1E [x>((x]]] we note that by taking large, we can make || < 8 for some exponentially small 5 >> O. We then bound Ey~U((.... ( Px [[]**[]] = Ex=Ql1/>*1,, where Q is the average over of p (note that everything here is non-negative, so there is no issue with the interchange of integrals). Thus, we can bound the desired quantity by noting that || is small and that the chi-squared norm of Q with respect to the standard Gaussian N₂, is bounded.
2 Preliminaries
We will use lowercase boldface letters for vectors and capitalized boldface letters for matrices and tensors. We use g--1 {x E " : ||x||2 = }} to denote the ne-iimensional unit sphere. For vectors u. E IR", we use vu to denote the standard inner product. For E R", we use ||ul|a = (>, 1 ) 1/ks to denote the f*-norm of u. For tensors, we will consider a k-tensor to be an element in (R=))* = R=* This can be thought of as a vector with n coordinates. We will use Air...ii to denote the coordinate of a k-tensor A indexed by the k-tuple (ii...., .x). By abuse of notation, we will sometimes also use this to denote the entire tensor. The inner product and (*-norm of k-tensor are defined by thinking of the tensor as vectors with n² coordinates and then use the definition of inner product and g norm of vectors. For a vector v E I",, we denote by v&k to be vector (linear object) in _=*., For matrix V E IR we denote by ||V| || to be the operator norm and Frobenius norm respectively. In addition, we denote by Vosk to be a matrix (linear operator) mapping R=* to Rm We use 1 to denote the indicator function of set, specifically 1( E 5) = l E S and 0 otherwise. We will use I' : R + R to denote the gamma function T(2) = _ f--lleed
We use B R B(2,, 22) = ((2)))())TTTC + 22). We use X to denote the chi-squared distribution with degrees of freedom. We use Beta(a, 8) to denote the Beta distribution with parameters and B.
> R to denote the beta function
5

---

For distribution D, we Prp[S] to denote the probability of event S. For continuous distribution D) over RR, we sometimes use D for both the distribution itself and its probability density function. For two distributions D1, D2 over a probability space 12, let drv (D1, D2) supsçn PPD, (S) - Prp, (S)] denote the total variation distance between DI and Dz. For two continuous distribution Di, D2 over Ik." we use (D,, D2) = Sg- Di(x)²/D2(x)) the chi-square norm of D w.r.t. D2. For subset S Rn with finite measure or finite surface
to denote
measure, we use (S) to denote the uniform distribution over S (w.r.t. Lebesgue measure for the volumn/surface area of 5).
Basics of Hermite Polynomials
Definition 2.1 (Normalized Hermite Polynomial). For k E N. we define the k-th probabilist's Henmite polynomials Hex I + R as Hex = (-1)& de -//2 We define the k-th normalized Hermite polynomial h4 IR (t) = (e)
+2/2,
Furthermore, we will multivariate Hermite polynomials in the form of Hermite tensors (as the entries the Hermite tensors are rescaled multivariate Hermite polynomials). We define the Hermite tensor as follows.
Definition 2.2 (Hermite Tensor). For E and x E R we define the k-tth Hermite tensor as
(H₂ (x)) (x))
Σ
X
Vk!
Partitions P of [k] (a.D)EP
{otEP
into
We denote by I,2(TR",N,, the function space of all functions f : IR" + such that Ev,,, [f*(v)) < For functions f,g E [2 ,Nn), use (f.9)N. Ex~N. (f()g(() denote their inner product. We use ll.l|2
f),.f),. to denote its - For func- tion f R" + R and l E N. we use fكt to denote f5((x) -i=o(An (Ax, (x))), where A = Ex~N, [x))), which is the degree-l approximation of f. We use f fst to denote its residue. We remark that normalized Hermite polynomials (resp. Hermite tensors) form complete orthogonal system for the inner product space (R, (resp. L (N,)). This implies that for f E (RR"", (R",,,,) .N,), lim |f = O. We also remark that both our definition of Her- mite polynomial and Hermite tensor are "normalized". In the sense that for Hermite polynomials, || = 1. For Hermite tensors, given any symmetric tensor A, we have (A, H& (x) = (A, A). The following claim states that for any orthonormal transformation B, the Hermite tensor (Bx) be written as applying the linear transformation B on the Hermite tensor Hx(x). The proof deferred to Appendix
Claim 2.3. Let 1 < < n. Ler B E RR with BB Im It holds that Ha(Bx) B Ha (x), x E R".
3 SQ-Hardness of NGCA: Proof of Theorem 1.5
The main idea of the proof is the following. Suppose that the algorithm only asks queries with tolerance r. and let f be an arbitrary query function that the algorithm selects. The key ingredient is to show that Ex-P3 [xx] Ex~NN, [x)]]
with high probability over V ~ U(O,,m). ). If this holds, then when the algorithm queries if the input is from the alternative hypothesis, with high probability, Ex-,N_ [x] is a valid answer for the query. Therefore, when the algorithm queries f. regardless of whether the input is from the alternative Ex-N,, [x()]. Then the algorithm will not observe any difference between the two cases with any small number of queries. Thus, is impossible distinguish the two cases with high probability. To prove the desired bound, we introduce the following proposition.
null hypothesis, the oracle can just return
Proposition 3.1. Let X 10. and m, d E N with be and m. d S n.. Let v R. and be a distribution on ! such that for any polynomial f T + F. of degree at most d and Ex-NN [f(x)²]=
[[xx(](x)] Ex [f(x)) Vv.

---

Let < (1 x)/8 and at least sufficientll large constant depending on G, then, for any function f R_ >> 1,,, II, it holds
T( ( 2
Pr V~U(O,,,)
E x-PV
[f(x)] - E
[f(x)] x
2
n (
(1000++111000 (1+ (1+)
< 22-1
r ((2)
mm)
Assuming Proposition 3.1 the proof of our main theorem is quite simple.
Proof for Theorem 1.5 Suppose there is an SQ algorithm A using < 2n 2n many queries of ac- curacy r 2 T(m/2) n (001-A/8--al + (1 [1++ o(1)) and succeeds with at least 2/3 probability. We prove by contradiction that such AA cannot exist. Suppose the input distribution is Nr,, and the SQ oracle always answers Ex-N, [x)) for any query f- Then the assumption on A implies that it answers "null hypothesis" with probability a 2/3. Now consider the case that the input distribution is PV and V ~ nO.,,m) Suppose the SQ oracle still always answers Ex~N,, [x()
m
for any query f. Let f1, fg be the queries the algorithm asks, where q 2 2(0) By Proposition 3.1 and union bound, we have
PIv.-UOo... E [a]. [ExPP [[()]] Ex-A,, [f(x)] 2 = o(1)
Therefore, with probability 1- ((1), the answers given by the oracle are valid. From our assumption on A, the algorithm needs to answer "alternative hypothesis" with probability at least 2 ((1))
But since the oracle always answers Ex~As, [f()) (which is the same the above discussed null hypothesis case), we know the algorithm will return "null hypothesis" with probability a > 2/3.
This gives contradiction and completes the proof.
The rest of this section is devoted to the proof of Proposition 3.1
3.1 Fourier Analysis using Hermite Polynomials
The main idea of Proposition 3.1 is to analyze Ex (x))] through Fourier analysis using Hermite polynomials. Before do the analysis, we will first truncate the distribution A inside 3T' (B) which is the f2-ormm unit ball in m-dimension with radius B for some B E 14 to be specified. Namely, we will consider the truncated distribution A' defined as the distribution of x A conditioned on x E 1 (B). The following lemma shows that given any m-dimensional distribution A that approximately matches the first moment tensor with the Gaussian, the truncated distribution A' is close to A in both the total variation distance and the first d moment tensors.
Lemma 3.2. Let n, m, d E N with d be even. Let A be a distribution on Ihm such that for any polynomial I of degree most d and Ex-N [x())] 1,
(x)] - Ex [f())] 2
where ei is least a sufficiently large universal constant and let A' be the truncated distribution defined as the distribution of x A conditioned on E IBTH (B). Then drv (A, O 22//2
Let B R. such that Bd 2 c1 22/22 F(d+m/ (2)
T(m/2)
Tld+m/2)
B-d, Furthermore, any k E N and k < d,
T(m/2)
T(d+ m/2) T(m/2)
Ex (H Ex HA (x)]l2= (0))) 24/2
B (-(d-k) +v.
The proof of Lemma 3.2 is deferred Appendix
B
Since (A, < 0 2d/2
l(d+m/2)
B B-d and f is bounded in [-1, 1], it follows that
((m/2)
E x [f(x)] Ex- [f(]]] S 2drv
P = 2dry (A,
=0 (
22/2
l'dd + m/2)
B-d
T(m/2)
7

---

Therefore, if suffices for us analyze E xx-Py [x)) instead of Ex-Pp [[()]. Furthermore, the property that A' is bounded inside IB" (B) will be convenient in the Fourier analysis later. We introduce the following lemma which decomposes E Ex~Px' [[(x) using Hermite analysis. The proof deferred to Appendix
Lemma 3.3 (Fourier decomposition Lemma). Let A' be any distribution supported on R V E R and VTV Im Then for any i E N, E Px-pxlf(xx) = Ei=o (Vok E Px (F>(() where A₁ = Ex (H&(x)) and Tr = Ex-NG Ex-N,,1 (x)))
( Ag. Ta) +
Remark 3.4. Ideally, in Lemma 3.3. would like have Ex [[()) O Ax, T&). However, since we do not assume that (A',, < co, this convergence may not hold.
Recall that our goal is to show that [ (xxP3(((x)) - Ex~N. is small with high probability. Observe that (x of Ei=of (V Ak. Tx) (since Ao 1). Therefore, given Lemma 3.3 it suffices to show are both small with high probability. We ignore the E Xx (x)]l part for now as this is mostly a technical issue. To bound (V Ar, T&)1, it suffices to analyze Ei. (V As, Ta) by looking at each term Ak. Tx (As, (VT)@*Tx) S (A T 12 To show that the summation is small, given we need to prove that (with high probability):
To which is the first term in the summation
that E (Vi A TxYl and Px
E
(
1. || | does not grow too fast w.r.t k;
2. [[VV) (VV)@/TTT To decays very fast w.r. ls (is small with high probability w.r.t the randomness of V).
| does not grow too fast: We will slightly different arguments depending the size
of k. We consider three cases : k < m, k S (1-A)/4 and k 2 (1-A)//4 (the value in the exponent will deviate by small quantity to make the proof go through). For k < m, ||Aulle grows
slowly by the approximate moment-matching property of A'. For m S l < n (1-A)/4 we require the following fact:
Fact 3.5. Let Hg be the k-th Hermite tensor for m-dimension. Suppose
||x|| 2 m. then
|H (x)ll2 20(h) max([1 (|)x]
We provide the proof of Fact 3.5 in Appendix B For k > (1-A)/44 we can show that || does grow too fast by the following asymptotic bound Hermite tensors.
Fact 3.6. Let Hg be the k-th Hermite tensor for m-dimension, then (x)]22 S 20(m) (k+m== m
1/2 exp((1x[1/4).
We provide the proof of Fact 3.6 in Appendix B
[I(VT) & & la decays very fast: We show that KV & bounding its a-th moment for some even a. Notice that since |H |l/lll S 1, we can then combine it with the following lemma. We defer its proof to Appendix B
Txy is small with high probability by
Lemma 3.7. Let k E Z,, a E 24 be even, T E RR" and m E 24 satisfy m < n. Then, we have
Ev-u(O,, ( [IT ok T S Ev-u(o....)
[IVTu| ak/2
T
Roughly speaking, this is just the ak dk/2-th moment of the correlation between a random sub- space and a random direction. which can be upper bounded by the following lemma and corollary (see Appendix B for the proofs).
II( (I(=t)) (r()))(()))))))))))))))))))))(
Lemma 3.8. For any even N, and u E 8n-1, Evi |u e
( ((()"))(
8

---

We show Corollary 399. Let 1) and S n.. Let k E N be even. We have that
S 11
(V..UO...)IIITTTT exp( exp(-S((*))0 ((
(n4t (n-m)/2) k+n
A: 2 n.
To combine the above results and give the high probability upper bound on Ex=1 (A (VT) we require the following lemma. The proof is deferred to Appendix B
Lemma 3.10. Under the conditions of Proposition 3.1 and further assume d, m S n//logn, n,
< 2 and Tid/2+m/2) n (2-(2-))/-- < [(m/22
2. Then for any that is at least suffi-
ciently small constant depending on c, there is an a' < (1 X)/8 such that for any B n where a' aa- < (1 X)/8 the following holds. Let A' be the truncated distribution defined as the distribution of x A conditioned on x E (B). Then drv(A, A') S
T(d/2+m/22) ) n (01-((11))/--00 Furthermore for any &. E N, except with probability at most 2 1 Ol T(m/2)
W.E. V ~ U(On,m) Eis (AR, (VT) (TT)&TTa) = Tid/2+m/2) n - (J0--) + (1 (
where A = Ax [x)(x)] and Tç = Ex-N, (x))]
3.2 Proof for Proposition 3.1
We are now ready to prove Proposition 3.1 which is the main technical ingredient of our main result. Ex~xN, is small with high probability. The main
Proposition 3.1 states that idea of the proof is to use Fourier analysis on Ex-Po' [x(x as we discussed in the last section, where A' is the the distribution obtained by truncating inside (B)
(1 A1/8 c. We will analyze Ex~A H [x) by truncating A. Therefore, we will apply Lemma 3.10 here. However, notice T(d/2+m/2 l(m/2)
Proof for Proposition 3./ For convenience, we let
Lemma 10 additionally assumes d, m S n2/loogr v < 2 and
n -d
that all these three conditions can be assumed true WLOG. If either the second or the third condition not true, then our lower bound here is trivialized and is always true since f is bounded between [-1,+1], For d, m S n logn, consider a A > À such that (1 XX/8 - (1-2)/8-{ Then it easy to see for any sufficiently large n depending on (1 A)/8 118--- we have d, m s n^ /log and < (1 A)/8- - Ç. Therefore, we can WLOG apply Lemma 3.10 for X.
Now let B n where the truncated distribution A' defined as the distribution of x ~ conditioned on x E BB)().
(1 A)/8 is the constant in Lemma 3.10
Then consider
By Lemma 3.10 we have dAv(A, A') S
[(d/2+m/22) -Cd Given that f bounded between ((m/2)
[-1,1] 1], this implies Ex~Py [f() - Ex-PY' [f(x)] I (dT. = 2dT z
2 (ldd/2mm/2) ((m/2) n cd. Thus, it suffices for us to analyze E Ex [[(x)] instead of Ex~ [x())]
L (n) E N be function depending only on the query function f and the dimension n (6 to be specified later). By Lemma 3.3, we have that E Ex [f(x) = Ek KAr. (VT)@kTT)!
Ex-Po (f>((x))())) Recall that we want to bound Exxpp [fxx) Ex-NN, [xx)] with high proba- bility, where we note that Ex-,N, [x)) (Ao: To). Therefore, can write
E Ex [f(x)] Ex [x)]]
E
(Ax. (VT) VT) k)) + Ex
k=1
For the first term, by Lemma 3.10 we have that El (Ak, (VT) (Tld/2tm/2)
n cd
12(m/2)
(1 o(1)),, except with probability 2 2(e) 2(e)
It now remains for us to show that E P [f (x)]l is also small with high probability. Con- sider the distribution D Ev-U
[P4
The following lemma shows that D is continuous

---

and (D, is at constant only depending on (independent of the choice of the one dimensional distribution A).
Lemma 3.11. Let A be any distribution supported on (n) for n E M which is at least suffi- ciently large universal constant. Let D Ev-U((n... [P4] Then, D is continuous distribution and x ( (D,Nm) = (1).
Roughly speaking, the proof of the lemma follows by noting that the average over V of P spherically symmetric. We defer its proof to Appendix B.2 Using this lemma, we write
Ev-c((.....) ( If (x)]]] I Ev-u((o,,.)
E Px
(x)]] = Ex-D[If>
D(x)
| S +1+ || 12,
= =Ex>An
(x)
where the first equality holds due to Fubini's theorem. Furthermore, since xD, On,(), there is function 8: R Ie such that 1 + (D,,NN,) S 8(n). Therefore, we have that
Ev~U(On...) [ [ Ex (x)]] S / (D., 5
We can take = (n) (l only depends on the query function f and dimension n) to be a sufficiently large function such that || S 6(m)
((d/2+m/22) n n-
cd. Then we get
T(m/2)
[Td/2+mm//
112 Se_ Ev~u(On...) m E Py || (x)]]] S 1(1)1152*12
T(m/2) n nCa
This gives the tail bound Pry [ Ex [/>((x)]]
(T4/22+m22)
T(m/2) n n-(a]
[d] sen
Using the above upper bounds, we have
E Xx [f(x)] Ex,,, [f(x)] S (VTT) (VT)STTA) + E ExpPy (x²()))] T(d/2+ 1 m/2)
=2 T(m/2)
n cc (1 + o(1)),,
except with probability 2 R(3) As we have argued at the beginning of the proof,
T(d/2 + m/2)
E Ex-py [f()) - E xxp [f(x)] $
l(m/2) n cd
Therefore,
Ex-P3
[x(x) [xxx)][[(x]]
Ex-AN [/()]l 5 Tíd/2+m/2)) T(m/2) n1 -d + (1+0(1)))
+
sd
except with probability R0) < nn
9i)) given O(1).
In the end, notice that the above argument is still true if we take 5² > Ç such that (1-X)/8-
(1-x/8-5 Using the above argument for Ç' and given n a sufficiently large constant depending
2
(1 x)/8 < = 2((1 - 2)/8 5²). we get
[(d/22 + (ld/2+m/2) n -c + +1+ T(m/2)
BExPp [x(x)] NG [xx)]]|
except with probability 2- 201 21/01-11/8-1 21/8-(3) C)) 2 proof.
Replaceing with (1 A)/8 c completes the
10

---

References
06] G. Blanchard, M. Kawanabe, M. Sugiyama, V. Spokoiny, and K.-R. Müller. In search of non-gaussian components of high-dimensional distribution. Journal of Machine Learning Research, 7(9):247-22) 282, 2006.
[BRST21] J. Bruna, O. Regev, M. J. Song, and Y. Tang. Continuous LWE. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694-707. ACM, 2021.
[CLL222] S. Chen, Li, and Y. Li. Learning (very) simple generative models is hard. In NeurlPS, 2022.
[DH23] Ding and Y. Hua. SQ lower bounds for random sparse planted vector problem. In International Conference Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 558-596. PMLR, 2023.
[DK22a]
Diakonikolas and D. Kane. Near-optimal statistical query hardness of learning half- spaces with massart noise. In Conference on Learning Theory, volume 178 of Pro- ceedings of Machine Learning Research, pages 4258-4282. PMLR, 2022. Full version available at https//arri..orraas22111...7
[DK22b] Diakonikolas and D. Kane. Non-gaussian component analysis via lattice basis re- duction. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4535 4547- PMLR, 2022.
[DK23] I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge university press, 2023. Full version available at https///sttes.goglee www.gll..co/vviiw/assbboooo..ooo
[DKK I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In STOC '22: 54th Annual A ACM SIGACT Symposium on Theory of Computing, pages 874-885, 2022. Full version available at https//arxxi..rr/abs//2 108.07867.
[DKKZ20] Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and SQ lower bounds for PAC learning one-hidden-layer relu networks. In Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1514-1539. PMLR, 2020.
[DKP*21] Diakonikolas, D. M. Kane, A. Pensia, T. Pittas, and A. Stewart. Statistical query lower bounds for list-decodable linear regression. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 3191-3204, 2021.
[DKPZ21] I. Diakonikolass, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial re- gression for agnostic learning under gaussian marginals in the SQ model. In Conference Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Re- search, pages 1552-1584. PMLR, 2021.
[DKPZ23] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. SQ lower bounds for learning mixtures of separated and bounded covariance gaussians. The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume 195 of Proceedings of Machine Learning Research, pages 2319-2349. PMLR, 2023.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 73-84, 2017. Full version at http://arxiv.or/aab////a
1.03473.
[DKS18] Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1047-1060, 2018. Full version available at https://anii..rrg/a///11.1..1
11

---

[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2745-2754, 2019.
[DKS23] Diakonikolas, D. M. Kane, and Y. Sun. SQ lower bounds for learning mixtures of linear classifiers. CoRR, abs/2310.118777 2023.
[DK7200 Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnos- tically learning halfspaces and relus under gaussian marginals. CoRR, abs/2006.16200, 2020.
[Fel16] V. Feldman. Statistical query learning. In Encyclopedia of Algorithms, pages 2090- 2095. Springer New York, 2016.
[FGR + 17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2:::1-8:37, 2017.
[FGV17] V. Feldman, C. Guzman, and S. S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2017, pages 1265-1277 SIAM, 2017.
[GGJ+20] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. R. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 3587-3596. PMLR, 2020.
[GGK20] S. Goel, A. Gollakota, and A. R. Klivans. Ratistical-query lower bounds via func- tional gradients. In Advances in Neural Information Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurlPS 2020, 2020.
[GS19] N. Goyal and A. Shetty. Non-gaus Kon-gaussian component analysis using entropy methods. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, STOC 2019, pages 840-851. ACM, 2019.
[Kea98] M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6))983-, 1998.
[Kra04] I. Krasikov. New bounds on the Hermite polynomials. arXiv preprint math/0401310. 2004.
[MV18] M. Meister and G. Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1530-1546. PMLR, 2018.
[SVWX17] L. Song,
Vempala, J. Wilmes, and B. Xie. On the complexity of learning neural networks. In Advances in Neural Information Processing Systems 30: Annual Con- ference on Neural Information Processing Systems 2017, NeurIPS 2017, pages 5514- 2017.
2017.
[SZB21] M. Song, Zadik, and J. Bruna. On the cryptographic hardness of learning sin- gle periodic neurons. In Advances in Neural Information Processing Systems 34: An- nual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 49602-29615, 2021.
[TV18] Y. S. Tan and R. Vershynin. Polynomial time and sample complexity for non-gaussian component analysis: Spectral methods. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 498-534.
PMLR. 2018.
[Va184] I. Valiant. theory of the learnable. Communications the ACM, 1984.
12

---

[ZSWB22] I. 7adik, J. Song, A. Wein, and J. Bruna. Lattice-based methods surpass sum-of- squares in clustering. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1247-1248, PMLR, 2022.
13


Reviews:
[{"review_id": "xVkr4EHgYr", "reviewer": "Reviewer_nJue", "summary": "\n\n\nThe paper discusses SQ lower bounds for Non-Gaussian component analysis. A very influential result by [DKS17] has established an SQ-lower bound suggesting d^m time as long as the non-Gaussian component's distribution A, satisfies (a) that the first m moments of A match the m moments of N(0,1) and (b) the \\chi^2 between A and N(0,1) is finite.\nThe authors prove that the same SQ lower bound holds under only condition (a) [i.e., without assuming condition (b)]\n\n## Correctness\n\nFrom my quick check, the argument appears correct and sound. \n\n", "questions": "My understanding is that by removing the \\chi^2 assumption, the authors result also shows that SQ algorithms fail even when the support of A is finite. This is a quite interesting case, as it includes examples of A supported on a lattice, where lattice-based methods work in polynomial time (e.g. see [Zadik et al' Lattice-Based Methods Surpass Sum-of-Squares in Clustering], , [Diakonikolas et al' Non-Gaussian Component Analysis via Lattice Basis Reduction]). Hence, this implies a separation between SQ methods and poly-time methods in NGCA. In case that is not already known, I encourage the authors to add this interesting implication of their result.", "limitations": "See above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the result very nice and the contribution a crucial addition to the literature. \n\nIt is quite interesting that the authors follow a direct approach, not using the \"standard\" SQ dimension approach introduced in [Feldman et al '2017].", "weaknesses": "A weakness is perhaps that the SQ lower bound technique seems to be very tailored to NGCA, as opposed to the Feldman et al 2017 result. ", "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 positive assessment of our work. We would like to address the following questions/comments.\n\n1. Regarding the reviewer’s point: \n“A weakness is perhaps that the SQ lower bound technique seems to be very tailored to NGCA, as opposed to the Feldman et al 2017 result.”\n\nThe focus of our work is on the problem of NGCA. Specifically, we show that under the moment-matching assumption the NGCA problem is SQ-hard. We note that a wide range of learning problems have at their core “hard instances” that can be formulated as specific instances of NGCA – for an appropriate choice of the moment-matching distribution $A$; see, e.g., lines 66-74 and the associated references. As a corollary, our result implies SQ-lower bounds for all these problems. \n\nOn the other hand,  [FGR+17] defines a notion of “SQ-dimension” and shows that “large SQ dimension implies SQ-hardness”. The notion of SQ dimension in that work is not sufficient for our setting. Moreover, even if the “SQ-dimension” of [FGR+17] had been sufficient (via an appropriate modification), one would need to establish that the NGCA problem has a “large SQ dimension” — which is the main technical contribution of our work. In summary, we believe that our contribution is incomparable with that of [FGR+17]. \n\n2. Regarding the reviewer’s point:\n“This is a quite interesting case, as it includes examples of A supported on a lattice, where lattice-based methods work in polynomial time (e.g. see [Zadik et al' Lattice-Based Methods Surpass Sum-of-Squares in Clustering], , [Diakonikolas et al' Non-Gaussian Component Analysis via Lattice Basis Reduction]). Hence, this implies a separation between SQ methods and poly-time methods in NGCA. In case that is not already known, I encourage the authors to add this interesting implication of their result.”\n\nThe reviewer is correct. As a corollary of our result, it follows that for the case of discrete distribution $A$, efficient SQ algorithms for NGCA do not capture all polynomial-time algorithms. In particular, the LLL-based algorithm in the aforementioned works is not efficiently implementable in the SQ model. (Interestingly, the same separation holds for low-degree polynomial tests and Sums-of-Squares algorithms.) We will add an appropriate remark in the revised version of our paper.\n\nReference:\\\n[FGR+17]  V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8:1–8:37, 2017."}, {"review_id": "BIdevRRViL", "reviewer": "Reviewer_YVEY", "summary": "The paper considers the SQ-hardness of non-Gaussian component analysis. The main result of the paper is a statement of the hardness without an assumption required by results stated in previous works: finite chi-squared distance between the non-gaussian distribution and the standard normal. Two applications are discussed. The bulk of the paper is focused on proof techniques, which makes use of Fourier transforms and Hermite polynomials to bound expected values of query functions.", "questions": "Some additional comments and questions:\n\n1. Possible typo on Line 289: \"i-th\" might have been a typo of \"k-th\".\n\n2. Lemma 3.10 requires that $d$ \"is at least a sufficiently large universal constant.\" How large does $d$ need to be in order for the results in the paper to be applicable?", "limitations": "There are limited discussions on limitations available in the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The main result of the paper by itself is interesting enough to be the greatest strength of the paper. \n\nOriginality. While the topic of hypothesis testing of NGCA in the Statistical Query (SQ) model is not new, and it has been known that the problem itself is SQ hard, this paper removes one of the main assumptions required for results in previous works to hold. From this perspective, the paper provides original contributions to the field.\n\nQuality. The quality of the paper is quite nice. The paper does a good job in describing the problem formulation, downfalls of past approaches, and definitions of the various technical tools required to establish the proof of the main result. \n\nClarity. The paper is well written and evidently polished. The main contributions of the paper are well stated and clear. The proof sections in the last few pages of the paper may need a bit more revision to be better readable.\n\nSignificance. The main results of the paper are widely applicable to various areas of machine learning theory.", "weaknesses": "Overall, the paper is nicely written. Some (minor) comments on weaknesses of the paper are:\n\n1. It is stated in the paper that the main result is \"near-optimal\". Can some elaborations be made on what is the \"optimal\" result, and, what are the technical difficulties causing the discrepancy between the results in this paper and the \"optimal\" result?\n\n2. Discrepancy in order of Theorem 1.8: the results in the paper give a tolerance requirement of the order \"$Ω(d)^{−k/32}$\" on $d$ while Fact 1.6. has the order \"$Ω(d)^{-(k+1)(1/4-c/2)}$\". In cases where $c$ is closer to $1/2$ it appears that the previous result is tighter, while the opposite is true when $c$ is closer to $0$. What is causing the discrepancy and why is this not reflected in the original comparison in line 62, i.e., is the order of magnitude listed in the equation on line 62-63 inaccurate?", "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 positive assessment of our work. We would like to address the following questions/comments.\n\n1. Regarding the reviewer’s point:\n“It is stated in the paper that the main result is \"near-optimal\". Can some elaborations be made on what is the \"optimal\" result, and, what are the technical difficulties causing the discrepancy between the results in this paper and the \"optimal\" result?”\n\nOur result is “near-optimal” in the sense that it is optimal up to a constant in the exponent — since one can solve the NGCA in $d^{O(k)}$ time. In fact, we believe that with the same approach but a more careful analysis, one can get a lower bound of $d^{ck}$, where c is any constant smaller than $1/8$ (and that the constant of $1/8$ cannot be improved in general). \n\n2. Regarding the reviewer’s point:\n“For the comparison between Fact 1.6 and Theorem 1.8, why is Fact 1.6 better for $c$ close to $0$ and Theorem 1.8 better for $c$ close to $1/2$?”\n\nWe believe this statement is actually not entirely accurate. Fact 1.6 uses the SQ lower bound in [DKS17], so the lower bound there in fact is roughly $\\exp(O(\\alpha^{-2/k}))d^{-k/(1/4-c/2)}$, where the extra $\\exp(O(\\alpha^{-2/k}))$ term corresponds to the chi-square distance of the one-dimensional distribution $A$ in the construction. So, if $\\alpha\\ll\\log(d)^{-k/2}$, regardless of the choice of $c$, Fact 1.6 will always fail to give any nontrivial bound. In contrast, Theorem 1.8 can still give a nontrivial lower bound. Indeed, there are some parameter regimes where Fact 1.6 will give a quantitatively slightly better bound than Theorem 1.8 (up to a constant in the exponent). This is due to the fact that our main result is proved for any one-dimensional distribution $A$ — while the prior result of [DKS17] is proved only for one-dimensional distributions $A$ with finite chi-square distance. This allows [DKS17] to obtain a better constant factor in the exponent, but at the same time costs an extra multiplicative “chi-square distance term”.\n\n3. Regarding the reviewer’s point:\n“Possible typo on Line 289: \"$i$-th\" might have been a typo of \"$k$-th\".”\n\nThank you for pointing out the typo. We will address it in the final version.\n\n4. Regarding the reviewer’s point:\n“Lemma 3.10 requires that “$d$ is at least a sufficiently large universal constant.\" How large does $d$ need to be in order for the results in the paper to be applicable?”\n\nWe need $d$ to be at least 10 so that Lemma 3.10 is true. Note that since $d$ is the dimension in the NGCA problem, if $d$ is smaller than 10, then for any number of matching moments $k$ only depending on $d$, the problem can always be solved in $d^{O(k)}$ time (which is constant time). Therefore, the main result Theorem 3.1 is applicable for any $d$ (since if $d$ is small, then the constant is absorbed in the big-O notation). \n"}, {"review_id": "Qovg2DMQGW", "reviewer": "Reviewer_oUue", "summary": "This work studies non-Gaussian component (NGCA) analysis in the context of the statistical query model. In NGCA the task is to distinguish a standard multi-variate Gaussian distribution from a distribution that is standard Gaussian in all but a random direction $w$ and equal to a one-dimensional distribution $A$ along $w$.\n\nPreviously, it was known that this problem is hard in the SQ model when\n1. $A$ matches many moments with the (one-dimensional) standard Gaussian,\n2. the $\\chi^2$-divergence between $N(0,1)$ and $A$ is finite.\n\nAlso, the quality of the lower bound depends on the $\\chi^2$-divergence: If this is very large with respect to other problem parameters (e.g., the dimension and the number of moments matched), the lower bound can potentially be weaker. \n\nIn their work, the authors show that Assumption (2) above is not necessary for the hardness result to hold. They use this to obtain an improved result for list-decodable mean estimation (when the inliers are Gaussian with identity-covariance). They further show SQ hardness of detecting whether a distribution has a constant fraction of its probability mass in a lower-dimensional subspace.\n\nOn a technical level, they are able to remove the assumption on the $\\chi^2$-divergence since they do not show hardness based on the SQ dimension (a widely used notion which implies SQ hardness), but rather show directly that every statistical query on the two distributions must receive the same answer up to some small error. They show this by carefully analyzing the Fourier moments of both distributions.", "questions": "In some of the existing SQ lower bounds using the NGCA framework it was very useful if the moments of $A$ only need to *approximately* match those of a standard Gaussian (e.g., the lower bounds for learning halfspaces under Massart noise in the distribution-independent setting). Are your techniques able to capture this scenario as well? If this is the case, it would be very helpful to include it in the main theorems since it would make them even easier to apply.", "limitations": "The authors give a fairly definitive answer to the question they studied.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In my eyes, the main strength of the paper is that it allows for more flexibility when using the NGCA framework. Second, it also makes it easier to apply. Since this framework has found numerous applications, I believe that many researchers will appreciate this result. On a conceptual level, it is pleasing to see that the $\\chi^2$-divergence condition is indeed just a technicality (and the \"true hardness\" comes from the moment-matching condition).\n\nI believe the result can lead to:\n1. improved lower bounds (since the $\\chi^2$-divergence did affect the quality of the lower bound),\n2. and simple(r) constructions (since we now have more flexibility).\n\nThe authors gave one example for each of the two in their paper.\n\nThe paper is generally well-written. The authors give a nice and easy-to-follow overview of the main result in Section 1.2. Their solution is very natural. The actual proofs are more technical, but this is shared with other SQ lower bounds using the NGCA framework.", "weaknesses": "Minor: While the quantitative improvement for the list-decoding lower bound is non-trivial, it appears only in a very restricted regime of parameters, when the fraction of inliers goes to 0 when the dimension grows.\n", "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 positive assessment of our work. We would like to address the following questions/comments.\n\n1. Regarding the reviewer’s point:\n“While the quantitative improvement for the list-decoding lower bound is non-trivial, it appears only in a very restricted regime of parameters, when the fraction of inliers goes to $0$ when the dimension grows.”\n\nWe point out that this setting of “small $\\alpha$” (e.g., subconstant in the dimension) is actually of interest in some applications, including in mean estimation. A concrete example in a related crowdsourcing setting is the COLT 2018 paper by Meister and Valiant [MV18] dealing with this  “small $\\alpha$” parameter regime.\n\n2. Regarding the reviewer’s point:\n“Does the technique here capture the scenario that $A$ only approximately matches moments with the Gaussian?”\n\nYes, our technique captures the approximate moment-matching scenario. The only difference in the statement and proof would be an extra term due the approximate matching-moment in all the calculations.\n\nReference:\\\n[MV18] M. Meister and G. Valiant. A Data Prism: Semi-verified learning in the small-alpha regime. In Conference on Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1530-1546. PMLR, 2018."}, {"review_id": "vE6xoCRppm", "reviewer": "Reviewer_g3gW", "summary": "This paper provides an SQ lower bound for the problem of distinguishing the standard Gaussian distribution from a distribution with a single non-Gaussian component, under relaxed assumptions compared to what was previously known. In particular, in prior work, similar SQ lower bounds were established in the case where the non-Gaussian component corresponded to any single-dimensional distribution $A$ whose low order moments match those of a standard Gaussian and the ($\\chi^2$) distance between $A$ and the standard Gaussian is bounded. In this work, the bounded ($\\chi^2$) distance assumption is removed.\n\nAs consequences of the main result, two additional SQ lower bounds are provided, one for List-Decodable Mean estimation and one for the problem of anti-concentration detection.\n\nThe approach is simple and consists of direct probabilistic bounds for the difference between the value of a statistical query under the Gaussian and the corresponding value under a distribution with a non-Gaussian component in a uniformly random direction. The bound is shown via Fourier analysis over the Hermite basis.", "questions": "1. My main question concerns the correctness of the main result. How does this result compare to Theorem 1.3 of [DK22]? Such a discussion should, in any case, be a part of the paper.\n\n2. Section 3 is quite dense and cannot be easily parsed, so it might be beneficial to substitute the proofs with proof sketches that contain less quantitative information (the full proofs can be moved to the Appendix).", "limitations": "The existence of an LLL-based algorithm for the problem in question [DK22] should be discussed thoroughly.\n\n[DK22]:  Diakonikolas, Ilias, and Daniel Kane. \"Non-gaussian component analysis via lattice basis reduction.\" Conference on Learning Theory. PMLR, 2022.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The problem is clear and well motivated. The claimed result is a strict improvement over prior work with some further applications.", "weaknesses": "The paper has several important weaknesses.\n\n1. The main result seems to contradict prior work (which is not cited in the paper), which raises serious doubts about its correctness. In particular, in Theorem 1.3 of [DK22] it is shown that non-Gaussian components that are far from the unit normal are detectable (even under the moment matching assumption). See also the discussion on page 2, paragraph \"Motivation of This Work\" of [DK22]. \n\n[DK22]:  Diakonikolas, Ilias, and Daniel Kane. \"Non-gaussian component analysis via lattice basis reduction.\" Conference on Learning Theory. PMLR, 2022.\n\n2. The presentation of related work contains inaccuracies. In particular, within the paragraph in lines 66-74, it is implied that all of the listed papers make use of results on the hardness of non-Gaussian component analysis (NGCA) to gain results for other problems. However, for example, [GGJ+20] does not even mention the problem of NGCA, but makes use of some appropriate combinatorial quantity (called statistical dimension) to arrive to their main result.\n\n3. The text in the introduction is sloppy and overly casual and section 3 is too technical. For example, lines 52-57 could use some polish and lines 148-153 give the impression that there are no further technical challenges, so the following paragraph becomes confusing. \n\n-- The authors addressed my main concern that their results seemed to contradict prior work.", "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 feedback on our work. We would like to address the following questions/comments.\n\n1. Regarding the reviewer’s point that the main result seems to contradict the algorithm in prior work [ZSWB22] and [DK22].\n\nIf we take the one-dimensional distribution $A$ in the NGCA to be a distribution with finite support and matching the first $k$ moments with the standard Gaussian, where $k$ is at least a sufficiently large integer, then the SQ lower bound given by our result will be larger than the algorithmic upper bound in [ZSWB22] and [DK22]. However, as also pointed out by reviewer nJue, the algorithms in [ZSWB22] and [DK22] are based on LLL lattice-basis-reduction which is not captured by the SQ framework, so this does not contradict our SQ lower bound result. \n\nAnother classical example is the exponential SQ-hardness of learning Parities, when a polynomial-time algorithm (based on Gaussian elimination) exists for the problem. Interestingly, the same situation holds for low-degree polynomial tests and SoS bounds (i.e., these restricted models of computation do not capture LLL or Gaussian elimination).\n\nWe would also like to point out that the above does not imply that any NGCA family of instances with infinite chi-square distance can be solved efficiently. Importantly, LLL-based algorithms only work in the restricted setting that the support of the one-dimensional distribution A is discrete/near-discrete. For example, if the one-dimensional distribution $A$ is a mixture of a discrete distribution and a continuous distribution (as is the case  in the Anti-concentration Detection problem considered in our paper), linear-algebraic algorithms will not work although the distribution has infinite chi-square distance and the problem is believed to be hard for all efficient algorithms. \n\n2. Regarding the review's point about presentation of Related Work:\n\nWithin the paragraph in lines 66-74, we have provided an extensive — but not exhaustive –  list of 12 papers using NGCA to establish SQ lower bounds. The reviewer points out that one of these papers, namely  [GGJ+20], does not explicitly use the NGCA problem. Upon inspection, one can see that the CSQ hard instance in [GGJ+20] uses a construction very similar to the concurrent work [DKKZ20] (which shows a quantitatively stronger lower bound for the same problem). The lower bound construction of [DKKZ20] explicitly relies on NGCA. This connection is discussed in the second to last paragraph of the “Our Techniques” section of [DKKZ20]. \n\nReference:\\\n[DK22] I. Diakonikolas and D. M. Kane. Non-Gaussian Component Analysis via Lattice Basis Reduction. In Conference on Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 4535-4547. PMLR, 2022.\\\n[GGJ+20] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. R. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 3587–3596. PMLR, 2020.\\\n[ZSWB22] I. Zadik, M. J. Song, A. S. Wein and J. Bruna. Lattice-Based Methods Surpass Sum-of-Squares in Clustering. In Conference on Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 1247-1248. PMLR, 2022.\n"}]

Author rebuttal:
We thank the reviewers for their time and effort in providing feedback. We are encouraged by the positive comments, and that the reviewers appreciated the paper for the following: (i) **importance** (YVEY), and (ii) **clarity** and **quality of writing** (YVEY, oUue). We would like to address the following question from the reviewers here.
1. “How does the main result of SQ lower bound for NGCA compare to the algorithms in [ZSWB22] and [DK22] which solve the NGCA when the hidden distribution is discrete?”

If we take the one-dimensional distribution $A$ in the NGCA to be a distribution with finite support matching the first $k$-degree moments with the standard Gaussian, where $k$ is at least a sufficiently large integer, then the SQ lower bound given by our result will be larger than the algorithmic upper bound in [ZSWB22] and [DK22]. However, as pointed out by reviewer nJue, the algorithms in [ZSWB22] and [DK22] are based on LLL lattice basis reduction which is not captured by the SQ framework, so this does not contradict our result. It is worth noting that not only the SQ model, but two other popular restricted computational models (lower-degree framework and SoS framework) also fail to capture the LLL lattice basis reduction. A comparison here can be made between the LLL algorithm and Gaussian elimination. While there is a classical exponential SQ hardness result for learning Parity functions, a polynomial-time algorithm based on Gaussian elimination can solve the problem. 

We would also like to point out that the above does not imply that any NGCA family of instances with infinite chi-square distance can be solved efficiently. Importantly, LLL-based algorithms only work in the restricted setting that the support of the one-dimensional distribution $A$ is discrete/nearly discrete. For example, if the one-dimensional distribution $A$ is a mixture of a discrete distribution and a continuous distribution (as is the case in the Anti-concentration Detection problem considered in our paper), linear-algebraic algorithms will not work although the distribution has infinite chi-squared distance and the problem is believed to be hard for all efficient algorithms. 

Reference: \
[DK22]  I. Diakonikolas and D. M. Kane. Non-Gaussian Component Analysis via Lattice Basis Reduction. In Conference on Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 4535-4547. PMLR, 2022.\
[ZSWB22] I. Zadik, M. J. Song, A. S. Wein and J. Bruna. Lattice-Based Methods Surpass Sum-of-Squares in Clustering. In Conference on Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 1247-1248. PMLR, 2022.


Meta-review: This paper provides a useful technical contribution to the area of statistical-computational gaps, by proving a more general/easier-to-use SQ lower bound for the task of non-Gaussian component analysis. This problem plays a key role in lower bounds for other problems and so seems likely to be useful for future works.  Discussion between the authors and reviewers identified some useful points concerning the relation to the LLL method which the authors have promised to include in the revision. Based on this, I recommend acceptance.
Decision: Accept (poster)