Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: # Review for "The Complexity of Sparse Tensor PCA"

This paper studies the "Sparse Tensor PCA" problem, which is a common generalization of two well-studied problems: sparse principal component analysis and tensor principal component analysis.
The problem is as follows: given a "single-spike" tensor of the form

$T = \lambda \cdot x^{\otimes p} + W$

where $W$ has i.i.d. Gaussian entries, $\lambda > 0$ is the "signal strength", and $x \in R^n$ is $k$-sparse for some $k \ll n$, find $x$.
(The problem can be generalized to more than one spike $x$; this is treated carefully in the paper.)

The paper contains interesting new algorithms and computational lower bounds for this problem.

main_review: Tensor methods are useful in high-dimensional statistics, with key applications to learning latent variable models, multi-way factor analysis, etc.
The single-spike model (tensor PCA without the sparsity assumption on $x$) is a well-studied model (with major developments in the last 5 years) of noisy tensor problems, whose computational complexity is by now largely well understood.
However, without a sparsity assumption on $x$, tensor PCA requires $\lambda$ to scale as $n^{\Omega(p)}$ for polynomial-time algorithms: this is expensive.

As in many settings, this may be alleviated if the underlying objects to be estimated from data are sparse.
In the matrix setting (i.e. $p = 2$), this has been extensively studied via the "sparse PCA" problem.
The sparse single spike tensor model above is a nice and simple "toy" model in which to understand just how much easier sparsity makes noisy tensor problems.
Thus, the main question addressed by the paper is: what is the computational complexity of sparse tensor PCA, as a function of tensor order $p$, ambient dimension $n$,  signal strength $\lambda$, and sparsity $k$?

The paper has two main results.


(1) The first is an algorithm for the sparse spike tensor model which recovers $x$  in polynomial time when $\lambda \gg k^{p/2}$ -- this a tensor analogue of the well known "diagonal thresholding" algorithm for sparse PCA.
This algorithm improves on the state of the art for the sparse tensor pca problem: previous algorithms required $\lambda \gg \sqrt{p k^p}$ -- this is a meaningful difference for high-order tensors $p \gg 1$.
(Whether such tensors are practically interesting is a little unclear to me, but the problem is mathematically fundamental enough that I think this is not a big deal.)

The paper actually offers a family of algorithms with a tune-able running-time parameter, giving running times which interpolate from polynomial to exponential time.
At the exponential-time end of the scale, the algorithm becomes information-theoretically optimal, capturing the natural brute-force search procedure for recovering $x$.
As the running time increases, the signal-strength $\lambda$ needed by the algorithm naturally decreases: this gives a nice "information-computation tradeoff".

Tune-able algorithms like this were already known for both sparse PCA and tensor PCA, so it is not entirely surprising that there is a common generalization.
(For the record, the algorithm here seems more along the lines of the tune-able algorithm for sparse PCA than the one for tensor PCA.)

(2) A computational lower bound which (almost) shows optimality of the algorithm above among so-called "low-degree" algorithms. This is a style of lower bound which has recently become popular and gives strong evidence that existing algorithmic techniques cannot improve very far on the algorithm given in this paper.

However, there is a small twist here compared to the analogous situations for sparse and tensor PCA (where similar lower bounds are also known): there *is* a gap between the lower bound given here and the algorithm *in the case of $p >> 1$*.
I don't view this as a significant failing of the paper: rather, it highlights the following interesting issue.
The natural way to prove such lower bounds for sparse and tensor PCA yields tight lower bounds -- this approach is to consider a certain "nice" prior on the signal vector $x$.
This same approach appears not to yield a tight lower bound for sparse tensor PCA, which leaves open the intriguing possibility of improved algorithms.

Overall, this paper mainly seems to adapt existing algorithmic and lower bound techniques to the sparse tensor PCA problem.
But it does so ably and comprehensively, and it was by no means obvious a priori what results one would get by applying these techniques in this setting.
It also highlights an interesting gap between the algorithms and lower bound which seem to be accessible with known techniques.
I therefore recommend acceptance.

