Landscape analysis of an improved power method for tensor decomposition
Authors: Joe Kileel
Timo Klock
João M. Pereira
Venue: NeurIPS 2021 Poster (2021)
Keywords: tensors
power method
non-convexity
optimization
robustness
CP decomposition

Abstract: In this work, we consider the optimization formulation for symmetric tensor decomposition recently introduced in the Subspace Power Method (SPM) of Kileel and Pereira.  Unlike popular alternative functionals for tensor decomposition, the SPM objective function has the desirable properties that its maximal value is known in advance, and its global optima are exactly the rank-1 components of the tensor when the input is sufficiently low-rank.  We analyze the non-convex optimization landscape associated with the SPM objective.  Our analysis accounts for working with noisy tensors.  We derive quantitative bounds such that any second-order critical point with SPM objective value exceeding the bound must equal a tensor component in the noiseless case, and must approximate a tensor component in the noisy case. For decomposing tensors of size $D^{\times m}$, we obtain a near-global guarantee up to rank $\widetilde{o}(D^{\lfloor m/2 \rfloor})$ under a random tensor model, and a global guarantee up to rank $\mathcal{O}(D)$ assuming deterministic frame conditions.  This implies that SPM with suitable initialization is a provable, efficient, robust algorithm for low-rank symmetric tensor decomposition.  We conclude with numerics that show a practical preferability for using the SPM functional over a more established counterpart.

