Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
 
The paper provides an interesting algorithm for tensor PCA, which is based on trace invariants. The problem consists of recovering a (single-spike/multiple orthogonal spikes) tensor corrupted by a Gaussian noise tensor. The authors proposed a new algorithm which allows recovering a signal for a sufficiently small signal to noise ratio. 

##########################################################################
Reasons for score: 
 
Overall, I vote for accepting. I like the idea, and the proofs seem to be coherent and correct. The problem has clear importance for the theoretical/statistical physics community; however, I am not convinced of the importance of the problem considered here for the ICLR community and appreciate the author’s comments on this. I also have a few minor concerns, which, hopefully, can be addressed by the authors in the rebuttal period. 
 
##########################################################################

Pros: 
1. The paper takes an interesting question about tensor PCA and proposes a promising approach to solve it based on the trace invariants. For me, the problem is encouraging, while I would appreciate a discussion about possible machine learning/AI applications (learning latent variable models? anything else?)
 
2. The mathematical justification of the statements seems to be correct for me and ok to follow.  

3. It is claimed in the paper that the algorithm improves the state-of-the-art (signal to noise ratio requirements) in several cases, while a brief survey/table of the recent results is missing.  Unfortunately, I am not working in this area and probably not familiar with recent results
 
##########################################################################
Cons: 
 
1. Applications for ML/AI/Language processing are not very clear for me, and I would appreciate a discussion on this in the paper. 

2. Empirical justification. I would highly appreciate having more experiments on real data (if any) and a detailed comparison of the methods in terms of accuracy/memory/time. 

review_title: A review of the paper "A new framework for tensor PCA based on trace invariants"

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper presents a pair of interesting algorithms using trace invariants to detect the signal in the signal-plus-noise tensor PCA framework.  The algorithms function by considering cutting an edge in the graph representation of the trace invariant, yielding a matrix whose leading eigenvector provides a (up to a rotation) estimate of the signal vector $v$.  This algorithm appears to be very interesting and works well in a series of simulations. 

Unfortunately, the presentation of the paper makes it very difficult to assess the importance of the contribution.  The introduction is well-written and well-motivated, though the later segmentation of the paper into many small subsections without much exposition makes the flow of the paper and its results hard to follow.  In addition, the notation and terminology in the paper are imprecise and, with important terminology and symbology introduced without definition or background citation.

Pros:
- The proposed algorithm is clever and appears to do well compared to existing approaches in experiments.

- Well written introduction (with the only complaint being some minor grammatical errors).



Cons:
- Important notation is introduced, and is not defined; Equation 4 is an example of this, where $\langle \cdot \rangle$ (I assume this means $\mathbb{E}$?), $\bar{\mathbf{T}}$, and $\mathcal{E}^0(\mathcal{G})$ are all undefined.  This occurs often in the paper and in the appendix.

- In the $\bullet, \times, \bullet$ decomposition at the start of Section 2.3, what is $\sqrt{N}$?

- What is the variance of a graph (as in Theorem 4)?  The proof sketch of this theorem is very hard to follow.

- Algorithm 1 is imprecise; what does "compare $\alpha$ to $\sigma(I^{(N)}(T))$ mean?  If $\alpha>\sigma(I^{(N)}(T))$ then a spike is detected?  How do you compute the variance of $I^{(N)}(T)$?  How would you compute this if the noise model did not have unit variance)?  

- Both algorithms are only presented for 3-way tensors, but the Theoretical claims are for higher order tensors?

- The proofs of the theorems and the statement of the theorems are, in general, a bit imprecise.  For example, in the proof of Theorem 2, Chebyshev's inequality will not guarantee disjointness everywhere, but only with high probability.  This is the case if $\beta_{det}$ is finite.  This is a finite $\beta_{det}$ result, with a claim only holding in the limit.

- In Theorem 5, what are the intermediate graphs/matrices?  In addition, this section (and Appendix C discussing perfect one-factorization) are a bit opaque.

- Is the decomposition after equation 5 only for the melon graph?  For more complex graphs (i.e., the tetrahedral), I believe you will have additional trace-like coefficients on all terms.  In any event, I am confused about the summands.  I do not see why the all $Z$ sum would have a $\beta$, while the cross-terms would not.  Furthermore, why would the all $v$ sum not have a $\beta^d$ coefficient?  This is what is implicitly being used in the proofs?

