Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the subspace power method (SPM) for symmetric tensors.
Specifically, this paper analyzes the non-convex optimization landscape associated with the SPM objective.
The main results are two theorems, theorem 6 and theorem 15. Under some assumptions, it is shown in theorem 6  that for low rank case, nSPM-P has 2K local maximizers which are good approximations of all components. For the overcomplete tensors, similar conclusion is given. Numerical experiments is presented to validate the theoretical findings.
main_review: 
Major concern:
(1) Theorem 6, the requirement (10) is too restrictive.
When n is relatively large,  (10) implies that rho_2 is tiny, as a result, all components  a_i's are almost orthogonal.
To be more specific,  let us relax the requirement (10) a little bit, say rho_2 <= 1 / (8n^2).
Set  K=2 (only two components a_1 and a_2), assume the angle between a_1 and a_2 is pi/3, 
then it is easy to see that rho_2 = 2 * (cos pi/6)^2  - 1 = 0.5. 
However, 0.5 > 1 / (8n^2) for all n>= 2.
When all components  a_i's are almost orthogonal, it is not surprising to draw the conclusion of Theorem 6.
I would like to raise my score if the authors are able to convince me that the requirement (10) is not restrictive.

(2) Theorem 15 is established under the assumption A3, which is only shown for n=2. The authors formulate the result as conjecture 14.
It is OK to make a such conjecture, but the readers may not buy it, especially c_2 is independent of K and D. It is better to provide the evidence (even numerical evidence) in the main text of this paper.

More comments

(1) The notation for || ||, || ||_F is unclear. In the notation, || || is declared to be the F-norm, but || ||_F still appears in the subsequent discussion. This leads to some confusing in Lemma 1, see details in (2).

(2) Lemma 1, eqn (3).  If F norm is used, \Delta_T in the denominator should be replaced by ||M - \hat M||_2.
If 2-norm is used,  \Delta_T in both numerator and denominator should be replaced by ||M - \hat M||_2.
The inequality between Lines 38 and 39 in the supplementary, the term pi/2 can be removed. 
Therefore, the bound in Lemma 1 can be improved.

(3) Lines 125 and 126, it is not appropriate to cite [9] here. This deflation procedure is closely related to the spectral theory of symmetric tensors, see the following paper for example. 
L. Qi, “The best rank-one approximation ratio of a tensor space”,SIAM Journalon Matrix Analysis and Applications, 32 (2011) 430-432.
Furthermore, it is unclear that such a procedure is able to find all components.

(4) Line 241, remark 18, is it possible to show that \tilde{a}_{\ell +1} falls into the a neibourhood of the true component, nSPM-P is able to recover?

(5) To make the numerical experiments more convincing, try larger n, rather than simply set m=4 (n=2).

I am satisfied with the authors' replies, and raised the score. 

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: In this paper, the authors consider the optimization formulation for symmetric tensor decomposition introduced in the Subspace Power Method (SPM). They analyze the non-convex optimization landscape associated with the SPM objective. The analysis focuses on the noisy tensors, and implies SPM with suitable initialization is a provable, efficient, robust algorithm for low-rank symmetric tensor decomposition. Numerical results coincide with the theoretical analysis.

The contributions is to analyze the landscape of SPM-P by characterizing all second-order critical points.
main_review: Nowadays, high-dimensional data sets are considered as higher-order arrays. That is, tensor. Finding the CP decomposition of given tensor is very important. The authors consider the symmetric tensor decomposition introduced in Subspace Power Method.
limitations_and_societal_impact: Yes. The authors give some "near-global" guarantee under a random tensor model and the deterministic frame conditions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes a different optimization problem for the task of finding one scaler/vector pair.
main_review: I am not familiar with this kind of work. I have one question concerns the deflation procedure. 