(I did not carefully check any mathematics; however, the stated guarantees seem at a high level to be in line with what I would expect from the techniques outlined by the authors.)
limitations_and_societal_impact: Limitations are considered carefully. This is a theory paper with no imminent direct societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a family of algorithms for solving the sparse tensor PCA problems, which is based on smooth interpolation between a polynomial-time algorithm and exponential-time search algorithm. Improved results are achieve for sparce PCA in the lower signal/noise ratio regime in distinct sparse signal cases, compared with existing guarantees. Lower bound analysis is also provided for the proposed algorithm.
main_review: The proposed algorithm is analyzed in several sparse models. In the single spike model, the proposed algorithm improves over existing guarantees in the sparser cases for sparse vectors, and achieves the same same guarantees for matrix cases. In the multiple spikes models, the proposed algorithm recovers the sparse PCA case by additional requirement of orthogonality on the sparse vectors. The trade-off is that the proposed algorithm allows weaker signals compared to the noise. Similar results hold when extended to the tensor cases.

The hardness of the result is also demonstrated, where the lower bound for the low-degree polynomials is provided that is same with the sparse PCA and tensor PCA cases. It is also tight in the analyzed case. Overall, the theoretical analysis for the proposed algorithm is rather comprehensive and covers most interesting scenarios. 

The paper is relatively easy to follow and clearly presented. The presented proof is mostly clear and seems correct, though I did not check all detailed analysis for the proof. Overall, I think the paper overall shows an interesting result.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the tradeoff between computational complexity and conditions for recovery in a symmetric sparse tensor estimation problem. There has been a great deal of work on related problems recently in the case of matrices (order 2 tensors) and the case of tensors (without necessarily imposing sparsity constraints). The main achievability result (Theorem 1) provides sufficient condition for single spike model in terms of the ambient dimension, the order the tensors, the degree of sparsity, the signal strength, and an integer parameter the interpolates between a ````"low complexity" algorithm  "high complexity" algorithm (essentially brute force search). Similar results of for a multiple spike model are given in Theorem 2. 

Necessary conditions for a certain testing problem are considered in Theorem 3 which provides necessary conditions such that a polynomial of bounded degree can "distinguish" between a planted model (with a signal of a given strength) and a null mull of only Gaussian noise. Here the criterion for distinguishability is a certain L2 test.

While similar results have been obtained in the literature, the authors argue that their results improve upon the existing ones in a number of ways. 
main_review: On the positive side, I think there are some good ideas in the work. The basic approach outlined at the start of Section 2 is very nice in describing a hierarchy of algorithms based on searching over increasingly more complex signal classes (parameterized by the degree of sparsity). To the extent that the results improve significantly upon the prior work, I think this paper should be published.

One concern with this paper is that it was difficult for me to read and parse the statements. It would have been easier for me if the authors had defined the notation and various recovery criterion and then stated formal results. The current approach gives only informal theorem statements in section 1 (before the notation and recovery objective are clarified) and I found it very difficult to interpret these results. (By contrast the material in section 2 and the appendix was easier to follow). 

Related to the above, I do not know the difference between the big O notation and the "less-than-approximately-equal-to" relation. The authors say they use "standard" notation on this front, but as far as I can tell, there is no "standard interpretation" for the less-than-approximately-equal-to relation. The context of the usage did not provide clues either (in some cases the authors combined the less than approximately sign with the big O notation). With respect to the presentation, I will also provide the feedback that the heavy use of footnotes was unpleasant. Even though I am quite interested in the topic and think the results are interesting, I did not enjoy reading this paper because of the lack of flow.

Finally, my main technical concern is about the interpretation of the "Lower bound" in Theorem 3. From my understanding, the lower bound is based on a certain polynomially constrained approximation to the chi-square divergence. A classical result, which the authors review in the appendix, is that boundedness of the chi-square divergence implies an impossibility result for testing (in the standard sense of type I and type II errors) with arbitrarily small error. Based on this fact, prior work has suggested the the behavior of the polynomially constrained approximation to the chi-square divergence could be used as an heuristic proxy for the difficulty of testing using polynomials. But this interpretation is only heuristic -- by itself, the argument does not rule out the possibility that a polynomial could achieve arbitrarily small testing error and/or recovery error. The discussion following Theorem 3 (e.g, line 183) seems to imply the inacheivability results holds in a stronger sense.  This is a case where I think its crucial to describe the precise meaning of the low-degree recovery criterion before stated the result.






