The Complexity of Sparse Tensor PCA
Authors: Davin Choo
Tommaso d'Orsi
Venue: NeurIPS 2021 Poster (2021)
Keywords: High-dimensional statistics
Matrix/tensor estimation
PCA

Abstract: We study the problem of sparse tensor principal component analysis: given a tensor $\pmb Y = \pmb W + \lambda x^{\otimes p}$ with $\pmb W \in \otimes^p \mathbb{R}^n$ having i.i.d. Gaussian entries, the goal is to recover the $k$-sparse unit vector $x \in \mathbb{R}^n$. The model captures both sparse PCA (in its Wigner form)  and tensor PCA.

For the highly sparse regime of $k \leq \sqrt{n}$, we present a family of algorithms that smoothly interpolates between a simple polynomial-time algorithm and the exponential-time exhaustive search algorithm. For any $1 \leq t \leq k$, our algorithms recovers the sparse vector for signal-to-noise ratio $\lambda \geq \tilde{\mathcal{O}} (\sqrt{t} \cdot (k/t)^{p/2})$ in time $\tilde{\mathcal{O}}(n^{p+t})$, capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-time and sub-exponential time regimes).

Our results naturally extend to the case of $r$ distinct $k$-sparse signals with disjoint supports, with guarantees that are independent of the number of spikes. Even in the restricted case of sparse PCA, known algorithms only recover the sparse vectors for $\lambda \geq \tilde{\mathcal{O}}(k \cdot r)$ while our algorithms require $\lambda \geq \tilde{\mathcal{O}}(k)$.

Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between signal-to-noise ratio and running time. This lower bound captures the known lower bounds for both sparse  PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples $n$, the sparsity $k$, and the tensor power $p$.