Landscape analysis of an improved power method for tensor decomposition
Joe Kileel UT Austin
Timo Klock
João M. Pereira UT Austin
Simula Research Laboratory
Abstract
this work, we consider the optimization formulation for symmetric tensor de- composition recently introduced in the Subspace Power Method (SPM) of Kileel and Pereira. Unlike popular alternative functionals for tensor decomposition, the SPM objective function has the desirable properties that its maximal value is known in advance, and its global optima are exactly the rank-1 components of the tensor when the input is sufficiently low-rank. We analyze the non-convex optimization landscape associated with the SPM objective. Our analysis accounts for working with noisy tensors. We derive quantitative bounds such that any second-order critical point with SPM objective value exceeding the bound must equal tensor component in the noiseless case, and must approximate tensor component in the noisy case. For decomposing tensors of size D we obtain near-global guar- antee up to rank ö (mm//) ) under a random tensor model, and a global guarantee up rank O(D) assuming deterministic frame conditions. This implies that SPM with suitable initialization is a provable, efficient, robust algorithm for low-rank symmetric tensor decomposition. We conclude with numerics that show practical preferability for using the SPM functional over a more established counterpart.
mm/2)
Introduction
From applied and computational mathematics [27] to machine learning [36] and multivariate statistics
29 many-body quantum systems [41], high-dimensional data arise that naturally organized
into higher-order arrays. Frequently these arrays, known as hypermatrices or tensors, are decomposed
into low-rank representations. In particular, the real symmetric CANDECOMPIPARATAC (CP)
decomposition
[3] is often appropriate:
Σ
Aa 6m
(I)
Here, we are given T, a real symmetric tensor size Dxm The goal to expand T sum of K rank-1 terms, coming from scalar/vector pairs (Ai, a;) E R x R.. Importantly, the number of terms K must be minimal possible for the given tensor, in which case K called the rank of the input T.
When m > 2 and K = O(Dm), CP decompositions are generically unique (up to permutation and scaling) by fundamental results in algebraic geometry [10]. An actionable interpretation 3 is that CP decomposition infers well-defined latent variables [(A,, a:) i E [K] encoded by T. Indeed in learning applications, where symmetric tensors are formed from statistical moments (higher-order covariances) or multivariate derivatives (higher-order Hessians), CP dccomposition has enabled
parameter estimation for mixtures of Gaussians 20
generalized linear models (34] shallow
neural networks 19
24 42
deeper networks 17
18
30
hidden Markov models [5], among others.
Unfortunately, CP decomposition is NP-hard in the worst
(23 In fact, it is believed to possess computationallto-sttiiii st-tttiitiillll gap 77 with efficient algorithms expected to exist for random tensors
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

PM objective
SPM objective
00
60
0.5
00
27
F7
2
7
Figure 1: Illustration of PM-P objective (left) and SPM-P objective (right) for D K
2 and 4, where S! is mapped to (-x, .T. We set d1 (1, a2 (cos fu sin 8o) for different values of 8g. If a₁ and 0g are not orthogonal (0g * )) then a₁ and a2 do not coincide with global or local maximizers of PM-P Too much correlation (Op 3 leads collapsing of the two distinet maxima into one isolated maximum for PM-P On the other hand. SPPM-P is not affected in this way by correlation: local maxima coincide with global maxima which the tensor components 01 42-
only up to rank = O(D/2)) For this reason, and due its non-convexity and sigh-dimensionnlltyy CP decomposition has served theoretically as key testing ground for better understanding mysteries of non-convex optimization landscapes. To date, this focus has been on the non-convex program
max
(T, x 2m))
(PM-P)
DER PERP:IIZ 1|
We label the problem PM-P
standing for Power Method Program, because projected gradient ascent applied to PM-P corresponds to the Shifted Symmetric Higher-Order Power Method of Kolda and Mayo 28 Important analyses of PMPP include Ge and Ma's 21 and the earlier 4 on overcomplete tensors, as well as (33 for low-rank tensors, and [3 which studied PM-P assuming the tensor components form unit-norm tight frame with low incoherence.
In this paper, we perform an analysis of the non-convex optimization landscape associated with the Subspace Power Method (SPM) for computing symmetric tensor decompositions. The first and third authors introduced SPM in 25). This method is based on the following non-convex program:
max ZERD: Ja
Fa(z),
(PMMP))
2
where Fa(xr) == ||(())==|PP<<>> (P n n: [m/2]. A = Span @n
and PA: : (RD) + A is orthogonal projection with respect to Frobenius inner product.
Note that SPM-P is particular polynomial optimization problem of degree 2n on the unit sphere.
There are at least two motivating reasons to study the optimization landscape of SPM-P Firstly, was observed in numerical experiments in 25 that the SPM algorithm is competitive within its applicable rank range of K O(D (Lm/)))) gave a roughly one-order of magnitude speed-up over the decomposition methods in (26 as implemented in Tensorlab [40]. while matching the numerical stability of FOOBI [14. Thus SPM is practical algorithm. Secondly, from a theory standpoint, the program SPM-P has certain desirable properties which (hiichPM-P]Jacke Specifically for an input tensor
T T= -E
dea@ with rank K S D Dlm/2] and Zariski-generid {(Ai, ) SPM-P is such that:
Each component La, is exactly a global maximum, and there are no other global maxima.
The globally maximal value is known in advance to be exactly 1. So the objective value gives a certificate for global optimality, and non-global critical points can be discarded.
These properties were shown for SPM-P in (25] but both fail for PM-P (see Figure D. Thus, SPM-P is more relevant theoretically than PM-P as a test problem for non-convex CP decomposition.
Prior theory. In 25 it is proven that projected gradient ascent applied to SPM-P initialized at almost all starting points with a constant explicitly- step size, must converge to a second-
order critical point of SPMMP at a power rate or faster. However this left open the possible existence
Zariski-generic means that the failure set can be described by the vanishing non-zero polynomials [22] so in particular, has Lebesgue measure 0.

---

of spurions second-order critical points, i.c., second-order points with reasonably high objective value that are not global maxima (unequal to, and possibly distant from, each CP component =a;). Such critical points could pose trouble for the successful optimization of [SPM-P Furthermore all theory for SPM-P in [25] was restricted the clean case: that is, when the input tensor exactly of a sufficiently low rank K. The analysis for PM-P in [2] 31 [3 also assume noiseless inputs. However, tensors arising in practice are invariably noisy due, e.g., to sampling or measurement errors.
Main contributions. We perform a landscape analysis of SSPMPPPp by characterizing all second-order critical points, using suitable assumptions on a1...... ag. Under deterministic frame conditions on a1.... ag. which are satisfied by mutually incoherent vectors, near- -otuooorttoomall systems, and random ensembles of size K O(D), Theorem 7 shows that all second-orde critical points of SPM-P coincide exactly with +4 Theorem 16 shows the same result for overcomplete random ensembles of size K = ō DIm/21), ). however requiring an additional superlevel set condition to exclude maximizers with vanishing objective values. Both results extend noisy tensor decomposition, where SPM is applied to a perturbation T = T. In this setting, second-order critical points with objective values exceeding (1 r) are O( - r))err to one of the components +-a We also show in Lemma 9 that spurious local maximizers (with lower objective values) do exist in the noisy case.
The results imply a clear separation of the functional landscape between near-global maximizers, with objective values close to I, and spurious local maximizers with small objective value. Hence, the SPM objective can be used to validate a final iterate of projected gradient ascent in the noisy case. In Theorem [8] we combine our landscape analysis with bounds on eπror propagation incurred during SPM's deflation steps. This gives guarantees for end-to- end tensor decomposition using SPM.
Lastly, we expose the relation between PM-P and SPM-PP Specifically, SPM-P can be expressed as PM-P with the appropriate insertion of the inverse of the Grammian (Gn)i == (a,, ay) ) The resulting de-biasing effect on the local maximizers with respect to the components =a (cf. Figure responsible for many advantages S-PMP) Along the way, we state conjecture about the minimal eigenvalue of Gn when o; are i.i.d. uniform on the sphere, which may be of independent interest.
2 Notation
Vectors and matrices. When x is a vector, ||æ||| is the fy-norm (p E (Ro)U(o))) For x, E RD, the entrywise (or Hadamard) product is zOy E "R,,, and the entrywise power is x := v E R (s E N). When M is a matrix, |/ is the spectral norm. If M real symmetric, M (M) is the eigenvalue of M that the j-th largest absolute value. We denote the identity by ldp DDD.
Tensors. A real tensor of length D and order m is an array of size D x Dx... x D (m times) of real numbers. Write Th" == D)) @m = " for the space of tensors of size D Meanwhile, Sym(TB)) C TB" is the subspace of symmetric tensors (i.e., tensors unchanged by any permutation of indices). The Frobenius inner product and norm are denoted by (: and |1 respectively. Given any linear subspace of tensors A C TB, let PA TB + A denote the orthogonal pro- jector onto A with respect to (: In the case A = Sym(TT)) ) the projector PSym(TT)) is the symmetrization operator, Sym TT + Sym (Tg) ). Given T E TT and S E Th the tensor (or outer) product is T @ S E TT defined by (T @ S) "......mm = T., Ti......mm, Stm, S1m,--....mm For T E Th and E N, the tensor power is 8 ;= T & ... @ T THT For T To S T with m2 2 m2, the contraction T S E Thu--a is defined by (T -S) -m Ei,...ii Ti maa -m imm.. Smm Let Reshape(T, (di....,d)) be the function that re- shapes the tensor T to have dimensions di,.. deg...,,,, de, as in corresponding Matlab/NumPy commands.
Other. The unit sphere in RDD is SD-1 and Uni is the associated uniform probability distribution. Given a function f RD- + R. the Euclidean gradient and Hessian matrix at x E R are fz)) E RD and V f(x) E Sym SD-1 at x E SD-1 are Vg--1 f(x) and V2 ffx) (see D.. Write Span for linear span, [K] := {1. ..... K}. and |A| for the cardinality of finite set A. Lastly, use asymptotic notation freely.
The Riemannian gradient and Hessian with respect to
3

---

3 Symmetric tensor decomposition via Subspace Power Method
In this section, we outline the tensor decomposition method SPM of (25), and provide basic insights on the program SPM-P Throughout we assume that m 2 2 is an integer and define n == [m/2]] /
SPM algorithm. The input is a tensor I E Sym(TD), ) with the promise that I ~ T= - X @m
for {(A, a:)) Zariski-generic and K I (D-n-l) -D (if m is even) and K - D (if m is odd). As first step, SPM obtains the orthogonal projector PA "BB" + A that projects onto the column span of Reshape(T, ()) by using matrix singular value decomposition. Provided that T Re T, the associated subspace approximation error A ~ A span(a 8n ..... aK
Sn) defined by
A = || PA
PAlF==F= TETB. 11T1,
sup
[| PA
can be bounded as follows. (Note that by 99 Lem. 2.3]. we know A S 1 a priori.)
Lemma 1 (Error in subspace). Let m 2 3. n 7. T E Sym(TT") and assume that M :=
Reshape(T, !D", Dm= has exactly K nonzero singular values 01 (M) 2 ... 2 [x(MM) > 0. Let
T E (ym(TT)) M == Reshape(T, [D", D Dm- Assume AM I| Mlla < (M)) Then
|Pim(M)) - P (mk 12 σx (x - AM
AM
where Im(M) S. T" denotes the image of M and Img (M) S RD" denotes the subspace spanned by the K leading left singular vectors of M. In particular, if T = =E 2
A = =a @n E [K]], dim(AA = K, and À is the subspace spanned by K leading tensorized left singular vectors of M, the right-hand side of (3 upper-bounds A
Remark 2. If Σi= Xza," one coefficient X; is small and the vectors {a, i E [K]] are not too correlated, then the flattened tensor Reshape(T, [D", Dm="l) has small eigenvalue. This makes estimating the corresponding eigenvector sensitive to noise. See Remark S.41 in the appendix.
Given A, SPM seeks one tensor component ag by solving the noisy variant of dPM-nddefined by
max EĄ(T), where Fz(z)= = (
(nSPM-P)
--
Starting from a random initial point zo ~ D )) the projected gradient ascent iteration
I T (I 8n) x S(n-1)
(4)
x + + A (I (n) (m(n11)1
with a constant step-size 7, is guaranteed to converge to second-order critical point of DSPM-PPPPP almost surely by (25). Here we require that the step-size y is less than an explicit upper bound given in (25). Denoting by â the final iterate obtained by SPM. accept the candidate approximate tensor component à; if F A (ā.) ) is large enough; otherwise we draw a new starting point 2g and re-run (4).
Next given à,, SPM evaluates a deflation formula based on Wedderburn rank reduction [12 from matrix algebra to compute the corresponding weight Å. Then, we update the tensor T + Ā Kragm..
To finish the tensor decomposition, SPM performs the projected gradient ascent and deflation steps K times to compute all of the tensor components and weights {(A,, k;))
Preparatory material about ISPMMPP The goal of this paper is show that second-order critical points of ISPMMP with reasonable function value must be near the global maximizers t..,..., +ak SPM- under suitable incoherence assumptions on the rank-one components a1,...,aK. a.. Natu- rally, the optimality conditions for (nSPMPPpppaa an important part in this analysis.
Proposition (Optimality conditions). Let E SD be first and second-orde critical for SPM-P Then for each z E SD-1 with 2 1 I, we have
Pa(x") 2- = (x)a,
(5)
Fx(x) 2
M) + (n - (x)) 222))
(6)
Furthermore, for any y E SD-1 we have
F Fx(x) 2 n (2((x~11)) + (n ((((("")) 2(n 1)F (() v/
(7)
4

---

In the analysis later, we make frequent use of expressing the objective (z( using the Gram matrix
G Sym((T) defined by (Gn)ij (a. " agn)) (ai, az)"
Under linear independence of the tensors o ..... K later, the inverse G exists and the noiseless program SPM-P can be expressed as follows.
@n which is implied by our assumptions made
Lemma 4. Let A == [a1 ... [x] E D and {a.T [K]] be linearly independent. We have
FA(x) = || PA(x = ((A x)) )))")" G ((ATx)))))
Lemma 4 exposes the relation between
SPM-P
and PM-P While PM-P can be rewritten (Tm) SPM-P takes into account correlations among the tensors
{(AA Jon (A 2));; if m is even, ai 6n 8n and inserts the Grammian Ge into Consequently, correlations among the tensor ..... K
components are considered in SPM-P without any priori knowledge of the tensors af ,..., ".. @n
In the special case of orthonormal systems, more generally systems that resemble equiangular tight frames 16. 37]. the (PM-- and objjectves coincide up to shift and scaling.
Lemma 5. Assume there exist E (-1,1) ( and M E IR such that (ai, ay) = for all i i and EveRy az)" M for all SP-- Denote A = =[aal.... lallaal E DxK K Then
FA(x) = p)- 114 2n ((1 +)2+kpp p)) p))- PM²
(10)
4
Main results
In this section, we present the main results about local maximizers of the nSPM-P program. Section 4.1 is tailored low-rank tensor models with K O(D) components that satisty certain determinis- tie frame conditions. Section 4.2 then considers the overcomplete case K ō (Lm/2)) in an average case scenario, where .1,..... OKK are modeled as independent copies of an isotropic random vector.
4.1 Low-rank tensors under deterministic frame conditions
Motivated by frame constants in frame theory I1 we measure the incoherence of the ensemble a1.-.., ak k by scalars Ps R2o. which are defined via
K
Ps = sup RESD
(x, a:)1" 1.
(11)
They satisfy the order relation Ps S p.' for s' S 8, due to ||a: 1, and can be related to extremal eigenvalues of Grammians G, and GLa/2] as shown in the following result.
Lemma 6. Let {a= E [K]] C CD-1 and (Ga)ij
az)" for N. Then
1 P. S M (G.) S (G.) S P S p4 (G
(12)
The characterization in Lemma T allows to compute bounds for As for low-rank tensors with mutually incoherent components or rank-O(D) D) tensor with random components. We provide details on this in Remark 8 below, but first state the main guarantee about local maximizers using P2 and Pr.
Theorem (Main deterministic result). Let {a; i [K]] C SD-1 and A = Span (af i E [K]]-
Let À C Sym(TB) be perturbation of A with A IP PAIIF F Let
1
2T
12 p2
(n² n)Pn and Do 2 4T + 3n
(13)
Then, if AAA < Dgr the program 1SPM-P has exactly 2K second-order critical points in the superlevel set where
2 27 3n²
F Fx(x) 2
2T A
(14)
5

---

Each of these critical points is strict local maximizer for F.. Further for each such point x", there exists unique E [K] and s {-1,1} such that
| - sa,112 2
(15)
In the noiseless case (A - 0), if 2 O then there are precisely 2K second-order critical points of SPM-P with positive finctionaa value, and they the global maxinizers so, (i E [K], [-1,1]}
Remark 8. Using Lemma we identify two situations where P2 and Pn can be bounded from above.
1. Mutually incoherent ensembles. Let d1....,aK ag have mutual incoherence p max (a,, a-)l, Using Gershgorin's circle theorem, we obtain (F)
Ps S MI (s/22))
Kai, ((),,)))) s (K 1)ple/21 for any Ng2, Ve K
max
Σ jzi
which implies that the conditions of Theorem are saisfied if Kp is sufficiently small. This setting is comparable to the analysis for PM-P in [33). Moreover, if K = D and a1...., 4K are mutually orthogonal, then P. 0 for each 2. Therefore Theorem holds with T = 1/6 for orthogonally decomposable tensors [6]
2. Low-rank random ensembles. Let ,x be independent copies of an isotropic unit-
norm random vector a with sub-Gaus Gaussian norm (L1/v (c.g., ~ Unif(s With high probability, the ensemble can achieve arbitrarily small p2, provided that K < CD for sufficiently small constant C > 0. The proof of this fact relies on A = [a1|... [ax] satisfying, with high probability, the so-called (K, restricted isometry property [38 Thm. 5.65] as defined in Definition T0 in the next section. We note that despite requiring
conditions milder than those in the unit-norm tight frame analysis for PM-P in [31. we
achieve comparable scaling of K = O(D).
In the noiseless case where A사 0, Theorem 7 shows that all local maximizers coincide with global maximizers =a..... =a provided the tensor components are sufficiently incoherent to ensure T 2 In the noisy case, all local maximizers with objective values (x()) 2 C(n, A) are A-AAoos to the global optimizers of the noiseless objective FA, where the constant C(n, increases as the incoherence of the vectors a1,..., ak shrinks. Unfortunately, the presence of spurious local maximizers of F'A with small objective values cannot be avoided under deterministic noise model, as the next result shows.
1). a E SD-1 and A spanfa Sn). Then there exists a subspace Á S Sym with dim = 1 and || PA =F such that MaPnSP possesses strict local maximizer of objective value exactly 8².
Lemma 9.
Let
4.2
Average case analysis of overcomplete tensors
The overcomplete case with K = o(Dlm/2)) falls outside the range of Theorem 7 because - in
13
becomes negative when K >> D. Instead, our analysis for the overcomplete case relies on A |ax] E PxX obeying the (p, -ertttidd isometry property (RIP) for O(D/ log ()).
Definition 10. Let A E DxX S p S K be an integer, and E (0, We say that A (p. RIPP
every x p submatrix Ap of A satisfies ||-4, Ap Id < 8.
A consequence of the RIP, which is particularly useful in the analysis of overcomplete tensor models, that the correlation coefficients {(a,, 2² : E [K]} can naturally be split into two groups. Lemma 11 (RIP-induce partitioning of correlation coefficients). Suppose that A = [al]... ... [ax] E
D K satisfies the (p. RIP for = Dc log(K)) Let čσ := (1 + 8)/c8. Then all x E 81-11 [ with cardinality p such that
there is subset of indices I(x) C
(a., x²² < 1+8 8 and () < čة log(K)
1 1-
Σ (EZ(z)
for i & I(z),
(16)
D
Let us now collect all assumptions needed to analyze the overcomplete case.

---

10P 00 13P 10
0.5
14 108
x
0.4
201
10'
Figure The average smallest eigenvalue of the Grammian (Gn).) (at, az) for random ensemble d1,- .....,a.g, .a consisting of independent copies of the random vector a Unif($D-1), over 100 runs per K, D, n. From left to right, we consider different tensor orders n = 2, 3, 4. As long as K S C(n) for some constant C(n) depending only on (red line), inverting the Grammian well-posed and the smallest eigenvalue of G,, is bounded from below, in accord with Conjecture 15
Definition 12. Let A [a1l... |ag]. We require the following assumptions:
A1 There exists Go 0, depending only on 6, such that A is
A2 There exists c > 0, independent of K, D, such that maxi ()) S ai log( (K)/D)
A3 There exists C2 0, independent of K, D, such that || cz.
To the best of our knowledge, there are no known deterministically constructed systems of size K o( mm/2)) which satisfy A1 A3 for small < 1 and constants сą, c1 C2 that do not depend on K. D. However, by modeling components via a sufficiently-spres considering an average case scenario with a; ~ Unif(SD-1), they hold with high probability.
random vector, i.e., by
Proposition 13 AA A3 for random ensembles). Let
Unif(sD-1) and assume a1..... ag K independent copies of a, where log(K) = o(D). Fix an arbitrary constant ô (0, 1). There exist constants C 0 and Do N depending only on 8 such that for all D Do, and with probability at least 1 K-1 2 exp(-CC62 -CC conditions A1 and A2 /with 0 S C) hold. Furthermore, if
and K o(D2), A3 holds with probability 1 C(eD/v/D
CVK for 02 C.
Remark 14 AA3 when n > 2). Following 2 15) we give a self-contained proof for A3 when n = in the appendix. We currently able extend the proof
2, because some technical tools such as the Hanson-Wrighe inequality (32] and an extension of 22 Thm. 3.3], which ensures the RIP for matrices whose columns have sub-exponential tails, have not yet been fully developed for random vectors with dependent entries and heavier tails (so-called a-sub-exponential tails or sub- lub-Weibull tails). However we strongly believe that A3 holds for this as conjecture, supplemented with numerical evidence presented in Figure We also add that the conjecture, once proven, would complement recent advances on the well poseddess of random tensors with fewer statistical dependencies among the components g 39
and K o(D)). For now, formulate
Conjecture 15 (Grammians of independent symmetric rank-one tensors). Let 01,..., OKK be inde- pendent copies of the random vector Unif(3D-1) and fix 0 arbitrarily. Then there exists some constant Kop > and an increasing function Th (0, Kn) + (0, 1), both depending only on n, such that Tn (k) + K O, and K S =D for some Kn. we have
P[ 11, 7n (k) +1
D D00
(17)
In particular, Kf o(D") then |G ||2 + 1 as D
We now present our main theorem about local maximizers ISPM-P in the overcomplete case.
Theorem 16 (Main random overcomplete result). Let K, D E N, define eg K log" (K) D and suppose that limp & = O. Assume a1.-.., a, E TR. satisfy A1 for some 8, c,, C2 > 0. Then there exist da, depending only on n, C₁ and c2, and Do. Do. C. which depend additionally on ca. such that if < 8a, D > Do, and AA S Do, the program InSPM-P has exactly 2K second-order critical points the superlevel set
{I S D-1 :F((x) CεK + +5A).
(18)
7

---

85
n 05
2K/02
02
Figure 3: The empirical average of PA(2) over 10000 trials of a random ensemble d1...., K x consisting of K independent copies of the random vector Unif(SP-1) for different scalings of and D. The shaded areas indicate plus/minus one empirical standard deviation.
Each of these critical points is strict local maximizer for F. Further for each such point x", there exists unique E [K] and s E { such that
2
|x - sa:ll3
(19)
Y1
In particular, in the noiseless case A 0), the second-order critical points in the superlevel set (88) are exactly the global maximizers sa, (i E [K], {-1,1])
all non-degenerate local maximizers in the superlevel set 18 are close to global maximizers of the noiseless objective FA. In the noiseless case A A = 0, they coincide with global maximizers and the right hand side in (18) tends to 0 as D oc. Hence, between the global maximizers i Eax and degenerate local maximizers with vanishing ob- jective value, that the objective value acts certificate for the validity of an identified maximizer.
By Theorem T6
have clear separation
Theorem 16 is not a global guarantee because a random starting point Zy Unif(SP-1), used for starting the projected gradient ascent iteration (4) is, with high probability, not contained in (18)
Remark 17 (Objective value at random initialization). For a random sample 20 Unif(S in
the clean case A = O, we empirically observe the objective value (x(x)) = CK/D" as illustrated in Figure 3 As such, we conjecture E Bag..a "tr..ai.....uUuiii -uiitt objective to the level set condition in Theorem I6.
(F)))) O (()K) Comparing the
K log" (K)
I IESD-1 SD-1 :F(x)) 2 C
+ 55AA
(20)
D
random starting point zo therefore falls short of satisfying (20) by log" [K)-ffctor only. In this sense, Theorem 16 furnishes a "near-global" guarantee for inSM-PP in the random overcomplete case.
4.3 End-to-end tensor decomposition
By combining our landscape analyses with bounds for error propagation during deflation, we obtain a theorem about end-to-end tensor decomposition using the SPM algorithm. That is, under the conditions of Theorem or T6 tweaking of SPM (Algorithm in the appendix) recovers the entire CP decomposition exactly the noiseless case (î T). the noisy regime, it obtains an approximate CP decomposition, and we bound the error in terms of A Due to space constraints, we leave precise descriptions Algorithm and our deflation bounds to the supplementary material.
Theorem 18 (Main result on end-to-end tensor decomposition). Let T and M Reshape(T) DD, Dm==]). Let (M) 2 2 (x(M) be the singular vulues of M, and assume a x (M) 0. For other tensor T E Sym((T)), let M Reshape(T, [D", DI)- assume AM := || M1] < foxx(M) (M) and let ÅΛ ox (x(M)-ar AM Suppose that T satisfies the assumptions of either Theorem or Theorem 16 define Do as in the corresponding theorem statement and let A(AA) be the corresponding level set threshold Then there exist constants C2, Cz. not depending on f or AM. such that if we define Å == Ci C2V the following holds. Assume
> >aa E BymmTTm
In both theorem statements, the level set threshold depends AA.

---

PM-P (1 2)
10-10
RSPM-P (n 2
10-10 nSPM-P (n
SSPM-P (n
DF
aVg miny
10
10
10
20
20
40
D
D
(a) Recovering individual tensor components using PM-P and DSPM-P in the noiscless case;
10
89g mil, 18 0.l
10-4
ming, [|a soullz
10-4
10
10-1
10
FM-P (n 2)
10
10
10
10-4
PM.P (u
aSPM-P (x= 2)
aSPM-P
10
00
100
150
200
50
100
150
200
10
10
(b) PM-P and -SPM-P applicd to noisy tensors;
(c) Error of individual recovery with nSPM-P after & deflations.
Figure 4:
Numerical results for symmetric tensor decomposition using PM-P versus DSPM-P The
shaded areas indicate plus/minus one standard deviation. The experiments are described Section
A < Ao and when apply Algorithm I to T each run of projected gradient ascent converges point with functional value least E( A() Then, letting (ū;, {s)EE(K] be the oulput of Algorithm I applied to T, there exist a permutation æ E Porm ()) and signs $1....,
SK E f1,,++1 with
[)((=(()- à S
2
and
m 1
S
2 2/m/n
DA++
4
AA ViE
Am(())
A ok (M)
ok
In particular, in the noiseless case (AM 0), Algorithm returns the exact CP decomposition of
conclude that the Subspace Power Method, with an initialization scheme for nSPM-P that gives R where (x) > ((Aa), is guaranteed algorithm for low-rank tensor decomposition.
5 Numerical experiments
Here we present numerical experiments that corroborate the theoretical findings of Section 4 We illustrate that SPM identifies exact tensor components in the noiseless case (in contrast PM). and that SPM behaves robustly in noisy tensor decomposition. We use the implementation of SPM of the first and third authors, available https: //gi thub com/joaomerree under the MIT license. All of our experiments presented below may be conducted on standard laptop computer within a few hours. where SPM was tested in a variety of other scenarios, justifying it as a possible replacement for wfae-oof-the-ar symmetric tensor decomposition methods such as FOOBI 14 or Tensorlab 44
/SPM, which is licensed
further numerical experiments, we refer the reader 25
Global optimizers and noise robustness. In the first set of experiments, we are interested in the recovery individual tensor components a; for different D, K and m from noisy approximately low rank tensors. With 2n as the tensor order, we create noiseless tensors with a; Unif(s0-11)
the tensor components and X; /Dm/EF ); as the tensor weights, where À; Unif([1/22 2)). This way, the variance of each entry of the tensor is about We construct noisy tensors 7 T by adding independent copies of (00 mlo?) to each entry of the tensor and then project onto

---

Sym(TD") The entries with all distint indices of the projected noise tensor have variance a²: the variance the remaining entries also a multiple of o² and the number of such entries is of D""
After constructing the tensor, we sample 10 points from Unif($D-1) as initializations for projected gradient ascent applied to PM-P and ISPMMP We iterate until convergence and record the distance between the final iterate and the closest =o; among the tensor components. Averages and standard deviations (represented by shaded areas) over 1000 distances (10 distances per tensor, 100 tensors) are depicted in Figures 4a and 4b In Figure 4a we use noiseless tensors with a O, while in Figure 4b ranges from 10 to 1, and the plots for 4th and 6 order tensors are superposed. We set D = 20, K = 100 for the 4th order tensor (n 2) and D 10, K 100 for the 6th order (n 3).
Figure 4a illustrates that projected gradient ascent applied to 1SPM-P always converges to the global maxima in the noiseless case (up to numerical error), provided the scaling is K = O(DIm//l)
O(D2) and the constant adheres to the rank constraints pointed out in [25] Prop. 4.2]. This is in agreement with Theorem 16. which shows local maxima with sufficiently large objective have to coincide with global maximizers. In the noisy case, Figure 4b illuttrates the robustness of P-PPM-P giving an error of O(r). In contrast to nSPM-P the PM-P objjective suffers from large bias and does not recover exact tensor components. The effect of the bias even dominates errors induced by moderately-size sized entrywise noise.
Deflation with SPM. In the second experiment, we recover complete tensors by using the deflation procedure described in (25). We are mostly interested in the noisy case, since deflation with exact a,'s, as identified by ISSMM-Pin in the noiseless case, does not induce any additional error.
We test 4th order tensors (n 2) with D 40, K 200 and 6th order tensors (n = 3) with D = 15, K = 200, vary the noise level a, and construct random tensors as in the previous experiment. Figure plots the average error over 100 repetitions of successively recovered tensor components, where the r-axis ranges from the first recovered component at 1 to the last component at index 300. The figure illustrates that MSPM-P combined with modified deflation allows for recovering all tensor components up to an error of O(ar). Surprisingly, we do not observe error propagation, despite the fact that noisy recovered tensor components are being used within each deflation step.
6 Conclusion
We presented a quantitative picture for the optimization landscape of a recent formulation (25 of the non-convex. digh-dimensional problem of symmetric tensor decomposition. We identified different assumptions on the tensor components 01, ag and bounds on the rank K so that all second-ord order critical points of the optimization problem SPMMP with sufficiently high functional value must equal one of the input tensor's ' CP components. In Theorem the assumptions were deterministic frame and low-rank conditions, while in Theorem 16 the hypotheses overcomplete rank. Our proofs accommodated noise in the input tensor's 's entries, and we obtained robust results for only by analyzing the program ISPMMPP Our analysis has algorithmic implications. As the Subspace Power Method of 25 is guaranteed to converge to second-order critical points, by combining with analysis of deflation, follows that SPM (with sufficient initialization) is provable under our assumptions. In Theorem 18 we gave guarantees for end-to-end decomposition using SPM.
random components and an
Compared to the usual power method functional, the novelty of the SPM functional is the di-biiging role played by the inverse of Grammian matrix recording correlations hetween rank-1 tensors (recall Eq. (8) ). This Grammian matrix is responsible for many of the SPM functional's 's desirable properties, but it also complicated our analysis. We showed that there are theoretical and numerical advantages in using the SPM functional for tensor decomposition over its usual power method counterpart.
This paper suggests several directions for future research:
What are the average-case properties of the Grammian matrix G,,? We formulated Conjec- ture 15 about the minimal eigenvalue of G,, How about the other eigenvalues?
In the random overcomplete setting, if we assume no noise (Аx = 0) then can we dispense with the superlevel condition in Theorem T6p This would give a fully global guarantee.
Why do we see no error propagation when using deflation and sequential solves of SSPMP for CP decomposition? Can errors accumulate if we choose the noise deterministically?
10

---

Acknowledgements and funding disclosure
We thank Massimo Fornasier for suggesting this collaboration the beginning, after a fortuitous exchange in Oaxaca, Mexico at the Computational Harmonic Analysis and Data Science workshop (October 2019). J.K. acknowledges partial support from start-up grants provided by the College of Natural Sciences and Oden Institute for Computational Engineering and Sciences at UT Austin.
References
[1] P.-.. Absil, R. Mahony, and R. Sepulchre. Oprimization Algorithms on Matrix Manifolds. Princeton University Press, 2009.
[2] R. Adamezak, A. E. Litvak, A. Pajor, and N. Jannzzak-Jegermaann Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Constructive Approximation, 34(1):61-88 1866118822200 2011.
[3] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgansky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(80):2773- 2832, 2014.
[4] A. Anandkumar, R. Ge. and M. Janzamin. Analyzing tensor power method dynamics in overcomplete regime. The Journal of Machine Learning Research, 18(1):752-79) 2017.
[5] A. Anandkumar, D. Hsu, and S. M. Kakade. A method of moments for mixture models hidden Markov models. In Conference on Learning Theory, pages 33-1. JMLR R Workshop and Conference Proceedings, 2012.
[6] A. Auddy and M. Yuan. Perturbation bounds orthogonally dccomposable tensors and their applications in high dimensional data analysis. arXiv preprint vrXiv:2007.09022 2020.
[7] A. S. Bandeira, A. Perry, and A. S. Wein. Notes computational-toosttiiiiiit gaps: Predictions using statistical physies. Portugaliae Mathematica, 75(2):159-186, 2018.
[8] J. Bryson, R. Vershynin, and H. Zhao. Marchenko-pasee law with relaxed independence conditions. arXiv preprint arxiv 1912 2019.
Y. M. Chen, X. S. Chen, and W. Li. On perturbation bounds for orthogonal projections. Numerical Algorithms, 73(2)4333444, 2016.
[10] L. Chiantini and C. Ciliberto. Weakly defective varieties. Transactions of the American Mathematical Society, 354(1))151-178, 2002.
[11] O. Christensen et al. An Introduction to Frames and Riesz Bases, volume Springer, 2003.
[12] M. T. Chu, R. E. Funderlic, and G. H. Golub, A rank-one reduction formula and its applications to matrix factorizations. SIAM Review, 37(4):512-553 1995.
[13] P. Comon, G. Golub, L.-H. Lim, and B. Mourrain. Symmetric tensors and symmetric tensor rank. SIAM Journal on Matrix Analysis and Applications, 3033):1254-12777 2008.
[14] L. De Lathauwer, J. Castaing, and J.-F. Cardoso. Fourth-order cumulant-based blind identification of underdetermined mixtures. IEEE Transactions on Signal Processing. (5(6):2965-2977 2007.
[15] A. Fengler and P. Jung. On the restricted isometry property of centered self Khatri-Rao Rao products. arXiv preprint arv:v: / 1905.09245, 2019.
[16] Fickus, D. G. Mixon, and C. Tremain. Steiner equiangular tight frames. Linear Algebra and its Applications, 1014 1027, 2012.
[17] C. Fiedler, M. Fornasier, T. Klock, and M. Rauchensteiner. Stable recovery of entangled weights: Towards robust identification of deep neural networks from minimal samples. arXiv preprint arXiv:2101.071 2021.
[18] M. Fornasier. T. Klock, and M. Rauchensteiner. Robust and resource efficient identification of two hidden layer neural networks. Construction Approximation, appear, 2021.
[19] M. Fornasier, J. Vybíral, and Daubechics. Robust and resource efficient identification of shallow neural networks by fewest samples. Information and Inference: A Journal of the IMA, 2021.
[20] R. Ge, Huang, and S. M. Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pages 761-770, 2015.
[21] R. Ge and T. Ma. On the optimization landscape of tensor decompositions. Mathematical Programming, pages 1-47, 2020.
[22] Harris. Algebraic Geometry: First Course, volume 133. Springer Science Business Media, 2013.
[23] C. J. Hillar and L.-H. Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM), 60(6):45:1-
45:39, 2013.

---

[24] M. Janzamin, H. Sedghi, and A. Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint urXiv:1506.08473. 2015.
[25] Kileel and J. M. Percira. Subspace power method for symmetric tensor decomposition and generalized PCA. arXiv preprint arXiv:1912.0400) 2019.
[26] T. G. Kolda. Numerical optimization for symmetric tensor decomposition. Mathematical Progranming,
15 (1(())222-- 2015.
[27] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, (1(3):455--55 500,
2009.
[28] T. G. Kolda and J. R. Mayo. An adaptive shifted power method for computing generalized tensor eigenpairs.
SIAM Journal on Matrix Analysis and Applications, 35(4): 1563-1811, 2014.
[29] P. McCullagh. Tensor Methods in Statistics. Courier Dover Publications, 2018.
[30] S. Oymak and M. Soltanolkotabi. Learning a deep convolutional neural network via tensor decomposition. Information and Inference: A Journal of the IMA, 2021.
[31] Q Qu, Zhai, X. Li, Y. Zhang, and Z. Zhu. Geometric analysis of nonconvex optimization landscapes for overcomplete learning. International Conference on Learning Representations. 2019.
[32] M. Rudelson and R. Vershynin. Hanson-Wright inequality and sub-Gaussian concentration. Electronic Communications in Probability, 18, 2013.
[33] M. Sanjabi, S. Baharlouei, M. Razaviyayn, and J. D. Lee. When does non-orthogonal tensor decomposition have no spurious local minima? arXiv preprint arXiv:/911 1.0099/,, 2019.
[34] H. Sedghi, M. Janzamin, and A. Anandkumar. Provable tensor methods for learning mixtures of generalized
linear models. Artificia Intelligence and Statistics, pages 1223-1231. PMLR, 2016.
[35] S. Sherman and T. G. Kolda. Estimating higher-order moments using symmetric tensor decomposition. SIAM Journal on Matrix Analysis and Applications, 4 (333):366-1138) 2020.
[36] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. Papalexakis, and Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):35113382 2017.
[37] Sustik, J. A. Tropp. I. S. Dhillon, and W. Heath the existence of equiangular tight frames. Linear Algebra and its Applications, 426((-3):619 335, 2007.
[38] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3022 2010.
[39] R. Vershynin. Concentration inequalities for random tensors. Bernoulli, 26(4):3139-3162 2020.
[40] N. Vervliet, O. Debals, L. Sorber, M. Van Barel, and L. De Lathauwer. Tensorlab 3.0. Available online. URL: http://www.teensorlab..tt 2016.
[41] S. R. White. Density matrix formulation for quantum remormalization groups. Physical Review Letters, 69(19)22863, 1992.
[42] Zhong, Z. Song, P. Jain, P. L. Bartlett, and Dhillon. Recovery guarantees for one- me-hidden--aan neural networks. In International Conference on Machine Learning, pages
PMLR, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The main limitations of our work are that do not obtain completely global understanding of ISPPSM-P in the
overcomplete case nor vanishing error propagation after using deflation in random noise models. These points discussed transparently in the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space con- straints, most proofs are included in the supplementary material.
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] We will upload the Matlab code for conducting our experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We run 100 repititions of each conducted experiment and report mean, 1/4, and 3/4 quantiles.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] All experiments in the main submission can be conducted on personal laptop with Intel Core i7-7700HQ CPU and 16.0GB of RAM in less than an hour.
4. If you using existing assets (e-g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did cite the creators? [Yes] We use the imple- mentation the SPM algorithm by Kileel and Pereira and properly cite their work.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wPysF5Svya4", "reviewer": "Reviewer_4wNn", "summary": "This paper considers the subspace power method (SPM) for symmetric tensors.\nSpecifically, this paper analyzes the non-convex optimization landscape associated with the SPM objective.\nThe 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.", "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": "\nMajor concern:\n(1) Theorem 6, the requirement (10) is too restrictive.\nWhen n is relatively large,  (10) implies that rho_2 is tiny, as a result, all components  a_i's are almost orthogonal.\nTo be more specific,  let us relax the requirement (10) a little bit, say rho_2 <= 1 / (8n^2).\nSet  K=2 (only two components a_1 and a_2), assume the angle between a_1 and a_2 is pi/3, \nthen it is easy to see that rho_2 = 2 * (cos pi/6)^2  - 1 = 0.5. \nHowever, 0.5 > 1 / (8n^2) for all n>= 2.\nWhen all components  a_i's are almost orthogonal, it is not surprising to draw the conclusion of Theorem 6.\nI would like to raise my score if the authors are able to convince me that the requirement (10) is not restrictive.\n\n(2) Theorem 15 is established under the assumption A3, which is only shown for n=2. The authors formulate the result as conjecture 14.\nIt 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.\n\nMore comments\n\n(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).\n\n(2) Lemma 1, eqn (3).  If F norm is used, \\Delta_T in the denominator should be replaced by ||M - \\hat M||_2.\nIf 2-norm is used,  \\Delta_T in both numerator and denominator should be replaced by ||M - \\hat M||_2.\nThe inequality between Lines 38 and 39 in the supplementary, the term pi/2 can be removed. \nTherefore, the bound in Lemma 1 can be improved.\n\n(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. \nL. Qi, “The best rank-one approximation ratio of a tensor space”,SIAM Journalon Matrix Analysis and Applications, 32 (2011) 430-432.\nFurthermore, it is unclear that such a procedure is able to find all components.\n\n(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?\n\n(5) To make the numerical experiments more convincing, try larger n, rather than simply set m=4 (n=2).\n\nI am satisfied with the authors' replies, and raised the score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Q9pWXCbB2Va", "reviewer": "Reviewer_ABgz", "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.\n\nThe contributions is to analyze the landscape of SPM-P by characterizing all second-order critical points.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "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": "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors give some \"near-global\" guarantee under a random tensor model and the deterministic frame conditions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "FxI4ZcirQat", "reviewer": "Reviewer_pP73", "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.\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": "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.\n\n* Pros: \nThis 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).\n\n* 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?\n\nIn 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?\n\n* Relation to Literature. There are several recent related results that are missing in reference, and it would better to be discussed:\n\n``Maziar Sanjabi, Sina Baharlouei, Meisam Razaviyayn, Jason D. Lee When Does Non-Orthogonal Tensor Decomposition Have No Spurious Local Minima?''\n``Qing Qu, Yuexiang Zhai, Xiao Li, Yuqian Zhang, Zhihui Zhu Geometric Analysis of Nonconvex Optimization Landscapes for Overcomplete Learning''\nIn 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Described in the question part in the main review.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "9lvdcklD10G", "reviewer": "Reviewer_diJc", "summary": "This paper analyzes a different optimization problem for the task of finding one scaler/vector pair.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "I am not familiar with this kind of work. I have one question concerns the deflation procedure. \n\nSo 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)