So far the paper considers finding one scaler/vector pair and guarantees are for the second-order stationary points. After finding one scaler/vector pair, due to the error in the pair found, simple deflation procedures, finding one pair each time and deflating the tensor by subtracting the rank 1 tensors found so far, will accumulate errors. Are there any guarantees for this deflation procedure? In remark 18, the author suggests a procedure in doing the deflation. Can the author say something about the technical difficulty in proving the correctness of the procedure proposed in Remark 18?

limitations_and_societal_impact: Limitations are not discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the non-convex landscape of the SPM-P optimization objective (in page 2) for tensor decomposition. Under both deterministic and random models of the components, the work shows that all second-order critical points coincide with the ground truth vectors (up to a sign difference) with different levels of overcompleteness. The result can also be generalized to the noisy cases under certain assumptions.

main_review: The work studies the nonconvex landscape of the symmetric tensor decomposition problem under the overcomplete setting. Overall this is a well-written and well-presented paper, the geometrical landscape analysis on the landscape provides new insight to tensor decomposition problems.

* Pros: 
This paper experimentally demonstrates that there are no spurious local maximizers of the SPM-P objective (in Figure 1) and corroborates their experiments with extensive theoretical results (Theorem 6 for the deterministic case and Theorem 15 for the noisy case).

* Questions: The result for the random model critically depends on a conjecture (Conjecture 14). Also, the landscape analysis is shown in super level set which a random initialization cannot be achieved. Can the author compare the size of the super level set with that in [18] and discuss it? On the other hand, are all other saddle points to be strict saddle points?

In Theorem 6, it seems that the assumption requires \rho_2 and \rho_n to be at the scale of O(1/n^2), does this happen in general? Or what other assumptions do we require for a_1,a_2,\dots,a_K so that \rho_2 and \rho_n satisfy the assumption in (eq. 10)? Perhaps the authors could either provide some theoretical justifications of empirical evidence?

* Relation to Literature. There are several recent related results that are missing in reference, and it would better to be discussed:

``Maziar Sanjabi, Sina Baharlouei, Meisam Razaviyayn, Jason D. Lee When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?''
``Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang, Zhihui Zhu Geometric Analysis of Nonconvex Optimization Landscapes for Overcomplete Learning''
In particular, the latter work considered the fourth-order overcomplete tensor decomposition problem under tight frame and incoherent assumptions, with application to overcomplete dictionary learning. The work showed a global landscape when overcompleteness is a constant, but with a different PM loss function. 

limitations_and_societal_impact: Described in the question part in the main review.
review_title: null

Meta-review: The paper studies the symmetric tensor decomposition problem, in which we are given a (noisy) superposition of outer products, and the goal is to recover these generating components. The paper analyzes the “subspace power method”, which seeks local maximizers of the norm of the projection of a component onto the span of a certain reshaping of the input tensor. For orthogonal tensors, this coincides with the standard power method; for general tensors with correlated components, the subspace power method has advantages: global maximizers are known to coincide with the generating components. In contrast, previous work does not prove that the problem lacks local maximizers, and as a consequence, does not establish algorithmic recovery guarantees. 

 The contribution of this work is a landscape analysis of the SPM, which proves that under certain deterministic incoherence conditions, there are no suboptimal maximizers in a certain super level set of the objective function. For low rank incoherent tensors (r = O(D)), this establishes that local maximizers are global. For random tensors with rank approaching the conjectured barrier O(D^{m/2}) for efficient methods, this result rules out suboptimal maximizers with large objective function (nonvanishing objective function in certain scalings of the problem parameters). The latter result can be compared to analyses of Ge and Ma for the traditional power method. 

Initial reviews were generally positive, acknowledging the theoretical contributions of the work, while also raising questions about (i) the strength of the paper’s incoherence conditions, and (ii) the semi-global nature of the paper’s results for random overcomplete tensors. The reviewers found the authors’ response on these points generally satisfying; the final consensus is to accept the paper. The AC concurs — the paper contributes a novel analysis of a method that seems to have practical advantages in handling correlated tensors. While there are many remaining issues (global results for highly over complete tensors?), the paper makes a contribution to the literature in this area. 
Decision: Accept (Poster)