The Complexity of Sparse Tensor PCA
Davin Choo"
Tommaso d'Orsi
Department of Computer Science National University of Singapore davingu. nus edu
Department Computer Science
ETH Zürich
tommaso dors @innf ettz. ch
Abstract
We study the problem of sparse tensor principal component analysis: given tensor Y = W + OF with W E @2R" having i.i.d. Gaussian entries, the goal is to recover the k-sparse unit vector x E g" The model captures both sparse PCA (in its Wigner form) and tensor PCA. For the highly sparse regime of k S yn, we present a family of algorithms that smoothly interpolates between simple polynomial-time algorithm and the exponential-ting -tiee exhaustive search algorithm. For any S S ki our algorithms recovers the sparse vector for signal-to- noise ratio À 2 Ö(vt- (k/t)p/2) in time Ó(nP=(, capturing the state-of-the-art guarantees for the matrix settings (in both the polynomial-timg and sub-ex eub-exxonenttal time regimes). Our results naturally extend to the case of r distinct h-sparse signals with disjoint supports, with guarantees that independent of the number of spikes. Even the restricted case of sparse PCA, known algorithms only recover the sparse vectors for A 2 (k-rr) while our algorithms require À 2 Ö(k). Finally, by analyzing the low-degree likelihood ratio, we complement these algorithmic results with rigorous evidence illustrating the trade-offs between hignal-tonoois ratio and running time. This lower bound captures the known lower bounds for both sparse PCA and tensor PCA. In this general model, we observe a more intricate three-way trade-off between the number of samples n, the sparsity k, and the tensor power p.
Introduction
Sparse tensor principal component analysis is a statistical primitive generalizing both sparse PCA and tensor PCA3. We are given multi-linear measurements the form of a tensor
Y W + 3p E 8"R"
(SSTM)
for Gaussian noise tensor W @PR" containing i.i.d. (0, 1) entries and signal-to-noise ratio > O. Our goal is to estimate the "structured" unit vector x E R". The structure we enforce on is sparsity: [supp(>)] < k. The model can be extended include multiple spikes natural
way: W Eg A (g) and even general order-p tensors: Y W + E Mg for X) = x (1 & ... & (( @PR" In this introduction, we focus on the simplest single spike setting of SSTM.
easy see that sparse PCA corresponds to the setting with tensor order p = On the other hand, tensor PCA is captured by effectively removing the sparsity constraint: |supp(x:) S n. In
Parr of the work was done while the author was ETH Zürich.
"Often in the literature, the terms sparse PCA and spiked covariance model refer the sparse spiked Wishart consider the sparse spiked Wigner matrix model.
model. However,
'Tensor PCA is also known the spiked Wigner tensor model, simply the spiked tensor model. 'Throughout the paper, we write random variables in boldface.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

recent years, two parallel lines of work focused respectively on sparse PCA [JL99, AW08, BR13a. DM16, HKP 17, DKWB19, HSV20, dKNS20] and tensor PCA [MR14, HSS15, MSS16, HKP 17. KWB19, AMMNI99 19], however no result captures both settings. The appeal of the sparse spiked tensor model (henceforth SSTM) is that it allows one to study the computational and statistical aspects of these other fundamental statistical primitives in unified framework, understanding the computational phenomena at play from a more general perspective.
In this work, we investigate SSTM from both algorithmic and computational hardness perspectives. Our algorithm improves over known tensor algorithms whenever the signal vector is highly sparse. We also present a lower bound against low-degree polynomials which extends the known lower bounds for both sparse PCA and tensor PCA, leading a more intricate understanding of how all three parameters (n, k and p) interact.
1.1 Related work
Disregarding computational efficiency, it is easy to see that optimal statistical guarantees can be achieved with simple exhaustive search (corresponding find a k-sparse unit vector maximizing (Y, x This algorithm returns a k-sparse unit vector T achieving constant squared correlation with the signal z as soon as X Z vk. log( (mp/k) /k. That is, whenever À Z max |= (W, w Unfortunately, this approach runs in time exponential in k and takes super-polynomin time when S k. As such, assume p S k from now on.
the maximum likelihood estimator):
Taking into account computational aspects, the picture changes. good starting point to draw intuition for SSTM is the literature on sparse PCA and tensor PCA. We briefly outline some known results here. To simplify the discussion, we hide absolute constant multiplicative factors using (+)).
2(-), S. and Z, and hide multiplicative factors logarithmic in n using (.).
1.1.1 Sparse PCA (Wigner noise)
Sparse PCA with Wigner noise exhibits a sharp phase transition in the top eigenvalue of Y for A 2 V [FPO7]. In this strong signal regime, the top eigenvector' of Y correlates" with with high probability, thus the following spectral method achieves the same guarantees as the exhaustive search suggested above: compute leading eigenvector of Y and restrict it to the top & largest entries in absolute value. Conversely, when X < vnn, the top eigenvector of Y does not correlate with the signal In this weak signal regime, [JL09] proposed simple algorithm known as diagonal thresholding: compute the top eigenvector of the principal submatrix defined by the & largest diagonal entries of Y. This algorithm recovers the sparse direction when À 2 Ö(k), thus requiring almost an additional vi factor when compared to inefficient algorithms. More refined polynomial-time algorithms (low-degree polynomials [dKNS20], covariance thresholding [DM16] and the basic SDP relaxation [dGJLO7, dKNS20]) only improve over diagonal thresholding by logarithmic factor in the regime n 1-1) x 122 < n. Interestingly, multiple results suggest that this informattion-computtiii gap is inherent to the sparse PCA problem [BR13a, 13,, DKWB19, dKNS20J. Subexponential time algorithms and lower bounds have also been shown. For instance, [DKWB19, HSV20) presented smooth trade-off's between signal strength and running time."
*One could also aim to find a unit vector with correlation approaching one or, in the restricted setting of E {0, #1/ /kkk). aim to recover the support of x. At the coarseness our discussion here, these goals could be considered mostly equivalent.
'Note that the problem input is of size nº. So when p 2 k exhaustive search takes n (()) time which is polynomial n². Thus, the interesting parameter regimes occur when p S
By "top eigenvector" or "leading eigenvector", we mean the eigenvector corresponding to "largest (in absolute value) eigenvalue".
"More precisely, the vector consisting of the k largest (in absolute value) entries of c.
Both works studied the single spike matrix setting. [HSV20] only considers the Wishart noise model and thus its guarantees cannot be compared to ours. [DKWB19 19] studied both the Wishart and Wigner noise models. In the Wishart noise model setting. both [HSV20] and [DKWB19 19] observe the same tradeoff' between running time and signal to noise ratio. In the Wigner noise model setting, our algorithm and the algorithm of [DKWB19 19] offer the same mmooth-trade off between running time and signal strength, up universal constants.

---

1.1.2 Tensor PCA
In tensor settings, computing max (Y, ..)) is NP-hard already for p 3 [HL13]. For even tensor powers p. one can unfold the tensor Y into a np/2-by-nP matrix and solve for the top eigenvector [MR14]. However, this approach is sub-optimal for odd tensor powers. For general tensor powers p. successful strategy tackle tensor PCA has been the use of semidefinite programming [HSS15, BGL16, HSS19]. Spectral algorithms inspired by the insight of these convex relaxations have also been successfully applied the problem [SS17]. These methods succeed in recovering the single-spike a when À 2 Ô (nP/1), thus exhibiting large gap when compared to exhaustive search algorithms. Matching lower bounds have been shown for constant degrees in the Sum-of-Squares hierarchy [BGL16, HKP+ 17] and through average case reductions [BB20].
1.1.3 Sparsity-exploiting algorithms and tensor algorithms
It is natural to ask how do the characteristics of sparse PCA and tensor PCA extend to the more general setting of SSTM. In particular, there are two main observations to be made.
The first observation concerns the sharp computational transition that we see for k: S vn in sparse PCA. In these highly sparse settings, the top eigenvector of Y does not correlate with the signal and so algorithms primarily based on spectral methods fail to recover it. Indeed, the best known guarantees are achieved through algorithms that crucially exploit the sparsity of the hidden signal. These algorithms require the signal strength to satisfy 2 Ö(VR), with only logarithmic dependency on the ambient dimension. To exemplify this to extreme, notice how the following algorithm can recover the support xxx with the same guarantees as diagonal thresholding, essentially disregarding the matrix structure of the data: zero all but the k.2 largest (in absolute value) entries of Y. A natural question to ask whether a similar phenomenon may happen for higher order tensors. the highly sparse settings where l 5 /ni can we obtain better algorithms exploiting the sparsity of the hidden vector? Recently, partial answer appeared in [1.720] with a polynomial time algorithm recovering the hidden signal for À 2 Ö(p )), albeit with suboptimal dependency on the tensor order p.
The second observation concerns the computational -statssstia gap in the spiked tensor model. As p grows, the gap between efficient algorithms and exhaustive search widens with the polynomial time algorithms requiring signal strength X 2 Ô (nz/4) while exhaustive search succeeds when 2 Ö(V)) [MR14]. The question here is: how strong the dependency on p for efficient algorithms in sparse signal settings?
In this work, investigate these questions in the high order tensors regime p E (1). We present family of algorithms with a smooth trade-off between running time and signal-to-noise ratio. Even restricting to polynomial-tin
settings, our algorithms improve over previous results. Furthermore, through the lens of low-degree polynomials, we provide rigorous evidence of an exponential gap in the tensor order p between algorithms and lower bounds.
Remark. The planted sparse densest sub- hub-yypeggaphh model [CPMB19, BCPPM2, CPSB20J is closely related to SSTM. We discuss this model in Appendix E.
1.2
Results
1.2.1
Single spike setting
Consider first the restricted, but representative, case where the planted signal is a (k, A)-sparse unit for some constant A 2 1. vector with non-zero entries having magnitudes in the range AVE We say that the signal is flat when A and approximately flat when A'
A
VE
Our first result is a limited brute force algorithm - informally, an algorithm that smoothly interpolates between some brute force approach and some "simple" polynomial time algorithm that exactly recovers the signal support of the planted signal 10
Theorem (Algorithm for single spike sparse tensor PCA, Informal), Let A 2 be a constant. Consider the observation tensor
Y W 0r
A similar algorithm analyzed by [DKWB19] for the special case of p and 1.
3

---

where the additive noise tensor W E @'R" contains i..d. [N,, entries and the signal E R is (ke -pasre unit vector with signal strength À > Let S t I k be an integer. Suppose that
2A2k V
A 2
Inn.
Then, there exists an algorithm that runs in (pne+*) time and, with probability 0.99, outputs the support of
Let's first consider Theorem 1 in its simplest setting where A = 1 and t is fixed constant. For k Vn. the theorem succeed when À 2 O(kp/2). thus improving over the guarantees of known tensor PCA methods which require À 2 ((P//4). addition, since support recovery is exact, one can obtain good estimate" of the planted signal by running any known tensor PCA algorithm on the subtensor corresponding its support. Indeed, the resulting subtensor will be of significantly smaller dimension and the requirement needed on the signal strength by single-spike tensor PCA algorithms are weaker than the requirement we impose on À (see Remark for details). As result, our algorithm recovers the guarantees of diagonal thresholding in the matrix (p 2) setting. Our polynomial algorithm also improves over the result of [LZZ2]], which required À Z /pk? log n, by removing the polynomial dependency of the tensor order p in the signal strength X.
Consider now the limited brute force parameter f. From the introductory exposition, we know that one can obtain a statistically optimal algorithm by performing a brute force search over the space of s-spaase flat vectors in R". The limited brute force algorithm is natural extension that takes into account computational constraints by searching over the smaller set of t-sparse flat vectors, for 1 S t S k, maximize (Y, u P)) The parametric nature of the algorithm captures both the brute force search algorithm (when f. = k) and the idea of diagonal thresholding (when / = 1 and p = 2). As long as k; using larger represents a direct trade-off between running time and the signal-to-noise ratio. Extending the result to approximately flat vectors, the dependency on A in the term 22 can be removed by increasing the computational budget to some value t' 2 2.
1.2.2 Multiple spikes
Theorem 2 (Algorithm for multi-spike sparse tensor PCA, Informal). Let A 2 1 be constant. Consider the observation tensor
Y Y W
2
Cp (a)
where the additive noise tensor W 8RR" contains i.i.d. N(0,1) entries and the signals I())..., I(r) E RD are (k, A)-sparse unit vectors with disjoint supports and corresponding signal
strengths X ... 2 d > O. Let S S k be an integer and < 6 $11 1/2. Suppose that
/
2A2k)
ス V
Inn and X 2 A (26)p-1.
Then, there exists an algorithm that runs in Orprett)) time and, with probability 0.99, outputs the individual signal supports of ((=())))... [(m(T))) for some unknown bijection
[r].
Theorem 2 requires two assumptions the signals: (1) signals have disjoint support; (2) there is
bounded signal strength gap of X, 2 _ (2e)a-1. -A1- In the context of sparse PCA, algorithms that recover multiple spikes (e.g. [JL.99, DM16)) only require the sparse vectors to be orthogonal.
However, their guarantees are of the form X, 2 Ö (Uuyrr)) supp (F())) That is, when the
signals have disjoint supports, they require the smallest signal to satisfy X, 2 ( -r. In comparison, already for constant Theorem successfully recovers the supports when X > ((k).
Recovery up to a global sign flip since (u, v)²² (u, uu for even tensor powers p. 12 The result of [LZ20] extends to the settings where Y = W + XX for an approximately flat tensor X E "R." Both Theorem I and Theorem 2 can also be extended these settings (see Appendix B.2).

---

thus removing the dependency on the number of signals and improving the bound by a 1/r factor' Meanwhile, the bounded signal strength gap assumption common identifiability assumption (e.g. see [CMW13, DM16)). We remark that Theorem 2 provides a tradeoff between this signal strength gap assumption and the signal strengths: we can recover the supports with a smaller gap the signal strengths are increased proportionally increasing X, by multiplicative factor a enables the algorithm to succeed with gap that is smaller by a multiplicatiie factor 1/a. As an immediate consequence, we also obtain tradeoff between gap assumption and running time: every time double I (while ensuring 1 < S k), X, increases by factor of (1/ (1/v2)p-1 and thus the algorithm can succeed with a smaller gap. Finally, as in the single spike case, the exact support recovery allow us to obtain good estimate of each signal by running known tensor PCA algorithms.
Remark
We remark that these results can be extended to the general tensor settings
Y
where for q E [r], M(n) = I() @ @ F(rr)) E 8PR" in a natural way. See Appendix B.2.
1.2.3 An exponential gap between lower bounds and algorithms
SSTM generalizes both sparse PCA and tensor PCA. Hence, tight hardness result for the model is interesting as it may combine and generalize the known bounds for these special cases. Here, give a lower bound for the restricted computational model captured by low-degree polynomials. Originally developed in the context of the sum of squares hierarchy, this computational model appears accurately predict the current best-known guarantees for problems such as sparse PCA, tensor PCA, community detection, and planted clique (e.g. see [HS17, HKP 17, Hop18, 18, BHK 19, 19, KWB19, dKNS20]).
Theorem (Lower bound for low-degree polynomials, Informal). Let S D S 2n/p and v be the distribution of Z E 8PR" with i..dd entries from (0,, 1). Then, there exists a distribution over tensors Y E @F of the form
Y W Sr
where W E R is a noise tensor with ii.dd N N(0, 1) entries, the marginal distribution of x is and and W are distributionally independent,
supported on vectors with entries +1 +1//TT 0 such that whenever
DD
P/4
k:
np
P/2
A
min
1
In
2
pD
pD
ck2
is indistinguishable" from v with respect to all polynomials of degree at most D.
Theorem states that for certain values of X, low-degree polynomials cannot be used to distinguish between the distribution of Y and W typical values of low-degree polynomials the same (up to a vanishing difference) under both distributions. The theorem captures known results in both sparse
and tensor PCA settings. When p = 2, our bound reduces to S min Vni, VD (1 |n 2n 1)
matching known low-degree bounds of [DKWB19 19] in the sparse PCA setting. Meanwhile, in the
8/1
tensor PCA settings (p 2 2, k = 12), Theorem 3 implies a bound of the form À VD PD recovering the results of [KWB19].
thus
PIt is an intriguing question whether an improvement of 1/r can be achieved in the more general settings of orthogonal spikes. Our approach relies the signals having disjoint support and expect it to not be generalizable orthogonal signals. This can noticed the simplest settings with brute-force parameter t = 1 and = 2 where the criteria of Algorithm for finding an entry of a signal vector to look at the diagonal entries of the data matrix. In this case, the algorithm may be fooled since the largest diagonal entry can depend on more than one spike. Nevertheless, we are unaware of any fundamental barrier suggesting that such guarantees computationally hard achieve.
In the sense that for any low-degree polynomial pYY) we have Enp(Y) - o()). See Appendix A.4.2.
vVp(Y)
5

