Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis

Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d. samples from a distribution$P_{v}^{A}$on$\mathbb{R}^{n}$that behaves like a known distribution$A$in a hidden direction$v$and like a standard Gaussian in the orthogonal complement, the goal is to approximate the hidden direction. The standard formulation posits that the first$k$- moments of$A$match those of the standard Gaussian and the$k$-th moment differs. Under mild assumptions, this problem has sample complexity$O(n)$. On the other hand, all known efficient algorithms require$\Omega(n^{k/2})$samples. Prior work developed sharp Statistical Query and low-degree testing lower bounds suggesting an information-computation tradeoff for this problem. Here we study the complexity of NGCA in the Sum-of-Squares (SoS) framework. Our main contribution is the first super-constant degree SoS lower bound for NGCA. Specifically, we show that if the non-Gaussian distribution$A$matches the first$(k-1)$moments of$\mathrm{N}(\mathrm{O},\ 1)$and satisfies other mild conditions, then with fewer than$n^{(1-\varepsilon)k/2}$many samples from the normal distribution, with high probability, degree$(\log n)^{\frac{1}{2}-o_{n}(1)}\mathbf{SoS}$fails to refute the existence of such a direction$v$. Our result significantly strengthens prior work by establishing a super-polynomial information-computation tradeoff against a broader family of algorithms. As corollaries, we obtain SoS lower bounds for several problems in robust statistics and the learning of mixture models. Our SoS lower bound proof introduces a novel technique’ that we believe may be of broader interest, and a number of refinements over existing methods. As in previous work, we use the framework of [Barak et al. FOCS 2016], where we express the moment matrix$M$as a sum of graph matrices, find a factorization$M\approx LQL^{T}$using minimum vertex separators, and show that with high probability$Q$is positive semidefinite (PSD) while the errors are small. Our technical innovations involve the following. First, instead of the minimum weight separator used in prior work, we crucially make use of the minimum square separator. Second, proving that$Q$is PSD poses significant challenges due to an intrinsic reason. In all prior work, the major part of$Q$was always a constant term, meaning a matrix whose entries are constant functions of the input. Here, however, even after removing a small error term,$Q$remains a nontrivial linear combination of non-constant, equally dominating terms. We develop an algebraic method to address this difficulty, which may have wider applications. Specifically, we model the multiplications between the “important” graph matrices by an R.-algebra, construct a representation of this algebra, and use it to analyze$Q$. Via this approach, we show that the PSDness of$Q$boils down to the multiplicative identities of Hermite polynomials.