Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 


strengths_and_weaknesses: Strengths:
1. 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. 
2. 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.

Weaknesses:
1. 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. 
2. 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.
3. 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. 
4. 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. 
questions: The following questions are roughly "chronological" in the paper. 
1. L101: what is n for sparse pca? This should be m perhaps?
2. 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. 
3. 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. 

Some suggestions regarding notation/organization:
1. 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
2. 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.
3. 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

Understanding 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.

This 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.
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.
1) Low-degree polynomials
2) Statistical queries
3) Semidefinite programming lower bounds (Sum-of-Squares and this paper's contributions fall here)
4) Reduction-based hardness

(I must note that the gap between the difficulty of 2 and 3 is quite large.)

In 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.

With respect to this paper's strengths and weaknesses I would like to touch upon two points:
A) 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.
B) 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.

Some 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.

Overall, I recommend acceptance.
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.
2. 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: --
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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*.

There 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.

This 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}$.

Their 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}$.

**Techniques**

The 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.

As 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.

Following 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.
strengths_and_weaknesses: **Strengths**

This 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.

Previous 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.

As 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.

**Weaknesses**

I 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.

Finally, it is almost impossible for readers unfamiliar with graph matrices to follow the proofs. Maybe include some example graphs?
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?

Where 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.

**Other comments**
- Line 102: “tradeoff between m, n and k” should be m, \lambda, k
- Line 256: what does “sufficient decay” mean?
- Line 757: I don’t think “trivial shapes” were defined before.
- Remark C.18: “improper” not defined (it’s only defined later).
limitations: The authors adequately addressed the limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strength: 1) In general, this is detailedly written paper;
                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;
               3) Their generalization of the framework from planted clique is likely to find applications in other problems. 

Weakness:
 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.
      
2) 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.
   

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." 
As 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?

2. 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. The text is easy to follow.
2. Visual illustrations (e.g., in Figure 1 ) assist in understanding the claims of the paper.
3. The paper is theoretical and appears to propose a broad result on the usefulness of SOS algorithms for sparse PCA and tensor PCA.

Weaknesses:
1. The flow of the paper can be further improved.
2. 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?
3. Figures are referred to as "Fig.". Please correct them.
4. Equations are not referenced. Please number them for easy reference. 
5. Line 124 consists of a tensor product notation and it is not explained. Please provide an explanation.

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?
2. 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.
3. Have SoS algorithms been used for sparse PCA in the past? If so, do they perform well? Can the authors comment on this?
4. 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. 
5. Repeated word "devise" in line 383. Please remove one of them.

limitations: The paper identifies relevant future directions of research based on limitations of the current work.
review_title: null

Meta-review: metareview: The reviewers appreciate the solid theoretical results on the hardness of sparse and tensor PCA. The nearly sharp characterization of limitations of sum-of-square methods makes the paper stand out. The proof techniques may potentially be useful for other problems. Based on the above, I recommend acceptance. Meanwhile, please carefully revise the paper to improve presentation. As the paper is technically involved, it would be nice to better elaborate the proof ideas and highlight the key challenges.
confidence: Certain
Decision: Accept