---

For constant power p and k 2 vn, our lower bound suggests that no estimator captured by polyno- mials of degree D log n can improve over our algorithmic guarantees by more than logarithmic factor. However, for p E w(1), an exponential gap appears between the bounds of Theorem 3 and state-of-the-are algorithms (both in the sparse settings as well as in the dense settings). 15 As concrete example, let us consider the setting where p = n < k. The polynomial time algorithm of Theorem requires À Z O(kP/²) while according to Theorem 3 it may be enough to have Ö (k/no.1)P2 Similarly, for k Z /np, known tensor algorithms recovers the signal for A 2 O(NP/t) while our lower bound only rules out algorithms for À S O (n0.9/44).
Surprisingly, for the distinguishing problem considered in Theorem 3, these bounds appear to be tight. For a wide range of parameters (in both the dense and sparse settings) there exists polynomial time algorithms that can distinguish the distributions v and ju right at the threshold considered in Theorem 3 (see Appendix C). It remains a fascinating open question whether sharper recovering algorithms can be designed or stronger lower bounds are required.
Finally, we would like to highlight that this non-trio trivial dependency on is a purely computational phenomenon as it does not appear in cogrmattion-thhoreed bounds (see Appendix D).
Remark Note that Theorem 3 is not in itself lower bound for the recovery problem. However, any algorithm which obtains a good estimation of the signal vector x for signal strength À 2 Volog can be used to design probabílistic algorithm which solve the distinguishing problem for signal strength (A))). Let us elaborate. Consider an algorithm that given Y = W + 2r outputs a vector i such that a)) 0.9. With high probability, max = (W, -WW,=pp = Õ(V)) and thus (Y, [I > A- (0.9)²
Ö(V)). Therefore, one can solve the distinguishing problem as follows:
output "planted" if (YY, & y Z Vk log n and "null" otherwise.
1.3 Notation and outline of paper
We write random variables in boldface and the set {1...., n) as [n]. We hide absolute constant multiplicative factors and multiplicative factors logarithmic using standard notations: O(-), 22()), S. 2, and (.). We denote by Cp E R the standard basis vectors. For x E RR" we use supp(z) S [m]] to denote the set of support coordinates. We say that is a (k:, A)-spare vector if k E [n). constant A 2 1, |supp(1)) = k, and AVE S | S VR say that x is k-sparse flat vector and may omit the parameter A. For general A > 1, we say that is approximately flat. For integer t 1, we define U,
A for & E supp(x)). When A = 1, we
{ u {
vt 0, v7 [supp(u)] = as the set of 1-sparse flat vectors. For a tensor T E &PPT" and a vector u E R", their inner product is defined as (T, u OP)- $1 Sppn
Σ Thm...d Uig ... Uip
The rest of the paper is organized as follows: Theorem I and Theorem 2. In Section 3, we flesh out some concrete unresolved research ques- tions. Appendix A contains preliminary notions. We formally prove Theorem and Theorem in Appendix B. The lower bound Theorem 3 is given in Appendix C. We present information theoretic bound in Appendix
In Section 2, we introduce the main ideas behind
D. Appendix E discusses the planted sparse densest sub-hypergraph model. Finally, Appendix F contains any deferred technical proofs required throughout the paper.
2 Recovering signal supports via limited brute force searches
We describe here the main ideas behind our limited brute force algorithm. We consider the model Model 4 (Sparse spiked tensor model). For A 2 1 2 1, S n we observe a tensor of the form
Y W
8p Ag
(4)
E
ERR"
g=1
I' particular, in the sparse settings & < /np, the p/2 factor could not be seen in the restricted case of sparse PCA (as this factor is constant when p 2).

---

where W E &'R" is a noise tensor with i..dd N(,, 1) entries, A1 2... 2 X, > 0 are the signal strengths, and 2(1)....:: (r)) are k-sparse flat unit length signal vectors.
We first look at the simplest setting of single flat signal (i.e. A and r 1). Then, we explain how to extend the analysis to multiple flat signals. For cleaner discussion, we assume here that all the non-zero entries of the sparse vector x and vectors in the set U, have positive sign. Our techniques also easily extend to approximately flat vectors (where A 2 1) and general signal tensors (()) @ @ (p) E @"R". We provide details for these extensions in Appendix B.
2.1 Single flat signal
Limited-brute force As already mentioned in the introduction, brute force search over U3 for the vector maximizing (Y, u u&P) returns the signal vector x (up to a global sign flip) with high probability whenever X Vk log This algorithm provides provably optimal guarantees but requires exponential time (see Appendix for an copommation-thhorete lower bound). The idea of a limited brute force search is to search over smaller set U, (1 maximizer V. to determine the signal support supp (z). The hope is that for sufficiently large signal-to-noise ratio, this t-sparse vector v. will still be non-trivially correlated with the hidden vector x. Indeed as grows, the requirement on À decreases towards the information-theoretii bound, at the expense of increased running time.
k) instead, and use the
As a concrete example, consider the matrix settings (p = 2). is easy to generalize the classic diagonal thresholding algorithm ([LL09)) into limited brute-force algorithm. Recall that diagonal thresholding identifies the support of x by picking the indices of the largest & diagonal entries of Y. In other words, the algorithm simply computes (Y, e,,0% for all E [m] and returns the largest indices. From this perspective, the algorithm can be naturally extended to t > 1 by computing the (+) vectors U2 maximizing (Y, u x² and reconstructing the signal from them. For t k. the algorithm corresponds to exhaustive search.
With this intuition in mind, we now introduce our family of algorithms, heavily inspired by [DKWB19]. We first apply a preprocessing step to obtain two independent copies of the data.
Algorithm Preprocessing
Input: Y.
Sample a Gaussian tensor Z E 8PR" where each entry is an i.i.d. standard Gaussian N(00 1).
Return two independent copies (() and (2) of Y as follows:
y()) Z) and (2)
V2 -Y-Z) 2)
2
Algorithm effectively creates two independent copies of the observation tensor Y. To handle the noise variance, the signal-to-noise ratio is only decreased by the constant factor 1/v2. For simplicity, we will ignore this constant factor in the remainder of the section.
Algorithm 2 Single spike limited brute force
Input: t and (1), Y obtained from Algorithm Compute v. argmax neU, (1) _OP).
Compute the vector a E R²" with entries ay := (2) v 3p-1 @ Ee) for every & E [n]. Return the indices of the largest ls entries of
Thee algorithm [DKWB19] specialization of ours (with comparable guarantees) the simplest setting of = 2 and a single spike. However, looking at [DKWB19], 19], it is priori unclear how to generalize the result to the settings of our interest. This is especially true in the tensor settings (p 2 3) with multiple spikes, where signals may interfere with each other.
7