limitations_and_societal_impact: The paper is theoretical and so I think the discussion is appropriate.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the estimation of a rank-one (or more generally a low-rank) tensor $x^{\otimes p}$ ($x \in \mathbb{R}^n$ is assumed to have unit norm) given $Y = \lambda x^{\otimes p} + W$, where $\lambda > 0$ and $W$ is a Gaussian noise tensor. Here the signal vector $x$ is assumed to have only $k$ non-zero entries.

The main contribution of the paper is an algorithm that recovers with high probability the support of $x$ in time $O(n^{p+t})$ provided that $\lambda \geq O(\sqrt{t} (k/t)^{p/2})$. The number $t$ can be arbitrarily chosen between $1$ and $k$, illustrating a tradeoff between statistical constraints on the signal-to-noise ratio $\lambda$ and runtime constraints on the estimation algorithm.
This generalizes to the 'tensor settings' previous results obtained about sparse PCA.

The authors also prove an information-theoretic lower bound for low-degree polynomials. More precisely, they prove that no test based on polynomial of degree at most $D$ can distinguish between the planted model $Y = \lambda x^{\otimes p} + W$ and the pure noise model $Y=W$, when $\lambda$ is smaller than some quantity depending on $D, n, k, p$. This bound generalizes previously obtained results for PCA and tensor PCA. This bound is tight for low-degree polynomials. However there is a gap with the  bound $\lambda \geq O(\sqrt{t} (k/t)^{p/2})$ needed for the algorithm that recovers the support.



main_review: This is a very good paper, in terms of results, clarity and significance. It is particularly well written, making it interesting and enjoyable to read.

The proposed support-recovery algorithm is simple and elegant, while achieving strong guarantees. Such a simple method is particularly refreshing when compared to other heavy/sophisticated approach that have used for low-rank tensor recovery (SDP, tensor unfolding, gradient methods ...). I would be very curious to see if this approach of 'limited brute force' can be extended to other problems! Also it would be of natural interest to see if this approach is optimal, or if one can achieve support recovery at smaller signal-to-noise ratios.

The lower bound for low-degree polynomial is also relevant. However this result is only about the hypothesis problem and low-degree polynomials, while the first result is about support recovery. Hence it seems to me that this result does not really complement the first algorithmic result since:
a) there could a priori exists polynomial time algorithms that works even when low-degree polynomial don't.
b) support estimation may be strictly harder than testing.
For these reasons I do not feel a strong connection between the two main results of the paper.
limitations_and_societal_impact: This point has been clearly and firmly addressed by the authors at line 324 with a dedicated remark asserting: 'This work does not present any foreseeable negative societal consequence'. I strongly agree with them.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of sparse tensor PCA (a generalization of sparse PCA and tensor PCA). The main result is an algorithm that -- for the highly sparse regime in which the sparsity is at most the square root of the signal dimension -- naturally interpolates between a poly-time efficient algorithm and exponential exhaustive search. This result is complemented by lower bounds for the rather popular computational model captured by low-degree polynomials. The lower bounds match the algorithm guarantees (although for the different problem of distinguishability) in the regime of constant tensor order $p$. 

The results of this paper recover several results of the literature, and provide a non-trivial extension. 
main_review: The authors propose a model that generalizes sparse PCA and tensor PCA -- two problems that have received a fair amount of attention in the recent theoretical literature. The idea of the algorithm is quite natural, and the proposed algorithm can be summarised as follows:

i) Create two independent copies of the tensor by adding and subtracting an independent Gaussian tensor (at the cost of a factor $1/\sqrt{2}$ in the SNR).

ii) Perform an exhaustive search over all $t$-sparse vectors and find the one that maximizes the scalar product between the first copy of the tensor and the $p$-th Kronecker power of the candidate. When $t=k$ -- $k$ being the signal sparsity -- this corresponds to exhaustive search. Choosing a smaller $t$ allows the trade-off between complexity and performance.

iii) Use the second copy of the tensor and the maximizer from (ii) to estimate the support of the signal. 

The authors also propose an algorithm for the recovery of multiple signals with disjoint support, which goes along similar lines (although the technical details do become more involved). 

The proof of the low-degree polynomial lower bound is not discussed in the main paper, and an inspection of the appendix seems to reveal that it follows a similar strategy of e.g.  [HKP$^+$17, HS17, DKWB19].

These results generalize existing ones, i.e., [DKWB19, LZ20], and offer a unified view of the two problems involving sparsity and tensors. However, the approach seems to resemble quite closely the one in [DKWB19] (which looks at sparse PCA) and it is not entirely clear what kind of new ingredients are needed to tackle the tensor case. The paper is overall clear and rather well written. The algorithms are described in an intuitive way, and the authors provide a comparison with similar results in the literature -- these are two features that I highly appreciated. At the same time, there are a few issues that I will detail below.

Although I am rather positive about this submission, I have the following concerns:

1) Novelty. As briefly described above, what's the difference with respect to [DKWB19]? What new ingredients are needed to handle tensors instead of matrices? The authors just mention that the family of algorithms is "heavily inspired by [DKWB19]", but a more thorough discussion is needed here.

2) One of the selling points is that, for $r$ distinct $k$-sparse signals, the proposed algorithm requires $\lambda\ge\tilde{\mathcal O}(k)$ ($\lambda$ is the SNR), while known algorithms require $\lambda\ge\tilde{\mathcal O}(k\cdot r)$. However, this paper requires disjoint supports while the existing works just need orthogonality. Is there any way to adapt the proposed approach to cover the case where the signals are just orthogonal? Is there any reason why one would expect that the improvement of the factor $r$ will remain also when the signals are just orthogonal?

3) Lines 67-68. The authors mention that [DKWB19, HSV20] provide a smooth trade-off between signal strength and running time. Is it possible to compare the results of this manuscript to the ones of [DKWB19, HSV20]? I could not find a discussion of this in the main body (the comparison seems to be only with [LZ20]).

4) What's the running time of the algorithm? In the abstract, the running time seems to be of order $n^{p+t}$, while in the theorem statements it becomes $n^{p+t+3}$ (I am looking at the case where $p, r$ are constants). Actually, looking at the proof of Lemma 22 in the appendix, I do not quite see why the running time is $n^{p+t+3}$ and not $n^{p+t}$. You have a factor $n^t$ from the cardinality of $U_t$, and a factor $n^p$ from the computation of the inner product between $Y^{(1)}$ and $u^{\otimes p}$. It seems to me that the additional $n^2$ (from checking the disjoint support) should be summed to $n^p$ (instead of taking the product). Also, why one needs to check for disjoint support for the single signal case? Same comment about the extra $n$ factor coming from obtaining the largest $k$ entries of the vector $\alpha$ (it seems to me that there should be a sum in the calculation of the running time, and not a product). 

5) The statement of Theorem 2 is missing some words/lines (see line 142).

6) Appendix, lines 654-655. How do you get this formula? Please discuss or refer to the corresponding equations in Appendix F. 

7) Appendix, formulas on top of page 30. How is $\tilde{x}$ defined? I could not follow here.


------

*Post-rebuttal update.* The authors addressed my concerns in a satisfactory way, and I have raised my score. 
limitations_and_societal_impact: I do not foresee potential negative societal impact for this contribution.
review_title: null

Meta-review: This paper consider the "Sparse Tensor PCA" problem,  an interesting generalisation  of the spike-matrix model. It is a theoretical paper focusing on computational complexity, and the main results (Theorem 1, 2) discussed the performance of a family of algorithms that smoothly interpolates between polynomial-time and the exponential-time exhaustive search algorithm. 

Overall, there is a clear agreement on the reviewers side to accept the paper for publication at Neurips. The consensus is that this is a good and solid paper, in terms of results and clarity.  While the paper  adapt existing algorithmic and lower bound techniques to the sparse tensor PCA problem, it has been judged well written, and enjoyable to read. Some of the reviewers actually increased their score after the rebuttal, acknowledging that the authors successfully answered their comments.




Decision: Accept (Poster)