- In the experiments, important details are left out.  What is the setup here: what are the $v$'s, how many iterations of tensor power method are applied, how many MC replicates are run to produce the error bars, what is the y-axis, what are the runtimes here, what is Random in Figure 6?  More detail would help a lot to understand how your new approach compares (it appears well) with the current literature.



review_title: Review of "A new framework for tensor PCA based on trace invariants"

final_score: rating: 3: Clear rejection
review_content: Summary:

This paper studies the detection and recovery problem in spiked tensor models in the form T = \beta v0^\otimes k + Z, where v0 is the underlying spike signal and Z is a Gaussian noise.  The authors claim that they propose a new framework to solve the problem, by looking at the trace invariants of tensors. The authors provide a detection algorithm (Algorithm 1) and a recovery algorithm (Algorithm 2), as well as the corresponding phases. The authors claim that: 1) they "build tractable algorithms with polynomial complexity", "a detection algorithm linear in time"; 2) the algorithms are very suitable for parallel architectures; 3) an improvement of the state of the art for the symmetric tensor PCA experimentally. The authors furthermore discuss the asymmetric case and the multiple spike case.


Recommendation:

At the current stage I vote for rejection. I am not able to follow the proofs in this paper due to missing definitions of terms and notations. Also some claims are not proved. See below for details.


Pros:

- The methods used in the paper seem new for spiked tensor models.

- Some experimental results are provided. 


Cons: 

- The readability of this paper severely suffers from its writing. At the current stage, filled with undefined or inconsistent notations and terms, this paper is not self-contained and hard to follow. This becomes worse considering the fact that this paper studies tensor problems -- many tensor-related terms have multiple definitions (e.g., eigenvalues, ranks). It will be very hard to follow the proofs if the definitions are unclear. Here is an incomprehensive list:
	- Middle of Page 3: what is the *formal* definition of contracting (instead of saying "equivalent to a matrix multiplication")? Also, trace invariants are never formally defined in this paper.
	- eq.(2),(3): what is O(n) here? Also, what does the bold O refer to? Right before eq.(4) the authors use another notation \mathcal{O}(n). Is this the same as the first O(n)? In the abstract the authors use \mathcal{O}(1) to refer to the constant order. Why the inconsistency?
	- End of Page 3: how is \mathcal{G} related to trace invariants formally?
	- Section 2.2: this is not clear. What are the matrices here? What is the definition of M_{G,e}?
	- Section 2.3: what is the definition of I_G(T)?
	- Theorem 3: what is the Loss function here?
	- Top of Page 5: what is the exact definition of "dominating" here?

- It should be noted that, without clear definitions of I_G(T) and M_{G,e}(T), there is no way to verify Algorithm 1 and 2.

- The authors claim "polynomial complexity" at the beginning of the paper, but it is never proved. Theorem 7 claims that Algorithm 1 and 2 run in linear time. I cannot find that in the proof.   

- It is unclear why the algorithms "are very suitable for parallel architectures", as the authors have claimed. Have the authors tried running the experiments in parallel?

- Theorem 4, 5, 9, 10 do not have complete proofs. 


Minor comments:

- Page 2 Notations: typeface of v is not consistent. 

- Page 8: "eg" should be "e.g."



review_title: Review

Meta-review: This paper studies the tensor principal component analysis problem, where we observe a tensor T = \beta v^{\otimes k} + Z where v is a spike and Z is a Gaussian noise tensor. The goal is to recover an accurate estimate to the spike for as small a signal-to-noise ratio \beta as possible. There has been considerable interest in this problem, mainly coming from the statistics and theoretical computer science communities, and the best known algorithms succeed when \beta \geq n^{k/4} where n is the dimension of v. The main contribution of this paper is to leverage ideas from theoretical physics and build a matrix whose top eigenvector is correlated with v for sufficiently large \beta using trace invariants. On synthetic data, the algorithms achieve better performance than existing methods.

The main negative of this paper is that it is not so clear how tensor PCA is relevant in machine learning applications. The authors gave some references to applications of tensor methods, but I want to point out that all of those works are about using tensor decompositions, which despite the fact that they are both about tensors, are rather different sorts of tools. Many of the reviewers also found the paper difficult to follow. I do think exposition is particularly challenging when making connections between different communities, as this work needs to introduce several notions from theoretical physics. I am also not sure how novel the methods are, since a somewhat recent paper Moitra and Wein, "Spectral Methods from Tensor Networks", STOC 2019 also uses tensor networks to build large matrices whose top eigenvalue is correlated with a planted signal, albeit for a different problem called orbit retrieval. 
Decision: Reject