Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis
Authors: Aaron Potechin
Goutham Rajendran
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sparse PCA
Sum of Squares
Tensor PCA
lower bounds

Abstract: Principal Components Analysis (PCA) is a dimension-reduction technique widely used in machine learning and statistics. However, due to the dependence of the principal components on all the dimensions, the components are notoriously hard to interpret. Therefore, a variant known as sparse PCA is often preferred. Sparse PCA learns principal components of the data but enforces that such components must be sparse. This has applications in diverse fields such as computational biology and image processing. To learn sparse principal components, it's well known that standard PCA will not work, especially in high dimensions, and therefore algorithms for sparse PCA are often studied as a separate endeavor. Various algorithms have been proposed for Sparse PCA over the years, but given how fundamental it is for applications in science, the limits of efficient algorithms are only partially understood. In this work, we study the limits of the powerful Sum of Squares (SoS) family of algorithms for Sparse PCA. SoS algorithms have recently revolutionized robust statistics, leading to breakthrough algorithms for long-standing open problems in machine learning, such as optimally learning mixtures of gaussians, robust clustering, robust regression, etc. Moreover, it is believed to be the optimal robust algorithm for many statistical problems. Therefore, for sparse PCA, it's plausible that it can beat simpler algorithms such as diagonal thresholding that have been traditionally used. In this work, we show that this is not the case, by exhibiting strong tradeoffs between the number of samples required, the sparsity and the ambient dimension, for which SoS algorithms, even if allowed sub-exponential time, will fail to optimally recover the component. Our results are complemented by known algorithms in literature, thereby painting an almost complete picture of the behavior of efficient algorithms for sparse PCA. Since SoS algorithms encapsulate many algorithmic techniques such as spectral or statistical query algorithms, this solidifies the message that  known algorithms are optimal for sparse PCA. Moreover, our techniques are strong enough to obtain similar tradeoffs for Tensor PCA, another important higher order variant of PCA with applications in topic modeling, video processing, etc.

Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis
Aaron Potechin University of Chicago potechin@uchicago.com
Goutham Rajendran" University of Chicago goutham@uchicago.. edu
Abstract
Principal Components Analysis (PCA) is diinension-reduction technique widely used in machine learning and statistics. However, due to the dependence the principal components all the dimensions, the components are notoriously hard interpret. Therefore, a variant known as sparse PCA is often preferred. Sparse PCA learns principal components of the data but enforces that such components must be sparse. This has applications in diverse fields such as computational biology and image processing. To learn sparse principal components, it's well known that standard PCA will not work, especially in high dimensions, and therefore algorithms for sparse PCA are often studied as a separate endeavor. Various al algorithms have been proposed for Sparse PCA over the years, but given how fundamental
for applications in science, the limits of efficient algorithms are only partially understood. In this work, we study the limits of the powerful Sum of Squares (SoS) family of algorithms for Sparse PCA. SoS algorithms have recently revolutionized robust statistics, leading breakthrough algorithms for long-standing open problems machine learning, such as optimally learning mixtures of gaussians, robust clustering, robust regression, etc. Moreover, it is believed be the optimal robust algorithm for many statistical problems. Therefore, for sparse PCA, it's plausible that it can beat simpler algorithms such diagonal thresholding that have been traditionally used. In this work, we show that this is not the case, by exhibiting strong tradeoff's between the number of samples required, the sparsity and the ambient dimension, for which SoS algorithms, even if allowed sub-exponential time, will fail to optimally recover the component. Our results are complemented by known algorithms in literature, thereby painting an almost complete picture of the behavior of efficient algorithms for sparse PCA. Since SoS algorithms encapsulate many algorithmic techniques such as spectral or statistical query algorithms, this solidifies the message that known algorithms are optimal for sparse PCA. Moreover, our techniques are strong enough to obtain similar tradeoffs for Tensor PCA, another important higher order variant of PCA with applications in topic modeling, video processing, etc.
Introduction
popular data processing and dimension reduction routine that is widely used. It has numerous applications in Machine Learning, Statistics, Engineering, Biology, etc. Given a dataset, PCA projects the data to lower dimensional space spanned by the principal components. The intuition is that PCA sheds lower order information such as noise
Principal components analysis (PCA) 62
"Equal contribution
A.... was supported in part by NSF grant CCF-2008920 and G.R. was supported in part by NSF grants CCF-181633 and CCF-2008920
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