---

The signal support recovery process outlined in Algorithm 2 has two phases. In the first phase, we search over U, to obtain a vector v. that is correlated with the signal z. In the second phase, we use v. to identify supp(ar). The correctness of the algorithm follows from these two claims:
The t-sparse maximizer v, shares large fraction its support coordinates with signal ø.
(ii) The largest entries of a belong to the support supp(r) of signal æ.
Crucial to analysis is the following standard concentration bound on Gaussian tensors. We directly use Lemma 5 in our exposition here, and formally prove a more general form in Appendix F.I.
Lemma 5. Let p S n, > 0 be an integer, and W &PPTR" be a tensor with i.i.d. N(0, 1) entries. Then, with high probability, for any E U..
(W, u P) S V Vllon.
For some constant
<<s]) 1/2,, suppose that
k X x (1 - (1- V
1
logn.
(1)
For any u E Uy with support supp(u) S supp(z), we have
(r o ((x, u) (W(1), u oy 2 x (1)--0)
On the other hand, any U, with support satisfying (supp(u) n suppp(=) (1 E) has small correlation with ( in the sense that
( k
4 + +0 (Vtlog)))
1 = A(2, u)" (W(), 2 - A1. c)p
By Eq. (I), with high probability, v. will have at least a fraction (1 -e) e) of its support contained in supp(æ), yielding the first claim. Observe that does not completely overlap with A priori, this might seem to an issue. However, turns out that we can still use v, to exactly reconstruct the support of Indeed, for all é supp(z),
at = X.22 De U.. + (2)
U. 00p-1 2 8ee)
A (1-6)
W12) -pp- 0ec)
Vlogn + (W (2) pp-1 x es)
Now, by independence (2) and v.. (2) @p-1 ee) behaves like standard Gaussian. Thus, with high probability, (W -ep @p-1
ez) S Vlog and a 2 Vlog Conversely, if is not in the support of the signal, then a S Vlog n. So, the vector a acts as indicator of the support of a!!
Remark 6. In its simplest form of 1, Algorithm 2 does exploit the tensor structure of the data: performs entry-wise search for the largest (in magnitude) over a subset of Y. However, this is longer true grows. For k; the algorithm computes the k-sparse flat unit vector maximizing (1), Sp).
2.2 Multiple flat signals with disjoint signal supports
Consider now the setting with r > 1 spikes. Recall that we assumed the vectors I(I).... Z(r) to have non-intersecting supports. We also assumed that for any g, g' E [r] and some fixed scalar 0 S k S 1, if >, 2 by,, then Ay Ag- We remark that may not recover the signal supports in a known
8

---

order, but we are guaranteed to recover all of them exactly. For simplicity of discussion, let us assume here that we recover the vector 2() at iteration i.
The idea to recover the r spikes essentially to run Algorithm 2 r times. At first, we compute the t-sparse vector V. by maximizing the product (r((), u Then, using V., we compute the vector a to obtain a set I, S [r]. With high probability, we will have I₁ = supp (I(1)) and so we will exactly recover the support of (1)) In the second iteration of the loop, repeat the same procedure with the additional constraint of searching only over the n dimensional subset of Ug containing vectors with disjoint support from I1. Similarly, at iteration we search over the subset of Ug containing
vectors with disjoint support from U Iz. As before, we first preprocess the data to create two
15jçi
independent copies ( and (2). Concretely:
Algorithm 3 Multi-spike limited brute force
Input: k, t,r and Y ( (2) obtained from Algorithm 1.
Repeat for to r:
Compute v, argmax uEU, (Y w) subject to supp (v.) n
U Iz = G.
isici
Compute the vector a R² with entries ag := (2) v. Let I4 be the set of indices of the largest &t entries of a. Return ,
1 @ ee) for every E [n].
The proof structure is similar to that of Algorithm 2 and essentially amounts to showing that the claims (i) and (ii) described in Section 2.1 hold in each iteration.
Let Amin = minge[r] A and Amax = maxge(r) Ag For some 0 < 1/2, let 2
such
that Amin 15 Amax- Suppose that
Amin c. (1 c)p Ve ((())
k
P log and Amin 2
p-1
1-c
mmax
Consider an arbitrary iteration i and suppose that we exactly recovered the support of one signal in each of the previous iterations. Without loss of generality, assume that Xmax is the largest signal strength among the yet to be recovered signals, and let [mmax] be one such corresponding signal.
For U, satisfying supp(u) S supp((((mxx) we have
t -0 -V((logg)
(17)) = Amax (m(ax) u)" + (W(11, mm 2 Amax
kk
On the other hand, for any u E U2 such that |supp (u) O ssupp (I(7)
S (1 - c) . for all E [r],
(1) u Sp)
Σ
)p( upp + (w(1), SP)
gelrl
(
tt) 4
((1 - c)2 + (²) + 0 ( (Vtlogn)
Xmax
1
(1) (1 c)p-1 + 0 (Vllogn)
4
Amax
1o
Thus, as in Section 2. follows that v. satisfies |supp (v.) n supp (z)) 2 (1 e) -)- for some signal T(a)- Note that (()) may not be [(maxx- Even though v. does not exactly overlap with any of the signal vectors, we will not accumulate an error at each iteration. This because, analogous to the single spike setting, we exactly identify the support of signal through For any

---

i supp (z()). it holds that at 2 Vlogn as before because (W - @ 8er) x Vlogn.
Conversely, since signal supports are disjoint, we see that for $ supp (z()))
Σ
(170)) (W(2) - x ez)
0f
nE(r]
GP-
Amax
+ +0 Vlog
V
k
Amin
e
+ (0(vvlgg (llgg
Vk
V log n.
So, once again, a exactly identifies the support of (i()) with high probability.
Remark 7 (On the strength of the assumption on k). As already briefly discussed in Section 1.2, the algorithm provides three-way trade-off between signal gap K, signal-to-noise ratio À and running time. By appropriately choosing the constant > O. the algorithm can tolerate different values of p-1
R. Indeed, the above analysis holds as long as K. -
This suggests two ways in which
we can loosen the requirement Amin 2 K Amax and still successfully recover the signals through Algorithm 3. One is increase the running time, so that we can decrease without increasing the signal-to-noise ratio Amiu. The other to decrease and increase the value of Amin accordingly.
Remark 8 (On independent copies of Y). To clarify why it suffices to have 2 independent copies of Y even for multiple iterations, observe that at each iteration i, the choice of the set I, depends only the vector with high probability. Consider the following thought experiment where we given fresh copy ( of Y in the second phase of each iteration i of the algorithm (while still using only single copy Y (1) for all the first phases). Even with fresh randomness, the result is the same as Algorithm with high probability because at each iteration the choice of maximizer v. causes the same output.
Remark (Reconstructing the signals from their supports). After recovering individual signal supports, one reconstruct signals using known tensor PCA algorithms (e.g. [MR 14, HSS15)) on the subtensor defined by each recovered support. The signal strength required for this new subproblem is weaker and is satisfied by our recovery assumptions. For instance, by concatenating our algorithm with [HSS15, Theorem 7.1], one obtains vectors (( ((r) such that (6(o). a())) 2 0.99, for any E [r]. with probability 0.99.
Open questions
Open question 1. Theorem 2 improves over existing sparse PCA multi-spike recovery algorithms (which only assumed orthogonal spikes) by a factor of 1/r in the case where these planted signals have disjoint support. Can one still obtain improvement of 1/r if we only assume orthogonality?
Open question 2. For E w(1), there is an exponential gap between the bounds of Theorem 3 and state-of-the-ar algorithms. natural question whether one can design better recover algorithms or prove stronger lower bounds for this range of tensor power p E w(1)?
Remark (Societal impact). This work does not present any foreseeble negative societal consequence.
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 815464). This research/project supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG-PhD/2021 108-001))- We thank David Steurer for several helpful conversations. We thank Luca Corinzia and Paolo Penna for useful discussions about the planted sparse densest sub-hypergraph model.
10

---

References
[AMMN19] Gerard Ben Arous, Song Mci, Andrea Montanari, and Mihai Nica. The landscape the spiked tensor model. Communications Pure and Applied Mathematics, 72(11):2282- 2330, 2019. 2
[AW08] Arash A Amini and Martin Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE International Symposium on Information Theory, pages 2454-2458. IEEE, 2008. 2
[BB20] Matthew Brennan and Guy Bresler. Reducibility and statistical conpsticalloomppuaaiionnaa gaps from secret leakage. Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austrial, pages 048-847, 2020. 3
[BCPS20] Joachim M Buhmann, Luca Corinzia, Paolo Penna, and Wojciech Szpankowski. Recovery of Planted k-Densest Sub-Hypergraph, 2020. Available at: https: //www. cs. purdue. wwwruu..ed//aee.ee http://omms//ppppae pttppppppppesssstttolllleeee
pdf. 3, 27
[BGL16] Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of-squares certifi- cates for maxima of random tensors on the sphere. arXiv preprint arXiv: 1605.0900,. 2016. 3
[BHK 19] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2):687-735, 2019. 16, 17
[BKW20] Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of certifying bounds on constrained PCA problems. In / Ith Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pages 78:1-78:299 2020. 16
[BR13a] Quentin Berthet and Philippe Rigollet. Complexity Theoretic Lower Bounds for Sparse Principal Component Detection. In Conference on Learning Theory, pages 1046-1066, 2013. 2
[BR13b] Quentin Berthet and Philippe Rigollet. OPTIMAL DETECTION OF SPARSE PRIN- CIPAL COMPONENTS IN HIGH DIMENSION. The Annals of Statistics, (1(4):1780- 1815, 2013. 2
[Cam60] Lucien Le Cam. Locally asymptotically normal families. Univ. California Publ. Statist.,
1960. 17
[CMW13) 13] T Tony Cai, Zongming Ma, and Yihong Wu. SPARSE PCA: OPTIMAL RATES AND ADAPTIVE ESTIMATION. The Annals of Statistics, (1(6):3074-311 3110, 2013. 5
[CPMB19] Luca Corinzia, Paolo Penna, Luca Mondada, and Joachim Buhmann. Exact Recovery for a Family of Conmmunity-etecttoon Generative Models. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 415-419, IEEE, 2019. 3,27
[CPSB20] Luca Corinzia, Paolo Penna, Wojciech Szpankowski, and Joachim M. Buhmann. Statis- tical and computational thresholds for the planted k-densest sub-hypergraph problem, 2020. 3, 27
[dGJLO7] Alexandre d' Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434-448, 2007. 2
[dKNS20] Tommaso d' d'Ori, Pravesh K. Kothari, Gleb Novikov, and David Steurer. Sparse PCA: Algorithms, Adversarial Perturbations and Certificates, 2020. To appear in FOCS 2020.
2, 5, 18
[DKWB19] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Subexponential-Timg Algorithms for Sparse PCA. arXiv preprint arXiv: 1907. 1635, 2019. 2, 3,

---

[DM66]
Yash Deshpande and Andrea Montanari. Sparse PCA via Covariance Thresholding. The Journal of Machine Learning Research, 17(1):4913-4953. 2016. 2, 4.5
[Duc16] John Duchi. Lecture Notes for Statistics 311/Eleccriiaal engineerin 277,2016 Available at:
pdf. 15,
16
[FP07] Delphine Féral and Sandrine Péché. The Largest Eigenvalue of Rank One Deformation of Large Wigner Matrices. Communications in mathematical physics, 172((1):85-22)) 2007. 2
[HKP-17] 17] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Stcurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pages 720-731, IEEE, 2017. 2, 3, 5, 16, 17, 22
[HL13] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
[Hop18] Samuel Brink Klevit Hopkinn. STATISTICAL INFERENCE AND THE SUM OF SQUARES METHOD. PhD thesis, Cornell University, 2018. 5, 16, 17
[HS17] Samuel B Hopkins and David Steurer. Efficient Bayesian estimation from few samples: community detection and related problems. In 20/7 JEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379-390. IEEE, 2017. 5, 16, 17, 22
[HSS15] Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via cum-of-squares proofs. In Conference Learning Theory, pages 956 1006, 2015. 2, 10
[HSS19] Samuel B Hopkins, Tselil Schramm, and Jonathan Shi. A robust spectral algorithm for overcomplete tensor decomposition. In Conference on Learning Theory, pages 1683-1722. 2019..
[HSV20] Guy Holtzman, Adam Soffer, and Dan Vilenchik. A greedy anytime algorithm for sparse PCA. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], pages 1939-1956, 2020. 2
[HW20] Justin Holmgren and Alexander Wein. Counterexamples the low-degree conjecture. arXiv preprint arXiv:2004.088 084554, 2020. 17
[JL09] lain M Johnstone and Arthur Yu Lu. On Consistency and Sparsity for Principal Compo- nents Analysis in High Dimensions. Journal of the American Statistical Association, 104(486):682-63) 693. 2009. 2, 4,
[KWB19] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio. arXiv preprint arXiv: 11636 2019. 2,
[LZ20] Yuetian Luo and Anru Zhang. Tensor clustering with planted structures: Statistical optimality and computational limits. CoRR. abs/2005. 2020. 3, 4, 21
[MR14] Andrea Montanari and Emile Richard. statistical model for tensor PCA. In Advances in Neural Information Processing Systems, pages 2897-2905, 2014. 2, 3, 10
[MSS16] Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-ting time tensor decomposi- tions with sum-of-square In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 438 446. IEEE, 2016.
[NP33] J. Neyman and E. S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical Physical Character, 231:289-337, 1933. 17
12

---

[NWZ20] Jonathan Niles-Weed and Ilias Zadik. The all-or-nothing phenomenon in sparse tensor pea. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors. Advances in Neural Information Processing Systems, volume 33, pages 17674-17684. Curran Associates, Inc., 2020.
[NZ20] Jonathan Niles- Weed and Ilias Zadik. The all-or nothing phenomenon in sparse tensor PCA. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. 25
[O'D14] Ryan O'Donnell. Analysis boolean functionn. Cambridge University Press, 2014. 15
[PWB16] Amelia Perry, Alexander S. Wein, and Afonso S. Bandeira. Statistical limits of spiked tensor models. CoRR, abs1161..077288 2016. 25
[PWB-20) Amelia Perry, Alexander S Wein, Afonso S Bandeira, et al. Statistical limits of spiked tensor models. In Annales de l'Institul Henri Poincaré, Probabilités et Statistiques, volume 56, pages 230-264. Institut Henri Poincaré, 2020. 26
[SC19] Jonathan Scarlett and Volkan Cevher. An Introductory Guide to Fano's Incquality with Applications in Statistical Estimation. arXiv preprint 19010005, 2019. 16
[SS17] Tselil Schramm and David Steurer. Fast and robust tensor decomposition with applica- tions to dictionary learning. arXiv preprint arXiv: 2017.
[Tao12] Terence Tao. Topics random matrix theory, volume 132. American Mathematical
Soc., 2012. 18
[Tao14] Terence Tao.
Metric
entropy analogues of sum set theory, 2014. https://terrytao -ww- theory/. 15
Available at:
[Tro15] Joel A Tropp. An Introduction Matrix Concentration Inequalities. arXiv preprint 1rXiv:550.0155// 2015. 18
[TS14] Ryota Tomioka and Taiji Suzuki. Spectral norm of random tensors. arXiv preprint arXiv: 1407. 2014. 18
[Ver18] Roman Vershynin. High- Sigh--iimnsional Probability: An Introduction with Applications in Data Science, volume 47, Cambridge University Press, 2018. 15, 18, 28
13


Reviews:
[{"review_id": "6ZxcBIU1dTb", "reviewer": "Reviewer_y5Ce", "summary": "# Review for \"The Complexity of Sparse Tensor PCA\"\n\nThis 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.\nThe problem is as follows: given a \"single-spike\" tensor of the form\n\n$T = \\lambda \\cdot x^{\\otimes p} + W$\n\nwhere $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$.\n(The problem can be generalized to more than one spike $x$; this is treated carefully in the paper.)\n\nThe paper contains interesting new algorithms and computational lower bounds for this problem.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Tensor methods are useful in high-dimensional statistics, with key applications to learning latent variable models, multi-way factor analysis, etc.\nThe 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.\nHowever, without a sparsity assumption on $x$, tensor PCA requires $\\lambda$ to scale as $n^{\\Omega(p)}$ for polynomial-time algorithms: this is expensive.\n\nAs in many settings, this may be alleviated if the underlying objects to be estimated from data are sparse.\nIn the matrix setting (i.e. $p = 2$), this has been extensively studied via the \"sparse PCA\" problem.\nThe 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.\nThus, 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$?\n\nThe paper has two main results.\n\n\n(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.\nThis 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$.\n(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.)\n\nThe paper actually offers a family of algorithms with a tune-able running-time parameter, giving running times which interpolate from polynomial to exponential time.\nAt the exponential-time end of the scale, the algorithm becomes information-theoretically optimal, capturing the natural brute-force search procedure for recovering $x$.\nAs the running time increases, the signal-strength $\\lambda$ needed by the algorithm naturally decreases: this gives a nice \"information-computation tradeoff\".\n\nTune-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.\n(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.)\n\n(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.\n\nHowever, 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$*.\nI don't view this as a significant failing of the paper: rather, it highlights the following interesting issue.\nThe 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$.\nThis same approach appears not to yield a tight lower bound for sparse tensor PCA, which leaves open the intriguing possibility of improved algorithms.\n\nOverall, this paper mainly seems to adapt existing algorithmic and lower bound techniques to the sparse tensor PCA problem.\nBut 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.\nIt also highlights an interesting gap between the algorithms and lower bound which seem to be accessible with known techniques.\nI therefore recommend acceptance.\n\n(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.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are considered carefully. This is a theory paper with no imminent direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "63oTfHcCj8_", "reviewer": "Reviewer_xHQE", "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. \n\nNecessary 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.\n\nWhile similar results have been obtained in the literature, the authors argue that their results improve upon the existing ones in a number of ways. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nOne 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). \n\nRelated 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.\n\nFinally, 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.\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is theoretical and so I think the discussion is appropriate. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "3owgrU7jFmb", "reviewer": "Reviewer_BF19", "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$. \n\nThe results of this paper recover several results of the literature, and provide a non-trivial extension. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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:\n\ni) 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).\n\nii) 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.\n\niii) Use the second copy of the tensor and the maximizer from (ii) to estimate the support of the signal. \n\nThe 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). \n\nThe 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].\n\nThese 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.\n\nAlthough I am rather positive about this submission, I have the following concerns:\n\n1) 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.\n\n2) 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?\n\n3) 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]).\n\n4) 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). \n\n5) The statement of Theorem 2 is missing some words/lines (see line 142).\n\n6) Appendix, lines 654-655. How do you get this formula? Please discuss or refer to the corresponding equations in Appendix F. \n\n7) Appendix, formulas on top of page 30. How is $\\tilde{x}$ defined? I could not follow here.\n\n\n------\n\n*Post-rebuttal update.* The authors addressed my concerns in a satisfactory way, and I have raised my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not foresee potential negative societal impact for this contribution.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "02smXZi30ef", "reviewer": "Reviewer_n5Ja", "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.\n\nThe 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.\nThis generalizes to the 'tensor settings' previous results obtained about sparse PCA.\n\nThe 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.\n\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThe 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.\n\nThe 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:\na) there could a priori exists polynomial time algorithms that works even when low-degree polynomial don't.\nb) support estimation may be strictly harder than testing.\nFor these reasons I do not feel a strong connection between the two main results of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "-aOEf_McYoD", "reviewer": "Reviewer_rbms", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThe 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. \n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)