but importantly preserves much of the intrinsic information present in the data that are needed for downstream tasks.
However, despite great optimality properties, PCA has its drawbacks. Firstly, because the principal components are línear combinations of all the original variables, it's notoriously hard to interpret them [84] Secondly, it's well known that PCA does not yield good estimators in high dimensional settings 13 97 61.
To address these issues, variant of PCA known as Sparse PCA is often used. Sparse PCA searches for principal components of the data with the added constraint of sparsity. Concretely, consider given data V1, V2,,,,,... U2,.... .... Um E RR In Sparse PCA, we want to find the top principal component of the data under the extra constraint that it has sparsity at most That is, we want to find a vector E I that maximizes > (v. vz)² such that ||o|| S k.
Sparse PCA has enjoyed applications in diverse range of fields ranging from medicine, compu- tational biology, economics, image and signal processing, finance and of course, machine learning and statistics (e.g. [117]
89
85
31 (2.. It's worth noting that in some of these applications, 115
other algorithms are also often used to learn statistical models with sparse structure, such as greedy algorithms (e.g. [60] 88 59 [24] ) and score- based algorithms (c.g. [28 90, [07]) but in this work, we focus on the widely used sparse PCA technique. Sparse PCA comes with the important benefit that the learnt components are easier to interpret. A notable example of this is recover topics from documents 55 Moreover, this has important benefits for algorithmic fairness in machine learning.
A large volume of research has been devoted to study Sparse PCA and its variants. Algorithms 73
have been proposed and studied by several works, e.g. 4
83
33
118
20, 82
34
[4
23
35
29 [36]]
For example, simple variants of PCA such as thresholding on top of standard PCA
66 29
work well in certain parameter settings. This leads to the natural question whether more sophisticated algorithms can do better either for these settings other parameter settings.
On the other hand, there have been works from the inapproximability perspective well (e.g.
[20 (54] 23 73 (35] [18]. (eecSinioon 3.1 for a more detailed overview) In particular, a lot of these inapproximability results have relied on various other conjectures, due to the difficulty of proving unconditional lower bounds. Despite these prior works, exactly understanding the limits of efficient algorithms to this problem is still an active research area. This is natural considering the importance of sparse PCA and how fundamental it is to a multitude of applications.
In this work, we focus on the powerful Sum-of-Square (SoS) family of algorithms [I3 92, 96 48 based on semidefinite programming relaxations. SoS algorithms have recently revolutionized robust machine learning, branch of machine learning where the underlying dataset is noisy, with the noise being either random or adversarial. Robust machine learning has gotten lot of attention in recent years because of its wide variety of use cases in machine learning and other downstream applications, including safety-critical ones like autonomous driving. For example, there has been a high volume of practical works in computer vision [14 47
121
50
112
122
42 76) and speech
recognition [57] 119 106 108 78 91 94). this important field, SoS has recently lead to brcakthrough algorithms for long-standing open problems [16
70
15
Highlights include
Robustly learning mixtures of high dimensional Gaussians. This an extremely important problem that has been subjected to intense scrutiny, with long line of work culminating in [16] 80].
Efficient algorithms for the fundamental problems of regression 770, moment estimation
(72), clustering [14] and subspace recovery [[5] in the presence of outliers. Also known as robust machine learning, this setting is more akin to real life data which almost always has outliers or corrupted data.
Moreover, SoS algorithms are believed to be the optimal robust algorithm for many statistical problems. In a different direction, SoS algorithms have led to the design of fast algorithms for problems such as tensor decomposition (53 IT.
Put more concretely, SoS algorithms, also known as the SoS hierarchy or the Lasserre hieararchy, offers a series of convex semidefinite programming (SDP) based relaxations to optimization problems. Due to its ability to capture a wide variety of algorithmic techniques, it has become fundamental tool in algorithms and optimization. It was and still remains an extremely versatile tool for combinatorial

---

optimization [46, 9 49 [022] but recently, it is being extensively used in Statistics and Machine Learning (apart from the references above, see also [7 [8 52
Therefore, we ask (also raised by and posed as an open problem in the works
82
54
55
Can -Quuares algorithms beat known algorithms for Sparse PCA?
In this work, we show that SoS algorithms cannot beat known spectral algorithms, even if we allow sub-exponential time! Therefore, this suggests that currently used algorithms such as thresholding or other spectral algorithms are sense optimal for this problem.
To prove our results, we will consider random instances of Sparse PCA and show that they are naturally hard for SoS. In particular, we focus on the Wishart random model of Sparse PCA. This model is more natural modeling assumption compared to other random models that have been studied before, such as the Wigner random model.
Note importantly that our model assumptions only strengthen our results because we are proving impossibility results. In other words, if SoS algorithms do not work for this restricted version of sparse PCA, then it will not work for more general models, e.g. with general covariance or multiple spikes. We now describe the model.
The Wishart model of Sparse PCA, also known as the Spiked Covariance model, was originally proposed by [6]] In this model, we observe vectors Ul,..., , E IR from the distribution N(0, la + Xumu") where u is k-sparse unit vector, that is, ||u|| S k and we would like to recover the principal component u. Here, the sparsity of vector is the number of nonzero entries and À is known as the hignal-t-nooise ratio.
As the signal to noise ratio gets lower, becomes harder and maybe even impossible to recover since the signature left by in the data becomes fainter. But it's possible that this may be mitigated the number of samples m grows. Therefore, there is a tradcoff between m, d, and À at play here. Algorithms proposed earlier have been able to recover at various regimes. For example, if the number of samples is really large, namely m >> max { ()) then standard PCA will work. But if this is not the case, we may still be able to recover u by assuming that the sparsity is not too large &² compared to the number of samples, namely m >> x². To do this, we use a variant of standard PCA known as diagonal thresholding. Similar results have been obtained for various regimes, while some regimes have resisted attack to algorithms.
Our results here complete the picture by showing that in the regimes that have so far resisted attack by efficient algorithms, the powerful Sum of Squares algorithms also cannot recover the principal component. We now state our theorem informally, with the formal statement in Theorem 3.1
Theorem 1.1. For the Wishart model of Sparse PCA, sub sub-exponential time SoS algorithms fail to recover the principal component when the number of samples m & min( d 8²
x x
In particular, this theorem resolves an open problem posed by
82 and
54
55
In almost all other regimes, algorithms to recover the principal component exist. We give summary of such algorithms in [Section 3] captured succinctly in Fig. We say almost all other d regimes because there is one interesting regime, namely XZ < m min(a.k) marked by light green in Fig. I where we can show that information theoretically, we cannot recover u but it's possible to do hypothesis testing of Sparse PCA. That is, in this regime, we can distinguish purely random unspiked samples from the spiked samples. However, we will not be able to recover the principal component even if we use an exponential time bruteforce algorithm.
techniques to also obtain strong results for the related Tensor Principal components analysis (Tensor PCA) problem. Tensor PCA, originally introduced by [11]]. is a generalization of PCA to higher order tensors. Formally, given an order k tensor of the form cu + B where E R is a unit vector and B E [R[n] has independent Gaussian entries, we would like to recover the principal component u. Here, À is known as the signal-to-noise ratio.
We
Tensor PCA is remarkably useful statistical and computational technique to exploit higher order moments of the data. It was originally envisaged to be applied in latent variable modeling
and indeed, it has found multiple applications in this context (e.g. [5] 68, 69 6). Here, tensor containing statistics of the input data is computed and then it's decomposed in order to recover the
latent variables. Because of the technique's 's versatility, it has gathered lot of attention in machine
3

---

Sparsity
Can hypothesis test spectrally but impossible recover u.
regime
Spectral
2ym
Diagonal thresholding
Diagonal thresholding (or)
Diagonal thresholding
(or)
Vanilla PCA
Spectral
Ambient diinension d
2m
2mm
(a) SNR À
Sparsity it
2m
Vanilla
regiiee
kym
Diagonal thresholding
Diagonal thresholding
(or)
Vanilla PCA
Ambient
2mm
Am
m
dimension d
(b) SNR À <
Figure I: Computational barrier diagram for Sparse PCA
learning with applications in topic modeling, video processing, collaborative filtering, community
detection, etc. (see c.g. [56] 7
38
79] and references therein.)
For Tensor PCA, similar sparse PCA. there has been wide interest in the community study
algorithms (c.g.
120 67 ()) as well as approximability and hardness (e.g. see Section 3.2 for more detailed overview). It's worth noting that many of these hardness results are conditional, that is, they rely on various conjectures, sometimes stronger than NP. Moreover, there has been widespread interest from the statistics community well, e.g.
22
52
53
110
125
88
75
58
9g
77
27), due to fascinating connections to random matrix theory and statistical physics. 26
In this work, we study the performance of sub-exponential time Sum of Squares algorithms for Tensor PCA. Our main result is stated informally below and formally Theorem 3.2
Theorem 1.2. For Tensor PCA, sub-exponential time SoS algorithms fail to recover the principal component when the signal to noise ratio < n
In particular, this resolves open question posed by the works 52 Therefore, main contributions can be summarized follows
22
54
55

---

1. Despite the huge breakthroughs achieved by Sum-of-Square algorithms in recent works on high dimensional statisties, we show barriers it for the fundamental problems of Sparse PCA and Tensor PCA.
2. We achieve optimal tradeoffs compared to known algorithmss, thereby painting a full pic- ture of the computational thresholds of tractable algorithms. This suggests that existing algorithms are preferrable for PCA and its variants.
3. Prior lower bounds for these problems have either focused on weaker classes of algorithms or were obtained assuming other hardness conjectures, whereas we prove high degree sub-exponential time SoS lower bounds without relying on any conjectures.
Acknowledgements and Bibliographic note We thank Sam Hopkins, Pravesh Kothari, Prasad Raghavendra, Tselil Schramm, David Steurer and Madhur Tulsiani for helpful discussions. We also thank Sam Hopkins and Pravesh Kothari for assistance in drafting the informal description of the machinery (Section C Parts of this work have also appeared in [99 104).
Sum-of-Squares algorithms
The Sum of Squares (SoS) hierarchy is powerful class of algorithms that utilizes the power of semidefinite programming for optimization problems, which has achieved breakthrough algorithms for many problems in machine learning and statistics. In this section, we briefly describe the sum of squares hierarchy of algorithms. For a more detailed treament with an eye towards applications to machine learning and statistics, see the ICM survey [[22] or the monograph [R]
Given an optimization problem given by program with polynomial constraints, the SoS hierarchy of algorithms gives a family of convex relaxations parameterized by an integer known as its degree. As the degree gets higher, the running time to solve the convex relaxation increases but on the other hand, the relaxation gets stronger and hence serves as a better algorithm. This offers a solve
smooth tradeoff between rumning time and the quality of approximation. In general, degree-D D.os sos SoS in (Dooo) time ff Therefore, constant degree SoS corresponds to polynomial time algorithms which in general translates to efficient algorithms. In this work, we focus on and show limitations of degree ne SoS which corresponds to subexponential running time.
Suppose are given multivariate polynomials p, .1.............................. Im variables ,1,..., (denoted collectively by x) taking real values. Consider the task:
maximize p(x) such that gi (x) = 0, O.... 9m (m( =0
In general, we could also allow inequality constraints, e.g., gi (x) 2 0. In this work, we only have equality constraints but much of the theory generalizes when we have inequality constraints instead.
We now formally describe the Sum of Squares hierarchy of algorithms, via the so-called pseudo- expectation operators.
Definition 2.1 (Pseudo-expectation values). Given multivariate polynomial constraints 91 9m on n variables F1...., Ina degree D sos expeedd-tpttttiion values are a linear map from polynomials of .1...., In of degree at most Deos to IR satisfying the following conditions:
1. [[1] =
2. iE[ 9i] = O for every E [m] and polynomial f such that deg(f 9:) S Dsos-
3. [B(s 2 for every polynomial J such that deg( S Dxos-
Any linear map É satisfying the above properties is known degree DEos pseudoexpectation operator satisfying the constraints 91 0, ...... Im = 0. ..........
The intuition behind pseudo-expectation values that the conditions on the -epueeeeppetttiion values are conditions that would be satisfied by any actual expectation operator that takes expected values over a distribution of true optimal solutions, so optimizing over pseudo-expectation values gives relaxation of the problem.
IIn pathological cases, there may be issues with bit complexity but that will not appear in our settings, For
details, 93 [0]
5

---

Definition 2.2 (Degree Do05 SoS). The degree Doos SoS relaxation for the polynomial optimization problem
Im maximize plz)) such that (ar) 9m =0 =0
is the program that maximizes Elp(æ)) over all degree Daos pseudoexpeetatiion operators E satisfying the constraints 91 .............................. 9m
The main advantage that the SoS relaxation can be efficiently solved via convex programming! In particular, [tem 3 Defimition 2. equivalent to matrix being positive semidefinite, therefore the degree D eos SoS relaxation can be done via semidefinite programming [16]. This meta-algorithm is known as a degree- Sagree-Dao> SoS algorithm. This algorithm runs in n ((D..))>) time Therefore, constant degree SoS can be solved in polynomial time. In the next section, apply SoS on PCA and formally state our results.
2.1 Related algorithmic techniques
Statistical Query algorithms Statistical query algorithms another popular restricted class of algorithms introduced by [66]. In this model, for a given data distribution, we are allowed to query expected value of functions. Concretely, for dataset D on IR" we have access it via an oracle that given as query function f R" + [-1, 1] returns Ex-D fz) up to some additive adversarial error. SQ algorithms capture a broad class of algorithms in statistics and machine learning and have been used to study information-cone computttionnootttttttiiii tradeoff's [109] 40 30 There has also been significant work trying to understand the limits of SQ algorithms (e.g. 40
34)). )). Formally, SQ algorithms and
SoS are in general incomparable. However, the recent work 25 showed that under mild conditions,
low-degree polynomial algorithms (defined next) and statistical query algorithms have equivalent power. But also, under these conditions, it's easy to see that SoS is more powerful algorithm than low degree algorithms and hence, SoS algorithms are stronger than statistical query algorithms. Therefore, SoS lower bounds as shown in this work give strictly stronger evidence of hardness than SQ lower bounds.
Low degree polynomial algorithms In statistics, a hypothesis testing problem is a problem where the input is sampled from one of two distributions and we would like to identify which distribution it was sampled from. In this setting, low degree polynomial a algorithm is to compare the expectation of low-degree polynomial to try and distinguish the two distributions. This method has been used to conjecture hardness thresholds for various problems [54]] (55] 75]. However, under mild conditions, the SoS hierarchy of algorithms is more powerful than low degree polynomial algorithms [54] and therefore potentially yields better algorithms. Therefore, the SoS lower bounds shown in this work
are stronger than low degree polynomial lower bounds as well.
3
Lower bounds for Sparse Principal Components Analysis
In this section, we will state our main results for Sparse PCA and Tensor PCA.
3.1 Sparse PCA
We recall the setting of the Wishart model of Sparse PCA: We are given ui...., Um E Rd sampled from NO0 Ia + Xuu²) where u is k-sparse unit vector and we wish to recover u.
We will further assume that the entries of u are in { -े- O, + chosen such that the sparsity is l (and hence, the norm is 1). Note importantly that this assumption is only strengthening our result: If SoS cannot solve this problem even for this specific u, it cannot do any better for the general problem with arbitrary u.
Let the vectors from the given dataset be Ui,..., Um. Let them form the rows of a matrix S E R Let Σ m Σ "asl be the sample covariance matrix. Then the standard PCA objective is to maximize x "x and recover I = Vku. Therefore, the sparse PCA problem can be rephrased as
m
m maximize
1
Ex
(r, vz)² such that ai = x; for all i S and 5
k

---

where the program variables are Fi....,.E.. The constraint z² = 2, enforces that the entries of z are in {-1,0, 1 and along with these constraints, the last condition > of enforces k-sparsity. Now, we will consider the series of convex relaxations for Sparse PCA obtained by SoS algo- rithms. In particular, we will consider SoS degree of d for a small constant E >> 0. Note that this corresponds to SoS algorithms of subexponential running time in the imput size d0(1),
Our main result states that for choices of m below certain threshold, when the vectors sampled from the unspiked standard Gaussian (0, Id), then sub-exponential time SoS algorithms will have optimal value at least m + mA. This is also the optimal value of the objective in the case when the vectors v1,--.g Um indeed sampled from the spiked Gaus- vku. Therefore, SoS is unable to distinguish (0, Ia) from (0, Ia + Xun") and hence cannot solve sparse PCA. Formally,
., Um 01.....
sian (0, Ia )uuu)) and
Theorem 3.1. For all sufficiently small constants E > O, suppose m S x S 5x and for some A O, dd k S d'-Ac, a v S dz, then for an absolute constant C O, with high probability over a random m x d imput matrix S with Gaussian entries, the sub-exponential time SoS algorithm of degree de for sparse PCA has optimal value at least m + +m o(1)
AE
In other words, sub- -ubbeexpoettial time SoS cannot certify that for a random dataset with Gaussian entries, there is no unit vector with k nonzero entries and m uuEu Eu Theorem is deferred to the appendix.
mX. The proof of
few remarks are in order.
1. Note here that + md is approximately the value of the objective when the input vectors U1,..., Um are indeed sampled from the spiked model (O, La + AuuF') and x vku. Therefore, sub-exponential time SoS is unable to distinguish a completely random distribu- tion from the spiked distribution and hence is unable to solve sparse PCA.
2. The constant A can be thought of as s 0 and it appears for technical reasons, ensure that we have sufficient decay in our bounds (see Remark K.8). In particular, most values of k, À fall under the conditions of the theorem.
Informally, our main result says that when < min
: x x
then subexponential time SoS
cannot recover the principal component u. This the content of Theorem 1.1
Prior work algorithms Due its widespread importance, tremendous amount of work has been devoted to obtaining algorithms for sparse PCA, both theoretically and practically. 4 73
B3
g 20 82
34,
54 23
35
29 36) to cite a few.
We now place result in the context of known algorithms for Sparse PCA and explain why it offers tight tradcoffs between approximability and inapproximability. Between this work and prior works, we completely understand the parameter regimes where sparse PCA is easy or conjectured to be hard up to polylogarithmic factors. In Fig. 1a and Fig. 1b. we assign the different parameter regimes into the following categories.
recovers the sparse Diagonal thresholding: In this regime, Diagonal thresholding 6
vector. Covariance thresholding [33 and SoS algorithms [37 also be used in this regime. The benefits of these alternate algorithms are that covariance thresholding has better dependence logarithmic factors and SoS algorithms works in the presence of adversarial errors.
Vanilla PCA: Vanilla PCA (i.e. standard PCA) can recover the vector, i.e. we do not need to use the fact that the vector is sparse (see e.g. 21 37
Spectral: An efficient spectral algorithm recovers the sparse vector (see e.g. [37
Can test but recover: simple spectral algorithm can solve the hypothesis testing version of Sparse PCA but it is information theoretically impossible to recover the sparse vector [37 Appendix E].
Hard: A regime where conjectured to be hard for algorithms to recover the sparse principal component. We discuss this in more detail below.
7

---

In la and Fig. 1b, the regimes corresponding to Diagonal thresholding, Vanilla PCA and Spectral are dark green, while the regimes corresponding Spectral* and Hard are light green and red respectively.
Prior work on hardness Prior works have explored statistical query lower bounds 25 basic SDP lower bounds [73], reductions from conjectured hard problems [21 20 23
118 lower bounds 44
via the low-degree conjecture (35 37 lower bounds via statistical physics (35 [2]. etc. We note that similar threshold behaviors as us have been predicted by [37], but importantly they assume a conjecture known as the low-degree likelihood conjecture. Similarly, many of these other lower bounds rely on various conjectures. To put in context, the low-degree likelihood conjecture is a stronger assumption than P * NP. In contrast, our results are unconditional and do not assume any conjectures.
Compared to these other lower bounds, there have only been two prior works on lower bounds against SoS algorithums 73 21 which are only for degree 2 and degree 4 SoS. In particular, degree 2 SoS lower bounds have been studied in [73] [1] although they don't state it this way. And (82 obtained degree 4 SoS lower bounds but they were very lossy, i.e. they hold for strict subset
1a of the Hard regime m < X² and m < fr. Moreover, the ideas used in these prior works do not generalize for higher degrees. The lack of other SoS lower bounds can be attributed to the difficulty in proving such lower bounds. In this paper, we vastly strengthen these known results and show almost-tight lower bounds for SoS algorithms of degree df which correspond to sub-exponential running time d= We note that SoS algorithms get stronger as the degree increases, therefore our results immediately imply these prior results and even in the special case of degree 4 SoS, we improve the known lossy bounds. In summary. (hhoormm 3.1 |subuumes all these earlier known results and is vast improvement over prior known SoS lower bounds which provides compelling evidence for the hardness of Sparse PCA in this parameter range.
The work [54] also states SoS lower bounds for Sparse PCA but it differs from our work in three important aspects. First, they handle the related but qualitatively different Wigner model of Sparse PCA. Their techniques fail for the Wishart model of Sparse PCA, which is more natural in practice. We overcome this shortcoming and work with the Wishart model. We emphasize that their techniques are insufficient to handle this generality and overcoming this is far from being a mere technicality. On the other hand, techniques can easily recover their results. Second, while they sketch high level proof overview for their lower bound, they don't 't give a proof. On the other hand, our proofs fully explicit. Finally, they assume the input distribution has entries in {+1}, that is, they work with the 11 variant of PCA. On the other hand, we work with the more realistic setting where the distribution is (0, 1). Again, our techniques can easily recover their results well.
3.2 Tensor PCA
We will now state our main result for Tensor PCA. Let k 2 2 be an integer. We are given an order k tensor A of the form A = Su + B where E R" is unit vector and B E Ria)* has independent Gaussian entries and we would like to recover the principal component u. Tensor PCA can be rephrased by the program
maximize (k) (A, 8 Dx) x) such that
2
=1
times
where the program variables are Ii, ,i...., Tn. The principal component u will then just be the returned solution x. We will again consider sub-exponential time SoS algorithms, in particular degree n² SoS, for this problem. This is sub-exponential time because the input size is o(1)
We then show that if the signal to noise ratio À is below a certain threshold, then sub-exponential time SoS for the unspiked input A ~ N (O, (mjj) will have optimal value close to X, which is also the optimal objective value in the spiked case when A = xu + B, B ~ (O, (nn}s) ) and x In other words, SoS cannot distinguish the unspiked and spiked distributions and hence cannot recover the principal component u.
Theorem 3.2. Let k be an integer. For all sufficiently small > if S n for an absolute constant C > O, with high probability over a random tensor A NO, [mn] ), the sub-exponential time SoS algorithm of degree n. for Tensor PCA has optimal value at least À - o(1)
8

---

Therefore, sub-exponential time SoS cannot certify that for random tensor A ~ NN, [mj))), there is no unit vector u such that (A,
u 22 A. The proof of Theorem 3.2 is deferred to the
times
appendix.
We again remark that when the tensor A is actually sampled from the spiked model A o + B, the optimal objective value is approximately À when 2 = u. Therefore, this shows that sub-exponential time SoS algorithms cannot solve Tensor PCA.
Informally, the theorem says that when the signal to noise ratio À < n., SoS algorithms cannot solve Tensor PCA, as stated in Theorem 1.2
Prior work
Algorithms for Tensor PCA have been studied in the works M
52 53 110
125
8l. It was shown in [22 that the degree 9 SoS algorithm certifies an upper bound of 2 2000 (n-polylog(n)) for the Tensor PCA problem. When n' this gives upper bound of
120,
67
q²/ 44/1-1/2
n -(e)) Therefore, our result is tight, giving insight into the computational threshold for Tensor PCA.
Lower bounds for Tensor PCA have been studied in various forms including statistical query lower bounds [25 39],, reductions from conjectured hard problems [123] 24), lower bounds from the low-degree conjecture [54] [55 [75]. evidence based on the landscape behavior [10] 88) etc. Compared lot of these works which rely on various conjectures, we remark that our lower bounds are unconditional and do not rely any conjectures.
In 14 similar to Sparse PCA, they state a similar theorem for a different variant of Tensor PCA. However, they do not give a proof whereas we give explicit proofs. particular, they state their result without proof for the +1 variant of Tensor PCA whereas we work with the more realistic setting where the distribution is (0, 1). We remark that their techniques do not recover our results but on the other hand, our techniques can recover theirs.
4 Related work
As stated in their respective sections, there have been some prior works on (degree at most 4) SoS lower bounds on Sparse and Tensor PCA and various other lower bounds that have mostly relied various hardness conjectures, some of which stronger than P * NP. The lack of results on higher degree SoS, compared to other models, can be attributed to the difficulty of proving such lower bounds, which we undertake in this work.
Sum of Squares lower bounds have been obtained for various problems of interest, such as Maximum Cut [87] Maximum Independent
Seeringtoo-Kirkpattien Hamiltonian 45] 74
104
Set (64] 104). Constraint Satisfaction Problems 71. Densest k- k-Subgraph 655 etc. The techniques
used this work are closely related to the work [19 which proved Sum of Squares lower bounds
for a problem known Planted Clique. Some of the ideas and techniques we employ in this work, namely pseudo-calibration and graph matrices have also appeared in other works [87] [103] 45 1 [64]
105 63 65 It's plausible that our generalized techniques could be applied other high dimensional statistical problems, which we leave for future work.
5
Conclusion
In this work, we show sabbexxonential time lower bounds for the powerful Sum-of- -finnrr-SSqares algorithms
for Sparse PCA and Tensor PCA. With the evergrowing research into better algorithms for Sparse PCA
4 83 [33 33 118
20
82
34
54
23
35| 36) and Tensor PCA [1] 22, 52
53
110
125
120 67
8
combined with the recent breakthrough of Sum of Squares algorithms in statisties [6
80
51
70 43
772 14 15 [ل it's therefore an important goal to understand whether Sum of Squares algorithms
can beat state of the art algorithms for these problems.
this work, we answer this negatively and show that even sub-exponential time SoS algorithms cannot do much better than relatively simpler algorithms. In particular, we settle open problems raised
by [82] (4 55 52 22). Our work does not handle exponential time 12()) degree SoS so analyzing these algorithms is potential future direction. Another important direction is to understand the limits

---

of powerful algorithms such as SoS for other statistical problems of importance, such as mixture modeling or clustering. For algorithm designers, our results illustrates the intrinsic difficulty of PCA problems and sheds light on information-computatioo gaps exhibited by PCA. For practitioners, this result provides strong evidence that existing algorithms work relatively well.
References
[1] K. Ahn, D. Medarametla, and A. Potechin. Graph matrices; Norm bounds and applications. abs/1604.03423, 2020. htttp:t/p//aaate wwtp:////g...g....ooooooo 03423
034233
[2] G. I. Allen and M. Maletić-Savatio Sparse non-negative generalized pea with applications to metabolomics. Bioinformatics,
3035, 2011.
[3] M. Alzantot, B. Balaji, and M. Srivastava. Did you hear that? adversarial examples against automatic speech recognition. arXiv preprint orXiv:1801 100544, 2018.
[4] A. A. Amini and M. J. Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE international symposium on information theory, pages 2454-2458. IEEE, 2008
[5] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky. Tensor decompositions for learning latent variable models, Journal of machine learning research, 15:2773-2832, 2014.
[6] A. Anandkumar, R. Ge, and M. Janzamin. Analyzing tensor power method dynamics: Ap- plications to learning overcomplete latent variable models. arXiv preprint arXiv:1411.1488, 2014.
[7] A. Anandkumar, R. Ge, and M. Janzamin. Guaranteed not-ootha tensor decomposition via alternating rank-1 updates. arXiv preprint arXiv: 1402.5 2014.
[8] A. Anandkumar, Y. Deng, R. Ge, and H. Mobahi. Homotopy analysis for tensor pea. In Conference on Learning Theory, pages 79-104. PMLR, 2017.
[9] S. Arora, S. Rao, and U. Vazirani. Expander flows and a vlog n-approximation to sparsest cut. 2004.
[10] G. Arous, Mei, A. Montanari, and M. Nica. The landscape of the spiked tensor model. Communications on Pure and Applied Mathematics, 72(1 72(11)22222-2300 2019.
[11] G. B. Arous, R. Gheissari, and A. Jagannath. Algorithmic thresholds for tensor pea. The Annals of Probability, 48(4)) 2020.
[12] G. B. Arous, A. Wein, and Zadik. Free energy wells and overlap gap property in sparse pea. In Conference on Learning Theory, pages 479-482, PMLR, 2020.
[13] J. Baik, complex sample covariance matrices. The Annals of Probability, 33(5): 1643-166431667 2005.
Arous, S. Péché, et al. Phase transition of the largest eigenvalue for nonnull
[14] A. Bakshi and P. Kothari. Outlier-robust clustering of non-spherical mixtures. arXiv preprint arXiv:2005.02977 2020.
[15] A. Bakshi and P. K. Kothari. List-decodable subspace recovery: Dimension independent error in polynomial time. arXiv preprint (:XXi::0002.0/339 2020.
[16] A. Bakshi, Diakonikolas, H. Jia, D. M. Kane, P. K. Kothari, and S. Vempala. Robustly learning mixtures of k arbitrary gaussians. arXiv preprint arXiv:2012.021199 2020.
[17] B. Barak, F. G. I.. Brandão, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. Hypercon- tractivity, sum-of-squares proofs, and their applications. CoRR, abs/1205 (es//12054444, 2012.
[18] B. Barak, J. A. Kelner, and D. Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pages 143-151, 2015.
10

---

[19] B. Barak, S. B. Hopkins, J. Kelner, P. Kothari, A. Moitra, and A. Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem, 2016.
[20] Q. Berthet and P. Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Conference Learning Theory, pages (046-1066, 2013.
[21] Q. Berthet, P. Rigollet, dimension. The Annals of Statistics, (1144::1780-8115, 2013.
Optimal detection of sparse principal components in high
[22] V. Bhattiprolu, V. Guruswami, and E. Lee. Sum-of-squares certificates for maxima of random tensors on the sphere. arXiv preprint 1605.0006000000 2016.
[23] M. Brennan and G. Bresler. Optimal average-case reductions to sparse pea: From weak assumptions to strong hardness. arXiv preprint arXiv:1902.07380,, 2019.
[24] M. Brennan and G. Bresler. Reducibility and statistical computatiooo gaps from secret leakage. In Conference Learning Theory, pages 648 847. PMLR, 2020.
[25] M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint 0x11:20009006107, 2020.
[26] W.-K. Chen. Phase transition in the spiked random tensor with rademacher prior. The Annals of Statistics, 47(5):2734-2766, 2019.
[27] W. K. Chen, M. Handschy, and G. Lerman. Phase transition in random tensors with multiple spikes. Scanning Electron Microse Meet at, 2018.
[28] D. M. Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554, 2002.
[29] A. Chowdhury, P. Drineas, D. P. Woodruff, and S. Zhou. Approximation algorithms for sparse principal component analysis. arXiv preprint arXiv:2006. 12748, 2020.
[30] C.-T. Chu, S. Kim, Y.-A. Lin, Y. Yu, G. Bradski, K. Olukotun, and A. Ng. Map-reduce for machine learning on multicore. Advances in neural information processing systems, 19, 2006.
[31] H. Chun and S. Keleş. Expression quantitative trait loci mapping with multivariate sparse partial least squares regression. Genetics, 182(1):79-90, 2009.
[32] A. d' d'Aspremont, L. Ghaoui, M. Jordan, and G. Lanckriet. direct formulation for sparse pea using semidefinite programming. Advances in neural information processing systems, 17, 2004.
[33] Y. Deshpande and A. Montanari. Sparse pea via covariance thresholding. The Journal of Machine Learning Research, 17(1):913-4953, 2016.
[34] I. Diakonikolas, D. M. Kane, and Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84, IEEE, 2017
[35] Y. Ding, D. Kunisky, A. S. Wein, and A. S. Bandeira. Subexponential-time algorithms for sparse pea. arXiv preprint 1907. 1635, 2019.
[36] T. d'Orsi, P. K. Kothari, G. Novikov, and D. Steurer. Sparse pea: algorithms, adversarial perturbations and certificates. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 553-564. IEEE, 2020.
[37] T. d'Orsi, P. K. Kothari, G. Novikov, and D. Steurer. Sparse pea: Algorithms, adversarial perturbations and certificates. In 2020 IEEE 61 Annual Symposium Foundations of Computer Science (FOCS), 2020.
[38] O. Duchenne, F. Bach, I.-S. Kweon, and J. Ponce. A tensor-based algorithm for high-order graph matching. IEEE transactions on pattern analysis and machine intelligence, 33(12): 2383-2395, 2011.
11

---

[39] R. Dudeja and D. Hsu. Statistical query lower bounds for tensor pea. Journal of Machine Learning Research, 22(83):1-51, 2021.
[40] V. Feldman, Grigorescu, Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1-37, 2017.
[41] V. Feldman, W. Perkins, and S. Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM Journal on Computing. 47(4):1294-1338, 2018.
[42] V. Fischer, M. C. Kumar, J. H. Metzen, and T. Brox. Adversarial examples for semantic image segmentation. arXiv preprint 1oXXv:1703.01100 2017.
[43] N. Fleming, P. Kothari, and T. Pitassi. Semialgebraic Proofs and Efficient Algorithm Design. 2019.
[44] C. Gao, Z. Ma, and H. H. Zhou. Sparse cca: Adaptive estimation and computational barriers. The Annals of Statistics, 45(5):2074-211 2101, 2017.
[45] M. Ghosh, F. G. Jeronimo, C. Jones, A. Potechin, and G. Rajendran. Sum-of-squares lower via Planted Affine Planes. In 2020 IEEE 61 Annual Symposium on Foundations Computer Science (FOCS), 2020.
bounds for Sherrington-Kirkpatt
[46] M. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115:1145, 1995. Preliminary version in Proc. of STOC'94.
[47] J. Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples. arXiv preprint 4rX1v:1412.6572, 2014.
[48] D. Grigoriev. Complexity of positivstellensatz proofs for the knapsack. computational complexity, 10(2):139 154, 2001.
[49] V. Guruswami and A. K. Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In FOCS, pages 482-491, 2011.
[50] Hendrycks, K. Zhao, S. Basart, J. Steinhardt, and D. Song. Natural adversarial examples. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 15262-15271, 2021.
[51] S. B. Hopkins. Mean estimation with uub-gaussian rates in polynomial time. The Annals of Statistics, 1932):1193-2213, 2020.
[52] S. B. Hopkins, J. Shi, and D. Steurer. Tensor principal component analysis via sum-of-squares proofs. In Conference on Learning Theory, pages 956-1006, 2015.
[53] S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum-of- squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 178-191, 2016.
[54] S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 720-731. IEEE, 2017.
[55] S. B. K. Hopkins. Statistical inference and the sum of squares method. 2018.
[56] D. Hsu, S. M. Kakade, and T. Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5):1460 1480, 2012.
[57] W.-N. Hsu, A. Sriram, A. Baevski, T. Likhomanenko, Q. Xu, V. Pratap, Kahn, A. Lee, R. Collobert, G. Synnaeve, et al. Robust wav2vec 2.0: Analyzing domain shift in self- supervised pre-training. arXiv preprint arXiv:2 04.00002. 2021.
[58] Jagannath, Lopatto, and I.. Miolane. Statistical thresholds for tensor pea. The Annals of Applied Probability, 3004):1910-1933 2020.
12

---

[59] A. Jalali, C. Johnson, and P. Ravikumar. On learning discrete graphical models using greedy methods. Advances in Neural Information Processing Systems, 24, 2011.
[60] C. Johnson, A. Jalali, and Ravikumar. High-dimensional sparse inverse covariance estimation using greedy methods. In Artificial Intelligence and Statistics, pages 574-582. PMLR, 2012.
[61] I. M. Johnstone and Y. Lu. Sparse principal components analysis. arXiv preprint Seiv:0901.4392. 2009.
[62] I. T. Joliffe and B. Morgan. Principal component analysis and exploratory factor analysis. Statistical methods in medical research, 1(1):69-95 95, 1992.
[63] C. Jones. Symmetrized fourier analysis of convex relaxations for combinatorial optimization problems. 2022.
[64] Jones, A. Potechin, G. Rajendran, M. Tulsiani, and Xu. Sun-of-squares lower bounds for sparse independent set. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 406-416. IEEE, 2022.
[65] C. Jones. A. Potechin, G. Rajendran, and J. Xu. Sum-of -ft-r-r--quues lower bounds for densest k-subgraph. 2023.
[66] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1066, 1998.
[67] C. Kim, A. Bandeira, and M. X. Goemans. Community detection in hypergraphs, spiked tensor models, and sum-of-squares. In 2017 International Conference on Sampling Theory and Applications (SampTA), pages 124 128. IEEE, 2017.
[68] B. Kivva, G. Rajendran, Ravikumar, and B. Aragam. Learning latent causal graphs via mixture oracles. Advances in Neural Information Processing Systems, 34, 2021.
[69] Kivva, G. Rajendran, Ravikumar, and B. Aragam. Identifiability of deep generative models under mixture priors without auxiliary information. arXiv preprint arXiv:2206.1004 2022.
[70] A. Klivans, K. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
[71] P. Kothari, R. Mori, O'Donnell, and D. Witmer. Sum of squares lower bounds for refuting any CSP. 2017.
[72] P. K. Kothari and D. Steurer. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1111.11811, 2017.
[73] R. Krauthgamer, B. Nadler, D. Vilenchik, et al. Do semidefinite relaxations solve sparse pca up the information limit? The Annals of Statistics, 43(3):1300-1333 2015.
[74] D. Kunisky. hypercube. arXiv preprint arXiv:2009.07266 2020.
extensions of sum-of-squares pseudomoments over the
[75] D. Kunisky, A. S. Wein, and A. S. Bandeira. Notes computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint 1rXiv:1907.11633 2019.
[76] Kurakin, I. Goodfellow, and S. Bengio. Adversarial machine learning scale. arXiv preprint arXiv:1611.01236 2016.
[77] T. Lesieur, I.. Miolane, M. Lelarge, F. Krzakala, and I.. 7deborová. Statistical and computa- tional phase transitions in spiked tensor estimation. In 20/7 IEEE International Symposium on Information Theory (ISIT), pages 511-515. IEEE, 2017.
[78] J. Li, Deng, R. Haeb-Umbach, and Gong. Robust automatic speech recognition: a bridge to practical applications. 2015.
13

---

[79] N. Li and B. Li. Tensor completion for on-board compression of hyperspectral images. In 2010 IEEE International Conference on Image Processing, pages 517-520. IEEE, 2010.
[80] Liu and A. Moitra. Settling the robust learnability of mixtures of gaussians. Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 518-531 2021.
[81] J. Liu, J. Ye, and R. Fujimaki. forward-backwant greedy algorithms for general convex smooth functions over a cardinality constraint. In International Conference on Machine Learning, pages 503-511. PMLR, 2014.
[82] T. Ma and A. Wigderson. Sum-of-squane lower bounds for sparse pea. In Advances in Neural Information Processing Systems, pages 1612-1620, 2015.
[83] Z. Ma. Sparse principal component analysis and iterative thresholding. The Annals of Statistics, 41(2):772-801. 2013.
[84] M. W. Mahoney and P. Drineas. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-70,, 2009.
[85] A. Majumdar. Image compression by sparse pea coding in curvelet domain. Signal, image and video processing, 3(1):27-34, 2009.
[86] D. Medarametla and A. Potechin. Bounds the norms of uniform low degree graph matrices. RANDOM, 2016.
[87] S. Mohanty, P. Raghavendra, and J. Xu. Lifting sum-of-squares lower bounds: degree-2 degree-4. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 840-853, 2020.
[88] A. Montanari, D. Reichman, and O. Zeitouni. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors. Advances in Neural Information Processing Systems, 28, 2015.
[89] N. Naikal, A. Y. Yang, and S. S. Sastry. Informative feature selection for object recognition via sparse pea. In 2011 International Conference on Computer Vision, pages 818-825, IEEE, 2011.
[90] P. Nandy, A. Hauser, and M. H. Maathuis. High-dimensionn consisttney in score-based and hybrid structure learning. The Annals of Statistics, 466613: 2018
[91] P. Neekhara, S. Hussain, P. Pandey, S. Dubnov, J. McAuley, and F. Koushanfar. Universal adversarial perturbations for speech recognition systems. arXiv preprint 1r0.v:1905.03828. 2019.
[92] Y. Nesterov. Squared functional systems and optimization problems. In High performance optimization, pages 405-440. Springer, 2000.
[93] R. O'Donnell.
Sos is not obviously automatizable, even approximately. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstub--LeibnizzZZentrru fuer Informatik, 2017.
[94] Olivier and B. Raj. Recent improvements of asr models in the face of adversarial attacks. 2022.
arXiv preprint
[95] D. Papailiopoulos, A. Dimakis, and S. Korokythakis. Sparse pea through low-rank approxima- tions. International Conference on Machine Learning, pages 747-755. PMLR, 2013.
[96] P. A. Parrilo. Structured semidefiite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, 2000.
[97] D. Paul. Asymptotics of sample eigenstructure for large dimensional spiked covariance model. Statistica Sinica, pages 1617-1642, 2007.
[98] Perry, A. S. Wein, and A. S. Bandeira. Statistical limits of spiked tensor models. arXiv preprint arXiv: 2016.
14

---

[99] A. Potechin and G. Rajendran. Machinery for proving sum-of-squares lower bounds on certification problems, arXiv preprint arXiv:2011.04253, 2020.
[100] A. Potechin and D. Steurer. Exact tensor completion with sum-of-squares. arXiv preprint arXiv:/702.062:: 2017.
[101] P. Raghavendra and B. Weitz. On the bit complexity of sum-of-squares proofs. Schloss Degstuhl-Lcibnizz-Zenttrru fuer Informatik, 2017.
[102] P. Raghavendra, S. Rao, and T. Schramm. Strongly refuting random esps below the spec- tral threshold. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 121-131, 2017.
[103] G. Rajendran. Combinatorial Optimization via the Sum of Squares hierarchy. 2018.
[104] G. Rajendran. Nonlinear random matrices and applications to the sum of squares hierarchy.
2022.
[105] G. Rajendran and M. Tulsiani. Concentration of polynomial random matrices via efron-stein inequalities. arXiv preprini 1xXiv:2209.026555 2022.
[106] G. Rajendran and W. Zou. Analyzing robustness of end-to-end neural models for automatic speech recognition. arXiv preprint arXiv:2208.c 08500, 2022.
[107] G. Rajendran, B. Kivva, M. Gao, and B. Aragam. Structure learning in polynomial time: Greedy algorithmss, bregman information, and exponential families. Advances in Neural Information Processing Systems, 166-18660-1672, 2021.
[108] M. Ravanelli, J. Zhong, S. Pascual, P. Swietojanski, J. Monteiro, J. Trmal, and Y. Bengio. Multi-task self-supervised learning for robust speech recognition. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 6989-6993, IEEE, 2020.
[109] L. Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004 00557, 2020.
[110] E. Richard and A. Montanari. A statistical model for tensor pea. In Advances in Neural Information Processing Systems, pages 2897-2905, 2014.
[111] T. Schramm and D. Steurer. Fast and robust tensor decomposition with applications to dictionary learning. In Conference on Learning Theory, pages 1760-1793. PMLR, 2017.
[112] Sebe and M. S. Lew. Robust computer vision: Theory and applications, volume 26. Springer Science & Business Media, 2013.
[113] 7.. Shor. An approach obtaining global extremums in polynomial mathematical program- ming problems. Cybernetics, ((5))6955700, 1987.
[114] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 2013.
[115] M. Tan, A. Petersen, and Witten. Classification of ma-seg data. In Statistical analysis of next generation sequencing data, pages 219-246. Springer, 2014.
[116] L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM review, 38(1):49-95, 1996.
[117] D. Wang, H. Lu, and M.-H. Yang. Online object tracking with sparse prototypes. JEEE transactions image processing, 22(1):314-32 2012.
[118] T. Wang, Q. Berthet, and J. Samworth. Statistical and computational trade-offs in estimation sparse principal components. The Annals of Statistics, 4465):1896-1930, 2016.
[119] Y. Wang, Li, Wang, Y. Qian, C. Wang, and Y. Wu. Wav2vec-switch: Contrastive learning from original-noisy speech pairs for robust speech recognition. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7097-7101. IEEE, 2022.
15

---

[120] A. S. Wein, A. EI Alaoui, and C. Moore. The kikuchi hierarchy and tensor pea. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1446-1468. IEFE, 2019.
[121] C. Xie, Y. Wu, L. d. Maaten, A. L. Yuille, and K. He. Feature denoising for improving adversarial robustness. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 501-509, 2019.
[122] C. Xie, M. Tan, B. Gong, J. Wang, A. L. Yuille, and Q. V. Le. Adversarial examples improve image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 819-828, 2020.
[123] A. Zhang and D. Xia. Tensor svd: Statistical and computational limits. IEEE Transactions on Information Theory, 64(11):7311-733) 2018.
[124] T. Zhang. Adaptive forward-backwarn greedy algorithm for sparse learning with linear models. Advances in neural information processing systems, 21, 2008
[125] Q. Zheng and R. Tomioka. Interpolating convex and non-convex tensor decompositions via the subspace norm. Advances in Neural Information Processing Systems, 28, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See SeesSeccinn 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is purely theoretical and has no significant societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3 Theorem 3.1 Theorem 3.2
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL.)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] Relevant theoretical works have been cited.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
16

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
17


Reviews:
[{"review_id": "ypOfrOlmj1E", "reviewer": "Reviewer_TgBm", "summary": "Sum-of-squares is a family of algorithms that capture many known techniques for combinatorial optimization problems, and it has been recently shown to be very powerful for many ML/robust statistics problems. For the theoretical computer science community, some has seen this as a proxy to strong algorithmic impossibility result especially in the average-case setting.  This paper rigorously establishes strong Sum-of-Squares lower bounds at n^\\eps degree for several problems in the colloquial “dense-graph” regime, including tensor PCA, sparse PCA both of which have been claimed by a previous work of Hopkins et al. [HKPRSS17] but without an explicit, spelled-out proof. On the technical level, it builds upon the SoS lower bound for Planted Clique by Barak et al [BHKKMP16] that they use the recursive factorization framework to show PSDness of the candidate moment matrix obtained from pseudo-calibration with intense matrix analysis. For the specific hardness this work obtains, not much is known before except deg-2 and deg-4 lower bound in the SoS realm, and this work obtains almost tight hardness matching known algorithms.\n", "questions": "1, \"Their techniques fail for the Wishart model of Sparse PCA, which is more natural in practice. We overcome this shortcoming and work with the Wishart model. We emphasize that their techniques are insufficient to handle this generality and overcoming this is far from being a mere technicality.\" \nAs surprising as it may be, this is quite strong and cryptic a statement. Apology if I missed something in the supplementary material, is there a way to highlight/encapsulate the difference from your technique should one try to apply the recursive factorization framework from planted clique in a somewhat straightforward manner?\n\n2. For Sparse PCA constraint of supporting on $k$ coordinates, is this constrained exactly satisfied by the pseudo-expectation or only on average? I suppose its the former, and it seems nice (and even important) to point out in the work if not yet considering the struggle for satisfying exact constraints in sos lower bounds.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: 1) In general, this is detailedly written paper;\n                2) Though the hardness result may not be too surprising, the almost tight hardness result of this work is certainly nice to have, and necessary for the community considering how universal these two problems are in ML practice;\n               3) Their generalization of the framework from planted clique is likely to find applications in other problems. \n\nWeakness:\n 1) As the paper is filled with details, it'd be nice to incorporate more exposition in the technical section. It is hard to imagine someone going through this generalization; and as technical as it already is, more intuition between the technical proofs can be helpful for readability.\n      \n2) It is not immediately clear what technical challenges the authors claimed to have overcome from planted clique. They note that the method from planted clique does not immediately work, while the challenges are not explicitly stated.\n   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "lASpqvgTYC", "reviewer": "Reviewer_Q86G", "summary": "This is a theoretical work that studies the applicability of sum of squares (SoS) algorithms for sparse principal component analysis (PCA) and tensor PCA. Specifically, this work provides theoretical proof that despite the success of SOS algorithms in high dimensional statistics, they underperform when applied to sparse PCA and tensor PCA. The paper claims that sub-exponential time SOS algorithms cannot beat traditional sparse PCA algorithms, even if allowed sub-exponential time.", "questions": "1. For sparse PCA, it seems like this work focuses on recovering a single principal component. If so, could the authors clarify why they focus on just a single component and how one could extend this to multiple components?\n2. Paper claims that the proposed theory is more general compared to existing results because the existing results assume an input distribution of +-1, whereas the proposed work relies on the distribution N(0,1). How does this make the proposed theory more general? Please provide intuition in terms of real-world examples.\n3. Have SoS algorithms been used for sparse PCA in the past? If so, do they perform well? Can the authors comment on this?\n4. Although the proposed theory is useful in itself, what is its practical applicability? It would be nice to see an empirical demonstration of the theory in practice. For example, demonstrate on real-world (or synthetic) data that sub-exponential time SoS algorithms are unable to recover sparse PCA solution while simple traditional algorithms succeed. \n5. Repeated word \"devise\" in line 383. Please remove one of them.\n", "limitations": "The paper identifies relevant future directions of research based on limitations of the current work. ", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The text is easy to follow.\n2. Visual illustrations (e.g., in Figure 1 ) assist in understanding the claims of the paper.\n3. The paper is theoretical and appears to propose a broad result on the usefulness of SOS algorithms for sparse PCA and tensor PCA.\n\nWeaknesses:\n1. The flow of the paper can be further improved.\n2. Is the proposed theory relevant in practice? Please elaborate. For example, theorem 3.1 assumes a range for m and theorem 3.2 assumes an upper limit for \\lambda. Are these valid assumptions in practice?\n3. Figures are referred to as \"Fig.\". Please correct them.\n4. Equations are not referenced. Please number them for easy reference. \n5. Line 124 consists of a tensor product notation and it is not explained. Please provide an explanation.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gaRzYGVE5em", "reviewer": "Reviewer_xtw5", "summary": "This paper develops high-degree lower bounds for the sparse PCA and tensor PCA problems. For both of these problems, there is a well-known discrepancy between the statistical complexity (i.e. #samples or snr required to detect the hidden signal by any means feasible) and computational complexity (i.e. #samples or snr required to approximately recover the hidden signal by computationally efficient i.e. poly time algorithms). (I phrase the above in terms of detection to align with the paper, analogous definitions using recovery may be made with the obvious ordering that detection is easier than recovery). Along with the planted clique problem, sparse and tensor PCA are arguably some of the most well-studied examples of statistical problems exhibiting this computational-statistical phenomenon. While one way of developing hardness arguments is to construct problem reductions, this paper contributes to the line of unconditional hardness results by analyzing the sum-of-squares hierarchy of convex programs for sparse/tensor PCA. The first two steps (also called degrees) in this hierarchy for sparse PCA were shown ineffective by Krauthgamer et al and Wigderson and Ma respectively. This paper develops bounds for the next dimension^{a small const} many degrees. \n\n", "questions": "The following questions are roughly \"chronological\" in the paper. \n1. L101: what is n for sparse pca? This should be m perhaps?\n2. L251: Technically this is a lower bound (by plugging in u in the objective). It is not obvious (though it probably is) to me that this is an upper bound. \n3. As I understand it, Thm 3.1 proves a lower bound on the value of the SDP applied to pure noise, i.e. the input covariance matrix is identity and has no dependence on lambda. If so, why is lambda involved in the value? This confused me for a while before I realized presumably this is because your solution (or certificate) is via pseudocalibration and explicitly has an alternative \"planted\" distribution involving lambda. But then why not sup over lambda in the feasible set? The same question holds for the Thm 3.2. \n\nSome suggestions regarding notation/organization:\n1. For sparse PCA it is best to keep the parameters (n, k, d, lambda) as (sample size, sparsity, dimension, snr). Similarly for tensor pca, it is probably better to keep something like (d, r, lambda)  (dimension, tensor order/rank, snr) respectively and avoid the collision use of \"k\". The choice in the paper appears to be first choosing dimension=n for tensor pca and then avoiding collision by choosing the somewhat confusing 'm' for sparse pca sample size. In terms of readability, this is significantly sub-optimal\n2. I'd relegate the \"general definition\" of sos programs to the appendix, and just write the specific programs for sparse/tensor pca. Perhaps just refer to a textbook for the general definition, and it anyway collides rather unfortunately (d, n etc...) with the notational choices in 1. Alternatively use different fonts to make things obvious.\n3. There are multiple points where things were also quite confusing to read in the appendix, which makes it difficult to understand/penetrate the proof techniques. For example, in L.1044 there is V(Id_U), U_{Id_U}, V_{Id_U} and E(Id_U), which is (at least all the same font) very confusing at first go. After a while I realized the first and the last were vertex/edge sets for the whole graph and the middle two were left/right parts respectively. The notation did not help though.  ", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I think the paper is an interesting and solid contribution to the hardness results on sparse PCA and tensor PCA. Both problems are (sparse PCA somewhat more than tensor PCA) well-motivated and used in applications. \n2. The proof techniques are (to my mind) also potentially interesting to the theory-inclined audience. Proving sum-of-squares lower bounds tends to be a technically challenging, intricate and involved task and the authors do a good job in the beginning of the appendix explaining some of the high-level ideas and challenges.\n\nWeaknesses:\n1. At the outset, and given 2, Neurips might not be the best fit for this submission. I would expect COLT, theoretical CS conferences STOC/FOCS and of course, a number of journals, on the other hand to be quite well-suited. \n2. The interesting and generalizable part of the paper seem to be some of the proof techniques, and these are relegated to the appendix. I did not have time to read the full appendix (65 pages) but the first 15-20 were useful.\n3. Separately from 1, the paper is made inaccessible by a somewhat loose use of notation that is widespread. As a small example, after using 'd' for dimension, the authors also use it for 'degree' of the SOS program in the beginning of Sec. 2. For accessibility to a stats/ml audience, this paper would require significant polishing. \n4. Related to 3, I trust the results despite point 2, but some of the main results in the text (Theorems 3.1 and 3.2) likely should be rephrased. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "E-vyYPFKocf", "reviewer": "Reviewer_t9p5", "summary": "Sparse PCA is a fundamental problem in the machine learning and statistical inference community. Suppose we are given vectors $v_1, \\dots, v_m \\in \\mathbb{R}^d$ sampled from the mean-zero Gaussian distribution with covariance $I_d + \\lambda uu^\\top$ where $u$ is a $k$-sparse vector, the task is to recover the hidden vector $u$ (principal component). This is the *Wishart model*.\n\nThere are several parameters in play here: the number of samples $m$, the dimension $d$, the signal-to-noise ratio $\\lambda$, and the sparsity $k$. A long line of work has established an almost complete picture of the tractability of sparse PCA in different parameter regimes; in particular, in the “hard” regime where $m \\lambda^2 \\ll d$ and $m \\lambda^2 \\ll k^2$, no known algorithm exists.\n\nThis paper shows that the powerful Sum-of-Squares (SoS) algorithm fails to solve sparse PCA in this hard regime even with degree $d^{O(1)}$. Specifically, the authors show that the natural SoS relaxation at degree $d^{O(\\epsilon)}$ fails at the (easier) task of distinguishing between vectors sampled randomly vs vectors sampled from the spiked model when $m \\lambda^2 \\ll d^{1-\\epsilon}$ and $m \\lambda^2 \\ll k^{2-\\epsilon}$.\n\nTheir techniques also apply to tensor PCA. For $k\\geq 2$, we are given an order $k$ tensor $A = \\lambda u^{\\otimes k} + B$ where $u\\in \\mathbb{R}^n$ is a unit vector and $B$ is a tensor with Gaussian entries, and the task is to recover $u$. They prove analogous SoS lower bounds for the regime $\\lambda \\ll n^{k/4}$.\n\n**Techniques**\n\nThe authors showed that in the hard regime, even when given random inputs (no planted spike), the canonical SoS relaxation has a large optimal value of $m + m\\lambda - o(1)$, thus failing to distinguish from the case when the inputs are drawn from the spiked Gaussian. To prove this, the authors constructed a candidate pseudo-distribution from the spiked distribution (aka planted distribution) using the pseudo-calibration method, which is by now a standard technique to prove SoS lower bounds.\n\nAs in the SoS lower bound for planted clique [18], they decompose the pseudo-moment matrix into a linear combination of “graph matrices”, which are structured random matrices that can be represented as graphs (called shapes) and whose spectral norms can be bounded by analyzing “vertex separators” in the shape.\n\nFollowing planted clique [18], they factorize each shape into “left”, “right”, and “middle” shapes and then bound the “intersection terms” (the errors in the factorization). One technicality is that the coefficients in the linear combination also depend on the shapes, which they handle by analyzing the “coefficient matrix”. They show that the middle part is PSD by charging non-trivial shapes to the diagonal, which implies the whole matrix is PSD. The bulk of their proof is in fact handling the intersection terms.", "questions": "What are the key innovations in the proofs that are different from Hopkins et al [49]. In particular, why do their techniques fail for the Wishart model?\n\nWhere are the requirements $d^A \\leq k \\leq d^{1-A\\epsilon}$ and $\\sqrt{\\lambda} / \\sqrt{k} \\leq d^{-A\\epsilon}$ used in the proof? They seem to be buried in the details in the proof, and it would be nice if you can explain this in Appendix A.\n\n**Other comments**\n- Line 102: “tradeoff between m, n and k” should be m, \\lambda, k\n- Line 256: what does “sufficient decay” mean?\n- Line 757: I don’t think “trivial shapes” were defined before.\n- Remark C.18: “improper” not defined (it’s only defined later).", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThis paper is important as it gives insights to the complexity of sparse/tensor PCA and also the power of SoS algorithms. It provides a strong piece of evidence that the hardness regimes are indeed hard.\n\nPrevious work by Hopkins et al [49] claimed SoS lower bounds for sparse PCA in the spiked Wigner model, though their proofs are not online. This paper generalizes their ideas and proves an SoS lower bound for the more natural Wishart model. I view this as the main contribution of this paper.\n\nAs in previous papers, proving SoS lower bounds requires a significant amount of work, especially for polynomial-degree. Therefore, even though many techniques in this paper are not new (e.g. factorization of shapes, charging arguments, etc), grinding out all the technical details is a strength in my opinion.\n\n**Weaknesses**\n\nI would like to see a detailed comparison to [49] and why their techniques fail for the Wishart model. I believe that [49] has most of the main ideas even though a full proof hasn’t been posted. There must be some technical challenges hidden in the details, but this was not explained in either the main paper or the appendix.\n\nFinally, it is almost impossible for readers unfamiliar with graph matrices to follow the proofs. Maybe include some example graphs?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5IW0SfoUS8H", "reviewer": "Reviewer_7iRg", "summary": "This paper fits into the broad area of theoretically understanding information-computation tradeoffs for statistical inference.  The abstract setup is that there is some signal x, typically in the vector space R^d.  And as input, we are given noisy observations about x -- v_1, v_2, ..., v_m.  And the goal is to infer x up to the best accuracy possible via an efficient algorithm.  When m is too small, the problem is impossible to solve, even information theoretically.  At some threshold for m the problem becomes information theoretically identifiable (information threshold) but could possibly remain computationally hard.  And at a (possibly distinct) threshold (computational threshold) for m the problem also becomes algorithmically easy to solve.\n\nUnderstanding the computational threshold for average-case problems, and in particular if there is a gap in between the information and computational thresholds is a topic that has attracted a lot of attention in the theoretical computer science community.  To understand the computational threshold, one must give an algorithm along with some evidence that the problem is hard under the threshold, which usually comes in the form of lower bounds against particular algorithms (semidefinite programs, statistical queries, polynomial-based methods, eigenvalue methods, iterative algorithms, etc).  A ubiquitous phenomenon for a wide variety of such average-case algorithmic problems is that at some threshold several simple algorithms (and most notably some spectral algorithm) succeed at solving the problem, and under the threshold many seemingly more powerful algorithms fail.\n\nThis work is concerned with providing more evidence to our understanding of this computational threshold for the sparse PCA (and also tensor PCA) problems.  In the sparse PCA problem, the hidden signal x is a random d-dimensional vector supported on a much smaller number of coordinates (k coordinates) where the nonzero entries are random in {±1}.  The observations are independent samples from the gaussian distribution with covariance spiked by x: N(0, Identity + lambda xx*), where lambda is some positive scalar (to be interpreted as a \"signal-to-noise\" parameter).  The main result of this paper is that a certain powerful subexponential-sized semidefinite programming-based algorithm (degree-n^epsilon Sum-of-Squares algorithm) fails to solve sparse PCA better than a simple spectral algorithm, which adds to our understanding of how hard this problem should be.  Similar results are presented for the tensor PCA problem as well.", "questions": "1. I encourage the authors to highlight that the distinguishing problem is information theoretically solvable (given exponential time) in some interesting regime covered by the theorem, because if it isn't an SOS lower bound holds for a silly reason.\n2. The discussion about SOS being \"clearly\" more powerful than low-degree polynomials and statistical queries is slightly questionable, and I would advise the authors to remove that line.  For a wide variety of settings we expect SOS to capture what low-degree polynomials can do, and in some settings we think low-degree lower bounds imply SOS lower bounds, but they're formally incomparable.  One example is, if you plant a random coloring in a sparse graph with signal-to-noise ratio below the so-called \"Kesten-Stigum threshold\", a low-degree polynomial should succeed at distinguishing this planted distribution from a random graph with constant probability, whereas the lingering belief is that SOS SDPs shouldn't solve this problem (since the intuition is that they're limited to what can be solved \"with high probability\").", "limitations": "--", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The current state of affairs in obtaining computational hardness for restricted classes of algorithms is that when we want to argue that it's computationally hard to beat a simple spectral, we study the following methods of hardness, which are listed in roughly increasing order of difficulty.\n1) Low-degree polynomials\n2) Statistical queries\n3) Semidefinite programming lower bounds (Sum-of-Squares and this paper's contributions fall here)\n4) Reduction-based hardness\n\n(I must note that the gap between the difficulty of 2 and 3 is quite large.)\n\nIn the current sociological setting of the subarea, it is a generally widespread belief that a hardness result against 1 or 2 does mean that our current algorithmic techniques likely won't surmount the barriers they are facing, and likely new algorithmic ideas are needed.  An important question to answer to support this belief is to show that hardness results for 1 and 2 (which are often easy to establish) imply hardness results for other algorithms.  Such meta-theorems are hard to come by with no particularly promising attacks for the case of Sum-of-Squares, and therefore the current approach is to substantiate the conjecture via a rich set of example lower bounds, which together hopefully illuminate a path to such meta-theorems.\n\nWith respect to this paper's strengths and weaknesses I would like to touch upon two points:\nA) Sparse PCA is a problem that has received a lot of attention in theoretical algorithmic statistics, and in light of that evidence for computational thresholds is interesting.  However, I would not say that the paper gave us a surprising answer as to where the computational threshold should lie; the pre-existing lower bounds in the style of #1 and #2 already told us what we think the answer should be.\nB) I think the paper's main strength is in progress in substantiating the predictions #1 and #2 have for sparse PCA, since Sum-of-Squares lower bounds are only known for a handful of problems, especially since they are technically difficult to achieve.  It is worthy to note that the best reduction-based hardness (conditional on some conjecture about planted clique) only rules out quasipolynomial time algorithms, as opposed to subexponential algorithms.\n\nSome of the other existing SOS lower bounds (planted clique, CSPs, SK model) highly use problem-specific structure, and the most desirable aspect for any new SOS lower bound is to rely less on the problem-specific structure, and try to abstract conditions needed; it is hard for me to tell whether this lower bound does this given the time constraint of the review, but it would be nice if the authors can comment on this.\n\nOverall, I recommend acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept